Sub-Task-Horizon Rollouts for Multi-Agent Tree Search

When a language-model agent plans by tree search, it has to judge how promising each partial plan is. Current systems take one of two extremes. Some score a step by asking the model how good it looks right now, with no lookahead. Others play the whole task out to the end before scoring. The first is cheap but blind to consequences a few steps later. The second is informative but very expensive and noisy: LATS spends about 185,000 tokens per HotpotQA question. This note proposes a middle depth, and argues that task decomposition supplies it for free.

When a planning agent splits a task into sub-tasks, each sub-task has a local goal, such as "find a train from city A arriving before noon" or "craft two sticks." So the natural rollout is not a full trajectory. It is a fast, greedy completion of only the next sub-task, run by a narrow sub-agent that sees only that sub-task's tools. That partial outcome is then compared against the outcomes of sibling branches, rather than graded on an absolute scale. The claim is that this sub-task-horizon rollout, scored comparatively, gives better value estimates per token than either myopic self-evaluation or full rollouts on long, decomposable agent tasks.

Core Claim

The idea borrows from classic Monte Carlo Tree Search (MCTS), the planning algorithm that grows a search tree by repeatedly selecting a promising branch, simulating forward from it, and passing the result back up the tree. A long line of work shows that MCTS lives or dies on how it simulates. Uniform random simulations scale badly: Yoshimoto et al. found sharply diminishing returns from a hundredfold increase in samples in Go. Cheap informed simulations help a great deal, including softmax-biased heuristic playouts in Rimmel et al. and greedy merge playouts that let CSG-UCT scale coalition formation to 500 agents. That literature fixed the simulation policy and asked how informed it should be. For language agents, the more consequential and unexplored choice is the simulation horizon, and multi-agent task decomposition offers a principled place to cut it.

Two pieces of evidence motivate the specific design. First, Li et al. show that language models are poor absolute verifiers of plans, with 0.00% pass rates as solvers on hard course planning. The same models are strong comparative rankers of candidate states: Claude 3.5 Sonnet reaches 92.25% Hit@3 on easy course planning. Second, TDAG shows that sub-agents with narrowed tool contexts, spawned per sub-task, reduce cascading failure from 34.78% to 4.35% on ItineraryBench, but TDAG performs no lookahead at all.

The proposal therefore makes one testable claim. On tasks whose structure decomposes into sub-goals, scoring a tree node by greedily completing the next sub-task and ranking the result against its siblings will dominate both myopic and full-horizon evaluation on the curve of value-estimate accuracy against tokens. That dominance should carry through to final task success at matched token budgets.

Relation to Prior Work

The closest systems fall into two camps. The first drops simulation entirely. MASTER removes rollouts and has each node's agent report a score and a confidence that modulates exploration. It reaches 76.0% on HotpotQA at about 11,000 tokens, but it depends on the model's self-calibration, which the authors concede is weak in smaller models. CoTS and SWE-Search likewise score nodes with fixed critic or value agents that give absolute rewards, which is exactly the role Li et al. find models handle poorly.

The second camp keeps simulation but makes it monolithic. LATS rolls a single model out to the terminal state. ToC restricts expansions to atomic text edits within patent drafting.

None of these ties the rollout horizon to the decomposition. The proposal differs from MASTER by restoring lookahead, from LATS by truncating it at a semantically meaningful boundary, and from all of them by replacing absolute critic scores with sibling-relative ranking. TDAG supplies the mechanism for spawning sub-agents, and CSG-UCT supplies the precedent that greedy, structure-aware playouts beat random ones. The proposal does not address irreversible environments, which LATS and SWE-Search also sidestep. All chosen benchmarks permit reset or are read-only, and this limitation is stated rather than solved.

Research Program

The system has three parts.

  1. Search over decompositions. A planner agent proposes the next sub-task, so tree edges are "commit to sub-task $k$ with this specification." This lets the tree branch over decompositions, not only over atomic actions.
  2. Sub-task rollout. At a new node, a sub-agent is spawned TDAG-style with only the tools relevant to that sub-task. It completes the sub-task greedily, at temperature zero and with a hard step cap, and returns the resulting state and a short summary. The rollout ends at the sub-task boundary.
  3. Comparative scoring and backup. The summaries from a node and its siblings, typically three to five, go to a single listwise ranking call. That call orders them by how much they advance the overall goal. Ranks are converted to values in $[0,1]$ by normalized rank and backed up with standard UCT, the usual MCTS rule for trading off a branch's average value against how rarely it has been visited.

Each ingredient can be swapped independently, and this is what makes the claims checkable:

Ingredient Settings compared
Horizon Zero steps (MASTER-like), next sub-task (proposed), full task (LATS-like)
Scoring Absolute 0–100 score, sibling ranking
Rollout model Same model as the planner, a smaller open model

