A Formal Framework for Understanding Length Generalization in Transformers

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

This refers to

$D_0 = \limsup_{n\rightarrow \infty} D_{n}(n) \geq \limsup_{n\rightarrow \infty} D_{n}(\tau_\infty) + 2^{-2p} \geq \liminf_{i\rightarrow\infty} D_{\nu_i}(\tau_\infty) + 2^{-2p} = D_0+ 2^{-2p}$ The first inequality holds because $D_n(n) \geq D_n(\tau_\infty)$ whenever $n \geq \tau_\infty$, simply because $D_n(\cdot)$ is monotonically increasing for each individual $n$.

The second inequality holds because $\nu_1, \nu_2, \dots$ is a subsequence of $1, 2, \dots$; hence a $\lim \sup ...$ over the larger sequence upper-bounds the $\lim \inf ...$ over the subsequence. We have made the steps more explicit in line 1091 of the new PDF.

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

We have made this more explicit and rephrased in line 1100-1107 of the revised PDF. It means that after $N_0$, all Limit Transformers traversed must be functionally equivalent to $f$.

(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?

We have made this more explicit in lines 1210-1223 of the revised PDF. Alice can partition the positions into a constant number of set, and for each of them needs to transfer the number of positions in that partition.

(14) How does periodicity fall out in the limit transformer?

This is an interesting observation. Indeed, periodicity falls out as a consequence of translation-invariance by Lemma 48: translation-invariant positional relations mediated by finite-rank matries are periodic. Hence, we are able to separate the positional relations in a sequence of transformers $T_n$ with bounded $\mathcal{R}(T_n)$ into local and periodic components. We now explain this better in Appendix A, point (7).

Why not have periodic positional encodings on the original transformer, instead of the offset independence condition?

We refer to our discussion of offset independence and translation invariance independence above, where we show that offset independence is empirically and theoretically well-motivated. Our aim is to describe the behavior of general learnable APE encodings, as in our experiments and the closely related paper, Zhou et al 2024.

(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.

Thanks, fixed.

(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?

As discussed in our response to Point 1, the simulation of positional encoding in NoPE is limited in its capacity, at least compared to APE. We thus conjecture that, similarly, NoPE cannot fully simulate RPE. We believe that theoretical understanding of RPE, analogous to our results for APE, would take substantial additional technical work and is out of scope.

(11) What is the role of $N_0$? Would it be interesting to explain why, in practice, transformers can generalize well with modest training lengths?

We agree that predicting and validating realistic bounds on $N_0$ is a very important next direction for research. Deriving an $N_0$ from our proof would give a valid and nonvacuous, but likely overly pessimistic estimate. More realistic bounds on $N_0$ will likely require advances in understanding SGD dynamics on transformers, which remains hard to understand, in particular in the multi-layer setup, needed for many of the functions in Figure 1.

Concerns on the proof of Lemma 17:

We thank the reviewer for the close reading, and have expanded the proof to clarify all these aspects.

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?

Let $A := sup_i \mathcal{R}_\infty(\tilde{T}_i) < \infty$.

The number of limit transformers $\tilde{T}$ with $R_\infty(\tilde{T}) \leq A$ is finite except for the functions $\phi_{l,h}$, because $A$ bounds (1) the number of parameters, (2) their magnitudes, (3) the precision at which they are represented. We make this explicit in line 993 of the new PDF.

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).

First, note that $R(T_n) \in [\frac{1}{n} + \inf_{T \in U_n} (R(T)), \inf_{T \in U_n} (R(T))]$ Due to boundedness and monotonicity, $\inf_{T \in U_n} (R(T)))$ converges to a limit, say $\tilde{R}$. Since $1/n \rightarrow 0$, the width of the interval converges to 0. The Squeeze Theorem then implies that $R(T_n) \rightarrow \tilde{R}$. We make this explicit in line 1008.

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

By definition of $R_-$, $D_{\nu_i}(\nu_i) = R(T_{\nu_i}) - R_-(T_{\nu_i})$ As both terms in the RHS converge, the LHS also has a limit. We make this more explicit in the text.

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

As $D_\infty(\tau)$ is monotonically increasing and bounded, it converges. Due to bounded precision, it only takes values in discrete steps (say, only multiples of $2^{-p}$ for some $p$); hence, it must attain the limit at some specific $\tau$, which we refer to as $\tau_\omega$. We have made this more explicit in line 1040.

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_{\nu_{i(n)}}(n) = D_{\infty}(n)$ true?

We have expanded (line 1042-1058 of the new PDF). The equality in question is $D_{\nu_{i(n)}}(n) = \liminf_{j\rightarrow\infty} D_{\nu_j}(n) = D_\infty(n)$ Regarding the first equality, such a $i(n)$ exists because $\phi_{l,h}$ has fixed precision, which entails that the $\lim\inf$ is attained infinitely often. Regarding the second equality, this is the definition of $D_\infty(n)$.

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.

Thanks for the suggestion. We now use a superscript to indicate this, e.g. $\phi_{l,h}^{(\tilde{T}_n)}(i,j)$ (line 989).

In the definition of $D_n(\tau)$, how can $\tau$ exceed $n$?

We now explicitly restrict summation to $\min(n,\tau)$.

(5) Why is translation invariance a reasonable constraint in the definition of the Hypothesis Class? Isn't there a gap between theory and experiments?

We agree that translation invariance merits further consideration. We distinguish two relevant properties:

• (A) offset-invariance of the input-output behavior; that is, the transformer's output $T(x,o)$ is independent of $o$;
• (B) translation-invariance of the product functions, such as $p_i^T K^T_{l,h} Q_{l,h} p_j$ as assumed in Definition 4 (Hypothesis Class).

Our experimental setup (Section 5) assumes that every training sample is presented with a random offset. This setup is a simplification of the setup in Zhou et al 2024, and aims to mimick how LLMs need to solve reasoning tasks no matter where they appear in a context. Due to this property of the experimental setup, the transformers are trained to be offset-invariant in their input-output behavior (A), in agreement with the theory.

Translation-Invariance (B) is a stronger requirement, and implies (A). We now discuss (B) in Appendix G.6, where we show the following:

• We provide theoretical evidence that translation invariance is beneficial for length generalization (Appendix G.6.1). There, we describe a sequence $T_n$ of transformers violating translation invariance, where $n$ operates at lengths $\leq n$, where $\sup_n \mathcal{R}(T_n)<\infty$ and each $T_n$ describes a target function (a simple induction head task) at lengths $\leq n/2$, but no $T_n$ represents the task at length $n$ -- that is, the models fail to length-generalize. This is in contrast to the translation-invariant setup, where such a situation necessarily leads to $T_n$ length-generalizing correctly for large $n$.

• Translation invariance is approximately satisfied in trained transformers (Appendix G.6.2), both in small transformers trained on algorithmic problems, and in a real-world LM, GPT-2. This suggests that translation invariance, even though not explicitly enforced, is implicitly favored by standard training, presumably because the target function itself is (at least approximately) offset invariant in these setups.

Overall, we conclude that

• standard training tends to implicitly favor translation invariance, at least in the setups relevant to our experiments
• translation invariance is theoretically beneficial for length generalization

(6) On the regularizer in definition 5

(6a) How does it enter Lemma 17?

The term is key to ensuring that $f$ is represented by a single LOCAL limit transformer. Specifically, boundedness of the regularizer term, across all context windows n, entails that $D_0$ (Equation 15) is finite, which is used to derive a contradiction in line 1090. That in turn is used to show that the $\phi$ functions are local for a uniform $\tau_\infty$. This is needed for concluding that the function $f$ is representable by a single LOCAL limit transformer.

Also, since all positions are equally penalized in this regularizer, why would things far off be more penalized?

The idea is that, when training on lengths $\leq n/2$, the training set constrains the attention behavior between positions at a distance $\leq n/2$, but not at larger distances $>n/2$. The regularizer discourages attention at such greater distances. For instance, consider an induction head task requiring attention to the previous token in Layer 1. Without an inductive bias discouraging attention (either through a regularizer, or implicitly through initialization), when tested on longer inputs, the attention head in Layer 1 could end up attending both to the preceding position and to some far-away position at distance $>n/2$, because the training data had no information about such distances.

Also, the justification based on initialization making the regularizer small is not fully clear.

We refer to our response under Point (2b): Proposition 54 shows that, if one randomly initializes transformers with increasing maximum context length $n$, the regularizer will, in expectation, stay bounded even as $n$ diverges.

(6b) What is the role of limit transformers and the regularizer in NoPE?

We refer to our response to Point (1), where we explain that APE is substantially more powerful than NoPE. Technically, NoPE is a special case with $p_i \equiv 0$, $\phi(i,j) \equiv 0$ (lines 264-266). Indeed, in this special case, limit transformers are not needed to arrive at our length generalization guarantee. Limit transformers are used to treat APE, which is substantially more powerful than NoPE. We explicitly remark this in Appendix B.2.

(7) Why are the below-diagonal values of $\phi(i,j)$ not constrained?

The values below the diagonal are irrelevant as we are considering only causally masked transformers (line 91), in line with standard LLMs and with Zhou et al 2024.

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

Agreed, fixed.

(3) Regarding the definition of limit transformers

(3a) Why do limit transfomers need both positional encodings and $\phi_{l,h}$ functions?

Because Limit Transformers have finite width $d$, the positional encodings ${\bf p}_i$ in the Limit Transformer can only absorb some parts of the information from the positional encodings ${\bf p}_i$ of the standard transformer, namely those that can be absorbed into finite-width and finite-precision encodings. It is desirable to assign Limit Transformers a finite width, so their definition is as close to standard transformers as possible.

Other parts of the positional information cannot be coded in this way -- for instance, it's not possible in a single transformer operating on unboundedly long inputs, to implement attention from position $t$ to position $t-1$ with a fixed-width positional encoding (cf. line 864). Hence, we introduce functions $\phi_{l,h}$ to absorb such remaining positional information. Due to its bounded width, $y_i$ will generally contain less positional information in the Limit Transformer than in a standard transformer, necessitating the additional term using $\phi_{l,h}$ in Equation 6.

(3b) Other than Eq. 6, is the rest of the construction of limit transformer same as standard transformer?

Yes, everything else is identical to the transformers from Section 2. Limit transformers have the same attention mechanism (Eq. 3); they just differ in adding $\phi(i,j)$ to the attention logits.

(3c) If we are happy with finitely many positional encodings, then why not just do some periodic encodings in the standard transformer?

Importantly, while the Limit Transformer has only finitely many distinct positional encodings, the standard transformers $T_1, T_2, T_3, ...$ found by the Inference Procedure can have unboundedly many distinct positional encoding vectors, because the width $d$ is not bounded by the definition of the Hypothesis Class. We find it useful to separating, in translating to Limit Transformers, the power of unbounded-width encodings into (i) bounded-width and bounded-precision encodings $p_i$ and (ii) the functions $\phi_{l,h}$. As explained in point 7 of Appendix A (expanded in the revision), $p_i$ capture periodic information, whereas $\phi_{l,h}$ encapsulate local relations. Hence, positional abilities of Limit transformers go beyond the periodic encodings $p_i$.

We study standard transformers with learnable APE encodings, rather than the periodic encodings suggested by the reviewer, to match the setup of Zhou et al 2024 [1]. Extending our theory to hard-coded periodic encodings could be another interesting topic.

We also would like to emphasize that Limit Transformers are a mathematical construct that helps us prove things about standard transformers (as defined in Section 2). There may be other ways of defining these limiting objects that allow proving the same results.

Re "we can operate with NoPE, express finitely many positional encodings, and simplify the whole story right?": Importantly, limit transformers have both bounded-width and bounded-precision positional encodings $p_i$ and $\phi_{l,h}$ functions; jointly, these simulate the power of standard APE transformers, and are substantially more powerful than beyond NoPE, as we explain under point (1).

(4) The presentation of the translation-invariance and locality constraints imposed on $\phi_{l,h}$ and positional encoding might need to be clearer.

We have rewritten Definition 3 to make this clearer. We would welcome any further advice on how to improve this aspect.

[1] Zhou et al, What algorithms can transformers learn?, ICLR 2024

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.

We thank the reviewer for the detailed reading and their feedback.

We believe the most important points to revolve around

• Detailed questions about the proof of Lemma 17, which we address in detail
• The role of APE vs NoPE, which we now discuss in Appendix G.4. While NoPE can partially simulate positional information, it is not as powerful as APE. We find in both theory and experiment that NoPE does not perform well on tasks not expressible in C-RASP$[\emptyset]$ (Figure 1 and Appendix G.4).
• The role of offset invariance and translation invariance, which we now discuss in Appendix G.6. We empirically show that translation invariance is often approximately satisfied in trained transformers, both small transformers trained on algorithmic problems, and a real-world LM with APE (GPT-2), suggesting that it is favored by standard training. We also theoretically show that translation invariance is beneficial for ensuring length generalization on a simple induction head task.

Point-by-Point Reponse

We address each question point-by-point. We paraphrase the questions for the sake of brevity.

(1) Can't NoPE simulate APE? Hence, isn't it sufficient to study NoPE, making the analysis much simpler?

It is true that up to a fixed input length $T$, a NoPE transformer can in principle compute positional information, in the sense of computing an activation with value $1/t$ at position $t$ (as in the proof of Theorem 1 in the Kazemnejad et al paper referenced by the reviewer). Importantly, this is weaker than the ways in which APE transformers can use positional information. In order to perform this simulation, the transformer would need either rapidly increasing MLP weight values or rapidly increasing width for larger values of $T$. For instance, distinguishing close-by positions, say $t-1$ and $t-2$, in such an encoding requires rapidly increasing parameter values as $t \rightarrow \infty$, as the values get arbitrarily close to $0$. In this sense, even a simple task such as an induction head, which requires attention from $t$ to $t-1$, requires parameters rapidly increasing with the input length Appendix G.4). In our theoretical framework, NoPE is not predicted to length-generalize as well as APE on such a task. Indeed, empirically, we find NoPE transformers not to perform well on a variety of tasks not expressible in $C-RASP[\emptyset]$ (Figure 1).

