PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Fang Wu, Weihao Xuan, Heli Qi, Ximing Lu, Aaron Tu, Li Erran Li, Yejin Choi

arXiv:2509.25454v4cs.AIcs.CL

TL;DR

RLVR training can plateau as sparse rollouts limit exploration of reasoning paths. DeepSearch integrates MCTS into RLVR training to explore systematically and assign credit across reasoning steps. It reports 62.95% average accuracy on mathematical reasoning benchmarks while using 5.7× fewer GPU hours.

  • Problem

    RLVR approaches rely on sparse training rollouts, while extended training can plateau after thousands of steps, leaving systematic exploration of the solution space limited.

    Source: §1 · p. 1

  • Method

    DeepSearch integrates MCTS into RLVR training, combining global frontier selection, entropy-guided supervision, and replay buffers with cached solutions.

    Source: §1 · p. 2, §4.2 · p. 6

  • Results

    62.95% average accuracy on mathematical reasoning benchmarks establishes a new state of the art for 1.5B models, using 5.7× fewer GPU hours.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The results suggest systematic exploration during training can, in many cases, provide greater gains than simply extending training time.

    Source: §6 · p. 10

    The work focuses on mathematical reasoning; extending DeepSearch to domains with distinct verification mechanisms remains future work.

    Source: LIMITATIONS AND FUTURE WORK · p. 26

Abstract

from arXiv · show

Although RLVR has become an essential component for developing advanced reasoning skills in language models, contemporary studies have documented training plateaus after thousands of optimization steps, i.e., 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 (MCTS) 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 gains over prolonged training. 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 an average accuracy of 62.95\% and establishes a new state-of-the-art reasoning model, while 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.

1 INTRODUCTION

DeepSearch embeds structured search into RLVR training to address sparse exploration and diminishing returns from prolonged training. It reports state-of-the-art mathematical reasoning accuracy for 1.5B models while using fewer GPU hours.

1 INTRODUCTION

  • RLVR training is constrained by sparse exploration, while prolonged training has shown performance plateaus after thousands of steps.The introduction questions whether simply increasing training steps is sufficient to realize RLVR’s potential.Source: §1 · pp. 1–2
  • DeepSearch embeds Monte Carlo Tree Search into RLVR training, using systematic exploration to provide supervision beyond correct solutions and direct rollouts.The framework shifts emphasis from scaling training depth to scaling training breadth.Source: §1 · p. 2
  • Its innovations include global frontier selection, entropy-guided selection of confident incorrect paths, and replay buffers that cache verified solutions.The replay strategy filters challenging problems and avoids redundant computation across training iterations.Source: §1 · p. 2
  • 62.95% average accuracy on mathematical reasoning benchmarks establishes a new state of the art for 1.5B reasoning models, using 5.7× fewer GPU hours.The paper presents this as more effective and practical than conventional approaches.Source: §1 · p. 2
  • The paper frames systematic training-time exploration as an alternative to prolonged training for scaling RLVR, with implications extending beyond mathematical reasoning.It argues for structuring learning to mirror sophisticated reasoning expected at inference time.Source: §1 · p. 2

2 RELATED WORKS

Prior work studies search at inference and RLVR training with direct rollouts, but integrating search into RLVR training remains largely unexplored. MCTS has broad applications, yet its effective use during RLVR training is unclear.

Search-based reasoning

  • Most search-based reasoning frameworks explore multiple solution paths at inference, while joint optimization of search and learning remains largely unexplored [23].These frameworks combine policy models, reward models, and search algorithms, including MCTS and beam search.Source: §2 · p. 3

Reinforcement learning from verifiable rewards

  • RLVR extensions improve training stability and efficiency, but predominantly use direct rollouts that can constrain systematic solution-space exploration [24].Source: §2 · p. 3

Monte Carlo Tree Search

  • MCTS has been applied across games, robotics, theorem proving, and other domains, but its effective use during RLVR training remains unclear [25].Source: §2 · p. 3

