DeepSearch：通过蒙特卡罗树搜索克服可验证奖励强化学习的瓶颈

后文有个数学小例子解释这篇文章的数学公式和逻辑，MCTS和RLVR是如何工作的。

在人工智能领域，特别是大语言模型（LLM）的推理能力提升上，强化学习与可验证奖励（RLVR）已成为一种关键范式。它允许模型从可客观评估的奖励信号中学习复杂推理路径。然而，正如许多前沿研究所揭示的，这种方法在训练过程中往往遭遇“高原”现象：经过数千步优化后，性能提升趋于平缓，计算投入的边际回报急剧下降。这背后的根源在于训练时的探索不足——模型依赖有限的直接 rollout，往往遗漏关键推理路径，导致解决方案空间覆盖不全。

本文将介绍一篇最新预印本论文《DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search》（arXiv:2509.25454v2，2025年10月1日发布），由斯坦福大学、东京大学、RIKEN AIP 等机构的学者共同撰写。该论文提出了一种创新框架 DeepSearch，将蒙特卡罗树搜索（MCTS）直接嵌入 RLVR 训练循环中，实现从“深度扩展”向“广度探索”的范式转变。对于初学者，这是一个关于如何让 AI “更聪明地思考”的故事；对于专家，它则提供了对训练动态、探索策略和奖励传播的深度剖析。让我们一步步深入。

问题：RLVR 的探索瓶颈与训练-推理脱节

大语言模型在复杂推理任务（如数学证明）上取得了显著进步，这得益于测试时计算扩展策略，例如树搜索结合过程级评估（Li et al., 2023; Yao et al., 2023）。然而，这些方法通常仅将结构化搜索限于推理阶段，而训练过程仍局限于直接策略 rollout。这种分离导致两个核心问题：

1. 稀疏探索模式：训练时模型仅生成有限路径，难以覆盖解决方案空间的多样性。结果是，模型虽能在推理时“临时”调用搜索，但无法从系统探索中习得内在模式。
2. 性能高原：近期延长 RL 训练的研究（Liu et al., 2025a）显示，数千步后收益递减——额外计算仅带来微弱改进，凸显单纯“堆积训练步数”的局限。

论文的核心洞见在于：要突破瓶颈，必须将训练时的探索置于首位。通过 MCTS 的结构化搜索，模型不仅学习正确解，还从探索过程本身获得丰富监督信号。这不仅是工程优化，更是范式革新：从“结果导向”转向“路径导向”学习。

DeepSearch 框架：MCTS 与 RLVR 的深度融合

DeepSearch 的设计围绕一个修改版 MCTS 展开，针对问题 $x$ 和策略模型 ${\pi }_{\theta }$ 构建搜索树。根节点表示问题 $x$，子节点对应中间推理步骤 $s$，一条从根到叶的路径形成轨迹 $t=x\oplus s_1\oplus s_2\oplus \cdots \oplus s_{\text{end}}$。不同于传统 MCTS 的根到叶遍历，DeepSearch 引入全局前沿选择，实现高效的树状扩展与回传。

框架迭代通过四个组件运行：扩展（Expansion）、选择（Selection）、分数备份（Score Backup）和自适应训练（Adaptive Training）。其整体流程如图 1 所示（论文第 3 页），强调从全局视角优先高潜力节点。

2.1 基于熵引导的扩展（Expansion with Entropy-Based Guidance）

在第 $i$ 步，收集当前观察$o_i=x\oplus s_1\oplus \cdots \oplus s_{i-1}$，用 ${\pi }_{\theta }(s_i|o_i)$ 生成 $n$ 个候选下一步 {si,j}j=1n\{s_{i,j}\}_{j=1}^n{si,j​}j=1n​。重复扩展直至终端节点 $s_{\text{end}}\in S_{\text{end}}$（到达最终答案或最大深度 $d_T$）。