In our theory, NoPE is a simple special case of the more powerful APE setup (lines 265), in which special case one can indeed prove Theorem 7 without limit transformers. This is explained in Appendix B.2.

(2) Regarding assumptions made by the theory

(2a) The theory uses the constraint that all transformers are offset-invariant

We believe that the reviewer refers to ''In line with the assumed setup, we focus on transformers whose input-output behavior is invariant across offsets: $T(x,o) = T(x,o')$ for any $0 \leq o, o' \leq N(T) - |x|$''. We have removed this statement, as it is not needed at this point. However, we do assume that the Hypothesis Class requires translation invariance, which we discuss under (5).

(2b) The inference procedure uses an additional regularizer that is not explicitly enforced in standard training

It is true that the additional regularizer (Equation 8) is not explicitly enforced in standard training. We argue that, nonetheless, it is likely to reflect an inductive bias of standard initialization: We know from Proposition 54 that, if one randomly initializes transformers at context length $N$, and sufficient width, the regularizer will in expectation remain bounded even as $N \rightarrow \infty$. Boundedness of the additional regularizer as $N \rightarrow \infty$ is thus likely to be favored by standard initialization.

More broadly, we argue that our results are highly interesting even if the theoretical setup makes idealizing assumptions. Despite a lot of empirical research, theoretical understanding of length generalization of transformers is in its infancy. The RASP-L Conjecture has not previously been formalized; there is no existing evidence beyond experiments. Our work already enables a proper formalization of the conjecture, in terms of limit transformers and C-RASP. As a step towards theoretically understanding length generalization, we study length generalization in an idealized setup abstracting away from training dynamics, as we clearly acknowledge in Sections 1 and 6. We lay groundwork for future work, both through theory (we provided a formal class of languages whose expressivity can be rigorously understood) and experiments (we provide evidence that this language class tracks empirical length generalization behavior).

Addendum: We have uploaded a new draft version with an added Appendix G.7, in which we report further experiments confirming that APE generalizes much better than NoPE on a family of induction head-like tasks, in agreement with our theoretical predictions. On a family of induction head tasks, APE achieves ~99% accuracy in generalizing to 3 times the training length, whereas NoPE shows <5% there. This confirms our theoretical point from Appendix G.4 that the simulation of positional information in Kazemnejad et al 2024 is not powerful enough to allow NoPE to subsume APE. Taken together, we believe that our revision convincingly demonstrates why our theory needs to study the more general (and more complex) case of APE, rather than NoPE.

(1) The paper is very long -- should it be multiple papers?

Our paper makes progress on multiple but tightly interleaved fronts, both establishing a length generalization guarantee in an idealized setup (Theorem 7), settling the (non)membership of many problems in C-RASP (Section 4 and Figure 1), and validating predictions empirically (Section 5). We believe that these theoretical and empirical components are tightly linked, and will be most convincing and impactful if presented together.

(2) The construction of the Limit Transformer is quite elaborate -- is this necessary?

Our guiding question was to formalize when there exists a single APE transformer-like ''algorithm'' for a problem across input lengths, which Zhou et al 2024 described as a key intuition behind their RASP-L conjecture. Formalizing this led us to the notion of limit transformers, which allowed us both to derive a length generalization guarantee for an idealized inference procedure (Theorem 7), and a new result on the expressiveness of APE transformers (Corollary 26).

(3) How does the setup compare to bounding the number of errors, as in Solomonoff Induction?

Thanks for pointing out the link to Solomonoff induction and similar settings. In fact, our setting is quite similar: In our setting, length generalization in the sense of ultimately converging on generalizing correctly when $n$ is large (Theorem 7) is equivalent to the number of mistakes being finite. We now make this explicit in Appendix G.5.

(4) Overall, is this paper too extensive and long for this conference?

We would like to remark that ICLR has published papers with similar length. For instance, [1,2,3] have 66 to 74 pages. This applies similarly across Machine Learning conferences, and there have been highly influential papers longer than our submission, such as [4] with 84 pages and [5] with 93 pages.

[1] Panigrahi et al, Effect of activation functions on the training of overparametrized neural nets, ICLR 2020, https://openreview.net/pdf?id=rkgfdeBYvH

[2] Li et al, Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning, ICLR 2024, https://openreview.net/forum?id=vNiI3aGcE6

[3] Li et al, Risk Bounds of Accelerated SGD for Overparameterized Linear Regression, ICLR 2024, https://openreview.net/forum?id=AcoXPIPh4A

[4] Allen-Zhu et al, Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers, NeurIPS, https://arxiv.org/pdf/1811.04918

[5] Bai et al, Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection, NeurIPS, https://arxiv.org/abs/2306.04637

(1) The paper focuses on APE and NoPE, whereas many transformers use relative encodings (RPE)

We closely follow Zhou et al 2024 in using APE, as our aim was to formalize the RASP-L conjecture. We were also motivated by [1], which found NoPE to be empirically competitive with relative positional encodings in various algorithmic problems. We believe that extending our theoretical study to relative positional encodings is an exciting next step for future research, as we also mention in Section 6.

[1] Kazemnejad, Amirhossein, et al. "The impact of positional encoding on length generalization in transformers."

(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.

We have not been able to find examples where the theory predicts length generalization but empirical performance is poor, or vice versa. Any such examples would of course be highly interesting for further refining our theory.

Questions:

(1) Have you tried the performance of RPE?

As described above (and in Section 6), we agree that expanding our theoretical treatment to RPE is a very interesting question. While NoPE can simulate some amount of positional encoding as shown by [1], this is strictly weaker than what APE can do, as we explain in Appendix G.4. We conjecture that the same applies to RPE, and that NoPE may not subsume general RPE. Hence, we believe treating RPE theoretically will require substantial additional technical work, out of scope for the present paper.

(2) Why are the model sizes in the experiments task-dependent?

There may be a minimum model size necessary in order to solve a particular algorithmic task. We conjecture that there is a link between model size and the formula complexity (e.g., length, nesting depth) in C-RASP. Zhou et al conjectured that shorter programs are easier to learn, and we thus conjecture that C-RASP complexity could also be used to predict minimum model size. As proving bounds on the smallest program or formula representing a problem is generally nontrivial, we leave rigorous exploration of this idea to future work.

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.

We thank the reviewer for the positive assessment.

(1) The scope of the paper is limited to algorithmic tasks and does not cover length generalization problems in natural language processing tasks.

We agree with this, and now make this explicit throughout Section 1. We note that prior empirical work on length generalization (whose results our work aims to give a theoretical foundation to) has largely focused on algorithmic tasks. Expanding to naturalistic language comprehension tasks is an interesting future direction.

(2) Analysis of training dynamics, instead of an idealized inference procedure, would be desirable.

We agree with this limitation, which we acknowledge in Section 6.

Questions:

(1) 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?

In Copy Unique and Addition (Figure 1), the NoPE results are represented by the red dotted curves, which do start out at 100% in Bin 1 in these tasks [dotted=NoPE, red=not in C-RASP]. Thus, on these tasks, NoPE does succeed on in-distribution samples. Please let us know if we should make some aspect of the figure or caption clearer to prevent misunderstanding.

We would also like to point out two differences with [2]. First, [2] report results for Addition on heldout lengths 8-16 (their Figure F.5) , much shorter than our heldout bins 100 and 150. Second, [2] report three "Copy" tasks, where NoPE shows length generalization from length 20 to length 40 only in the first two variants (their Figure F.4), which require matching only the length of the string, but not its character sequence. On their third variant, NoPE does not generalize from length 20 to 40 at all.

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

We thank the reviewer for the close reading and further questions. As the rebuttal deadline is approach, we for now provide concise answers for the questions:

I am slightly confused about the statement in Definition 6. Shouldn't each $T_i$ be an element of $\Theta_i$, not $\Theta_n$?? Based on the explanation stated between Lines 228 to 231 of the revised version, I guess that $T_1$ is an element of $\Theta_1$ . Furthermore, following Definition 4, it seems that $\Theta_n \subset \Theta_1$ holds, which would imply $T_1 \not\in \Theta_n$.

Thanks for the close reading. The phrasing in Definition 6 is indeed not optimal. As the reviewer inferred, we intend to say that $T_1 \in \Theta_1$, $T_2 \in \Theta_2$, $T_3 \in \Theta_3$, etc. We will fix this in our next version. We believe that this addresses the reviewer's question.

I might have missed this, but can any Limit Transformer be translated into a standard Transformer? If so, can you outline the method?

Yes, such a translation can be carried out for any finite context length N of the resulting standard transformer, and importantly the translation is uniform in the sense that $\sup_N R(T_N) < \infty$, even though the width of the translation needs to increase. This is formalized in Lemma 47. The outline of the method is as follows; a discussion is also provided in lines 2724-2751 (page 51):

• Intuitively, the positional encodings of $T_N$ consist of those of the Limit Transformer, concatenated with one-hot vectors for the positions from 1 to N. The overall width is thus $d+N$.
• Token embeddings just consist of those of the Limit Transformer, concatenated with the N-dimensional zero vector.
• For each attention head, the $K^T Q$ matrices encode both those of the Limit Transformer (in the first $d$ dimensions) and the $\phi_{l,h}$ functions (in the final $N$ dimensions).
• Complications arise from the fact that this construction (i) does not ensure translation invariance, (ii) does not keep the regularizer in Eq. (8) bounded. This is solved by (i) attending to SOS and computing position relative to that to ensure translation invariance, (ii) routing some of the positional information through the attention mechanism, effectively making it invisible to Eq. (8). This makes the construction more complex, but allows us to prove that translation invariance and a bounded value for Eq. (8) can indeed be achieved, which in turn is an important insight leading to Theorem 7. This is summarized in lines 2724-2751.

We will add this high-level explanation before the proof of Lemma 47 in the next version.

For a task that is not expressible by the Limit Transformer satisfying Periodic and Local (e.g., n-digit addition), the authors state that any run of the Idealized Inference Procedure will result in a sequence of Transformers with bad properties (Lines 418 to 421). Does this imply that "for Transformers with fixed depth, number of heads, parameter norms, ranks, MLP dimensions, and precision p, there does not exist a length-generalizable solution for n-digit addition"?

We believe that this is an accurate statement: intuitively, if such a length-generalizable solution existed, the Idealized Inference Procedure should find it; hence, it cannot exist. We will consider adding an explicit statement and proof in the next version; one thing to take care of is to show that this conclusion holds when bounding depth, number of heads, parameter norms, ranks, MLP dimensions, and precision p, but not necessary explicitly bounding Eq. (8).

line 186: R(T) is referenced before it is formally defined.

Thanks for catching this. We will fix this in the next version.

Dear reviewer Gpiw,

Thanks for your feedback on our paper!

Reply Regarding Weaknesses

(1) The paper does not include interpretive analysis of existing models

We would like to clarify that our paper focuses on a theoretical framework establishing general criteria for when length generalization is achievable when training transformers on some problem, and leave interpretive analysis of existing specific models out of scope. We have rephrased the introduction to make explicit that we are interested in the setting where transformers are specifically trained on short inputs from some task.

(2) What is the practical impact of this paper?

We believe that a theoretical understanding explaining empirical findings (Zhou et al. 2024) can improve current and future applications in NLP. A possible practical consequence is deriving new positional encoding or scratchpad schemes using our theoretical insights to enable stronger length-generalization. For instance, RASP and RASP-L have been used to derive practical advances in the design of transformers for various problems, e.g. [1,2]. Additionally, our framework may be used for more refined methods of interpretability due to the formal connection between our RASP variant and length-generalizing transformers - for instance, decompilation of transformer weights into RASP programs [4]. Hence, we believe our theoretical framework is highly valuable for practical work to build upon.

(3) C-RASP and formal languages are quite distinct from common scenarios

As described in our response to (2), RASP and RASP-L have had substantial impact in research on transformers. Formal languages are a principled way to model sequences of unbounded length - crucial for understanding length generalization. They provide a formal way to analyze the capabilities of transformers to perform practically relevant tasks, such as induction heads (which we have analyzed in this paper). In fact, formal languages have also been used to validate new positional encoding schemes [3].

[1] Fan et al, Looped Transformers for Length Generalization, 2024. https://arxiv.org/abs/2409.15647

[2] Hou et al, Universal Length Generalization with Turing Programs, 2024. https://arxiv.org/abs/2407.03310

[3] Ruoss et al, Randomized Positional Encodings Boost Length Generalization of Transformers, 2023. https://arxiv.org/pdf/2305.16843

[4] Friedman et al, Learning Transformer Programs, 2023. https://arxiv.org/abs/2306.01128

Reply Regarding Questions

(1) How does the theory relate to widely used transformer models?

As we describe above, our study focuses on general properties of the transformer architecture. We empirically test the predictions by training models on various problems from scratch in Section 5. We expect that the results also have implications for the algorithmic abilities of commonly used specific models (such as GPT-3 or LLaMa-3), but more detailed exploration of this to future work.

(2) Can more content from the FAQ be included in the main text?

We are glad to hear that the FAQ is useful. We have made some changes to the main text to make the relevant information (e.g., about the role of limit transformers) more salient.