3 DEEPSEARCH WITH MCTS

DeepSearch builds stepwise reasoning trees with MCTS, verifies terminal solutions, and backs up trajectory scores. Entropy-guided selection and a hybrid local-global search strategy guide exploration and supervision.

3 DEEPSEARCH WITH MCTS

  • DeepSearch builds a stepwise MCTS tree from the question, with policy-generated intermediate steps and q-values assigned along terminal trajectories.A trajectory may end in a correct, incorrect, or incomplete solution.Source: §3 · p. 3

3.1 EXPANSION WITH ENTROPY-BASED GUIDANCE

  • For expansion, the policy generates candidate reasoning steps until a terminal answer or depth limit, then verification guides selection of the lowest-entropy incorrect trajectory for supervision.The paper reports that selecting the most-confident incorrect trajectory outperforms random and least-confident selection across benchmarks.Source: §3.1 · pp. 3–4

3.2 HEURISTIC SCORE BACKUP

  • Score backup initializes node q-values at zero and propagates terminal rewards with depth decay; constrained updates preserve positive scores on correct paths while penalizing incorrect or incomplete outcomes.Terminal rewards are +1 for correct solutions and −1 for incorrect or incomplete ones.Source: §3.2 · p. 4

3.3 HYBRID SELECTION STRATEGY

  • The hybrid strategy uses UCT for local sibling comparisons and global frontier selection to distribute search across subtrees, with frontier priority incorporating parent quality, policy entropy, and depth.The authors state that this combination mitigates UCT’s myopia, avoids redundant traversals, and improves exploration coverage.Source: §3.3 · pp. 4–5

4 ADAPTIVE TRAINING STRATEGY WITH REPLAY BUFFER

The adaptive training strategy concentrates costly MCTS on challenging problems while replaying discovered solutions to preserve progress. Tree-GRPO trains on tree-structured reasoning traces with regularized q-values and node-level advantages.

4 ADAPTIVE TRAINING STRATEGY WITH REPLAY BUFFER

  • MCTS is computationally infeasible for every example, so iterative filtering and replay focus search on challenging problems while retaining solved ones.Source: §4 · p. 5

4.1 ITERATIVE TRAINING WITH PROGRESSIVE FILTERING

  • After each phase, the policy is reevaluated on the hard subset, and a 25% threshold retains problems with insufficient success rates for further training.The initial subset is constructed by evaluating direct rollouts on the full training set, sampling four solutions per problem.Source: §4.1 · pp. 5–6

4.2 REPLAY BUFFER WITH CACHED SOLUTIONS

  • Cached correct trajectories are combined with fresh direct rollouts, while uncached problems receive full MCTS; this avoids redundant search and preserves solutions.Incorrect samples containing garbled text or infinite repetitions are removed.Source: §4.2 · p. 6

4.3 TREE-GRPO TRAINING OBJECTIVE

  • Tree-GRPO combines q-value regularization with policy optimization to train from tree-structured reasoning traces.The objective uses a 4096-token response-length penalty and removes KL regularization.Source: §4.3 · pp. 6–7
  • Soft clipping bounds intermediate-node q-values to [−qmax, qmax] while preserving gradients and their relative ordering.Terminal-node q-values are unchanged; fewer than about 5% of intermediate values fall in the saturation region.Source: §4.3 · pp. 6–7
  • Node-level advantages use each node’s q-value relative to the tree’s mean terminal reward, enabling finer credit assignment across reasoning steps.Using terminal outcome rewards for every node reduces Tree-GRPO to vanilla DAPO.Source: §4.3 · p. 7

5 EXPERIMENTS

DeepSearch outperforms the previous best 1.5B model on average mathematical-benchmark accuracy and uses substantially fewer GPU hours than extended training. Ablations and training-dynamics results examine how global search, depth guidance, and trajectory selection contribute to its approach.

