BFS-PO: Best-First Search for Large Reasoning Models¶

会议: NeurIPS 2026
arXiv: 2602.14917
代码: https://github.com/aimagelab/BFS-PO
领域: Reasoning
关键词: 大推理模型, 最佳优先搜索, 强化学习, 思考过度缓解, 链长压缩

一句话总结¶

本文提出面向大推理模型的强化学习算法 BFS-PO，利用基于最大熵回溯的最佳优先搜索策略引导在线探索生成更短且正确的思维链，结合树状分支优势函数，在无需过程奖励模型的前提下同时降低推理长度并提升模型准确率。

研究背景与动机¶

大语言推理模型（LRMs，如 OpenAI o1 和 DeepSeek-R1）通过在推理时展开长思维链（Chain of Thought, CoT）展现出强大的复杂逻辑推理能力。然而，推理时计算扩展往往会诱发极长乃至数千上万 token 的推理序列，引发被称为“过度思考”（overthinking）的严重问题。这不仅带来沉重的计算与内存开销，而且经验证据表明 CoT 长度与推理正确率之间常常存在显著的负相关。在现有的强化学习微调框架（如 GRPO 或 DAPO）中，受损失函数内序列长度归一化机制或负优势惩罚的影响，模型甚至更容易被鼓励生成冗长冗余的负例响应，进一步加剧了过度思考倾向。

现有缓解过度思考的方案大致分为两类，但各具局限。基于监督微调（SFT）的路径（如 TokenSkip、C3oT、A*-Thought）依赖人工或大模型预先构建包含紧凑 CoT 的静态数据集对模型进行蒸馏剪裁，但在有限数据上极易出现过拟合，且多数方法在缩短 CoT 的同时以牺牲模型准确率为代价；而引入长度惩罚项的纯强化学习方法在独立采样策略下往往只能被动施加经验惩罚，缺乏对正确紧凑推理空间的针对性探索引导。另一方面，虽有方法尝试引入树搜索（如 Tree of Thoughts），但通常需要额外的过程奖励模型（PRM）来评估局部步骤，而 PRM 本身需要标注密集局部奖励，计算成本极其高昂。

面对上述矛盾，本文提出了一种无需 PRM 即可在线搜索高质短路径的强化学习探索机制：不再从根节点对每个问题做多次盲目独立的无记忆随机采样，而是将探索过程组织为以“最短且正确”为启发目标的最佳优先搜索（BFS）树。通过识别高熵关键决策 token 实施局部回溯与分支衍生，让模型自身在训练过程中动态自生成逐步压缩且保持严谨的 CoT 样本。核心 idea：将强化学习中的轨迹采样组织为基于最大熵回溯点的最佳优先搜索树，以“正确且最短”为目标引导探索，并提出树结构分支优势函数进行稠密策略优化，实现思考长度压缩与推理准确率的双向提升。

方法详解¶

整体框架¶

BFS-PO 在每个训练样本上构建探索搜索树 \(\mathcal{T}\)。整个流水线包含两个核心阶段：基于当前最短正确解与最大熵回溯节点的树构建阶段（Tree Construction），以及基于分支优势的稠密策略优化阶段（Optimization）。输入为训练问题 \(q\) 及参考答案 \(a^*\)，首先由旧策略采样一组初始解；随后通过 \(K\) 轮最佳优先迭代，动态筛选当前最短且正确的叶子路径，并在该路径上检索信息熵最高的 token 作为回溯决策点展开新的候选分支。在树结构生成完成后，利用基于最终答案的验证器为叶子节点赋予奖励，并通过树节点自底向上递归平均生成内部节点的稠密奖励，最后计算分支优势并使用非对称裁剪的强化学习目标更新策略网络。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入问题与参考答案<br/>(q, a*)"] --> B["初始组采样<br/>独立生成 G 个候选完整解"]
    B --> C["最短正确解筛选<br/>筛选当前最短正确路径 oj"]
    C --> D["最大熵回溯点定位<br/>定位路径上最高熵分支节点 wb"]
    D --> E["局部条件分支扩展<br/>从前缀引出 G 个全新分支并入树 T"]
    E -->|迭代 K 次扩展| C
    E --> F["叶子节点奖励评估<br/>验证器打分结合序列长度软惩罚"]
    F --> G["树结构自底向上聚合<br/>子节点递归平均构建稠密奖励"]
    G --> H["分支优势函数计算<br/>同父节点分支间标准化打分"]
    H --> I["稠密策略优化更新<br/>DAPO 目标更新模型参数 θ"]

关键设计¶

1. 最短正确解筛选与最大熵回溯点定位：在无 PRM 下锁定关键逻辑分叉点

传统树搜索算法高度依赖步骤级过程奖励模型（PRM），不仅训练代价高，且容易在推理链的局部分析上带来奖励黑客（reward hacking）现象。BFS-PO 完全规避了 PRM，仅依靠终局结果验证器 \(v(\cdot)\) 与输出长度 \(|o|\) 联合筛选当前搜索树中最有希望的局部最优解。在已生成的候选路径集合 \(\mathcal{T}\) 中，选取满足结果正确 \(v(o_j, a^*) = 1\) 且长度最短 \(|o_j| \le \min_{o_i \in \mathcal{T}} (|o_i|)\) 的路径 \(o_j\)。

确定基准路径后，算法需要判断从何处切断回溯以生成更精炼的替代方案。根据大模型推理的信息熵特性，低熵 token 主要用于维护自然语言语法与句式连贯，而高熵 token 才是决定逻辑推理走向、算子选择与解题策略的核心决策分歧点。因此，BFS-PO 直接在路径 \(o_j\) 中检索未曾被访问过的最大熵 token 作为回溯点 \(w^b\)：

\[w^b = o_{j, t^*} = \arg\max_{o_{j, t} \in o_j, \, o_{j, t} \notin B} H(o_{j, t})\]

其中 \(H(o_{j, t}) = -\sum_{w \in V} \pi_\theta(w | q, o_{j, \le t}) \log \pi_\theta(w | q, o_{j, \le t})\) 为 token 生成分布的信息熵，\(B\) 为当前样本已使用过的回溯点集合。锁定回溯点后，将从问题到该回溯点的前缀 \((q, o_{j, 1}, \dots, o_{j, t^*})\) 作为全新提示，采样 \(G\) 条全新子链并入搜索树。这种机制引导模型在关键决策点附近反复探索更短更捷径的解题分支，从而让模型自发生成高质量的紧凑思维链数据。

2. 树结构自底向上聚合与分支优势函数计算：将群体标准化拓展至树形局部子空间

GRPO 和 DAPO 是在同一个问题的所有独立生成样本之间计算全局均值与标准差来获取优势，如果将此方法直接套用在搜索树中，由不同深度、不同回溯点派生出的分支混在一起统计，会引入巨大的方差并抹杀局部优秀分支的相对价值。为此，BFS-PO 提出了适配树结构的分支优势函数（Branch Advantage）。

首先，叶子节点（即完整解链）根据最终答案正确性与软超长惩罚计算终端奖励 \(R_i = \pm 1 + R_l(o_i)\)。对于树内的任意非叶子节点 \(w_n\)，其奖励值 \(R(w_n)\) 递归定义为其所有子节点集合 \(C(w_n)\) 的平均收益：

\[R(w_n) = \frac{1}{|C(w_n)|} \sum_{w_m \in C(w_n)} R(w_m)\]

当某个回溯节点 \(w_n^b \in B\) 衍生出包含原始延续与新分支在内的 \(k = G + 1\) 个子分支时，记其子树分支集合为 \(S(w_n^b)\)。对于任意从该回溯点引出的子分支 token \(w_m \in S(w_n^b)\)，其优势值并非对比全树，而是对比该回溯节点所聚拢的局部平均期望与标准差：

\[\hat{A}_m = \frac{R(w_m) - R(w_n^b)}{\sigma(w_n^b)}, \quad \sigma(w_n^b) = \operatorname{std}\left(\{R(w_{m_i}) \mid w_{m_i} \in C(w_n^b)\}\right)\]

通过这种分支优势设计，局部探索不仅获得了自底向上的稠密监督信号，且由于树结构中祖先节点的前缀完全共享，训练阶段可在前向推理与梯度计算中直接复用祖先路径的 KV Cache，使训练吞吐相比独立多链采样的 DAPO 提升了约 1.37 倍。

3. 稠密策略优化更新：结合非对称裁剪与样本长度平衡的强化学习训练

