HyperMCTS improves long-task planning for large language model agents
HyperMCTS: Hypergraph-Augmented MCTS for Long-Horizon LLM Agents
Artificial Intelligence
Summary
Long tasks require planning many steps ahead, which is hard and slow for large language models (LLMs). The authors find that a standard decision search method called Monte Carlo Tree Search (MCTS) is limited because it does not share knowledge across similar decision groups appearing in different plans. They propose HyperMCTS, which adds a network (hypergraph) connecting these decision groups to reuse past outcomes more efficiently. This method improves planning accuracy and reduces the need for repeated computations when tested on several benchmarks.
What this means in practice
- •For ai developers: Make large language model agents more efficient at planning long, multi-step tasks by better reusing previous decision outcomes.
- •For automated customer support teams: Improve question answering performance in complex scenarios with fewer language model calls using enhanced search methods.
Authors
Tingsong Xiao, Nithish Balachandar Moudhgalya, Chandrayee Basu, Lichao Wang, Luyang Kong, Benjamin Z. Yao, Zhe Jiang, Jie Hao
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.