DeepSearch: Overcome the Bottleneck of Reinforcement Learning with
  Verifiable Rewards via Monte Carlo Tree Search
Authors: name: Fang Wu; name: Weihao Xuan; name: Heli Qi; name: Ximing Lu; name: Aaron Tu; name: Li Erran Li; name: Yejin Choi
Published: 2025-09-29 20:00:29

Abstract: Although RLVR has become an essential component for developing advanced
reasoning skills in LLMs, contemporary studies have documented training
plateaus that emerge following thousands of optimization steps, demonstrating
notable decreases in performance gains despite increased computational
investment. This limitation stems from the sparse exploration patterns inherent
in current RLVR practices, where models rely on limited rollouts that often
miss critical reasoning paths and fail to provide systematic coverage of the
solution space. We present DeepSearch, a framework that integrates Monte Carlo
Tree Search directly into RLVR training. In contrast to existing methods that
rely on tree search only at inference, DeepSearch embeds structured search into
the training loop, enabling systematic exploration and fine-grained credit
assignment across reasoning steps. Through training-time exploration,
DeepSearch addresses the fundamental bottleneck of insufficient exploration,
which leads to diminishing performance improvements over prolonged training
steps. Our contributions include: (1) a global frontier selection strategy that
prioritizes promising nodes across the search tree, (2) selection with
entropy-based guidance that identifies confident paths for supervision, and (3)
adaptive replay buffer training with solution caching for efficiency.
Experiments on mathematical reasoning benchmarks show that DeepSearch achieves
62.95% average accuracy and establishes a new state-of-the-art for 1.5B
reasoning models - using 5.7x fewer GPU hours than extended training
approaches. These results highlight the importance of strategic exploration
over brute-force scaling and demonstrate the promise of algorithmic innovation
for advancing RLVR methodologies. DeepSearch establishes a new direction for
scaling reasoning capabilities through systematic search rather than prolonged
computation.