mlsanityData to 7 Oct 2026

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

arXiv 2604.00510 ↗First posted 1 Apr 2026cs.AIcited by 0

On the map: LLM reasoning → Test-time compute and efficient thinking

also in 1 more
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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

16 of 35 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search6 Mar
  2. 2024Efficiently Scaling LLM Reasoning with Certaindex30 Dec
  3. 2024Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models1 Aug
  4. 2023Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training29 Sep

Other references · 12

  1. 2024The Llama 3 Herd of Modelscited by 14,192
  2. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  3. 2024Qwen2.5 Technical Reportcited by 4,713
  4. 2023Let's Verify Step by Stepcited by 3,598
  5. 2025The Lessons of Developing Process Reward Models in Mathematical Reasoningcited by 402
  6. 2025rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinkingcited by 308
  7. 2024SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinementcited by 124
  8. 2024Easy-to-Hard Generalization: Scalable Alignment Beyond Human Supervisioncited by 95
  9. 2025GenPRM: Scaling Test-Time Compute of Process Reward Models via Generative Reasoningcited by 94
  10. 2024Alibaba LingmaAgent: Improving Automated Issue Resolution via Comprehensive Repository Explorationcited by 58
  11. 2025Monte Carlo Planning with Large Language Model for Text-Based Game Agentscited by 22
  12. 2018Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Searchcited by 13

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs
  2. 2024Interpretable Contrastive Monte Carlo Tree Search Reasoning
  3. 2025Dynamic Parallel Tree Search for Efficient LLM Reasoning
  4. 2026When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models
  5. 2025MCTS-Judge: Test-Time Scaling in LLM-as-a-Judge for Code Correctness Evaluation
  6. 2025textttSPECS: Faster Test-Time Scaling through Speculative Drafts
  7. 2025First Finish Search: Efficient Test-Time Scaling in Large Language Models
  8. 2025Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey