acceptodds
Under review as a conference paper at ICLR 2027

HyperMCTS: Hypergraph-Augmented MCTS for Long-Horizon LLM Agents

Abstract

Long-horizon tasks require large language model (LLM) agents to coordinate decisions under constraints that span an entire solution. Monte Carlo Tree Search (MCTS) offers a promising approach to test-time scaling by exploring alternative action trajectories, but model computation and environment interaction make search costly. Efficient search therefore requires effective reuse of trajectory feedback. Standard MCTS maintains prefix-specific statistics, without explicitly accumulating outcomes for decision groups that recur across different paths. To fill this gap, we propose HyperMCTS, a training-free method that augments an ordered MCTS tree with a cross-trajectory hypergraph. Hyperedges represent groups of canonical decisions and accumulate their observed returns within the current task. Our hypergraph-guided HyperUCT selection rule aggregates evidence from overlapping hyperedges into an action prior, allowing outcomes collected under one prefix to inform selection under another while preserving execution histories in the tree. On DeepPlanning, HyperMCTS improves average planning accuracy by 2.3–7.3 percentage points over the strongest baseline for each of three backbone models. It enables Qwen3.6-27B to outperform Claude Opus 4.6 (max) on Shopping Planning, while achieving higher accuracy with fewer LLM calls and output tokens than the evaluated MCTS-based baselines. SealQA experiments further demonstrate improvements in question answering.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Long-Horizon Planning, Test-Time Scaling, Agentic Planning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_5eLxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents HyperMCTS, a training-free augmentation of MCTS for long-horizon LLM agents that adds a cross-trajectory hypergraph capturing unordered groups of canonicalized decisions. Experiments on DeepPlanning (Travel, Shopping) across three backbone LLMs and on SealQA show consistent gains over strong structured and unstructured test-time scaling baselines, improved search efficiency in LLM calls/tokens versus MCTS variants, and ablation/sensitivity analyses that attribute a substantial portion of the improvement to the hypergraph component.

Critical strengths
  1. Improved accuracy with reduced model usage. The efficiency evaluation on Shopping Planning demonstrates a favorable relationship between planning performance and inference resource consumption.
  2. The problem framing is clear and well-motivated: the gap between partial-credit scores and Case Accuracy illustrates why constraint-coupled planning needs search, and the observation that standard MCTS statistics are prefix-local and cannot pool outcomes of recurring decision groups identifies a real limitation.
Critical weaknesses
  1. Missing fine-grained ablations of the hypergraph design. The hypergraph has several components whose contributions are never separated: trajectory-level versus objective-level hyperedges, the Jaccard-based merging of similar decision sets, and the aggregation rule. The only ablation reported is the full hypergraph on versus off, and the only sensitivity study is over λ. The paper also does not state whether the Jaccard merge was enabled in the reported experiments. Without these ablations, it is unclear which design choices matter, and whether the specific aggregation heuristics are better than simpler alternatives such as a count-weighted mean.

  2. The ablation cannot attribute the gain to the hypergraph. Hypergraph statistics are used in two places: the additive term in the selection rule, and a “domain-specific guidance” component that also reads these statistics and makes extra LLM calls but is never described. The paper itself notes that removing the hypergraph requires disabling this guidance as well, not just setting λ = 0, and that the ablation evaluates the hypergraph as a whole. The reported gap therefore reflects both mechanisms removed together.

  3. Missing best-of-N control. The final answer is selected by the verifier as the highest-reward trajectory among the five evaluated, so part of the gain may come from verifier-based selection rather than from structured search.

Questions for authors
  1. What exactly does the domain-specific guidance do? Which hypergraph statistics does it serialize, where are they injected (candidate generation, simulation policy, tie-breaking, stopping), and how many LLM calls per rollout does it add?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 5eLx

Thank you for highlighting HyperMCTS's search efficiency and the motivation for sharing feedback across recurring decision groups.

