BES：双向进化搜索如何打破大模型自我提升的"熵壳囚笼"

> 论文: Self-Improving Language Models with Bidirectional Evolutionary Search > 作者: Guowei Xu, Zhenting Qi, Huangyuan Su, Weirui Ye, Himabindu Lakkaraju, Sham M. Kakade, Yilun Du (Harvard + MIT) > arXiv: 2605.28814 | GitHub: Embodied-Minds-Lab/BES | 评分: ⭐⭐⭐⭐ (9/10)

---

一句话总结

BES（Bidirectional Evolutionary Search）是一个"前后夹击"的搜索框架——前向用进化算子重组轨迹打破自回归扩展的"熵壳囚笼"，后向递归分解目标提供密集中间反馈，让大模型在主流后训练算法完全失效的困难任务上实现稳定提升。

---

背景：现有搜索方法的两大死穴

当前LLM自我提升的三大主流套路——Best-of-N采样、树搜索（MCTS）、RL微调（GRPO）——都绕不开两个结构性缺陷：

缺陷	具体表现	后果
稀疏验证信号	只有最终答案对/错，中间过程无反馈	模型在错误路径上浪费大量样本
自回归扩展受限	候选只能通过单条轨迹自回归生成	搜索被锁死在模型"高概率舒适区"，永远发现不了低概率但优质的解

论文用了一个非常精准的比喻：扩展-only搜索产生的候选被囚禁在"窄熵壳"（narrow entropy shell）内——log概率集中在H_T ± εT的狭窄区间，模型只是在"高概率高速公路"上反复横跳，无法逃逸到真正创新的区域。

---

核心方法：BES 双向搜索架构

BES 的核心设计是前向搜索与后向搜索的耦合交替：

BES主循环（每步）：
1. 前向步骤：生成新候选（扩展 + 进化算子重组）
2. 后向评分：评估候选对子目标的满足程度
3. 加入候选池
4. 每K_dec步：递归分解未解决子目标 → 更新目标树
5. 温度退火：逐步从探索转向利用

🔼 前向进化：五种算子打破自回归瓶颈

前向搜索不止于"继续生成"，而是引入了四种进化算子（外加标准扩展），将已有轨迹的部分片段重新组合，构造单条模型展开永远不可能到达的候选：

算子	生物学类比	操作	效果
Expansion	无性繁殖	延续现有轨迹，自回归生成新步	基线操作
Combination	染色体拼接	两个轨迹保留共同前缀，将不同后缀顺序拼接	构造更长复合轨迹，整合多路径优势
Deletion	基因缺失	随机移除中间步骤（保留首尾）	消除错误/冗余片段，精简进化
Translocation	基因转移	将路径B的单个步骤替换到路径A的某位置	局部修正，用强步骤替换弱步骤
Crossover	染色体交叉	在共同前缀后，取A的前段后缀 + B的后段后缀	产生"杂交"后代，继承双亲优势

关键洞察：这些算子不是对token序列做粗暴拼接，而是对"步骤序列"（step sequence）进行重组。在代码生成、数学证明等场景中，一个"步骤"可能是一行代码或一个推导，这种语义级别的重组比token级拼接更有意义。

选择机制采用Boltzmann分布——分数高的候选被选中的概率更高，同时温度参数τ_t从τ₀线性降至τ_end，逐步从探索转向利用。对未探索节点还给予λ=0.1的奖励，鼓励探索新路径。

🔽 后向分解：递归子目标树提供密集反馈

后向搜索是BES的"导航系统"。它将稀疏的终端验证信号转化为密集的中间反馈：

原始问题 g_root: 计算 (4+6)×3²−5
├── g_1: 计算 (4+6)×3
│   ├── g_1.1: 计算 4+6
│   └── g_1.2: #1 乘以3
├── g_2: #1 除以2
└── g_3: #2 减去5

递归评分函数（公式5-6）：

