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

• URL: http://arxiv.org/abs/2604.00510v1
• Date: Wed, 01 Apr 2026 05:52:38 GMT
• Title: Adaptive Parallel Monte Carlo Tree Search for Efficient Test-time Compute Scaling
• Abstract summary: Monte Carlo Tree Search (MCTS) is an effective test-time compute scaling (TTCS) method for improving the reasoning performance of large language models.<n>Existing optimizations such as positive early exit, reduce latency in favorable cases but are less effective when search continues without meaningful progress.<n>We introduce it negative early exit, which prunes unproductive MCTS trajectories, and it adaptive boosting mechanism that reallocates reclaimed to reduce resource contention.
• Score: 5.526787431354678
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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.

Related papers

• Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees [68.04613115686509]
  Self-consistency boosts inference-time performance by sampling multiple reasoning traces in parallel and voting.<n>We propose Distinct Leafion (DLE), a deterministic decoding method that treats truncated sampling as a pruned tree and systematically enumerates distinct leaves instead of sampling with replacement.<n>DLE explores higher-quality reasoning traces, yielding better performance on math, coding, and general reasoning tasks.
  arXiv  Detail & Related papers  (2026-04-22T12:42:03Z)
• Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
  Inference-time compute has re-emerged as a practical way to improve LLM reasoning.<n>Most test-time scaling (TTS) algorithms rely on autoregressive decoding.<n>We propose Prism, an efficient TTS framework for dLLMs.
  arXiv  Detail & Related papers  (2026-02-02T09:14:51Z)
• Hidden States as Early Signals: Step-level Trace Evaluation and Pruning for Efficient Test-Time Scaling [19.080366193748127]
  Large Language Models (LLMs) can enhance reasoning capabilities through test-time scaling by generating multiple traces.<n>The combination of lengthy reasoning traces with multiple sampling introduces substantial computation and high end-to-end latency.<n>We propose STEP: Step-level Trace Evaluation and Pruning, a novel pruning framework that evaluates reasoning steps using hidden states.
  arXiv  Detail & Related papers  (2026-01-14T02:54:55Z)
• Seer Self-Consistency: Advance Budget Estimation for Adaptive Test-Time Scaling [55.026048429595384]
  Test-time scaling improves the inference performance of Large Language Models (LLMs) but also incurs substantial computational costs.<n>We propose SeerSC, a dynamic self-consistency framework that simultaneously improves token efficiency and latency.
  arXiv  Detail & Related papers  (2025-11-12T13:57:43Z)
• Noise Hypernetworks: Amortizing Test-Time Compute in Diffusion Models [57.49136894315871]
  New paradigm of test-time scaling has yielded remarkable breakthroughs in reasoning models and generative vision models.<n>We propose one solution to the problem of integrating test-time scaling knowledge into a model during post-training.<n>We replace reward guided test-time noise optimization in diffusion models with a Noise Hypernetwork that modulates initial input noise.
  arXiv  Detail & Related papers  (2025-08-13T17:33:37Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree.<n>We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference.<n> Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• SETS: Leveraging Self-Verification and Self-Correction for Improved Test-Time Scaling [39.57154199908565]
  Self-Enhanced Test-Time Scaling (SETS) is a simple yet effective approach that overcomes limitations by strategically combining parallel and sequential techniques.<n>SETS exploits the inherent self-verification and self- computation capabilities of Large Language Models, unifying sampling, verification, and correction within a single framework.<n>Our results show SETS achieves significant performance improvements and more advantageous test-time scaling behavior than the alternatives.
  arXiv  Detail & Related papers  (2025-01-31T17:03:16Z)
• CQIL: Inference Latency Optimization with Concurrent Computation of Quasi-Independent Layers [21.91815582658188]
  Large scale language models are delivering unprecedented performance on almost all natural language processing tasks. The overwhelming complexity incurs a high inference latency that negatively affects user experience. We propose to identify quasi-independent layers, which can be concurrently computed to significantly decrease inference latency.
  arXiv  Detail & Related papers  (2024-04-10T03:30:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.