Technical Summary: Learning to Reason with Curriculum II: Compositional Generalization

1. Problem Statement

The paper investigates the theoretical underpinnings of compositional generalization—the ability to solve complex problems by combining solutions to simpler sub-problems—a mechanism central to chain-of-thought (CoT) reasoning in artificial intelligence. The core question addressed is: When and why does decomposing a problem into parts yield more efficient learning than solving it directly?

To answer this, the authors formalize the problem using semiautomaton simulation. A semiautomaton is defined by an unknown, Markovian, stationary transition function $\pi^*: S \times \Sigma \to S$. Given an initial state $s_0$ and an input word $w_{1:T}$, the goal is to predict the terminal state $s_T$ after $T$ steps. The intermediate states $s_{1:T}$ constitute a chain of thought. This model captures state tracking, regular language recognition, and modular arithmetic.

The paper studies two specific learning settings:

1. Interactive Chain-of-Thought Supervision (iSFT): The learner has access to an oracle that can return the state at any step $t$ of a computation for a cost of one unit. The goal is to minimize the number of oracle queries (query complexity) and training instances (sample complexity) required to learn a model with low error.
2. Reinforcement Learning with Verifiable Rewards (RLVR): The learner has access to a pre-trained "weak" reference model $\pi_{ref}$ that can solve short instances of length $B \ll T$ with constant probability, and an outcome verifier that checks the correctness of a terminal state guess. The goal is to improve the reference model to solve length-$T$ instances efficiently, overcoming the exponential drop in success probability that occurs when rolling out a weak model over long horizons.

2. Methodology

The authors propose autocurriculum-based approaches that recursively decompose long sequences into shorter sub-problems, learn to solve them, and compose the solutions. This approach builds on Part I of the series, utilizing a template of composition and boosting.

Core Algorithmic Components

• Composition: A model trained to solve instances of length $\tau$ can be composed $L$ times (where $T = L\tau$) to solve instances of length $T$. However, errors accumulate under composition; thus, the short-range models must be trained to high accuracy.
• Boosting: To achieve the necessary high accuracy on short sub-problems, the authors employ a multiscale boosting strategy. This involves training an ensemble of weak learners on reweighted distributions that focus on "hard" instances (where the current ensemble fails) and aggregating them (e.g., via plurality vote).
• Self-Generated Curriculum: Instead of a fixed schedule, the learner adaptively selects which sub-problems to train on based on the failures of models trained at finer scales.

Key Technical Innovations

• Inverted Sampling: A central technical contribution is a new sampling technique to handle the distribution shift inherent in boosting. Standard rejection sampling from reweighted mixtures of marginals is inefficient (requiring $\Omega(L)$ samples in the worst case). The authors introduce inverted sampling, which first applies rejection sampling independently to all $L$ sub-instances within a long sequence and then selects one of the accepted instances uniformly. This achieves an acceptance probability proportional to the number of sub-instances, significantly reducing sample complexity while maintaining sufficient approximation guarantees for the learning algorithm.
• Multiscale Recursion: The algorithm (AutoLearn) applies the boosting + composition template recursively. It decomposes length-$T$ instances into length-$\tau$ sub-problems, which are further decomposed until reaching length-1 (next-token prediction). This creates a hierarchy where models solving shorter, easier problems are composed to solve harder ones.
• Guess-and-Check for RLVR: In the RLVR setting, where intermediate state labels are not directly available, the authors simulate the interactive oracle using the weak reference model and the verifier. By generating rollouts for each block and verifying the terminal state of the block, they can effectively "label" intermediate states to construct the curriculum.

3. Key Contributions and Results

Setting I: iSFT (Interactive Supervision)

The paper presents AutoLearn, an algorithm that learns semiautomata with subpolynomial query and sample complexity in the sequence length $T$.

• Result: The query and sample complexity are upper bounded by $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.
• Comparison: This breaks the $\Omega(T)$ barrier inherent in direct simulation methods.
  • Full CoT Supervision: Requires $\Omega(T)$ queries per instance to label every state.
  • End-to-End Feedback: Requires $\Omega(T)$ sample complexity due to the inability to generalize from terminal states without intermediate grounding.
• Mechanism: By adaptively selecting sub-problems and using inverted sampling to manage distribution shift, AutoLearn achieves a complexity that is subpolynomial in $T$, specifically $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.

Setting II: RLVR (Verifiable Rewards)

The paper presents AutoLearn.RL, which improves a weak reference model $\pi_{ref}$ from block-level competence ($B$) to full-length competence ($T$).

• Result: The algorithm achieves high accuracy on length-$T$ instances with costs governed by the reference model's coverage at the shorter block length $B$, rather than the full length $T$.
• Coverage Expansion: Standard RLVR methods require the reference model to have non-trivial coverage at length $T$, which is exponentially unlikely if it only has coverage at length $B$ (i.e., $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$). AutoLearn.RL reduces this requirement to coverage at length $B$.
• Complexity:
  • Sample complexity: $\tilde{\mathcal{O}}(d/\varepsilon)$.
  • Query complexity: $\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$.
  • Computational cost: $\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$.
• Significance: The "burn-in" cost depends on the coverage at the short scale $B$, allowing the effective coverage at length $T$ to expand from exponentially small to constant through the curriculum.

4. Significance and Claims

The paper claims that composition combined with self-generated curriculum can achieve superpolynomial reductions in supervision and computational cost compared to non-curriculum baselines.

• Theoretical Foundation: It provides a rigorous theoretical framework explaining why decomposing problems helps: it allows the learner to trade off sequence length for accuracy requirements via composition, while boosting ensures the necessary accuracy on sub-problems.
• Efficiency: The results demonstrate that for tasks like semiautomaton simulation, learning can be achieved with $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ complexity, a dramatic improvement over the linear $\Omega(T)$ complexity of standard approaches.
• Generalization: The findings suggest that autocurricula, where the learner designs its own problems, are not just heuristics but can be theoretically justified as a mechanism to overcome the statistical and computational barriers of long-horizon reasoning.
• Limitations and Future Work: The authors acknowledge simplifications, such as restricting the model class to Markovian models (excluding full-history attention like Transformers) and assuming deterministic transitions. They note that extending these results to non-Markovian models and stochastic transitions is a key direction for future work. They also highlight that while their current results achieve subpolynomial dependence on $T$, achieving polylogarithmic dependence remains an open question, potentially requiring stronger assumptions like finite mistake bounds.

In summary, the paper establishes that compositional generalization, when guided by an adaptive curriculum and supported by techniques like inverted sampling, offers a provably efficient path to learning complex sequential tasks that are intractable for direct learning methods.