Introduces negative early exit and adaptive boosting to make Monte Carlo Tree Search (MCTS) practical for real-time LLM inference.
April 2, 2026
Original Paper
Adaptive Parallel Monte Carlo Tree Search for Efficient Test-time Compute Scaling
arXiv · 2604.00510
The Takeaway
Test-time compute scaling (o1-style) is often too slow for production; this work drastically reduces p99 latency by pruning unproductive search trajectories. It allows for high-reasoning performance without the typical long-tail latency bottlenecks.
From the abstract
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 adap