acceptodds
Under review as a conference paper at ICLR 2027

Provable Compositional Reasoning via Curriculum Learning

Abstract

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 steps of sequential computation), a model that captures state tracking, regular language recognition, and modular arithmetic. We show that a *curriculum based* approach—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 tokens of supervision; i.e., *subpolynomial* in the sequence length , overcoming the 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 to coverage at a shorter block length , an exponentially weaker condition.

Primary area:
learning theory
Keywords:
Reasoning, Chain-of-Thought, Curriculum Learning, Coverage

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_4VphOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies compositional generalization in a theoretical setting where the learner constructs its own curriculum of shorter subproblems to solve longer computations. The authors focus on the case of semiautomaton simulation in which an unknown transition function governs the state evolution, and the goal is to predict the end state of a length-T input.

Critical strengths

Overall, I found this work to contain an interesting and substantial set of theoretical results. The paper formalizes how intermediate-state supervision or verifier feedback can support learning accurate short-range predictors, which can then be composed into solutions to longer problems. The RLVR result is nice, and may be potentially relevant to understanding how LLMs actually generalize in practice during post-training. The high level argument makes sense, basically that a sufficient ref-model coverage of short computations can support accurate long-range predictions when the right compositional structure and feedback is available.

I think that the main result is interesting, which bounds both the number of sampled long inputs and the number of oracle queries with subpolynomial dependence on T, of the form (2^{\widetilde O(\sqrt{\log T})}), modulo factors depending on model-class complexity, desired accuracy, etc. AutoLearn.RL extends this approach to the RLVR setting. Theorem 4.5 is nice, since the assumptions that go in are that the reference model has some coverage at a short block length (B), while its accuracy guarantee concerns full length-T problems.

Critical weaknesses
  1. The presentation makes the main ideas quite difficult to follow. I understand the page-limit constraints, but understanding the algorithms requires going back and forth between the main text and appendices. Details needed to understand the procedure (including Algorithm 2 itself which is a core algorithm of the paper!), are put in the appendix. In my opinion, a more informal main presentation using some simple examples and the intuition behind each result, could communicate the contributions more effectively. I am not a specialist in this area of learning theory, so my comments focus primarily on accessibility and interpretation, but I suspect these changes would help a broader audience appreciate the results.

  2. I think the existing overview and figures would be much more useful alongside a small numerical example, such as modular addition. This could show which intermediate states are queried, how blocks are filtered and selected, what training examples are produced, and how the resulting predictors are composed.

    I don't think empirical experiments are necessary for a theoretical contribution of this kind. However, for a paper proposing two concrete algorithms, it would be helpful to see what curriculum each algorithm actually constructs on a concrete task (otherwise what's the point of stating it as an algorithm vs just a construction for the proof of a theorem?). A synthetic experiment could also help interpret the results, while acknowledging that optimization may fall outside the theoretical assumptions.

  3. The implications for practical learning and language-model reasoning need clarification. The compositional structure is clear in the semiautomaton setting as a block starting at an intermediate state is itself a valid shorter problem. But it's less clear to identify the corresponding states, steps, etc in natural-language reasoning. Similarly, the ability to verify the constructed subproblems is a substantial requirement. Formal-verification settings like Lean are an interesting motivation, but there verification may be expensive, and the availability of a verifier for a complete task may not automatically work for every subproblem. I'm curious how the authors think about this and how it relates to their work.

Minor issue: Theorem 4.5 contains an unresolved “??” reference to the trajectory-set optimization oracle.

Overall, I view this as a strong theoretical paper that is somewhat hampered by its presentation. I would raise my score if the authors substantially improved the pedagogy and made the algorithms easier to follow.

Questions for authors
  1. Can the proposed algorithm help when expressivity is sufficient but learning is difficult? Something that comes to mind is the A_5 state tracking task with 3-cycle inputs, or related S_5 tasks, using a linear-recurrent architecture that can express the correct computation but doesn't reliably learn a solution that generalizes to longer sequences. If not, what assumptions get violated? Could the framework guide curriculum construction when the learner is implemented through gradient-based training?
  2. What happens when verification is available only for some subproblems? Could the guarantee be extended when only a fraction of the constructed blocks can be verified? In particular, how would randomly missing verification differ from a setting where certain types of subproblems cannot be verified at all? (Eg, Lean comes to mind here, and the implications for math).
  3. What would the required decomposition look like for natural language chain-of-thought? In light of the limitations discussed in Remark 2.4, what would constitute a state, a step, and a valid block in a language-model application? What additional structure would you need to so that a block can be treated as a shorter instance of the same problem, initialized from an intermediate state and checked by a verifier (if such structure exists)?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 4Vph