新生成终端节点集 $S_{\text{end}}^{(k)}$ 通过验证函数 V:Send→{0,1}V: S_{\text{end}} \to \{0,1\}V:Send​→{0,1} 分区：
Scorrect(k)={s∈Send(k)∣V(s)=1},Sincorrect(k)={s∈Send(k)∣V(s)=0}. S_{\text{correct}}^{(k)} = \{s \in S_{\text{end}}^{(k)} \mid V(s) = 1\}, \quad S_{\text{incorrect}}^{(k)} = \{s \in S_{\text{end}}^{(k)} \mid V(s) = 0\}. Scorrect(k)​={s∈Send(k)​∣V(s)=1},Sincorrect(k)​={s∈Send(k)​∣V(s)=0}.
若无正确解，则选最自信负例：
$$s_{\text{neg}}^{\ast }=\arg \underset{s\in S_{\text{incorrect}}^{(k)}}{\min }\bar{H}(t(s)),$$
其中平均轨迹熵 $\bar{H}(t(s))=\frac{1}{|t(s)|}{\sum }_{i=1}^{|t(s)|}H({\pi }_{\theta }(s_i|o_i))$，$H$ 为香农熵的蒙特卡罗估计。这优先针对模型“自信错误”的路径，提供针对性监督。

2.2 启发式分数备份（Heuristic Score Backup）

选定轨迹 $t^{\ast }$（正确或负例）后，沿路径更新 q 值：
$$q^{(m)}(s_i)=q^{(m-1)}(s_i)+\gamma (i,l)\cdot q^{(m)}(s_{\text{end}}),$$
$\gamma (i,l)=\max \left(\frac{i}{l},{\gamma }_{\min }\right)$（${\gamma }_{\min }=0.1$）赋予终端附近节点更高权重。终端奖励 $q(s_{\text{end}})=+1$（正确）或 $-1$（错误/不完整）。约束规则确保正确路径 q 值非负：
$$q^{(m)}(s_i)=\{\begin{array}{ll}{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}})\ge 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{array}$$
这实现细粒度信用分配，避免负值污染正确中间步骤。

2.3 混合选择策略（Hybrid Selection Strategy）

结合局部 UCT（Upper Confidence Bounds for Trees）和全局前沿选择：

• 局部选择（兄弟比较）：$UCT(s)=Q(s)+\lambda \sqrt{\frac{\ln N_{\text{parent}}(s)}{N(s)}}$，平衡利用与探索。
• 全局前沿选择：前沿集 F={s∈T∣ξ(s)=0,s∉Send,d(s)<dT}F = \{s \in T \mid \xi(s)=0, s \notin S_{\text{end}}, d(s) < d_T\}F={s∈T∣ξ(s)=0,s∈/Send​,d(s)<dT​}，优先分 $F(s)={\lambda }_1\tanh (Q_{\text{parent}}(s))+{\lambda }_{2}H({\pi }_{\theta }(s|o))+{\lambda }_{3}D(d(s))$（$D(d(s))=\sqrt{d(s)/d_T}$）。$s^{\ast }=\arg {\max }_{s\in F}F(s)$。

混合设计提升效率：局部确保子树最优，全局避免“局部最优陷阱”，并通过熵奖金引导不确定区域探索。

自适应训练：效率与遗忘防护

为避免全样本 MCTS 的计算开销，DeepSearch 引入迭代过滤与回放缓冲（Replay Buffer）：

• 迭代过滤：初始硬集 Dhard(0)={x∈Dtrain∣Pass@1@K(x,πθ(0))<δ(0)}D_{\text{hard}}^{(0)} = \{x \in D_{\text{train}} \mid \text{Pass@1@K}(x, \pi_{\theta}^{(0)}) < \delta^{(0)}\}Dhard(0)​={x∈Dtrain​∣Pass@1@K(x,πθ(0)​)<δ(0)}（$K=4,\delta =0.25$）。迭代 Dhard(i+1)={x∈Dhard(i)∣Pass@1@K(x,πθ(i))<δ(i)}D_{\text{hard}}^{(i+1)} = \{x \in D_{\text{hard}}^{(i)} \mid \text{Pass@1@K}(x, \pi_{\theta}^{(i)}) < \delta^{(i)}\}Dhard(i+1)​={x∈Dhard(i)​∣Pass@1@K(x,πθ(i)​)<δ(i)}，聚焦难题。
• 缓存解决方案：缓冲 $R^{(i+1)}=R^{(i)}\cup R_{\text{candidates}}^{(i)}$，$R_{\text{candidates}}^{(i)}=\{(x,t_{\text{correct}})\mid \dots \}$。 rollout 策略：若缓存可用，则 $t_{\text{cached}}\cup \text{DirectRollouts}(x,\beta )$; 否则全 MCTS。
• Tree-GRPO 目标：q 值软裁剪 $q(s_j)=\tanh (q^{(k_{\max })}(s_j)/{ϵ}_q)\cdot q_{\max }$（${ϵ}_q=1,q_{\max }=1$）。目标：

$$J(\theta )={\mathbb{E}}_{T\sim \mathcal{T},t_i\sim T,(s_j,o_j)\sim 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-ϵ,1+ϵ){\hat{A}}_{j,k}\right)\right],$$

${\hat{A}}_{j,k}=q(s_j)-{\mu }_t$（序列级归一化）。这融合 q 值正则与策略优化，退化为 DAPO 时忽略树结构。

实验：SOTA 性能与效率跃升

基于 Nemotron-Research-Reasoning-Qwen-1.5B v2 和 DeepMath-103K 数据集，在 AIME24/25、AMC23、MATH 等基准上评估（Pass@1, n=32）。表 1 显示 DeepSearch-1.5B 平均准确率 62.95%，超越 Nemotron v2 的 61.70%（提升 1.25%），尤其在 AIME24（53.65% vs 51.77%）和 AMC（90.39% vs 88.83%）。

效率分析（表 2）更亮眼：延长训练 1875 步耗 1883.2 GPU 小时仅达 62.02%，而 DeepSearch 仅 50 步用 330 GPU 小时即超之（5.7× 效率）。图 2 展示训练动态：DAPO 线性缓慢，DeepSearch 高效陡峭，验证探索优于 brute-force。

结语：探索驱动的 RLVR 新范式

DeepSearch 不仅解决了 RLVR 的探索瓶颈，还开辟了将训练镜像推理的路径。它提醒我们：AI 推理的未来在于算法创新，而非单纯规模扩张。模型已在 Hugging Face 开放（https://huggingface.co/fangwu97/DeepSearch-1.5B），欢迎开发者探索。未来，可扩展至代码生成或多模态推理，值得持续关注。

DeepSearch 框架：MCTS 与 RLVR 的深度融合——以一个简单数学题为例

在上一篇文章中，我们概述了 DeepSearch 如何通过蒙特卡罗树搜索（MCTS）破解 RLVR（强化学习与可验证奖励）的探索瓶颈。今天，我们深入框架的核心：将 MCTS 直接嵌入 RLVR 训练循环，实现从“盲目试错”到“系统探索”的转变。对于初学者，这就像给 AI 一个“思维导图”，帮助它一步步规划推理路径；对于专家，它提供了全局前沿选择和细粒度 q 值传播的数学优雅设计。别担心，我们会用一个通俗的数学例子——“一个数加上它的一半等于 15，求这个数”——来模拟整个过程，让抽象概念落地。公式会简单解释，确保易懂。

框架回顾：为什么 MCTS 能“拯救” RLVR？

传统 RLVR 训练像扔飞镖：模型 ${\pi }_{\theta }$ 从问题 $x$ 直接生成有限路径（rollout），用验证函数 $V$ 检查正确性（$V=1$ 表示对，$V=0$ 表示错）。但路径太少，容易错过关键分支，导致训练后“高原”——多投几镖也难中靶心。

DeepSearch 的创新在于：用 MCTS 建一棵“推理树” $T$，根节点是问题 $x$，每个子节点 $s$ 是中间步骤（如“设这个数为 $y$”）。树路径 $t=x\oplus s_1\oplus \cdots \oplus s_{\text{end}}$ 形成完整轨迹。从树提取轨迹集 T={t1,…,tn}\mathcal{T} = \{t_1, \dots, t_n\}T={t1​,…,tn​}，用于 RLVR 优化。不同于推理时才搜树，这里训练时就搜，确保模型学到“路径智慧”。