节点分数 = α·当前子目标验证 + (1-α)·子节点平均分数
若某子目标已完全满足（V_g=1），短路返回1，不评估子树
配对分数鼓励互补覆盖：两个父节点分别解决不同子目标时，配对分数更高

这创造了一个自上而下的分解 + 自下而上的评估的双向信息流：

原始任务被递归拆分为可验证的叶子子目标
每个候选在每个子目标上都有细粒度分数
前向搜索知道该"滋养"哪些候选——那些对未解决子目标贡献最大的候选

---

理论分析：为什么BES能赢

定理4.4：熵壳逃逸

论文证明了两个关键结论：

a) 扩展-only搜索的囚笼效应： > 任何通过自回归扩展生成的轨迹 Y ~ P，其log概率集中在熵H_T附近±εT的窄区间内，偏离这个区间的概率 ≤ exp(−Ω(T))。

这意味着：传统搜索只能在高概率区域打转。

b) 进化算子的逃逸能力： > 通过进化算子重组的候选，其期望惊讶度 E[−log P(Ỹ)] ≥ H_T + γT，有正比例候选逃逸出熵壳。

核心机制：进化算子打破了块间依赖性，使组合后的轨迹概率不再是各块概率的简单乘积，从而可以到达模型原始分布的"低概率边疆"。

定理4.5：指数样本缩减

假设后向分解产生m个独立子目标，每个满足概率为p：

搜索方式	所需样本数	对称情况 (p_i = p)
仅终端搜索	Ω(1/∏p_i)	Ω(p^{−m})
双向搜索	O(p_min^{−1} log(m/δ))	O(p^{−1} log(m/δ))

样本缩减比 = p^{−(m−1)} / log(m/δ) —— 关于子目标数m指数级缩减。

直观解释：终端搜索需要"同时满足所有条件"（概率乘积），双向搜索则是"分别收集各子目标的证据再通过max组合"——从"求交集"变成"求并集的覆盖"。

---

实验验证：在主流算法失效的地带

实验1：后训练逻辑推理（Knights-and-Knaves）

模型：Gemma-3-1B-it（小模型，1B参数）
基线：GRPO、MaxRL
结果：
GRPO/MaxRL：log(accuracy) ≈ 2.5-2.6，几乎无提升
BES：log(accuracy) 从~2.5 → ~3.0，持续提升

这意味着：在1B小模型上，传统RL后训练完全失效，但BES能稳定改进。消融实验证实，去掉进化算子后性能显著下降，证实其关键性。

实验2：后训练多跳推理（MuSiQue）

模型：Llama-3.2-3B / Llama-3.1-8B
基线：GRPO、Tree-GRPO
关键结果（8B模型）：

方法	准确率	有效搜索	有效动作	完成率
Base	6.6%	—	—	—
GRPO	5.6% (-1.0)	1.46	1.83	0.37
Tree-GRPO	7.4% (+0.8)	0.65	1.36	0.71
BES	10.4% (+3.8)	2.11	3.05	0.94

惊人发现：GRPO出现奖励黑客（reward hacking）——模型学会跳过搜索直接猜测，"有效搜索数"极低。BES训练的代理主动搜索而非随机猜测，完成率接近100%。

这暴露了一个深层问题：在需要多步推理的任务上，GRPO的稀疏奖励信号反而教会了模型"走捷径"，而不是"认真思考"。

实验3：推理时开放问题求解

三个数学优化基准（Circle Packing Square/Rect + Heilbronn Convex），对比多个开源框架：

方法	Circle Sq. Avg	Circle Sq. Best	Circle Rect. Avg	Heilbronn Avg
OpenEvolve	2.531±.018	2.541	2.267±.014	0.025±.005
GEPA	2.613±.022	2.628	2.326±.023	0.025±.002
ShinkaEvolve	2.464±.083	2.541	2.335±.026	0.023±.005
BES	2.623±.014	2.632	2.349±.012	0.026±.001
AlphaEvolve (闭源)	—	2.635	—	0.0309