5.2 TRAINING EFFICIENCY ANALYSIS

  • 325 additional training steps achieve 61.78% accuracy with 326.4 GPU hours, while 1,875 steps reach 62.02% despite 1,883.2 GPU hours.The authors characterize these extended-training gains as diminishing returns; Figure 2 plots average AIME 2024, AIME 2025, and AMC 2023 performance after 3K RLVR training, with evaluation markers and linear trends.Source: §5.2 · pp. 7–8, Figure 2 · p. 8

5.1 BENCHMARK PERFORMANCE EVALUATION

  • 62.95% average accuracy lets DeepSearch-1.5B outperform the previous best, Nemotron-Research-Reasoning-Qwen-1.5B v2, at 61.70%, across six mathematical benchmarks.Notable gains include AIME 2024 (53.65% vs 51.77%) and AMC (90.39% vs 88.83%).Source: §5.1 · p. 7, Table 1 · p. 8

5.2 TRAINING EFFICIENCY ANALYSIS

  • 62.95% accuracy with 330 GPU hours gives DeepSearch a 5.7× resource reduction versus the most extensive baseline, which used 1,883.2 GPU hours.The paper reports that this comparison uses 50 additional training steps for DeepSearch; extended training reached 62.02% after 1,875 steps and 1,883.2 GPU hours.Source: Table 2 · p. 8, §5.2 · p. 8
  • After 3K RLVR training, DAPO improves gradually with a shallow slope, whereas DeepSearch shows more efficient learning through structured exploration over 20 hours.The authors interpret the convergence comparison as suggesting that exploration quality, rather than training time alone, is a bottleneck.Source: Figure 2 · p. 8, §5.2 · p. 8

5.3 SEARCH STRATEGY ABLATION

  • Global frontier selection reduces iterations by 10.4% (209.6 → 187.7) and improves trajectory reward (−0.82 → −0.65) versus vanilla UCT, with similar depth and entropy.The comparison uses 1.2K samples from extremely hard DeepMath-103K problems.Source: Table 3 · p. 9, §5.3 · p. 9
  • Linear depth bonuses cut per-tree time by 59% (1179.6s → 480.9s) but reduce solution quality; the square-root bonus retains −0.65 reward, while uncertainty weighting raises entropy from 1.23 to 1.31.The uncertainty bonus also introduces computational variability, with 92.5 ± 22.5 iterations.Source: §5.3 · p. 9

5.4 ALGORITHM EVOLUTION AND COMPONENT CONTRIBUTIONS

  • Outcome-based advantages yield more stable credit assignment, node-level advantages target individual reasoning steps, and mean-only normalization addresses GRPO miscalibration while maintaining stable scaling.The ablation reports global frontier selection as the largest single component improvement, with each component contributing meaningfully to final performance.Source: §5.4 · pp. 9–10
  • Selecting the lowest-entropy incorrect trajectory achieves the best average performance: +0.86 over random selection and +1.05 over least-confident selection, with gains across all benchmarks.The comparison treats low average trajectory entropy as the model’s most confident mistake.Source: Table 5 · p. 10, §5.4 · p. 10

6 CONCLUSION

DeepSearch integrates tree-based search into RLVR training to address exploration bottlenecks. On mathematical reasoning benchmarks, it reports 62.95% average accuracy for 1.5B models while using 5.7× fewer GPU hours.

6 CONCLUSION

  • 62.95% average accuracy on mathematical reasoning benchmarks establishes a new state-of-the-art for 1.5B models, with 5.7× fewer GPU hours.The comparison is with extended training approaches.Source: §6 · p. 10
  • DeepSearch integrates tree-based search into RLVR training to address exploration bottlenecks associated with performance plateaus.Source: §6 · p. 10
  • The conclusion argues that systematic training-time exploration can in many cases yield greater gains than simply extending training time.It frames this as scaling training breadth through algorithmic innovation rather than relying solely on deeper compute.Source: §6 · p. 10

A EXPERIMENTAL DETAILS

The experimental setup uses veRL for DeepSearch training and a larger H100 cluster for evaluation. Training uses DeepMath-103K with a specified prompt, sequence limits, and dynamic batching.