迭代包括：扩展（生成候选）、选择（挑最佳节点）、备份（传播奖励）和自适应训练。全局前沿选择取代传统根到叶遍历，避免浪费计算。接下来，用例子走一遍。

例子：解决“一个数加上它的一半等于 15”

假设问题 $x$：“一个数加上它的一半等于 15，求这个数。”（正确解：设 $y$ 为数，则 $y+y/2=15\to 1.5y=15\to y=10$。）模型 ${\pi }_{\theta }$ 是 1.5B 参数的推理 LLM，最大深度 $d_T=4$（限 4 步推理），每步生成 $n=3$ 候选。验证 $V$ 用简单求解器检查最终答案。

步骤 1: 扩展（Expansion with Entropy-Based Guidance）

从根 $x$ 开始，第 1 步观察 $o_1=x$，${\pi }_{\theta }$ 生成 3 候选 $s_{1,j}$：

• $s_{1,1}$: “设这个数为 $y$。”
• $s_{1,2}$: “这个数是 10。”
• $s_{1,3}$: “加一倍是 30。”（错分支）

重复扩展：对每个 $s_{1,j}$ 生成下一步，直到 $d=4$ 或答案。假设第 1 迭代 $k=1$，生成终端集 $S_{\text{end}}^{(1)}$ 有 6 个（树枝展）：