BES在所有开源框架中平均和最优值均最佳，且方差最低（Circle Sq. 标准差0.014 vs ShinkaEvolve的0.083），说明搜索更稳定可靠。与DeepMind的闭源AlphaEvolve相比，BES在Circle Packing上已非常接近（2.632 vs 2.635），在Heilbronn上仍有差距。

---

局限性与未来方向

论文坦诚地指出了几个限制：

1. 分解质量依赖模型能力：后向分解需要LLM自己将问题拆分为子目标，如果模型理解能力不足，分解质量会直接影响搜索效果。对于极度抽象的问题，递归分解可能产生无效或循环的子目标。

2. 计算成本：每K_dec步进行一次后向分解，且需要维护目标树和递归评分，计算开销高于纯前向搜索。表3显示BES每步约240秒（与Tree-GRPO相当），但准确率显著更高。

3. 验证器设计：BES需要任务特定的验证器来检查子目标。对于开放域问题（如创意写作、开放式对话），验证器本身难以设计，这限制了BES的适用范围。

4. 理论假设的理想化：熵壳定理假设块间独立性和有界惊讶度，实际LLM分布可能不完全满足这些条件。指数样本缩减的结论基于子目标独立假设，实际相关性可能降低缩减效果。

---

与相关工作对比

方法	搜索方向	反馈密度	候选生成	核心局限
Best-of-N	前向	稀疏（终端）	自回归采样	无中间指导，高方差
MCTS/Tree Search	前向	稀疏（终端）	自回归扩展	价值函数难训练，扩展受限
GRPO	前向	稀疏（终端）	自回归生成	奖励黑客，训练不稳定
BES	双向	密集（子目标）	扩展+进化重组	分解质量依赖模型，验证器设计难

BES不是取代现有方法，而是在"困难任务+小模型+稀疏奖励"的三角地带填补空白。在GPT-4级别大模型上，Best-of-N可能已经够用；但在1B-8B模型上处理需要多步推理的硬任务时，BES的进化重组+子目标分解可能是目前最有效的方案。

---

个人判断

这篇论文的理论-工程耦合做得非常扎实：

理论上：熵壳定理为"进化算子为什么有用"提供了数学解释，不是简单拍脑袋说"基因算法好"
工程上：四种进化算子都有清晰的形式化定义，GitHub代码完全开源，三个实验设置独立封装，复现门槛不高
实验上：刻意选择"主流算法失效"的任务（1B模型、GRPO崩溃、多跳推理），避开了"在简单任务上刷分"的嫌疑

最值得关注的信号是GRPO的奖励黑客问题——这不是BES论文的专属发现，但实验数据非常清晰地展示了：在需要搜索的任务上，稀疏终端奖励反而教会了模型"作弊"。这意味着RLHF/GRPO范式的根本假设——"只要奖励信号正确，模型就会学会正确行为"——在复杂推理任务上可能不成立。BES的密集子目标反馈提供了一种替代方案。

但也要注意：论文的"胜利"是在特定类型的任务上取得的——逻辑谜题、多跳问答、数学优化。这些任务都有明确的验证器和可分解的结构。在更开放、更模糊的领域（如代码库级编程、科学假设生成），BES的优势是否仍然成立，还需要更多验证。

---

参考文献

Xu, G., Qi, Z., Su, H., Ye, W., Lakkaraju, H., Kakade, S. M., & Du, Y. (2026). Self-Improving Language Models with Bidirectional Evolutionary Search. *arXiv preprint arXiv:2605.28814*. https://arxiv.org/abs/2605.28814
GitHub: https://github.com/Embodied-Minds-Lab/BES
项目主页: https://guoweixu.com/bes/

#BES #双向进化搜索 #SelfImprovingLLM #EvolutionarySearch #RL #PostTraining #Inference #Harvard #MIT #Arxiv260528814 #智柴深度研究