acceptodds
Under review as a conference paper at ICLR 2027

Recursive Language Models Generalize Out of Domain

Abstract

We study when limiting what a language model can see improves learning. We compare standard CoT, the more general learner that reads the full trace, with recursive language models, which restricts itself by solving each subtask in an isolated context. In-distribution, this generality comes for free: CoT can efficiently simulate the recursive rule, so the IID generalization guarantee changes only by a constant factor, and recursion does not offer much. But out of domain, CoT can fit training by relying on context outside the current subtask, i.e. a shortcut that breaks once those tokens change; recursive context isolation rules out this failure mode. Even though CoT's class still covers the recursive rule, simplicity bias picks the shortcut over the truth. Thus, to go beyond distributional accuracy and truly reason, covering the right rule is not enough—in contrast to classical learning theory.

Primary area:
foundation or frontier models, including LLMs
Keywords:
recursive language models, out-of-domain generalization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_8m7POpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the generalization difference between standard chain-of-thought (CoT) reasoning and recursive language models (RMs), focusing on whether restricting context access can improve out-of-domain (OOD) generalization. The authors develop an MDL-based theoretical framework suggesting that, while CoT can efficiently represent recursive rules and achieve comparable IID generalization, access to the full reasoning trace may enable simpler shortcut solutions that fail under distribution shift. In contrast, RM isolates subproblems and therefore removes some of these shortcut opportunities. Controlled symbolic experiments are provided to support the theoretical arguments.

Critical strengths
  1. The paper studies an interesting and relatively underexplored question regarding the relationship between context accessibility, simplicity bias, and OOD generalization.
  2. The comparison between IID and OOD generalization provides an interesting perspective on why greater expressiveness or access to more information may not always improve generalization.
  3. The paper attempts to connect recursive reasoning, MDL, shortcut learning, and invariance within a unified theoretical framework.
Critical weaknesses
  1. The theoretical motivation and presentation could be substantially improved. The transition from simplicity bias to the MDL formulation is rather abrupt, and the paper introduces many definitions and intermediate constructs for concepts that are often relatively intuitive. This makes the genuinely non-trivial theoretical contributions difficult to identify. Given the amount of formalism, a high-level roadmap showing the dependencies among the definitions, propositions, and theorems would greatly improve readability.

  2. The scope of the theoretical OOD claim appears narrower than the paper’s broader framing. The invariance analysis primarily concerns changes to the surrounding context while preserving a visible subproblem encountered during training, rather than generalization to genuinely unseen subproblems or semantic domains. The distinction between this form of context shift and more general OOD generalization should be made clearer.

  3. The empirical evidence is limited relative to the breadth of the conclusions. The experiments rely primarily on a controlled symbolic expression-evaluation testbed, with several OOD shifts and shortcuts explicitly constructed to reflect the theoretical setting. While useful for mechanism verification, this alone provides limited evidence that the conclusions extend to realistic reasoning tasks, natural distribution shifts, or pretrained LLMs.

  4. The generality beyond the specific CoT–RM comparison remains unclear. Although the paper frames context restriction and specificity as general principles, the analysis focuses almost exclusively on RM. Comparisons with alternative context-control mechanisms, such as masking, pruning, or restricted-context CoT, would help determine whether the findings reflect a general principle or properties specific to RM.

  5. The current comparison does not cleanly isolate context isolation as the causal factor. As the paper itself acknowledges, visibility, sequence segmentation, and positional exposure change simultaneously between CoT and RM. More controlled ablations are needed before attributing the OOD improvements specifically to context isolation.

  6. The connection between the MDL explanation and the empirical results remains somewhat indirect. The theory attributes failure to a preference for shorter shortcut rules, whereas the experiments mainly demonstrate that CoT can exploit planted shortcuts. Stronger empirical evidence connecting the learned shortcuts to the proposed simplicity/description-length mechanism would make the theoretical explanation more convincing.

  7. The manuscript would benefit from more careful proofreading and formatting consistency. There are several inconsistencies in notation and capitalization throughout the paper, such as “Fig.” vs. “fig.” and “IID” vs. “iid”. The authors should carefully check and standardize these expressions throughout the manuscript.

Questions for authors

No

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

This paper studies in-distribution (ID) and out-of-distribution (OOD) generalization of recursive language models (RM) against standard chain-of-thought (CoT). In RM, each subproblem in the sequence is solved in an isolated context, and only the answer is passed to the parent context. The authors show that CoT can mimic this behavior with constant extra depth and a constant-factor increase in parameters, so both learners have comparable ID guarantees. However, CoT can fit the training data with shortcut rules that rely on tokens outside the current subproblem, which fail OOD. Authors demonstrate this behavior by using a 6-layer Transformer on synthetic arithmetic expressions (Figure 1 contains an example): CoT matches RM with enough data in ID evaluation, but RM is more robust to longer sequences and deeper recursion than those seen at training time. The authors argue that representing the correct rule is not enough to achieve OOD reasoning: instead, limiting what the model sees helps OOD generalization.

Critical strengths
  • The paper establishes the relation between RM and CoT ID performance: CoT has comparable ID guarantees under a constant-factor increase in parameters.
  • Results show that RM is robust in the OOD experimental setup, while CoT falls into reasoning shortcuts.
  • The paper provides evidence that OOD generalization can be improved when limiting the context the model sees.
Critical weaknesses

