Monte Carlo Tree Search (MCTS) is an effective test-time compute scaling (TTCS) method for improving the reasoning performance of large language models, but its highly variable execution time leads to severe long-tail latency in practice. Existing optimizations such as positive early exit, reduce latency in favorable cases but are less effective when search continues without meaningful progress. We introduce {\it negative early exit}, which prunes unproductive MCTS trajectories, and an {\it adaptive boosting mechanism} that reallocates reclaimed computation to reduce resource contention among concurrent searches. Integrated into vLLM, these techniques substantially reduce p99 end-to-end latency while improving throughput and maintaining reasoning accuracy.
Figures & tables
Figure 1: Two categories of the TTCS method: (a) sequential search and (b) parallel search. t denotes the time.
Figure 2: Comparison of search efficiency between Beam Search and MCTS, and the token reduction enabled by early exit, with MCTS using 12 rollouts and Beam Search using 8 beams.
Figure 3: End-to-end latency distribution of sequential MCTS (a) with and (b) without early exit. Maximum number of rollouts is 32.
Figure 4: Impact of parallelism on latency and accuracy. (a) Average latency per tree search decreases as parallelism increases. (b) Higher parallelism leads to minor fluctuations in accuracy. Results are reported on a subset of challenging problems that require generating a large number of tokens.
Figure 5: Overview of negative early exit mechanism with a acceptance threshold of τ=0.3 .
Figure 6: Selective Futility Check Mechanism. (a) Trajectories with low initial scores tend to yield low final scores. (b) Selective futility check leveraging this correlation.
Figure 7: Impact of request arrival rates on p50 (darker) and p99 (lighter) end-to-end latency across different search strategies.
Figure 8: Request throughput across various model-task configurations. PE and NE consistently increase throughput. PE+NE+Boosting yields throughput gains across most cases.
Method
Math500
amc23
Llama
Qwen
Llama
Qwen
Beam Search
72.9
87.1
52.5
67.5
MCTS (Vanilla)
75.3
88.3
57.5
72.5
MCTS + PE
76.2
88.3
47.5
69.2
Ours (Full Suite)
74.8
87.6
55.0
65.0
Table 1: Accuracy Comparison Across Optimizations (%)
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: Node-reusing MCTS algorithm with four phases.
Figure 10: Beam Search algorithm with beam width 2 and 4 sampled candidates per beam.
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
Test-time scaling improves the reasoning performance of large language models but incurs substantial cost in both total computation and latency. Existing adaptive sampling methods partially mitigate this issue by dynamically deciding when to stop sampling, yet they typically rely on heuristic rules or rely on distribution assumptions. In this work, we formulate adaptive sampling as a Markov decision process (MDP). We train a lightweight sampling controller with reinforcement learning (RL) to jointly balance answer correctness, latency, and computation cost. At each round, the controller decides to stop sampling or to acquire additional samples. Our method is lightweight which only relies on statistics of final answers, and can be trained and deployed on CPU. We further show that the resulting framework admits an interpretation as the Lagrangian relaxation of a constrained optimization problem with explicit budget constraints. Experiments against strong baselines such as ASC and ESC show that our method achieves improved trade-offs among answer correctness, sampling rounds, and total samples required.
Runpeng Dai, Tong Zheng, Rui Liu +2
University of North Carolina at Chapel Hill · University of Maryland, College Park · Washington University in St. Louis
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.
Leonid Ugadiarov, Yuri Kuratov, Aleksandr Panov +1