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

Tingsong Xiao; Nithish Balachandar Moudhgalya; Chandrayee Basu; Lichao Wang; Luyang Kong; Benjamin Z. Yao; Zhe Jiang; Jie Hao

cs.AISep 27, 2026

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

Authors: Tingsong Xiao, Nithish Balachandar Moudhgalya, Chandrayee Basu, Lichao Wang, Luyang Kong, Benjamin Z. Yao, Zhe Jiang, Jie Hao

Organizations: University of Florida · Amazon

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.

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). $R_{i}$ 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.	Avg Acc.	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 $\lambda$ 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$ , $h_{t}$ , $\tau$	Query, observable interaction history, and complete or horizon-terminated trajectory
$H$ , $B$ , $b$	Interaction horizon, search-iteration budget, and expansion branching factor
$\pi_{\theta}$ , $\mathcal{A}_{\mathrm{dec}}(h)$	Frozen proposal policy and task-defined search decisions
$V$ , $R(\tau)$	Terminal search verifier and trajectory reward
$\mathcal{G}$ , $\mathcal{Y}$	Query objectives and hyperedge labels
$\mathcal{U}$ , $\phi$ , $\mathcal{C}(\tau)$	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
Model	Agent	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
Level	Agent	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	$\lambda$	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

\lambda

(%). Bold marks the best value of each metric within each model, including ties.

Agent	Qwen3.6-27B			Qwen3.5-27B
Agent	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.

Explore similar work

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning
Jul 9, 2026Maureese Williams, Dymitr NowickiLarge Language Model Planning Classical Planning
Institute for Cybernetics of NAS of Ukraine
SGA-MCTS: Decoupling Planning from Execution via Training-Free Atomic Experience Retrieval
Apr 16, 2026Xin Xie, Dongyun Xue, Wuguannan Yao +5Large Language Model Planning Agentic Reasoning
Ant Digital Technologies, Ant Group · Hefei Comprehensive National Science Center, Hefei, China
HyperTool: Beyond Step-Wise Tool Calls for Tool-Augmented Agents
Jun 11, 2026Yaxin Du, Yifan Zhou, Yujie Ge +7Tool Invocation Agentic Workflow Design
Shanghai Jiao Tong University · IQuest Research · Beijing University of Aeronautics and Astronautics

Jul 9, 2026, cs.AIJ/K move · Enter open · S save

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

Maureese Williams, Dymitr Nowicki

Institute for Cybernetics of NAS of Ukraine

Large Language Model Planning Classical Planning Multi-Agent Planning Tree Search World Models LLM Inference Optimization

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

SGA-MCTS: Decoupling Planning from Execution via Training-Free Atomic Experience Retrieval

HyperTool: Beyond Step-Wise Tool Calls for Tool-Augmented Agents