acceptodds
Withdrawn from ICLR 2027

A Unified Formal Framework To Predict Length Generalization in Linear RNNs, Transformers and Hybrid Models

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

Abstract

CRASP-based formal frameworks are currently the best known predictors of length generalization in Transformers. However, similar theoretical generalization guarantees do not yet exist for Linear RNNs (LRNNs) and Hybrid models (which combine LRNNs and Transformers), even though much work has characterized their capabilities empirically. To help explain these phenomena, we introduce a unified RASP variant, different slices of which characterize these models' length generalization behavior. We extend previous length generalization frameworks for Transformers to establish guarantees for both LRNNs and Hybrid models. Using this unified framework, we show that all these sequence models length generalize on different classes of tasks, but globally are constrained to sublinear communication complexity and therefore are unlikely to length generalize on copying, addition, and multiplication. We test our framework on standard task suites and find it to be predictive of empirical performance for all models.

Primary area:
learning theory
Keywords:
Length Generalization, Formal Framework, RASP

Reviews

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

The paper attempts to identify a limitation of C-RASP, which, in my understanding, is a commonly used benchmark/prediction task to quantify the length generalization capabilities of different variants of sequence modeling architectures, including causal attention, linear attention and hybrid models.

Unfortunately, I do not fully understand the authors' formal presentation of their proposed HRASP, because of lack of experience in this field.

Critical strengths

I do not have sufficient expertise to answer this question.

Critical weaknesses

I do not have sufficient expertise to answer this question.

Questions for authors

In plain words, what are the fundamental difference between C-RASP and the proposed H-RASP? Why does it matter for evaluating length generalization capabilities?

What is a monoid?

1 comment

We are sorry to hear that the reviewer could not follow our presentation. We thank the reviewer for engaging with us despite not following the details fully.

Difficult to follow despite careful reading.

We would greatly appreciate feedback for how we can make the paper more accessible.

In plain words, what are the fundamental difference between C-RASP and the proposed H-RASP? Why does it matter for evaluating length generalization capabilities?

C-RASP can be thought of as a programming language, and one where if one is able to write a program for a task/function then Transformers can learn length-generalizable solutions to such functions.

These are two completely separate notions, and in a prior result by [1], the existence of a CRASP program for a task was linked to a guarantee of getting length generalization for Transformers on that task (with some simplification assumptions).

The proposed H-RASP is a superset of C-RASP with more primitives in the programming language, and thus we can write richer programs. Secondly, we were able to show in our paper that the existence of an H-RASP program guarantees that Hybrid models (i.e. language models that interleave Transformers and Linear RNNs) will length generalize, thus extending Huang et al's results to an architecture that is being more commonly used in modern LLMs.

What is a monoid?

A monoid is one of the most fundamental algebraic structures. It is a set with a single binary associative operator (which let us say we denote with '.') i.e. for elements a, b, c in a monoid, (a.b).c = a.(b.c)) and an identity element (i.e. if the identity element is e, any other element of the set satisfies the fact that a.e=a). Examples would be Natural numbers with addition as the operator or Strings acting under concatenation.

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

The paper extends C-RASP with finite-monoid prefix products and symbolic matching, proving idealized length-generalization guarantees and a sublinear-communication bound that rules out copying and arithmetic. Experiments on copying variants, arithmetic formats, state tracking, and standard formal-language suites largely agree with the predicted slice memberships.

Critical strengths
  1. The hybrid is an interesting framing. The paper separates three abilities: counting (shared by all three families), finite-monoid prefix products (recurrence), and symbolic matching (attention). The hybrid describes how recurrence and attention compose across layers, rather than just taking the union of their capabilities. For example, a recurrent layer finds the last marker, and an attention layer then retrieves relative to it.
  2. The task designs isolate the impact of each piece. The four copying variants and the two addition serializations make the predicted distinctions concrete and testable. They also show that vocabulary assumptions, access patterns, and input format can matter more than coarse circuit-complexity classes. This is useful for designing and interpreting length-generalization experiments.
Critical weaknesses
  1. About the communication bound: A fixed number of state coordinates does not bound information automatically. An explicit state-precision assumption should fix it.
  2. The unique copy program uses two equalities in one match mask, which the single-equality restriction forbids.
Questions for authors
  1. The assumption: Like weakness 1, what assumption you are using for the communication bound?
  2. As in weakness 2, is the single-equality restriction violated?
5 comments

We thank the reviewer for their thoughtful review, and for appreciating the task designs to isolate the ability of every aspect of the model. We will try to now address the concerns of the reviewer.

About the communication bound: A fixed number of state coordinates does not bound information automatically. An explicit state-precision assumption should fix it.

Thank you to the reviewer for catching this. As said in our response to Reviewer wXCz, we unfortunately missed remarking on a few critical things in our setup that has led to the soundness of the claims being questioned. We fully accept the mistake, and would like to reiterate the main precision assumption that was left implicit in our submitted draft.

