# Learning to Reason with Curriculum II: Compositional Generalization

arXiv: https://arxiv.org/abs/2606.27721 · HTML: https://mlsanity.com/paper/2606.27721/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 55 references that are in the map.
- First posted on arXiv 26 Jun 2026.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

## Builds on (most cited first, 19 of 19)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Absolute Zero: Reinforced Self-play Reasoning with Zero Data](https://mlsanity.com/paper/2505.03335/) (2025)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Self-Evolving Curriculum for LLM Reasoning](https://mlsanity.com/paper/2505.14970/) (2025)
- [Efficient Reinforcement Finetuning via Adaptive Curriculum Learning](https://mlsanity.com/paper/2504.05520/) (2025)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [OpenRLHF: An Easy-to-use, Scalable and High-performance RLHF Framework](https://mlsanity.com/paper/2405.11143/) (2024)
- [RLVE: Scaling Up Reinforcement Learning for Language Models with Adaptive Verifiable Environments](https://mlsanity.com/paper/2511.07317/) (2025)
- [Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration](https://mlsanity.com/paper/2503.07453/) (2025)
- [The Coverage Principle: How Pre-Training Enables Post-Training](https://mlsanity.com/paper/2510.15020/) (2025)
- [A Theory of Learning with Autoregressive Chain of Thought](https://mlsanity.com/paper/2503.07932/) (2025)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [h1: Bootstrapping LLMs to Reason over Longer Horizons via Reinforcement Learning](https://mlsanity.com/paper/2510.07312/) (2025)
- [On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach](https://mlsanity.com/paper/2510.04115/) (2025)
- [Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum](https://mlsanity.com/paper/2603.18325/) (2026)

## Built on by (most cited first, 3 of 3)

- [Learning Generalizable Behaviors for Terminal Agents](https://mlsanity.com/paper/2608.22631/) (2026)
- [What Pretraining and Midtraining Make Learnable from Rewards?](https://mlsanity.com/paper/2609.38446/) (2026)
- [Verification with Transfer: Exact Information Frontiers and Their Price in Calls](https://mlsanity.com/paper/2610.12211/) (2026)

## Abstract (arXiv)

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^O(√log T) tokens of supervision; i.e., subpolynomial in the sequence length T, overcoming the Omega(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.