In general, this paper is very hard to follow, and its quality suffers a lot from relying on too abstract definitions (replacing simple statements) when experiments do not actually need them. I also found inconsistencies in experiments and issues hard to address in the methodology:

  1. The OOD definition seems unfair in CoT against RM: OOD traces are mostly frames seen in training but just expanded to form longer sequences. For RM, these samples are in-distribution at frame level (e.g. the operator add(2,1)), while for CoT they are genuinely OOD. CoT is the one being asked to extrapolate while RM keeps reasoning in small fragments. This is something admitted in L420 "many OOD executions still reuse locally familiar subproblems for RM". The paper is then not measuring RM's OOD generalization but CoT's. A fair OOD setting for RM would be evaluating on frames or combinations of symbols not seen in training.

  2. Positional exposure differs between CoT and RM, harming CoT in OOD: Both models use RoPE, but CoT traces in OOD are longer than any training sequence, so CoT is asked to reason on unseen positions. This is something that does not happen in RM since each individual frame restarts the positional encoding. Table 1 then cannot attribute the gap only to shortcuts, since failure to extrapolate to unseen positions is a known phenomenon on its own. The authors acknowledge this confound on L470-471 ("Visibility, sequence segmentation, and positional exposure therefore vary together").

  3. The theory is close to tautological and barely connected to the experiments: Authors formalize their analysis via the Minimum Description Length (MDL) view (an MDL learner returns the shortest predictor consistent with training data), and build most of their definitions and results on this principle. However, this MDL learner seems not possible to compute with Transformers or machine learning training, so I fail to understand why this formalization is introduced when it does not help explain the experiments. Moreover, the key OOD result (Theorem 6) only holds if a strictly shorter shortcut rule exists, a condition that is never verified.

  4. Experiments are limited to synthetic tasks that might not occur naturally in real datasets: The claims of the paper are supported in a synthetic task where the real capabilities of Transformers are limited to create an artificial OOD environment. There is no discussion on whether these shortcuts arise naturally in realistic language datasets, where ambiguity is also a factor that increases complexity for both models.

  5. Recursion is not learned but given by an oracle: Both learners are trained with teacher forcing on interpreter-generated traces with <call>/<return> tokens. RM never learns how to decompose a problem, so recursion and frame isolation are given by an oracle, not learned by the network. The OOD robustness is therefore mostly a property of a hard-coded experimental design, while the hard part of RMs (learning how to decompose) is not addressed.

  6. Clarity and presentation: Although there are many examples, these are the ones in the intro:

    • No concrete ID vs OOD example anywhere in the intro. The core idea fits in one line (e.g. train on add(square(2),1)-style short expressions, test on accum_sum(9,0) that unfolds into a long, deep trace).
    • L041–047 report results ("RM needs fewer samples…", "CoT collapses on traces only modestly longer than training") before the reader knows what the task, the samples, or the distribution shift are. Define the setting before summarizing results or explain with an example.
    • Abstract claims are stacked before any object is defined: "simplicity bias", "invariance", "the recursive rule is compactly contained inside CoT", "description-length term".
    • L048 "the usual generality-over-specificity argument": not a standard name. It is loosely motivated in L029–032 (Sutton 2019; Rissanen; Grünwald; Shalev-Shwartz & Ben-David), but then referred to as "the usual ... argument" as if established.
    • L050–051 "The corresponding IID upper bound changes only by a constant-factor overhead in the description-length term" is very hard to understand without the MDL background. Plain-language version: "the generalization bound for CoT is at most a constant factor worse than for RM, so CoT needs at most ~C× more data in the worst case."
  7. Title and scope: Recursive Language Models where initially proposed for natural language modeling. The title of the paper suggests conclusions that can be misleading. The experiments come from results in a synthetic task with a very small vocabulary, not natural language. The intro links the work to deployed agent systems (L085–086, citing Anthropic and OpenAI blog posts) without any experiment in such settings.

  8. Formalism and notation: Heavy formalism for a simple ideas, all definitions are hard to follow for the LLM audience the paper targets. In general, having a simple intuitive sentence explaining the definition would help readability.

Questions for authors
  1. Does the Table 1 change if the positional encodings for the CoT baseline are modified to make them robust to unseen positions?
  2. Can you show a shortcut emerging without being planted on a task not constructed for it?
  3. Is there a task where context isolation hurts? How does RM perform there?
  4. Is MDL meant as a faithful model of SGD training or as an illustration?
  5. What does Theorem 6 predict beyond the existing shortcut-learning / invariance literature?
  6. Could you give an intuitive sentence of what each definition/theorem is stating with an example?
Reviewer_x9ojOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper defends the idea that decomposing tasks into subtasks with recursive models in isolated contexts can reduce reliance on misleading patterns in the surrounding execution history of a CoT. This helps the model learn local rules that allow the model to generalize better in its training.

Critical strengths

Interesting research question. The paper examines whether other subproblems’ internal work supplies shortcuts that let a model fit training data without learning reusable reasoning rules.

Useful theoretical framework. It formalizes how context isolation protects predictions when surrounding history changes.

Experiments supporting the proposed mechanism. Planted-shortcut experiments provide evidence that CoT predictions follow misleading trace cues.

Critical weaknesses
  • The tasks they run the experiments on are structured and easy to decompose into subtasks. Would be interesting to see experiments on more complicated tasks in multi-agent environments.
  • Modern problems aren’t always easily separable into smaller tasks. Even when they are, a subproblem might need information from other parts of the problem.
  • If there’s a shortcut inside the subproblem, it seems like the recursive model can still exploit it. So I feel like there can still be undesired patterns just inside the local context.
  • I feel like the framework of subagents is more natural than talking about recursive models and CoT. Those terms feel broad. Talking explicitly about function composition (like f compose g) for the tasks could also make the theory a bit easier to follow.
Questions for authors
  1. Would this work in a multi-agent environment? Like having subagents for instance?
  2. How do we decompose complicated problems when the subtasks aren’t cleanly separable?
  3. What are the tradeoffs between using CoT and recursive models in terms of compute and latency? Are these things to consider?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.