课程学习推理II：组合泛化

arXiv cs.LG 论文
reasoning curriculum-learning compositional-generalization chain-of-thought automata-simulation theoretical-analysis

摘要

本文从理论上分析了课程学习通过将复杂问题分解为更简单的子问题并组合解决方案，如何显著降低学习模拟顺序计算（半自动机）的样本复杂度——相较于直接方法，在监督微调中实现次多项式监督需求，并在可验证奖励的强化学习中实现指数级更弱的覆盖条件。

arXiv:2606.27721v1 公告类型：新 摘要：组合泛化——通过将简单子问题的解组合来解决复杂问题的能力——是自然智能和人工智能的基本能力，也是思维链推理的关键机制。然而，组合泛化的理论基础仍然知之甚少：将问题分解成部分何时以及为何能比直接求解产生更高效的学习？我们通过半自动机模拟学习的经典问题（预测 $T$ 步顺序计算的结果）来研究这个问题，该模型涵盖了状态追踪、正则语言识别和模算术。我们展示了基于本系列第一部分的自课程（autocurriculum）方法，通过递归地将较长的序列分解为较短的子问题，学习求解它们并组合解，相较于直接方法实现了显著更好的统计复杂度。(i) 在受监督微调（SFT）启发的设定中，学习器接收关于计算中间状态的交互式反馈，课程学习仅需 $2^{\mathcal{O}(\sqrt{\log T})}$ 个监督符号即可学习，即序列长度 $T$ 的次多项式，克服了直接模拟所需的 $\Omega(T)$ 符号障碍。(ii) 在受可验证奖励强化学习（RLVR）启发的设定中，学习器使用结果验证器改进预训练参考模型，我们证明课程学习将参考模型的要求从完整序列长度 $T$ 上的覆盖降低到较短块长度 $B \ll T$ 上的覆盖，这是一个指数级更弱的条件。
查看原文
查看缓存全文

缓存时间: 2026/06/29 05:25 

# 基于课程学习进行推理（二）：组合泛化
来源：https://arxiv.org/abs/2606.27721
查看 PDF (https://arxiv.org/pdf/2606.27721)

> 摘要：组合泛化——通过组合简单子问题的解决方案来解决复杂问题的能力——是自然智能与人工智能的一项基本能力，也是链式思维推理的关键机制。然而，组合泛化的理论基础仍不明确：何时以及为何将问题分解为多个部分比直接求解能带来更高效的学习？我们通过一个经典问题来研究这一问题：学习模拟半自动机（预测 \(T\) 步顺序计算的结果），该模型涵盖了状态追踪、正则语言识别和模运算。我们证明，基于本系列第一部分提出的自动课程学习方法——递归地将较长序列分解为较短的子问题，学习求解这些子问题，再组合解决方案——能够获得比直接方法显著更优的统计复杂度。(i) 在一种受监督微调（SFT）启发的场景中，学习者接收关于计算中间状态的交互反馈，课程学习仅需 \(2^{\mathcal{O}(\sqrt{\log T})}\) 个监督令牌即可完成学习；即，在序列长度 \(T\) 下达到次多项式复杂度，克服了直接模拟所需的 \(\Omega(T)\) 令牌壁垒。(ii) 在一种受带可验证奖励的强化学习（RLVR）启发的场景中，学习者使用结果验证器改进预训练参考模型，我们证明课程学习将参考模型的覆盖要求从完整序列长度 \(T\) 降低到较短的块长度 \(B \ll T\)，这是一个指数级更宽松的条件。

## 提交历史

来自：Nived Rajaraman [查看邮件](https://arxiv.org/show-email/ba6853cb/2606.27721) **\[v1\]** 2026年6月26日星期五 05:09:08 UTC (119 KB)

相似文章

通用推理的可迁移性：多领域RLVR的自动化课程设计

Hugging Face Daily Papers

本文提出了一种迁移感知课程（TAC），这是一种基于多臂老虎机风格的多领域RLVR在线课程，通过梯度几何对齐优先选择其更新能惠及其他领域的领域。与固定课程和仅基于可学习性的课程相比，TAC在Qwen3-1.7B和Llama3.2-3B上提升了宏观平均准确率。