We are essentially following Huang et al's [1] choice of precision model for Transformers. In the submitted draft, we mention that intermediate computations use exact arithmetic, where the output of the attention head is rounded to a fixed number of fractional bits. This as Huang et al remarked just means logarithmic precision for the Transformer models. To ensure fair comparisons, we therefore also assume that Linear RNN heads are operating under logarithmic precision as well. This was worded in a really bad manner and has led to rightful soundness concerns. However, we hope that this relieves the major concerns. We have updated this in the latest version and would appreciate knowing whether the reviewer agrees that the theoretical results are indeed sound.

The unique copy program uses two equalities in one match mask, which the single-equality restriction forbids.

The construction for Unique Copy with only a single match was already provided in [2] which we had missed and in that sense our construction here is superfluous and we will remove it from the draft.

However in the process of thinking about a response to this, we in fact were able to think of a way of translating the entire match predicate with multiple equalities at the same time into the Transformer without using the reciprocal activations of [2]. We are excited about this prospect and are working towards updating the draft and will be providing a construction within the next 2 days in an updated version of the draft.

We are very grateful to the reviewer once again for such a close reading of the paper and pointing out these concerns which we hope we have been able to address aptly.

[1] Huang et al. A Formal Framework for Understanding Length Generalization in Transformers, ICLR 2025.

[2] Sarrof et al. On the Ability of Transformers to Verify Plans, ICML 2026

Thank you for the response. Two follow-up questions:

  1. Theorem 3 for hybrids. The log-precision assumption bounds the information in the LRNN state, but attention can still retrieve any earlier token if it is given exact positions, and LRNN layers can compute these by counting?
  2. Unique Copy. Which program does the paper now use, and how does it check the order of the copied tokens? (The program in Sarrof et al. also accepts reordered copies)

Thank you for following up with us.

  1. Right, the construction provided by the reviewer would work, except such a counter-based lookup would have keys whose norms grow with sequence length. Essentially any way of transferring this information from the LRNN layer to the transformer would no longer have uniformly bounded attention inputs. In fact this is one of the reasons with which Huang et al.[1] were able to establish their periodicity lemma as well to show why Transformers can't just do such a thing itself. We acknowledge that this is a bit implicit currently, if the reviewer thinks so, we would be happy to make this reasoning more clear and explicit.

  2. Oh! you are completely right. Yes, that prior construction for Unique Copy is indeed incorrect. So, we will just stick with our original construction that we had in the paper which required 2 matches. Indeed, we have been able to provide a proof of the fact that the whole match predicate can be encoded into Symbolic Limit Transformers (in purple in the draft) and with that our 2 equality match construction is now valid. Thank you again for pointing out this issue, which resulted in a lot of confusion in our work. We hope that, now, everything is correct and up to the reviewer's standard.

We would be happy to hear any more concerns and discuss them.

[1] Huang et al. A Formal Framework for Understanding Length Generalization in Transformers, ICLR 2025.

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

The authors propose new variants of RASP tailored to linear recurrent neural networks (LRNNs/R-RASP) and hybrid transformer/LRNN models (H-RASP). They also propose an idealized inference procedure for LRNN and hybrid models, similar to the inference procedure proposed by Huang et al. (2025) for (limit) transformers. The inference procedure is a proxy for training the model, where the assumption is that training one of these models to reproduce the outputs of a target function will select a model which matches all of the training data and with near-minimum value of a regularization function. Their theoretical results show that under this inference procedure, a LRNN (or hybrid model, respectively) trained to match target functions which belong to R-RASP (H-RASP respectively) will eventually length generalize, i.e., match the target function on inputs longer than the training data. They also give negative theoretical results, e.g. showing functions in other RASP classes on which LRNNs will fail to length generalize without exploding weight norms, or that hybrid models will fail to length generalize when learning target functions with linear communication complexity requirements. Finally, they empirically train LRNN and hybrid models on various tasks and show that their theory gives good practical agreement with when length generalization occurs.

Critical strengths

A RASP equivalent for LRNNs and hybrid LRNN/transformer models is valuable, as these architectures are used in some frontier LLM architectures. The description of the RASP variants is clear, as is the connection to prior work. The empirical results also show excellent agreement with the theoretical predictions, and in the case where there is a theory/practice gap, a plausible explanation is given.

Critical weaknesses

I believe there are some major flaws with the theoretical results.

First, the proof provided for Theorem 2 is more of a sketch than a rigorous proof. Furthermore, the reasoning in the sketch contradicts statements made in the proof of Theorem 1. In particular, in the informal argument given for Theorem 2, it is stated that (lines 1335-1337):

"Note that the input can have any character appearing in it till the last character, thus the LRNN model has no way of knowing which cj to keep in memory, and it has to keep all the distinct tokens seen in an input in its hidden state to be able to solve the underlying task...the only way for LRNNs to solve this task is to keep maintaining an increasing amount of memory, LRNNs fail to learn to solve this task length generalizably."

However, in the proof of Theorem 1 (lines 1305-1306), it is stated that the hidden state can encode the output of the counting operation without the local constraint, which is unbounded. The earlier setup in Section 2.1 also allows exact computations in intermediate states, in line with the proof of Theorem 1. Thus the argument for Theorem 2 does not seem to hold as stated. For a similar reason, the informal argument given for Theorem 3 also does not hold, since the hidden states can store unbounded integers and therefore unbounded information.

