A Formal Framework for Understanding Length Generalization in Transformers

Authors: Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, Michael Hahn
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: transformers, theory, length generalization, expressivity, analysis, algorithmic reasoning, systematic generalization, formal languages

Abstract:
A major challenge for transformers is generalizing to sequences longer than those observed during training. While previous works have empirically shown that transformers can either succeed or fail at length generalization depending on the task, theoretical understanding of this phenomenon remains limited. In this work, we introduce a rigorous theoretical framework to analyze length generalization in causal transformers with learnable absolute positional encodings. In particular, we characterize those functions that are identifiable in the limit from sufficiently long inputs with absolute positional encodings under an idealized inference scheme using a norm-based regularizer. This enables us to prove the possibility of length generalization for a rich family of problems. We experimentally validate the theory as a predictor of success and failure of length generalization across a range of algorithmic and formal language tasks. Our theory not only explains a broad set of empirical observations but also opens the way to provably predicting length generalization capabilities in transformers.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730297202902

thread_type:
official_review

<thread_object>
creator: reviewer_h3pw

<content>
summary:
In the recent years, with the surge of LLMs and transformers, there has been an increasing interest to formally understand the generalization failures of transformer. A notorious and common failure mode that is often mentioned in the literature pertains to length generalization, where the model is trained on sequences of certain length, and then is tested to longer sequences. Many works have shown the failures of modern architectures on a range of tasks (most popular ones being parity) and others have come up with strategies to fix the failures (e.g., changes in positional embeddings). In recent work, Zhou et al., authors proposed an insightful conjecture, the RASP-L conjecture, that aims to dilineates the tasks that are easy for transformers to learn and length generalize on, and then tasks that continue to be hard for transformers. While the conjecture was empirically backed, theoretical justifications for the same have been lacking. In this work, the authors aim to formalize and provide a theoretical justification to the RASP-L conjecture. 

The authors study two types of positional encodings -- no positional encodings, and absolute positional encodings. When dealing with absolute positional encodings the number of parameters grow with length of the input. To address this challenge, the authors introduce a new object, the limit transformer. This transformer encapsulates the behavior of transformers on longer and longer sequences into a single object. The authors define an idealized inference procedure, which searches for the transformer that minimizes the risk along with a regularization constraint. The regularization constraint is a special one, i.e., it is not the standard constraint based on purely say the l2 norm of the weights. With these constraints in place, the authors show that if the ideal function f is expressable in a limit transformer that satisfies two properties -- Local and Periodic, then the transformer is able to learn the function f and length generalize on it. In the second half of the paper, the authors show that for every program C-RASP[phi, Psi) with local and periodic phi and Psi respectively, there exists a limit transformer that accepts the same set of strings that P accepts. The authors also provide communication complexity based arguments to explain the limits of limit transformers. Finally, the authors conduct experiments to match the predictions of the theory.

strengths:
1. The authors tackle a hard problem, i.e., providing a formal justification of RASP conjecture for multi-block transformer models. This is both a hard problem and an important one. 
2. The authors have been creative in several aspects of the paper -- i) the regularization constraints that have been imposed seem particularly important to the inference procedure's success, ii) the construction of the limit transformer, iii) the tight connection between the limit transformer and the C-RASP language from Yang and Chiang.
3. The main body of the paper is nicely written and does a nice job of getting to the main results quite fast.

weaknesses:
There are quite a few concerns that I have for various parts of the paper. My current score is a reflection of these weaknesses. I would be happy to change my score if the authors can provide satisfactory explanations and no other major concerns appear in the course of discussion. 

1. **No Positional Encoding vs. Absolute Positional Encoding**:  In the current work, the authors went through great detail to construct limit transformer with the idea that limit transformer can encapsulate longer and longer transformers into one limiting object. The first thing that bothers me is that if we take no positional encodings then we do not need this object. The authors do not explain the need of limiting transformer in the context of NoPE as there is no growth in number of parameters anymore that limit transformer needs to cater to. 
The second thing that bothers me is that from an expressivity point of view, the NoPE based transformer can express APE up to a large length. So why can't we use
Theorem 1  (https://proceedings.neurips.cc/paper_files/paper/2023/file/4e85362c02172c0c6567ce593122d31c-Paper-Conference.pdf) from this work. This work essentially is arguing that NoPE can approximate APE (or RoPE). 

2. **About invariance to offsets and regularization** 
     a) The authors introduce the constraint that the transformer should be invariant to offsets, i.e., if the problem appears at different locations in the context window then the solution should not change. This constraint is not explicitly enforced.  
     b)  The authors also have an idealized inference procedure, where the regularizer has been introduced for the purpose of theory. The authors argue that there is an implicit bias towards small values of it at initialization. I don't quite see how. Also, this regularizer is also not explicitly enforced. 
  Since there is quite some gap between the theory and expmts, what do you think is the explanation for this gap? 