• 正确：$s_{\text{end,1}}$ (“$y=10$”，$V=1$）。
• 错误/不完整：其余 5 个（如直接猜 20，$V=0$）。

分区：
Scorrect(1)={s∈Send(1)∣V(s)=1},Sincorrect(1)={s∈Send(1)∣V(s)=0}. S_{\text{correct}}^{(1)} = \{s \in S_{\text{end}}^{(1)} \mid V(s)=1\}, \quad S_{\text{incorrect}}^{(1)} = \{s \in S_{\text{end}}^{(1)} \mid V(s)=0\}. Scorrect(1)​={s∈Send(1)​∣V(s)=1},Sincorrect(1)​={s∈Send(1)​∣V(s)=0}.
这里 $S_{\text{correct}}^{(1)}$ 非空，用正确轨迹；若空，则选低熵负例：
$$s_{\text{neg}}^{\ast }=\arg \underset{s\in S_{\text{incorrect}}^{(1)}}{\min }\bar{H}(t(s)),$$
$\bar{H}(t(s))=\frac{1}{|t(s)|}{\sum }_{i}H({\pi }_{\theta }(s_i|o_i))$ 是平均轨迹熵（$H$ 测模型“犹豫度”，低熵=自信错）。解释：熵像“困惑指数”，选“模型最确定却错”的路径训它，避免纠结的模糊例。

步骤 2: 启发式分数备份（Heuristic Score Backup）

选 $t^{\ast }$（这里正确轨迹：$t^{\ast }=x\oplus$ “设 $y$” $\oplus$ “$y+y/2=15$” $\oplus$ “$1.5y=15$” $\oplus$ “$y=10$”）。沿 $t^{\ast }$ 更新 q 值（奖励信号）。

初始 $q^{(0)}(s_i)=0$。终端 $q(s_{\text{end}})=+1$（正确）。迭代 $m$ 次更新：
$$q^{(m)}(s_i)=q^{(m-1)}(s_i)+\gamma (i,l)\cdot q^{(m)}(s_{\text{end}}),$$
时序衰减 $\gamma (i,l)=\max \left(\frac{i}{l},0.1\right)$（$i$ 当前步，$l$ 终端步；近终端权重高）。例如，$l=4$，第 3 步 $i=3$，$\gamma =\max (3/4,0.1)=0.75$。

约束版（保正确路径正 q）：
$$q^{(m)}(s_i)=\{\begin{array}{ll}{q}^{(m-1)}(s_i)+\gamma (i,l)\cdot q^{(m)}(s_{\text{end}})& \text{若符号一致},\\ \gamma (i,l)\cdot q^{(m)}(s_{\text{end}})& \text{若终端正，重置},\\ q^{(m-1)}(s_i)& \text{否则，保持正}.\end{array}$$
结果：$q(s_{\text{end}})=1$，$q(s_3)=0.75$，$q(s_2)=0.5$ 等。解释：像“信用链”，终端成功“拉高”上游节点，但衰减防早期步过度乐观；约束避负污染，确保“设 $y$” 得正反馈。

步骤 3: 混合选择策略（Hybrid Selection Strategy）

备份后，选下一扩展节点。

• 局部选择（兄弟比）：扩展 $s_{1,1}$ 时，3 候选用 UCT：
  $$UCT(s)=Q(s)+\lambda \sqrt{\frac{\ln N_{\text{parent}}(s)}{N(s)}},$$
  $Q(s)=q(s)/N(s)$（平均奖励），$\lambda$ 平衡利用（高 Q）和探索（低访 N）。选“设 $y$” 因 Q 高。

• 全局前沿选择：前沿 F={s∣F=\{s \midF={s∣ 无子、未完、$d(s)<4\}$。优先 $F(s)={\lambda }_1\tanh (Q_{\text{parent}}(s))+{\lambda }_{2}H({\pi }_{\theta }(s|o))+{\lambda }_3\sqrt{d(s)/d_T}$（质量+不确定+深度奖金）。选 $s^{\ast }=\arg \max F(s)$，如第 2 步“$y+y/2$”因父 Q 高、熵中（需探索）。

解释：局部如“家族投票”，全局如“全城竞选”——避陷一枝，广搜树。

重复 K=100 次迭代，建完整树。

步骤 4: 自适应训练（Adaptive Training with Replay Buffer）

树 $\mathcal{T}$ 后，迭代过滤硬题集 Dhard(i+1)={x∈Dhard(i)∣Pass@1@K(x,πθ(i))<0.25}D_{\text{hard}}^{(i+1)} = \{x \in D_{\text{hard}}^{(i)} \mid \text{Pass@1@K}(x, \pi_\theta^{(i)})<0.25\}Dhard(i+1)​={x∈Dhard(i)​∣Pass@1@K(x,πθ(i)​)<0.25}（K=4，难题留）。缓存正确 $t_{\text{correct}}$ 到缓冲 R，下轮若有，用 $t_{\text{cached}}\cup$ 少量 rollout；否则全 MCTS。

Tree-GRPO 优化：
先软裁剪 $q(s_j)=\tanh (q^{(k_{\max })}(s_j)/1)\cdot 1$（防爆炸，保梯度）。

目标：
$$J(\theta )=\mathbb{E}\left[\frac{1}{|s_j|}\sum _k\min \left({\rho }_{j,k}{\hat{A}}_{j,k},\text{clip}({\rho }_{j,k},1-{ϵ}_{\text{low}},1+{ϵ}_{\text{high}}){\hat{A}}_{j,k}\right)\right],$$

$\rho ={\pi }_{\theta }/{\pi }_{\text{old}}$（重要比，防漂移），${\hat{A}}_{j,k}=q(s_j)-{\mu }_t$（优势，${\mu }_t$ 树均奖励，序列归一防长文）。解释：像“剪刀优化”，$\min$ 和 $\text{clip}$ 稳更新，q 导路径学，训模型偏好高 $\hat{A}$ 步。

一轮后，${\pi }_{\theta }$ 更懂“设变量”路径。多次迭代，准确升。

启示：从例子看框架威力

这个小题模拟了 DeepSearch 如何转“运气猜”为“结构搜”：扩展广生分支，选择精挑路径，备份准传奖励，训练智用缓存。实验中，它让 1.5B 模型在 MATH 等题上达 62.95%——非堆计算，而是聪明探索。

框架不止数学：可推代码调试或逻辑谜题。开源在 Hugging Face，试试建你的“推理树”！浅看，它教 AI“多想想再答”；深究，混合选择和 Tree-GRPO 是 RL 新范式。欢迎讨论你的例子。

后记

2025年10月4日于山东，在grok 4 fast辅助下完成。