- 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
-
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.
-
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.
-
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
- 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?
- 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).
- 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
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.
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:
[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:
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 T tasks specified by a user.
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 T 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 S5 / 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)