We appreciate the detailed and informative feedback! Below are the responses to the reviewer’s questions and comments:

 

[W1,W2] Can the presentation of the main algorithm be improved?

With the additional space available during the rebuttal, we have made changes to the draft to improve accessibility of the paper:

  1. We discuss an overview of the algorithm, as well as a modular addition example in detail in the main text (Section 3.3)
  2. We run an experiment to illustrate the curriculum on modular addition with a masked transformer (Appendix K). We see that the curriculum requires much less expert supervision, compared to a full-CoT baseline.

 

[W3] Can the implications for language model reasoning be clarified?

Our theory takes the first step toward understanding how curricula can bring difficult problems within reach in settings where states are observable. Developing a theory for how curricula can help, in the absence of strong identifiability assumptions on easier subtasks, is a northstar for this line of work. That said, in Remark 2.4 in the paper, we clarify that the semiautomata state space need not be small, capturing rich settings, e.g., fixed-window attention, and recurrent models, on state-identifiable tasks.

We point out three examples (not mentioned in the paper) which connect our work more closely to specific language models applications:

  1. Code generation: In modern agentic applications models interact with a codebase making changes that a user suggests. Viewing the semiautomaton state as the state of the code repository and the input as a sequence of instructions from a user, the simulation task is to make correct changes to the codebase. Each state transition is an entire CoT+actions taken by a language model. Our results demonstrate which atomic tasks the model must be supervised on to ensure that it can generalize to solving a sequence of TT tasks specified by a user.

  2. Reasoning with context compression. Approaches like MEMENTO [1] and Self-summarization [2] allow language models to compact their own context periodically for long context reasoning. After each summarization step, the previous tokens are dropped from the context. Reasoning traces are formatted as: <think_1><summary_1><think_2><summary_2>.... The reasoning process is now Markovian in the "state", <think_j><summary_j>. Our results show how to supervise the language model on a small number of <think><summary> blocks, so as to ensure that the composed reasoning across TT steps achieves high performance.

To summarize, the purpose of our work is to understanding how and when models can benefit from constructing their own curriculum of examples. Our theory gives the first steps toward answering this question under structured assumptions, toward more abstract settings (e.g., general language models) where reasoning is not Markovian and states are not explicit. Identifying what structure of problems enables curricula to be constructed efficiently is an open question---the answer depends on how the learner gets feedback, and what side information may be available.

 

[Q1] Can the algorithm help when expressivity is sufficient but learning is difficult? Can the curriculum guide gradient-based approaches?

We believe that our curriculum should be useful for gradient-based learners as well. The paper prescribes which next-token examples should be selected to train on; in practice, gradient-based methods can be used to update the model on these examples. As for the examples of S5S_5 / parity the reviewer mentions, where expressivity is sufficient but learning is difficult---these settings are hard to learn when the intermediate CoT is not observed. Our work addresses this by letting the model query intermediate states in the CoT. In general, there are works which show that these settings are learnable when supervised with full CoTs (e.g., [3]).

 

[1] Kontonis, V., Zeng, Y., Garg, S., Chen, L., Tang, H., Wang, Z., Awadallah, A., Horvitz, E., Langford, J., & Papailiopoulos, D. (2026). MEMENTO: Teaching LLMs to Manage Their Own Context. (arXiv:2604.09852)

[2] Cursor. (2026, March 17). Training Composer for longer horizons. Cursor Blog. https://cursor.com/blog/self-summarization

[3] Kim, J., & Suzuki, T. (2024). Transformers provably solve parity efficiently with chain of thought (arXiv:2410.08633)

AuthorsOpenReview ↗

Response to Reviewer 4Vph (contd.)

[Q2] What happens if not every sub-problem can be verified?

This is an interesting setting, and the answer to this question depends precisely on how the "unverifiable" sub-problems are modeled. If very few useful sub-problems are verifiable, we expect that the setting will become computationally hard (collapsing to pure end-to-end feedback in the limit).

A related setting is where the learner obtains noisy feedback upon querying the verifier. Here, learning may still be tractable because the learner can repeatedly query the verifier to sharpen its signal. Extending our results to settings where certain kinds of sub-problems are completely unverifiable is an interesting direction for future work, accounting for practical considerations.

 

[Q3] What would the state decomposition look like for natural-language CoTs?

The answer to this question depends on the specific settings under consideration. in our response to W2 above, we discuss two examples, coding and context compaction, where these states are easy to infer. There are other settings, e.g., GSM8k style math reasoning problems, where intermediate steps can be verified with regex-style verifiers, making it compatible with our results.

More broadly, for free-form reasoning tasks, our work makes assumptions which may be strong. For these settings, a verifier for intermediate steps may be inexact or unavailable, and the states themselves may not be identifiable. Extending our work to account for these considerations is a natural question for future research.

I thank the authors for addressing my questions and comments, an improving the presentation of their work. I am satisfied with the changes and have increased my score.

Reviewer_KWmiOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This manuscript proposes AutoLearn. By recursively decomposing long tasks into shorter subtasks, enhancing the accuracy of subtasks through boosting, and subsequently reassembling into a complete task via composition, authors claim that it can achieve more efficient compositional reasoning.

Critical strengths
  1. Focus on the critical issue of compositional generalization, and demonstrates effectiveness of proposed method through both theoretical analysis and experiments.
  2. Proposes Multiscale Boosting which recursively combines boosting with composition to address the issue of error accumulation in long-horizon task sequences. The algorithm design is innovative.
Critical weaknesses

‌The iCoT oracle defined in Definition 3.1 can directly return a computation result of length t at a query cost of 1. However in practice, computing a single intermediate state using a semiautomata may still require an amount of work that scales with the sequence length. Thus supervisory query complexity is not equivalent to the actual supervisory token complexity. I suggest distinguishing between actual computational efficiency and oracle query efficiency.

Questions for authors

‌See Weakness.

2 comments
AuthorsOpenReview ↗

Response to Reviewer KWmi

We thank the reviewer for their feedback and comments! We answer the question below:

 

Is the iCoT oracle cost accounting equivalent to the cost of supervision?

There are natural examples, e.g., modular arithmetic and linear recurrences where intermediate states can be computed in parallel in O(log⁡t)\mathcal{O} (\log t) time by divide-and-conquer over matrix or group products (we give more such examples in Appendix A.1 in the paper). However, across many settings, labeling an intermediate token may require the teacher to generate all tokens until that point in an autoregressive manner. We are up front about this limitation in the paper.

Extending our results to account for supervision costs in the manner the reviewer mentions is an interesting question for future work. Generically, there are strong lower bounds (since the cost of observing the final answer on even a single input is Θ(T)\Theta(T)). However, under stronger assumptions, or alternate feedback mechanisms, it may be possible to show benefits of curricula in this realistic setting.

Thanks to the authors for their clarification, which address my concerns. So I will maintain my positive score.

Reviewer_b87rOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies learning to simulate time-homogeneous semiautomata over T steps. The proposed curriculum recursively learns shorter computations and composes their solutions, using boosting to control error accumulation and a sampling procedure to obtain the required distributions over subproblems. In the interactive supervised setting, the sample and supervision-query complexity has subpolynomial dependence on T. In the verifier-based setting, the analysis replaces coverage of correct full-length trajectories with coverage at a shorter block length B. The results are established theoretically. I lean toward acceptance because these are meaningful learning-theoretic contributions, although their implications for practical language-model training are limited by the feedback and optimization assumptions.

Critical strengths
  1. The paper identifies a concrete benefit of compositional curricula: improving the dependence on computation length and enabling learning from short-block coverage. This is a substantive extension beyond using adaptive data selection to improve the dependence on target accuracy in earlier autocurriculum work, and is the main reason for my weak-accept recommendation.

  2. The contribution goes beyond the intuitive observation that long problems can be split into shorter ones. Controlling composition errors while sampling the distributions needed by the recursive learners is a real technical issue. The combination of multiscale boosting and distribution sampling provides a useful algorithmic account of this issue. The supervised reduction can also use a suitable weak next-state learner, making it interesting independently of its language-model motivation.

