When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models
2026-08-31 • Computation and Language
Computation and Language
AI summaryⓘ
The authors explain that as making language models bigger helps less over time, a new method called Test-Time Scaling (TTS) tries to improve reasoning by searching through partial steps during inference. They focus on tree-search methods, like Monte Carlo Tree Search (MCTS), which explore many possible paths instead of just one, helping avoid early mistakes. The authors organize recent research into a unified framework that looks at how these searches are structured, evaluated, and controlled. They also suggest a common way to report computing effort to better compare different approaches.
Test-Time ScalingChain-of-ThoughtMonte Carlo Tree SearchInferenceExploration-ExploitationSearch TopologyEvaluation SignalsControl DynamicsCompute-Accuracy Trade-offPartial Reasoning States
Authors
Jiaqi Wei, Xiang Zhang, Yuejin Yang, Wenxuan Huang, Juntai Cao, Sheng Xu, Xiang Zhuang, Zhangyang Gao, Muhammad Abdul-Mageed, Laks VS Lakshmanan, Chenyu You, Wanli Ouyang, Siqi Sun
Abstract
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.