Revisiting Tree Search for LLMs: Gumbel and Sequential Halving for Budget-Scalable Reasoning

Leonid Ugadiarov; Yuri Kuratov; Aleksandr Panov; Alexey Skrynnik

cs.AIMar 22, 2026

Revisiting Tree Search for LLMs: Gumbel and Sequential Halving for Budget-Scalable Reasoning

Authors: Leonid Ugadiarov, Yuri Kuratov, Aleksandr Panov, Alexey Skrynnik

Organizations: AXXX, Moscow, Russia · MIRAI, Moscow, Russia

Abstract

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 (

\pi_{\theta}

), each evaluated by the value network

v_{\phi}

, 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

\lceil\log_{2}M\rceil=3

rounds. After each round, the bottom half of actions (by score

g_{i}+\log p(a_{i})+\sigma(v(a_{i}))

) 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\pm 1.2$	$58.8$	0.2K–2K	$74.4\pm 12.0$	$86.7$
ReSCALE	Small	0.5K–2K	$55.1\pm 1.1$	$58.6$	0.2K–2K	$71.6\pm 10.5$	$81.2$
AlphaZero	Medium	6K–8K	$56.7\pm 0.9$	$58.3$	2K–4K	$84.3\pm 1.0$	$86.2$
ReSCALE	Medium	6K–8K	$57.9\pm 1.0$	$60.2$	2K–4K	$83.4\pm 1.4$	$85.9$
AlphaZero	Large	16K–18K	$53.6\pm 0.7$	$55.0$	4K–6K	$82.9\pm 1.1$	$84.8$

Table 1: Combined results on GSM8K and Game24. For each budget level, mean accuracy

\pm

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%).

Explore similar work

When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models
Aug 31, 2026Jiaqi Wei, Xiang Zhang, Yuejin Yang +10Inference-Time Search Inference-Time Scaling
1Zhejiang University · 2Shanghai AI Laboratory · 4Fudan University +3
Beyond Fixed Budgets: Characterizing the Inelasticity and Limitations of Tree-of-Thought Reasoning Strategies
May 19, 2026Atkia Mahila, Avinash Maurya, M. Mustafa Rafique +1LLM Evaluation Inference-Time Search
Rochester Institute of Technology Rochester, USA · Argonne National Laboratory Lemont, USA
Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents
Mar 13, 2026Yushu Li, Wenlong Deng, Jiajin Li +1Cost-Aware Inference Tree Search
University of British Columbia · Vector Institute

Aug 31, 2026J/K move · Enter open · S save

When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models

Jiaqi Wei, Xiang Zhang, Yuejin Yang, Wenxuan Huang+9

1Zhejiang University · 2Shanghai AI Laboratory · 4Fudan University+3

Inference-Time Search Inference-Time Scaling Monte Carlo Tree Search LLM Reasoning

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models

Beyond Fixed Budgets: Characterizing the Inelasticity and Limitations of Tree-of-Thought Reasoning Strategies

Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents