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

ArXiv: 2509.25454

🎯 Pitch

Simply training LLMs longer with direct policy rollouts hits a wall, where thousands more steps yield near-zero accuracy gains. DeepSearch breaks through this plateau by embedding Monte Carlo Tree Search into the training loop, using the tree's structured failures to teach the model exactly which reasoning paths it is missing, and it reaches a new state-of-the-art for 1.5B models while using 5.7× fewer GPU hours than prolonged training.

---

1. Executive Summary

DeepSearch introduces a framework that embeds Monte Carlo Tree Search (MCTS) directly into reinforcement learning with verifiable rewards (RLVR) training, addressing the exploration bottleneck that causes performance plateaus after thousands of optimization steps. The core innovation is a global frontier selection strategy (prioritizing promising nodes across the entire search tree rather than following traditional root-to-leaf UCT traversals), coupled with entropy-based guidance (selecting the most confident incorrect reasoning trajectories for targeted supervision) and an adaptive replay buffer (progressively filtering challenging problems while caching verified solutions to avoid redundant computation). Trained on DeepMath-103K and evaluated on six mathematical reasoning benchmarks, DeepSearch-1.5B achieves 62.95% average accuracy — a new state-of-the-art for 1.5B models — while using 5.7× fewer GPU hours than extended training approaches (330 hours versus 1,883.2 hours for a baseline that plateaus at lower accuracy), establishing that systematic exploration during training can outperform brute-force scaling of training steps only when the exploration strategy actively surfaces the reasoning paths that direct policy rollouts systematically miss.

2. Context and Motivation

The Core Problem: RLVR Training Hits a Wall That Brute-Force Scaling Cannot Break

The paper addresses a specific, empirically documented failure mode in reinforcement learning with verifiable rewards (RLVR) for language model reasoning: training plateaus where additional compute investment yields sharply diminishing returns. This is not a hypothetical concern — the paper presents concrete evidence in Table 2, showing that extended RLVR training produces the following trajectory:

• Starting from DeepSeek-R1-Distill-Qwen-1.5B (49.46% average math accuracy)
• After 2,000 DAPO steps: 60.10% accuracy (16,000 GPU hours)
• After 3,000 DAPO steps: 61.70% accuracy (24,000 GPU hours, the Nemotron v2 baseline)
• After +325 additional steps beyond v2: 61.78% accuracy (326.4 GPU hours)
• After +785 additional steps: 62.08% accuracy (788.8 GPU hours)
• After +1,875 additional steps: 62.02% accuracy (1,883.2 GPU hours)

The pattern is stark: the first 2,000–3,000 steps produce substantial improvements (~10–12 percentage points), but the next ~1,900 steps collectively contribute less than 0.5 percentage points, and performance actually regresses from the intermediate checkpoint. This is a clear saturation signal — the training process has exhausted whatever signal direct policy rollouts can provide.

This matters because the dominant paradigm in RLVR for reasoning — exemplified by DeepSeek-R1 (Guo et al., 2025), DAPO (Yu et al., 2025), and the Nemotron series (Liu et al., 2025a) — treats scaling as a matter of training depth: run more optimization steps, process more rollouts, and expect monotonic improvement. The evidence in Table 2 and Figure 2 shows this assumption breaks down. After a certain point, the model's policy generates essentially the same distribution of rollouts, and those rollouts contain no new information about how to reason correctly. Gradient updates continue, but they're optimizing over a stale exploration signal.

The authors frame this as a fundamental exploration bottleneck (Section 1):

"Current RLVR approaches remain constrained by sparse exploration patterns during training... models are expected to demonstrate sophisticated search behaviors only at inference time."

In plain language: during training, the model learns from whatever solutions it happens to sample under its current policy. If those solutions systematically miss certain reasoning paths — because the policy collapses to high-probability but limited strategies — the model never sees counterexamples that would teach it to correct those blind spots. The training signal is bounded by the diversity of the policy's own rollouts, creating a self-reinforcing cycle: narrow exploration → narrow learning → narrow policy → even narrower exploration.

Why This Problem Matters Now

The paper's timing is significant. As of early 2025, RLVR had become "an essential component for developing advanced reasoning skills in language models" (Section 1 abstract), driven by the success of models like DeepSeek-R1 and its open-source descendants. The community had largely converged on a recipe: start with a strong base model, apply GRPO-style RL with outcome-based verifiable rewards (math answer checking, code unit tests), and scale training steps. The Nemotron v1 → v2 progression (2,000 → 3,000 DAPO steps for +1.53% average accuracy) already showed signs of diminishing returns, but it took the extended training experiments in Table 2 to expose the full extent of the plateau.

The practical stakes are high. If RLVR plateaus after a few thousand steps, then:

• Compute budgets are being wasted: The 1,883.2 GPU hours spent on extended training (Table 2, last row) achieved worse results than the 330 GPU hours spent by DeepSearch. That's 5.7× more resources for a net loss in accuracy.
• Model capability ceilings are lower than expected: If no amount of additional RLVR training can push a 1.5B model past ~62% on these math benchmarks, then the scaling path for small reasoning models is blocked — you'd need to scale model size, not just training, to make further progress.
• The inference-time search advantage remains untapped during training: Sophisticated search strategies (tree search, beam search, best-of-N with verifiers) work well at inference time (Snell et al., 2024; Wu et al., 2024; Zhang et al., 2024c), but they're applied after the model is frozen. The model never learns from the exploration patterns those search strategies uncover.

The paper's motivation is thus both practical (stop wasting GPU hours on diminishing-return training) and conceptual (rethink the relationship between exploration and learning in RLVR).

Prior Approaches and Where They Fall Short

The paper situates itself against two broad categories of prior work, identifying specific limitations in each.

Search-Based Reasoning (Inference-Only). A substantial body of work has developed structured search strategies for LLMs at inference time. Tree-of-Thoughts (Yao et al., 2023) introduced explicit tree search over reasoning paths, using the LLM itself to generate and evaluate intermediate steps. Subsequent work refined this paradigm with better reward models (Lightman et al., 2023; Wang et al., 2023), more efficient search algorithms (Zhang et al., 2024a; Chen et al., 2024), and analysis of compute-optimal scaling (Snell et al., 2024). The defining characteristic of all this work is that search operates only at inference time — the policy model remains frozen, and the search process is external to the model's training. The model learns nothing from the search it performs; it merely outputs the highest-scored path.

The limitation is clear: if a model could learn from systematic exploration during training, it might internalize reasoning patterns that it currently relies on external search to discover. Conversely, if the model never encounters certain reasoning structures during training, even the best inference-time search cannot compensate — the model simply doesn't generate those paths in the first place. The paper cites this gap explicitly (Section 2):

"most methods restrict search to inference and do not integrate exploration signals into training, leaving the potential for jointly optimizing search and learning largely unexplored."

Reinforcement Learning with Verifiable Rewards (RLVR). The RLVR paradigm, as implemented in methods like DeepSeek-R1 (Guo et al., 2025), DAPO (Yu et al., 2025), and ProRL (Liu et al., 2025a), trains language models using outcome-based reward signals from automatically verifiable tasks (math answer checking, code execution). These methods generally use GRPO-style policy optimization with direct rollouts: the model samples $N$ solutions per problem, rewards are assigned based on correctness, and the policy is updated to increase the probability of high-reward outputs relative to a group baseline.

The critical weakness that DeepSearch identifies is the exploration mechanism (or lack thereof). Direct rollouts from the current policy $\pi_\theta$ behave like importance sampling: they draw from $\pi_\theta$'s current distribution, which is increasingly concentrated on high-probability regions as training progresses. The paper describes this as "blind sampling" (Section 5.5):

"Direct rollouts from $\pi_\theta$ behave like blind sampling: they quickly collapse into high-probability but low-diversity regions, rarely reaching deeper reasoning paths."

This creates an exploration-exploitation imbalance. RLVR relies on the stochasticity of sampling (temperature, top-p) to provide exploration, but this is inherently limited — it can only explore within the support of the current policy, not discover entirely new reasoning strategies. As the policy becomes more confident in its (potentially flawed) strategies, the probability of sampling corrective counterexamples decreases, and training stalls.

Recent work has attempted to address related issues. DAPO (Yu et al., 2025) introduced Clip-Higher and dynamic sampling to improve training stability. ProRL (Liu et al., 2025a) demonstrated that prolonged training yields continued improvements, but only up to a point — the very plateau that DeepSearch confronts. The Open-RS series explored various training recipes (Dang & Ngo, 2025). However, none of these approaches fundamentally change how the training data is generated; they all rely on direct policy rollouts.

Monte Carlo Tree Search in Other Domains. MCTS has a rich history in game-playing AI (Silver et al., 2016), robotics (Best et al., 2019), theorem proving (Lample et al., 2022), and combinatorial optimization (Fawzi et al., 2022). The AlphaGo paradigm — using MCTS both during training (to generate self-play data) and inference — is directly inspirational for DeepSearch. However, prior applications of MCTS to LLM reasoning (Zhang et al., 2024a;b;c; Qi et al., 2024) have almost exclusively used it as an inference-time search mechanism, not as a training data generation strategy. The paper notes this gap (Section 2):

"Despite the demonstrated potential of MCTS for heuristic exploration, it remains unclear how to effectively employ it during RLVR training."

The specific challenge is that running full MCTS rollouts for every training example would be computationally prohibitive. Section 4.1 acknowledges this directly: "applying MCTS to every training example is computationally infeasible." This is why prior work didn't attempt it — the naive approach is too expensive. DeepSearch's contribution is showing that with intelligent filtering (progressive hard-set selection), caching (replay buffer), and efficient node selection (global frontier scoring), MCTS can be made practical for RLVR training.

How DeepSearch Positions Itself

The paper's positioning is a direct intervention in the RLVR-as-scaling-problem narrative. Rather than asking "how many more training steps do we need?" it asks "how can we make each training step convey more information?"

The conceptual shift is from scaling training depth to scaling training breadth (Section 1):

"DeepSearch... represent[s] a fundamental shift from scaling training depth to scaling training breadth."

"Depth" here refers to the number of optimization steps (the axis explored by ProRL and extended training). "Breadth" refers to the diversity of reasoning paths explored during data generation for each step. The intuition is that a single training step informed by systematic tree search (which explores multiple reasoning branches, backpropagates rewards through intermediate nodes, and identifies high-confidence errors) provides richer supervision than many training steps informed by narrow direct rollouts.

This framing connects to a broader principle: the quality of exploration determines the ceiling of RL, not the quantity of optimization. When exploration is poor, RL converges to a local optimum determined by the initial policy's biases. When exploration is systematic — as MCTS provides — the policy encounters counterexamples to its flawed strategies and learns to avoid them.

DeepSearch does not claim to replace RLVR or inference-time search; rather, it proposes to integrate them:

• RLVR remains the optimization framework (specifically Tree-GRPO, a variant of GRPO with node-level advantages derived from MCTS q-values).
• MCTS becomes the exploration strategy that generates training data, replacing direct rollouts for hard problems.
• Inference-time search remains available, but now the model has been trained on trajectories that incorporate tree-structured exploration, potentially making it more amenable to search-based decoding.

The paper explicitly positions this as filling a gap between two previously disconnected lines of work (Section 2): search-based reasoning (which stays at inference) and RLVR (which relies on shallow exploration). By embedding MCTS into the training loop, DeepSearch aims to achieve what neither approach achieves alone: a model that learns from systematic exploration rather than from random sampling.

The Specific Technical Gap: Credit Assignment Across Reasoning Steps

Beyond the high-level exploration argument, the paper identifies a more granular technical gap: fine-grained credit assignment. In standard RLVR with outcome rewards, every token in a solution receives the same reward signal — +1 if the final answer is correct, 0 (or −1) otherwise. This is "outcome-based supervision" (Section 1). The problem is that a correct final answer can mask intermediate reasoning errors (the model made a mistake but coincidentally arrived at the right answer), and an incorrect final answer provides no signal about which step went wrong.

PRM-based methods (Lightman et al., 2023; Wang et al., 2023) address this at inference time by scoring individual steps, but they don't feed those step-level signals back into training. DeepSearch's MCTS backpropagation (Section 3.2) assigns q-values to intermediate nodes based on whether they lie on paths that ultimately lead to correct solutions. These q-values then serve as token-level advantages in the Tree-GRPO objective (Section 4.3, Equation 14). This means the model receives a differentiated signal: tokens on promising branches get positive reinforcement, tokens on dead-end branches get penalized, even if both branches share the same final outcome reward.

This credit assignment capability is a direct consequence of tree-structured exploration: you need to explore multiple continuations from the same intermediate step to know whether that step was good or bad. Direct rollouts can't provide this — you only see one continuation per prefix, so you can't distinguish a good step that happened to be followed by a mistake from a bad step that happened to be followed by a lucky correction.

Summary of the Gap and the Response

The paper thus positions itself not as an incremental improvement to RLVR but as a structural change to how training data is generated during RLVR — replacing blind sampling with guided exploration — motivated by the clear empirical evidence that the blind-sampling approach has hit a wall.

3. Technical Approach

3.1 Reader Orientation

DeepSearch is a training framework that replaces the standard random-sampling data generation in RLVR with a principled Monte Carlo Tree Search (MCTS) exploration engine. It solves the problem of training plateaus in reasoning models by making each training step more informative: instead of learning only from random rollouts that tend to collapse onto the same few reasoning patterns, the model learns from systematically explored solution trees that explicitly identify which intermediate reasoning steps lead to correct answers and which confident-looking steps lead to dead ends.

3.2 Big-Picture Architecture (Diagram in Words)

The DeepSearch system has five major components arranged in an iterative training loop:

1. The Policy Model ($\pi_\theta$) — a 1.5B-parameter language model initialized from Nemotron-Research-Reasoning-Qwen-1.5B v2 (itself trained via DAPO-style RLVR for 3,000 steps). This is the model being trained. It accepts a math problem as input and autoregressively generates reasoning steps.

2. The MCTS Exploration Engine — builds a search tree for each problem by iteratively (a) selecting promising frontier nodes using a global priority score, (b) expanding selected nodes by sampling $n = 8$ candidate next reasoning steps from $\pi_\theta$, (c) evaluating whether completed paths reach correct answers via a verifier $V$, and (d) backpropagating terminal rewards (+1 correct, −1 incorrect/incomplete) to intermediate nodes using depth-decayed q-value updates.

3. The Verifier ($V$) — a deterministic function that checks whether a complete reasoning trajectory's final answer (extracted from the last \boxed{} environment) matches the ground-truth answer, returning $V(s_{\text{end}}) = 1$ for correct and $V(s_{\text{end}}) = 0$ otherwise. This is outcome-based verification, not a learned process reward model.

4. The Adaptive Training Pipeline — manages which problems get full MCTS treatment versus cached solution reuse. It maintains: (a) a hard subset $\mathcal{D}_{\text{hard}}$ of problems the current policy fails to solve reliably (Pass1@4 < 25%), (b) a replay buffer $\mathcal{R}$ storing verified correct solution trajectories discovered by MCTS, and (c) a hybrid rollout strategy that inserts cached correct solutions directly into training data for previously-solved problems while running full MCTS only on remaining hard problems.

5. The Tree-GRPO Optimizer — updates $\pi_\theta$ using a modified GRPO objective where each token's advantage is derived from the q-value of the enclosing reasoning step (computed during MCTS backpropagation), rather than from the final outcome reward alone. This enables fine-grained credit assignment: tokens on branches that lead to correct solutions receive positive advantages, while tokens on dead-end branches receive negative advantages.

Information flows as follows: the current policy $\pi_\theta$ samples candidate reasoning steps during MCTS expansion → completed trajectories are verified against ground truth → terminal rewards are backpropagated through the tree to assign q-values to all intermediate nodes → successful trajectories are cached in the replay buffer → unsolved problems remain in the hard set for the next round → training batches are constructed by combining cached solutions with fresh MCTS rollouts → Tree-GRPO updates $\pi_\theta$ using per-node q-values as token-level advantages → the updated policy is re-evaluated on the hard set → problems that now pass the 25% success threshold are removed → the cycle repeats.

3.3 Roadmap for the Deep Dive

• First, the MCTS tree structure and node-level q-value semantics, because every subsequent component (expansion, selection, backup, training objective) operates on and modifies these q-values.
• Second, the expansion mechanism with entropy-based guidance, because this is how the tree grows and how the system decides which negative (incorrect) trajectories are worth learning from.
• Third, the heuristic score backup rule, because this determines how terminal rewards propagate to intermediate nodes and enables the fine-grained credit assignment that distinguishes DeepSearch from outcome-only RLVR.
• Fourth, the hybrid selection strategy (local UCT for siblings, global frontier scoring for next-expansion decisions), because this is the core algorithmic innovation that makes MCTS computationally efficient enough for training-time use.
• Fifth, the adaptive training strategy with progressive filtering and replay buffer, because this addresses the fundamental cost problem (MCTS is expensive — don't run it on problems you've already solved or that are trivially easy).
• Sixth, the Tree-GRPO training objective, because this connects the exploration engine's outputs (q-values) to the policy update, completing the loop from exploration to learning.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a systems and algorithms paper whose core idea is that embedding structured tree search into the RLVR data-generation process — rather than restricting search to inference time or relying on direct policy rollouts — overcomes the exploration bottleneck that causes training plateaus. The technical contribution comprises: (1) a novel MCTS variant with global frontier selection that makes training-time tree search computationally tractable, (2) an entropy-based mechanism for selecting the most informative incorrect trajectories for supervised learning, and (3) an adaptive curriculum with solution caching that progressively focuses computational resources on the hardest remaining problems.