3. **Regarding the definition of limit transformers**
     a) The limit transformer is introduced in Definition 2. The term y_i(l) in equation (6), is it the same as how it was defined in equation 4. If so, then does it already have positional encoding in it like in equation (1). If so, then how does the function phi that is introduced additionally absorb the terms that involve inner product of two different positional encodings. It feels if y_i^(0) already had positional encodings in it then won't the first term in equation 6 already take care of the stuff. 

   b) Is the rest of the construction of limit transformer same as standard transformer and the only difference is equation (6)? I ask this because following equation (6), we are not told what happens to attention logits. 

   c) In point 2 in the definition u say that the positional encodings p_i are encoded in finite precision. If that is the case, then when we increase the length to arbitrary large values, the positional encodings start overlapping and we only have finitely many positional encodings.    This does not address the increase in the parameter count issue that the author state was the very reason to define the limit transformer. If we are happy with finitely many positional encodings, then why not just do some periodic encodings in the standard transformer? Also, if we are happy to do everything with finitely many positonal encodings then this goes back to my first concern on NoPE, we can operate with NoPE, express finitely many positional encodings, and simplify the whole story right? 

 
4. **Concerning periodic and local in definition 3.** In Definition 3, you state that phi_l,h is translation-invariant and local. You also stated that phi_l,h expresses the inner product involving positional encodings. This translates into a constraint on the positional encodings. This creates confusions. The authors should be more clear on this whole connection in the main body. 

5. **About the hypothesis class definition 4** In definition 4, you say that each product function involving position encoding is translation invariant. You also say that each function involving exactly one product function is translation invariant. These constraints seem very restrictive. Is there a reason to believe that imposition of these constraints is not over simplifying the problem somehow? Are these constraints implying offset invariant condition? I think offset invariance on its own was reasonable but this seems not very digestable. I would appreciate if authors gave more insights into why these constraints are not unreasonable? Also, some numerical insights into what it means to enforce these constraints? This goes back to my point 2. If you see point 2, I state that there is gap between theory and expmts. In this case, the theory would require some of these constraints, which how do u really enforce? Perhaps these constraints are strong sufficient conditions for length generalization? and far from necessary? Is offset invariance a necessary condition btw for length generalization?

6. **On the regularizer in definition 5** 
    a) After definition 5, you state that the idea of this regularizer is to discourage attention between far-away positions that do not appear together during training, which could hamper length generalization. At what point do you use this insight in the proofs. For instance in Lemma  17 how does it come up? I don't quite see it. Also, since all positions are equally penalized in this regularizer, why would things far off be more penalized? Also, the justification based on initialization making the regularizer small is not fully clear. 

   b) If we use NoPE positional encoding, then p_i is set to zero for all i. As a result, I don't quite understand the role of the regularizer anymore. Since the regularizer is supposed to penalize far away positions, those positions don't seem distinguisable under the regularizer as p_i is set to zero. Further, if p_i is set to zero, then what is the role of the phi function in equation (6), and eventually why do we need the limit transformer? 

7. **On phi function** In the line 260, you indicate that for phi function, we need to only care abt it its values such as phi(1,1), phi(1,2),..phi(1,tau). The values above the diagonal are taken care of by translation invariance, but what abt the values below the diagonal, i.e., phi(2,1)..I don't think you assume symmetry, do you? 

8. **Minor remark on line 326/327** Shouldn't the Q_a in the RHS be Q_a(j) and not Q_a(i)?

9. **Notation remark on Theorem 9**. In an unfortunate use of notation, u call Psi function local and Phi function periodic. Earlier u had used phi for local in the definition 3. 

10. Since the results from the work hold for NoPE positional embeddings. From Theorem 2 in https://proceedings.neurips.cc/paper_files/paper/2023/file/4e85362c02172c0c6567ce593122d31c-Paper-Conference.pdf, the results should extend to relative positional encodings too?