W1. Fine-grained hypergraph design.

Thanks for these suggestions! Given the limited time for rebuttal, we evaluated the edge types, merging strategy, and aggregation rule on 50 Shopping Level-1 cases using Qwen3.6-27B and a five-rollout budget. The results are summarized below.

ConfigurationCase AccuracyMatch Score
HyperMCTS62.0%88.8%
Objective-level edges only58.0%84.2%
Trajectory-level edges only60.0%87.4%
Jaccard merging disabled54.0%85.6%
Count-weighted mean aggregation56.0%82.8%

Jaccard merging was enabled in the reported configuration, with a threshold of 0.8. The default aggregation combines the maximum objective-edge value and the mean trajectory-edge value with weights 0.7 and 0.3, respectively. When only one edge type is available, its score is used. We will make these settings explicit and include the detailed component comparisons in the revised paper.

W2 / Q1. Guidance and attribution.

We would like to clarify that constructing the domain-specific guidance requires no separate LLM call. It deterministically converts existing hypergraph statistics into a short prompt such as:

  • Product IDs associated with objective-level edges having Q ≥ 0.5.
  • Product IDs with Q < 0.4 after at least two observations.
  • Requirement labels associated with the high-scoring edges.
  • A flag indicating whether a trajectory-level edge has Q ≥ 0.5.

This summary is prepended once, before the first model call of each rollout, and conditions candidate generation. It adds input tokens but makes no separate model request. It does not implement tie-breaking or stopping.

We also separated the numeric prior and prompt guidance in a four-condition comparison on the same 50 cases:

Numeric priorPrompt guidanceCase AccuracyLLM callsOutput tokens
OnOn62.0%101213K
OnOff54.0%121246K
OffOn46.0%112228K
OffOff54.0%114235K

The full configuration uses the fewest LLM calls and output tokens among the four settings. Compared with disabling both mechanisms, it reduces calls by 11.4% and output tokens by 9.4%. Disabling either pathway increases both costs, supporting the benefit of combining numeric prior and prompt guidance for search efficiency.

W3. Best-of-N baseline.

Thanks for suggesting this comparison. We evaluated Best-of-N with N = 5, generating five independent ReAct trajectories per case and selecting the highest-scoring trajectory with the search-time verifier. Results on DeepPlanning Shopping (120 cases, Qwen3.6-27B) are below.

MethodCase AccuracyMatch Score
Best-of-N (N = 5)56.7%85.0%
Our HyperMCTS60.8%87.0%

HyperMCTS scores 4.1 percentage points higher in Case Accuracy and 2.0 points higher in Match Score. Both methods use verifier-based final selection; HyperMCTS also reuses earlier rollout feedback to guide subsequent trajectory construction.

We will include this comparison in the revised paper.

AuthorsOpenReview ↗

A Kind Reminder on Following up

Dear Reviewer 5eLx,

We would like to kindly follow up on our rebuttal. We have made significant efforts to address your concerns, including: (1) Adding fine-grained ablations of edge types, merging, and aggregation; (2) Separately evaluating the numeric prior and prompt guidance, and clarifying that constructing guidance requires no separate LLM call; (3) Adding a Best-of-5 comparison using independent ReAct trajectories and the same verifier.

We would greatly appreciate your feedback on whether these additional results and explanations address your concerns. If so, we hope you will consider revising your score accordingly. Please let us know if any points would benefit from further clarification.

Best regards, The Authors

Reviewer_SWM3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an improvement to MCTS for LLM exploration to improve estimates for actions taken in previous trajectories but in a different order. They compare it to typical mechanisms that scale test time compute as well as some MCTS variants.

Critical strengths

The idea to improve standard MCTS for LLMs is good.

Critical weaknesses

Only one seed with B=5 trajectories is not enough, furthermore there are no error bars computed anywhere. This paper doesn’t involve expensive LLM training, so error bars would definitely be needed, as well as more this is something that I would expect.