A EXPERIMENTAL DETAILS

  • DeepSearch is implemented in veRL, trained on 16 H100 GPUs, and evaluated on a 128 H100 cluster to reduce wall-clock time.The policy starts from Nemotron-Research-Reasoning-Qwen-1.5B v2, with DAPO-based extended training using the same initialization and training configuration for comparison.Source: §A.1 · p. 15

A.1 TRAINING DATA AND CONFIGURATION

  • Training uses DeepMath-103K and a step-by-step prompt template, with prompts truncated to 2,048 tokens and responses capped at 16,384 tokens.Source: §A.1 · p. 15
  • A global batch size of 256 samples uses DAPO-style Dynamic Batching to optimize memory utilization and training efficiency.Source: §A.1 · p. 15

A.2 MONTE CARLO TREE SEARCH IMPLEMENTATION

The appendix specifies DeepSearch's search, optimization, sampling, and training settings, then explains the rationale for its depth cap, expansion length, and asymmetric q-value backup.

A.2 MONTE CARLO TREE SEARCH IMPLEMENTATION

  • Global Frontier Selection and depth-based bonuses guide backtracking, while entropy is estimated from sampled response tokens as a proxy for decision confidence.The implementation sets maximum depth to 64, allocates 256 tokens per node, expands 8 children, and uses UCT local-selection λ = 2.0.Source: §A.2 · p. 15

A.3 ADVANTAGE ESTIMATION AND OPTIMIZATION

  • Advantage estimation uses GRPO with sibling-mean normalization; q-values are soft-clipped, incomplete trajectories receive −1.0, and standard-deviation normalization is disabled.The actor uses AdamW at 1 × 10^-6 learning rate, with 10 warmup steps, weight decay 0.1, and gradient clipping at 1.0.Source: §A.3 · p. 15

A.4 SAMPLING AND REWARD CONFIGURATION

  • Rollouts use temperature 1.0 with 8 samples per prompt, and evaluation uses temperature 0.6; rewards score the final boxed answer against ground truth.The scoring logic follows veRL's DAPO normalization and supports responses up to 16,384 tokens.Source: §A.4 · p. 16

A.5 TRAINING PROTOCOL

  • Training runs for 100 steps, with model checkpoints saved every 5 steps.Source: §A.5 · p. 16

B.1 MAXIMUM DEPTH AND EXPANSION LENGTH

  • The 16,384-token rollout budget and 256-token expansions imply an approximate 64-step depth cap, which covers nearly all reasoning chains in DeepMath-103K.The cap is an upper bound because many trajectories terminate earlier, and it is framed as a trade-off between modeling requirements and training efficiency.Source: §B.1 · p. 16
  • A 64-level maximum depth follows from the 16,384-token rollout budget and 256-token node expansions; 256 tokens balances search coverage, stability, and efficiency.Longer expansions reduce tree breadth, while shorter ones raise prefix re-encoding costs that dominate GPU time in MCTS exploration.Source: §B.1 · p. 16

B.2 RATIONALE BEHIND THE ASYMMETRIC Q-VALUE BACKUP RULE

  • Asymmetric backup preserves nonnegative q-values for nodes ever seen on correct trajectories, while only never-correct nodes can accumulate stable negative values.Same-sign evidence accumulates with depth decay; a negative-to-positive transition overwrites the negative value, and positive nodes are protected from later negative signals.Source: §B.2 · p. 17

B.3 EVOLUTION OF CACHED VS. UNSOLVED PROBLEMS DURING ADAPTIVE TRAINING

Across adaptive-training rounds, MCTS adds verified solutions to the replay buffer and shifts computation toward harder remaining problems. The pipeline uses a fixed success-rate threshold to select the next hard set.

B.3 EVOLUTION OF CACHED VS. UNSOLVED PROBLEMS DURING ADAPTIVE TRAINING

  • By Round 5, one-third of the hard subset has at least one cached solution, while unsolved problems contract to extremely difficult tail cases.The cached proportion increases as MCTS uncovers verifiable solution paths and problems move from the unsolved pool into the replay buffer.Source: §B.3 · p. 17

