Neural tree search is a powerful decision-making algorithm widely used in complex domains such as game playing and model-based reinforcement learning. Recent work has applied AlphaZero-style tree search to enhance the reasoning capabilities of Large Language Models (LLMs) during inference, but we find that this approach suffers from a scaling failure: on GSM8K and Game24, accuracy drops as the search budget increases. In this paper, we present ReSCALE, an adaptation of Gumbel AlphaZero MCTS that replaces Dirichlet noise and PUCT selection with Gumbel sampling and Sequential Halving, restoring monotonic scaling without changes to the model or its training. ReSCALE reaches 58.4% on GSM8K and 85.3% on Game24 at budgets where the baseline degrades. Ablations confirm that Sequential Halving is the primary driver of the improvement.
Figures & tables
Figure 1: Gumbel + Sequential Halving enables scaling of MCTS for reasoning. Comparison of tree-search methods for LLM reasoning on GSM8K across increasing token budgets. The standard AlphaZero-style approach plateaus and declines at higher budgets, while proposed ReSCALE decoding achieves sustained accuracy gains, demonstrating better scaling with additional compute.
Figure 2: Left: A single simulation in tree search with sentence-level actions. Each simulation traverses from the root to a leaf, selecting actions via Sequential Halving with Gumbel noise at the root and an improved policy at non-root nodes. The selected leaf is expanded by sampling w actions from the LLM ( πθ ), each evaluated by the value network vϕ , and the resulting values are backpropagated to update ancestor statistics. Right: Sequential Halving at the root node. From M=8 candidate actions, the budget of N=24 simulations is split evenly across ⌈log2M⌉=3 rounds. After each round, the bottom half of actions (by score gi+logp(ai)+σ(v(ai)) ) is eliminated, until a single winner remains.
GSM8K
Game24
Tree Search
Budget
Tokens
Acc., %
Max. Acc., %
Tokens
Acc., %
Max. Acc., %
AlphaZero
Small
0.5K–2K
56.0±1.2
58.8
0.2K–2K
74.4±12.0
86.7
ReSCALE
55.1±1.1
58.6
71.6±10.5
81.2
AlphaZero
Medium
6K–8K
56.7±0.9
58.3
2K–4K
84.3±1.0
86.2
ReSCALE
57.9±1.0
60.2
83.4±1.4
85.9
AlphaZero
Large
16K–18K
53.6±0.7
55.0
4K–6K
82.9±1.1
84.8
Table 1: Combined results on GSM8K and Game24. For each budget level, mean accuracy ± std is computed across hyperparameter configurations; for Best-of-N, across three random seeds. Best single-configuration accuracy (Max. Acc.) is also reported. On GSM8K, AlphaZero accuracy drops at Large budget (53.6%) while ReSCALE continues to improve (58.4%), both surpassing the Best-of-N baseline (53.4%). On Game24, AlphaZero similarly degrades at Large budget (82.9%), whereas ReSCALE continues to improve (85.3%), both outperforming the Best-of-N baseline (54.1%).
As pretraining scaling laws approach saturation, Test-Time Scaling (TTS) has emerged as an important direction for improving reasoning by allocating inference-time compute to a fixed model prior. Viewed at a high level, TTS reframes inference as search over a space of partial reasoning states. While Chain-of-Thought (CoT) exposes intermediate steps, common instantiations rely on single-trajectory decoding, limiting recovery from early errors and exploration. This survey systematizes recent progress in tree-search-based reasoning, viewing inference as instance-specific optimization rather than decoding. We trace the evolution from uninformed search to Monte Carlo Tree Search (MCTS), highlighting how sampling-based control supports principled exploration-exploitation trade-offs. To unify a fragmented literature, we introduce a Unified Design Space spanning search topology, evaluation signals, and control dynamics, and advocate a standardized compute-reporting abstraction to make compute-accuracy trade-offs explicit and comparable.
Jiaqi Wei, Xiang Zhang, Yuejin Yang +10
1Zhejiang University · 2Shanghai AI Laboratory · 4Fudan University +3
Tree of Thought (ToT) search has become a promising direction for improving the reasoning capabilities of large language models, but deploying these methods in practice raises a question that has received little systematic attention: how do different search strategies behave under varying compute budgets, model sizes, and problem difficulties? In this work, we evaluate two representative ToT methods; DPTS, a Monte Carlo tree search based approach, and SSDP, a semantic deduplication based approach, across two mathematical reasoning benchmarks (Math500 and GSM8K), two model scales (Llama-3B and Llama-8B), and four token budgets (3k--10k). Our analysis reveals that the two methods exhibit limitations that pull in opposite directions. DPTS suffers from a cold-start bottleneck at low budgets: it requires sufficient exploration before its value estimates become reliable, making it a poor fit for resource-constrained settings despite strong scaling behavior at higher budgets. SSDP, on the other hand, reaches candidate solutions efficiently but is prone to frontier depletion; its aggressive node merging permanently discards unexplored paths, leaving it unable to improve regardless of how much budget remains. Together, these findings suggest that neither a fixed exploration strategy nor a fixed pruning strategy is sufficient across compute continuum. We argue that effective search for scientific reasoning agents requires strategies that can adapt their behavior based on search progress and available resources.
Atkia Mahila, Avinash Maurya, M. Mustafa Rafique +1
Rochester Institute of Technology Rochester, USA · Argonne National Laboratory Lemont, USA
Test-time scaling has become a dominant paradigm for improving LLM agent reliability, yet current approaches treat compute as an abundant resource, allowing agents to exhaust token and tool budgets on redundant steps or dead-end trajectories. Existing budget-aware methods either require expensive fine-tuning or rely on coarse, trajectory-level heuristics that cannot intervene mid-execution. We propose the Budget-Aware Value Tree (BAVT), a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree guided by step-level value estimation within a single LLM backbone. Another key innovation is a budget-conditioned node selection mechanism that uses the remaining resource ratio as a natural scaling exponent over node values, providing a principled, parameter-free transition from broad exploration to greedy exploitation as the budget depletes. To combat the well-known overconfidence of LLM self-evaluation, BAVT employs a residual value predictor that scores relative progress rather than absolute state quality, enabling reliable pruning of uninformative or redundant tool calls. We further provide a theoretical convergence guarantee, proving that BAVT reaches a terminal answer with probability at least 1−ε under an explicit finite budget bound. Extensive evaluations on four multi-hop QA benchmarks across two model families demonstrate that BAVT consistently outperforms parallel sampling baselines. Most notably, BAVT under strict low-budget constraints surpasses baseline performance at 4× the resource allocation, establishing that intelligent budget management fundamentally outperforms brute-force compute scaling.