HyperMCTS augments with a hypergraph that groups canonical decisions and accumulates their observed returns across different search paths. This allows outcomes from one prefix to inform selection under another, unlike standard MCTS which keeps prefix-specific statistics separate. On DeepPlanning tasks, HyperMCTS improved average planning accuracy by 2.3 to 7.3 percentage points over the strongest baseline for each of three backbone models (Qwen3.6-27B, Qwen3.5-27B, Sonnet 4.6). It also enabled Qwen3.6-27B to outperform Claude Opus 4.6 on Shopping Planning while using fewer LLM calls and output tokens than other MCTS-based methods. The approach is interesting because it reuses trajectory feedback without extra training, directly addressing the high cost of environment interaction in long-horizon planning.
Hypergraphs help language agents reuse feedback across planning paths
HyperMCTS shares returns among recurring groups of decisions, improving long-horizon planning without additional training.
Big Tech
Tingsong Xiao · Nithish Balachandar Moudhgalya · Chandrayee Basu · Lichao Wang · Luyang Kong · Benjamin Z. Yao · +2 more
University of Florida · Amazon
Research Digest··2 min read
In one line
HyperMCTS uses a hypergraph to share decision outcomes across trajectories, improving MCTS efficiency and accuracy for LLM agents.
Before you read this
Three ideas this paper builds ontest-time scalingAllocating extra computation during inference to improve output quality.117 papers →monte carlo tree searchA search algorithm that uses random sampling to evaluate actions and builds a tree for planning.5 papers →trajectory transferUsing demonstrations or solutions from one task, domain, or agent to improve performance or training in another.28 papers →
Read it as
The authors augment Monte Carlo Tree Search with a task-specific hypergraph that connects equivalent or related decisions appearing under different trajectory prefixes.
HyperMCTS retains an ordered search tree for complete execution histories while adding a cross-trajectory hypergraph.
How it works
before and afterThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.