📊 statistics

Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

本文从理论上证明，尽管基于过程奖励的强化学习与监督微调均能使单层 Transformer 通过思维链推理可证明地学习稀疏布尔函数，但两者的学习动态存在根本差异：强化学习同时习得整个推理链，而监督微调则逐步习得。

原作者： Bochen Lyu, Yiyang Jia, Xiaohao Cai, Zhanxing Zhu

发布于 2026-05-27

📖 1 分钟阅读☕ 轻松阅读

原作者： Bochen Lyu, Yiyang Jia, Xiaohao Cai, Zhanxing Zhu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你有一个非常聪明但略显困惑的机器人（一个Transformer），它需要解决一个复杂的谜题。这个谜题是一个布尔函数，这只是一个花哨的说法，指答案要么是“是”（+1），要么是“否”（-1）的逻辑问题。具体来说，这篇论文研究的是“稀疏”谜题，意味着答案仅依赖于隐藏在大量噪声中的少数几条特定信息。

为了解决这些谜题，机器人使用一种称为**思维链（Chain-of-Thought, CoT）**的策略。它不是直接跳到答案，而是将问题分解为一系列小的中间步骤，就像人类在草稿纸上一步步解数学题一样。

这篇论文研究了两种不同的方法来教导机器人有效使用思维链：监督微调（SFT）和强化学习（RL）。作者证明这两种方法都有效，但它们教导机器人的方式从根本上是不同的。

以下是使用简单类比进行的分解：

1. 谜题：递归分解

想象这个谜题是一棵巨大的树。为了找到顶部的答案，你必须先解决底部的两个小逻辑问题，然后将这些答案结合起来解决稍大一点的两个逻辑问题，以此类推，一直到达顶部。

目标：机器人需要学会在每一步中只关注所需的两条特定信息（“相关”的叶子节点），而忽略其余的噪声。

2. 两位老师

老师 A：严格的教官（SFT）

监督微调（SFT）就像一位为谜题的每一步都提供完美答案键的老师。

工作原理：老师说：“第 1 步的答案是 X。第 2 步的答案是 Y。”
关键点：机器人必须基于它刚刚写下的第 1 步答案来生成第 2 步的答案。
结果（逐步学习）：论文证明，这个机器人是一步一步学习的。
- 类比：想象学习一套舞蹈动作。如果你第一步做错了，你就无法学习第二步，因为你的起始位置是错误的。机器人必须先完美掌握第 1 步，才能开始学习第 2 步。它需要一次训练课程来修正第 1 步，然后另一次课程来修正第 2 步，依此类推。这是一个缓慢的线性过程。

老师 B：过程教练（带过程奖励的 RL）

强化学习（RL）就像一位不仅看最终得分，而且对机器人做的每一个动作都给予反馈的教练。

工作原理：机器人尝试解决谜题。如果它做对了一个小步骤，教练会立即给予“做得好”的奖励。如果做错了，它就会受到惩罚。
结果（同时学习）：论文证明，这个机器人是一次性学会整个步骤链的。
- 类比：想象教练同时大喊：“第 1 步的步法很好！第 5 步的手位很好！第 3 步的肘部动作不对！”因为机器人无论之前的步骤是否完美，都能获得针对每一个具体步骤的明确反馈，它可以在单次训练课程中调整整个套路。它同时学会了整支舞蹈。

3. 重大发现：“过程”与“结果”

论文强调了这两位老师给予反馈方式的根本区别：

SFT 依赖于机器人自己的先前输出。如果机器人在开始时出错，下一步的“真实标签（ground truth）”就会变成令人困惑的噪声。这迫使它进行逐步学习。
RL（特别是带有过程奖励的 RL）为每一步独立地提供正确的“真实标签”。无论机器人是否搞砸了第 1 步，教练仍然知道第 2 步应该是什么样子，并据此给予奖励或惩罚。这实现了“一次性”学习。

4. 关于“困难”的谜题呢？

论文在三种特定类型的逻辑谜题上测试了这一点：

k-PARITY：就像检查一组开关中“开启”位置的数量是偶数还是奇数。（这对人工智能来说，如果没有帮助是出了名地难学）。
k-AND：检查是否所有特定开关都是“开启”的。
k-OR：检查是否至少有一个特定开关是“开启”的。

论文从数学上证明，对于这三种谜题，只要机器人能够区分“重要”信息和“噪声”，这两种教学方法都有效。

研究结果总结

两者都有效：你可以使用 SFT 或 RL 来教导 Transformer 进行复杂的推理。
它们不同：
- SFT 就像一个必须在继续之前掌握基础的学生。它是逐步学习的。
- RL（带过程奖励） 就像一个对问题的每个具体部分都能获得即时反馈的学生。它是同时学习整个链条的。
警告：如果在现实生活中比较 SFT 和 RL，你必须小心。如果你改变老师给予反馈的方式（例如，仅在最后使用“最终奖励”而不是在每一步使用“过程奖励”），学习行为就会完全改变。论文表明，比较这两种方法需要控制奖励是如何设计的，而不仅仅是方法本身。