The algorithm is very similar, if not identical, to Gelly and Silver RAVE + AMAF, and the paper doesn’t compare to it.

Questions for authors

How does this differ from Rapid Action Value Estimation (RAVE) plus All Move As First (AMAF) (Gelly and Silver, 2011)? From what I understand the underlying mechanism is exactly the same, and the authors even cite the paper, but do not compare it in any way. It seems to me the two may be following basically the same algorithm.

Furthermore if we were to increase the number of trajectories, standard MCTS would then become more accurate, Gelly and Silver have a specific decay term to account for this, so that their algorithm becomes more similar to MCTS as more trajectories are explored.

3 comments
AuthorsOpenReview ↗

Response to Reviewer SWM3

We sincerely thank the reviewer SWM3 for the constructive feedback and recognizing the value of improving MCTS for LLM agents.

W1. Robustness

We evaluated Qwen3.6-27B with three random seeds and report the sample standard deviation of Case Accuracy across runs as below. Standard deviations are higher for Travel across all methods. One possible explanation is that Travel tasks involve longer sequences of interdependent decisions, giving early errors more opportunities to propagate and affect whether the final itinerary satisfies all constraints.

MetricReActCoTReflexionToTRAPLATSFLAREOur HyperMCTS
Travel Case Accuracy10.4%11.7%21.7%20.4%22.5%24.2%20.0%33.8%
Travel Std. (pp)3.182.062.892.713.542.373.312.29
Shopping Case Accuracy46.7%51.7%51.7%51.7%57.5%53.3%53.3%60.8%
Shopping Std. (pp)2.501.272.411.672.551.732.681.44

W2 / Q1. Distinction from RAVE and AMAF.

This is a very good question! Thanks for bringing up RAVE [1].

RAVE shares feedback across rollouts through prefix-conditioned, individual-action estimates. Our HyperMCTS utilize hypergraph to maintain decision-group shared across tree prefixes (§3.2). The same group accumulates evidence from different action orders and branches, while overlapping groups retain distinct return estimates. HyperUCT aggregates this group-level evidence into an action prior (§3.3).

We also implemented MCTS+RAVE with node-local AMAF updates and a visit-dependent mixing schedule. Given the limited time, we focus on DeepPlanning Shopping (120 cases, Qwen3.6-27B, five-rollout budget), with the new RAVE results shown below. We will include more experimental results in the revised paper.

MethodCase AccuracyMatch Score
MCTS+RAVE55.8%83.7%
Our HyperMCTS60.8%87.0%

Q2. Decay of the hypergraph prior.

Thanks for this helpful suggestion! We agree that the balance between shared feedback and local tree estimates should account for the evidence accumulated during search. Our current experiments use a fixed hypergraph weight λ to study decision-group sharing under finite inference budgets.

Following the idea behind RAVE's decay, we will explore adaptive weighting based on node visit counts and estimate confidence in future work. This would allow stronger use of shared feedback at sparsely visited prefixes and gradually reduce its influence as local estimates become better supported, adapting the balance to different search budgets.

[1] Gelly, S., and Silver, D. (2011). Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, 175(11), 1856–1875.

AuthorsOpenReview ↗

A Kind Reminder on Following up

Dear Reviewer SWM3,

We would like to kindly follow up on our rebuttal. We have made significant efforts to address your feedback, including: (1) Discussing robustness across random seeds; (2) Clarifying the distinction from RAVE/AMAF and adding a dedicated MCTS+RAVE comparison; (3) Discussing adaptive prior weighting to balance shared feedback and local tree estimates as search progresses.

We would be grateful for your feedback on whether these responses resolve your concerns. If so, we hope you will consider updating your assessment and score. We would also be happy to clarify any remaining questions.

Best regards, The Authors

Thank you for the response and clarifications. I will review these points carefully and take them into account during the reviewer–AC discussion period.