11. Currently the results require a large N_0, which practically speaking can be very large. The authors do mention this limitation. While I am not expecting a bound of any sort in this work, I want to understand the consequences of the results better. The current machinery in this work (if correct), seems to indicate that allowing for a very large N_0 and some strong constraints (periodic, local on hypothesis class), length generalization is achievable for a large N_0 seen during training. If this N_0 from the theory is quite large, then would you say that research in this should try to explain why can transformers do it with a much smaller N_0 than theory predicts? I want to understand the hunch of the authors here. If one tries to bound N_0, then would we run the risk of vaccuous bounds?


12. **Concerns on the proof of Lemma 17**:  
    a) In line 976 you say there are only a finitely many settings traversed by the limit transformer \tilde{T}_i. Why is this the case? Can you properly justify?

      b) In equation 9, you say that we select an R(Tn) that is less than 1/n + inf (R(T)). In line 981, you argue that R(Tn) should converge because inf R(Tn) is bounded and monotonically increasing. This argument only tells that the RHS in equation (9) converges, which is the upper bound. Why does it imply that the LHS converges? You crucially use the existence of this limit in equation (14).

     c) In line 995, you say that lim D_v_i(v_i) is D_0. Why does this limit exist? 

     d) Below equation 17, you state "As this function is monotonically increasing, and as phi_{l,h} has bounded precision, there must be t_infty..." Why does this hold true? I don't quite follow. 

      e) In line 1010-1017, you construct a sequence of T'n satisfying certain properties. Why does this have to exist? For instance why is  D_{vi(n)}(n) = D_{infty}(n) true?

      f) The phi_l,h(i,j) in equation (10) should also bear the index n as it would be different for each limit transformer. This makes the rest of the stuff bit confusing.  For instance, you define D_n(tau) in line 984. Why would it be the case that tau can be larger than n in the summation? Since positional embeddings for that transformer would only be defined up to n right? 

      g) I do not follow the inequality in line 1044?  

      h) In line 1049-1052, you say that set of functions traversed becomes stationary, what do u precisely mean here? 

13. In line 1121 to 1127, how does the C logN fall out. Do you mean that since you partition stuff into N positions and that takes log N bits to compute, we get C log N?


14. I realize that there was one question I had forgotten to add in the above list. In the Definition 4 of your hypothesis class, I do not see any constraint on positional encodings being periodic. Does periodicity fall out as a consequence of the offset independent constraint you add later in the definition? What confuses me quite a bit is that while your transformer is not periodic but your limit transformer is periodic. How is it that a transformer with non-periodic positional encodings with an ever growing context window is captured by another transformer like object with periodic positional encodings? And relatedly why not just have periodic positional encodings on the original transformer to begin with instead of the very strong offset independence conditions in definition 4.

questions:
Please see weakness section, where I list both the weaknesses and questions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730653385508

thread_type:
official_review

<thread_object>
creator: reviewer_odfa

<content>
summary:
**Update after rebuttal:**
The authors have clarified my questions and made improvements to the presentation of the main manuscript (though it remains a very long paper of course, with some important parts in the appendix, hence I will leave my 'Presentation' rating on 2). I am now more confident that the work is important and is ready to be presented and discussed with the wider ML community. I would now raise my score to a 7, but ICLR does not allow this score this year. I do think that some weaknesses remain, and that the paper does not quite hit an 8. But for the sake of expressing a clear opinion for the decision-making process, I am raising to an 8 (as the only available option), but will keep my confidence low to indirectly indicate that the score is a bit inflated.

---

This paper formally defines a function class, implicitly via the construction of the Limit Transformer, and shows that length generalization with transformers (of arbitrary context length) is provably guaranteed within this function class (this does not include SGD training though). The main part of the proof is the use of an “inference procedure” (Definition 6), which, informally, iterates through all transformers of increasing context size and eliminates the ones that do not fit the data. By construction, the set of functions that these transformers can implement (with increasing long context) is finite, such that eventually, at some finite context size, only the transformer that generalizes correctly to arbitrary length remains (all others have been ruled out by the data at this point; to be precise a complexity regularizer is also required to make the choice unique). This is the main argument in Theorem 7.2 (part of the main result). Keeping the parameters of transformers with increasing context width finite is central to the whole construction, and is reflected in the notions of PERIODIC and LOCAL of the Limit Transformer (informally: the functions implemented via attention only operate on a finite/small context window, and are translation invariant). Finally, the paper shows that a version of C-RASP (with either learned absolute positional encodings or no positional encodings) can be proven to be expressible via Limit Transformers, leading to the conjecture that length generalization with practical transformers is strongly related to whether a solution can be expressed in C-RASP or not. A small set of relevant experiments supports this conjecture well, including a (potential) explanation why some relatively simple regular languages cause trouble with length generalization (for which no C-RASP implementation provably exists).

