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.