---

MCTS Tree Structure and Q-Value Semantics

The search tree $\mathcal{T}$ is rooted at the problem statement $x$. Child nodes represent intermediate reasoning steps $s_i$ (blocks of up to 256 tokens generated autoregressively by $\pi_\theta$). A path from the root to a terminal node $s_{\text{end}}$ forms a complete trajectory:

$\mathbf{t} = x \oplus s_1 \oplus s_2 \oplus \cdots \oplus s_{\text{end}}$

where $\oplus$ denotes string concatenation and each step $s_i$ is a contiguous segment of the model's output.

Each node $s$ in the tree carries:

• A q-value $q(s) \in \mathbb{R}$: an estimate of whether this node tends to lead toward correct solutions (positive values) or toward dead ends (negative values). The q-value is updated during backpropagation (Section 3.2) and serves as the basis for token-level advantages in the Tree-GRPO objective.
• A visit count $N(s) \in \mathbb{Z}^+$: the number of times this node has been reached across all rollouts.
• A children count $\xi(s) \in \mathbb{Z}^+$: the number of child nodes generated from this node (equals $n = 8$ after expansion, 0 for unexpanded frontier nodes).
• A depth $d(s) \in \mathbb{Z}^+$: the number of edges from the root to this node. The root has $d(x) = 0$.

The frontier set $\mathcal{F}$ is the collection of all leaf nodes that have been generated but not yet expanded:

$\mathcal{F} = \{s \in \mathcal{T} \mid \xi(s) = 0, s \notin \mathcal{S}_{\text{end}}, d(s) < d_T\}$

where $\mathcal{S}_{\text{end}}$ is the set of terminal nodes (nodes that reached either a correct answer, a verifiably incorrect/incomplete state, or the maximum tree depth $d_T = 64$), and $d_T$ is the maximum allowed depth.

What this structure computes: the tree explicitly represents the branching exploration of reasoning paths. Unlike a flat set of independent rollouts (where each trajectory is isolated), the tree shares prefixes — if two trajectories share the same first three reasoning steps, those steps are represented as a single shared path that then branches. This sharing is what enables credit assignment: if 7 out of 8 branches from a shared prefix lead to correct answers, the prefix node's q-value will be high, indicating that the reasoning up to that point is reliable. If 0 out of 8 branches succeed, the q-value will be low, indicating a flawed strategy.

Why this form over alternatives: flat (non-tree) rollouts cannot assign credit to prefixes because each trajectory is generated independently — there is no mechanism to observe counterfactual continuations from the same intermediate state. A prefix that coincidentally leads to a correct answer in one rollout might be terrible on average, but you'd never know because you only sampled one continuation. Conversely, a prefix that failed in one rollout might be excellent if only a different next step had been chosen. The tree structure exposes these counterfactuals by forcing exploration of multiple children per node.

---

Expansion with Entropy-Based Guidance

At each expansion step, the system selects a frontier node $s^*$ (chosen via the hybrid selection strategy described below), constructs its observation (prefix) $o_{s^*} = x \oplus s_1 \oplus \cdots \oplus s^*$, and samples $n = 8$ candidate continuations from the policy:

$\{s_j\}_{j=1}^8 \sim \pi_\theta(\cdot \mid o_{s^*})$

Each candidate $s_j$ is a block of up to 256 tokens. The system then continues expanding greedily (always selecting the first sampled child at each subsequent step) until a terminal condition is reached for each branch: either the model outputs a final answer (detected by the presence of \boxed{}) or the maximum tree depth $d_T = 64$ is reached. The set of newly completed terminal nodes at expansion iteration $k$ is denoted $\mathcal{S}^{(k)}_{\text{end}}$.

The verifier $V: \mathcal{S}_{\text{end}} \to \{0, 1\}$ checks correctness by extracting the final boxed answer and comparing it (after text normalization) to the ground-truth answer. This partitions the terminal nodes:

$\mathcal{S}^{(k)}_{\text{correct}} = \{s \in \mathcal{S}^{(k)}_{\text{end}} \mid V(s) = 1\}$

$\mathcal{S}^{(k)}_{\text{incorrect}} = \{s \in \mathcal{S}^{(k)}_{\text{end}} \mid V(s) = 0\}$

What this computes: the expansion step grows the tree by one layer at the selected frontier node, generating 8 alternative next reasoning steps and then following each to completion (either correct answer or failure). The partition separates successful trajectories from failed ones.

The entropy-based negative selection rule. When no correct solution is found in the current expansion ($\mathcal{S}^{(k)}_{\text{correct}} = \emptyset$), the system must still extract a useful training signal. Rather than discarding the failed trajectories or selecting one at random, DeepSearch identifies the most confident mistake — the incorrect trajectory where the model exhibited the lowest average uncertainty during generation, indicating it was systematically wrong rather than randomly wrong:

$s^*_{\text{neg}} = \arg\min_{s \in \mathcal{S}^{(k)}_{\text{incorrect}}} \bar{H}(\mathbf{t}(s))$

where $\mathbf{t}(s) = (x, s_1, s_2, \ldots, s)$ is the unique trajectory from root to terminal node $s$, and the average trajectory entropy is:

$\bar{H}(\mathbf{t}(s)) = \frac{1}{|\mathbf{t}(s)|} \sum_{i=1}^{|\mathbf{t}(s)|} H(\pi_\theta(s_i \mid o_i))$

with the per-step entropy computed via Monte Carlo estimation over the token-level distribution:

$H(\pi_\theta(s_i \mid o_i)) = -\sum_{a_{i,k}} \pi_\theta(a_{i,k} \mid o_i, a_{i,<k}) \log \pi_\theta(a_{i,k} \mid o_i, a_{i,<k})$

where $a_{i,k}$ is the $k$-th token of step $s_i$, and $a_{i,<k}$ denotes all preceding tokens in that step.

What this computes: for each incorrect trajectory, we measure how "surprised" the model was by its own token choices along the way. Low entropy means the model was confident in its (wrong) decisions — every token was assigned high probability. High entropy means the model was uncertain, essentially guessing. The $\arg\min$ selects the trajectory with the lowest average entropy, i.e., the most confident incorrect path.

Why this form: the intuition is that confident mistakes expose systematic reasoning errors — the model genuinely believes in a flawed approach. Training on these examples corrects deep-seated misconceptions. In contrast, high-entropy (uncertain) incorrect trajectories represent random noise — the model was already unsure, so there's little systematic error to correct. Table 5 validates this empirically: selecting the most confident incorrect trajectory outperforms random selection (+0.86% average) and least-confident selection (+1.05% average). The least-confident strategy actually underperforms random selection, confirming that low-confidence errors are uninformative distractions.

Implementation note on entropy estimation: the paper approximates the per-step entropy using only the average token-level negative log-probability along the sampled trajectory (Appendix A.2), rather than summing over the full vocabulary. This is a computational efficiency trade-off: computing full-softmax entropy would require evaluating $\pi_\theta$ over the entire 100K+ vocabulary at every token position, which is infeasible at the scale of MCTS tree construction. The negative log-probability of the sampled tokens serves as a cheap, correlated proxy.

---

Heuristic Score Backup

After each expansion produces terminal nodes, one trajectory $\mathbf{t}^*$ is selected for backpropagation. If $\mathcal{S}^{(k)}_{\text{correct}} \neq \emptyset$, the system simply uses any correct trajectory (and all correct trajectories are extracted for the training dataset). If no correct solution exists, $\mathbf{t}^* = \mathbf{t}(s^*_{\text{neg}})$, the most confident incorrect trajectory.

Let $q^{(m)}(s_i)$ denote the q-value for node $s_i$ after $m$ rollouts of backpropagation. Terminal nodes receive their reward based on verification:

$q(s_{\text{end}}) = \begin{cases} +1 & \text{if } V(s_{\text{end}}) = 1 \text{ (correct)} \\ -1 & \text{if } V(s_{\text{end}}) = 0 \text{ (incorrect) or } d(s_{\text{end}}) < d_T \text{ (incomplete)} \end{cases}$

Intermediate node q-values are initialized to $q^{(0)}(s_i) = 0$ and updated using a depth-decayed propagation:

$q^{(m)}(s_i) = q^{(m-1)}(s_i) + \gamma(i, l) \cdot q^{(m)}(s_{\text{end}})$

where $\gamma(i, l): \mathbb{Z}^+ \times \mathbb{Z}^+ \to [0, 1]$ is the depth decay function:

$\gamma(i, l) = \max\left(\frac{i}{l}, \gamma_{\min}\right)$

with $i$ being the index of the current node in the trajectory (counting from 1 at the root), $l$ being the index of the terminal node, and $\gamma_{\min} = 0.1$ being the minimum decay floor.

What this computes: the terminal reward (+1 or −1) is propagated backward along the trajectory, with each node receiving a fraction of the terminal reward proportional to its position. Nodes closer to the terminal node receive larger updates (via $\gamma(i, l) = i/l$, which grows linearly from $1/l$ at the root to $l/l = 1$ at the terminal). The $\gamma_{\min} = 0.1$ floor ensures that even the root node receives at least 10% of the terminal reward, preventing the signal from vanishing completely for very deep trees.

Why this form over uniform backpropagation: the depth-dependent decay reflects the intuition that later reasoning steps are more directly responsible for the final outcome than early steps. A mistake in step 8 of a 10-step solution is more informative about where the reasoning went wrong than a generic "the whole thing failed" signal. However, early steps still matter — the $\gamma_{\min}$ floor prevents them from being completely ignored, which is important because a flawed assumption in step 1 can doom all subsequent reasoning even if the later steps are logically consistent.

The constrained update rule. To maintain certain invariants (specifically, that nodes ever observed on a correct trajectory retain non-negative q-values), the paper applies an asymmetric update:

$q^{(m)}(s_i) = \begin{cases} q^{(m-1)}(s_i) + \gamma(i, l) \cdot q^{(m)}(s_{\text{end}}) & \text{if } q^{(m-1)}(s_i) \cdot q^{(m)}(s_{\text{end}}) \geq 0 \\ \gamma(i, l) \cdot q^{(m)}(s_{\text{end}}) & \text{elif } q^{(m)}(s_{\text{end}}) > 0 \\ q^{(m-1)}(s_i) & \text{elif } q^{(m-1)}(s_i) > 0 \end{cases}$

What this computes — three cases in operational English:

1. Same sign reinforcement (line 1): If the node's current q-value and the terminal reward have the same sign (both positive or both negative), the update is the standard additive rule. Nodes on consistently correct paths accumulate positive evidence; nodes on consistently incorrect paths accumulate negative evidence.

2. Negative-to-positive transition (line 2): If a node currently has a negative q-value (it has only appeared in failed trajectories so far) but now lies on a correct trajectory ($q^{(m)}(s_{\text{end}}) > 0$), the accumulated negative evidence is discarded and the node is reset to a positive value $\gamma(i, l) \cdot q^{(m)}(s_{\text{end}})$. This implements the principle: "once a node is shown to lead to success even once, treat it as valuable rather than penalizing it for past failures."

3. Positive suppression of negative evidence (line 3): If a node already has a positive q-value (it has appeared on at least one correct trajectory), new negative terminal rewards are suppressed — the node keeps its existing positive value. This implements the principle: "a node proven capable of contributing to a correct solution should not be downgraded by occasional failures." Those failures could arise from downstream mistakes or stochastic expansions unrelated to this node's quality.

Why this constrained form: the asymmetry encodes a deliberate inductive bias toward optimism about nodes that have demonstrated value. In mathematical reasoning, a correct reasoning step is objectively correct — if it ever contributed to a valid solution, it remains a valid step regardless of how many unrelated failed attempts used it. The constraint prevents destructive interference where a node that correctly performed an essential algebraic manipulation gets its q-value driven negative by being included in many incorrect trajectories that failed for unrelated reasons (e.g., a later arithmetic error). Appendix B.2 provides further justification, establishing that this rule guarantees:

• Invariant 1: any node that has appeared on at least one correct trajectory retains a non-negative q-value.
• Invariant 2: only nodes never observed on any correct trajectory can accumulate stable negative values.

This separation is crucial for the training objective, where negative q-values are used to penalize specific reasoning patterns while positive q-values reinforce reliable ones.

---

Hybrid Selection Strategy

DeepSearch employs two distinct selection mechanisms operating at different granularities, motivated by the observation that traditional MCTS root-to-leaf UCT traversals are computationally wasteful and myopic for training-time tree search.

Local Selection for Sibling Comparison (UCT). When the selected frontier node $s^*$ is expanded, the policy generates $n = 8$ candidate children. To determine which children to add to the tree (and in what priority order for future expansion), the system uses the standard UCT formula applied to siblings:

$\text{UCT}(s) = Q(s) + \lambda \sqrt{\frac{\ln N_{\text{parent}}(s)}{N(s)}}$

where $Q(s) = q(s) / N(s)$ is the average reward per visit (the exploitation term), $N_{\text{parent}}(s)$ is the total number of visits from the parent node, $N(s)$ is the number of visits to this specific child node, and $\lambda = 2.0$ balances exploitation and exploration.

What this computes: for each child node, UCT estimates its value as the observed average reward plus an exploration bonus that decreases as the node is visited more frequently. The exploration bonus is proportional to $\sqrt{\ln N_{\text{parent}} / N(s)}$, which rewards under-visited children while asymptotically vanishing for well-explored children. This is the standard bandit-based selection rule from Kocsis & Szepesvári (2006).

Why UCT for siblings: within a single parent's children, the comparison is clean — all children share the same prefix context, so differences in their values reflect genuine differences in step quality. UCT provides principled exploration-exploitation balancing in this local setting.

Global Frontier Selection for Next Expansion. After each expansion-backup cycle, the system must decide which node to expand next. Instead of descending from the root using UCT at each level (the traditional approach), DeepSearch directly compares all frontier nodes simultaneously using a global priority score:

$F(s) = \lambda_1 \times \underbrace{\tanh(Q_{\text{parent}}(s))}_{\text{Quality Potential}} + \lambda_2 \times \underbrace{H(\pi_\theta(s \mid o_s))}_{\text{Uncertainty Bonus}} + \lambda_3 \times \underbrace{D(d(s))}_{\text{Depth Bonus}}$

where:

• $F(s)$ is the frontier priority score for node $s \in \mathcal{F}$
• $Q_{\text{parent}}(s)$ is the average reward of $s$'s parent node (tanh-squashed to $[-1, 1]$)
• $H(\pi_\theta(s \mid o_s))$ is the policy's entropy when generating node $s$ from observation $o_s$
• $D(d(s))$ is the depth bonus function evaluated at the node's depth
• $\lambda_1 = 0.4$ (quality potential coefficient), $\lambda_2 = 0$ in the default configuration (uncertainty bonus disabled), $\lambda_3 = 0.01$ (depth bonus coefficient)

The next expansion target is simply the frontier node with the highest priority score:

$s^* = \arg\max_{s \in \mathcal{F}} F(s)$

What this computes — component by component:

1. Quality potential $\tanh(Q_{\text{parent}}(s))$: encourages expansion of nodes whose parents have high empirical value. The $\tanh$ transformation maps the parent's Q-value (which can be arbitrarily positive or negative) to $[-1, 1]$, preventing nodes with extremely high parent Q-values from dominating selection. The sign of $Q_{\text{parent}}$ is preserved: positive parent values increase priority, negative values decrease it.

2. Uncertainty bonus $H(\pi_\theta(s \mid o_s))$: measures how uncertain the policy was when generating this node. In the default configuration, $\lambda_2 = 0$ (disabled), but when enabled ($\lambda_2 = 0.4$ was tested in Table 3), it steers selection toward high-entropy (uncertain) or low-entropy (confident) regions depending on the sign of $\lambda_2$.

3. Depth bonus $D(d(s)) = \sqrt{d(s) / d_T}$: provides additional priority to deeper nodes, encouraging the search to follow promising paths to completion rather than breadth-first expanding all shallow options. The square-root form provides diminishing returns — the bonus grows quickly for shallow depths and then plateaus, so very deep nodes don't completely dominate. The paper tested alternative forms: $d(s)$ (linear) produced the deepest exploration but sacrificed solution quality, while $\log(d(s) + 1)$ produced minimal improvements (Table 3).

The default configuration uses $\lambda_1 = 0.4$, $\lambda_2 = 0$, $\lambda_3 = 0.01$, and $D(d(s)) = \sqrt{d(s)/d_T}$, which Table 3 shows balances computational efficiency (189.3 iterations per tree), search quality (−0.65 average trajectory reward), and stable performance.

Why global frontier selection over traditional root-to-leaf UCT:

1. Computational efficiency: Traditional MCTS performs a full root-to-leaf traversal for each iteration, visiting each node along the path, computing UCT scores at every level, and descending. For a tree of depth 20, this requires 20 UCT computations per iteration. Global frontier selection computes $F(s)$ once per frontier node and directly picks the maximum — a constant-time operation per iteration regardless of tree depth. Table 3 shows this reduces iterations by 10.4% (209.6 → 187.7) and per-tree time by ~8% (1179.6s → 1087.7s).

2. Mitigating UCT's myopia: UCT is locally greedy — at each level, it picks the best child according to that node's statistics, then descends. This can get trapped in subtrees that look promising locally but are globally suboptimal. Global frontier selection considers all frontier nodes simultaneously, allowing the algorithm to allocate resources across subtrees based on a holistic view. For example, a deep node on a moderately promising path might outrank a shallow node on a slightly more promising path if the depth bonus compensates, preventing premature commitment.

