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

• Long-horizon tasks require decisions whose consequences span a solution, so individually plausible choices can jointly violate a budget or conflict in time.A DeepPlanning itinerary illustrates the issue: it attains a 93.8% Composite Score but fails because an attraction is scheduled twice.Source: §1 · p. 1, Figure 1 · p. 2
• Standard MCTS stores values for history–action pairs but does not explicitly track recurring decision groups across prefixes, leaving outcomes from different paths unshared.Prior reuse methods do not maintain numerical outcome statistics indexed by recurring unordered decision groups and aggregate overlapping-group evidence to guide MCTS selection within a task.Source: §1 · p. 2
• HyperMCTS augments ordered MCTS with a cross-trajectory hypergraph that shares decision-group outcomes while preserving execution histories.HyperUCT aggregates incident hyperedge statistics into an action prior alongside tree values and exploration; the evaluation also includes hypergraph ablations, weight sensitivity, and SealQA question answering.Source: §1 · p. 2
• HyperMCTS improves average planning accuracy over each backbone model’s strongest baseline by 7.3, 2.7, and 2.3 percentage points for Qwen3.6-27B, Qwen3.5-27B, and Sonnet 4.6, respectively.On Shopping Planning, Qwen3.6-27B reaches 60.8% Case Accuracy versus Claude Opus 4.6 (max) at 56.2%.Source: §1 · p. 2
• HyperMCTS achieves higher accuracy with fewer LLM calls and output tokens than the evaluated MCTS-based baselines, and SealQA experiments show question-answering improvements.Source: §1 · p. 2

2.1 PRELIMINARIES

• The agent interacts with an environment through tools or APIs and follows a policy over observable history in a finite-horizon episode.Planning branches at information-gathering and commit decisions; valid search decisions label tree edges and map to canonical hypergraph nodes.Source: §2.1 · p. 3
• Tasks specify objectives and terminal feedback, while global constraints such as a total budget depend jointly on multiple decisions.Objective-level feedback can supplement search feedback, which need not equal a final benchmark metric.Source: §2.1 · p. 3

2.2 PROBLEM DEFINITION

• At test time, only a finite set of trajectories can be evaluated, so the planner must allocate its search budget to let one rollout inform others without a shared action prefix.The operational objective is defined over trajectories generated and evaluated within the search budget, without updating the frozen policy.Source: §2.2 · p. 3

3.1 OVERVIEW

• Across different tree paths, shared and overlapping decision groups accumulate feedback that can inform later choices under another prefix.The tree retains valid execution histories; pooling outcomes does not assume the task is order-invariant.Source: §3.1 · p. 4, Figure 2 · p. 4, §3.2 · p. 5

3.2 CROSS-TRAJECTORY HYPERGRAPH

• The hypergraph maps decisions to canonical identities and pools counts and mean feedback for recurring decision groups across prefixes.Trajectory-level observations pair the recorded decision set with trajectory reward; objective-level observations use an objective score when available, or trajectory reward otherwise.Source: §3.2 · pp. 4–5

3.3 HYPERUCT SELECTION

• HyperUCT combines tree-local exploitation and exploration with a prior aggregated from hyperedges incident to each candidate decision.The prior is heuristic: it does not condition on the complete current decision set and does not change the verifier reward.Source: §3.3 · p. 5

3.4 THE HYPERMCTS ALGORITHM

• Each HyperMCTS iteration follows selection, expansion, simulation, and backup, then updates the hypergraph after an evaluated rollout.Each nonterminal node is expanded at most once, adding up to b distinct-decision children; the final choice uses stored rewards from evaluated trajectories.Source: §3.4 · p. 5

4.1 EXPERIMENTAL SETUP

• The evaluation uses DeepPlanning Travel and Shopping tasks with verifiable constraints, three backbone models, and baselines spanning unstructured and structured test-time scaling methods.The experiments also evaluate fact-seeking question answering over noisy evidence on SealQA.Source: §4.1 · p. 6

4.2 MAIN RESULTS (RQ1)

• HyperMCTS improves Average Accuracy over the strongest baseline by 7.3, 2.7, and 2.3 percentage points for Qwen3.6-27B, Qwen3.5-27B, and Sonnet 4.6, respectively.Table 1 reports results on DeepPlanning and SealQA; Avg Acc. averages Travel and Shopping Case Accuracy.Source: §4.2 · p. 6, Table 1 · p. 7

4.3 SEARCH EFFICIENCY (RQ2)