strengths:
* Very timely question. While frontier models show many surprising and unprecedented capabilities, they fail catastrophically on some really simple problems in length generalization. Understanding the underlying reasons is crucial for Safety and Reliability, and may also pave the way to address these issues in future-generation architectures.
* The expressivity result stating that all C-RASP programs can be expressed by a Limit Transformer, and are thus identifiable in theory via the inference process in Def. 6, is a strong result that bridges the theory to very concrete and empirically testable hypotheses.
* Empirical results show that despite a very elaborate construction of a limit process and complex regularizer, the theoretical predictions have actual practical consequences on standard transformers trained in a standard fashion (that differs significantly from the inference process in Def. 6)

weaknesses:
* The paper is very extensive (72 pages, 62 are appendix, with 3887 lines in total; given the conference timelines and workload I could not review the appendix). The main paper is thus more a summary of the appendix than a standalone paper. While it makes no sense to have the main results and theorems without the proofs, maybe splitting the publication into a journal- / long-format theory paper and a separate more extensive empirical verification for a mainstream ML conference could be better.
* The construction of the Limit Transformer is quite elaborate (or rather the construction to go to the infinite context limit with non-exploding parameter sets / maintaining a finite function class) and the inference procedure in Def. 6 is completely impractical. Without any empirical results I would have been very skeptical about the practical relevance, and to be fully convinced I would like to see further results (though I believe Fig. 1 is significant and very promising). It is a bit unclear whether the theory had to be this complex and the connection to C-RASP dropped out as a lucky coincidence (which is how the paper is currently written), or whether putting C-RASP on a theoretical footing was the original goal that demanded this level of complexity.
* The inference procedure in Def. 6 seems a bit crude (though it does the job theoretically; same applies to the regularizer which is composed of 8 different complexity terms). The standard approach (e.g., in algorithmic information theory / Solomonoff Induction) is to not try to identify the correct function at some point $N_0$ but bound the overall number of mistakes (which is finite for any finite-length program). $N_0$ would be the point where the “last” mistake happens, which is generally unknown, and usually having bounds and generalization guarantees in terms of numbers of (remaining) mistakes are much tighter and shrink much faster with increasing number of observations. This is probably a question for future work, but it is unclear whether the restriction of using Def. 6 (having to identify the correct function) is implicitly limiting the function class where generalization is possible, and whether this class could be extended by focusing on a theoretical scheme that relies on bounding the mistakes (number of mistakes, and/or their cumulative magnitude).

**Verdict:**
Overall I am a bit ambivalent about the paper. On one hand it tackles a very timely and important problem by starting to make good progress from a theoretical angle (rather than adding even more contradicting experiments). On the other hand the current theory and presentation are quite complex and extensive. If the theory had been published in a journal / long-format paper before, and this paper would solely focus on empirically testing the conjecture that C-RASP expressiveness predicts length generalization, then a 10-page conference format seems like a great fit. Similarly, without the empirical results, I would have strongly doubted the practical relevance of the theory. But, the empirical results in Fig. 1 look very promising; though at this point it is unclear whether any results that contradict the main claims can easily be found or not. I do believe that the ML community needs more exposure to good theory, particularly at conferences, though I am not sure that this paper is the best example (due to its excessive length). I am also quite certain that this paper will spark quite a bit of follow-up work to make the theory simpler and/or more complete (expand the function class), and that publishing it will stir the community to conduct more empirical tests of the theory (which will make overall faster progress than asking the authors to perform more experiments). I am therefore currently slightly in favor of accepting the paper, though I would not be upset if others argue that ICLR may be the wrong venue. My confidence is currently on the low end - I did not have time to go through the extensive appendix, and there are a few bits and pieces of the main paper where I am not fully sure how they work out / will be proven. I am very happy to reconsider my opinion based on the other reviews and authors’ responses, and to make my criticism concrete, I leave some suggestions for improvement in the Questions section below.

