Revisiting Tree Search for LLMs: Gumbel and Sequential Halving for Budget-Scalable Reasoning
On the map: LLM reasoning → Test-time compute and efficient thinking
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 3 of its 25 references that are in the map. First posted on arXiv 22 Mar 2026.
Builds on
3 of 25 references.
References · 3
- 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
- 2021Training Verifiers to Solve Math Word Problemscited by 9,743
- 2024OpenAI o1 System Cardcited by 1,220
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2023Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training
- 2026When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models
- 2025Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey
- 2025Policy Guided Tree Search for Enhanced LLM Reasoning
- 2024Enhancing LLM Reasoning with Reward-guided Tree Search
- 2025SELT: Self-Evaluation Tree Search for LLMs with Task Decomposition
- 2026Amortized Reasoning Tree Search: Decoupling Proposal and Decision in Large Language Models
- 2024Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning