精读：Transformer如何通过RL自主学习搜索

1 论文概览

一句话总结：本文首次从理论上证明，双头Transformer在策略梯度RL和深度课程学习下，可从稀疏终端奖励中自发涌现出随机化深度优先搜索（DFS），且仅在浅层树上训练即可泛化到更深的树。

核心问题：树搜索是智能体推理和决策的核心抽象——智能体必须探索动作、记忆失败、回溯到有前途的替代方案。然而，我们缺乏对Transformer策略如何从RL训练动态中获得搜索能力的理论理解。具体而言：一个仅通过稀疏反馈训练的Transformer，能否在没有专家演示的情况下自主学习搜索？

主要贡献：

1. 构造性证明：构建了一个最小双头Transformer，明确实现随机化DFS——一个注意力头充当内部栈追踪先前动作，另一个检测失败并触发回溯
2. 训练动力学证明：在深度课程学习下，通过策略梯度分析证明相同的DFS机制可从稀疏强化反馈中分阶段涌现，无需任何专家演示
3. 深度泛化：仅在深度-1和深度-2的树上训练后，策略成功运行于更深的完整树上——表明模型内化了DFS的递归结构而非记忆浅层模式
4. 排序DFS：在非均衡目标分布下，折扣回报使策略收敛为”排序DFS”，优先探索高概率分支，将经典best-first搜索启发式与涌现行为连接
5. 机制范式（Mechanistic Normal Form）：识别了Transformer搜索的统一机制范式——注意力头通过专业化分工和协作，从上下文中提取决策相关轨迹并转化为动作选择

2 方法详解

架构/方法概述

论文的研究框架围绕一个精心设计的随机$k$-叉树环境展开，包含三个核心组件：

环境：随机$k$-叉树

• 智能体在随机$k$-叉树上导航，目标是找到隐藏的叶子目标节点
• 智能体仅观测自身的轨迹历史（交互记录），不拥有树的拓扑信息
• 奖励信号为稀疏终端奖励——仅到达目标节点时获得奖励
• 这是一个最小化抽象：保留了”探索-记忆-回溯”循环的核心结构，同时去除了所有外部干扰

模型：双头Transformer

论文构造了一个最小化的双头Transformer架构，精确实现了随机化DFS：

• 注意力头1（轨迹追踪头）：追踪先前的动作选择，功能上等价于DFS中的内部栈。在DFS执行过程中，栈记录当前搜索路径，使得回溯时能正确返回上层节点
• 注意力头2（失败检测头）：检测失败结果（到达叶子但非目标节点），触发回溯行为。当探索某个分支失败后，此头发出”应该回溯”的信号

“One attention head tracks previous actions — functioning as an internal stack — while the other detects failure outcomes and triggers backtracking.” — The Agent Times 对论文的解读

这个设计的关键在于最小性：它隔离了经典树搜索的根本循环——探索-记忆-回溯（explore-remember-backtrack），没有引入任何冗余机制。

训练：策略梯度 + 深度课程学习

• 算法：策略梯度（Policy Gradient），即REINFORCE算法族
• 课程设计：深度递进课程（depth-wise curriculum）——先在深度-1的树上训练，再在深度-2的树上训练，然后暴露给更深的树结构
• 无需专家演示：训练过程中不提供任何专家轨迹或示范数据，仅依赖稀疏终端奖励

关键创新点

1. 从构造性到涌现性的双重论证

论文的论证结构非常独特，分为两个层次：

• 第一层（构造性）：手工构造一个双头Transformer，证明存在一个可以实现DFS的Transformer参数配置（Theorem 1）
• 第二层（涌现性）：证明在策略梯度RL和深度课程学习下，相同的DFS机制可以从随机初始化中自发涌现（Theorem 2-5）

这种”先存在性、后可学习性”的论证路径，在LLM机制可解释性文献中是罕见的。

2. 深度泛化的理论保证

论文证明了DFS机制具有组合性（compositionality）：在深度-1和深度-2的树上习得的探索-记忆-回溯模式，可以直接组合应用到更深的树上。这不是简单的外推，而是因为DFS本身就是递归定义的——深度$d$的DFS是深度$d-1$的DFS的组合。

“The resulting policy exhibits depth generalization: after training only on depth-1 and depth-2 trees, it succeeds on deeper full trees.” — 论文摘要

3. 折扣因子作为搜索效率的归纳偏置

在非均衡目标分布（某些分支更可能包含目标）下，论文证明了折扣回报（discounted return）导致策略收敛为”排序DFS”——优先探索高概率分支。这揭示了一个精妙的对应：

经典搜索	涌现搜索
Best-first search启发式	排序DFS
人工设计优先级函数	折扣因子自动诱导优先级
外部编排搜索顺序	RL奖励塑形自发涌现搜索顺序

4. 机制范式（Mechanistic Normal Form）

论文提出了Transformer搜索的统一机制范式，由三个要素构成：

1. 专业化分工：注意力头分化为轨迹追踪和失败检测两种专门功能
2. 协作提取：头之间协作从上下文中提取决策相关的历史信息
3. 动作转换：提取的信息通过RL训练转化为智能体动作选择

这个范式与机制可解释性（mechanistic interpretability）直接连接——如果搜索在Transformer中可靠地分解为可识别的头专业化模式，则可以验证大规模语言模型是否展现类似内部结构。

与基线方法的区别

论文与现有工作的根本区别在于理论深度：

方法类型	代表工作	搜索来源	理论保证
显式搜索框架	Tree-of-Thought, MCTS	外部工程注入	无
模仿学习	SFT on search traces	专家演示	无
隐式涌现	RL训练推理模型	RL涌现	经验观察
本文	双头Transformer + PG	RL涌现	可证明

3 实验结果

主要指标

论文的核心评估维度包括：

1. DFS涌现率：训练后策略是否实现了DFS行为模式
2. 目标达成率：在随机$k$-叉树上找到隐藏目标的成功率
3. 深度泛化：在深度$d > 2$的树上的成功率
4. 排序DFS收敛性：在非均衡分布下折扣因子对搜索策略的影响

与SOTA的对比

本文的定位是理论基础而非工程方案，因此不直接与LLM推理基准比较。但论文的贡献可与几个关键参照系对比：

vs. Tree-of-Thought / MCTS方法

ToT和MCTS将搜索作为外部模块附加到LLM上——LLM本身不”会”搜索，只是被外部算法调用。本文证明了搜索能力可以通过RL训练内化到Transformer参数中，无需外部搜索框架。

vs. 模仿学习（SFT on expert search traces）

模仿学习需要专家搜索轨迹作为训练数据。本文证明稀疏终端奖励足以诱导DFS涌现——无需任何专家数据。这与Spurious Rewards论文的发现形成对话：如果随机奖励也能提升推理性能，那么稀疏奖励能够诱导搜索能力涌现就不那么反直觉了。

vs. 推理模型的”涌现搜索”

近期的推理模型（如o系列、DeepSeek-R1）确实展现出类搜索行为（自我验证、替代路径探索、回溯），但这些都是经验观察，缺乏理论解释。本文提供了首个可证明的理论框架——注意力头如何专业化分工实现搜索。

消融实验关键发现

论文包含5个定理（Theorem 1-5）、2个命题（Proposition 1-2）、9个引理（Lemma 1-9），形成完整的理论体系：

Theorem 1（构造性定理）：存在双头Transformer参数配置，精确实现随机化DFS。

Theorem 2-3（训练动力学定理）：在深度课程学习下，策略梯度训练使DFS机制分阶段涌现：

• 阶段一：在深度-1树上训练时，模型学会基本的”探索-检测”循环
• 阶段二：在深度-2树上训练时，模型学会”探索-检测-回溯-再探索”的完整循环

Theorem 4（深度泛化定理）：仅在深度-1和深度-2树上训练的策略，成功运行于更深的完整树。

Theorem 5（排序DFS收敛定理）：在非均衡目标分布下，折扣回报使策略收敛为排序DFS。