• At each tested branching factor, HyperMCTS has the highest Case Accuracy and fewest LLM calls and output tokens; at b = 3, it reaches 60.8% accuracy with about 122 calls and 85K output tokens.At b = 3, RAP reaches 57.5% accuracy with 144 calls and 141K tokens; HyperMCTS at b = 3 is more accurate and less costly than every baseline at b = 6.Source: §4.3 · p. 7, Figure 3 · p. 8

4.4 ABLATION STUDY (RQ3)

• With the same backbone models, rollout budget, and branching factor, HyperMCTS has higher Case Accuracy than MCTS without the hypergraph in both domains on all three models.This comparison evaluates the hypergraph component as a whole, not the additive HyperUCT term in isolation.Source: §4.4 · p. 8, Figure 4 · p. 8

4.5 SENSITIVITY ANALYSIS (RQ4)

• The best hypergraph weight varies by model and metric: Qwen3.5-27B peaks at λ = 0.3 for both reported metrics, while Qwen3.6-27B peaks at λ = 0.7.Sonnet 4.6 has its highest Case Accuracy at λ = 0.7 but its highest Comp Score at λ = 0.3.Source: §4.5 · p. 8, Figure 5 · p. 9

4.6 GENERALIZABILITY (RQ5)

• On SealQA, HyperMCTS exceeds the strongest baseline by 2.7 and 3.6 percentage points for Qwen3.6-27B and Sonnet 4.6, respectively, and ties ToT at 17.1% for Qwen3.5-27B.SealQA evaluates question answering over noisy evidence.Source: §4.6 · p. 9

5 LIMITATIONS

• HyperMCTS assumes reversible actions, state restoration, or replay; irreversible actions or persistent external effects require a simulator or another way to evaluate alternatives without committing them.Shopping-cart construction and travel-plan revision are given as settings where tentative choices can be changed before execution.Source: §5 · p. 9
• The hypergraph is most useful when trajectories share decision groups; limited overlap reduces sharing, while omitted order or context can lead it to pool incompatible feedback.The tree still preserves execution order, but the hypergraph represents decision groups as unordered sets.Source: §5 · p. 9

6 CONCLUSION AND FUTURE WORK

• HyperMCTS achieves the highest Average Accuracy on the evaluated DeepPlanning models and improves over the no-hypergraph variant; Shopping also shows higher accuracy with fewer calls and output tokens on Qwen3.6-27B.SealQA extends the evaluation to question answering; future work may combine HyperMCTS with world models for irreversible-action planning.Source: §6 · p. 9
• The method organizes search outcomes by labelled decision groups in a cross-trajectory hypergraph, while retaining ordered histories in the MCTS tree.HyperUCT combines the group statistics with prefix-specific tree values and exploration.Source: §6 · p. 9

A.1 NOTATION SUMMARY

• Table 2 summarizes the notions used in the search tree and cross-trajectory hypergraph.Source: §A.1 · p. 12

A.2 HYPERGRAPH SPECIFICATION

• Hyperedges record groups of canonical decisions with terminal search scores, while objective-level records pair an individual decision with an objective label.The recorded set may contain only decisions materialized in the tree, not every tool call in a simulated suffix.Source: §A.2 · p. 12
• The prior combines the maximum empirical objective-level value with the unweighted mean of incident trajectory-level values, using weights 0.7 and 0.3 when both exist.If only one record type exists, its value is used; with neither, the prior is zero.Source: §A.2 · p. 12
• This bounded heuristic averages trajectory-group means without weighting by observation count and does not estimate the causal effect of selecting a decision.Approximate Jaccard merging at threshold 0.8 can create a union of overlapping sets that never appeared in one rollout, and merge order can affect clusters.Source: §A.2 · pp. 12–13

A.3 DOMAIN INTERFACES AND SEARCH INTEGRATION

• Domain adapters define candidate generation, child selection, rollout depth, stopping rules, and task-specific failure behavior; tree backup follows represented paths while simulated suffix decisions may still update the hypergraph.Search may stop before its iteration budget, and the final choice uses stored rewards without re-evaluation.Source: §A.2 · p. 12, §A.3 · p. 13
• In SealQA, Search, Lookup, and Finish actions append observations to a question’s history, while canonical action identities use action type and arguments.An argument-only Lookup identity can conflate decisions made under different retrieval contexts.Source: §A.3 · p. 13

A.4 ILLUSTRATIVE SEARCH EXAMPLE