3. Entropy-guided targeting: The uncertainty bonus (when enabled) lets the system steer selection toward regions where the policy is uncertain (high exploration value) or confident (high error-identification value). In the default configuration, $\lambda_2 = 0$, so this mechanism is disabled — the paper found it introduced computational variability ($92.5 \pm 22.5$ iterations, Table 3) without consistent accuracy benefits.

4. No redundant traversals: Traditional UCT requires evaluating nodes that have already been fully expanded (all children generated and evaluated). Global frontier selection only considers unexpanded leaf nodes, eliminating wasted computation on nodes with no remaining exploration value.

Why not fully learn the selection policy (AlphaZero-style)? The paper acknowledges this as future work (Section "Limitations and Future Work") but deliberately chose fixed heuristics for this work. Learning the frontier priority function would require a fundamentally different training paradigm — a controller that jointly optimizes search and policy — which would introduce substantial additional complexity and obscure the core contribution (showing that MCTS during training helps at all). The fixed heuristics were selected through systematic offline experiments (Table 3) and provide stable, reproducible behavior.

---

Adaptive Training Strategy with Replay Buffer

MCTS is expensive. Running full tree search for every training example would be computationally prohibitive. The adaptive training strategy addresses this through three mechanisms that progressively focus MCTS computation on the hardest remaining problems while efficiently reusing previously discovered solutions.

Initial Hard Subset Construction. Given the initial policy $\pi_{\theta^{(0)}}$ (Nemotron-Research-Reasoning-Qwen-1.5B v2, already trained for 3,000 DAPO steps), the system evaluates performance on each problem in the full training set $\mathcal{D}_{\text{train}}$ (DeepMath-103K) using $K = 4$ direct rollouts:

$\mathcal{D}^{(0)}_{\text{hard}} = \{x \in \mathcal{D}_{\text{train}} \mid \text{Pass1@4}(x, \pi_{\theta^{(0)}}) < \delta^{(0)}\}$

where $\text{Pass1@K}(x, \pi)$ is the fraction of $K$ sampled solutions that achieve correct final answers for problem $x$ under policy $\pi$, and $\delta^{(0)} = 25\%$ is the initial filtering threshold.

What this computes: a problem enters the hard set only if the current policy fails to solve it in at least 75% of 4 attempts. Problems the model already solves consistently are excluded — they don't benefit from expensive MCTS exploration because direct rollouts already generate correct solutions reliably. The threshold of 25% (i.e., retain problems with <25% success rate) is the key hyperparameter: it determines the boundary between "mastered" and "challenging."

Why $\delta = 25\%$ and $K = 4$: the threshold is a fixed heuristic chosen for simplicity — the paper explicitly avoids adaptive threshold schedules to keep the design space clean and attribute improvements to MCTS rather than curriculum engineering (Appendix B.4). $K = 4$ balances the cost of evaluation (16 total rollouts per problem to estimate Pass1@4) against reliability (more rollouts would give better estimates but at higher cost). With 4 rollouts, a Pass1@4 of 0 or 1 is fairly reliable (the problem is clearly hard or clearly easy), while values of 2 or 3 are noisier — but the 25% threshold means only problems with 0 or 1 successes out of 4 are retained, reducing noise impact.

Iterative Refinement. After each training phase $i$ (which updates $\pi_\theta$ using Tree-GRPO on MCTS-generated data), the updated policy $\pi_{\theta^{(i)}}$ is re-evaluated on the current hard subset, and problems that now exceed the success threshold are removed:

$\mathcal{D}^{(i+1)}_{\text{hard}} = \{x \in \mathcal{D}^{(i)}_{\text{hard}} \mid \text{Pass1@4}(x, \pi_{\theta^{(i)}}) < \delta^{(i)}\}$

with $\delta^{(i)} = 25\%$ held constant across all iterations.

What this computes: this is curriculum learning by competence filtering. As training improves the policy, problems that were previously challenging become solvable by direct rollouts. These problems are removed from the hard set, meaning they no longer consume MCTS computation. The hard set thus shrinks over time, focusing MCTS resources on an increasingly concentrated set of genuinely difficult problems.

Why decreasing the hard set matters computationally: Table 6 in Appendix B.3 quantifies this effect. Across 5 training rounds with 13,658 initial hard problems:

• Round 1: 0 cached, 13,658 unsolved (0% cache rate, full MCTS on all problems)
• Round 2: 765 cached, 12,893 unsolved (5.6% cache rate)
• Round 3: 1,452 cached, 9,423 unsolved (13.4% cache rate)
• Round 4: 2,243 cached, 7,423 unsolved (23.2% cache rate)
• Round 5: 2,894 cached, 5,829 unsolved (33.2% cache rate)

The monotonic increase in cached solutions means that by Round 5, one-third of the hard set bypasses full MCTS, and the unsolved set has contracted by 57% (from 13,658 to 5,829). This is the mechanism that makes DeepSearch computationally viable: MCTS costs are concentrated on the hardest tail, not diluted across the entire dataset.

Replay Buffer Population. During each training iteration $i$, problems that obtained correct solutions through MCTS exploration but still fail the Pass1@4 threshold are identified:

$\mathcal{R}^{(i)}_{\text{candidates}} = \{(x, \mathbf{t}_{\text{correct}}) \mid x \in \mathcal{D}^{(i)}_{\text{hard}}, \exists \mathbf{t}_{\text{correct}} \in \mathcal{T}(x), \text{Pass1@4}(x, \pi_{\theta^{(i)}}) < \delta^{(i)}\}$

These candidate (problem, solution) pairs are added to the cumulative replay buffer:

$\mathcal{R}^{(i+1)} = \mathcal{R}^{(i)} \cup \mathcal{R}^{(i)}_{\text{candidates}}$

What this computes: when MCTS discovers a correct solution for a problem that the policy still can't solve consistently (Pass1@4 < 25%), that solution is cached. The problem remains in the hard set for continued training (it's not yet mastered), but the verified solution is preserved so that future iterations don't need to re-discover it.

Why cache solutions for problems that aren't yet mastered: this is an anti-catastrophic-forgetting mechanism. If the problem were simply removed from training data because a solution was found once, the policy might gradually forget how to solve it. By caching the solution and continuing to train on it (via the hybrid rollout strategy below), the system ensures that discovered solutions are reinforced while still exploring for alternative (potentially better) solutions.

Hybrid Rollout Strategy. When constructing the training batch for iteration $i$, each problem $x \in \mathcal{D}^{(i)}_{\text{hard}}$ is processed based on cache availability:

$\text{Rollout}(x) = \begin{cases} \mathbf{t}_{\text{cached}} \cup \text{DirectRollouts}(x, \beta) & \text{if } (x, \mathbf{t}_{\text{cached}}) \in \mathcal{R}^{(i)} \\ \text{MCTS}_{\text{full}}(x) & \text{otherwise} \end{cases}$