简而言之，这篇论文表明，虽然这两种方法都能教会机器人进行逻辑思考，但它们具有不同的“学习速度”和“教学风格”，理解这些差异是构建更好人工智能的关键。

技术摘要：带有强化学习或监督微调的 Transformer 可证明地学习稀疏布尔函数，但方式不同

问题陈述
基于 Transformer 架构的大语言模型（LLM）通过思维链（CoT）提示展现了卓越的推理能力。尽管监督微调（SFT）和强化学习（RL）是增强这些能力的主要方法，但其底层学习动态的理论机制仍鲜为人知。具体而言，目前缺乏严谨的分析来比较 RL（特别是结合过程奖励）与 SFT（特别是无教师强制）如何使 Transformer 能够学习那些在端到端方式下难以学习的复杂稀疏布尔函数。本研究通过调查 $k$ -稀疏布尔函数（即由一小部分 $k$ 个输入位决定的函数）的可学习性来填补这一空白，研究使用配备中间推理步骤的单层 Transformer 进行探索。

方法论
作者提出了一个统一的理论框架，用于分析 RL 和 SFT 在特定一类 $k$ -稀疏布尔函数上的学习动态。这些函数被递归分解为固定的 2-稀疏布尔函数（例如奇偶校验、与、或），形成类似于 CoT 的推理链。

模型架构：研究利用了一个简化的单层 Transformer，包含位置编码、自注意力层和前馈层。该模型设计为在生成最终答案之前，迭代生成中间推理步骤（ $y^{(t)}$ ）。
“预训练”掩码：为了确保理论上的可处理性并模拟从预训练中获得的结构性先验，作者对注意力权重施加了特定的“预训练”掩码。该掩码将推理 token 的注意力限制在其相关子节点（由递归分解定义）和输入序列上，从而有效控制误差传播。
学习范式：
- 带过程奖励的 RL：Transformer 通过策略梯度进行优化，以最大化奖励函数，其中奖励被分配给每个中间推理步骤（ $r_t$ ），而不仅仅是最终结果。
- 无教师强制的 SFT：Transformer 被训练以最小化生成推理链与真实标签之间的损失（铰链损失）。关键在于，模型在训练期间自行生成中间步骤（自回归生成），而不是接收真实前缀（教师强制），从而解决了训练与推理不匹配的问题。
核心分析工具：作者引入了一个“关键梯度分量”（ $\gamma$ ）。他们证明，该分量的分离——即相关位置（子节点）的梯度信号严格大于无关位置的梯度信号——是可证明可学习性的充分条件。

主要贡献与结果
本文确立了充分条件，证明单层 Transformer 可以通过 RL 和 SFT 可证明地学习 $k$ -稀疏布尔函数。主要发现如下：

统一的可学习性条件：如果关键梯度分量能够区分相关位置与无关位置，则 RL 和 SFT 均能成功。这一条件在三个基本示例中得到了验证： $k$ -PARITY（ $k$ -奇偶校验）、 $k$ -AND（ $k$ -与）和 $k$ -OR（ $k$ -或）。
截然不同的学习动态：
- RL（过程奖励）：在分离条件下，RL 在单次梯度更新中同时学习整个 CoT 推理链。过程奖励为所有步骤提供信息信号，无论其他步骤的当前状态如何，从而使模型能够立即获得完整的推理能力。
- SFT（无教师强制）：相比之下，SFT 表现出逐步的学习行为。由于生成的自回归性质，模型无法可靠地学习第 $t$ 步，直到第 $t-1$ 步被正确生成。因此，SFT 需要 $T$ 次梯度更新（其中 $T$ 是链长）才能学习整个链条，每次更新解决一步。
最终奖励的困难性：本文证明，仅使用最终（基于结果的）奖励进行优化的 RL 无法高效地学习这些函数。策略梯度的方差呈指数级小，导致信号淹没在噪声中，这解释了过程奖励对于复杂推理任务的必要性。
扩展到串行 CoT：分析从二叉树分解扩展到了串行 CoT 结构（在实际 LLM 中常见），证实了在适当的掩码下，相同的学习动态（RL 为同时，SFT 为逐步）依然成立。

意义与主张
作者声称，这项工作首次对带有过程奖励的 Transformer 的 RL 学习动态进行了理论刻画，填补了文献中的关键空白。通过移除先前理论工作中常用的教师强制和数据增强策略（例如 Kim & Suzuki, 2025），本研究提供了 RL 与 SFT 之间更现实的比较。

其意义在于揭示：虽然两种方法都能实现可学习性，但它们通过根本不同的机制实现：

带有过程奖励的 RL 通过同时学习整个链条，模拟了带有教师强制的 SFT 的效率。
无教师强制的 SFT 自然地诱导了一种逐步课程，这是自回归训练的内在属性，不需要外部课程学习或数据过滤。

本文得出结论，RL 与 SFT 之间的实证比较必须仔细控制诸如奖励设计（过程奖励与结果奖励）和训练机制（教师强制与自回归生成）等因素，因为这些因素会显著改变学习动态，并可能混淆对优化方法本身的比较。