• At the illustrated B1-then-A1 history, C1’s prior can use feedback from A1B1, while C2’s can use records from both A1B1C2 and A2B1C2.This constructed example demonstrates possible cross-prefix evidence transfer, not its frequency or decision impact in experiments; separate tree values and visit counts also inform HyperUCT selection.Source: §A.4 · p. 14

B.1 EXPERIMENTAL AND IMPLEMENTATION DETAILS

• DeepPlanning Travel evaluates 240 instances from 120 tasks in Chinese and English, while Shopping evaluates 120 multi-product cart tasks; SealQA uses the 111-question Seal-0 subset.Travel outputs are parsed into structured representations, and final outputs are scored by rule-based checkers; SealQA accuracy and partial-credit formulas are specified separately.Source: §B.1 · p. 15
• Comparisons use the same frozen backbone within each method comparison, spanning unstructured tool-use approaches and structured trajectory-search methods including MCTS variants.The appendix identifies ReAct, CoT, and Reflexion as unstructured methods, and ToT, RAP, LATS, FLARE, and HyperMCTS as structured methods.Source: §B.1 · p. 15
• Unless otherwise stated, DeepPlanning HyperMCTS uses at most five search iterations and branching factor three, with efficiency tests varying branching factor across 2, 3, and 6.The UCT exploration coefficient is 1.414; reported λ weights differ by task and model configuration.Source: §B.1 · p. 15

B.2 REWARD COMPUTATION AND EVALUATION PROMPTS

• Terminal rewards update tree and hypergraph statistics, but the hypergraph prior guides selection rather than being added to the reward.All three configurations retain the candidate with the highest observed terminal reward; Travel and Shopping allow early stopping at 0.95, while SealQA uses its configured value stop.Source: §B.2 · p. 16
• Shopping search feedback uses a model-configured judge score, whereas final benchmark scores use reference-product and coupon matching.For SealQA, terminal value evaluation receives reference-derived grader feedback in the terminal observation, although the value prompt has no reference-answer field.Source: §B.2 · p. 16

C ADDITIONAL EXPERIMENTAL RESULTS

• The appendix reports per-language Travel and per-difficulty Shopping breakdowns, ablation and sensitivity results, full SealQA metrics, and additional Opus 4.8 results.These breakdowns underlie the DeepPlanning results in Table 1.Source: C ADDITIONAL EXPERIMENTAL RESULTS · p. 19

C.1 TRAVEL PLANNING

• On Sonnet 4.6, HyperMCTS has the highest EN PS Score (88.3%) and Comp Score (91.8%), with overall PS Score tied best at 81.3%.Its overall Comp Score is 82.9%.Source: §C.1 · p. 19
• For Sonnet 4.6 Travel, HyperMCTS reaches 53.3% Case Accuracy on EN versus 7.5% on ZH.The passage suggests pretraining differences in Chinese–English capabilities may partly explain the contrast.Source: §C.1 · p. 19

C.2 SHOPPING PLANNING

• Shopping results include per-difficulty breakdowns, while Figure 6 presents Case Accuracy by Travel language and Shopping difficulty.Source: §C.2 · p. 20, Figure 6 · p. 21

C.3 HYPERGRAPH ABLATION BREAKDOWNS

• HyperMCTS improves over MCTS on ZH and EN for all three models; the two Qwen models gain 15.0 and 10.0 points at Shopping Level 3.Level 3 includes coupon optimization.Source: §C.3 · p. 21
• Sonnet’s Shopping gains are 6.0, 6.0, and 5.0 points across levels, while Qwen3.5-27B ties MCTS at 54.0% on Level 2.Gains do not increase uniformly with difficulty, and Level 3 contains 20 cases versus 50 each for Levels 1 and 2.Source: §C.3 · p. 21

C.4 HYPERGRAPH WEIGHT SENSITIVITY

• The Travel λ sweep reports four overall metrics across five λ values, holding B = 5, b = 3, and c = 1.414 fixed.Source: §C.4 · p. 22, Table 5 · p. 22

C.5 SEALQA RESULTS

• SealQA scoring covers 111 answers: accuracy is 100C/N, and Mean grants half credit to not-attempted answers.Correct, not-attempted, and wrong answers are denoted C, NA, and W and sum to N = 111.Source: §C.5 · p. 23
• The SealQA results use λ = 0.2 for Qwen3.6-27B and Sonnet 4.6, and λ = 0.5 for Qwen3.5-27B and Opus 4.8.Source: §C.5 · p. 23
• On Opus 4.8, HyperMCTS reaches 30.6% accuracy, 4.5 percentage points above the strongest baselines, LATS and FLARE at 26.1%.Source: §C.5 · p. 23