ASE-MCTS: Asynchronous Self-Evaluated Monte Carlo Tree Search for Efficient LLM Reasoning
Abstract
AbstractMonte Carlo Tree Search (MCTS) is a promising test-time method for improving LLMs on hard reasoning problems, where correct trajectories are often sparse. Self-evaluated MCTS is attractive because it avoids external reward models, verifiers, and stronger judges, but it faces a central paradox: MCTS depends on reliable intermediate rewards, while LLM self-evaluation is noisy and unstable. We propose ASE-MCTS, an Asynchronous Self-Evaluated MCTS framework. ASE-MCTS uses search-oriented reward analysis to derive an effective composition of rollout, process, and pairwise rewards from their global and local search roles. It further combines flexible search-space control with dependency-aware asynchronous execution, reducing redundant exploration and latency. Experiments on mathematical and scientific reasoning benchmarks show that ASE-MCTS improves reasoning without external supervision, especially on hard sparse-trajectory problems, and achieves up to a 6× wall-clock speedup over Sync-MCTS in the branch-factor scalability experiment.