B.4 ON THE CHOICE OF A FIXED FILTERING THRESHOLD δ

  • Each round retains problems with Pass1@4 success rates below δ = 25% for the next hard set, filtering mastered problems while preserving challenging cases.Source: §B.4 · p. 17
  • The authors use a fixed threshold to avoid adding schedules and hyperparameters and to keep the contribution of MCTS-based exploration clear.Adaptive thresholding is left as a possible direction, while this work demonstrates gains using a fixed hard-sample selection rule.Source: §B.4 · p. 18

C COMPUTATION PROFILING

DeepSearch profiling finds GPU policy inference dominates per-tree runtime, while the framework combines MCTS exploration with adaptive training and cached solutions.

C COMPUTATION PROFILING

  • 1060.76 ms for tgenerate accounts for more than 99% of per-tree computation, while CPU-side operations take only a few milliseconds.The profiling table reports per-component times in milliseconds as mean ± standard deviation.Source: Table 7 · p. 18, C COMPUTATION PROFILING · p. 18

D PSEUDOCODE OF DEEPSEARCH

  • Algorithm 1 integrates MCTS-based exploration with adaptive training, progressively allocating resources to challenging problems while retaining previously solved solutions through caching.The framework trains from correct solutions and systematic exploration rather than outcome-based supervision alone.Source: D PSEUDOCODE OF DEEPSEARCH · p. 18
  • For cached problems, the pseudocode combines the cached solution with direct rollouts, while uncached problems receive full MCTS search.The pseudocode also includes frontier selection, terminal-state evaluation, and replay-buffer updates.Source: D PSEUDOCODE OF DEEPSEARCH · p. 19

E QUALITATIVE CASE STUDIES

Six representative math-benchmark cases compare DeepSearch-1.5B with Nemotron-Research-Reasoning-Qwen-1.5B v2, illustrating differences in hesitation, error correction, and answer reliability.

E QUALITATIVE CASE STUDIES

  • The case studies present lightly abridged reasoning traces from different datasets to illustrate hesitation patterns, error correction, and final-answer reliability.The comparison includes the original questions and model-generated traces.Source: E QUALITATIVE CASE STUDIES · p. 20
  • Across six examples, DeepSearch-1.5B reaches correct solutions with shorter, more stable reasoning, while Nemotron often loops through hesitation and sometimes ends incorrectly.The cases span different problem types and datasets.Source: E QUALITATIVE CASE STUDIES · p. 20
  • In the symbolic-logic example, Nemotron produces over a thousand hesitation markers, while DeepSearch uses two orders of magnitude fewer tokens and reaches the correct value.The DeepSearch trace maintains algebraic consistency in this example.Source: E QUALITATIVE CASE STUDIES · p. 20

LIMITATIONS AND FUTURE WORK

The authors identify broader domains and learned search guidance as directions for extending DeepSearch beyond its current mathematical-reasoning setting.

LIMITATIONS AND FUTURE WORK

  • Extending DeepSearch beyond mathematical reasoning requires work on domains with distinct verification mechanisms.Proposed directions include approximate verifiers for subjective tasks and human-in-the-loop validation for complex reasoning chains.Source: LIMITATIONS AND FUTURE WORK · p. 26
  • Transfer learning and domain-agnostic reward and verification strategies are proposed to broaden the framework’s applicability.The authors also propose leveraging mathematical-reasoning capabilities for broader problem-solving tasks.Source: LIMITATIONS AND FUTURE WORK · p. 26
  • The frontier priority function and expansion width remain fixed heuristics; making search guidance learnable would require a different training paradigm.The authors propose exploring an AlphaZero-style controller that jointly optimizes search and policy.Source: LIMITATIONS AND FUTURE WORK · p. 26

Related papers

Loading 2509.25454v4…