Learning to Reason with Curriculum II: Compositional Generalization

📄 arXiv: 2606.27721v1 📥 PDF

作者: Nived Rajaraman, Audrey Huang, Miroslav Dudik, Robert Schapire, Dylan Foster, Akshay Krishnamurthy

分类: cs.LG

发布日期: 2026-06-26

备注: 82 pages, 5 figures

💡 一句话要点

提出基于自适应课程学习的方法以解决组合泛化问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 组合泛化 自适应课程学习 半自动机 监督学习 强化学习

📋 核心要点

  1. 组合泛化的理论基础尚不明确，现有方法在解决复杂问题时效率低下。
  2. 提出基于自适应课程的学习方法，通过递归分解问题并组合解决方案来提高学习效率。
  3. 实验结果显示，该方法在监督微调和强化学习设置中显著降低了学习所需的标记数量和模型覆盖要求。

📝 摘要（中文）

组合泛化是自然和人工智能的基本能力，涉及通过组合简单子问题的解决方案来解决复杂问题。本文探讨了在何种情况下将问题分解为部分能更有效地学习。通过学习半自动机的经典问题，研究表明基于自适应课程的方法在统计复杂性上显著优于直接方法。在受监督微调的设置中，课程学习使得学习者只需$2^{ ext{O}( ext{sqrt}( ext{log} T))}$个监督标记，克服了直接模拟所需的$Ω(T)$标记障碍。在强化学习的设置中，课程学习将对参考模型的覆盖要求从全序列长度$T$降低到短块长度$B ext{（}B ext{ } ext{≪} T ext{）}$，这是一个指数级的弱条件。

🔬 方法详解

问题定义：本文旨在解决组合泛化问题，现有方法在处理复杂问题时效率低，尤其是在需要大量标记的情况下。

核心思路：通过自适应课程学习，递归地将长序列分解为短子问题，逐步学习并组合解决方案，从而提高学习效率。

技术框架：整体流程包括问题分解、子问题学习和解决方案组合三个主要模块。首先将复杂问题分解为简单子问题，然后分别解决这些子问题，最后将解决方案组合以得到最终结果。

关键创新：该研究的核心创新在于通过自适应课程学习显著降低了学习所需的监督标记数量，相较于传统方法，提供了更高效的学习路径。

关键设计：在实验中，设置了不同的参数以优化学习过程，采用了特定的损失函数来引导学习，并设计了适合递归分解的网络结构。具体细节包括对中间状态的反馈机制和对参考模型的覆盖要求的调整。

📊 实验亮点

实验结果显示，在受监督微调设置中，课程学习使得学习者仅需$2^{ ext{O}( ext{sqrt}( ext{log} T))}$个标记，相较于直接模拟所需的$Ω(T)$标记，提升了学习效率。在强化学习设置中，课程学习将模型覆盖要求从全序列长度$T$降低到短块长度$B ext{（}B ext{ } ext{≪} T ext{）}$，展现出显著的优势。

🎯 应用场景

该研究的潜在应用领域包括自然语言处理、机器人控制和复杂系统模拟等。通过提高组合泛化能力，能够在更复杂的任务中实现更高效的学习和推理，具有重要的实际价值和广泛的未来影响。

📄 摘要（原文）

Compositional generalization, the ability to solve complex problems by combining solutions to simpler sub-problems, is a fundamental capability of both natural and artificial intelligence, and a key mechanism underlying chain-of-thought reasoning. However, the theoretical underpinnings of compositional generalization remain poorly understood: when and why does decomposing a problem into parts yield more efficient learning than solving it directly? We study this question through the canonical problem of learning to simulate semiautomata (predicting the outcome of $T$ steps of sequential computation), a model that captures state tracking, regular language recognition, and modular arithmetic. We show that an autocurriculum-based approach building on Part I of this series, recursively decomposing longer sequences into shorter sub-problems, learning to solve them, and composing the solutions, achieves dramatically better statistical complexity than direct methods. (i) For a setting inspired by supervised fine-tuning (SFT) where the learner receives interactive feedback on intermediate states of the computation, curriculum facilitates learning from only $2^{\mathcal{O}(\sqrt{\log T})}$ tokens of supervision; i.e., subpolynomial in the sequence length $T$, overcoming the $Ω(T)$ token barrier required by direct simulation. (ii) For a setting inspired by reinforcement learning with verifiable rewards (RLVR), where the learner improves a pre-trained reference model using an outcome verifier, we show that curriculum reduces the requirement on the reference model from coverage at the full sequence length $T$ to coverage at a shorter block length $B \ll T$, an exponentially weaker condition.