Adaptive Parallel Monte Carlo Tree Search for Efficient Test-time Compute Scaling

Computer Science > Artificial Intelligence [Submitted on 1 Apr 2026] Adaptive Parallel Monte Carlo Tree Search for Efficient Test-time Compute Scaling Hongbeen Kim, Juhyun Lee, Sanghyeon Lee, Kwanghoon Choi, Jaehyuk Huh 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. Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2604.00510 [cs.AI]   (or arXiv:2604.00510v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2604.00510 Focus to learn more Submission history From: Hongbeen Kim [view email] [v1] Wed, 1 Apr 2026 05:52:38 UTC (505 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-04 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)