Critical weaknesses
  1. The feedback model supplies substantial structure. Interactive supervision can return the terminal state of a chosen shorter computation, and the verifier can check subproblems starting from intermediate states. This is stronger access than a verifier that only evaluates the original long task. The short-block coverage condition in Definition 4.4 is also uniform over block inputs, rather than an average-case guarantee on naturally occurring short tasks. Relatedly, the baseline separations compare specific feedback protocols: full-CoT labeling and terminal-only supervision versus interactive intermediate-state queries. They do not establish a separation from every non-curriculum learner with the same interactive access. These distinctions constrain the broader interpretation, even though they do not invalidate the constructive result.

  2. The efficiency guarantees are relative to learning oracles. In particular, Remark D.1 states that the RL procedure requires exact optimization of a trajectory-set loss that differs from the next-token prediction objective. The reported computational cost counts state generations and excludes this optimization. Likewise, the supervised query bound does not include the teacher's computation needed to answer a query. These cost boundaries should be more prominent when discussing efficient training. They are my main reservation about interpreting the results as guarantees for standard SFT or RLVR pipelines, rather than as a conditional theory of compositional learning.

Questions for authors
  1. Please clarify the role of uniform short-block coverage in the existing proof: which step requires coverage over all block inputs, rather than only over distributions induced by the curriculum? This would help assess how restrictive the assumption is.

  2. Please make the optimization assumption in Theorem 4.5 explicit and fix its unresolved cross-reference. Does the current result provide any reduction of the trajectory-set optimization primitive to ordinary next-token learning, or is it an additional oracle whose cost is entirely excluded?

  3. Please state explicitly which baseline separations hold with the same intermediate-state query access, and which rely on restricting the feedback available to the baseline. This clarification matters to the interpretation of the curriculum advantage.

2 comments
AuthorsOpenReview ↗

Response to Reviewer b87r

We thank the reviewer for the positive comments! Our responses are attached inline.

 

[W1a] Does interactive supervision / intermediate rewards supply too much structure?

We believe these feedback models are well motivated for the curriculum setting: the learner requires some mechanism to construct easier subproblems out of harder ones, or else we are subject to lower bounds (due to exponential coverage in the RL setting). Moreover, even though it is possible existentially to combine short subproblems into solutions in our setting, the key challenge is identifying what distribution of subproblems to train on. The underlying challenge is how to address the distribution shift emerging from solving short subproblems constructed from longer problems---a challenge which goes beyond the specific feedback models we consider. We view our setup as a minimal framework where this distribution shift can be isolated and studied.