Proposition 1-2：建立了折扣因子与搜索优先级之间的定量关系。

论文附录A-C包含所有定理的完整证明（约122页），其中附录A.3含8个子节的详细推导，附录B证明命题1-2，附录C证明构造定理和深度泛化定理。

4 个人分析

亮点

1. 论证结构的典范

“先存在性、后可学习性”的双重论证是本文最精彩的设计。构造性证明建立了上界（“Transformer可以做到”），训练动力学证明建立了可达性（“RL可以学到这里”）。这种论证结构可以迁移到其他”涌现能力”的研究中——不限于搜索，还包括推理、规划等。

2. 搜索作为内在能力的范式转换

从”搜索是外部模块”到”搜索是内在能力”的范式转换，直接挑战了当前AI智能体设计的主流思路。如果搜索可以通过RL内化，那么Tree-of-Thought、MCTS等外部搜索框架可能只是通向同一目标的更昂贵路径。

3. 课程学习与组合性的深层联系

深度泛化不是一个偶然发现——它根植于DFS的递归结构。深度$d$的DFS = 深度$d-1$的DFS + 回溯 + 继续搜索。这种组合性意味着课程学习可以从简单组件”搭建”复杂行为，这为复杂推理能力的课程训练提供了理论依据。

4. 折扣因子作为归纳偏置的理论洞见

折扣因子在RL文献中通常被视为技术手段（降低方差、保证收敛），但本文揭示了它作为搜索策略归纳偏置的新角色。仅改变折扣因子，就能系统性地偏置搜索策略——从盲目DFS到有向搜索。这为RL训练中的”奖励设计即架构设计”提供了新视角。

局限性

1. 环境过于简化

随机$k$-叉树 + 稀疏终端奖励，与现实世界智能体任务的差距是显著的：

• 现实任务涉及连续状态空间、部分可观测性
• 多步工具使用产生的奖励信号远比二值目标指示器噪声大
• 现实搜索空间的分支因子和深度不是固定的

论文作者明确将其定位为理论基础而非部署方案，但简化环境是否足以捕捉搜索涌现的本质？这是一个开放问题。

2. 模型规模差距

双头架构远小于生产级Transformer（数百个注意力头）。机制范式是否能扩展到大规模模型？作者承认这是开放问题。如果大规模模型中的搜索机制涉及更复杂的多头协作模式，那么双头范式可能只是”玩具版”。

3. 课程假设过强

深度递进课程是一个强假设——实践中智能体很少遇到按复杂度整齐排列的任务。DFS涌现是否在随机任务排序或对抗性课程下同样成立？论文未讨论这一点。这与Forks in the Road论文的发现形成对比——推理模型中的”岔路口”决策点并非总是有序的。

4. 缺乏与实际推理模型的对标

论文没有验证大规模推理模型（如o系列、DeepSeek-R1）是否实际展现出”轨迹追踪头”和”失败检测头”的分工模式。这使得机制范式的预测力尚未被检验。

对大模型领域的影响

短期影响（6-12个月）：

1. 课程学习设计：深度课程学习的理论有效性可能推动更多”从简单到复杂”的推理训练实践，替代当前的”混合难度”训练
2. 机制可解释性新工具：注意力头专业化分工的发现为检测模型内部搜索能力提供了新探针——可以检查模型是否存在”栈头”和”回溯头”

中期影响（1-2年）：

3. 内化搜索 vs. 外部搜索的路线之争：如果搜索能力可以通过RL内化，那么MCTS/ToT等外部框架的价值需要重新评估——它们可能只是”搜索能力尚未充分训练时的补丁”
4. 折扣因子调优：折扣因子作为搜索效率的归纳偏置，可能成为RL训练超参数调优的新维度

长期影响：

5. 涌现能力的统一理论框架：本文的”构造性 → 可学习性”论证范式可能推广到其他涌现能力（推理、规划、元学习），成为理解LLM涌现的理论基础

5 实践启示

可以借鉴的技术

1. 课程学习作为涌现的脚手架

深度课程学习不仅是训练效率的优化手段，更是能力涌现的必要条件。在实践中，这提示我们：

• 在推理能力训练中，应该设计从简单到复杂的课程，而非直接用高难度问题训练
• 课程的粒度可以很粗——仅在深度-1和深度-2上训练就能涌现出深度泛化，说明”简单到复杂”的方向比具体的课程细节更重要
• 这与SR²AM论文中”RL使规划视野+22.8%而频率仅+2.0%（更深非更频繁）“的发现一致——课程训练促进的是搜索深度的增长，而非搜索频率

2. 注意力头专业化作为能力诊断器

如果搜索能力可靠地分解为”栈头”和”回溯头”的分工，那么：

• 可以设计探针检测模型是否具备搜索能力——检查注意力头是否分化出轨迹追踪和失败检测功能
• 可以诊断推理失败——如果模型在复杂推理任务中失败，且未观察到头专业化分工，那么可能需要更多RL训练而非更多参数
• 这与TACT论文中”残差流中overthinking/overacting漂移轴的AUC≈0.9”发现呼应——注意力头的功能结构可能比我们想象的更具可解释性

3. 折扣因子作为搜索效率调优旋钮

实践中，可以通过调整折扣因子来控制搜索策略的效率-覆盖率权衡：

• 低折扣因子（更重视短期回报）：搜索更高效，优先探索高概率分支，但可能错过低概率的正确路径
• 高折扣因子（更重视长期回报）：搜索更全面，但可能浪费大量计算在低概率分支上
• 这与Overthinking论文中”推理token使用量随复杂度呈倒U型曲线”的发现形成对比——折扣因子可能是控制”倒U型曲线”峰值位置的旋钮

4. 最小化实验设计的方法论

论文的环境设计遵循”最小化抽象”原则——保留核心机制，去除所有干扰。这种设计思路可以迁移到其他能力涌现的研究中：

• 研究推理涌现：用受控逻辑谜题（如Z3可验证的推理链），而非开放域QA
• 研究规划涌现：用确定性网格世界，而非复杂的文本游戏
• 研究元学习涌现：用固定分布的few-shot任务，而非多域混合

潜在应用场景

1. 推理模型的课程训练：将深度课程学习应用于LLM推理训练——先在简单推理题上训练，逐步增加难度。当前主流做法是混合不同难度的数据，可能不如课程训练高效

2. Agent搜索能力的自动验证：基于注意力头专业化分工模式，设计自动化工具检测Agent模型是否具备内化搜索能力，无需运行完整评估套件

3. 高效推理路由：折扣因子驱动的搜索效率调优可用于推理路由系统——简单问题用低折扣因子（快速定向搜索），复杂问题用高折扣因子（全面搜索）

4. 小模型推理能力提升：如果搜索能力可以通过RL内化而非依赖模型规模，那么小模型+更多RL训练可能是比大模型+少量训练更经济的路径。这与ThinC论文中”4B超越235B”的发现方向一致

---

与前期论文的对话链：

本文与论文精读系列的多篇前期工作形成深度呼应——

• Overthinking / Illusion of Thinking：DFS的”探索-回溯”循环提供了推理模型中token使用量倒U型曲线的机制解释——模型在”搜索”正确路径时过度探索（Overthinking），而搜索能力的内化意味着可以通过RL训练控制搜索深度
• Sparse Policy Selection：RL仅改变1-3%高熵决策点——这些高熵点可能正是搜索中的”岔路口”决策（先探索哪条分支？何时回溯？）
• Forks in the Road：推理模型pass@k退化源于训练数据中的”岔路口”决策点——DFS的回溯机制恰好提供了”从岔路口返回”的能力
• Equilibrium Reasoners：吸引子收敛和DFS搜索是两种不同的推理动力学——前者是向不动点收敛（确定性推理），后者是显式树探索（组合推理）。两者可能对应不同类型的推理任务
• GRAM：概率潜变量生成推理提供了DFS的随机化版本——本文的随机化DFS可以视为GRAM在确定性环境中的特例