acceptodds
Withdrawn from ICLR 2027

Training Recursive Language Models for Hierarchical Generalization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Language models may excel at applying familiar reasoning patterns yet struggle when those patterns must be combined in a novel way. Recursive inference offers a natural way to tackle novel compositions by decomposing them into potentially familiar subproblems and composing their results. Prior work has largely studied recursion for long-context processing and efficient inference, leaving its effect on compositional generalization unclear. We introduce a controlled Countdown benchmark for hierarchical compositional generalization and compare recursive and linearized execution on the same reasoning trajectories with matched training and inference token budgets. Recursive inference improves accuracy on held-out compositions up to while generating about 40% fewer tokens. Separated subproblem contexts also permit training on reasoning trajectories whose total length greatly exceeds one context window, and extending search may further help by exploring alternative ways to combine these familiar constituents. Training on wider recursive trajectories and allowing wider search at inference increases compositional accuracy by , whereas doubling the generation limit yields only a 10% relative increase. Allocating search budgets across recursion levels improves the accuracy–compute trade-off, while mixing search budgets during training achieves similar quality with roughly half as many generated tokens. Finally, we build an adaptive curriculum by utilizing the compositional relationships between the tasks, doubling the held-out compositional accuracy.

Primary area:
foundation or frontier models, including LLMs
Keywords:
recursive language model, compositional generalization

Reviews

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

This paper studies the compositional generalization ability of recursive language models (RLMs), with a focus on hierarchical reasoning tasks. Specifically, the authors first introduce a controlled synthetic benchmark based on Countdown tasks, where the evaluation splits explicitly test novel combinations of components observed during training. Experiments with SmolLM2-135M, Gemma3-270M, and SmolLM2-1.7B consistently show that recursive execution substantially outperforms the linearized baseline in compositional generalization. The authors further investigate the effect of inference-time computation and find that increasing recursive search width (i.e., the number of subcalls) leads to greater performance improvements than increasing the output length of linearized baselines. Finally, they propose an adaptive curriculum method to further improve compositional generalization, assuming access to held-out validation compositions.

Critical strengths
  • The paper investigates an interesting question: whether recursive language models (RLMs) can improve hierarchical compositional generalization. As interest grows in using external scaffolding and recursive inference to solve problems that models struggle to solve on their own, this work provides a useful perspective on when and why RLM-style approaches may be beneficial.

  • The paper introduces a controlled Countdown benchmark that could be useful for future research on hierarchical compositional reasoning. The empirical results are promising, showing substantial improvements in compositional generalization over the linearized baseline. The additional investigations into search budget allocation and curriculum learning also provide interesting insights.

Critical weaknesses
  • The study is conducted exclusively on the controlled Countdown task, and it remains unclear whether the observed improvements in hierarchical compositional generalization would transfer to more realistic reasoning tasks. It is also unclear how the proposed composition-aware curriculum could be applied to realistic LLM training scenarios, where the compositional relationships between tasks are typically not explicitly available. This limits the broader applicability of the findings.
  • The experiments are conducted on relatively small models, with SmolLM2-1.7B being the largest. It would be important to verify whether the conclusions hold for more capable contemporary models, such as Qwen3 models at similar scales (e.g., 1.7B or 4B), or larger models (e.g., Qwen3-8B), as evaluated in the original RLM work [1].

[1] Alex L. Zhang, Tim Kraska, and Omar Khattab. Recursive Language Models. arXiv preprint arXiv:2512.24601, 2026.

Questions for authors
  • The proposed adaptive curriculum assumes access to the compositional structures and per-pattern errors of held-out validation tasks. Do the authors have insights into how this method could apply to realistic LLM training scenarios where such information is typically unavailable? Or does the method have to rely on knowing the target validation distribution?