构建完搜索树 \(\mathcal{T}\) 并为每个 token 赋予优势值 \(\hat{A}_n\) 后，算法在整棵树的全部 token 节点上进行策略梯度反向传播。目标函数吸收了 DAPO 的非对称裁剪（Asymmetric Clip）机制与组级 token 归一化特性，避免因序列过长导致的错误奖励失衡：

\[\mathcal{J}_{\text{BFS-PO}}(\theta) = \mathbb{E}_{(q, a^*) \sim \mathcal{D}, \, w_n \in \mathcal{T}} \left[ \frac{1}{|\mathcal{T}|} \sum_{w_n \in \mathcal{T}} \min \left( r_n(\theta)\hat{A}_n, \, \operatorname{clip}(r_n(\theta), 1-\epsilon_l, 1+\epsilon_h)\hat{A}_n \right) \right]\]

其中重要性采样比率定义在历史祖先路径上：

\[r_n(\theta) = \frac{\pi_\theta(w_n \mid q, P(\dots P(w_n)\dots), \dots, P(w_n))}{\pi_{\theta_{\text{old}}}(w_n \mid q, P(\dots P(w_n)\dots), \dots, P(w_n))}\]

参数设置上沿用 DAPO 经过大规模验证的标准超参数（下限裁剪 \(\epsilon_l = 0.2\)、上限裁剪 \(\epsilon_h = 0.28\)），在训练过程中保证策略稳定更新。在推理测试阶段，模型无需运行任何树搜索或回溯，直接以单链贪婪或常规采样方式输出极度凝练且高精度的推理轨迹。

实验关键数据¶

主实验¶

论文在 GSM8K、MATH-500 以及跨域泛化评测集（MMLU-STEM、AIME'25、MINERVA-MATH）上评估了 BFS-PO，基模涵盖 Qwen2.5-3B-Instruct、Llama-3.1-8B-Instruct 和 Qwen2.5-7B-Instruct。核心评测指标包括准确率（Acc.）、平均推理长度（Avg. Len.）以及兼顾精度提升与长度缩减的综合效率指标 Accuracy Efficiency Score（AES）。

基座模型与训练任务	评测数据集 (设置)	方法	Acc. (%) ↑	Avg. Len. ↓	AES ↑
Qwen2.5-3B-Instruct (在 GSM8K 训练)	GSM8K (In-Domain)	Zero-shot SFT TokenSkip DAPO BFS-PO (本文)	83.7 83.4 83.2 85.6 86.2	315 319 263 290 269	0.00 -0.03 0.14 0.15 0.24
Llama-3.1-8B-Instruct (在 GSM8K 训练)	GSM8K (In-Domain)	Zero-shot Tree of Thoughts TokenSkip DAPO BFS-PO (本文)	86.2 74.0 81.1 87.6 87.9	213 385 129 209 189	0.00 -1.51 0.10 0.07 0.17
Qwen2.5-7B-Instruct (在 GSM8K 训练)	GSM8K (In-Domain)	Zero-shot TokenSkip DAPO BFS-PO (本文)	91.4 87.9 91.9 92.3	298 178 277 234	0.00 0.21 0.09 0.24
Llama-3.1-8B-Instruct (在 MATH-500 训练)	MATH-500 (In-Domain) GSM8K (Out-of-Domain) MMLU-STEM (Out-of-Domain) AIME'25 (Out-of-Domain) MINERVA (Out-of-Domain)	DAPO BFS-PO (本文) DAPO BFS-PO (本文) DAPO BFS-PO (本文) DAPO BFS-PO (本文) DAPO BFS-PO (本文)	50.8 50.6 85.8 86.5 61.2 61.7 8.6 13.6 19.1 22.4	497 398 215 199 285 236 804 585 554 468	0.15 0.39 -0.03 0.08 0.44 0.67 1.11 3.71 0.02 0.69

消融实验¶

基于 Qwen2.5-3B-Instruct 和 GSM8K 验证核心组件对性能、推理长度与综合效率的影响：

