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

arXiv: https://arxiv.org/abs/2604.00510 · HTML: https://mlsanity.com/paper/2604.00510/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 1 Apr 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 16 of 16)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking](https://mlsanity.com/paper/2501.04519/) (2025)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement](https://mlsanity.com/paper/2410.20285/) (2024)
- [GenPRM: Scaling Test-Time Compute of Process Reward Models via Generative Reasoning](https://mlsanity.com/paper/2504.00891/) (2025)
- [Easy-to-Hard Generalization: Scalable Alignment Beyond Human Supervision](https://mlsanity.com/paper/2403.09472/) (2024)
- [Alibaba LingmaAgent: Improving Automated Issue Resolution via Comprehensive Repository Exploration](https://mlsanity.com/paper/2406.01422/) (2024)
- [Efficiently Scaling LLM Reasoning with Certaindex](https://mlsanity.com/paper/2412.20993/) (2024)
- [Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search](https://mlsanity.com/paper/2503.04412/) (2025)
- [Monte Carlo Planning with Large Language Model for Text-Based Game Agents](https://mlsanity.com/paper/2504.16855/) (2025)
- [Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search](https://mlsanity.com/paper/1810.11755/) (2018)

## Abstract (arXiv)

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.