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.
Figures & tables
Figure 1: (a) A recorded DeepPlanning Travel failure despite 93.8% Comp Score. (b) An independent schematic under a $600 budget: Paths 1 and 2 construct the same flight–hotel combination in different orders; Path 3 changes the hotel. Returns 0.9 and 0.2 are illustrative feedback, not measurements or values derived from the budget check.
Figure 2: HyperMCTS illustrated with shopping decisions. (a) Four rollouts through a tree of commit actions. (b) Shared and overlapping action groups accumulate counts and mean feedback across trajectories. (c) At the highlighted history h , HyperUCT combines tree-local UCT (blue) with a prior obtained by aggregating incident-hyperedge statistics (gray). Ri denotes symbolic search-time feedback; costs indicate budget feasibility only. The panels show successive operations. Only trajectory-level hyperedges are drawn; search-iteration subscripts are omitted.
Model
Agent
DeepPlanning
SealQA
Travel
Shopping
Avg Acc.
Acc.
CS Score
PS Score
Comp Score
Case Acc.
Match Score
Case Acc.
Qwen3.6-27B
ReAct
77.2
71.3
74.2
10.4
82.0
46.7
28.6
13.5
CoT
76.2
67.1
71.7
11.7
83.6
51.7
31.7
14.4
Reflexion
82.0
75.4
78.7
21.7
84.8
51.7
36.7
14.4
ToT
84.4
80.8
82.6
20.4
84.1
51.7
36.1
17.1
Table 1: Results (%) on DeepPlanning and SealQA. Avg Acc. averages Travel and Shopping Case Accuracy. Bold marks the best result per metric and model, including ties.
Figure 3: Accuracy–cost trade-offs of MCTS-based methods on Shopping Planning ( 120 cases, Qwen3.6-27B, thinking mode). Costs are rounded per-case averages. Labels denote branching factors 2 , 3 , and 6 ; lines connect configurations of the same method.
Figure 4: Hypergraph ablation on DeepPlanning, comparing MCTS (w/o hypergraph) and HyperMCTS (w/ hypergraph).
Figure 5: Sensitivity to the hypergraph weight λ on Travel Planning. Each curve shows one backbone model with B=5 , b=3 , and c=1.414 .
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
x , ht , τ
Query, observable interaction history, and complete or horizon-terminated trajectory
H , B , b
Interaction horizon, search-iteration budget, and expansion branching factor
πθ , Adec(h)
Frozen proposal policy and task-defined search decisions
V , R(τ)
Terminal search verifier and trajectory reward
G , Y
Query objectives and hyperedge labels
U , ϕ , C(τ)
Canonical decision space, canonicalization map, and recorded decision set
Appendix
Table 2: Core notation for the search tree and cross-trajectory hypergraph.
Model
Agent
ZH
EN
Overall
CS Score
PS Score
Comp Score
Case Acc.
CS Score
PS Score
Comp Score
Case Acc.
CS Score
PS Score
Comp Score
Case Acc.
Qwen3.6-27B
ReAct
74.7
76.7
75.7
7.5
79.6
65.8
72.7
13.3
77.2
71.3
74.2
10.4
CoT
73.3
72.5
72.9
6.7
79.1
61.7
70.4
16.7
76.2
67.1
71.7
11.7
Reflexion
79.5
85.8
82.7
15.8
84.5
65.0
74.8
27.5
82.0
75.4
78.7
21.7
ToT
82.4
86.6
84.5
15.8
86.4
75.0
80.7
25.0
84.4
80.8
82.6
20.4
RAP
79.7
82.8
81.3
22.5
81.2
75.0
78.1
22.5
80.5
78.9
79.7
22.5
Appendix
Table 3: Travel Planning, per-language breakdown (%) with all models in thinking mode. CS Score (Commonsense Score), PS Score (Personalized Score), Comp Score (Composite Score), and Case Acc. (Case Accuracy) follow the definitions in the main text. For each model and language group (including Overall), the best value of every metric is in bold , including ties.
Level
Agent
Qwen3.6-27B
Qwen3.5-27B
Sonnet 4.6
Match Score
Case Acc.
Match Score
Case Acc.
Match Score
Case Acc.
L1 ( n=50 )
ReAct
84.7
46.0
83.3
46.0
75.3
36.0
CoT
84.6
50.0
86.1
52.0
75.8
38.0
Reflexion
86.5
54.0
84.2
52.0
84.2
46.0
ToT
86.1
50.0
84.2
48.0
76.0
38.0
RAP
88.4
58.0
82.8
46.0
81.4
44.0
Appendix
Table 4: Shopping Planning, per-difficulty breakdown (%) with all models in thinking mode. Case Acc. denotes Case Accuracy. For each model and difficulty group (including Overall), the best value of every metric is in bold , including ties.
Figure 6: Case Accuracy (%) by Travel language and Shopping difficulty for MCTS (w/o hypergraph) and HyperMCTS (w/ hypergraph).
Model
λ
CS Score
PS Score
Comp Score
Case Acc.
Qwen3.6-27B
0.1
86.1
82.8
84.4
31.2
0.3
86.0
82.1
84.1
30.0
0.5
86.7
82.5
84.6
32.1
0.7
86.9
83.8
85.3
33.8
0.9
85.6
84.6
85.1
32.5
Qwen3.5-27B
0.1
77.7
81.7
79.7
18.6
Appendix
Table 5: Travel sensitivity to λ (%). Bold marks the best value of each metric within each model, including ties.
Agent
Qwen3.6-27B
Qwen3.5-27B
Mean
Acc. (%)
C/NA/W
Mean
Acc. (%)
C/NA/W
ReAct
0.338
13.5
15/45/51
0.441
12.6
14/70/27
CoT
0.324
14.4
16/40/55
0.437
13.5
15/67/29
Reflexion
0.311
14.4
16/37/58
0.401
13.5
15/59/37
ToT
0.302
17.1
19/29/63
0.446
17.1
19/61/31
RAP
0.297
14.4
16/34/61
0.405
13.5
15/60/36
Appendix
Table 6: Full SealQA results. Mean is on a 0 – 1 scale; accuracy is in %. Bold marks the best Mean and accuracy for each model, including ties.
Large Language Model (LLM) agents have shown promise in multi-step planning tasks, but existing approaches like LATS (Language Agent Tree Search) and ReAct rely heavily on LLM inference during planning, leading to high computational costs and stochastic behavior. We present \textbf{GATS} (Graph-Augmented Tree Search), a planning framework that combines systematic UCB1-based tree search with a layered world model to eliminate LLM calls during inference while achieving superior planning performance. Our three-layer world model integrates: (L1) exact symbolic action matching, (L2) statistics learned from execution logs, and (L3) LLM-based prediction for unknown actions. On synthetic planning tasks with branching paths and dead-ends, GATS achieves \textbf{100% success rate} compared to 92 % for LATS and 64% for ReAct. On a comprehensive stress test spanning 12 challenging scenarios -- including coding workflows, web navigation, and long-horizon tasks -- GATS maintains \textbf{100% success} while LATS drops to 88.9 % and ReAct to 23.9%. GATS requires \textbf{zero LLM calls per task} during planning (vs. 37 per task for LATS) and produces deterministic plans with zero variance across runs. Our results demonstrate that systematic search with learned world models can substantially outperform LLM-guided exploration for agent planning.
LLM-powered systems require complex multi-step decision-making abilities to solve real-world tasks, yet current planning approaches face a trade-off between the high latency of inference-time search and the limited generalization of supervised fine-tuning. To address this limitation, we introduce \textbf{SGA-MCTS}, a framework that casts LLM planning as non-parametric retrieval. Offline, we leverage Monte Carlo Tree Search (MCTS) to explore the solution space and distill high-fidelity trajectories into State-Goal-Action (SGA) atoms. These atoms are de-lexicalized primitives that abstract concrete entities into symbolic slots, preserving reusable causal logic while discarding domain-specific noise. Online, a retrieval-augmented agent employs a hybrid symbolic-semantic mechanism to fetch relevant SGAs and re-ground them into the current context as soft reasoning hints. Empirical results on complex benchmarks demonstrate that this paradigm enables frozen, open-weights models to match the performance of SOTA systems (e.g., GPT-5) without task-specific fine-tuning. By effectively amortizing the heavy computational cost of search, SGA-MCTS achieves System 2 reasoning depth at System 1 inference speeds, rendering autonomous planning both scalable and real-time feasible.
Xin Xie, Dongyun Xue, Wuguannan Yao +5
Ant Digital Technologies, Ant Group · Hefei Comprehensive National Science Center, Hefei, China
Tool-augmented LLM agents commonly rely on step-wise atomic tool calls, where each invocation, observation, and value transfer is exposed in the main reasoning trace. This creates an \emph{execution-granularity mismatch}: locally deterministic tool workflows are unfolded into repeated model-visible decisions, consuming context and forcing the model to manage low-level dataflow in the trace. We introduce \textbf{HyperTool}, a unified executable MCP-style tool interface that changes the model-visible unit of tool execution. A model invokes HyperTool with a code block that can call existing tools through their original schemas, manipulate returned values, and pass intermediate results locally, folding deterministic tool subroutines into a single outer call. To train models to use this interface, we synthesize HyperTool-format trajectories from cross-tool compositional tasks and verify them in real MCP environments. On MCP-Universe, HyperTool improves average accuracy from 15.69% to 35.29% on Qwen3-32B and from 9.93% to 33.33% on Qwen3-8B, and surpass GPT-OSS and Kimi-k2.5 on average accuracy, showing that our HyperTool can substantially improve multi-step tool use.
Yaxin Du, Yifan Zhou, Yujie Ge +7
Shanghai Jiao Tong University · IQuest Research · Beijing University of Aeronautics and Astronautics