Reviewer_oxv4OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper show that recursive inference is more effective than linearized search training in achieving efficient hierarchical compositional generalization with experiments on a controlled Countdown benchmark. In addition, the authors further propose an adaptive curriculum learning approach to adjust the allocation of training compute for recursive models, achieving substantial empirical improvements.

Critical strengths
  1. I find the introduction of the task setting and the associated definitions very clear and well-structured, making the paper accessible and reader-friendly.

  2. The authors design a curriculum learning strategy that allocates training budgets based on the dependencies and interactions between different patterns. I find the theoretical modeling and analysis underlying this approach particularly compelling.

  3. The experiments are clearly structured and presented in a logical manner, and the conclusions are well supported by the results within the experimental setting considered in the paper.

Critical weaknesses
  1. The experimental scope of the paper appears somewhat limited. The adopted countdown benchmark uses a fixed and relatively small set of basic operations and a limited number of leaf nodes. It remains unclear whether the benefits of recursive inference can generalize to problems of larger scales and greater complexity. Furthermore, the Countdown benchmark focuses mainly on basic arithmetic operations. If possible, evaluating on other types of compositional tasks (such as program execution) would provide further support for the experimental conclusions.

  2. The theoretical modeling and analysis of the curriculum learning approach is reasonable and well-motivated. I have the following questions:

a. The computation of the allocation vector u seems to rely heavily on accurate estimates of the model's current performance on different patterns. I am curious about how the proposed approach handle the patterns that have been rarely observed or not encountered during training, for which accuracy estimates may be relatively noisy. A more detailed explanation of how such cases are handled would be helpful.

b. The curriculum learning approach also leverages structural information relating the training and validation patterns to compute R_t Beyond the training pattern data. This appears to implicitly introduce additional learning preferences toward novel patterns in the validation set into the training process. It would be helpful to further clarify the extent to which the proposed approach depends on such structural priors.

  1. The paper could benefit from further discussion of how the insights and findings from this study might translate into improvements for existing LLMs in practical applications.
Questions for authors

see Weakness.

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

The paper builds a controlled Countdown benchmark for hierarchical compositional generalization and compares recursive against linearized execution with matched search supervision and training budgets. Recursive execution improves held-out compositional accuracy across three models while generating fewer tokens. Follow-up experiments on SmolLM2-135M cover search-budget scaling, call allocation across recursion levels, mixed-budget training, and a composition-aware curriculum that roughly doubles compositional accuracy.

Critical strengths

The evaluation is the strongest part of the paper. Held-out problems are filtered so that no training pattern can solve them, which makes the benchmark a real test of novel composition rather than new numerical instances of old structure. The recursive-vs-linearized comparison is also convincing as far as it goes: the gain holds across three models under matched supervision, with fewer generated tokens, and the compositional ratios add evidence beyond raw accuracy.

Critical weaknesses

(1) The curriculum’s contribution is not isolated. Table 3 changes two things at once: the adaptive allocation rule and the subtrajectory sampling scheme. Appendix A.2 shows that sampling matters, but only with the curriculum enabled; there is no run that pairs the same sampling with a nonadaptive allocation. So I cannot tell how much of the .042 -> .083 gain comes from the allocation rule itself and that rule is what RQ3 is about. As written, RQ3 is not answered fully.

(2) Uncertainty is characterized incompletely. Tables 1-3 give point estimates with no error bars and no clearly stated seed counts. Appendix A.2 bootstraps over patterns but uses one run per setting, so training variability is unmeasured. This matters most where the differences are small, the budget-allocation comparisons in Table 2 and the curriculum gain, though it does not undermine the direction of the recursive-vs-linearized result.

Questions for authors
  1. The missing control: what does nonadaptive allocation achieve under the same subtrajectory sampling, token budget, and checkpoint selection as the curriculum? This regards RQ3.

  2. How many training seeds underlie Tables 1-3? Can you report paired, pattern-level confidence intervals for the main differences, and any across-seed numbers for the curriculum comparison?

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

Related papers

Discussion (0)

Sign in to comment.