Of course, extending our results to more general settings where curricula can be constructed without intermediate reward feedback or interactive supervision is an important research question for future work. A simple example where the learner can reconstruct subproblems purely from outcome feedback is when fT(x)f_T (\boldsymbol{x}) encodes a parity function on TT bits. The state st∈0,1s_t \in \\{0,1\\} tracks the running parity of the first tt bits of x\boldsymbol{x}. Given sufficiently many end-to-end examples {(x,fT⋆(x))}\{ (\boldsymbol{x},f^\star_T(\boldsymbol{x}))\}, a learner can compute ft(x′)f_t(\boldsymbol{x}') for any other x′\boldsymbol{x}' via Gaussian Elimination, thereby allowing subproblems to be constructed. However, this exploits the specific algebraic structure of the parity problem. A general understanding of when useful intermediate subproblems can be constructed purely from outcome feedback remains an impactful open question.

 

[W1b] Are the separations general, if they are relative to specific baselines?

Even though our results do not provide a separation between curriculum and every no-curriculum algorithm in the iCoT model, we show that a natural curriculum-based algorithm improves over natural baselines to establish a type of guarantee that was not previously known.

That said, it is possible to show stronger lower bounds than those we present in the paper. In the newly added Proposition C.10 in the paper, we show that no non-adaptive algorithm can improve over full-CoT learning, requiring Ω(T)\Omega(T) iCoT queries to achieve constant error. This gives stronger reasons to use an adaptive curriculum.

 

[W2,Q2] Is the computational oracle for RL reducible to next-token prediction?

Indeed, our work considers a different computational oracle than next-token prediction (i.e., trajectory-set loss). This is not in the current version of the paper, but it is possible to show that RL (given a reference model satisfying sequence-level coverage) can be NP hard even when next-token prediction can be implemented in polynomial time. This means that stronger oracles are required for oracle efficient algorithms in the RL setting. We are happy to include this in the paper if the reviewer feels it would help the presentation of our results.

Why trajectory-set loss? We believe that the trajectory-set loss minimization oracle we consider in the RL setting is natural because it closely related to agnostic next-token prediction (i.e., NTP on datasets which are not realizable). To see this, observe that, for any collection of responses (Di)( D_i ) which are deduplicated (i.e., every response within DiD_i is unique),

\sum_{i=1}^n \mathbb{I} ( \pi_{1:T} (x^i) = D_i ) = \sum_{i=1}^n \sum_{y_{1:T} \in D_i} \mathbb{I} ( \pi_{1:T} (x^i) = y_{1:T} ) \tag{Trajectory-set oracle} \qquad\qquad\qquad\qquad\text{vs.}\ \ \sum_{i=1}^n \sum_{y_{1:T} \in D_i} \left[ \sum_{t=1}^T \mathbb{I} ( \pi_t (x^i) = y_t ) \right] \tag{Agnostic NTP oracle} In the case where the datasets ∪i∈[n]Di\cup_{i \in [n]} D^i is realizable, both of the above equations have the same minimizer (i.e., the oracles coincide in the realizable setting). However, when datasets are not realizable, their minimizers may differ. Thus, we believe that the trajectory-set oracle we consider is natural---it is a simple modification to next-token prediction which allows for oracle-efficient RL algorithms.

AuthorsOpenReview ↗

Response to Reviewer b87r (contd.)

[Q1] Does the proof really require a reference model with uniform coverage over input blocks?

The proof does not require a uniform bound on coverage, and still obtains an exponential improvement over outcome-based RL under a natural average-case notion of coverage. We include a proof of this result in Appendix D.4 of the paper and summarize it below.

 

Assumption. (Average-case block coverage). Let ρˉB\bar{\rho}_B be the distribution over length-BB blocks obtained by splitting an instance x∼ρ\boldsymbol{x} \sim \rho into length-BB blocks and picking one at random (where the initial state is labeled by π⋆\pi^\star). Let CavgC_{\text{avg}} be the sequence-level coverage of πref\pi_{\text{ref}} under ρ‾B\overline{\rho}_B.

Informal Theorem. (learning semiautomata under average-case coverage). Assume πref\pi_{\text{ref}} satisfies the above assumption. Then for ε,δ∈(0,1)\varepsilon,\delta \in (0,1), AutoLearn.RL modified to the average-case coverage setting achieves sample complexity O(d/ε)\mathcal{O} (d/\varepsilon), rollout cost O~(d/ε⋅(T+LCavg))\widetilde{\mathcal{O}} (d/\varepsilon \cdot ( T + L C_{avg})), and verifier calls, O~(dLCavg/ε)\widetilde{\mathcal{O}} (d L C_{avg}/\varepsilon).

 

[Q3] Which baselines do not require intermediate label / verifier feedback?

In the paper, the end-to-end feedback setting in the iSFT setting does not require intermediate feedback (while the full-CoT setting uses it). That said, to connect this question back to our response to [W1b], our results should be interpreted more as highlighting the additional power that intermediate feedback gives, rather than saying that our curriculum-based algorithm is better in absolute terms. A discussion of which oracles use what feedback is already included in the paper in Section 3.4.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Overall Response

We thank all reviewers for their valuable comments. We have updated the draft of the paper (highlighted in red) to include some new results in response to reviewer comments and to improve readability. We summarize these changes below,

  1. With the additional page available during the rebuttal phase, we added an explanation of our main algorithm, AutoLearn, to Section 3.3. We also present a modular addition example (Figure 3) to walk through how our algorithm selects examples to train on.

  2. We prove a new lower bound in the iSFT setting showing that in the worst case, non-adaptive algorithms cannot improve upon full-CoT learning in query complexity. Together with our main result, this strengthens the separation between curriculum-based vs. non-adaptive algorithms, beyond the full-CoT and end-to-end comparions which were already in the paper. This addresses a weakness pointed out by Reviewer b87r and is presented in Appendix C.2.3.

  3. We prove that our main result in the RL setting can be extended from worst-case coverage to average-case notions of coverage. This shows that exponential improvements of curriculum-based approaches over vanilla outcome-based RL are possible under weaker assumptions than uniform block-level coverage. This addresses a weakness pointed out by Reviewer 4Vph and is presented in Appendix D.4.

  4. We add a new set of experimental results to Appendix K, training masked transformers on a modular addition task to compare AutoLearn vs. full-CoT supervision. We observe that training with the curriculum induced by AutoLearn results in a drastic reduction in the number of tokens of supervision required relative to learning from full CoTs. We observe that the curriculum achieves this by focusing on short addition tasks which the current model fares poorly at. This addresses a question of Reviewer 4Vph.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.