当语言模型学会犯错和改正：搜索流(SoS)方法解析
引言
语言模型的能力日新月异，但它们在执行复杂规划任务时仍面临着明显的局限。这是因为大多数训练数据只展示了最终的"正确答案"，而非解决问题的完整过程。想象一下，如果我们只能看到数学题的最终答案，而从不知道解题过程中的尝试、错误与修正，我们能真正学会解题吗？斯坦福大学、MIT和哈维穆德学院的研究团队在论文《Stream of Search (SoS): Learning to Search in Language》中提出了一个新颖观点：语言模型需要学习"如何搜索"，包括探索、错误和回溯的完整过程。
研究问题：自回归模型的规划弱点
研究者指出，基于Transformer的自回归模型存在两个核心问题：
- 错误累积：单个错误可能导致后续步骤性能越来越差，形成雪球效应。
- 预见任务难度：模型难以预测其行动在多步之后的后果。
这两个问题源于语言模型缺乏搜索和回溯能力。虽然近期有研究将语言模型与符号搜索算法结合，但这些方法只是在推理阶段辅助语言模型，没有让语言模型真正学会搜索。研究团队认为，如果语言模型能在训练过程中学习搜索，它们可能能够发现更灵活的搜索策略，从而更好地应对复杂规划挑战。
创新方法：搜索流(Stream of Search)
研究团队提出了"搜索流"(SoS)方法，将搜索过程表示为序列化的文本字符串。这种表示保留了搜索的关键元素，包括：
- 当前状态：正在探索的状态
- 状态扩展：基于当前状态生成新状态
- 移动决策：在搜索树中的移动
- 回溯操作：放弃当前路径，返回之前的节点
- 目标检查：验证是否达到目标状态
这种表示方法将搜索过程"翻译"成语言形式，使语言模型能够学习搜索的核心组件和策略。下面是SoS方法表示搜索的示例：
Current State: 50:[39, 66, 33, 13], Operations: []
Exploring Operation: 66-13=53, Resulting Numbers: [39, 33, 53]
Generated Node #0,0: 50:[39, 33, 53] Operation: 66-13=53
Moving to Node #0,0
Current State: 50:[39, 33, 53], Operations: ['66-13=53']
研究团队选择了"倒计时"(Countdown)游戏作为测试案例，这是一个需要将输入数字通过算术运算组合达到目标数字的问题。
数据集构建
研究者构建了一个多样化的搜索轨迹数据集：
-
搜索策略：结合12种不同的搜索策略
- 深度优先搜索(DFS)
- 广度优先搜索(BFS)，带有不同的广度限制b∈[1,2,3,4,5]
- 两种启发式函数：求和启发式和乘法启发式
-
数据集规模：
- 500,000个搜索轨迹
- 其中约57%(285,000个)成功找到解决方案
- 目标数字范围从10到100
-
测试集划分：
- 已见目标+新输入：评估泛化到新输入组合的能力
- 未见目标+新输入：评估泛化到全新问题的能力
实验设计与结果
1. 搜索流vs最优路径训练
研究者比较了两种训练方法：
- 最优路径(OP)：仅在正确解决步骤上训练
- 搜索流(SoS)：在完整搜索过程（包括错误和回溯）上训练
| 训练方法 | 已见目标+新输入 | 未见目标+新输入 |
|---|---|---|
| 最优路径(OP) | 25.73% | 24.86% |
| 搜索流(SoS) | 51.27% | 49.00% |
| 符号算法平均 | 53.92% | 51.65% |
搜索流方法显著优于最优路径训练，接近专门设计的符号搜索算法的性能，尽管SoS模型面临更复杂的挑战：它必须同时学习状态转换和算术运算。
2. 策略改进方法评估
研究者使用两种策略改进方法进一步优化SoS模型：
- STaR：自我训练推理器，通过筛选正确解决方案进行自我改进
- APA：优势诱导策略对齐，使用强化学习优化搜索策略
| 模型 | 已见目标+新输入 | 未见目标+新输入 |
|---|---|---|
| SoS基础 | 51.27% | 49.00% |
| SoS+STaR | 55.59% | 53.34% |
| SoS+APA | 56.52% | 54.23% |
两种策略改进方法都显著提高了模型性能，特别是APA方法。
3. 错误分析
对生成轨迹的错误类型进行详细分析：
| 模型 | 算术错误 | 格式错误 | 探索错误 | 其他错误 |
|---|---|---|---|---|
| SoS基础 | 2.25±0.10 | 0.01±0.00 | 0.01±0.00 | 0.02±0.01 |
| SoS+STaR | 1.93±0.08 | 0.01±0.00 | 0.02±0.00 | 0.07±0.01 |
| SoS+APA | 0.67±0.04 | 0.01±0.00 | 0.01±0.00 | 0.02±0.00 |
APA方法显著减少了算术错误，从每轨迹约2.3个错误减少到约0.7个错误。
4. 搜索效率分析
评估模型找到正确解决方案所需的平均搜索步骤：
| 模型 | 已见目标+新输入 | 未见目标+新输入 |
|---|---|---|
| SoS基础 | 75.04±0.64 | 81.75±0.64 |
| SoS+STaR | 66.18±0.64 | 72.25±0.65 |
| SoS+APA | 64.73±0.65 | 70.85±0.66 |
策略改进显著提高了搜索效率，减少了达到目标所需的状态数量。
5. 解决新问题能力
评估改进模型解决原始符号算法无法解决问题的能力：
| 模型 | 解决未解决问题比例 | 解决困难问题比例 |
|---|---|---|
| SoS基础 | 28.9% | 1.5% |
| SoS+STaR | 36.2% | 3.9% |
| SoS+APA | 35.7% | 4.1% |
改进后的模型能够解决约36%之前未解决的问题，展示了超越原始训练数据中符号算法的能力。
更广泛的意义与未来方向
这项研究的意义远超倒计时游戏问题，它揭示了语言模型学习复杂规划能力的新途径：
-
符号推理能力的内化：研究表明，结构化搜索、启发式评估和世界模型构建等符号推理的核心特征可以在序列建模范式内实现。
-
错误的价值：展示了错误和回溯对学习过程的重要性，这可能启发未来AI训练方法的设计。
-
自我改进的可能性：模型不仅学会了搜索，还能通过自我改进发现新的解决策略，这为AI系统的持续学习提供了新思路。
未来研究方向包括将SoS方法扩展到更复杂的现实问题、整合子目标和分层规划，以及探索搜索能力在不同领域间的迁移性。
结论
该研究揭示了一个关键洞见：要让AI真正掌握解决复杂问题的能力，我们不应只展示成功的最终结果，还需要展示整个过程中的探索、错误和修正。正如人类通过试错学习一样，语言模型也需要"犯错"和"改正"的经验来发展更强大的推理能力。这种方法不仅提高了模型在特定任务上的表现，还为解决自回归模型在规划方面的根本局限提供了新思路。
注：本文是对论文《Stream of Search (SoS): Learning to Search in Language》的解读。该论文由Kanishk Gandhi、Denise Lee、Gabriel Grand等人撰写，发表于2024年4月。