实验配置变体	扩展轮数 \(K\)	分支优势 (Branch Adv.)	长度软惩罚 (\(R_l\))	Acc. (%) ↑	Avg. Len. ↓	AES ↑	说明与结论
Zero-shot	-	-	-	83.7	315	0.00	未经微调的基础基模 baseline
DAPO (K=0)	0	-	✓	85.6	290	0.15	退化为纯独立采样 DAPO baseline
BFS-PO (K=1)	1	✓	✓	85.9	286	0.17	引入单轮回溯扩展，长度开始收敛
BFS-PO (K=2)	2	✓	✓	86.2	271	0.23	探索步数增加，显著缩短 CoT 并提点
BFS-PO (K=3, 默认)	3	✓	✓	86.2	269	0.24	最佳设定：长度缩短 46 token 且达最高精
w/o BFS	3	✓	✓	86.0	311	0.10	仅按全局高熵回溯、未以最短正确路径为先验，长度显著膨胀
Global Adv.	3	✗	✓	85.7	271	0.22	弃用树状分支归一化改用全树全局池化优势，准确率回落
w/o \(R_l(\cdot)\)	3	✓	✗	86.1	275	0.21	移除 DAPO 长度显式惩罚，性能仍远胜 DAPO，说明收益源自搜索本身

关键发现¶

打破“简短即降精度”的既有困局：传统 CoT 压缩策略（如 TokenSkip、SFT 蒸馏）虽然能极大压减 token 数量（如 Llama-3.1-8B 上 TokenSkip 压至 129 token），但准确率严重失真（从 86.2% 剧降至 81.1%）。BFS-PO 在全基准测试上始终兼得准确率上升与序列显著缩短（例如在 Qwen2.5-7B 上较 Zero-shot 提升 0.9% 精度并节省 64 个 token）。
最佳优先搜索是精简推理链的核心引擎：消融实验 w/o BFS 显示，若脱离“最短正确解”引导、仅凭高熵盲目回溯建树，生成的平均推理长度（311 tokens）与未经优化的基模（315 tokens）几乎无异；唯有在最短正确路径上回溯，才能有效促使模型自生成精炼的 CoT。
极佳的跨域鲁棒性与高难数学攻坚表现：在 MATH-500 上微调的 Llama-3.1-8B 迁移至具有高度挑战性的 AIME'25 时，DAPO 准确率仅为 8.6%（804 tokens），而 BFS-PO 准确率跃升至 13.6%（585 tokens），AES 从 1.11 飙升到 3.71，证明受控探索避免了泛化崩塌。

亮点与洞察¶

以最大熵作为天然的逻辑决策回溯点：无需引入成本高昂、容易过拟合的过程奖励模型（PRM），巧妙借助输出概率分布的信息熵捕获模型真正的逻辑分支点，以极轻量代价实现了树搜索引导。
前缀共享带来的 KV Cache 复用与加速：相比独立随机采样的多路生成，树状拓扑让大量历史祖先路径得以共享，使得训练阶段的前向采样相较 DAPO 实现 1.37× 的显著加速。
启发未来大模型后训练策略：证明了强化学习中的探索策略（Exploration Policy）可以通过结构化启发机制自组织出比随机盲目采样更优质的轨迹数据分布，为后续思考链蒸馏与后训练提供了通用范式。

局限与展望¶

基座模型规模受限：论文验证范围停留在 3B 至 8B 中小规模开源模型，未在 14B、32B 或 70B 及以上超大规模 LRM 上进行万级上下文的全面验证。
超参数 \(K\) 的静态设定：目前每道题目的树扩展次数 \(K\) 均为固定值（\(K=3\)），未能根据输入题目的推理难度动态分配搜索扩展预算（如简单题 \(K=1\)、极难题动态扩至更深）。
多步回溯深度的扩展性：算法当前仅针对一条最优主干进行单节点最大熵回溯，未来可将 Best-First 扩展至更具弹性的蒙特卡洛广义树流（MCTS）与多步回溯框架中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙融合最大熵回溯与最佳优先搜索，摆脱 PRM 实现了免监督的紧凑 CoT 在线强化学习。
实验充分度: ⭐⭐⭐⭐☆ 覆盖 3 个主流模型架构与 5 项数学/STEM 领域基准，主实验、跨域泛化及各模块消融非常详实，若有 14B 以上大模型评测则更佳。
写作质量: ⭐⭐⭐⭐⭐ 数学建模清晰，符号规范，对比实验与图表逻辑链条紧凑严谨。
价值: ⭐⭐⭐⭐⭐ 精准击中当前大推理模型“过度思考”与推理算力膨胀的痛点，兼顾高准确率与低延时，工程落地性极高。