where $\text{DirectRollouts}(x, \beta)$ samples $\beta \cdot B$ additional solutions from the current policy $\pi_\theta(\cdot \mid x)$, with $B = 8$ being the standard sampling budget and $\beta \in [0, 1]$ implicitly determined by the number of cached solutions (fewer direct rollouts are allocated as more solutions are cached, though the paper doesn't specify the exact formula).

What this computes in operational English:

• For cached problems: the training data includes the stored correct trajectory (guaranteeing positive examples are present) plus a smaller number of fresh direct rollouts (providing continued exploration at minimal cost). These direct rollouts may discover alternative correct solutions or produce new negative examples for training.
• For uncached problems: full MCTS is run, consuming the majority of the computational budget but only on the problems that genuinely need it.

The total training dataset for iteration $i$ is the union over all hard problems:

$\mathcal{T}^{(i)}_{\text{train}} = \bigcup_{x: (x, \mathbf{t}_{\text{cached}}) \in \mathcal{R}^{(i)}} \{\mathbf{t}_{\text{cached}} \cup \text{DirectRollouts}(x, \beta)\} \cup \bigcup_{x: (x, \mathbf{t}_{\text{cached}}) \notin \mathcal{R}^{(i)}} \text{MCTS}_{\text{full}}(x)$

Additionally, the paper filters out "garbled text or infinite repetitions" from incorrect samples before training, citing empirical evidence that such data frequently causes training collapse (Bai et al., 2025).

Why this hybrid strategy over alternatives:

1. Computational efficiency: avoids redundant MCTS on problems with known solutions. A problem that MCTS solved in round 2 doesn't need MCTS again in rounds 3–5; the cached solution plus cheap direct rollouts suffice.

2. Solution preservation: guarantees that every training batch includes verified correct trajectories for cached problems. Without the cache, there's no guarantee that random sampling or even MCTS would rediscover a correct solution; the policy might forget how to solve these problems.

3. Continued exploration at reduced cost: the direct rollouts on cached problems provide a stream of fresh negative examples (and occasional alternative correct solutions) without the overhead of tree search. This prevents the training signal from becoming stale.

4. No artificial sampling ratios: the paper explicitly notes that this approach "eliminates the need for artificial sampling ratios or complex batch composition strategies." The proportion of cached vs. fresh data naturally adapts to problem difficulty and training progress.

Training Protocol Details. The complete training spans 100 steps with model checkpointing every 5 steps. The policy is trained using a global batch size of 256 samples with DAPO-style Dynamic Batching to optimize memory utilization. Training runs on 16×H100 GPUs (96GB each), while evaluation uses a larger 128×H100 cluster to reduce wall-clock time. Responses are limited to 16,384 tokens, and the left side of prompts is truncated to keep the most recent 2,048 tokens.

---

Tree-GRPO Training Objective

The final component connects the MCTS exploration engine's outputs to the policy update. Tree-GRPO is a variant of GRPO (Group Relative Policy Optimization) where token-level advantages are derived from node q-values rather than from outcome-level rewards.

Q-Value Soft Clipping. Before being used as advantages, intermediate node q-values are soft-clipped to prevent explosion:

$q(s_j) = \tanh\left(\frac{q^{(k_{\max})}(s_j)}{\epsilon_q}\right) \cdot q_{\max}$

for all $s_j \in \mathcal{T} \setminus \mathcal{S}_{\text{end}}$, where:

• $k_{\max}$ is the maximum number of rollout iterations for this tree
• $\epsilon_q = 1.0$ is the temperature parameter controlling the sharpness of the clipping
• $q_{\max} = 1$ defines the maximum allowable q-value magnitude

Terminal node q-values remain unchanged as defined in Equation 4 ($+1$ or $-1$).

What this computes: the raw q-value (which can grow without bound as a node accumulates evidence across multiple rollouts) is passed through $\tanh(q / \epsilon_q)$, which smoothly compresses it to $[-1, 1]$, then scaled by $q_{\max} = 1$ (so the output range is exactly $[-1, 1]$). The $\tanh$ function is linear near zero (preserving fine-grained differences for well-behaved q-values) and asymptotically saturates (compressing extreme outliers).

Why soft clipping over hard clipping: hard clipping (e.g., $\text{clip}(q, -1, 1)$) creates a zero-gradient region for all values outside $[-1, 1]$ — the model receives no training signal from nodes with extreme q-values. Soft clipping via $\tanh$ preserves gradients everywhere (even saturated nodes receive a small gradient), preventing the dead-gradient problem. The paper notes that "fewer than about 5% of intermediate node q-values fall into the saturation region and less than 0.5% lie near the boundaries," confirming that clipping mainly compresses pathological tails rather than fundamentally altering the q-value distribution.

Why clip at all: without clipping, a node that appears on many correct trajectories could accumulate a very large positive q-value, dominating the advantage signal and causing unstable gradient updates. The clipping bounds the advantage magnitude, preventing any single node from exerting disproportionate influence on the policy update.

Training Objective. With regularized q-values, the Tree-GRPO objective maximizes:

$\mathcal{J}(\theta) = \mathbb{E}_{\mathcal{T} \sim \mathcal{T}, \mathbf{t}_i \sim \mathcal{T}, (s_j, o_j) \sim \mathbf{t}_i} \left[ \frac{1}{|s_j|} \sum_{k=1}^{|s_j|} \min\left( \rho_{j,k}(\theta) \hat{A}_{j,k}, \text{clip}(\rho_{j,k}(\theta), 1 - \epsilon_{\text{low}}, 1 + \epsilon_{\text{high}}) \hat{A}_{j,k} \right) \right]$

where:

• $\mathcal{T}$ is the distribution over search trees (the training set)
• $\mathbf{t}_i$ is a trajectory sampled from tree $\mathcal{T}$
• $(s_j, o_j)$ is a step in trajectory $\mathbf{t}_i$ with observation $o_j$ (the prefix up to step $s_j$)
• $|s_j|$ is the number of tokens in step $s_j$
• $\rho_{j,k}(\theta) = \frac{\pi_\theta(a_{j,k} \mid o_j, a_{j,<k})}{\pi_{\theta_{\text{old}}}(a_{j,k} \mid o_j, a_{j,<k})}$ is the importance sampling ratio for token $k$ of step $j$ — it measures how much the current policy's probability for this token differs from the old policy's probability (the policy used to generate the training data)
• $\hat{A}_{j,k}$ is the advantage for token $k$ of step $j$
• $\epsilon_{\text{low}} = 0.2$ and $\epsilon_{\text{high}} = 0.28$ are the clipping thresholds (following DAPO's Clip-Higher strategy)
• $\text{clip}(r, a, b) = \max(a, \min(r, b))$ clamps the importance ratio to $[1 - \epsilon_{\text{low}}, 1 + \epsilon_{\text{high}}]$

What this computes in operational English: for each token in each step of each trajectory, we compute a policy gradient update that increases the probability of tokens with positive advantages and decreases the probability of tokens with negative advantages. The $\min(\rho \hat{A}, \text{clip}(\rho) \hat{A})$ is the standard PPO-style clipped objective: it takes the more conservative of the unclipped update ($\rho \hat{A}$) and the clipped update ($\text{clip}(\rho) \hat{A}$), preventing the policy from changing too drastically in a single update. The expectation is over trees, trajectories, and steps.

Why Clip-Higher ($\epsilon_{\text{high}} > \epsilon_{\text{low}}$): DAPO found that allowing larger increases than decreases in token probabilities stabilizes training for reasoning tasks. The intuition: when the model discovers a good reasoning step (positive advantage), we want to increase its probability aggressively ($\epsilon_{\text{high}} = 0.28$ allows the importance ratio to go up to 1.28). When the model makes a mistake (negative advantage), we want to decrease probability more conservatively ($\epsilon_{\text{low}} = 0.2$ limits the ratio to 0.8) to avoid destabilizing the model's overall distribution.

Advantage Computation. The critical difference from standard GRPO is how advantages $\hat{A}_{j,k}$ are computed. In Tree-GRPO, all tokens within the same step $s_j$ share the same advantage, derived from that step's node q-value:

$\hat{A}_{j,k} = q(s_j) - \mu_t$

where $\mu_t$ is the average reward of the terminal nodes throughout the entire tree $\mathcal{T}$:

$\mu_t = \frac{1}{|\mathcal{S}_{\text{end}}|} \sum_{s_{\text{end}} \in \mathcal{S}_{\text{end}}} q(s_{\text{end}})$

What this computes:

1. Per-step q-value: $q(s_j)$ is the node's q-value after soft clipping (Equation 13). For nodes on paths that lead to correct solutions, this is positive (typically in $[0, 1]$). For nodes on paths that consistently lead to failures, this is negative (typically in $[-1, 0]$). For intermediate nodes that haven't been conclusively evaluated, this is near zero.

2. Tree-level baseline: $\mu_t$ is the mean terminal reward across the entire tree. If the tree contains many correct solutions, $\mu_t$ will be close to $+1$; if most branches fail, $\mu_t$ will be close to $-1$.

3. Centered advantage: subtracting $\mu_t$ centers the advantages around zero. A node with $q(s_j) = 0.5$ on a tree where $\mu_t = -0.3$ gets a positive advantage $\hat{A}_{j,k} = 0.8$ — it's better than the tree average. The same node on a tree where $\mu_t = 0.8$ gets a negative advantage $\hat{A}_{j,k} = -0.3$ — it's worse than the tree average, even though its q-value is positive.

Why mean-only normalization (subtracting $\mu_t$) rather than standard deviation normalization (subtracting $\mu_t$ and dividing by $\sigma_t$): Table 4 shows that mean-only normalization (62.32% average) slightly outperforms standard normalization (62.27% average), though both beat unnormalized advantages (61.85%). The paper cites Bereket & Leskovec (2025) on miscalibration issues in GRPO and argues that standard deviation normalization introduces variance-based scaling that can destabilize training when $\sigma_t$ is small (all terminal nodes have similar rewards). Mean-centering alone is sufficient to provide a relative baseline while being more stable — the magnitude of the advantage is determined by the raw q-value difference, not amplified by an inverse-variance factor.

Why this form over outcome-only advantages ($\hat{A}_{j,k} = q(s_{\text{end}}) - \mu_t$ for all nodes): Table 4 quantifies the benefit. Coarse-grained token scores (all tokens in a trajectory share the terminal reward) achieve 61.38% average. Fine-grained token scores (each step gets its own node q-value) achieve 61.85% — a 0.47 percentage point gain. The improvement, while modest in isolation, compounds with other components (advantage normalization, frontier selection) to produce the final 62.95% result. The mechanism is intuitive: a trajectory that starts with a flawed assumption but coincidentally arrives at the correct answer would receive positive outcome rewards for all tokens, including the flawed assumption. With node-level q-values, the flawed prefix would have a low q-value (because MCTS explored other branches from that prefix that failed), while the later steps that rescued the solution would have positive q-values. This differentiated signal teaches the model to avoid the flawed prefix while preserving the rescuing reasoning.

Additional Design Choices in Tree-GRPO:

1. No KL regularization: the KL divergence penalty term standard in PPO is removed ($D_{\text{KL}} = 0$). This follows the finding in Luo et al. (2025a) and He et al. (2025a) that removing KL regularization allows the policy to diverge more naturally from the base distribution during reasoning training.

2. Overlong buffer penalty: responses exceeding 4,096 tokens receive a penalty factor of 1.0 (the paper does not specify the exact penalty mechanism, but it likely involves truncating the advantage or the loss contribution). This discourages the model from learning to produce excessively long reasoning chains that waste computation without improving accuracy.

3. Token-mean loss aggregation: the per-token losses within each step are averaged (the $\frac{1}{|s_j|}$ factor in Equation 14), ensuring that steps of different lengths contribute equally to the gradient rather than longer steps dominating.

4. Dynamic batch sizing: up to 18,432 tokens per GPU, adapting batch composition to fit within memory constraints.

5. Optimizer settings: AdamW with learning rate $1 \times 10^{-6}$, 10 warmup steps, weight decay 0.1, gradient clipping at 1.0, mini-batches of 32 samples per policy update, entropy coefficient 0 (pure exploitation, no entropy bonus in the loss).

Relationship to DAPO and standard GRPO: Tree-GRPO degenerates to vanilla DAPO if $q(s_j)$ is replaced by $q(s_{\text{end}})$ for all intermediate nodes — i.e., if all tokens in a trajectory receive the same terminal reward as their advantage. DeepSearch's implementation uses DAPO's Clip-Higher strategy and dynamic batching, so the only structural difference is the advantage computation. This means any performance improvement over the Nemotron v2 baseline (which used DAPO) must be attributed to the MCTS-derived q-values and the exploration they represent, not to optimizer tweaks.

---

Summary of Design Choices and Their Justifications

• Global frontier selection over root-to-leaf UCT: eliminates redundant traversals (10.4% fewer iterations), mitigates UCT's myopia (considers all frontier nodes simultaneously), and enables depth-guided exploration via the depth bonus (Table 3).
• Square-root depth bonus $\sqrt{d(s)/d_T}$ over linear or logarithmic alternatives: linear bonus ($d(s)$) produced deepest exploration but lowest solution quality (−0.76 reward vs. −0.65); logarithmic bonus ($\log(d(s) + 1)$) provided minimal improvement; square root balanced depth, quality, and efficiency (Table 3).
• Most-confident incorrect trajectory selection over random or least-confident: targets systematic errors where the model is confidently wrong, providing the most informative negative supervision. Empirically validated in Table 5 (+0.86% over random, +1.05% over least-confident).
• Asymmetric q-value backup (Equation 5) over uniform additive updates: prevents a single correct appearance from being drowned out by many incorrect appearances, establishing clean invariants (positive for ever-correct nodes, negative for never-correct nodes) that stabilize the advantage signal.
• Soft clipping ($\tanh(q / \epsilon_q)$) over hard clipping: preserves gradients everywhere, preventing dead-gradient problems when q-values saturate. Only ~5% of q-values are affected, so clipping mainly handles pathological tails.
• Mean-only advantage normalization ($q(s_j) - \mu_t$) over standard-normalization ($q(s_j) - \mu_t / \sigma_t$): avoids variance-based instability while providing a sufficient relative baseline. Empirically slightly superior (Table 4).
• Node-level advantages ($q(s_j)$) over outcome-level advantages ($q(s_{\text{end}})$) for all tokens in a trajectory: enables fine-grained credit assignment where different reasoning steps receive different signals based on their contribution to success or failure (Table 4, 61.38% → 61.85%).
• Progressive filtering with $\delta = 25\%$ over uniform training: focuses MCTS computation on truly challenging problems (the hard set contracts by 57% over 5 rounds, Table 6), making training-time tree search computationally viable.
• Replay buffer with cached solutions over naive MCTS everywhere: guarantees positive examples are present in every batch for previously solved problems, prevents catastrophic forgetting, and dramatically reduces MCTS overhead as training progresses (33.2% cache rate by round 5).
• No KL regularization ($D_{\text{KL}} = 0$): allows the policy to diverge more freely from the base distribution, following empirical findings that KL penalties can hinder reasoning training (Luo et al., 2025a; He et al., 2025a).
• $n = 8$ children per expansion, 256 tokens per step, $d_T = 64$ maximum depth: these hyperparameters balance search breadth (more children = broader exploration but higher cost), step granularity (256 tokens is derived from the reasoning-length distribution in DeepMath-103K, Appendix B.1), and tree depth (limits total computation while covering full reasoning chains for nearly all problems).

4. Key Insights and Innovations

Innovation 1: The Exploration Bottleneck Is THE Bottleneck, Not Just One of Many

The paper's most fundamental conceptual contribution is establishing that the performance plateaus observed in RLVR training are not merely a matter of insufficient optimization steps or imperfect reward design — they are fundamentally an exploration pathology. This is a diagnostic insight, not a new algorithm. Prior work (ProRL, DAPO, Nemotron series) implicitly treated RLVR scaling as a depth problem: more training steps → more optimization → better performance, with the open question being how many steps are needed and what tricks stabilize long-horizon training. The implicit assumption was that direct policy rollouts, given enough steps, would eventually cover the solution space adequately.

DeepSearch challenges this assumption by demonstrating that the exploration quality ceiling is reached long before the optimization ceiling. The evidence in Table 2 is designed to make this point unambiguous: after 3,000 DAPO steps, the Nemotron v2 model achieves 61.70% accuracy. Adding 1,875 more steps (a 62.5% increase in training) yields 62.02% — a net regression from the intermediate 62.08% checkpoint at +785 steps. This is not slow improvement; it's a hard ceiling. The interpretation — and this is the paper's core diagnostic — is that direct policy rollouts have exhausted their exploration capacity. The model is sampling from a distribution that has collapsed to a local mode, and gradient updates on samples from that mode cannot escape it.

This reframes the RLVR problem in a way that makes the search-based solution (MCTS) not merely a nice-to-have improvement but a structural necessity for continued scaling. The prior framing was "RLVR works, we just need to run it longer and tune it carefully." The new framing is "RLVR works until exploration saturates, after which it's dead in the water regardless of compute investment — and exploration saturates surprisingly quickly." This diagnostic has implications beyond this paper: it suggests that any RLVR method that relies solely on policy rollouts for exploration has a hard ceiling determined by the policy's mode-collapse rate, not by the total number of optimization steps.

The significance of this reframing extends to how the community should allocate research effort. If the problem were optimization stability or reward sparsity, the solution would involve better optimizers, better reward shaping, or better regularization — all within the existing rollout-based paradigm. If the problem is exploration, as DeepSearch argues, then the solution must involve a qualitatively different data generation mechanism that exposes the policy to trajectories it would never sample on its own. MCTS is one such mechanism; the paper implicitly argues that any mechanism achieving the same effect (structured exploration beyond the policy's mode) would address the same bottleneck. The paper is thus less a proposal for "use MCTS" and more a proposal for "the exploration side of RLVR is the binding constraint, and here's one way to fix it."

The concrete empirical anchor is Table 2 and Figure 2: the extended training baselines show a flat-to-declining accuracy curve after thousands of steps, while DeepSearch's curve (in Figure 2) continues to rise with a steeper slope, using 5.7× fewer GPU hours. The curves diverge not because DeepSearch optimizes better, but because it explores better — each training step contains more novel, informative reasoning trajectories.

---

Innovation 2: Training-Time Search and Inference-Time Search Are Complements, Not Substitutes — and the Training Side Has Been Neglected

The field has converged on a clean division of labor: structured search (tree search, beam search, best-of-N with verifiers) is applied at inference time to extract better answers from a frozen model, while training uses simple direct rollouts with outcome rewards. This division is so entrenched that the terms "test-time compute scaling" and "inference-time search" are essentially synonymous with structured exploration in the LLM reasoning literature (Snell et al., 2024; Wu et al., 2024; Zhang et al., 2024c). The underlying assumption is that the model should learn to reason from data, and search should help it deploy that reasoning — but the model doesn't need to learn from search.

DeepSearch's key conceptual move is to break this division. It shows that search is not just a deployment tool; it is a training data generation tool, and that using search during training produces a model that is better at reasoning even without inference-time search. This is not obvious. One might reasonably expect that if inference-time search already provides the exploration benefits, there's no marginal value to embedding it in training — the model can just rely on search at test time. The paper's results argue otherwise: DeepSearch-1.5B achieves 62.95% average accuracy with standard sampling at evaluation (temperature 0.6, top-p 0.95 — not tree search), outperforming all baselines including those that could themselves be combined with inference-time search. This means the training-time exploration has produced a model whose base policy is qualitatively better, not just a model that happens to be measured under favorable conditions.

This insight has a crucial practical implication: training-time search and inference-time search are complements with compounding benefits, not substitutes. A model trained with MCTS exploration learns more robust reasoning strategies, which means its base rollouts are higher quality, which means inference-time search has better raw material to work with. The paper doesn't explore this compounding (DeepSearch is evaluated without inference-time search in Table 1), but the implication is clear — and it's explicitly left as future work ("we did not experiment with PRM tree-search techniques in combination with revisions").

The prior approach — restricting search to inference — is thus revealed as a missed opportunity. Every inference-time search algorithm is, implicitly, an exploration mechanism that could generate training data. The fact that the field treated them as separate is not a technical necessity but a conceptual blind spot: search was categorized as "deployment optimization," not "training data augmentation." DeepSearch changes that categorization.

The evidence for this innovation is structural rather than localized to a single table. The entire DeepSearch framework embodies the principle: MCTS generates training trajectories (Section 3), the Tree-GRPO objective learns from them (Section 4.3), and the resulting model is evaluated under standard (non-search) decoding in Table 1. The 62.95% result — a new state-of-the-art for 1.5B models — was achieved without inference-time search, demonstrating that training-time exploration transfers to improved base policy quality.

---

Innovation 3: Asymmetric Credit Assignment via Tree-Structured Backpropagation Enables Learning from Systematic Mistakes, Not Just Successes

Outcome-based RLVR treats every token in a solution identically: if the final answer is correct, all tokens get positive reinforcement; if wrong, all get penalized. This is a coarse signal that cannot distinguish between a brilliant insight and a lucky guess, or between a fundamental conceptual error and a trivial arithmetic slip in an otherwise sound solution. The field has recognized this limitation — process reward models (Lightman et al., 2023; Wang et al., 2023) were developed precisely to provide step-level evaluation — but PRMs have been used almost exclusively at inference time, not for training.

DeepSearch introduces a fundamentally different mechanism for credit assignment that emerges naturally from the tree structure, without requiring a separately trained process reward model. When MCTS explores multiple continuations from the same intermediate node, the node's q-value reflects the empirical success rate of all branches originating from it. A node from which 7/8 branches reach correct answers gets a high positive q-value; a node from which 0/8 branches succeed gets a negative q-value. This is not a learned estimate from a reward model — it's a direct empirical measurement of the node's quality under the current policy and search process.

The conceptual innovation is that tree-structured exploration automatically generates counterfactual data for credit assignment. Standard RLVR can only observe one continuation per prefix (the one that was actually sampled), which makes credit assignment fundamentally underdetermined: if a solution fails, you don't know which step(s) caused the failure. The tree structure resolves this by forcing exploration of multiple continuations, creating the counterfactuals that make credit assignment possible. The q-value for a node summarizes the answer to: "When the model starts from this reasoning state, how often does it ultimately succeed?"

This is a conceptual advance over PRMs because it doesn't require training a separate verifier model. PRMs require either human annotations (expensive) or Monte Carlo rollouts with an outcome verifier for supervision (computationally heavy and dependent on a frozen base policy). DeepSearch's q-values are a byproduct of the exploration process itself — they're computed as part of MCTS backpropagation, not trained separately. This collapses the exploration and evaluation functions into a single process.

The asymmetric backup rule (Equation 5) is the concrete mechanism that makes this work, but the idea is more general: once a node has been observed on any correct path, treat it as capable of contributing to success, regardless of how many failed paths also pass through it. This encodes an inductive bias that is specific to reasoning: a valid reasoning step is valid regardless of how frequently it appears alongside mistakes. A correct algebraic manipulation doesn't become incorrect just because it's often followed by arithmetic errors. The backup rule's invariants — positive q-values for ever-correct nodes, negative q-values only for never-correct nodes — formalize this intuition.

The significance extends beyond this paper. This mechanism suggests that any exploration strategy that generates structured trees (not just MCTS) can produce fine-grained credit assignment for free, as long as it explores multiple continuations from shared prefixes. This opens the design space for other exploration strategies (beam search with shared prefixes, multi-armed bandit approaches, even simple ensemble methods) that might achieve similar benefits without full MCTS.

The empirical anchor is Table 4, which shows that moving from outcome-based advantages ("Coarse-grained Token Scores," 61.38%) to node-level advantages ("Fine-grained Token Scores," 61.85%) provides a measurable improvement, and that this improvement compounds with advantage normalization and frontier selection to reach the final 62.95% result. The gain from fine-grained credit assignment is modest in isolation (+0.47 points) but enables the other components to work better by providing a cleaner training signal.

---

Innovation 4: Difficulty-Aware Adaptive Training Makes Training-Time Tree Search Computationally Viable

The most obvious objection to embedding MCTS in RLVR training is computational cost. Running full tree search for every problem in every training iteration would be mathematically elegant but practically impossible — the paper acknowledges this directly in Section 4.1. The conceptual challenge, then, is not whether tree search helps (that's almost definitionally true if you could afford it), but whether it can be made selective enough to be practical while still providing enough exploration to matter.

DeepSearch's solution — progressive filtering with cached solutions — represents a specific design philosophy: don't spend expensive exploration on problems that don't need it, and don't re-explore paths you've already discovered. This sounds obvious in retrospect, but it's a genuine innovation because it changes the cost structure of training-time search from $O(N \cdot C)$ (where $N$ is dataset size and $C$ is MCTS cost per problem) to $O(N_{\text{hard}} \cdot C + N_{\text{cached}} \cdot c)$ (where $N_{\text{hard}}$ shrinks over time, $N_{\text{cached}}$ grows, and $c \ll C$ is the cost of direct rollouts).

The adaptive filtering mechanism (Section 4.1) is a curriculum-learning strategy where the curriculum is defined by the model's own competence — problems graduate out of the hard set when the model can solve them consistently. This is not a fixed schedule but an emergent curriculum that adapts to the model's improving capabilities. The replay buffer (Section 4.2) is an anti-catastrophic-forgetting mechanism that ensures the model continues to practice previously solved problems without paying the full MCTS cost.

The conceptual insight is that computational efficiency in training-time search is not about making search cheaper per problem, but about being strategic about which problems get search. The paper demonstrates that even simple heuristics (25% threshold, deterministic cache reuse) can reduce the unsolved problem set by 57% over 5 training rounds (Table 6, from 13,658 to 5,829), concentrating MCTS computation on an increasingly pure tail of genuinely hard problems. This is the mechanism that makes the 5.7× efficiency gain in Table 2 possible — the 330 GPU hours are not spread uniformly over all problems but focused on the subset where MCTS actually provides novel exploration value.

This design philosophy contrasts with approaches that attempt to make search efficient through technical optimizations (faster inference, better caching, speculative decoding — which the paper shows account for <1% of per-tree cost in Table 7) while applying search uniformly. DeepSearch argues that selective application is a more powerful lever than per-unit optimization. The profiling in Table 7 (Appendix C) shows that 99%+ of MCTS time is model inference; algorithmic optimizations to the search logic itself provide negligible savings. The only way to substantially reduce total cost is to run MCTS on fewer problems — hence the filtering strategy.

The significance is that this approach generalizes beyond MCTS. Any expensive exploration mechanism — process reward model scoring, multi-agent debate, tool-augmented reasoning — could benefit from a similar adaptive filtering strategy that reserves the expensive method for problems where the cheap method (direct rollouts) fails. The paper establishes a template: (1) evaluate current policy competence on each problem, (2) filter to retain only challenging cases, (3) cache discovered solutions to prevent re-exploration, (4) progressively tighten the filter as the policy improves. The specific threshold (25%) and evaluation protocol (Pass1@4) are engineering choices; the pattern is the conceptual contribution.

The empirical evidence is the combination of Table 2 (5.7× efficiency gain), Table 6 (57% reduction in unsolved problems), and Figure 2 (superior convergence slope despite using fewer GPU hours). Without adaptive filtering, the MCTS cost would scale with the full dataset size, and the efficiency advantage over extended training would disappear. The fact that DeepSearch achieves better results with dramatically less compute is not just an algorithmic benefit of MCTS — it's a direct consequence of the adaptive strategy that makes MCTS affordable in the first place.

5. Experimental Analysis

Evaluation Methodology

• Dataset. All training uses DeepMath-103K (He et al., 2025c), described as "a large-scale mathematical dataset designed to be highly challenging and rigorously decontaminated across numerous benchmarks." Evaluation is conducted on six mathematical reasoning benchmarks: AIME 2024, AIME 2025, AMC2023, MATH500 (Hendrycks et al., 2021), Minerva (Lewkowycz et al., 2022), and Olympiad (He et al., 2024). The MATH500 split is the standard 500-question test set from Hendrycks et al. (2021). The paper does not report the exact sizes of the AIME, AMC, Minerva, and Olympiad evaluation sets, but these are established benchmarks with known sizes (AIME: 30 questions per year; AMC: typically 25 questions; Minerva: 272 questions; Olympiad: a multi-subject benchmark with hundreds of questions).

• Base model(s). DeepSearch-1.5B is initialized from Nemotron-Research-Reasoning-Qwen-1.5B v2 (Liu et al., 2025a), a 1.5-billion-parameter model that had already undergone 3,000 steps of DAPO-style RLVR training starting from DeepSeek-R1-Distill-Qwen-1.5B. The paper also reports extended training baselines (DAPO and DAPO + KL) initialized from the same Nemotron v2 checkpoint. The choice of 1.5B scale is positioned as representative of the "small reasoning model" regime where training efficiency matters most, and where the RLVR plateau phenomenon is most clearly observable.

• Metrics. The primary metric throughout is Pass@1 accuracy (the fraction of problems for which a single sampled solution produces the correct final answer), estimated using $n = 32$ samples per problem. For benchmark evaluation, a low temperature of 0.6 and top-p of 0.95 are used (Appendix A.4). Answers are extracted from the last occurrence of \boxed{} in the model's output and compared to ground truth after text normalization following veRL's DAPO recipe. The "Avg" column in Tables 1 and 4 is the unweighted mean across the six benchmarks. For the adaptive filtering strategy, a separate metric Pass1@K with $K = 4$ samples is used to estimate per-problem success rates for hard-set construction.

• Baselines. Table 1 compares against an extensive set of 1.5B-scale models: Qwen2.5-Math-1.5B and its Instruct variant (Yang et al., 2024); DeepSeek-R1-Distill-Qwen-1.5B (DeepSeek-AI, 2025); STILL-3-1.5B (Team, 2025); Qwen2.5-Math-1.5B-Oat-Zero (Liu et al., 2025b); the Open-RS series (Open-RS1, Open-RS2, Open-RS3; Dang & Ngo, 2025); DeepScaleR-1.5B (Luo et al., 2025b); and two Nemotron-Research-Reasoning-Qwen-1.5B checkpoints (v1 at 2,000 DAPO steps, v2 at 3,000 DAPO steps; Liu et al., 2025a). Table 2 adds three extended training baselines: DAPO for +325 steps, DAPO + KL for +785 steps, and DAPO + KL for +1,875 steps, all initialized from DeepSeek-R1-Distill-Qwen-1.5B. These span base models, RL-trained models, and search-augmented inference methods.

• Generation budget / compute accounting. The paper uses GPU hours as the universal compute metric for efficiency comparisons (Table 2). All training runs use the same hardware (16×H100 GPUs at 96GB each for training, 128×H100 for evaluation), so GPU-hour comparisons are directly comparable. For MCTS, computation is further profiled in Table 7 (Appendix C), which breaks down per-tree runtime into components. The paper explicitly accounts for the cost of MCTS exploration versus direct rollouts: cached problems require only cheap direct rollouts ($\beta \cdot B$ samples), while uncached problems incur full MCTS cost. The progressive filtering mechanism (Table 6) shows how the fraction of problems requiring full MCTS decreases over training rounds.

• Cross-validation / statistical protocol. Results in Table 1 are reported as Pass@1 accuracy estimated with $n = 32$ samples, following the methodology of Hochlehnert et al. (2025) for consistency. The paper does not report confidence intervals or standard deviations for the main benchmark results. For the search strategy ablation (Table 3), results are presented as "mean ± standard deviation" over 1,200 sampled problems. The adaptive training protocol involves 100 total training steps with model checkpointing every 5 steps (Appendix A.5); the paper reports results from the final checkpoint but does not specify whether results are averaged across multiple seeds. No explicit cross-validation protocol is described for hyperparameter selection — the $\lambda$ coefficients and depth bonus functions appear to be selected through the systematic sweep reported in Table 3 and then fixed for all subsequent experiments. This is a potential limitation: without multiple training runs with different random seeds, it is unclear whether the reported 62.95% result is reliably achievable or represents a favorable seed.

Main Quantitative Results

Benchmark Performance (Table 1)

DeepSearch-1.5B achieves 62.95% average accuracy across six mathematical reasoning benchmarks, establishing a new state-of-the-art for 1.5B-parameter reasoning models. The closest baseline, Nemotron-Research-Reasoning-Qwen-1.5B v2, achieves 61.70% — a 1.25 percentage point gap.

The per-benchmark breakdown reveals consistent improvement rather than dominance on any single benchmark: AIME 2024 (53.65% vs. 51.77%, +1.88 points), AIME 2025 (35.42% vs. 32.92%, +2.50 points), AMC2023 (90.39% vs. 88.83%, +1.56 points), MATH500 (92.53% vs. 92.24%, +0.29 points), Minerva (40.00% vs. 39.75%, +0.25 points), Olympiad (65.72% vs. 64.69%, +1.03 points). The gains are concentrated on the hardest benchmarks (AIME 2024/2025, Olympiad) with smaller improvements on MATH500 and Minerva, where the baseline is already near ceiling for the 1.5B scale. This pattern is consistent with the claim that MCTS-based exploration helps most on challenging problems — exactly the regime where direct rollouts are least likely to discover correct solutions, and where systematic tree search provides the greatest exploration benefit.

The comparison against the broader baseline field shows that DeepSearch's 62.95% substantially exceeds DeepScaleR-1.5B (55.64%, a 7.31 point gap), STILL-3-1.5B (50.73%, a 12.22 point gap), and the DeepSeek-R1-Distill baseline (49.46%, a 13.49 point gap). However, it is important to note that DeepSearch inherits the Nemotron v2 initialization, which already incorporated 3,000 DAPO steps and provides 61.70% as a starting point. The marginal improvement from DeepSearch's 50 additional Tree-GRPO steps is +1.25 points over this already-strong baseline — a meaningful but not dramatic gain. The paper's framing emphasizes the state-of-the-art result (62.95%), but the more informative comparison is against the Nemotron v2 base: DeepSearch adds 50 MCTS-augmented training steps to achieve what brute-force scaling could not achieve with 1,875 additional DAPO steps (which only reached 62.02% and then regressed).

Training Efficiency (Table 2, Figure 2)

The central efficiency result: DeepSearch achieves 62.95% average accuracy using 330 GPU hours (50 Tree-GRPO training steps), compared to 1,883.2 GPU hours for extended DAPO + KL training (1,875 additional steps) that achieves only 62.02% — a 5.7× reduction in compute for superior accuracy.

Table 2 traces the full efficiency landscape:

• DeepSeek-R1-Distill-Qwen-1.5B baseline: 49.46% (pretraining + distillation)
• Nemotron v1 (2,000 DAPO steps): 60.10% (16,000 GPU hours)
• Nemotron v2 (3,000 DAPO steps): 61.70% (24,000 GPU hours)
• Extended DAPO (+325 steps beyond v2): 61.78% (326.4 GPU hours) — +0.08 points for substantial compute
• Extended DAPO + KL (+785 steps): 62.08% (788.8 GPU hours) — +0.30 additional points
• Extended DAPO + KL (+1,875 steps): 62.02% (1,883.2 GPU hours) — regression from the +785 checkpoint
• DeepSearch (+50 Tree-GRPO steps): 62.95% (330 GPU hours)

The diminishing returns pattern is unambiguous. The first 2,000–3,000 DAPO steps provide ~10–12 points of improvement. The next ~500 steps provide ~0.4 points. The next ~1,400 steps provide negative returns (regression). DeepSearch's 50 steps reverse this trend, achieving +1.25 points over the v2 baseline with 72× less compute than the v1→v2 progression (24,000 GPU hours for v2 training, compared to the 330 hours for DeepSearch on top of v2). The paper frames this as a 72× efficiency improvement over Nemotron v2 training, though this comparison conflates the cost of training a model from scratch (v2) with the cost of fine-tuning an already-strong model (DeepSearch). A fairer comparison is DeepSearch's 330 hours vs. the extended training's 1,883.2 hours — a 5.7× improvement — which better isolates the efficiency of MCTS-augmented training versus continued DAPO training from the same initialization.

Figure 2 plots training dynamics over 20 hours following the 3,000-step RLVR training. The DAPO curve shows gradual linear improvement with a shallow slope (approximately 0.5–1.0 points over 20 hours). The DeepSearch curve shows a steeper slope and reaches a higher final accuracy, though the figure's resolution makes precise quantification difficult. The dotted linear trend lines show that DeepSearch's per-hour improvement rate is substantially higher than DAPO's, consistent with the claim that structured exploration extracts more value per unit of computation.

Critically, the GPU hour accounting in Table 2 does not include the cost of the initial 3,000 DAPO steps used to train the Nemotron v2 base model. DeepSearch-1.5B is initialized from v2, so the total cost to produce the model is 24,000 (Nemotron v2 training) + 330 (DeepSearch) = 24,330 GPU hours. The extended training baselines are initialized from DeepSeek-R1-Distill, not from Nemotron v2, so their costs are: 0 (distillation) + extended training hours. The paper's comparison therefore juxtaposes different base models with different total training budgets. A fully fair accounting would compare (1) DeepSeek-R1-Distill + extended DAPO training against (2) DeepSeek-R1-Distill + Nemotron DAPO training + DeepSearch Tree-GRPO training. The paper does not report this total-cost comparison explicitly.

Adaptive Training Dynamics (Table 6)

The caching mechanism reduces the unsolved problem count from 13,658 (Round 1) to 5,829 (Round 5) — a 57.3% reduction — while the cached proportion grows from 0% to 33.2%. The monotonic increase in cached solutions demonstrates that DeepSearch progressively transfers problems from the unsolved pool into the replay buffer as MCTS uncovers verifiable solution paths.

The detailed round-by-round breakdown: Round 1 starts with 0 cached and 13,658 unsolved (0% cache rate, full MCTS on all problems). Round 2 has 765 cached and 12,893 unsolved (5.6% cache rate). Round 3: 1,452 cached, 9,423 unsolved (13.4%). Round 4: 2,243 cached, 7,423 unsolved (23.2%). Round 5: 2,894 cached, 5,829 unsolved (33.2%). The largest absolute reduction occurs between Rounds 2 and 3 (12,893 → 9,423, a decrease of 3,470 problems), suggesting that the policy improvement between these rounds is particularly significant — many problems cross the 25% success threshold and are removed from the hard set.

This shrinking hard set directly validates the adaptive training design: computation is increasingly concentrated on truly challenging problems. By Round 5, only 5,829 problems require full MCTS, while 2,894 problems use the much cheaper cached-solution path. Without this filtering, all 13,658 problems would require MCTS in every round, multiplying the total cost by roughly 2.3× for the later rounds. The adaptive strategy thus provides a >2× efficiency gain on top of whatever benefits MCTS itself provides.

Search Strategy Ablation (Table 3)

Table 3 compares global frontier selection against vanilla UCT on 1,200 samples from "extremely hard" DeepMath-103K problems, with results reported as mean ± standard deviation.

Global vs. local selection. Under the basic configuration (λ₁ = 0.4, no depth or uncertainty bonuses), global frontier selection reduces the number of iterations by 10.4% (209.6 ± 14.8 → 187.7 ± 16.2), reduces per-tree time by 7.8% (1179.6s → 1087.7s), and improves trajectory reward (−0.82 ± 0.57 → −0.65 ± 0.76), while maintaining similar search depth (20.11 vs. 20.28) and entropy (1.23 for both). This is the core evidence that global selection is more efficient: it achieves better solutions with fewer iterations and less total time.

Depth bonus impact. Three depth bonus functions are tested: $\log(d(s) + 1)$, $d(s)$ (linear), and $\sqrt{d(s)/d_T}$ (square root), all with λ₁ = 0.4, λ₃ = 0.01. The logarithmic bonus provides minimal improvements over no depth bonus — essentially unchanged metrics. The linear bonus produces the most aggressive efficiency gains: a 59.2% reduction in per-tree time (1179.6s → 480.9s) and deepest average exploration (21.55 depth), but at the cost of solution quality — trajectory reward drops to −0.76, the worst among all configurations. The square-root bonus offers the best balance: it maintains search quality (−0.65 reward, matching the no-depth-bonus configuration) while providing computational savings and the second-deepest exploration (20.83 depth). The paper selects $\sqrt{d(s)/d_T}$ as the default based on this balanced profile.

Uncertainty bonus. Adding λ₂ = 0.4 (uncertainty weighting) to the square-root depth configuration increases exploration diversity (entropy 1.23 → 1.31) but introduces computational variability (92.5 ± 22.5 iterations, compared to 189.3 ± 14.7 without uncertainty). The trajectory reward drops to −0.79, suggesting that prioritizing high-uncertainty regions does not translate to better solution quality in this setting. The paper disables the uncertainty bonus (λ₂ = 0) in the default configuration.

Configuration selection rationale. The default configuration (λ₁ = 0.4, λ₂ = 0, λ₃ = 0.01, $D(d(s)) = \sqrt{d(s)/d_T}$) is chosen for its balance of computational efficiency (189.3 iterations), search quality (−0.65 reward), and stable performance (low standard deviation on iterations). The paper does not report accuracy on downstream benchmarks for each configuration — the selection is based on search metrics (depth, entropy, reward, cost) rather than end-to-end model quality. This is a limitation: it is possible that a configuration with slightly worse search metrics (e.g., the linear depth bonus with its deeper exploration) could produce better training data and higher final accuracy, despite its lower per-trajectory reward during search.

Algorithm Evolution and Component Contributions (Table 4)

Table 4 traces the step-by-step evolution from the Nemotron v2 baseline to the full DeepSearch system, with each row adding one component:

1. Nemotron v2 baseline: 61.70% average accuracy.

2. + Vanilla DeepSearch (basic MCTS integration with simple q-value updates): 60.27% — a degradation of −1.43 points. This negative result is significant: naive MCTS integration actually harms performance, likely because the simple q-update rule fails to provide useful credit assignment. The paper does not elaborate on this degradation, but it serves as important evidence that the specific design choices in DeepSearch (constrained backup, entropy-based selection, etc.) are necessary, not optional.

3. + New q Update & Coarse-grained Token Scores (constrained backup rule from Equation 5, but with outcome-based advantages $\hat{A}_{j,k} = q(s_{\text{end}})$ for all tokens): 61.38% — a +1.11 point recovery over vanilla, but still −0.32 points below the baseline.

4. + New q Update & Fine-grained Token Scores (node-level advantages $\hat{A}_{j,k} = q(s_j)$): 61.85% — +0.47 points over coarse-grained, now +0.15 points above the baseline. This is the threshold where DeepSearch begins to outperform its initialization.

5. + Standard Advantages Normalization (normalize by mean and standard deviation: $\hat{A}_{j,k} = (q(s_j) - \mu_t) / (\sigma_t + \varepsilon)$): 62.27% — +0.42 points over unnormalized.

6. + Mean-only Advantages Normalization (remove standard deviation scaling, keep mean centering): 62.32% — +0.05 points over standard normalization. The paper attributes this to avoiding variance-based miscalibration (citing Bereket & Leskovec, 2025).

7. + Frontier Selection (global frontier selection strategy replacing traditional UCT traversals): 62.95% — +0.63 points, the single largest component-level improvement.

The cumulative improvement from the baseline to full DeepSearch is +1.25 points (61.70% → 62.95%). The frontier selection component provides the largest individual gain (+0.63 points), followed by the transition from coarse to fine-grained token scores (+0.47 points), and then advantage normalization (+0.42 points). Notably, the initial vanilla MCTS integration (−1.43 points) and the new q-update with coarse-grained scores (−0.32 points relative to baseline) are both harmful compared to the baseline. This means that the positive contributions of the later components must first overcome the negative effects of the earlier components. The paper does not present an ablation that adds components in a different order to determine whether the negative effects compound or whether they are independent.

A limitation of this analysis: the progressive addition means each component's marginal contribution is evaluated in the context of all previously added components. The +0.63 points attributed to frontier selection might be different if it were added directly to the baseline (without the other components). Interaction effects cannot be disentangled from this linear trace.

Entropy-Based Trajectory Selection (Table 5)

Table 5 compares three strategies for selecting which incorrect trajectory to use for training when no correct solution is found in the current MCTS expansion, starting from the Nemotron v2 baseline (61.70%):

• Random incorrect trajectory: 62.09% average (+0.39 points over baseline)
• Least confident incorrect trajectory (highest entropy): 61.90% (+0.20 points) — underperforms random selection
• Most confident incorrect trajectory (lowest entropy, the DeepSearch default): 62.95% (+1.25 points)

The most-confident strategy outperforms random by +0.86 points and least-confident by +1.05 points. The least-confident strategy actually underperforms random selection, confirming the paper's claim that high-entropy incorrect trajectories are noisy and uninformative for training — the model was already uncertain about those decisions, so there is no systematic error to correct.

This ablation is important because it validates a non-obvious design choice. One might intuitively expect that selecting the most uncertain trajectories would maximize learning (the model is confused, so training on those examples should help). The results show the opposite: confident mistakes are the most valuable training signal. This aligns with the reasoning in Section 5.5: confident incorrect trajectories expose "systematic reasoning errors" where the model genuinely believes in a wrong approach. Training on these examples corrects deep-seated misconceptions rather than adding noise.

A limitation: Table 5 reports only final average accuracy, not per-benchmark breakdowns. It is possible that the most-confident strategy helps disproportionately on certain benchmarks (e.g., competition math where systematic errors in algebraic manipulation dominate) and less on others (e.g., Minerva where errors may be more diverse). The aggregate result masks this heterogeneity.

Ablation Studies and Robustness Checks

Search algorithm comparison (Table 3, global frontier selection vs. vanilla UCT): Global frontier selection achieves better trajectory rewards (−0.65 vs. −0.82) with fewer iterations (187.7 vs. 209.6) and reduced per-tree time (1087.7s vs. 1179.6s), confirming that comparing all frontier nodes simultaneously is both more effective and more efficient than root-to-leaf UCT. The improvement is attributed to eliminating redundant traversals through already-expanded nodes and preventing UCT's local myopia from trapping search in shallow subtrees.

Depth bonus function sweep (Table 3): Three functional forms are tested: $\log(d(s) + 1)$ (minimal impact), $d(s)$ (59% per-tree time reduction but degraded reward to −0.76), and $\sqrt{d(s)/d_T}$ (best balance, −0.65 reward with computational savings). The non-monotonic relationship between depth exploration and solution quality is notable: the linear bonus produces the deepest trees (21.55 average depth) but the worst solutions, likely because it overly encourages deep exploration of unpromising branches at the expense of breadth. The square-root bonus's diminishing returns property — rapid bonus increase for shallow depths, plateauing for deep depths — appears important for maintaining this balance.

Uncertainty bonus (Table 3, λ₂ = 0.4): Enabling entropy-based guidance in frontier selection increases exploration diversity (entropy 1.23 → 1.31) but degrades trajectory reward (−0.65 → −0.79) and introduces substantial iteration-count variance (189.3 ± 14.7 → 92.5 ± 22.5). The paper disables this in the default configuration, and the degradation suggests that prioritizing high-uncertainty regions in MCTS is counterproductive — the model's uncertainty is not a reliable signal of where exploration will be most valuable.

Q-value backup rule (Table 4, rows 2–3): The transition from the vanilla backup (simple additive) to the constrained backup rule (Equation 5) is critical. Without the constraint, DeepSearch degrades performance (60.27% vs. 61.70% baseline). Even with the constrained backup but using coarse-grained (outcome-level) token scores, performance is still below baseline (61.38%). Only when both the constrained backup and fine-grained node-level advantages are combined does DeepSearch surpass the baseline (61.85%). This shows that the asymmetric invariants (positive q-values for ever-correct nodes, negative only for never-correct nodes) are necessary to extract a useful training signal from the tree structure.

Advantage normalization (Table 4, rows 5–6): Moving from unnormalized to standard-normalized advantages improves from 61.85% to 62.27% (+0.42 points). Switching to mean-only normalization provides a further small gain to 62.32% (+0.05 points). The paper argues that standard deviation scaling introduces miscalibration when $\sigma_t$ is small (terminal rewards are homogeneous), but the empirical gain is small enough that the choice may not matter much in practice.

Trajectory selection strategy (Table 5): The most-confident incorrect selection (62.95%) substantially outperforms random (62.09%) and least-confident (61.90%) selection. The key negative result is that least-confident selection underperforms random — selecting for uncertainty is actively harmful. This validates the core intuition that systematic errors (confident mistakes) are more informative for training than random or uncertain errors.

Extended training scaling limits (Table 2): The extended DAPO + KL baseline at +1,875 steps regresses to 62.02% from the +785-step checkpoint at 62.08%, using 1,883.2 GPU hours. This is a critical negative result demonstrating that RLVR training does not monotonically improve with more steps. The regression may be due to overfitting to the training distribution, policy collapse, or reward hacking. The paper does not analyze the cause, but the existence of the regression is the primary motivation for the entire DeepSearch approach.

Vanilla MCTS degradation (Table 4, row 2): The -1.43 point drop from the Nemotron v2 baseline when using naive MCTS integration (simple q-value updates, no constrained backup) is an important negative result that the paper mentions but does not extensively analyze. It suggests that tree-structured exploration without proper credit assignment mechanisms can be worse than no exploration at all — the model may learn from misleading signals (e.g., penalizing good steps that happened to appear in bad trajectories, or rewarding bad steps that coincidentally appeared in good trajectories).

Per-tree computation profiling (Table 7, Appendix C): The breakdown shows that model inference dominates MCTS cost: $t_{\text{generate}}$ = 1060.76 ms (99%+ of per-tree time), while all CPU-side operations (prompt construction, terminal checking, input preparation, node expansion) collectively account for <4 ms. This demonstrates that algorithmic improvements to the search strategy (which operate on the CPU side) have negligible direct cost impact — the only way to substantially reduce total MCTS cost is to run MCTS on fewer problems (via adaptive filtering) or to speed up model inference. This profiling validates the paper's design choice to focus on selective application (adaptive training) rather than low-level search optimizations.

Missing ablations. Several potentially informative experiments are not reported: (1) An ablation varying the hard-set filtering threshold $\delta$ from 25% to other values (e.g., 10%, 50%) to determine sensitivity. (2) A comparison where DeepSearch is initialized from the DeepSeek-R1-Distill baseline rather than from Nemotron v2, to isolate DeepSearch's contribution from the 3,000 DAPO steps used to create v2. (3) An ablation testing the impact of the number of MCTS iterations per tree (the paper uses $k_{\max}$ iterations but does not specify the exact number or show performance as a function of this budget). (4) An ablation on the number of children per expansion ($n = 8$) — does performance improve with more children (broader search) or fewer (deeper search per unit compute)? (5) An experiment evaluating DeepSearch with inference-time search (e.g., best-of-N or tree search at evaluation) to test the claim that training-time and inference-time search are complements with compounding benefits.

Critical Assessment

Claim: DeepSearch overcomes the RLVR exploration bottleneck and avoids training plateaus.

The evidence in Table 2 and Figure 2 supports this claim with qualifications. DeepSearch does achieve 62.95% accuracy while extended DAPO plateaus at ~62.02% — a clear improvement. However, the magnitude of improvement (+0.93 points over the best extended training checkpoint, +1.25 points over the v2 base) is modest in absolute terms. Whether this constitutes "overcoming" the plateau or merely "slightly exceeding" it depends on one's expectations. If the exploration bottleneck is fundamental, as the paper argues, one might expect a larger breakthrough — DeepSearch achieves 62.95% where extended training reaches 62.08%, a 0.87-point difference. This is real but incremental. The paper's strongest evidence is not the absolute accuracy gain but the efficiency gain: 330 GPU hours vs. 1,883.2 GPU hours to reach comparable or better performance. The plateau is overcome in the sense that DeepSearch achieves more with less, but the absolute performance ceiling appears to be only marginally higher — 62.95% vs. 62.08% — suggesting that exploration is not the only bottleneck, or that MCTS provides only a partial solution to the exploration problem.

Claim: DeepSearch establishes a new state-of-the-art for 1.5B reasoning models.

Supported. The 62.95% average accuracy exceeds all 1.5B baselines in Table 1, including the previous best Nemotron v2 at 61.70%. However, the gap is modest (1.25 points) and concentrated on harder benchmarks (AIME, Olympiad). On MATH500 and Minerva, the improvement is barely perceptible (0.29 and 0.25 points respectively). The state-of-the-art claim is technically correct but should be contextualized: DeepSearch achieves this by building on the already-state-of-the-art Nemotron v2, adding 50 MCTS-augmented training steps to gain ~1.25 points. It is unclear whether the same MCTS framework applied to a weaker base model would produce comparable gains, or whether the Nemotron v2's strong starting point is necessary for MCTS training to be beneficial.

Claim: DeepSearch uses 5.7× fewer GPU hours than extended training approaches.

Supported but requires careful interpretation. The 5.7× figure compares DeepSearch's 330 GPU hours (for 50 Tree-GRPO steps on top of Nemotron v2) against the extended DAPO + KL baseline's 1,883.2 GPU hours (for 1,875 steps on top of DeepSeek-R1-Distill). These are different starting points: DeepSearch starts from a much stronger model (61.70%) than the extended training baseline (49.46%). A fair efficiency comparison would need to account for the cost of reaching the starting point. The paper also reports a 72× improvement over Nemotron v2 training (24,000 GPU hours to train v2 from DeepSeek-R1-Distill vs. 330 hours for DeepSearch from v2), but this compares training-from-scratch against fine-tuning, which are fundamentally different cost categories. The 5.7× figure is the most defensible comparison, but even it compares different training procedures (Tree-GRPO vs. DAPO) from different starting models. A proper efficiency comparison would initialize both methods from the same checkpoint and measure compute to reach a target accuracy.

Claim: Training-time search and inference-time search are complements.

This is a conceptual claim, not an empirically tested one. DeepSearch is evaluated without inference-time search in Table 1 (temperature 0.6, top-p 0.95, standard decoding). The paper does not report results for DeepSearch combined with inference-time tree search, beam search, or best-of-N. The complementarity claim is therefore speculative — the paper demonstrates that training-time search improves base model quality, but does not show that this improvement makes inference-time search more effective, or that the combination achieves more than either alone. This is acknowledged as future work ("we did not experiment with PRM tree-search techniques in combination with revisions," Section "Limitations and Future Work"), but the claim of complementarity in the paper's narrative goes beyond the evidence presented.

Genuine weaknesses in the experimental design:

1. Single initialization: All results are from a single training run initialized from Nemotron v2. Without multiple seeds, there is no measure of variance. The 62.95% result could be a favorable draw from a distribution whose mean is closer to 62.5%. The paper does not report error bars on any main result.

2. Confounded improvements: DeepSearch adds multiple components simultaneously (MCTS exploration, constrained q-backup, node-level advantages, global frontier selection, adaptive filtering, replay buffer). The ablation in Table 4 traces linear addition, but this does not disentangle which components are individually necessary versus merely helpful in combination. For instance, would MCTS with simple outcome rewards (no q-values, no constrained backup) outperform the baseline if combined with adaptive filtering? We cannot tell from the reported experiments.

3. Single model family and scale: All experiments use 1.5B-parameter Qwen-derived models. There is no evidence that the exploration bottleneck exists at larger scales (7B, 14B, 70B) or in other model families. The 1.5B scale may be a sweet spot where the policy's exploration is particularly limited; larger models with more diverse capabilities might not exhibit the same plateau, or might benefit less from MCTS-augmented training.

4. Single domain (mathematical reasoning): The benefits of MCTS-based exploration may be specific to math, where verification is clean (exact answer matching) and where systematic tree search naturally aligns with the step-by-step structure of mathematical proofs. The paper does not evaluate on code generation (where execution provides verification), logical reasoning, or other domains. The claim that DeepSearch "establishes a new direction for scaling reasoning capabilities" (abstract) is therefore premature — mathematical reasoning is one domain, and the transferability of the approach is unsubstantiated.

5. No inference-time compute scaling comparison: The paper compares against models that use standard decoding, but many baselines (especially search-based methods like Qwen2.5-Math-Oat-Zero) are designed to work with inference-time search. Evaluating DeepSearch with inference-time search and comparing against baselines also evaluated with their preferred inference-time methods would provide a more complete picture. Without this, we cannot rule out that a baseline model with aggressive inference-time tree search could match or exceed DeepSearch's accuracy at comparable total (training + inference) cost.

6. Pass@1 estimation with n=32 samples: The benchmark results use 32 samples to estimate Pass@1 accuracy. For models with high accuracy (e.g., 92.53% on MATH500), the estimation error from 32 samples is small but non-zero. For lower-accuracy benchmarks (e.g., 35.42% on AIME 2025), 32 samples provide a reasonable estimate but with error bars of roughly ±5–8 percentage points (assuming binomial sampling). The paper does not report these uncertainties, making the per-benchmark comparisons noisier than they appear.

7. Replay buffer evaluation: The adaptive training strategy is evaluated only through its effect on the hard-set composition (Table 6) and indirectly through final accuracy. There is no ablation comparing DeepSearch with and without the replay buffer (i.e., running MCTS on all hard problems every round, without caching). This makes it impossible to determine how much of the efficiency gain comes from the replay buffer versus the MCTS exploration itself. It is possible that MCTS without caching would achieve similar or better accuracy at higher cost, and that the replay buffer is trading some accuracy for efficiency — but we cannot tell from the reported data.

8. Filtering threshold sensitivity: The $\delta = 25\%$ threshold for the hard set is a fixed heuristic. No ablation tests alternative thresholds (10%, 50%, adaptive scheduling). If DeepSearch's performance is sensitive to this threshold — and it likely is, since it determines the boundary between problems that receive MCTS and those that don't — the reported result may be a tuned optimum rather than a robust default. The paper's justification (Appendix B.4) that a fixed threshold "prioritizes methodological simplicity and clear attribution of improvements" is reasonable for an initial study, but it limits the strength of the efficiency claims.

9. Oracle answer access during training: DeepSearch requires ground-truth answers to compute the verifier $V(s_{\text{end}})$ and the Pass1@K metric for filtering. This limits applicability to domains where ground-truth verification is available (math with exact answers, code with unit tests). The paper does not discuss approximate verification or learned reward models as alternatives for broader domains.

Experiments that would have strengthened the paper:

1. Multiple training seeds (at least 3) with reported mean and standard deviation for final accuracy and per-benchmark results.

2. Scaling study across model sizes (e.g., 0.5B, 1.5B, 7B) to determine whether the exploration bottleneck and MCTS benefits are scale-dependent.

3. Inference-time compute scaling comparison: evaluate DeepSearch and baselines with best-of-N (N = 4, 8, 16, 32) and with tree search at inference time. This would test the complementarity claim and provide a more complete cost-benefit picture.

4. Replay buffer ablation: DeepSearch without caching vs. DeepSearch with caching, matched for total MCTS iterations. This would isolate the efficiency contribution of the replay buffer from the exploration contribution of MCTS.

5. MCTS budget ablation: performance as a function of MCTS iterations per tree ($k_{\max}$), number of children per expansion ($n$), and maximum tree depth ($d_T$). The current paper fixes these based on empirical heuristics (Appendix B.1) but does not show the sensitivity of results to these choices.

6. Evaluation on code generation benchmarks (HumanEval, MBPP) where execution provides clean verification. This would test domain generalization.

7. Comparison against a baseline that uses process reward model (PRM) training rather than MCTS backpropagation for credit assignment. The paper claims that tree-structured exploration provides credit assignment "for free" without needing a separately trained PRM, but does not compare against a baseline that does train a PRM and uses it for step-level advantages.

Conditional nature of the claims:

• The claim that MCTS overcomes the exploration bottleneck holds for the specific regime tested: 1.5B parameters, mathematical reasoning with verifiable answers, initialized from a strong RLVR-trained model (Nemotron v2). It may not hold for weaker base models (where the exploration space is larger and MCTS may not find correct paths), larger models (where direct rollouts may be more diverse), or domains without clean verification.

• The efficiency claim (5.7× fewer GPU hours) holds when comparing DeepSearch fine-tuning against extended DAPO fine-tuning from different starting points. A fully controlled comparison would likely yield a smaller (but still positive) efficiency gap.

• The state-of-the-art claim is accurate for the specific benchmarks and model scale tested, as of the paper's publication date. The margin over the previous best (1.25 points) is real but small enough that a different random seed, slight hyperparameter change, or benchmark re-weighting could alter the ranking.

6. Limitations and Trade-offs

Single Model Scale and Family: The 1.5B Regime May Be a Sweet Spot for MCTS-Augmented Training

The assumption or constraint. All experiments use a single model from a single family: Nemotron-Research-Reasoning-Qwen-1.5B v2, a 1.5-billion-parameter model derived from Qwen2.5 and fine-tuned with DAPO-style RLVR. The paper does not test DeepSearch at other scales (e.g., 0.5B, 7B, 14B, 70B) or with other model families (e.g., Llama, DeepSeek, Gemma). This is an intentional scope limitation — the paper focuses on the "small reasoning model" regime where training efficiency matters most — but it leaves open the question of whether the exploration bottleneck generalizes.

The consequence. Smaller models have less diverse output distributions than larger models. A 1.5B model's direct rollouts may exhibit rapid mode collapse precisely because the model has limited capacity to represent diverse reasoning strategies. A 7B or 14B model, with richer internal representations, might naturally produce more varied rollouts, reducing the relative benefit of structured tree search during training. Conversely, even larger models might exhibit different exploration pathologies (e.g., overconfidence in certain reasoning patterns rather than mode collapse, or failure modes that MCTS cannot address because correct solutions exist at lower sampling temperatures but direct rollouts at training temperature do not reach them). Without scaling experiments, we cannot distinguish whether DeepSearch addresses a universal RLVR limitation or a scale-specific one.

There is also a practical deployment implication: if the benefits are largest at 1.5B (where exploration is most constrained), practitioners training 7B+ models — where compute budgets are far larger and the cost of MCTS-augmented training would be proportionally higher — may see smaller or even negligible returns. The paper cannot guide that decision.

What evidence exists in the paper. None explicitly addressing scale dependence. The paper's entire empirical foundation (Tables 1–5, Figures 1–2) is built on 1.5B models. The extended training baselines in Table 2 (which demonstrate the plateau) are also 1.5B models initialized from DeepSeek-R1-Distill-Qwen-1.5B. The paper does not cite or report results from larger models to argue that the exploration bottleneck is scale-invariant. The framing in Section 1 — "performance plateaus after thousands of optimization steps" — is presented as a general claim about RLVR, but all supporting evidence comes from a single scale point.

Mitigation status. Not addressed. The paper does not even mention scale dependence as a limitation or future work direction. The "Limitations and Future Work" section (Section 6, final paragraphs) focuses on extending to non-math domains and learning MCTS components, but says nothing about testing at other model sizes. This is a significant omission given how central the "exploration bottleneck" diagnosis is to the paper's narrative.

---

Oracle Verifier and Training-Set Answer Access: The Method Requires Ground-Truth Answers During Training

The assumption or constraint. DeepSearch's MCTS engine relies on a deterministic verification function $V$ that checks whether a completed trajectory's final answer matches the ground-truth answer (Section 3.1, Equation 1). This requires access to the correct answer for every problem in the training set. Additionally, the adaptive filtering strategy (Section 4.1) requires computing Pass1@K — the fraction of sampled solutions achieving correct final answers — to determine which problems belong in the hard set. Both mechanisms assume the availability of ground-truth labels during training.

This is not a hidden assumption — it follows directly from the definition of the verifier in Equation 1 and the filtering criterion in Equations 8–9. The paper is transparent that $V(s) = 1$ indicates a correct answer and $V(s) = 0$ indicates otherwise. What the paper does not discuss is what happens when such a verifier is unavailable.

The consequence. DeepSearch is directly applicable only to domains with automatic, ground-truth verification: mathematics (exact answer matching), code generation (unit test execution), and formal theorem proving (proof checker acceptance). It cannot be applied to open-ended reasoning tasks (essay writing, creative problem-solving, strategic planning), subjective tasks (summarization quality, dialogue coherence), or tasks where correctness is graded on a continuous scale rather than as a binary judgment. Even within mathematics, the approach requires the training set to consist of problems with known answers — it cannot be used for self-supervised exploration on unlabeled math corpora.

The practical scope is therefore narrower than the paper's abstract framing suggests. The abstract positions DeepSearch as addressing "the bottleneck of reinforcement learning with verifiable rewards" broadly, but "verifiable" here means human-annotated ground truth must exist for every training example. This is a stronger requirement than simply having a reward signal (which could be learned, heuristic, or partial). Many RLVR applications — including some reasoning tasks — use learned reward models, heuristic scoring, or partial-credit evaluation that would not satisfy DeepSearch's binary, oracle-verifier requirement.

What evidence exists in the paper. The paper provides no experiments or discussion about approximate or learned verifiers. The verifier is described only as a deterministic correctness check on final answers (Section 3.1, Equation 4: $q(s_{\text{end}}) = +1$ if correct, $-1$ if incorrect). The training data, DeepMath-103K, is described as "verifiable" (Section 5.1) — meaning it contains problems with known answers. No ablation tests performance with a learned reward model substituting for the oracle verifier, or with a reduced set of problems where only some have verified answers. Appendix B.4's discussion of the filtering threshold $\delta$ assumes Pass1@K can be computed, which requires ground truth.

Mitigation status. Not addressed in the current paper. The "Limitations and Future Work" section (final paragraphs) mentions "developing approximate verifiers for subjective tasks" and "exploring human-in-the-loop validation for complex reasoning chains" as future work, but this acknowledges the limitation only obliquely — it frames the extension to non-verifiable domains as future work, not as a current constraint on applicability. The paper does not quantify how many of MATH's test problems or DeepMath-103K's training problems have unique, automatically checkable answers versus problems requiring human judgment, nor does it discuss the cost of labeling new training problems with ground-truth answers.

A practitioner reading this paper needs to know: if your task does not have exact-match ground truth for every training example, DeepSearch cannot be applied directly. This constraint applies to whole categories of reasoning tasks that the paper's title and abstract might otherwise suggest are in scope.

---

The Cost of Difficulty Estimation and Adaptivity Is Not Fully Amortized in the Efficiency Accounting

The assumption or constraint. The adaptive training strategy (Section 4.1) requires evaluating the current policy's Pass1@4 on the full training set at each iteration to construct the hard subset. With an initial hard set size of 13,658 problems (Table 6), this means 13,658 × 4 = 54,632 direct rollouts per filtering round just to determine which problems need MCTS. Across 5 rounds (Table 6), the total Pass1@4 evaluation cost is at least 5 × 54,632 = 273,160 rollout generations, though this decreases slightly as the hard set shrinks in later rounds (problems removed from the hard set presumably still need evaluation to confirm they remain above the threshold).

Additionally, the replay buffer check (Section 4.2) requires looking up cached solutions for each problem — computationally cheap per problem, but requiring infrastructure to maintain and query the buffer across training rounds. The hybrid rollout strategy for cached problems still requires $\beta \cdot B$ direct rollouts per problem (Equation 11), where $\beta$ is determined by the number of cached solutions.

The consequence. The headline efficiency number — 330 GPU hours for DeepSearch versus 1,883.2 GPU hours for extended training (Table 2, 5.7× reduction) — accounts only for the Tree-GRPO training steps themselves (50 steps, Section 5.2). It does not appear to include: (1) the cost of Pass1@4 evaluations at each round to update the hard set, (2) the cost of MCTS exploration for unsolved problems, which is the dominant computation in each training round, or (3) the cost of direct rollouts for cached problems.

The paper does not provide a breakdown of the 330 GPU hours across these components. If the 50 Tree-GRPO training steps are cheap (policy updates on pre-generated data) but the MCTS data generation is expensive, the "330 hours" may represent only part of the total pipeline cost. Table 7's per-tree profiling shows that a single MCTS tree with the default configuration takes 1070.7 seconds (approximately 18 minutes) on "extremely hard" problems (Table 3). With 5,829 unsolved problems in Round 5 (Table 6), full MCTS on all of them would cost 5,829 × 1,070.7s ≈ 1,733 GPU hours — already exceeding the reported 330 hours. This suggests either that the 330-hour figure accounts for only a subset of training, that MCTS is run on far fewer than all unsolved problems, or that the per-tree cost on the filtered hard set is substantially lower than the 1,200-sample average reported in Table 3.

What evidence exists in the paper. The profiling in Table 7 (Appendix C) provides per-tree timing for the default configuration, but the paper does not report (1) how many trees are constructed per training round, (2) the total GPU hours spent on MCTS data generation versus policy optimization, or (3) the total cost including all auxiliary computations (Pass1@4 evaluations, replay buffer maintenance). The 330 GPU hour figure in Table 2 is attributed to "DeepSearch-1.5B" as a single number with no component breakdown. The 5.7× comparison against extended training's 1,883.2 hours also lacks component-level accounting, making it unclear whether the comparison is fair — extended training's 1,883.2 hours presumably include both rollout generation and policy optimization, while DeepSearch's 330 hours may be counting only the optimization steps.

Mitigation status. Partially acknowledged. Section 4.1 states that "applying MCTS to every training example is computationally infeasible" — an explicit recognition of the cost problem. The adaptive training strategy is presented as the solution, and Table 6 demonstrates that it reduces the unsolved problem count by 57% over 5 rounds. But the paper does not report the total cost of the adaptive pipeline including evaluation, MCTS, direct rollouts, and training. The efficiency claim (5.7×) is therefore a lower bound on the relative cost if only the policy optimization steps are counted, and could be significantly smaller (or even reversed) under full-cost accounting.

For a practitioner, the key question is: "If I implement DeepSearch, what is the total GPU hours to go from my current model to a trained DeepSearch model?" The paper provides 330 hours as the answer, but a close reading reveals this number is almost certainly not the full cost. The missing cost breakdown is the single largest obstacle to assessing DeepSearch's practical viability.

---

No Evaluation with Inference-Time Search: The Claim of Complementarity Between Training and Inference Search Is Untested

The assumption or constraint. The paper's conceptual contribution includes the claim that training-time search and inference-time search are "complements with compounding benefits" (Innovation 2 in Section 4). The idea is that MCTS-augmented training produces a model whose base policy is qualitatively better, which in turn provides better raw material for inference-time search to work with. However, all benchmark evaluations in Table 1 use standard decoding: temperature 0.6, top-p 0.95, single sample per problem (estimated with n = 32 samples for Pass@1 accuracy). DeepSearch is never evaluated with inference-time search — no best-of-N, no beam search, no tree search at test time.

The consequence. The complementarity claim is speculative. It is entirely possible that the 1.25-point improvement from DeepSearch over the Nemotron v2 baseline (61.70% → 62.95%) would be smaller if both models were evaluated with inference-time search. Concretely: if Nemotron v2 with best-of-32 at inference time achieves 68% accuracy, and DeepSearch with best-of-32 achieves 68.5%, the marginal benefit of training-time search shrinks when inference-time search is available. The exploration that MCTS provides during training might overlap with the exploration that inference-time search provides — the model might already be encountering diverse reasoning paths at test time, so learning from them during training adds less marginal value.

Conversely, DeepSearch might actually benefit more from inference-time search than the baselines — the improved base policy might be more amenable to search (e.g., providing more reliable step-level decisions for tree-based search algorithms). Without evaluating this, we cannot tell whether DeepSearch's practical value is in improving base model quality (as measured in Table 1) or in creating a model that is particularly well-suited for deployment with inference-time search (which would be measured by a different evaluation protocol). The paper's narrative implies both, but tests only the first.

This matters for real-world deployment. If an organization plans to use inference-time search regardless (as is increasingly common for high-stakes reasoning tasks), the relevant metric is accuracy after inference-time search, not base sampling accuracy. The paper provides no evidence that DeepSearch improves this metric relative to baselines that also receive inference-time compute.

What evidence exists in the paper. None. The evaluation protocol (Appendix A.4) specifies low-temperature sampling without any mention of best-of-N, majority voting, beam search, or tree search at evaluation time. The baselines in Table 1 include Qwen2.5-Math-1.5B-Oat-Zero, which is designed for inference-time search (Liu et al., 2025b), but it is evaluated under the same single-sample protocol as DeepSearch — potentially understating its capabilities.

Mitigation status. Acknowledged as future work. The final paragraph of Section 6 ("Limitations and Future Work") mentions this as a general direction: "we did not experiment with PRM tree-search techniques in combination with revisions" — but this phrasing frames it as an unexplored combination rather than a missing evaluation. The paper does not state that the complementarity claim is untested or that the benchmark results should be interpreted as reflecting base model quality, not deployment-time accuracy with search. A practitioner reading Table 1 might reasonably assume that DeepSearch's 62.95% represents the best achievable accuracy, period — without realizing that applying inference-time search to baselines might close or reverse the gap.

---

Empirical Coverage Is Narrow: Single Domain, Single Dataset, Single Training Run Per Configuration

The assumption or constraint. All experiments use mathematical reasoning benchmarks (AIME 2024/2025, AMC2023, MATH500, Minerva, Olympiad) for evaluation, and DeepMath-103K for training. The paper provides no results on code generation (HumanEval, MBPP), logical reasoning (ARC, FOLIO), scientific QA, or any non-math domain. Additionally, the paper reports results from what appears to be a single training run per configuration — the main result (62.95%) is a point estimate without confidence intervals, error bars, or multi-seed averaging. Tables 1, 2, and 4 report single numbers with no measure of variability.

The consequence on domain generalization. Mathematical reasoning has properties that make MCTS-augmented training particularly natural: (1) solutions have a clear step-by-step structure that maps cleanly onto tree nodes, (2) intermediate steps can be evaluated for partial progress (though DeepSearch uses only terminal verification), and (3) the verification function is exact (answer matching after normalization) with no ambiguity. These properties may not hold in other domains. Code generation has structural similarities (executable steps, test-based verification) and is the most likely domain for transfer. But scientific reasoning, multi-hop QA, and strategic planning involve fuzzier intermediate states, partial credit, and verification that may require human judgment or learned reward models. The paper provides no evidence that DeepSearch's benefits transfer to these settings, and the strong dependence on exact-match verification (see limitation above) makes transfer to non-verifiable domains impossible without modification.

The consequence on result reliability. Without multiple training runs, the reported 62.95% result could be a favorable seed. Given that the improvement over the Nemotron v2 baseline is only 1.25 percentage points, even modest run-to-run variance could mean the true expected improvement is smaller (or zero). The extended training baselines in Table 2 show that performance can vary non-monotonically: the +785-step checkpoint achieves 62.08% while the +1,875-step checkpoint regresses to 62.02%. If DeepSearch exhibits similar variance, the comparison against the 1,875-step baseline (which DeepSearch beats by 0.93 points) is within the range of possible run-to-run variation. Without error bars, we cannot assess whether the 62.95% vs. 62.02% difference is statistically significant or within noise.

What evidence exists in the paper. The search strategy ablation in Table 3 reports "mean ± standard deviation" over 1,200 samples for search metrics (depth, entropy, reward, iterations, timing), which is the only quantitative variability estimate in the paper. The main benchmark results contain no such estimates. The paper cites Hochlehnert et al. (2025) for evaluation methodology consistency, but that reference addresses benchmark contamination and evaluation protocols, not multi-seed reliability. The training protocol (Appendix A.5) specifies 100 training steps with checkpointing every 5 steps, and it is standard practice in RL training to report results from the best or final checkpoint — but without multiple seeds, there is no way to know if a different random initialization would produce a different best checkpoint.

Mitigation status. Not addressed. The paper does not mention the lack of multi-seed evaluation as a limitation, does not report confidence intervals, and does not discuss statistical significance. For the domain generalization gap, the "Limitations and Future Work" section (final paragraphs) acknowledges this implicitly by proposing future work on "extend[ing] DeepSearch beyond mathematical reasoning to domains with distinct verification mechanisms" and "developing approximate verifiers for subjective tasks." This frames domain generalization as future work rather than a current limitation, but the absence of any non-math results means the paper's claims — including the title's "Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards" — are only validated for mathematical reasoning with exact-match verification.

---

The Replay Buffer May Mask Catastrophic Forgetting Rather Than Preventing It

The assumption or constraint. The replay buffer (Section 4.2, Equation 10–12) caches correct solutions discovered by MCTS and forcibly includes them in subsequent training batches alongside fresh direct rollouts. This ensures that the model continues to see correct solutions for previously solved problems. The paper presents this as an anti-catastrophic-forgetting mechanism: by including cached correct trajectories, the model does not forget how to solve problems that MCTS previously cracked. The hybrid rollout strategy (Equation 11) mixes cached correct solutions with fresh direct rollouts for cached problems.

The consequence. The replay buffer may be masking catastrophic forgetting rather than preventing it. The model might be forgetting how to independently produce correct solutions for cached problems, but the forced inclusion of cached trajectories in the training data means the model is trained on those solutions regardless — it learns to reproduce the cached answer rather than maintaining the ability to generate it from scratch. The Pass1@4 metric used for filtering (Section 4.1) should catch this (if Pass1@4 drops below 25%, the problem goes back into the unsolved set), but the paper does not report Pass1@4 metrics for cached problems over successive rounds. If the model's independent success rate on cached problems degrades (while still above 25% to avoid re-filtering), the replay buffer is providing a crutch — the model appears to maintain performance only because it's being force-fed the correct answers.

This is a general concern with experience replay in RL: mixing off-policy data (cached trajectories from an older policy) with on-policy data (fresh rollouts from the current policy) can create distributional mismatch that destabilizes learning. The Tree-GRPO objective uses importance sampling ratios (Equation 14, $\rho_{j,k}(\theta)$) to correct for this mismatch, but the correction is only valid locally — if the policy has changed substantially since the cached trajectory was generated, the importance ratio may be a poor approximation.

Practically, this means that a model deployed after DeepSearch training might perform worse on problems that were in the replay buffer than the benchmark results suggest. The benchmark evaluation in Table 1 tests the model's independent problem-solving ability (single-sample generation), which should reveal any such degradation — but the paper does not report per-problem performance comparing cached vs. never-cached problems. It is possible that the aggregate 62.95% accuracy is inflated by strong performance on problems where the model memorized cached solutions, while performance on non-cached hard problems is lower.

What evidence exists in the paper. Table 6 shows the cached-to-unsolved ratio across rounds, demonstrating that caching increases. But there is no ablation comparing DeepSearch with and without the replay buffer (e.g., re-running MCTS on all hard problems every round without caching), no Pass1@4 tracking for cached problems specifically (only aggregate hard-set filtering), and no analysis of how much of the training data in later rounds comes from cached versus freshly generated trajectories. The paper does not report whether the policy's independent success rate on cached problems degrades over rounds.

Mitigation status. Partially addressed through the design of the hybrid rollout strategy. By supplementing cached solutions with fresh direct rollouts (Equation 11), the model continues to see on-policy data for cached problems, which should mitigate distributional shift. The importance sampling correction in Tree-GRPO also provides some theoretical protection. However, the paper does not empirically validate that these mechanisms are sufficient — no experiment demonstrates that DeepSearch's performance does not degrade when the replay buffer is removed, or that the model's independent success rate on cached problems remains stable. The progressive filtering (Equation 9) should theoretically re-identify problems where performance degrades, but the 25% threshold is a coarse filter — a problem could drop from 100% success to 30% success (a catastrophic degradation) without being re-flagged for MCTS.

For a practitioner deciding whether to adopt DeepSearch, this limitation matters because it affects confidence in the deployed model's robustness. If the model's strong benchmark performance is partially sustained by forced exposure to cached correct answers during training, it may underperform in deployment when it must independently solve similar problems without access to those cached solutions. The paper provides no evidence to rule this out.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper reframes the RLVR research agenda from an optimization problem to an exploration problem. Before DeepSearch, the dominant narrative treated RLVR scaling as a matter of training depth: more optimization steps, more rollouts, better performance — with diminishing returns accepted as inevitable and the open question being how to push the saturation point further out through better optimizers, reward shaping, or regularization. The Nemotron v1 → v2 progression (2,000 → 3,000 DAPO steps for +1.53% average accuracy) already hinted at diminishing returns, but the extended training baselines in Table 2 make the diagnosis unambiguous: after ~3,000 steps, direct policy rollouts have exhausted their exploration value, and further optimization on rollouts from a mode-collapsed policy yields zero or negative returns (62.08% at +785 steps, regressing to 62.02% at +1,875 steps). This is not slow improvement — it is a hard ceiling.

The conceptual shift, then, is that the exploration mechanism determines the performance ceiling, not the optimizer. This changes what "scaling RLVR" means. Instead of asking "how many more steps can we afford?", the question becomes "how do we generate training data that contains reasoning paths the policy would never sample on its own?" DeepSearch provides one answer — MCTS with global frontier selection — but the framing matters more than the specific algorithm. The paper implicitly argues that any training method that relies exclusively on the policy's own rollouts for data generation will hit a qualitatively similar ceiling, and that breaking through requires an external exploration engine that can surface trajectories outside the policy's mode.

This reframing has several specific consequences for the field:

RLVR research shifts from optimizer engineering to exploration engineering. The marginal returns to tweaking learning rates, clip thresholds, KL penalties, or reward normalization are fundamentally capped by the informativeness of the training data. DeepSearch shows that a structurally different data generation process (MCTS) yields +1.25 points over the Nemotron v2 baseline in 50 steps, while 1,875 steps of continued DAPO optimization on direct rollouts regresses below both. The implication is that research effort currently devoted to optimizer variants (of which DAPO, GRPO, and their many derivatives are examples) should be partially redirected toward exploration mechanisms — tree search, multi-agent debate, tool-augmented reasoning chains, or learned exploration policies — that can produce training data the base policy cannot generate alone.

The inference-training division of labor becomes a design spectrum, not a clean separation. The field has treated search as an inference-time mechanism and training as a rollout-based optimization process. DeepSearch collapses this distinction by using search as the training data generator, demonstrating that the exploration patterns discovered by MCTS at training time produce a better base policy even when inference-time search is not used (Table 1, where DeepSearch is evaluated with standard decoding). This makes inference-time search and training-time search two points on a spectrum of exploration investment, rather than fundamentally different activities. A model trained with MCTS exploration has already internalized some of what inference-time search would otherwise need to discover, making the remaining inference-time exploration potentially easier or less necessary. The paper does not test this compounding, but the conceptual implication is clear: the optimal allocation of search compute between training and inference is a new optimization problem that the field has not yet framed.

Process reward models (PRMs) become one option among several for credit assignment, not the only option. DeepSearch's node q-values — computed as a byproduct of MCTS backpropagation — provide step-level credit assignment without requiring a separately trained PRM. This is not to say PRMs are obsolete (they operate at inference time without tree construction, which MCTS q-values cannot do), but it demonstrates that credit assignment can emerge from the structure of exploration itself rather than from a learned evaluator. The field now has two distinct paradigms for step-level supervision: learned (PRMs trained on human labels or Monte Carlo rollouts) and exploratory (q-values derived from counterfactual branch evaluation in a search tree). The tradeoffs between them — PRM training cost vs. MCTS tree construction cost, PRM generalization across domains vs. MCTS requirement for ground-truth verification — are unexplored and constitute a new axis of research.

The small-model reasoning regime is revealed as the natural testbed for exploration research. The exploration bottleneck is most severe at 1.5B parameters, where the policy's output distribution is narrow enough that direct rollouts quickly collapse. At larger scales (7B, 14B, 70B), the policy may have sufficient internal diversity that direct rollouts remain informative for longer — or it may exhibit entirely different exploration pathologies (overconfidence rather than mode collapse). The paper effectively establishes 1.5B as the "exploration stress test" scale: if a new exploration method doesn't help here, it's unlikely to help anywhere; if it does, scaling experiments determine whether the benefit grows, shrinks, or plateaus with model size. This gives the field a principled starting point for exploration research — start at 1.5B where the signal is clearest, then scale up.

The "more training steps" research program is partially devalued. The extended training baselines in Table 2 demonstrate that brute-force scaling of RLVR steps beyond ~3,000 yields sharply diminishing returns and eventual regression. While stability tricks (KL penalties, dynamic batching, Clip-Higher) can extend the point of collapse slightly (+1,875-step DAPO + KL achieves 62.02% vs. the +325-step DAPO at 61.78%), the trend is clear: you cannot out-train an exploration deficit. This does not mean optimizer research is worthless — the 3,000 DAPO steps from DeepSeek-R1-Distill to Nemotron v2 provide +12.24 points, which is enormous — but it means that after the optimizer has extracted all available signal from direct rollouts, further progress requires a different data source. Papers proposing "just train longer with better hyperparameters" as a path to improved reasoning now carry the burden of demonstrating that their approach surpasses the exploration ceiling, not just that it matches or slightly exceeds prior training-curve baselines.

Follow-Up Research This Work Enables

Scaling DeepSearch to larger model sizes to determine whether the exploration bottleneck is scale-dependent. The paper's entire empirical foundation rests on 1.5B models. A natural and urgent follow-up is to replicate the core experiment — MCTS-augmented training vs. extended DAPO training — at 7B, 14B, and 70B scales using the same DeepMath-103K dataset and comparable initialization protocols (e.g., DeepSeek-R1-Distill-Llama-8B + 3,000 DAPO steps for the 8B case, then apply DeepSearch vs. continued DAPO). The key measurement is the marginal benefit of MCTS as a function of model size: does the +1.25-point gain at 1.5B grow (because larger models can better exploit richer exploration), shrink (because larger models' direct rollouts are already diverse enough), or vanish (because larger models hit a different bottleneck, such as reward signal quality rather than exploration coverage)? A negative result — MCTS provides negligible benefit at 7B+ — would limit DeepSearch's practical impact to the small-model regime but would not invalidate the exploration bottleneck diagnosis; it would instead suggest that the bottleneck's severity is inversely proportional to model capacity. A positive result — gains compound with scale — would make MCTS-augmented training a standard component of large-model RLVR pipelines.

Evaluating DeepSearch models with inference-time search to test the complementarity hypothesis. The paper claims training-time and inference-time search are complements but evaluates DeepSearch only with standard decoding (temperature 0.6, top-p 0.95, single sample). A direct test: take DeepSearch-1.5B and Nemotron v2, evaluate both with best-of-N (N = 4, 8, 16, 32, 64), beam search, and tree search at inference time, and measure whether the accuracy gap at N=1 (1.25 points) grows or shrinks as inference compute increases. The complementarity hypothesis predicts the gap should widen: DeepSearch's superior base policy provides better raw material for inference-time search to refine, so the marginal benefit of inference compute should be larger for DeepSearch than for Nemotron v2. The substitution hypothesis predicts the gap should shrink: inference-time search compensates for the baseline model's weaker training, so both models converge to similar accuracy given enough inference compute. The null hypothesis predicts a constant gap: inference-time search provides the same additive benefit regardless of base model quality. Distinguishing these would clarify whether DeepSearch's practical value proposition is "better base model" or "better ecosystem compatibility with inference-time methods."

Replacing the oracle verifier with a learned process reward model to extend DeepSearch to domains without ground-truth answers. DeepSearch's MCTS engine requires $V(s_{\text{end}})$ to check terminal node correctness (Equation 1), and the adaptive filtering strategy requires Pass1@K with ground-truth labels. Both are currently oracle-dependent. A critical follow-up replaces the oracle verifier with a PRM trained on the base model's outputs using Monte Carlo rollouts (as in Wang et al., 2023) or human step-level labels (Lightman et al., 2023), then measures the degradation in DeepSearch's final accuracy as a function of PRM quality. The experiment could use MATH training data (where oracle answers exist) to train PRMs of varying quality (by varying PRM training data quantity), then run DeepSearch with each PRM substituting for the oracle, comparing against the oracle-verifier upper bound (62.95%). This would establish the verifier quality threshold below which DeepSearch's benefits disappear — a crucial number for practitioners considering domains like code generation (where unit tests provide noisy verification), scientific reasoning (where heuristics are imperfect), or open-ended tasks (where learned reward models are the only option). If DeepSearch is robust to moderate PRM degradation (e.g., 90% PRM accuracy yields 62.5% vs. 62.95% oracle), the approach generalizes broadly. If it collapses (e.g., 90% PRM accuracy yields 60% final accuracy), DeepSearch is effectively restricted to oracle-verifiable domains.

Ablating the replay buffer to measure whether caching masks or prevents catastrophic forgetting. The replay buffer (Section 4.2) forces cached correct solutions into training data for previously-solved problems, guaranteeing positive examples are always present. This could be a genuine anti-forgetting mechanism, or it could be a crutch — the model might forget how to independently produce correct solutions for cached problems but maintain Pass1@4 above 25% only because the cached solutions are in-distribution at training time. A clean ablation: run DeepSearch with and without the replay buffer, evaluating Pass1@K for cached problems specifically at each round. If the replay buffer is essential (accuracy collapses without it, even with MCTS re-run on all problems each round), it reveals that catastrophic forgetting is a first-order problem in RLVR for reasoning — a finding that would motivate dedicated research on stable continual learning for reasoning models, beyond just caching. If the replay buffer is largely about efficiency (MCTS without caching achieves similar accuracy but at higher cost), it confirms the paper's framing but raises the question of whether the efficiency gap in Table 2 (5.7×) would shrink under full-cost accounting that includes re-running MCTS. This ablation is also practically important: in domains where MCTS is cheap (short reasoning chains, fast verifier), the complexity of maintaining a replay buffer may not be worth the savings; in domains where MCTS is expensive, the buffer is essential. The paper provides no data to guide this decision.

Testing whether the entropy-based negative selection rule (most confident incorrect trajectory) transfers to other exploration mechanisms beyond MCTS. Table 5 shows that selecting the lowest-entropy incorrect trajectory for training outperforms random selection by +0.86 points and least-confident selection by +1.05 points — a robust finding that the paper attributes to targeting systematic reasoning errors. This insight is not MCTS-specific: any exploration mechanism that generates incorrect trajectories (beam search, best-of-N with verifier rejection, multi-agent debate, even direct rollouts with confidence scoring) could apply the same entropy-based filtering. A follow-up study would test whether training on the lowest-entropy incorrect trajectories from direct rollouts (without any tree search) already improves upon standard RLVR. Concretely: for each problem, sample N=8 direct rollouts, verify correctness, and if no correct solution exists, select the single lowest-entropy incorrect trajectory for the training batch (discarding the other 7). Compare against standard RLVR where all 8 trajectories are used. If the entropy filter alone provides a meaningful fraction of DeepSearch's gain (e.g., +0.5 of the +1.25 points), it suggests that the primary mechanism is data curation (identifying informative errors) rather than data generation (tree-structured exploration). This would be a practically important finding: entropy-filtered direct rollouts are far cheaper than MCTS and could be deployed immediately in any RLVR pipeline.

DeepSearch applied to code generation, where execution-based verification is natural but reasoning structures differ from mathematics. Code generation shares key properties with math — verifiable outcomes (unit tests), step-by-step structure (lines of code, intermediate subgoals), and a solution space where systematic search is known to help at inference time (AlphaCode-style sampling, execution-guided beam search). However, coding introduces differences that stress-test DeepSearch: (1) solutions are evaluated against multiple test cases, not a single ground-truth answer, so the verifier $V$ is inherently multi-dimensional (passing 3/5 tests is not binary correct/incorrect), (2) the branching factor for code is enormous (vastly more ways to write a function than to solve an algebra problem), potentially making MCTS tree construction prohibitively expensive, and (3) the notion of a "step" is less naturally discretized (a code block vs. a reasoning sentence). A replication on HumanEval and MBPP using DeepSeek-R1-Distill-Qwen-1.5B as the base and some code-specific training set (e.g., a filtered CodeContests split) would test whether DeepSearch's design choices (256-token steps, $n = 8$ children, $d_T = 64$ depth, asymmetric q-backup) transfer to a structurally different reasoning domain or require domain-specific adaptation. The key metric: does DeepSearch on code achieve comparable efficiency gains over extended DAPO training as it does on math? A null result here would bound DeepSearch's generality; a positive result would open the much larger code generation RLVR community as an application domain.

Practical Applications and Downstream Use Cases

Budget-constrained deployment of small reasoning models for competition-level math assistance. Table 1 shows DeepSearch-1.5B achieves 53.65% on AIME 2024 and 90.39% on AMC2023 — competition-math performance that previously required larger models (DeepSeek-R1-Distill-Qwen-7B achieves comparable AIME scores) or substantially more training compute. For organizations building math tutoring systems, automated problem-solving pipelines, or contest-preparation tools, this means a 1.5B model — deployable on a single consumer GPU with no inference-time search overhead — can serve as the reasoning engine rather than requiring a 7B+ model on datacenter hardware. The 5.7× training efficiency advantage (Table 2) translates to lower iteration costs for model updates: when new competition problems are released (e.g., AIME 2026), fine-tuning DeepSearch on those problems requires 330 GPU hours rather than 1,883+, enabling faster turnaround. The key constraint is that the training pipeline requires ground-truth answers, which for competition math is a one-time labeling cost per problem set.

Data generation for self-improvement loops in verifiable domains. DeepSearch's MCTS engine produces not just a trained policy but also a replay buffer of verified correct solution trajectories for challenging problems (Table 6: 2,894 cached solutions by Round 5). These cached trajectories are high-quality training data in their own right — they represent diverse reasoning paths discovered through systematic search, not just the paths the policy happened to sample. An organization running a self-improvement pipeline (e.g., STaR or ReST$^{EM}$-style iterative fine-tuning) could use DeepSearch as the data generation step: run MCTS-augmented training for a few rounds, extract the replay buffer as a curated dataset of challenging problems with verified solutions, and use that dataset to fine-tune a larger model or to bootstrap the next iteration of RLVR training. This decouples exploration (which DeepSearch handles via MCTS) from optimization (which can be done with any RLVR method on the enriched dataset). The paper's finding that the Nemotron v2 base model (3,000 DAPO steps) benefits from DeepSearch's 50 additional Tree-GRPO steps suggests that the MCTS-discovered solutions contain novel information not present in the direct rollouts used for original DAPO training — information that might similarly benefit other models or training stages.

Cost-sensitive inference for high-volume mathematical reasoning APIs. Services that process large volumes of math problems (homework grading platforms, automated contest judging, quantitative finance reasoning) face a compute allocation problem: send every problem to a large model with inference-time search (accurate but expensive) or send everything to a small model with standard decoding (cheap but inaccurate). DeepSearch offers a third option: deploy the 1.5B model without inference-time search and achieve accuracy competitive with larger or search-augmented models. For example, DeepSearch-1.5B's 92.53% on MATH500 and 90.39% on AMC2023 are within striking distance of what 7B+ models achieve on these benchmarks, despite requiring a fraction of the inference FLOPs. A platform processing 1 million math queries per day with DeepSearch-1.5B at batch size 1 would consume roughly 1/5th the GPU-hours of a 7B model (assuming linear FLOP scaling with parameters for inference), with accuracy degradation measured in low single-digit percentage points on benchmarks where both models are near ceiling. The practical tradeoff — whether the accuracy gap justifies the cost gap — can now be made with concrete numbers rather than speculation.

When to Prefer This Method

The paper does not articulate an explicit decision rule or tradeoff matrix against named alternatives, so a forced "Prefer DeepSearch when... / Prefer extended DAPO when..." matrix would be generic boilerplate. However, the paper's experimental design implies a clear set of conditions under which DeepSearch is the appropriate choice, based on the evidence presented:

• When the base model is in the 1.5B parameter range (or comparably capacity-constrained) and has already undergone substantial RLVR training (2,000–3,000 steps) that shows signs of plateauing. The exploration bottleneck is most severe in this regime, and the +1.25-point gain over Nemotron v2 is evidence that MCTS provides marginal value where extended DAPO provides zero or negative value. For a freshly initialized model or one early in RLVR training (e.g., < 1,000 steps), the relative benefit of MCTS over continued direct rollouts is unknown — the Nemotron progression from DeepSeek-R1-Distill (+12.24 points in 3,000 DAPO steps) suggests that direct rollouts are productive early on, and MCTS might be an unnecessary expense in that phase.

• When the training domain has exact-match ground-truth verification available for all training examples, and Pass1@K evaluations are cheap relative to MCTS tree construction. The oracle verifier constraint is hard — without it, DeepSearch cannot operate as described. The adaptive filtering requires periodic Pass1@4 evaluations on the full training set, which adds overhead. If verification is expensive (e.g., requiring human judgment or slow simulation), the total pipeline cost may exceed extended DAPO training even if the optimization steps themselves are cheaper.

• When the total training compute budget is measured in thousands rather than tens of thousands of GPU hours, and marginal accuracy improvements of 1–2 percentage points at the 60%+ accuracy level are meaningful. DeepSearch's 330 GPU hours (whatever they include — see Section 6 discussion) produces a model at 62.95% vs. 61.70% from the initialization. This is a high-accuracy regime where improvements are inherently incremental. If the goal is a 50% → 55% jump, the Nemotron v2 base (3,000 DAPO steps, 24,000 GPU hours) is a more appropriate target than DeepSearch's fine-tuning step. DeepSearch is a refinement tool, not a replacement for initial RLVR training.