技术摘要：学习推理之课程学习 II：组合泛化

1. 问题陈述

本文研究了**组合泛化（compositional generalization）**的理论基础——即通过组合简单子问题的解决方案来解决复杂问题的能力——这是人工智能中思维链（CoT）推理的核心机制。本文探讨的核心问题是：何时以及为何将问题分解为部分，比直接解决问题更有效率？

为了回答这个问题，作者使用**半自动机模拟（semiautomaton simulation）**对问题进行了形式化。一个半自动机由一个未知的、马尔可夫性质的、平稳的转移函数 $\pi^*: S \times \Sigma \to S$ 定义。给定初始状态 $s_0$ 和输入词 $w_{1:T}$，目标是在 $T$ 步后预测终止状态 $s_T$。中间状态 $s_{1:T}$ 构成了思维链。该模型捕捉了状态追踪、正则语言识别和模运算等特性。

本文研究了两种特定的学习设置：

1. 交互式思维链监督（iSFT）： 学习者可以访问一个能够返回计算中任意步骤 $t$ 的状态的算子（oracle），其代价为一个单位。目标是最小化学习具有低误差的模型所需的查询复杂度（query complexity）和训练实例数量（sample complexity）。
2. 带有可验证奖励的强化学习（RLVR）： 学习者可以访问一个预训练的“弱”参考模型 $\pi_{ref}$，该模型能以常数概率解决长度为 $B \ll T$ 的短实例，以及一个用于检查终止状态猜测是否正确的输出验证器。目标是改进参考模型以高效解决长度为 $T$ 的实例，从而克服在长时程（long horizon）展开过程中出现的成功概率指数级下降问题。

2. 方法论

作者提出了基于自生成课程（autocurriculum-based）的方法，该方法递归地将长序列分解为较短的子问题，学习解决这些子问题，并组合这些解决方案。这种方法建立在系列论文的第一部分之上，利用了**组合与提升（composition and boosting）**的模板。

核心算法组件

• 组合（Composition）： 一个被训练用于解决长度为 $\tau$ 的实例的模型可以被组合 $L$ 次（其中 $T = L\tau$）以解决长度为 $T$ 的实例。然而，误差会在组合过程中累积；因此，短程模型必须经过高精度训练。
• 提升（Boosting）： 为了在短程子问题上达到必要的精度，作者采用了多尺度提升策略。这涉及在重新加权的分布上训练一个弱学习器集成，这些分布侧重于“困难”实例（即当前集成失败的实例），并通过聚合（例如通过多数投票）来处理。
• 自生成课程（Self-Generated Curriculum）： 学习者不是使用固定的进度表，而是根据精细尺度模型训练时的失败情况，自适应地选择训练哪些子问题。

关键技术创新

• 反向采样（Inverted Sampling）： 一个核心技术贡献是处理提升过程中固有的分布偏移（distribution shift）的新采样技术。标准的从边际分布的重新加权混合中进行拒绝采样的做法效率较低（在最坏情况下需要 $\Omega(L)$ 个样本）。作者引入了反向采样，它首先对长序列中的所有 $L$ 个子实例独立进行拒绝采样，然后均匀地选择其中一个被接受的实例。这使得接受概率与子实例的数量成正比，在保持算法足够的近似保证的同时，显著降低了样本复杂度。
• 多尺度递归（Multiscale Recursion）： 该算法（AutoLearn）递归地应用“提升 + 组合”模板。它将长度为 $T$ 的实例分解为长度为 $\tau$ 的子问题，这些子问题进一步分解，直到达到长度为 1（下一个 token 预测）。这创建了一个层次结构，其中解决较短、较易问题的模型被组合起来以解决更难的问题。
• 猜想与检查（Guess-and-Check）用于 RLVR： 在 RLVR 设置中，由于无法直接获得中间状态标签，作者利用弱参考模型和验证器来模拟交互式算子。通过为每个块生成展开过程并验证该块的终止状态，他们可以有效地为中间状态“打标签”，从而构建课程。

3. 核心贡献与结果

设置 I：iSFT（交互式监督）

本文提出了 AutoLearn 算法，该算法学习半自动机的查询复杂度与样本复杂度在序列长度 $T$ 下均为**次多项式（subpolynomial）**级别。

• 结果： 其查询和样本复杂度被上限约束为 $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$。
• 对比： 这打破了直接模拟方法中存在的 $\Omega(T)$ 壁垒。
  • 全 CoT 监督： 每个实例需要 $\Omega(T)$ 次查询来标记每个状态。
  • 端到端反馈： 由于无法从终端状态进行泛化而缺乏中间接地（grounding），其样本复杂度需要 $\Omega(T)$。
• 机制： 通过自适应地选择子问题并使用反向采样来管理分布偏移，AutoLearn 实现了在 $T$ 上的次多项式复杂度，具体为 $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$。

设置 II：RLVR（可验证奖励）

本文提出了 AutoLearn.RL，它将弱参考模型 $\pi_{ref}$ 从块级能力（$B$）提升到全长能力（$T$）。

• 结果： 该算法在长度为 $T$ 的实例上实现高精度，其成本受限于参考模型在较短块长度 $B$ 处的覆盖率，而非全长 $T$。
• 覆盖率扩张（Coverage Expansion）： 标准 RLVR 方法要求参考模型在长度 $T$ 时具有非平凡的覆盖率，如果它仅在长度 $B$ 时有覆盖率，那么在长度 $T$ 时的覆盖率是指数级微小的（即 $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$）。AutoLearn.RL 将这一要求降低到了对长度 $B$ 的覆盖率。
• 复杂度：
  • 样本复杂度：$\tilde{\mathcal{O}}(d/\varepsilon)$。
  • 查询复杂度：$\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$。
  • 计算成本：$\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$。
• 意义： “热身”（burn-in）成本取决于短尺度 $B$ 处的覆盖率，这使得长度 $T$ 的有效覆盖率能够通过课程学习从指数级微小扩张到常数级。

4. 重要性与主张

本文声称，组合结合自生成课程可以实现相对于非课程基准模型的超多项式级（superpolynomial）减少在监督和计算成本上的开销。

• 理论基础： 它提供了一个严谨的理论框架来解释为什么分解问题会有帮助：它允许学习者通过组合在序列长度与精度要求之间进行权衡，而提升（boosting）则确保了子问题所需的精度。
• 效率： 结果表明，对于像半自动机模拟这样的任务，学习可以在 $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ 的复杂度下完成，这比标准方法的 $\Omega(T)$ 线性复杂度有了巨大的提升。
• 泛化： 研究结果表明，自生成课程（即学习者设计自己的问题）不仅是一种启发式方法，而且在理论上是可以证明的，作为克服长时程推理障碍的一种机制。
• 局限性与未来工作： 作者承认存在一些简化，例如将模型类限制为马尔可夫模型（排除了 Transformer 等全历史注意力机制）并假设转移是确定性的。他们指出，将这些结果扩展到非马尔可夫模型和随机转移是未来的一个重要方向。他们还强调，虽然目前的成果实现了对 $T$ 的次多项式依赖，但实现多项式对数（polylogarithmic）依赖仍是一个开放性问题，这可能需要更强的假设，如有限错误界限。

总之，本文确立了组合泛化在自适应课程的引导下，结合反向采样等技术，为学习复杂的序列任务提供了一条可证明的高效路径，而这些任务对于直接学习方法而言是难以处理的。