questions:
**Improvements:**
(I consider all of them optional suggestions, not strict requirements)
 1. Maybe give the reader a better sense of where this is going early in the paper. It should be clear early on that the paper constructs a function class for which generalization can be proven in the theoretical limit, but the theory does not answer how this relates to training actual transformers of fixed context length via SGD (i.e., there may be functions that can theoretically be proven to be length-generalizable, but this may not work in practice). Also state that this function class is likely not complete (i.e., there may be functions where transformers can length-generalize that lie outside this function class).
2. I really liked lines 255-264 in terms of clarifying the paper. Maybe the same information can be qualitatively given early in the paper to prime the reader.
3. Definition 2 can be a bit misleading - it informally may suggest that a Limit Transformer is basically “just a normal transformer with infinite context”. This needs to be clarified. The text already mentions that the Limit Transformer is a *theoretical* construct (maybe consider calling it a Limit Transformer Process or similar, to make sure that the object is not confused with a concrete architecture). The finite precision argument in Def. 2 is theoretically ok, but in practice it just says that the precision is an arbitrarily high natural number (with no upper bound given), which is not implementable “like a standard transformer”. Also state here or earlier in the paper that the Limit Transformer cannot be trained via SGD, but uses a theoretical procedure (Def. 6) that cannot be practically implemented. And finally, the functions $\phi_{l,h}$, whose complexity is not bounded as far as I can tell, do a lot of the heavy lifting and are not just marginal additions to a standard transformer.

**Minor questions**

1. L200-202: This is a very interesting requirement. Together with the requirement for periodicity and locality I am reminded of the pumping lemma for regular languages. But if I understand correctly (some experiments, Fig. 10, and discussion following L 486), C-RASP defines a subset of $TC^0$ and it covers some but not all regular languages and some simple non-regular languages.
2. Showing that C-RASP with a small extension can provably be expressed by a Limit Transformer is very interesting. Can C-RASP potentially still be extended without violating this equivalence, or is the current set of operations (likely) complete?
3. What is the relation of Theorem 7 to standard learnability / language identifiability results (language identifiability is generally not possible from positive examples only)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694281524

thread_type:
official_review

<thread_object>
creator: reviewer_6ztg

<content>
summary:
This paper develops a theoretical framework for transformer length generalization, introducing "Limit Transformers" and proving generalization guarantees for functions satisfying PERIODIC and LOCAL properties. They characterize functions that are identifiable with APE and NOPE, and validate the prediction from theory with experiments on algorithmic and formal language tasks.

strengths:
1. The paper provides theoretical analysis of length generalization in transformers, including both sufficient conditions for generalization and communication complexity bounds showing certain functions cannot exhibit length generalization. This addresses an important open problem in theory. Also, it is the first to include length generalization theories with positional encodings to my best knowledge.
2. The theoretical framework successfully predicts empirical length generalization behavior across diverse tasks. The C-RASP formalism provides an interpretable way to determine whether a function should exhibit length generalization, making the theory practically useful.
3. The experimental evaluation is thorough with both algorithmic tasks and formal languages.

weaknesses:
1. The main contribution compared to the previous C-RASP work and the RASP-L work is to extend the framwork to include positional encodings. However, the positional encodings considered are APE and NOPE, while the more frequently used encodings in practice are relative positional encodings. Also see question 1.
2. The limitation of the proposed theoretical framework is discussed, but it could benefit from more empirical evidence, like where the theory predicts length generalization but empirical performance is poor, or vice versa.

questions:
1. Have you tried the performance of RPE although the current theory does not cover it yet? In [1], NOPE is shown to inherently learn some kind of relative positional encoding. Does RPE behave similarly to NOPE in certain tasks? 
2. The model size provided in the appendix is highly dependent on the specific tasks (different tasks use different model depths, embedding space sizes, etc). Do you observe the sensitivity of the generalization performance in terms of model sizes? Or are there other reasons for this?

[1] The Impact of Positional Encoding on Length Generalization in Transformers
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, Siva Reddy
</content>
</thread_object>

</thread>
<thread>
creation date:
1730720079555

