Adaptive Parallel Monte Carlo Tree Search for Efficient Test-time Compute Scaling
This work addresses latency issues in MCTS for LLM reasoning, offering practical improvements for deployment efficiency, though it is incremental as it builds on existing optimizations.
The paper tackled the problem of high and variable latency in Monte Carlo Tree Search (MCTS) for test-time compute scaling in large language models by introducing negative early exit and adaptive boosting, resulting in reduced p99 latency and improved throughput while maintaining accuracy.
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.