DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search

• URL: http://arxiv.org/abs/2509.25454v2
• Date: Wed, 01 Oct 2025 05:09:42 GMT
• Title: DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search
• Authors: Fang Wu, Weihao Xuan, Heli Qi, Ximing Lu, Aaron Tu, Li Erran Li, Yejin Choi,
• Abstract summary: We present DeepSearch, a framework that integrates Monte Carlo Tree Search directly into RLVR training.<n>In contrast to existing methods that rely on tree search only at inference, DeepSearch embeds structured search into the training loop.<n>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.
• Score: 53.27052683356095
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• How to Train Your Deep Research Agent? Prompt, Reward, and Policy Optimization in Search-R1 [34.39666907043139]
  Deep Research agents tackle knowledge-intensive tasks through multi-round retrieval and decision-oriented generation.<n>We conduct a systematic study along three decoupled dimensions: prompt template, reward function, and policy optimization.<n>Our study reveals that 1) the Fast Thinking template yields greater stability and better performance than the Slow Thinking template used in prior work; 2) the F1-based reward underperforms the EM due to training collapse driven by answer avoidance; this can be mitigated by incorporating action-level penalties, ultimately surpassing EM.
  arXiv  Detail & Related papers  (2026-02-23T05:33:17Z)
• SimpleDeepSearcher: Deep Information Seeking via Web-Powered Reasoning Trajectory Synthesis [89.99161034065614]
  Retrieval-augmented generation (RAG) systems have advanced large language models (LLMs) in complex deep search scenarios.<n>Existing approaches face critical limitations that lack high-quality training trajectories and suffer from distributional mismatches.<n>This paper introduces SimpleDeepSearcher, a framework that bridges the gap through strategic data engineering rather than complex training paradigms.
  arXiv  Detail & Related papers  (2025-05-22T16:05:02Z)
• ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning [74.65632662894086]
  We propose ReSearch, a framework that trains LLMs to Reason with Search via reinforcement learning.<n>Our approach treats search operations as integral components of the reasoning chain, where when and how to perform searches is guided by text-based thinking.<n>Analysis reveals that ReSearch naturally elicits advanced reasoning capabilities such as reflection and self-correction.
  arXiv  Detail & Related papers  (2025-03-25T09:00:58Z)
• Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1-like reasoning approach is challenging, and researchers have been making various attempts to advance this open area of research.<n>We present a preliminary exploration into enhancing the reasoning abilities of LLMs through reward-guided tree search algorithms.
  arXiv  Detail & Related papers  (2024-11-18T16:15:17Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Reannealing of Decaying Exploration Based On Heuristic Measure in Deep Q-Network [82.20059754270302]
  We propose an algorithm based on the idea of reannealing, that aims at encouraging exploration only when it is needed. We perform an illustrative case study showing that it has potential to both accelerate training and obtain a better policy.
  arXiv  Detail & Related papers  (2020-09-29T20:40:00Z)
• PBCS : Efficient Exploration and Exploitation Using a Synergy between Reinforcement Learning and Motion Planning [8.176152440971897]
  "Plan, Backplay, Chain Skills" combines motion planning and reinforcement learning to solve hard exploration environments. We show that this method outperforms state-of-the-art RL algorithms in 2D maze environments of various sizes.
  arXiv  Detail & Related papers  (2020-04-24T11:37:09Z)
• Reinforcement Learning with Probabilistically Complete Exploration [27.785017885906313]
  We propose Rapidly Randomly-exploring Reinforcement Learning (R3L) We formulate exploration as a search problem and leverage widely-used planning algorithms to find initial solutions. We experimentally demonstrate the method, requiring only a fraction of exploration samples and achieving better performance.
  arXiv  Detail & Related papers  (2020-01-20T02:11:24Z)

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.