thread_type:
official_review

<thread_object>
creator: reviewer_vn9i

<content>
summary:
The paper studies the length generalization problem in decoder-only Transformers, which refers to the inability of models to deal with longer samples than encountered during the training phase. The paper aims to identify which tasks can achieve length generalization. To this end, the authors introduce Limit Transformer, a theoretical model designed to generalize across varying sequence lengths. Importantly, the authors prove that under an idealized inference procedure, any tasks that can be expressed by Limit Transformer, satisfying Periodic and Local constraints, can provably achieve length generalization. Furthermore, the authors show that any C-RASP programs can be expressed by Limit Transformer, leading to the conclusion that such tasks can also generalize to longer inputs. On the other hand, the paper presents that copying and addition cannot be generalized as these tasks do not exhibit logarithmic communication complexity. Finally, the paper provides experimental results, demonstrating that tasks expressible by C-RASP programs (binary majority, sort, copy unique) easily length-generalize while tasks outside C-RASP (copy repeat, parity, addition) fail to achieve length generalization.

strengths:
- The paper addresses an important question in the literature: which tasks can achieve length generalize and which cannot. Prior work on length generalization has mainly focused on improving empirical performance, with fewer studies providing a theoretical understanding. While [1] introduces RASP-L to identify tasks that can achieve length generalize, their argument still remains conjectural. This study goes one step further than the previous RASP-L conjecture, offering a theoretical framework to determine whether certain tasks will provably achieve length generalization or not. Therefore, I believe this paper makes a significant contribution to the literature.
- The FAQ section in the appendix effectively conveys the paper's intuition and enhances the reader’s understanding.
- Overall, the paper is well-structured and provides a detailed analysis to present their findings.

[1] Zhou, Hattie, et al. "What algorithms can transformers learn? a study in length generalization."

weaknesses:
I don’t see any significant weaknesses in the paper, but there are a few minor limitations, which I don’t consider critical issues in evaluating this paper.

- The scope of the paper is limited to algorithmic tasks and does not cover length generalization problems in natural language processing tasks.
- As explained in the paper, a key assumption in the framework is the idealized inference procedure, which assumes that we can obtain Transformers that are fitted to reproduce a target function while minimizing a specific regularizer $R(T)$, and thus the current framework is not fully end-to-end. Introducing an analysis of training dynamics to replace this assumption would be a promising direction, achieving a truly end-to-end, complete argument.

questions:
- In Figure 1, why do Transformers with NoPE fail even on in-distribution samples (Bin 1) for Copy Unique and Addition? Doesn’t this contradict the observations in [2], which argue that NoPE can length-generalize for these tasks to some extent?

[2] Kazemnejad, Amirhossein, et al. "The impact of positional encoding on length generalization in transformers."
</content>
</thread_object>

</thread>
<thread>
creation date:
1731038065576

thread_type:
official_review

<thread_object>
creator: reviewer_gpiw

<content>
summary:
This work studies the challenge of enabling transformers to generalize to sequences longer than those seen during training. This capability is often inconsistent across tasks and lacking strong theoretical understanding. The authors present a new theoretical framework to examine length generalization in causal-attention transformers with learnable positional encodings. Using this framework, they analyze the conditions under which transformers can generalize to longer sequences under certain conditions. The theoretical findings are further validated through empirical tests on a set of tasks.

strengths:
* Length generalization is a very important problem that is being explored from various perspectives, though primarily through algorithmic and empirical studies, with relatively few theoretical analyses. This work takes a different approach, offering distinct advantages.
* It's encouraging to see that, under certain conditions (as shown in Theorem 7), they identify cases where length generalization is achievable.
* Provides several formalizations (e.g. Limit Transformer) and proofs on this topic that would be valuable for future research.

weaknesses:
* The paper’s current writing seems to focus more on demonstrating how to achieve length generalization under specific conditions than on examining the limitations of existing models. For example, it centers on proving Theorem 7 by introducing various modeling assumptions, such as the Limit Transformer and specific inference conditions (like the proposed regularizer). This approach differs somewhat from the expectations set in the introduction, which suggests a more interpretive analysis of current models.
* The practical impact of this paper feels somewhat limited. It would be valuable if the authors could identify practical applications that leverage their findings.
* C-RASP and formal languages are quite distinct from traditional text corpora or other common scenarios. Even though the aim is to theorize the formalism in this field, there seems to be a significant gap between the formalism presented in this paper and that of other widely used settings.