The program also includes a diagnostic study of value estimation itself. For a sample of tree nodes, we estimate a reference value by running many full, high-budget completions. We then measure each estimator's Spearman rank correlation with that reference as a function of the tokens it spends. This separates "better estimates" from "better search luck."

Baselines

Naive reference points. The do-nothing reference is ReAct-style linear acting with the same base model. LATS reports ReAct at 0.32 exact match on HotpotQA. Plan-and-Execute is the static-decomposition reference, with a 34.78% cascading-failure rate on ItineraryBench reported by TDAG. These tell us whether search of any kind is worth its cost.

MASTER, the strongest efficient competitor. MASTER reports 76.0% accuracy on HotpotQA at about 11,000 tokens and 80.0% on WebShop. It is the system to beat on cost, because it shows that dropping rollouts can be both cheap and accurate. We re-implement its confidence-weighted UCT with our base models and give it the identical per-task token budget. We tune its exploration constant over the same small grid used for our method, on a held-out split. Beating it means higher success at equal tokens, or equal success at clearly fewer tokens. We will also report its published numbers alongside, with the caveat that model versions differ.

LATS, the strongest full-rollout competitor. LATS reports 0.71 exact match on HotpotQA and 75.9 on WebShop with GPT-3.5. We run it under two conditions: its native budget, and capped to our budget. The capped condition shows whether full rollouts collapse when they are starved of tokens.

TDAG, the strongest decomposition-without-search competitor. TDAG reports a 49.08 fine-grained score on ItineraryBench and 73.5% success on TextCraft. We run it with the same sub-agent spawning code our method uses, so the only difference is whether lookahead exists.

Ablations. Two ablations isolate the key ingredients. The horizon ablation holds sibling ranking fixed and varies only rollout depth. The scoring ablation holds sub-task-horizon rollouts fixed and swaps ranking for absolute critic scores. If the horizon ablation shows no gain over zero-step evaluation, the core claim fails.

Why not just…?

Why not just give LATS a smaller, cheaper model for its full rollouts? This is the most serious threat. If cheap full rollouts match sub-task rollouts at equal tokens, then the horizon does not matter and only the cost per token does. The cross-design settles this directly by running both horizons with the small rollout model. The proposal predicts that full rollouts from a weak model compound errors over long horizons. AgentBoard's finding that open-weight models fall below 50% action-grounding accuracy, against GPT-4's 85.6% (AgentBoard), suggests such errors accumulate with depth, but this must be shown, not assumed.

Why not just improve MASTER-style self-evaluation, for example with better confidence prompts? Myopic evaluation is cheap, and on short-horizon HotpotQA it may suffice. We expect it to win or tie there and say so in advance. The case against it rests on tasks where a step looks fine but breaks a later constraint, which is the tactical-blindness failure that motivated informed rollouts in Lanctot et al.. The value-correlation study on ItineraryBench, where constraints span sub-tasks, is where this alternative should visibly lose.

Why not just spend the same tokens on best-of-N sampling of whole TDAG runs, ranked at the end? This takes the comparative-ranking strength from Li et al. without any tree. It is a fair and simple competitor, and it is included at matched budget. If it matches our method, the contribution shrinks to "ranking beats critics," and we would report it that way. Our method should win only if partial credit at sub-task boundaries lets the search abandon bad decompositions early. This is visible in how the per-task token budget is spent before the first failure is detected.

Proposed Experiments

The primary benchmarks are ItineraryBench and TextCraft, where decomposition is natural and TDAG gives reference numbers. WebShop and HotpotQA serve as head-to-head comparisons with MASTER and LATS. A subset of AgentBoard tasks (hkust-nlp/AgentBoard) adds progress rate as a graded signal; its automated progress rate correlates with human judgments at Pearson r above 0.95.

Every method runs at two per-task token budgets: about 11,000, matching MASTER's reported cost, and about 50,000. Each runs with two base models, one frontier API model and one roughly 70B open model, so we can test whether comparative ranking holds up where self-confidence does not. We report success, the benchmark's fine-grained or progress score, tokens, and wall-clock time, with three seeds.

Two checks are decisive.

  1. Estimator quality. On the value-correlation diagnostic, sub-task-horizon rollouts with ranking must lie on the Pareto frontier of rank correlation against tokens, above both zero-step and full-horizon estimators on ItineraryBench and TextCraft.
  2. Task success. At the 11,000-token budget, the full system must beat both MASTER and the best-of-N TDAG baseline on those two benchmarks.

If the first check holds but the second does not, the estimator is better but search cannot exploit it at these budgets. If neither holds, the horizon hypothesis is wrong. We also expect, and will report, a smaller or absent gain on HotpotQA, whose short horizon leaves little room between "next sub-task" and "whole task."