BES 让语言模型多了一条搜索路径

01 / 论文简介

问题与挑战
- 当前主流采样方法（Best-of-N、Tree Search）存在：
  1. 验证信号稀疏；
  2. 候选解受限于模型自身分布，难以探索低概率区域。
BES 方法
- 前向搜索（Forward Search）：通过扩展和四种演化操作（Combination、Deletion、Translocation、Crossover）生成候选解。
- 后向搜索（Backward Search）：将任务递归分解为子目标，为前向搜索提供密集反馈。
- 理论证明：演化操作能突破信息熵壳（entropy shell）限制；后向分解可指数级减少找到正确答案所需样本数。
演化操作
- Combination：合并两个候选轨迹的不同后缀；
- Deletion：删除轨迹中某一步；
- Translocation：替换轨迹中某一步；
- Crossover：交叉两个轨迹的片段。
实验与结果
- 逻辑推理（Knights-and-Knaves）和 多跳推理（MuSiQue）任务上，BES显著优于 GRPO 和 Tree-GRPO。
- 开放问题求解（Circle Packing, Heilbronn Convex）上，BES比现有开源框架表现更稳定，平均和最优目标值更好。
- 案例研究展示，translocation操作能将部分正确推理从一个分支转移到另一个分支，生成最终正确答案。
理论分析
- Shell Confinement：扩展搜索受限于典型轨迹集；
- Shell Escape：演化操作能生成超出熵壳的轨迹；
- Bidirectional Search：后向分解可将多目标问题从乘法级别概率提升为子目标收集问题，实现指数加速。
潜在局限
- 需要明确的目标奖励信号；
- 后向搜索依赖模型分解能力，弱模型能力有限；
- 实验中仅测试了小型模型（最高8B参数）。

02 / 追问

BES 到底是个啥

BES = Bidirectional Evolutionary Search，双向演化搜索

通常，模型在寻找 S->T 答案的时候，每次将在候选步骤中选择一个或者几个最“优”的步骤，往前迭代寻找答案，最终形成一个树形轨迹。而 BES 则借用了 meet in the middle 的思想，从 S, T 两边同时进行搜索。

具体的，BES 将搜索过程拆成两步：

第一，从前往后迭代当前解

模型会从当前解开始，生成很多候选解，也就是不同的推理路径，这个叫做 forward search，即前向搜索

第二，从后往前拆分目标

模型从后往前将原问题拆成更小，更容易检查的子目标，称之为 backward search，后向搜索。这样，即使某个答案没有完全做对，他也可能完成了一个子目标，对到达最终答案有贡献。而这里的“贡献”，就为前向搜索提供了“哪一步有用”的信息，从而能基于此构建更好的解。

前向迭代：像进化一样前进

在每轮前向迭代中，不是单纯的往前走一步，而是对已有的解做一些特殊的操作，称之为“演化操作”：

操作	解释
Expansion	接着当前思路继续写
Combination	把两个答案的有用部分合并
Deletion	删除一个可能有问题的步骤
Translocation	把一个答案中的某一步移植到另一个答案里
Crossover	像基因交叉一样，把两个答案的前后段拼接

所以 BES 的 “Evolutionary” 不是说模型真的进化了，而是说它用类似遗传算法的方式，对答案片段进行重组，从而让迭代多一些随机性。

后向搜索：将大目标拆成小目标

普通搜索中，很多问题只有对 / 错，导致反馈过于稀疏，无法有效的指导前向迭代。比如做一道复杂推理题，你只知道它错了，但并不知道错在哪里，那就无法快速找到正确的解题路径———这个时候还是让老师出场吧。

BES 就充当了老师的作用，他从正确答案开始倒推，将最终答案分为几个小分支。如果前向推理过程中遇到了这些分支，便能获得“部分分”。将多个得分路径综合起来，就更容易找到解题方法。

BES 的目标是让模型不要只靠一次次完整采样，也不要只像树搜索那样沿着单一路径继续扩展，而是利用已有候选答案中的局部有效信息（后向搜索），通过重组、删除、移植、交叉等方式（演化），构造出模型原本很难直接生成的候选解。

总而言之，BES 的本质是：一种把“目标分解 + 候选解重组 + 搜索反馈”结合起来的 LLM 搜索框架。

BES 解决的核心问题是什么

前向迭代的结果被熵壳（entropy shell）限制
反馈过于稀疏，中间过程没有足够信号

前向演化：负责“跳出熵壳”

由于自回归模型的性质，当模型做 Expansion-only 迭代，一步步按自身分布往后生成时，会被困在模型的典型轨迹区域里。这个区域就是所谓的熵壳（entropy shell）。直观上，模型最容易生成的是那些符合自己既有分布的路径，而复杂问题的正确解法可能恰好在低概率区域。

于是，BSE 就利用四种演化操作（Combination、Deletion、Translocation、Crossover），来打破单条轨迹的自回归依赖。它不是等模型自然生成完整低概率路径，而是把多个候选轨迹中的片段重组出来，从而构造出超出这个典型壳边界的候选。

后向搜索：提供反馈

演化操作本身并不保证新轨迹是正确的，但 BES 通过 Backward Score 给每个新轨迹打分：

如果新轨迹在当前子目标树上覆盖了更多子目标 → 得分高 → 未来被选中概率高
如果新轨迹破坏了关键逻辑 → 得分低 → 被自然淘汰

BES 成立的条件是什么

如果是随机乱演化，那么将正确的低概率的路径拼出来的概率份反而更低。如果 BES 是“随机拼接”，大部分拼出来的东西都是废的。但 BES 的关键不是“随机拼出正确答案”，而是将

一次性生成完整正确路径

转化为

分别找到若干局部有用片段 -> 用子目标评分识别它们 -> 有偏地选择互补片段 -> 重组 / 修复 / 扩展

这就是 BES make sense 的核心数学直觉：

局部正确性比全局正确性更容易出现；如果能检测局部正确性，就可以把局部正确性重新组合。

当然，这个想法不是无条件成立。它 make sense 需要几个前提：

第一，问题必须有可分解结构。 如果任务没有清晰子目标，或者正确性高度依赖整体风格，BES 就没那么有效。

第二，局部片段要能被识别。 如果 verifier 只能判断最终答案，完全看不出中间片段好坏，那 BES 的优势会下降。

第三，片段要有一定可组合性。 比如多跳问答、数学推理、程序搜索、规划任务比较适合；纯文学创作、主观审美任务就不一定适合。

第四，重组后要能被修复或继续扩展。 尤其是代码任务里，论文也不是简单做 token 拼接，而是让 LLM 根据 combination / translocation / crossover 指令重写程序，因为直接拼代码通常会坏掉。

这篇文章的核心贡献是什么

BES 把搜索过程中分散出现的局部有效信息，通过后向子目标评分识别出来，再用演化重组改变候选生成分布，从而突破 expansion-only 搜索的熵壳限制。