Furthermore, under the current assumptions of Theorem 2, the theorem does in fact hold but for somewhat vacuous reasons which would also extend to other languages which should be expressible by the LRNN. In particular, the regularizer includes the Frobenius norm of the embedding matrix. In finite precision, the norm of the embeddings have a minimum nonzero value, so if inference procedure returns a sequence of models with bounded regularizer, then there can be at most a finite number of symbols in C\mathcal{C} with nonzero embedding. Thus, models satisfying the conditions of Theorem 2 will not be able to length generalize on target functions which need to be able to distinguish between an unbounded number of symbols in C\mathcal{C}.

Minor: F(Σ)\mathcal{F}(\Sigma) is used several times but never explicitly defined in the paper.

Questions for authors

Please address the issues with the theoretical results discussed in the weaknesses section.

1 comment

We are glad to note that the reviewer found our presentation clear and finds the overall framework we are proposing compelling. We are also glad that the reviewer notes the predictive power of our theoretical predictions.

We are also thankful to the reviewer for their constructive criticism and would like to respond to each of the raised concerns. The soundness concerns are totally valid, as our precision assumption was not stated clearly (which caused confusion for Reviewer ywoF as well).

We follow Huang et al's [1] choice precision model and so all learned parameters have finite precision. Additionally in the submitted draft, we mentioned that intermediate computations use exact arithmetic, where the output of the attention head is rounded to a fixed number of fractional bits. This was a bit misleading. Intermediate exact arithmetic with such fractional rounding in the presence of log scaling just led to logarithmic precision for the Transformer model used by Huang et al. To ensure fair comparisons, we therefore also assume that Linear RNN heads are operating under logarithmic precision as well. This was worded in a really bad manner and has led to rightful soundness concerns. However, we hope that this clarification relieves the major concerns of the reviewer and we thank you again for pointing this out.

First, the proof provided for Theorem 2 is more of a sketch than a rigorous proof.

We wanted to increase the readability of the proof and hence have stated it in simpler language. We realize that we trade off rigor in favour for readability and have therefore updated the proof to be stated in more formal terms, where we first establish the available memory for LRNNs (Lemma 5) and then show why the match predicate might require more than the memory available. The argument is the same as before, but simply stated more formally.

Furthermore, the reasoning in the sketch contradicts statements made in the proof of Theorem 1 ---

maintaining an increasing amount of memory Theorem 1 (lines 1305-1306), it is stated that the hidden state can encode the output of the counting operation without the local constraint For a similar reason, the informal argument given for Theorem 3 also does not hold, since the hidden states can store unbounded integers

We hope now that with the correctly mentioned precision model, the reviewer's concerns about the correctness is resolved.

Essentially in all of the positive results, the information stored never required more than log precision of memory, and in the impossibility results, we require memory that is linear in the input length.

regularizer includes the Frobenius norm of the embedding matrix. In finite precision, the norm of the embeddings have a minimum nonzero value, so if inference procedure returns a sequence of models with bounded regularizer, then there can be at most a finite number of symbols in with nonzero embedding.

That is true, essentially our Theorem 2 is currently true for 'boring' reasons. However, our theorems are somewhat robust to how we treat the embeddings via the regularizer. All of our theoretical results also hold if the regularizer for the Linear RNNs bounds the euclidean norm of each entry of the embedding matrix (i.e. max⁡w∈Ω∣∣E(w)∣∣2\max_{w \in \Omega} || E(w) ||_2) instead of the overall embedding table. In fact this way, we can make the regularizer for LRNNs closer to the one used for Transformers. Importantly this change gets rid of the vacuous reasons for the theorem being correct, and yet at the same time preserves the theorem statements and implications. We have made these changes in the PDF already and updated the resulting proof. We agree with the reviewer that perhaps the current way of treating the embeddings was less interesting and hope that this new choice and the robustness of our theorem statement makes our stated result more convincing to the reviewer.

We in fact also conduct some experiments to further check if the intuition provided by our theory can be further stress tested. To this end, we increase the memory of the LRNN being trained on Unique Copy, as the core bottleneck in the case of a growing alphabet is the memory required to solve this task. Indeed LRNNs length generalize on 3x the smaller lengths (length=150) with a bigger memory (dimension=256) but not with dimension=64. LRNNs start to fail when trained at larger lengths (length=250 on) and evaluated on 3x. In contrast Hybrid models keep performing the task perfectly upto lengths of 1500 even with smaller dimensions of 64.

We are grateful once again to the reviewer for their thoughtful review. This led to minimal albeit crucial changes in the draft (marked in blue), and we agree that they definitely help convey the soundness of the results more convincingly.

We would appreciate any further feedback on the changes made by us.

[1] Huang et al. A Formal Framework for Understanding Length Generalization in Transformers, ICLR 2025.

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

Related papers

Discussion (0)

Sign in to comment.