- 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
- Improved accuracy with reduced model usage. The efficiency evaluation on Shopping Planning demonstrates a favorable relationship between planning performance and inference resource consumption.
- 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
-
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.
-
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.
-
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
- 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
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
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.
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:
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:
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.
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.