Reviewer_t8uAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes HyperMCTS, a training-free method that augments MCTS with a hypergraph to share feedback across search trajectories. The search tree preserves ordered interaction histories, while the hypergraph records groups of canonical decisions and their observed returns. During action selection, the proposed HyperUCT rule combines tree-local values and an exploration bonus with an action-level prior aggregated from relevant hyperedges. After each rollout, its reward updates both structures, and the method returns the evaluated trajectory with the highest reward.

The authors evaluate HyperMCTS on travel and shopping planning in DeepPlanning and question answering in SealQA using three backbone models. HyperMCTS achieves higher average planning accuracy than the strongest baseline for each model and higher shopping accuracy with fewer calls and output tokens in the evaluated efficiency configurations.

Critical strengths
  • Across all three models, the proposed method achieves higher average accuracy across travel and shopping planning than the strongest baseline for each model. Removing the entire hypergraph component also reduces performance on all three models, supporting its effectiveness in the evaluated settings.

  • On shopping tasks, HyperMCTS achieves higher accuracy with fewer LLM calls and output tokens across the compared configurations. This suggests that the gains do not simply come from increased inference compute.

Critical weaknesses
  • Although the method records groups of actions, it ultimately aggregates the statistics of hyperedges containing each action into a single action-level score. Comparisons with directly sharing individual action returns and sharing only pairwise information are needed to establish the additional benefit of higher-order representations. The existing ablation supports the usefulness of the overall sharing component, but does not establish the necessity of a hypergraph.

  • In Table 1, average planning accuracy improves from 34.2% to 36.9% on Qwen3.5-27B and from 39.2% to 41.5% on Sonnet 4.6—gains of 2.7 and 2.3 percentage points, respectively. On SealQA, the gains over the strongest baseline are 2.7 points for Qwen3.6-27B and 3.6 points for Sonnet 4.6, corresponding to approximately three and four additional correct answers on the 111-question evaluation set. Without repeated runs or confidence intervals, it is difficult to determine how robust these differences are to search randomness and evaluation-sample variation.

  • Credit assignment is coarse: the same terminal reward is assigned to all relevant decisions. Sharing these statistics across trajectories may propagate misleading feedback.

  • Hypergraph construction relies on domain-specific choices, including action canonicalization and associations between decisions and objectives. More implementation details and evaluation are needed to assess its generalizability.

Questions for authors

The default configuration uses a branching factor of 3 and at most 5 search iterations. Unvisited expanded actions receive an infinite score and are therefore explored first. With such a small budget, many selections may be determined by this rule rather than by the HyperUCT scores. How often does the hypergraph prior actually influence action selection under this configuration?

2 comments
AuthorsOpenReview ↗

Response to Reviewer t8uA

Thank you for highlighting HyperMCTS's planning accuracy and search efficiency.

W1. Decision-group sharing.

Figure 2 illustrates what the hypergraph stores. Selecting the same three products in different orders updates one hyperedge. Swapping the webcam updates a different hyperedge, with both groups sharing the monitor and keyboard. We observed this kind of recurrence in practice. In 56 of 120 Shopping cases (46.7%), the same product group appeared in different orders across rollouts. HyperUCT aggregates these group-level returns into an action prior (§3.2–3.3).

As there is no action-level sharing control among existing baselines, we constructed a dedicated MCTS+RAVE baseline by integrating Rapid Action Value Estimation (RAVE [1]) into MCTS framework. RAVE shares rollout returns through node-local action estimates, providing a comparison with the cross-trajectory decision-group sharing introduced by Our HyperMCTS. On DeepPlanning Shopping (120 cases, Qwen3.6-27B, five-rollout budget), MCTS+RAVE achieves 55.8% Case Accuracy and 83.7% Match Score. Our HyperMCTS achieves 60.8% and 87.0%, respectively.

W2. Robustness.