questions:
* Could the authors more directly relate their theorem to widely used transformer models? For example, which specific conditions do not hold in these models, and how does this align with the empirical observations in Section 5?
* The FAQ in Appendix A actually was quite useful providing valuable insights and gives readers motivation. Could the authors consider integrating some of these discussions more naturally into the introduction or relevant sections?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732380880728

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We thank all reviewers for their overall positive assessment, extensive comments and constructive criticism. The detailed feedback on both the work's presentation and technical details have allowed us to make the paper more readable and the results more sound. We summarize the reviewers' major concerns and list the changes we have made to address them. 

We have uploaded a revised PDF, with changes highlighted in **blue**.

> The treatment of positional encodings produces seemingly contradictory results with Kazemnejad et al. 2023

The cited paper shows that NoPE transformers can simulate APE transformers up to a large input size. Taken at face value this suggests we don't need limit transformers to prove guarantees for APE transformers. However, there is an important distinction: the parameters in a transformer must increase rapidly to perform the cited simulation on larger inputs. Because of this, our theory predicts that NoPE transformers will length-generalize worse than APE transformers on certain tasks. Indeed, our experimental results confirm that APE transformers can length-generalize on several problems that NoPE transformers do not. Furthermore, the experimental setup in the cited paper differs notably from ours. We have written a treatment of this issue in Appendix G.4, as we believe it is quite important (and thank the reviewers for pointing it out). We also provide further experimental results confirming that APE generalizes better than NoPE in agreement with our theory, and even when performing much broader hyperparameter search for NoPE (Appendix G.7): On a family of induction head tasks, APE achieves ~99% accuracy in generalizing to 3 times the training length, whereas NoPE shows <5% there.

> The requirement of translation-invariant product functions is unrealistic

It is true that standard training of transformers does not enforce translation invariance in the product functions. However, we can *prove theoretically* that translation invariance is helpful for length-generalization (on induction heads for instance), and *show empirically* that length-generalizing transformers often learn translation invariant product functions in practice (both in transformers trained from scratch and in GPT-2). As such, we suggest translation-invariance is favored by standard training even though it may not be explicitly enforced. We have written a new section on this in Appendix G.6.

> The paper is too elaborate

Because theoretical understanding of length generalization of transformers is still in its infancy, building a formal framework for it requires the synthesis of many different ideas. We believe that presenting our simultaneous progress in multiple areas - both theoretical and empirical - is necessary to form a solid theoretical framework. In order to make the paper more approachable, we have rewritten the introduction and changed prose throughout the body of the paper. 

> The practical impact of this paper is not clear

Indeed, our paper focuses on a theoretical framework explaining the length-generalization on algorithmic problems (rather than analyzing transformers in practice on natural language tasks). Nevertheless, we believe that a solid theoretical understanding can enable future work to have a more immediate practical impact. We have given pointers towards potential avenues for this (new positional encodings, improved interpretability) and modified our introduction to make the limitations of our setting clearer. 

Overall, we thank the reviewers for their constructive criticism and support.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary:
The paper introduces a theoretical framework analyzing length generalization in causal transformers with learnable absolute positional encodings. The authors introduce "Limit Transformer" to handle growing parameters and show that C-RASP programs (under specified periodic and local constraints) can be translated into Limit Transformers, providing a concrete class of problems where length generalization is guaranteed. The theoretical findings are supported by empirical experiments demonstrating that tasks expressible by C-RASP programs succeed in length generalization, while others, such as copying with repetitions and n-digit addition, fail.

Strengths:
- Addresses an important open problem in transformer theory - length generalization capabilities
- Provides rigorous theoretical analysis with concrete proofs and guarantees
- Formalizes and proves aspects of the previously conjectural RASP-L hypothesis
- Strong empirical validation across diverse tasks showing alignment between theory and practice

Weakness:
- Treatment is limited to absolute positional encodings rather than more popular schemes
- The theoretical setup makes some idealized assumptions that do not reflect practice
- Focus is primarily on algorithmic tasks rather than natural language

Decision:
All the reviewers were in consensus that the paper represents an important step forward in understanding transformer capabilities and limitations, providing both theoretical insights and practical implications for future work. It merits publication at ICLR 2025.