We evaluated Qwen3.6-27B with three random seeds and report the sample standard deviation of Case Accuracy across runs as below. Standard deviations are higher for Travel across all methods. One possible explanation is that Travel tasks involve longer sequences of interdependent decisions, giving early errors more opportunities to propagate and affect whether the final itinerary satisfies all constraints.

MetricReActCoTReflexionToTRAPLATSFLAREOur HyperMCTS
Travel Case Accuracy10.4%11.7%21.7%20.4%22.5%24.2%20.0%33.8%
Travel Std. (pp)3.182.062.892.713.542.373.312.29
Shopping Case Accuracy46.7%51.7%51.7%51.7%57.5%53.3%53.3%60.8%
Shopping Std. (pp)2.501.272.411.672.551.732.681.44

W3. Credit assignment.

This is precisely the credit-assignment challenge HyperMCTS addresses in long-horizon LLM planning. Standard MCTS backs up the same terminal return along the rollout path and stores the resulting action values at individual tree prefixes. In DeepPlanning, many outcomes depend on decisions made far apart in that path. For example, a flight may fit the budget with one hotel and exceed it with another. HyperMCTS records the return for the observed decision group, so combinations that share the same flight can have distinct return estimates. HyperUCT reuses this group-level evidence across rollouts and combines it with the tree value at the current prefix (Appendix A.2 and §3.3).

W4. Domain-specific construction.

Appendices A.2–A.3 describe the decision identities used across domains. Shopping uses product IDs and links them to parsed requirements such as a requested brand. Travel records staged choices such as transport and accommodation. SealQA uses ReAct action types and arguments. The same hypergraph update rule operates on the decision identities supplied by each domain.

Q1. The prior.

Equation (11) gives unvisited children priority during tree descent. This follows the standard UCT convention [2]. UCT/UCB-based exploration is also used by prior LLM planning methods, including RAP [3], LATS [4], and FLARE [5]. The prior can affect the ranking once all expanded children at a node have been visited. Crucially, tree descent is only one point where the prior is used. In Shopping, candidate continuations within a rollout are scored using the progress score plus the hypergraph prior. Earlier rollout returns can therefore inform candidate scores before a tree node is revisited. A five-rollout budget still permits multiple branch comparisons within each trajectory. Sparse tree revisits therefore do not imply that hypergraph feedback is inactive. Our reported ablation further shows that removing the hypergraph reduces planning accuracy across all three backbones, supporting the effectiveness of cross-trajectory sharing under the evaluated search budgets.

References

[1] Gelly, S., and Silver, D. (2011). Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, 175(11), 1856–1875.

[2] Browne, Cameron B., et al. "A survey of monte carlo tree search methods." IEEE Transactions on Computational Intelligence and AI in games 4, no. 1 (2012): 1-43.

[3] Hao, Shibo, et al. "Reasoning with language model is planning with world model." In Proceedings of the 2023 conference on empirical methods in natural language processing, pp. 8154-8173. 2023.

[4] Zhou, Andy, et al. "Language agent tree search unifies reasoning acting and planning in language models." ICML 2024.

[5] Wang, Zehong, et al. "Why reasoning fails to plan: A planning-centric analysis of long-horizon decision making in llm agents." arXiv preprint arXiv:2601.22311 (2026).

AuthorsOpenReview ↗

A Kind Reminder on Following up

Dear Reviewer t8uA,

This is a gentle reminder to follow up on our rebuttal. We have made significant efforts to address your concerns, including: (1) Adding an MCTS+RAVE comparison to evaluate action-level sharing; (2) Reporting three-seed results with standard deviations to assess robustness; (3) Clarifying credit assignment, domain-specific construction, and the prior’s role under a five-rollout budget.

We would greatly appreciate your feedback on whether these additional results and clarifications address your concerns. If these have addressed your concerns, we hope you will consider revising your score accordingly.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.