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
Venue: ICLR 2025 Poster (2025)
Keywords: transformers
theory
length generalization
expressivity
analysis
algorithmic reasoning
systematic generalization
formal languages
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We introduce a theoretical framework for understanding which problems transformers length-generalize on.

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.

Published as a conference paper at ICLR 2025
A FORMAL FRAMEWORK FOR UNDERSTANDING LENGTH GENERALIZATION IN TRANSFORMERS
Xinting Huang 1x
Andy Yang2* Satwik Bhattamishra Yash Sarrof
Andreas Krebs* Hattie Zhou'
Preetum Nakkiran Michael Hahn
1 "Saarland University University of Tübingen
University of Notre Dame Mila, Université de Montréal 6 Apple
University of Oxford
ABSTRACT
A major challenge for transformers is generalizing to sequences longer than those observed during training. While previous works have empirically shown that transformers either succeed fail at length generalization depending the task, theoretical understanding of this phenomenon remains limited. In this work, we introduce 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 us- ing a norm-based regularizer. This enables us to prove the possibility of length generalization for rich family of problems. We experimentally validate the the- ory as a predictor of success and failure of length generalization across a range of algorithmic and formal language taskę"] Our theory not only explains a broad set of empirical observations but also opens the way to provably predicting length generalization capabilities in transformers.
INTRODUCTION
A key problem in neural sequence modeling is generalization from shorter sequences seen during training longer sequences afterwards length generalization. A wide range of empirical research has found that transformers sometimes succeed and sometimes fail at tongth-gnneaalzztionn (c.g.
Bhattamishra et al. 2020; Anil et al. 2022 Wang al. 2024a Kazemnejad al., 2023 Zhou et al. 2024b] Awasthi & Gupta 2023] Telassi et al. 2023 2024 Chang & Bisk (024) with no theo-
retical explanation as to why. For instance, while transformer decoders can easily copy long strings (Bhattamishra et al. 2024), length generalization is substantially more brittle: Transformers trained to copy short strings often do not generalize well longer strings when the input string includes repeated substrings (Zhou et al. [2024a] Jelassi et al.] (002)). Similarly, while transformers can in principle simulate many finite-state automata (Liu et al. (023), their success at length generaliza- tion in practice varies widely across different automata (L et al., 2023) Bhattamishra et al. 2020). Theoretical understanding of these phenomena largely lacking, making it difficult to anticipate on which problems transformers will succeed or fail at ningttggnneralzzation.
An important step towards theoretical understanding was made in the RASP-L Conjecture (Zhou eet al., 2024a). This conjecture states that transformers are likely to length-generalize exactly on those algorithmic tasks that can be solved by simple programs in RASP-L, a fragment of the RASP language (Weiss et al.) (202I) with substantial restrictions the ways in which positional informa- tion can be used. While et al. (2024)) provided empirical evidence in support of this idea, two important gaps remain: First, while compelling empirical evidence supports link between defin- ability in RASP fragments and length generalization, no formal proof exists. Second, the RASP-L language has not been fully formalized, so is largely open how prove that certain problem is not representable in it.
"II and AY co-first authors.
LLead senior author. Contact: w www..uunnnsaaaaanaaa.aa.aaa
Code available at atthtpss: / http:///tttuuuuu.o
zatiioo in

---

Published as a conference paper at ICLR 2025
We address both these gaps by presenting general theoretical framework analyzing length gener- alization as ultimate identifiability in the limit for a well-defined class of functions: When the input- output behavior of a given function is observed at increasing imput lengths, can learner converge on inferring the ground-truth function? We give a positive answer for a specific idealized learning strategy: in this setting, transformers are guaranteed length generalize given any function in the aforementioned class, Later, we rigorously characterize the expressivity of this class.
We define an idealized inference procedure in which sequence of transformers is fitted reproduce a target function on successively longer inputs while minimizing a specific norm-based regularizer, producing an infinite sequence of transformers operating on longer and longer context windows. Our results provide conditions under which the computations represented by these transformers converge to a single underlying algorithm reproducing the target function. In this case, generalization is guaranteed for sufficiently long inputs.
Our results apply to multilayer transformers, focusing on causal transformers trained from scratch with absolute positional encodings (APE) or without positional encodings (NoPE). A key technical challenge in analyzing length generalization for absolute positional encodings is the scaling of the transformer's s parameter count with the input length. To address this, we define a transformer-lit limiting object, the Limit Transformer, which encapsulates the computations of a sequence of trans- formers operating longer and longer inputs into single object. Our main theoretical result states that the inference procedure will ultimately lead to length generalization for sufficiently long train- ing inputs, provided the ground-truth function is expressible by a single Limit Transformer across all input lengths:
Theorem 1 (Informal Version of Theorem 7 Let f be the target function expressible by a single Limit Transformer at all input lengths, subject to restrictions on the use of positional information. Choose transformers Tr, (n = 2, 3, ... with context size n, where Tn reproduces the behavior of f up to length 5. while minimizing a norm-based regularizer. Then, for large n, Tn will match the output of the target function f up to length S n.
We then show that the expressivity of Limit Transformers can be understood for many previously studied algorithmic tasks, as well as new ones. We extend recently introduced RASP variant (C-RASP, Yang & Chiang 2024) to provide lower bounds, showing that, under the idcalized in- ference procedure, transformers will succeed at length generalization on various concrete problems. Conversely, we employ communication complexity to obtain upper bounds on the class of functions for which length generalization is predicted. While we have not proven this class is complete, ex- periments confirm that the theory predicts both success and failure at length generalization across various algorithmic tasks and formal languages. Overall, our results formalize the RASP-L Conjec- ture and take step toward theoretical understanding of length generalization.
2 MODEL OF TRANSFORMERS
Positional Encoding Scheme We study two positional encoding schemes. One uses no positional encoding all; we refer to this as NoPE (No Positional Encoding). The other one uses Absolute Positional Encodings (APE), with learned per-position embedding vectors Pi,... PN. We follow Zhou et al. (2024a) requiring transformers be able to perform a task at different offsets within a longer context. Whereas Zhou et al. (2024a) concatenated different examples of a task, we simply encode an input x of length ax]
N using positional encodings Pi+o..... Pk+o where o is an offset such that k + o < N, and require that the transformer correctly performs the task language models, where the same reasoning task can typically appear at different places in a long context. For simplicity, treat positions outside of the input, including those preceding the offset, as empty.
independently of the offset o 2 This mimics the computations
Parameterization We focus on transformers with causal masking; for simplicity, we will use the term "transformer" for these throughout. A transformer T is parameterized by a finite alphabet E, a width E N, token embedding matrix E E R|E]xd a context width N(T) E NO (+x0). positional encodings {p: E Rd < i < N(T) + 1}. depth L E N. head count H E N. key, < S L, 1 < h < II), MLP matrices and biases {A, E Rdxd B, E dddd b, E Rd 1 S I < L). and an unembedding matrix U e R! For matrices, we use || and || denote the spectral and Frobenius norm respectively.
query, and value matrices Ki,,, Q1, Vi, E idxd
2

---

Published as a conference paper at ICLR 2025
Computation of Activations and Outputs We assume standard causal transformer, with a few technical points: We explicitly scale attention logits with the logarithm of the input length, omit layer norm, allow Hcaviside activations in addition to ReLU activations, and assume that, while the transformer may overall compute at infinite precision, attention logits are computed at fixed fractional precision. We next define all computations formally. Reserving special SOS symbol not in M, written as "S", we take the set of input strings to be G, the set of strings I E ) where I1 and $ does not occur in /x.../x/- We now define the computation of the transformer T on an input G where 1 < |a] < NTT) + (that is - | S N(T) if (T) < oc, and |-|| is any finite length otherwise). If is the number of layers, then we write the output of layer | = 1,..., L at position be any offset such that |a| + < (T) + 1 that is, still fits into the transformer's 's context width if encoded at offset o. Given this offset, we set
i = 1, .,.............................. (T) as y Rd. Let
Ez, + Pi+o i i |a|
where 2t E is the input symbol position Attention logits, at query position i and key position j are computed as
(1,)) L.j
(U)-1)/TK? QLAy (1-1) for 1 S i |c:]; 1= L; h h 1, H
(2)
We assume standard softmax attention, but incorporate scaling with log |a: following prior work finding it necessary to theoretically represent sparse functions and circumvent theoretical limitations of soft attention (Chiang & Cholak 2022 Edelman al. 2022):
H Σj= exp llgg |a| an3 (.h)) Vi,n. (111)
y = y
(1-1)
(3)
Σj= exp (log |ao| -al.
1=1
After each attention block, the activations are passed through one-layer MLP:
(1) Bi 11 (AIY," + bi)
(4)
where we allow the activation function t/ to be, in each coordinate, either ReLU Heaviside (see Appendix [.I]] for discussion of this). We omit layer norm, as it plays no important role in our results, but can be accounted for (See Appendix D.3) We assume the activations, with the restriction that attention logits (2) and the output of the exp(-) function are both rounded to p fractional bits of precision before further processing. This is mild restriction preventing tiny changes in attention patterns from potentially snowballing into large changes in the output due to infinite precision (See Appendix D.2p.
setup for
A transformer T maps strings E 6 ([2) < N(T) to vectors of next-token prediction logits,
T(x, o) RI=**E,, where T'x, 0); Uy
[,...,/2)) for the unembedding matrix U R! xd and is the offset. Let F(E) be the set of all maps f mapping x E 6 f(x) E RR x|
L)
3 THEORETICAL FRAMEWORK
3.1 LIMIT TRANSFORMERS
Our theory addresses the setting of transformers with absolute positional encodings, where the width may grow with the input length. Importantly, we cannot view the ground-truth function as realized by a single transformer: Even if one assigned such a transformer an infinite number of positional encodings, it would still effectively only be able to distinguish between bounded number of po- sitions, because the width of positional encodings within a single transformer is bounded. Instead, will derive parameterization of transformers that allows to convert sequences of transform- ers operating on longer and longer sequences to a single limiting transformer-like object. Our key technical idea is to reparameterize the transformer in terms of product functions, inner products of parameter vectors as mediated by parameter matrices, such as
EY KT SI.LLE E, p KTT Q VIP,
P KG Q1AP; U, V,
(5)
3

---

Published as a conference paper at ICLR 2025
and various others; see Appendix F.1 for the full formal definition. We first note that the trans- former's computations are uniquely specified by such products. The number of products as in (5) depends, among others, on |-|, L, H. (T), but crucially not on d. We will use this parameteri- zation to translate sequences Ti, 72, 73,... of transformers running on inputs of length 2,2,3, ..... to limiting transformer-like objects that are applicable all input lengths, while keeping width d bounded even if the widths of nn diverge to infinity. This limiting object, Limit Transformer, differs from an ordinary transformer, as defined in Section 2 just in a few respects. Formally:
Definition 2. A Limit Transformer is a transformer T where:
1. N(T) = +00
2. All parameters (including positional encodings ps, and the output of @1,1) are expressed in p-bit precision, for some p E N
3. Attention logits input length N computed
(1hh)
(0) 1 TT, K.,. (111) + dn,(i,
where ΦL N N IR
The most important point is the third one, which augments the attention logits (Eq. 2 with a second term, II (j, i), where ΦI is potentially arbitrary function. Thus, Limit Transformer can use positional information in two ways: through bounded-widd and bounded peeeedd-reeisionn positional en- codings p;, and additionally through potentially more complicated functions 0r,6. Our main result will link length generalization to expressibility by Limit Transformers satisfying specific properties:
Definition 3. A Limit Transformer satisfies
1. PERIODIC if p, = & for all for some À >
2. LOCAL if each di.,. is translation-invariant and local.
Here, a function f : N + R is irraslation-imvariane if f(i,j) ((lt,, and "local" if there is T such that f((i,j) = when j i
The parameterization in terms of inner products permits a translation from transformer T to bounded-width Limit Transformer satisfying PERIODIC and LOCAL (Lemma 52 in the Appendix). In this translation, products of the form p. Qt..P, are encoded into the functions dL (ē. per- mitting the Limit Transformer to distinguish infinitely many different positions even while keeping its width bounded. We note that Limit Transformer are a mathematical construct helping us prove statements about standard transformers, and are not themselves trained or implemented.
3.2 DEFINITION OF INFERENCE PROCEDURE
To define the inference procedure, we specify the following hypothesis class at each input length no 3, ..., define the hypothesis class On as the set of transformers T (as defined in Section 2 where (1) N(T) n, (2) each parameter vector and matrix T is represented at p bits of precision. for some p E N, (3) each product function involving positional encodings is translation conslation-invariant. That is, every product function involving exactly one positional encoding is constant across positions, and for every S i, A, ASA n,
Definition 4 (Hypothesis Class). For each
p.
= M MM...MMPi44
(7)
whenever M .M, is a product of parameter matrices linking the inpul layer
Note that the width d of the transformers T E ④ is unconstrained. The most interesting requirement here is the third one: We ask that, while the positional encodings will typically vary with position, their contributions to the transformer's computations are offset-indeeendentt This is stronger quirement than for the input-output behavior to be offiettindeeennent we ask for the transformer's "algorithm" itself be the same across offsets. This is substantive condition, but to be a natural requirement in the context of length generalization (Appendix (.6). Our inference procedure will use regularizer R favoring simpler hypotheses. The following will be sufficient:
believe it
Such KT Q1h. V2 K! 3,10 Q3, Vi, and similar. See Appendix
E2 for formal definition.
4

---

Published as a conference paper at ICLR 2025
Definition 5 (Regularizer). Let T On thus (T) Define R(T) as the (1) L+ H; (2) the precision used in Definition(4 the precision p used for rounding attention logits and the oupur of exp (Section 2 (3) max,, rank(Vi,,)) (4) max4, [K] Qt,kll max4, [| max; ||
[Bll ||U|| (5) max; ||Pil22 max |B max | lb: :: (6) the term
L
H
N(T)
ΣΣΣ
Σ
K Qtmp,|
(8)
1=1
The idea of (8) is to discourage accidental attention between far-away positions that do not appear together during training, which could hamper length generalization. Due to translation invariance, this term entails a bound on products for all pairs P. (i S j) entering causal attention. While such a regularizer is not part of standard training, standard initialization tends lead to bounded values for (8) when d is large (Appendix G.Ip; p: it thus captures implicit bias of standard initialization and training. Importantly the width does not explicitly enter R; as consequence, for any sufficiently large C, the number of transformers T, On with R(T,) I C is infinite, simply because d is not constrained. Nonetheless, this regularizer will be sufficient for identification under our idealized inference procedure, which observes the input-output behavior of the target function f inputs of length < 2 and selects a transformer T with maximal context window n, T E O, that exactly fits that input-output behavior while minimizing the regularizer R(T)::
Definition 6 (Inference Procedure). Given a function f F(E), the Inference Procedure obtains a sequence of transformers Tı E 2,, 2 E θ..... as follows. Define Un as the set of T E Or matching the behavior of f on all inputs of length 3. Then choose Tn Un such that
R(T,) S inf R(T) TEU,
(9)
In 99, we do not simply ask for minimizing the regularizer, as the set of elements Un with R(T) smaller than given value need not be finite and thus minimum need not be attained by any Tr. Importantly, we only ask Tr to match the behavior of f up to length 5. formalizing the idea of training on shorter inputs and testing on longer ones; our identifiability guarantee will provide conditions under which Tn will end up matching f correctly up to length n representing length generalization. While take the testing length to be twice the training length, there is nothing special about this; our analysis works whenever the training length diverges to infinity.
3.3
MAIN RESULT: CONVERGENCE OF INFERENCE PROCEDURE
Our main result asymptotically characterizes length generalization under the inference procedure from Definition 6 For functions representable by Limit Transformers satisfying LOCAL and PERI- ODIC, we guarantee that any run of the Inference Procedure will ultimately achieve length general- ization, so that transformers with context length chosen to fit the target function on inputs with length < a will, when n is sufficiently large, also perform correctly at all lengths I n. Formally,
2
Theorem (Guaranteed Length Generalization in the Limit). Let e F(E). Then the following are equivalent:
1. f is expressible by Limit Transformer satisfying PERIODIC and LOCAL.
2. (Guaranteed Length Generalization) Applying the Inference Procedure from Definition 6 generates sequence Tı, Ti,T2.--. with suPm=1.2.3... R(T,)) <, cc, for which there some No such that, for all m > No. T... matches f on all inputs of any length k S m.
The formal proof is in Appendix B. Intuitively, if f expressible by a Limit Transformer satis- fying PERIODIC and LOCAL, then, even though the Inference Procedure produces infinitely many distinct transformers Ti, T2,.... these can only traverse a finite set of underlying algorithms, each described by some Limit Transformer. PERIODIC and LOCAL ensure that the Limit Transformer's parameter count effectively remains finite, as its position-relatee related parameters can be fully specified in terms of ....... PA and 611, .). .0,,,,,(1,, r). of the Limit Transformers; this keeps the set algorithms traversed finite. Each of these finitely many algorithms will either be ruled out at some input length n, or else match the behavior of at
The regularizer bounds width. depth, and precision
5

---

Published as a conference paper at ICLR 2025
all imput lengths. At some finite No. only the latter type of algorithm remains; hence, transformers produced after this point will match the target function. The proof also entails a result on NoPE length generalization: Applying the inference procedure to while constraining p; = 0 will lead to length generalization when f' is expressible by a Limit Transformer where all p; and all Φ1. are zero (Corollary T8p. While Theorem 7 guarantees length generalization from length / to length n for expressible problems, it does not rule out length generalization for inexpressible problems. Such statement becomes possible if we allow arbitrary scaling of training vs. testing lengths (Ap- pendix [B44). Besides length generalization guarantees, Limit Transformers are also useful in pro- viding expressiveness results for transformers with absolute positional encodings (Appendix(B.3
4 WHICH FUNCTIONS ARE IDENTIFIABLE? EXPRESSIVENESS OF LIMIT TRANSFORMERS AND C-RASP
We have found that, if a target function f is expressible by a Limit Transformer satisfying PERIODIC and LOCAL, then Theorem 7 implies length generalization under our Inference Procedure. In order to understand the ramifications of this result, we now study what functions Limit Transformers can express for these functions, Theorem 7 will then guarantee length generalization.
4.1 SIMPLE EXAMPLE: INDUCTION HEAD
We consider the task of predicting the next token in proportion to the frequency at which different tokens had previously followed tokens matching the current one:
IN) [ < 1 21, 2K+1
(10)
#1k < : x2
A Limit Transformer solves this with the Induction Head construction Olsson et al. 2022). in two layers and one head: In the first layer, Φ(t,5) = 1 if i + 1 = and 0 else; the head copies the preceding symbol. In the second layer, attention focuses on positions with the same symbol. The transformer outputs next-token predictions in proportion to bigram frequencies in the context, up to approximation error ) (due to logit scaling). Hence, Theorem 7 guarantees that the Inference Procedure will exactly once; here, such an induction head circuit suffices to copy a string (Zhou et al. 2024a), we thus obtain a length generalization guarantee for copying such strings (see Section 55).
(1O). A special of (IO) occurs when each symbol occurs
4.2 LENGTH GENERALIZATION FOR C-RASP
We next present a large class of functions for which Theorem guarantees length generalization. We extend the C-RASP formalism (Yang & Chiang, 2024) with positional information, and then show that any function defined by a C-RASP program is expressible by a Limit Transformer; hence, transformers will, by Theorem 7 eength-generalize
those functions. We first define C-RASP:
Definition 8 (C-RASP). Let Σ be an alphabet, let & be a set of unary relations & : N + 10,1), and let V be is defined as a sequence Pı,..., Ps. of C-RASP operations. There are two sorts of operations:
of binary relations và N x N - {0,1). A C- Y program P
.....P.
Boolean- Valued Operations
Count- Valued Operations
Initial
P(i) == (i) for E Σ
Counting C(i) = # [j s i, (i.j)) P()) for ve E (U)
Boolean
P(i) (P) P(i) = (i( P2(1)
Conditional
C(i) == C() C2(1
Addition
C(i) := +10)+
Constant
P(i) == T
Subtraction C(i) = -
Positional
P(i) ((i) for & E &b
Constant
C(i) := 1
Comparison
P(i) = Ci()) & (2(
Counting operation returns the number of positions j < where P() and (ii hold. A
conditional operation returns (i) if P(i), and C2(i) otherwise. We use the value of the last

---

Published as a conference paper at ICLR 2025
cooluan-valued operation, at the last position of the string. to determine acceptance using C-RASP program. That is, if the program is run on input w with final operation L, then we accept w if and only if L([w]) is true. C-RASP periodie, perioodd,i,ddi,, local] is the class of C-RASP programs where each o(i) is periodic in i, and each () is translation-invarian and local (Definition (3.. We also write C-RASP(periodic, local] for the class of all languages accepted by some C-RASP pperiodic, local]
program. As an example, we present a program recognizing L = k abL* over > {a,
C-RASP program for E' ab over E {a. b)
C.- = و = Qa(1)
# of immediately preceding
(1)
(.- C. (1) 21
Position i 1 holds
(2)
Qas(1) Qo(1) Pa-(1)
substring ab ends at position
(3)
(is(1) = # (j S (a)
of substrings
(4)
L(i) == (1) 21
At least one ab precedes position è (5)
Any C-RASP C-RAAPPperiodic,, local] program can be translated to Limit Transformer with correspond-
ing positional functions. We say a Limit Transformer T accepts an input if the value in the last dimension in the last position of the output greater than 0, and rejects otherwise.
Theorem 9. For every C-RASP(4, V program P with local functions Y and periodic functions & there exists Limit Transformer Too that satisfies PERIODIC and LOCAL such that for all E", P accepts w of accepts Sw. If P uses no local or periodic relations, then T requires no functions oth or positional encodings p:.
The proof is in Appendix B.6 As a consequence, the Inference Procedure will ultimately length- generalize on inputs from a function f expressible by a C-RASP C-RASP program requires positional functions (i.e., is in C-RASP(0)). then length generaliza- tion will succeed even with NoPE transformers. We establish that various functions are in C-RASP:
local| program. the
Theorem 10. Membership in the following languages is definable in C-RASP(0): (1) MAJORITY, (2) DYCK-I, (3) c..
The proof is in Appendix C.I By Theorem 2 these positive results translate into length general- ization guarantees. For these tasks, length generalization even with NoPE is empirically already well-documented (Bhattamishra et al. 2020). Further, C-RASPlocal] can implement versions of the Induction Head task from Section 4. (Appenndi C.2.2 C-RASP also helps understand why transformers show varying abilities even on simple finite-state languages (Bhattamishra al.,
2020
Liu et al., 2023: 2024), fact poorly understood theoretically. For instance, we find:
Lemma 11. Consider the alphabet Σ {a, b)..
1. PARITY 6" (ab" ab") & C-RASP (periodic, local
2. (aa)" E C-RASP (arriPPeeioiic,, local) and (aa)" & C-RASP(0)
3. be & C-RASP C--RAPPpperiddic, local)
4. I. E C-RASP(O) for piecewise testable
The proof is in Appendix C.3 Notably, all of these languages are recognizable by simple finite-state automata which are expressible by transformers (Liu et al. 2023), but empirical length generaliza- tion behavior differs in line with C-RASP expressiveness (Section 5). PARITY (1) has long been
found difficult for transformers (e.g. Hahn 2000 Bhattamishra et al. 2020 Anil et al. 2022 Chiang
& Cholak 2022 Delétang et al. 2023 Hahn & Rohn| 2024). Result (2) exemplifies the effect of dif-
ferent positional relations. The language he (3) is simple model of FlipFlop (Liu et al. 2024). a language on which transformers empirically struggle to generalize perfectly despite its simplicity
for recurrent models (Liu et al. 2024 Sarrof et al. 2024). The class (4) is useful for determining
expressibility of languages in C-RASP (0). as Section 1.1
4.3 LIMITATIONS: LOGARITHMIC COMMUNICATION COMPLEXITY
Having shown that various functions definable by Limit Transformers, provide simple technique for showing that various functions are not definable by Limit Transformers. Informally, any function satisfying the conditions in Theorem 7 has logarithmic communication complexity:
7

---

Published as a conference paper at ICLR 2025
Theorem 12. Let T be a Limit Transformer satisfying PERIODIC and LOCAL. On input I E ΣRN, assume Alice has access to IN..N and Bob has access to 2N.1...2N- Then Alice can communicate C log N bits Bob, where C depends on T but not N, so that Bob can compute each 1 activation in the second half, y. (N+15is 2N).
The proof is in Appendix B.3 In principle, computing activations in the second half of the input requires full knowledge of the first half of the input, because positions in the second half can freely attend positions in the first half. In this situation, one would expect Bob to need full knowledge of 2 input symbols from Alice's 's part, exponentially more than the C' Colog N claimed in the theorem. This is indeed needed if T' performs the task of, say, checking if æ1....N and 2 are identical. However, if T satisfies PERIODIC and LOCAL, attention must largely be determined by the pres- ence of tokens and token sequences; when an attention head's behavior is determined by positional information, it can only focus its attention on a local neighborhood or equally distribute it over periodic pattern. Intuitively, in such cases, the set of possible queries and keys can be grouped into finite partitioning, of size bounded independently of N. It then suffices for Alice to communicate, for each possible group of keys, an aggregate of the value vectors at the positions where a matching key is computed. The proof (Appendix (B.3) formalizes this. As corollary:
N
Corollary 13. The following problems are not expressible by Limit Transformers satisfying PERI- ODIC and LOCAL: (1) copying arbitrary strings, (2) addition of n-digil numbers.
This is proven in Appendix B.3 As consequence, any run of the Inference Procedure on these functions will output solutions Ti, T2, T3.... for which the depth, number of heads, parameter norms or ranks, MLP dimensions, or precision p. must increase with the input length n; indeed, length generalization is empirically challenging for these functions (Section
5 EXPERIMENTS
We evaluate the expressiveness of Limit Transformers and C-RASP as predictors of empirical length generalization. Based generalize on problems with a C-RASPPperiodic..oaaa
Srreorems[aand] expect that APE transformers should length-
program, and that NoPE transformers will be successful on problems with a C-RASP[0] program. We test this prediction on suite of algo- rithmic problems and formal languages, largely from prior empirical work on length generalization (Bhattamishra et al. 2020 Zhou et al. (024a), but evaluated within a uniform framework.
For each task, the model is trained on inputs whose LEN is in the range [miin 50). where mmi is the minimum length for this task. LEN is the length of the input the algorithmic tasks (Appendix [H.2). and the overall sequence length in the formal language tasks. The model is tested on 3 test sets, where LEN is in the range [iminn 50), [51, 100). [101, 150]: these lengths are based on the source of the regular languages benchmark (Bhattamishra et al., 2020). We trained using a standard Adam W setup; see details in Appendix [E.3 Hyperparameters are selected by searching in order of increasing complexity until we find setting that performs well up to length 100. We interpret results on lengths [101, 150] as a measure of length generalization. Each model has as many positional encodings as needed to encode the longest inputs (at least 150); each input is presented with tasks,
random offset in agreement with the theoretical setup. On algorithmic sequence-to-sequeee train with cross-entropy loss the output. On formal languages, where next-symbol predictions are generally not deterministic, we instead train the model to predict the set of legal next symbols, with each such set coded as an atomic symbol (as in Bhattamishra et al. 2020 Sarrof et al., 2024). At test time, predictions are considered correct on sequence if and only if the output at every step correct; the random baseline is thus very low on the formal language benchmark. We report accuracy as the fraction of test sequences where the predictions are correct at each step.
We first evaluate on algorithmic problems, which largely overlap with Zhou et al. (2024a), but are tailored to those where C-RASP expressiveness can be clearly settled. Tasks are defined formally in Appendix E.2. A new problem here is BINARY MAJORITY INTERLEAVE, which interleaves multiple MAJORITY functions and can be solved by C-RASP using periodic functions. Length generalization behavior matches C-RASP expressiveness: C-RASP(0) expressiveness predicts the success of NoPE (see Figure ID. In agreement with prior empirical results (Zhou et al., 2024a Jelassi et al. 2023), COPY is difficult in the presence of repetition and easy when it is avoided; these findings match C-RASP expressiveness (Corollary 13 and Section 4.1.
8

---

Published as a conference paper at ICLR 2025
Foand CRASPPuriaiic Locdl] Program
No CRASPPPricdi, Looaf] Program
Found CRASP]) Program
No CRASP) Progaam
Binary Majority
Binary Majerity
Majority
100
100
100
100
3
30
50
50
50
Bn
Bin
Bn2
Bln1
Bin
Copy
Copy
Unique
Repeat
Parity
Addition
100
100
76
50
50
50
0-
Bm
Bn2
Bin
Bn2
3
Bin1
Bin2
Bin
Bin
Bin
Figure 1: Experimental results (y axis: accuracy), at lengths < 50 (Bin 1, training), [51, 100] (Bin 2), and [101, 150] (Bin 3, generalization), for APE (solid) and NoPE (dotted). Green lines indicate that we found a C-RASP program (C-RASP(peen) periodic, local] for APE, C-RASP[0] for NoPE), red lines indicate that we proved nonexistence, or found no program. Random baselines are indicated in gray in (left), and very close to zero in (right). On the algorithmic problems (left), repli- cate prior empirical findings; C-RASP expressiveness predicts observed length generalization. On the regular languages (right, with same and y-axes left, Table 2). length generalization tracks C-RASP expressiveness established in Lemma II (11) (aa)", (17) = be""") and other results (see Appendix E. C-RASP expressiveness performs much better than circuit complexity and standard notions of regular language complexity predicting length generalization (Appendix, Figures 3
We next applied the experimental framework to 17 regular languages assembled by Bhattamishra eet al. (2020), who evaluated length generalization in transformers and LSTMs. Whereas LSTMs perform strongly across the board, the behavior of transformers on these regular languages has so far eluded theoretical understanding. While it is known that transformers struggle with PARITY, it has remained unclear why they would struggle languages. We found C-RASP periodic.local programs for 13 of the languages and proved nonexis- tence for the others (Appendix E.1.2). Length generalization succeeded in those cases where we had found C-RASP[periodes local] program (see Figure [ right). In those cases where C-RASP(0) program exists, generalization also succeeded with NoPE. Generalization failed for languages where no C-RASP program exists, such as be" (#17 in Figure I Lemma
eength-generaiiz on some seemingly very simple
6 DISCUSSION
Prior work has empirically found that transformers' length generalization capabilities differ between tasks, but thcoretical understanding has been lacking. We have introduced a formal framework analyzing length generalization in idealized inference procedure. The framework explains the commonality across diverse tasks where successful length generalization has been observed in prior research, in terms of expressiveness in two simple mathematical formalisms, Limit Transformers and C-RASP. We also proved that various problems, on which length generalization is less successful empirically, are not expressible in one both of these formalisms. Beyond length generalization, the framework further sheds light on the expressiveness of APE transformers. Our results on length generalization study an idealized regularizer and assume perfect fitting of the training distribution. Making the guarantee from Theorem 7 more realistic by incorporating SGD training dynamics and subsampling of training data is an interesting problem for future research.
Our results can be viewed as formalizing the RASP-L Conjecture (Zhou et al.) 2024a). Both Limit formalize intuitions underlying RASP-L in restricting how positional information can be used. An important advance over Zhou et al. (022aa) is that we settle the expressiveness of these formalisms for many problems, and are able to explicitly prove a variety of problems with poor empirical length generalization, such as copying with repeated strings, to be inexpressible by Limit Transformers. Our results provide a step towards rigorously confirming the idea that expressiveness in such restricted formalisms predicts length generalization.
Transformers and C-RASP[periodic..ocal

---

Published as a conference paper at ICLR 2025
Expressiveness of Transformers A substantial line of research has studied the in-principle pressiveness of transformers (Strobl et al. 2024). Transformers express a subset of the class TC but unknown if this inclusion proper. All prob- lems considered in Section S are in TC", but empirical length generalization behavior largely tracks C-RASP(periodic.ooaal expressiveness, which defines proper subelass of TC (Appendix C.3.1 While it remains open if the expressive power of transformers exhausts TC our results suggest separation between TC" and those problems for which length generalization is possible with abso- lute positional encodings. In particular, our results suggest that the existence of APE transformers that perform task across larger ranges of input lengths is linked to the expressiveness of Limit Transformers (Section C. It is an open question how far new, yel-to-be-discovered positional en- coding schemes may increase the range of length generalization; empirical evidence indicates that NoPE and APE may be hard to beat by other purppose encodings (Kazemnejad et al. 2023). The proof of Theorem is closely linked previous communication-compl.....
(Merrill & Sabharwal 2023b, Strobl 2023). |trobl|
bounds for trans- former layers (Sanford et al. 2023 2024: Peng et al.) 2024 Bhattamishra et al., 2024), which im- portantly were shown only for individual layers, not multilayer transformers. Indeed, [Bhattamishra et al. (2024) showed that such logarithmic bound is not in general possible for arbitrary multi- layer transformers. In contrast, our result applies even at multilayer models, which is enabled by the restrictions on the ways in which positional information can be used in a Limit Transformer.
Length Generalization of Transformers Various studies have empirically evaluated length gen- eralization in transformers. Our work is most closely related to Zhou et al.] (2024a). discussed above. Bhattamishra et al. (2020) study length generalization on formal languages: we find that C- RASP periodic.local expressiveness explains behavior on their benchmark well (Section [5. Anil al. (2022) show that language models, finetuned on various reasoning problems, do not length- generalize well. Wang et al. (2024a) evaluate length generalization of NoPE transformers on real- world tasks. Kazemnejad et al. (2023) explore length generalization across different positional en- coding schemes, finding NoPE to perform surprisingly well. Zhou al. (2024b) show that length generalization for addition improves with specific encoding schemes and input formats. Jelassi et al. (2024) show that transformers can succeed in length generalization copying when inputs avoid 7--rrmm repetition. Chang & Bisk (2024) empirically find limitations in generalization in counting. In contrast the rich landscape of empirical studies, theoretical understanding of length general- ization has been limited. Most relevant, [Ahuja & Mansouri] (2024) study length generalization in simple neural architectures, including one-layer transformer setup with linear (not softmax) atten- tion. Our results, in contrast, apply to multi-layer softmax transformers and make statements about many concrete problems that have been studied empirically. Some other works (c.g. Hou et al.) Xiao & Liu 2023) provide negtt-gennrallzing constructions for certain problems, but leave open whether learning would lead to such constructions. |Wang et al. (2024b) show that GD training leads to length generalization on a specific token selection task.
2024
Limitations We study idealized asymptotic identification of global minimum with perfect knowledge of behavior on the training distribution (cf. Q.4 in AArr more discussion). Extend- ing Theorem 7 to account for subsampling the training data and learning dynamics is an important problem for future research. In particular, providing a practical upper bound on the threshold No which length generalization is expected an interesting problem. Our study focuses on absolute positional encodings; extending it to other positional encodings (e.g. [Su et al. 2024 Press et al.) 2021 Ruoss al. 2023) another important problem for future research.
7 CONCLUSION
We have introduced a theoretical framework that unifies broad array of empirical findings about successes and failures of length generalization in transformers with absolute positional encodings. Our framework is based on the analysis of an idealized inference procedure, for which length gen- eralization provably happens whenever the ground-truth function is expressible with only limited access to positional information. By providing upper and lower bounds on the expressiveness of transformers trained using this inference procedure, we accurately predict the success and failure of length generalization across wide set of algorithmic tasks and formal languages.
10

---

Published as a conference paper at ICLR 2025
CONTRIBUTIONS
MH coordinated the project. MH and XH developed the conceptual framework of Theorem 7 with input from the other authors. XH and YS contributed Section | AY contributed Section with
input from MH and AK. MH, XH, AY, YS jointly developed the translation to Limit Trans former; MH worked out the formalization. SB contributed Proposition 54 Lemma[56] and provided concep- tual input throughout the project. AK contributed to settling the C-RASP expressiveness of formal languages. PN and HZ provided conceptual and writing-level input over the course the project. MH drafted the remaining portions of the paper and the proof of Theorem 7 including definitions and lemmas.
ACKNOWLEDGMENT
Funded by the Deutsche Forschungsgemminnccatt (DFG, German Research Foundation)- - Project- ID 232722074 SFB 1102. MH thanks Lena Strobl, Dana Angluin, David Chiang, Mark Rofin, Anthony Lin, and Georg Zetzsche for conversations on related topics. We thank Entang Wang for comments the draft. We also thank anonymous reviewers for their close reading and detailed feedback.
REFERENCES
Kartik Ahuja and Amin Mansouri. On provable length and compositional generalization. arXiv preprint arXiv:2402.0485 04875, 2024.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Am- brose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 95:38546-38555 2022.
Pranjal Awasthi and Anupam Gupta. Improving length- gemeralization in transformers via task hinting. CoRR, abs/2310.007266, 2023. doi: 10.48500ARXXI.2310000222 URL https:
//doi. 48550/ 2310. 2370.00766
Pablo Barcelo, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii. Logical languages accepted by transformer encoders with hard attention. In The Twelfth International Conference on Learning Reprexentations, 2024,
net nwt./orunfff forum?
id=gbbH7q0 7mq]
David A Mix Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. Regular languages in NC1. Journal of Computer and System Sciences, 44(3):478-499, 1992.
Christoph Behle, Andreas Krebs, and Mark Mercer. Linear circuits, two-variable logic and weakly blocked monoids. In Luděk Kučera and Antonín Kučera (eds.), Mathematical Foundations of Computer Science 2007, pp. 147-158, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. ISBN 978-3-540-74456-6,
Christoph Behle, Andreas Krebs, and Stephanie Reifferscheid. Regular languages definable by majority quantifiers with two variables. In Volker Diekert and Dirk Nowotka (eds.), Developments in Language Theory, pp. 91-102, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-02737-6.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online. November 16-20, 2020, pp. 7096-711 116. Association for Computational Linguisties, 2020. 10. 106538661122222 emn www.mmnnmmmme 1p-ma p .576
URI. https: //do: .rrg/
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations the repre- sentational capabilities of transformers and recurrent architectures. CoRR, abs/2406.09347,, 2024.

---

Published as a conference paper at ICLR 2025
doi: 10.4855/ARRXV.2446000222 09347
Michaël Cadilhac and Charles Paperman. The regular languages of wire linear AC Acta Infor- matica, 59(4):321-336, 2022. doi: 10. 10.107/500236-002--00422222 htth::tt: /rrg/
10.1007 0000000000033--222220
Yingshan Chang and Yonatan Bisk. Language models need inductive biases to count inductively. CoRR, abs/2405.20031,, 2024. doi: 10:4550/ARKXV.205522033.. URL htthhttps://oo .org/
10. 10.48550/ar2111 240.:xiii...........m 2405.20133 20131
David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022, pp. 7634-7664. Association for Computational Linguistics, 2022. doi: 10. 100.8655/11222244L--LL00 2022.ac1-long 527.
URL
Arthur Conmy, Augustine Mavor-Parker, Aengus Lynch, Stefan Heimersheim, and Adrià Garriga- Alonso. Towards automated circuit discovery for mechanistic interpretability. Advances Neural Information Processing Systems, 36:16318-16352 2023.
Colin De la Higuera. Grammatical inference: learning automata and grammars. Cambridge Uni- versity Press, 2010.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Mareus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the chomsky hierarchy. 2023. URL #bxHAzke@on
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation self-attention mechanisms. In International Conference on Machine Learning, pp- 5793-5831, PMLR, 2022.
Benjamin L Edelman, Ezra Edelman, Surbhi Goel, Eran Malach, and Nikolaos Tsilivis. The evolution of statistical induction heads: In-context learning markov chains. arXiv preprint 1rXiv:2402.11004, 2024.
Michael Hahn. Theoretical limitations of self-attention neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171 171, 2020.
Michael Hahn and Mark Rofin. of the 2024 Annual Conference of the Association for Computational Linguisties (ACL 2024), 2024. arxiv Preprint 2402.09963.
Why are sensitive functions hard for transformers? In Proceedings
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-810, 2022.
Kaiying Hou, David Brandfonbrener, Sham M. Kakade, Samy Jelassi, and Eran Malach. Universal length generalization with turing programs. CoRR, abx/2407..33110 2024. doi: 10. 4050/////.X... 2407.03310. URL httpp::///oo http:///.....00/00//222220000000
Samy Jelassi, Stéphane d' Ascoli, Carles Domingo- Enrich, Yuhuai Wu, Yuanzhi Li, and François Charton. Length generalization in arithmetic transformers. CoRR, abs/2306. 15400, 2023. doi: 10. 2S550/ARRIIV.230.11544.
BtLLhhtts::/// //tpi. wrw/10...1..... 48550/ arwiv 2306 15400
Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. Repeat after me: Trans- formers better than state space models at copying. In Forty-first International Conference Machine Learning. ICML 2024, Viemna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL
net /ttp://rmmmmiouoooeeeeeee http://ppaanaooeeeeeeeeeeooooaea
12

---

Published as a conference paper at ICLR 2025
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. In Al- ice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 files//pperr22233/1a Conference.
16, 2023, 2023. URL
A Coneraaoooootoreeeeeeeeeeeee html
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization transformers. Advances in Neural Information Processing Systems, 36, 2024.
Andreas Krebs. Typed semigroups, majority logic, and threshold circuits. PhD thesis, Universität Tübingen, 2008.
K-J Lange. Some results majority quantifiers over words. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pp. 123-129. IEEE, 2004.
Ming Li and Paul Vitányi. An Introduction Kolmogorov Complexity and its Applications. edition, 2008.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representa- tions, 2023. URL https:://ppenreriiiiie Detp://wwweeeetoommddddddeddeeee
Bingbin Liu, Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Exposing attention glitches with flip-flop language modeling. Advances in Neural Information Processing Systems, 36, 2024.
Robert McNaughton and Seymour A Papert. Counter-Free Automata (MIT research monograph no. 65). The MIT Press, 1971.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In NeurlPS 2023 Workshop on Mathematics of Modern Machine Learning, 2023a. URL https: //openreview nwt. http///ormmmmmmmmmeememeee
William Merrill and Ashish Sabharwal. A logic for expressing log-precision transformers. In Thirty- seventh Conference on Neural Information Processing Systems, 2023b.
William Merrill and Ashish Sabharwal. The parallelism tradeoff:: Limitations of log-precision trans-
formers. Transactions of the Association for Computational Linguistics, 11:5315545, 2023c.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. Advances in neural information processing systems, 30, 2017.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209. 2022.
Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. arXiv preprint orXiv:2402.08164, 2024.
Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108. 12409, 2021.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 188):9 2019.
Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Ben- nani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. arXiv preprint, 2023.
13

---

Published as a conference paper at ICLR 2025
Clayton Sanford, Daniel J. Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In Alice Oh, Tristan Naumann, Amir Glober- son, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural In- formation Processing Systems 36: Annual Conference on Neural Information Pro- cessing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023, URL
nips. ccpp.cc/pappe files/paperr20233 h 73bf69244 E (177444439999c998888 Abs Cowpeet-oooeeeeneeeem html
Abstract
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. One-layer transformers fail to solve the induc- tion heads task. arXiv preprint, 2024.
Yash Sarrof, Yana Veitsman, and Michael Hahn. The expressive capacity of state space models: A formal language perspective. CoRR, abs/2405. 177394 2024. doi: 1048500ARRXIV2255.733)
URL /ttp::///ooi..//1100.. 48540/ arxiv. 2405.
Marcel Paul Schüizzeberrger. On finite monoids having only trivial subgroups. Inf. Control., 8(2):
190-194, 1965.
Noam Shazeer. GLU variants improve transformer. arXiv preprint arXiv:2002.05200 2020.
Lena Strobl. Average-hard attention transformers are constant-depth uniform threshold circuits. CoRR, abs/2308 032112, 2023. doi: 10-4855/ARXXI.23000082)) URL httpp:://///. 10. 1.0.4550/arXiv. 03212
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What Formal Lan- guages Can Transformers Express? A Survey. Transactions of the Association for Computa- tional Linguistics, 12:543- 561, 05 2024. ISSN 2307-387X. doi: 10060633 URL
https: /ttp////c... 11t.taa1l1/aaaccc. a 00663
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: En- hanced transformer with rotary position embedding. Neurocomputing, 568: 167066,, 2024.
Pascal Tesson and Denis Thérien. Diamonds are forever: The variety DA. In Semigroups, algo- rithms, automata and languages, pp. 475 World Scientific, 2002.
Masaru Tomita. Dynamic construction of finite-state automata from examples using hill-climbing. In Proceedings of the Fourth Annual Conference of the Cognitive Science Society, pp. 105-108, 1982.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
Jie Wang, Tao Ji, Yuanbin WI, Hang Yan, Tao Gui, Qi Zhang, Xuanjing Huang, and Xiaoling Wang. Length generalization of causal transformers without position encoding. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Linguistics, ACL 2024, Bangkok, Thailand and virtual meeting, August 11-16, 2024, pp. 14024- 14040. Association for Computational Linguistics, 2024a. URL hallattts//acaathhhttt org/ 1ttp:2222....nni www.ffiinnnnnnaane acl. 834
Zixuan Wang. Stanley Wei, Daniel Hsu, and Jason D. Lee. Transformers provably learn sparse token selection while fully-connected nets cannot. In Forty-first International Conference Machine Learning. 2024b.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Confer- on Machine Learning, pp. 11080- 1190.. PMLR, 2021.
Changnan Xiao and Bing Liu. Conditions for length generalization in learning reasoning skills. CoRR, 11./2311..61777 2023, doi: 10.48550/RRXI.2311..111 URL [RL/attps://cc..co 10. 20.48850/a200 (0/550//aXivv 2311.1611 16173
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. In First Conference on Language Modeling, 2024. URL https:
//openrevi ew. wwt.fforuus http:mmmmmmdmmmmmmmu.uu..
14

---

Published as a conference paper at ICLR 2025
Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transformers recognize actly the star-free languages. arXiv Preprint, 2023.
Hattie Zhou, Arwen Bradley, Etai Littwin Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms transformers learn? A study in length generalization. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024a. URL /ttpp:://gpenzevien. AdsSsssummii
Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou. Transformers can achieve length generalization but not robustly. CoRR, abs/2402.0937// 2024b. doi: 10.48500/ARXIV.240200911 URL https: //t::///oiio wttp.//..../0///.......... 2402. 09371
15

---

Contents
Introduction
2
Model of Transformers
Theoretical Framework
3.1
Limit Transformers
3.2
Definition of Inference Procedure
3.3
Main Result: Convergence of Inference Procedure
4
Which Functions are Identifiable? Expressiveness of Limit Transformers and C-RASP
4.1
Simple Hxample: Induction Head
4.2
Length Generalization for C-ASSP
6
4.3
Limitations: Logarithmic Communication Complexity
5
Experiments
6
Discussion
7
Conclusion
10
FAQ
17
B
Proofs about Limit Transformers
19
Proof of Theorem
19
B.2
Result for NoPE Transtormers
23
B.3
Logarithmic Communication Complexity for Limit Transformer
23
B.4
Statement Main Theorem for Arbitrary Training Lengths
25
B.5
Corollary about Expressivity
26
B.6
From C-RASP to Limit Transformers
26
Expressivity Proofs for C-RASP
28
C.I
C-RASP Constructions
28
C.I.1
Majority
28
C.1.2
Dyck-1
28
C.1.3
a "
29
C.1.4
Existential Quantification
29
C.1.5
Piecewise Testable Languages
29
C.2
C-RASP
periioii, local Constructions
30
C.2.1
Induction Head (Argmax Version)
30
C.2.2
Induction Head (All possible next symbols)
30
C.2.3
(aa)²
31
C.3
Expressibility of Regular Languages in C-RASP periodic.ooal
31
C.3.1
Link to Majority Logic Inexpressibility of Σ"
32
C.3.2
34
C.3.3
Inexpressibility of PARITY
37
Discussion of Design Choices
39
D.I MI.P Activation Functions
................................
D.2 Fixed Precision
D.3 Layer Norm
Additional Details for Experiments
40
E.1
Regular Languages from the Bhattamishra et al 2020 Benchmark
40
E.I.1
Language Definitions
40
E.1.2
C-RASP Expressiveness
41
E.2
Algorithmic Tasks
45
F.2.1
Task Definitions for Algorithmic Problems
45
16

---

Published as a conference paper at ICLR 2025
E.2.2
Limit Transformers and C-RASP expressiveness algorithmic tasks
46
Details of Experimental Setup
47
Translating between Transformers and Limit Transformers
49
F1
Product Parameterization
49
F2
Formal Definition of Hypothesis Class
52
From Limit Transformers to Transformers
53
F44
From Transformers to Limit Transformers
57
F.4.1
Proving Lemma 52
(I): Preliminaries
59
F44.2
Proving Lemma 52 (II): Construction /x
60
F.4.3
Proving Lemma 52 III:: Proving Correctness
63
Additional Supporting Results
71
G.1
Regularizer at Initialization
G.2
Empirical Length Generalization of Positional Functions
................................
73
G.3
Bound for Encodings Norm in Terms of Function Complexity
73
G.4
Positional Abilitics NoPE vs APE]
75
G.5
Conceptual Relation to Solomonoff Induction
76
G.6
The Role of Translation Invariance
77
G.6.1 Non Invariant Transformers Failing to Length- Generalie
G.6.2
Translation- Inverriann-n in Trained Transformers
79
G.7
Comparing APE and NoPE on Induction Head Tasks
A
FAQ
(1) What is the point of introducing Limit Transformer??
Limit Transformers are mathematical formalism helping us prove a length generalization guarantee (Theorem 7 for broad class of functions, not just one specific function. They thus serve as an object that can help us prove things about standard transformers.
(2) What is the relation between Limit Transformers and C-RASP? Why use two different for- malisms?
They serve two distinct purposes one is easier to prove length-generalizztion guarantee with, and the other is easier to prove expressivity results with. Limit Transformers are closely connected to standard transformers, and provide convenient formalism for formalizing length generalization guarantee in our inference setup (Theorem 7): they also provide bounds on APE transformer ex- pressiveness side result (Appendix C. C-RASP is formalism based on the RASP language (Weiss et al. 2021), intended to provide a formal abstraction of the kinds computations that trans- formers perform in a human- readable format. Limit Transformers with PERIODIC and LOCAL express all the functions definable in --RASP(periodicc.oos local], though it is open if this inclusion is strict. We provide rigorous tools for understanding the expressiveness of both formalisms. For Limit Transformers, we prove logarithmic communication complexity bound (Theorem (2). C-RASP brings additional use in understanding expressiveness from two angles. First, one can conveniently prove functions expressible by writing down programs, as we did in Section 4.2 Second, to prove negative results, we can bring to bear set of deep results about logies using majority quantifiers Krebs) 2008), which allow us to provably settle expressiveness of many problems. Positive results translate into positive results about Limit Transformer expressiveness and hence, under our ideal- ized learning setup, length generalization. While it is open if problems not expressible in C-RASP cannot in principle show length generalization, experimental results suggest that such an implication might hold in many cases.
(3) Why are Limit Transformers needed can't one just consider transformers whose parameters have infinite precision and hence accommodate infinitely many different positional encodings p,?
The key advantage of Limit Transformers is that they effectively have finite parameter counts when- ever they satisfy LOCAL and PERIODIC, which useful establishing Theorem 7 In an ordinary transformer, due to fixed width, effectively distinguishing unboundedly many positions requires in-
17

---

Published as a conference paper at ICLR 2025
finitely many parameters P:- Even then, function simple as ((i.j) 6. cannot be exactly represented for infinitely many i,j by product p. Kp, at bounded width d.
We used Limit Transformers as a tool specifically to prove results about APE transformers. We note in Corollary [8] that the analogous results for the special case of NoPE transformers do not require the use of Limit Transformers. Understanding what is needed to derive results for other positional encoding schemes (such as relative positional encodings) is left for future work.
(4) Why is the idealized senup considered for the analysis, as opposed to more frameworkss of learning?
Proving guarantees in a more practical setting (SGD training dynamics, subsampling of training data) would, of course, be ideal. However, such guarantees have been notoriously difficult to estab- lish for deep learning models (Neyshabur et al. 2017). Standard frameworks for learning, such as PAC-learning, assume that the training and test distributions are the same, which precludes out-of- distribution guarantees such as length generalization. Even within the PAC-learning framework, ob- taining nontrivial guarantees for deep neural networks remains challenging without making strong assumptions. Instead of analyzing the learning and generalization of Transformers trained with gradient-based methods, our work aims to understand the length generalization properties of Trans- formers from an architectural perspective. A substantial body of work (cf. Section has empirically investigated the length generalization properties of Transformers and found a complex array of em- pirical behavior, while theoretical understanding has been very limited. Hence, consolidating the theoretical relation between these empirical observations and the computational model of Trans- formers seems like an important direction. Our work provides a formal framework, based an idealized model of learning, that separates the tasks on which Transformers succeed and those on which they fail length-generraize. The learning model considered in work is closely related to the "identification in the limit" setting, which has been widely studied for decades in the context of learning automata and grammars (De la Higuera (010)) Our framework is successful in explaining a wide range of empirical observations (Figure retical framework has been able to explain the empirical patterns in Figure to the extent that our framework can. We hope that further work can build on these insights to establish guarantees that reproduce this success while narrowing the gap between theoretical analysis and practical learning.
This is a substantial advance, as no prior theo-
(5) Why does the length generalization condition in Theorem ask for sup, RTT,) < co? Isn't asking for length generalization sufficient?
If sup,, R(T,.) = co, a transformer T minimizing R(T) while fitting behavior at some length will be unlikely to work at substantially longer lengths, because performing the task correctly at longer and longer lengths requires unbounded increase in R(T)). It might still happen that generalization from length / to length n is possible in certain problems not expressible by Limit Transformers. However, this will depend the problem and the specific scaling of test lengths relative to training lengths; for problems not satisfying the conditions in Theorem 7 length generalization will fail when the test length is made sufficiently longer than the training length, even the training length diverges to infinity. We make this formal in Section B.4.
(6) Given task, how can one settle Limit Transformer and C-RASP expressiveness?
Showing that a task is definable by Limit Transformers or C-RASP simply requires providing an explicit construction, definable in these formalisms, we provide a battery of methods which allow us to provide an answer for many tasks: communication complexity (Theorem 12) applies to both formalisms; for showing non-definability in C-RASP, reduction to specific languages already proven not to be expressible (such as Parity and Lss. see Appendix E.I.2) is frequently useful. Although Theorem 4.2 shows that every function expressible in C-RASP is expressible by Limit Transformers, it is not known whether or not this inclusion is strict.
exemplify for various tasks (Section C.I For showing that a task is not
(7) Why does the guarantee specifically apply to PERIODIC and LOCAL Limit Transformers? What is special about such positional relations?
Local positional relations are important because, if product function of the form p.. Q Kpj. where the rank of Q, K is not constrained, takes nonzero values at unboundedly long distances j i, there is no general reason why the function should sungh--gnerraiiee. Independent initialization of the p.'s 's tends to lead to values close to zero for most of these products (Appendix G.T); ; our Inference
18

---

Published as a conference paper at ICLR 2025
Procedure incorporates this via the term Given this, expects learned model to still exhibit small products at distances not present in the training distribution, and hence a failure of length generalization in the presence of nonlocal product functions. In the translations between standard transformers and Limit Transformers, such local positional relations correspond to the functions 01,
The situation is different for products involving VL matrices, whose rank is penalized by R()); these are able to represent not local, but periodic functions. Periodicity falls out of the setup: In the finite-precision setup, a translation-invariann product function of the form p M M.P, must be periodic in j - whenever one the matrices ..... ..M has bounded rank as the number of positions considered diverges to infinity, with period bounded in terms of the rank (Lemmaa (48). Hence, a transformer E O,. any product function involving one or more Vi,1 matrices needs to be periodic with period bounded in terms of RRT). In the translations between standard transformers and Limit Transformers, such periodic relations are encoded into bounded-wind width bounded- bounded-precisionn positional encodings p; of the Limit Transformer; finite width and precision are sufficient due to periodicity.
B PROOFS ABOUT LIMIT TRANSFORMERS
B. PROOF OF THEOREM 7
We re-state and then prove Theorem
Theorem 14 (Guaranteed Length Generalization in the Limit, restated from Theorem Let f E F(E). Then the following are equivalent:
1. f is expressible by Limit Transformer satisfying PERIODIC and LOCAL.
2. (Guaranteed Length Generalization) Consider the inference procedure from Definition applied to f with RR generating a sequence T2,...... For any such sequence, there is some No such that, for all m > No, T' matches f on all inputs of any length k S m, and s1Pp==1,.3,... R(T,) <
Remark 15. We note that limit transformer Too representing need not itself be offset-invariant. It is sufficient to have
(x, f(z)
(6)
Lemma 47 shows that such a function has sequence of transformers Tn E On which are offset- invariant, even without assuming Too to be offset-invariant
High-Level Proof Sketch The key to the proof is compactness property: Any sequence Ti, T2.... (T; E Q₂) where sup, R(T;) < oo has a subsequence transformers whose behav- ior across inputs can be summarized into single Limit Transformer. For 1=2, given sequence generated by the Inference Procedure, we show that R. stays bounded and use the compactness property show that a subsequence exhibits behavior equivalent f. To show that, in fact, all pos- sible sequences Tn generated by the Inference Procedure ultimately exhibit behavior equivalent to f. when large, we show that subsequences failing attention dot products between far-away positions as input length increases. However, due to the penalty on attention dot products in R. any such sequence would, for large n, need to have higher value of R than sequences avoiding such an increase. For 2=1, we obtain the Limit Transformer from the compactness property applied to the sequence generated by the Inference Procedure. The penalty attention dot products enforces that it satisfies LOCAL; the bounds on the MLP and value matrices enforce that the positional encodings the Limit Transformer can be taken to be periodic.
gengtthgenrralize would exhibit increasing
Preliminaries and Formal Proof We now proceed to the formal proof. We make crucial use of which provide translations between ordinary transformers and
the two technical Lemmas 47 and 52 Limit Transformers.
The following definition will be used:
Definition 16. IfT E O; then define R_ (T) to be R(T) minus the term in Eq. 8
That is,
R(T)) R_ (T) Σ Σ
Inf KT Qu.ppy?
IA ISSEN(T)
19

---

Published as a conference paper at ICLR 2025
The following lemma will be used for both directions of the main theorem:
Lemma 17. Let Ti, T2...., where Tn E en, be sequence generated by the Inference Procedure based on the functional behavior of a function f F, and such that
sup n=1,23....
R(T,) <00
(8)
Then f expressible by a Limit Transformer satisfying PERIODIC and LOCAL, and there is some No such that, for all m > No. Tm matches on all inputs of length l S m.
Proof. As we will be reasoning over the ΦT functions different limit transformers, we use (T) superscript, Pith to indicate the relevant limit transformer.
From the sequence T2,T..... generated by the Inference Procedure, we obtain, using Lemma 52
Limit Transformers Ti, T2.... such that sup, Re (T,) < where
(1 (x(x,,) to,
(9)
and, in each Tn, Tn,
(h.) L (1,5) (1.1) P K QLhP,
(10)
Each limit transformer T; consists of two parts: (i) the collection of its parameter vectors and ma-
trices, (ii) the functions o1,1) We will write T(T.) for the collection of parameter vectors and matrices of T,. Let A == sup, (T,) < co. Then (TT(T) R. s A} is finite, because A bounds (1) the number of parameters, (2) their magnitudes, (3) the precision at which they represented. Hence, only finite number of Limit Transformer parameter settings P(I:) will be traversed as + co. The remainder of the proof devoted to showing that, fact, the number of limit transformers T; itself finite. For this, we need show that each P only traverses a finite
(T:)
(Tt) set of distinct functions as i + co. Each function Pi,k is local; however, priori, they might not be local for any single finite t across the different Tn. We will show that this is not possible, i.e., will show that all proof.
F. 07, are local for single finite This will occupy for the remainder of the
Now note that
R(T,)) E inf (R(T)), + inf (R(T)) TEU.
(TEUm
Because infreu, R(T) is bounded and monotonically increasing in n, infrev, (R(T)) converges limit, say R. Since 1/n + O, the width of the interval converges The Squeeze Theorem then implies that R(T,)) + it.
For each and each we consider
min( T)
Da(T)= Σ
Σ
10th (1,0) R(T..)
1
(T)) has precision bounded in terms of RT,,), (Dn(T): N) is discrete set. An important As oL consequence is that any accumulation point of the sequence (Da(T))neN must equal D,,r)) for infinitely many n.
Consider R_ (T.) (Equation 7p. Let
Rg = lim inf R_ (T,) n-000
(11)
and vn, U2, Va. be such that
lim R_ (_(wv:) Ro 10000
(12)
Then, for some Do.
lim Dw,(ys) = Do 1-000
(13)
20

---

Published as a conference paper at ICLR 2025
and
R= lim R(T,) lim R(Tv.) Ro + Do
(14)
12000
1-720
Indeed,
Do = sup (n(
(15)
20000
because
Do + Ro lim (R- (n.nt)
lim R- (Tr) + lim (n.
(16)
12+20
Define, for each N,
(T) = inf Dz, (T)
(17)
10000
(Ti) As this function is monotonically increasing, and as each 01,h has precision bounded in terms of R(r,,, there must be Too such that (To(T lim (T).
Now define a sequence Ty as follows. For each n, recall from the definition of Dao that
Inm Du, (m) Dn)(n) S (To) 5+0
As 6L has bounded precision, there are infinitely many 24 such that D2, (n) lim in DN, (n). Hence, we can select i(n) E N such that Vi(n) and
Diso (n) = lim inf Du, (n)
Then, for each define TV as the restriction of T (u( to positions to n. As T Tum.. agrees with the behavior of f up to length 2 2. length Then
we also find that Tú agrees with the behavior of f up to
limsup
R(T,)) Ras.RPPPPT)...
sup sup R_ (Tr) + Derco (n)
lim
n=000
n=+00
lii sup R_ (T (Tss ) (To)
n-1n0
=Ro + D (Tx))
Since Ta was created by the Inference Procedure, we have
lim sup R(T)) 2 lim R(T,)
(18)
x=000
On the other hand, since R(T)) R(T2 ) we also have
lim sup R(T)) < lim R(T.)
(19)
x-+20
giving
lim sup R(T,) = lim R(T,)) = Do + Ro n- n-
(20)
Hence,
Ro + Doo (Tx) lim sup R(T")) n-toc
lim R(Tn)
Ro + Do
'In general, if a, + b,, converges and a., b, are bounded, then the limit lim(a, + b.)) equals lim sup a. + lim inf ba. For, assume lim sup + lim inf b, > lim(an + 6.) (similar if > is replaced by <). Then let i(n) he subsequence such that az(a). + limsup Then lim(a, + b,) lim(a baw))) lim sup an + lim baco) 2 lim sup a, lim inf b, > lim(a, b.), contradiction.
21

---

Published as a conference paper at ICLR 2025
and (To() = Do. Now assume there are infinitely many n such that Pi
(Tx)
not Too-laal, hence,
infinitely many n such that (n 2 (Too) + 22,,p, Then:
Do = lim sup D (n)
20000
2 lim sup D, (Too) + +2 2p
n+030
lim inf Du, (Tx)) 22
10000
=Do + 2 2p
This is a contradiction. Here, the first inequality holds because (n) 2 (Tx) whenever > Thex simply because D. (-) is monotonically increasing for each individual nt. The second inequality holds because (Ns)ieN is subsequence of (n)nEN; hence sup sup over the larger sequence upper- bounds the lim inf over the subsequence. Overall, and as announced at the beginning the proof, (T.) we thus have shown that the functions Ll must be local for uniform Too.
(Im) (i, equals an inner product P K Qu.PPy all values are expressed at pre- Because each Pi.h cision bounded by (Ro)*, and are bounded in absolute value by s ||p:||a|| Qt,a ||pp||2 s (Ro)*. There are only a finite set of functions that satisfy these properties and are are local for this Too.
Above, we have remarked that each limit transformer 7 consists of (i) the collection P(7) of pa- (T) $1 (i. Hence, we know that, := = (
rameter matrices and vectors, (ii) the collection of functions
(21)
finite. Let 2x C Q be the set of Limit Transformers that equal T; for infinitely many different i. By definition of the Inference Procedure, every element of Qxo is functionally equivalent to f at all input lengths. Because Q is finite, there is No such that T E Qoo for each i 2 .No. Hence, 7; is functionally equivalent to f at all lengths as soon as i exceeds the threshold No.
We now prove the theorem.
Proof of the Theorem. Both directions are corollaries of Lemma 17
2=1: This directly follows from Lemma 17
1= By Lemma 47 for each i 1,2,3, there are T, E O such that R:= sup, R((;)
< co
such that
|2] +os
(22)
such that
p. KT, Qu.pP = (1.1)
(23)
By LOCAL,
R(T.) <
(24)
and we conclude
lim sup R(T,) < lim sup R()) <0 i
(25)
i-+20
where T; refers to the sequence generated by Inference Procedure in Lemma 17 Lemma 17 now
provides No > 0 and a function g such that for all m > No.
Tm o) g(x), Va: |x| + S m
(26)
On the other hand, for any string E 6, we have
f(x) (a, 0), Vn 2 2|2|
(27)
Hence, f g and for all m > No.
[z = f(x), Vr + m
(28)
22

---

Published as a conference paper at ICLR 2025
B.2 RESULT FOR NoPE TRANSFORMERS
Corollary 18. For ease of the reader, we mark the differences to Theorem 7 in blue font.
Let F(E). Then the following are equivalent:
1. f is expressible by Limit Transformer where all 0, Φ1 = =.
2. (Guaranteed Length Generalization) Consider the inference procedure from Definition 6 applied to f with while constraining all p; = 0, generating a sequence Ti, T2,.... For any such sequence, there is some No such that, for all > No, Im matches f on all inputs of any length $ m, and 11 R(Tw) < oc.
Note that a Limit Transformer where all 0i is also an ordinary transformer as defined in Sec- tion 2. Hence, in the special case of NoPE transformers, our proof boils down to an argument using standard transformers, effectively without Limit Transformers. In contrast, Limit Transformers are key to our proof in the more general case of APE transformers.
Proof. Retracing the proof of Lemma 47 shows that, when translating a Limit Transformer to an ordinary transformer, the positional encodings can be taken to be when p: = 0, Φı, in the Limit Transformer. Retracing the proof of Lemma shows that, when p: = 0 in transformer, the resulting Limit Transformer will have zero positional encodings and zero outputs for all 01,6. The proof of Theorem then applies equally to show Corollary 18
B.3 LOGARITHMIC COMMUNICATION COMPLEXITY FOR LIMIT TRANSFORMER
Theorem (Restated from Theorem 12p. Let T be a Limit Transformer satisfying PERIODIC and LOCAL. On input E y2N, assume Alice has access T1...N and Bob has access to NN.... There is a communication protocol which Alice and Bob exchange at most log N bits, where C depends on T but not N or and Bob can compute each activation in the second half, y (1) (N + 1 S i 2N). Further, is bounded linearly by Roc (T))
Proof. We first establish that all activations y; computed Ollo N) precision. This holds because (i) parameters are at fixed precision, (ii) the output of cxp(-) in the softmax attention compu- tation is computed at fixed fractional precision, (iii) and hence attention weights be represented at (log N) precision.
We first consider the attention logits, in the where j < S
(1.b) Round,((y] "-)"" KÊ Qu. (1-1) + (r,
where Roundpl... rounds each entry to the closest number with fractional bits. It is certainly sufficient have access
(1.b) d
(Round (b) (Round/1H)) ) K Qu.hy (-1)) + Round (t,
where p' depends on and the largest singular value of KTT,0, Qi,ks which is finite constant. We can thus partition the positions j ........ into a bounded number of sets, indexed by
1. Round 1-11
2. max(N J. L) where L max(k 61, 00.
Let K. E N be the number of these sets; we then write these sets as , Note that, while always disjoint, their elements are input-dependent they depend the activations
these 0 (1-1)
Due to the finite precision rounding of logits and the locality of positional relations, maintain a finite set of keys and queries (though not values). This is fundamental to getting a logarithmic communication bound.
23

---

Published as a conference paper at ICLR 2025
We show the claim by induction over the layers.
We can write
H Σ j=1 exp(log |r| ais )
(1.h) Vinn (1-1)
(1-1) Y, y
Ej=1 exp(log |.|| at.5)
The residual stream is known to Bob by inductive hypothesis. We need to understand the term inside the sum. The green terms are fully known Alice, the blue ones are fully known to Bob by inductive hypothesis:
Ej= exp(log |x|| aij
(1.b) Vi
Ej= exp(log |a|| ai.i)
Σ N-1 exp(log |2| a..)
(1.b) Vinyy 11-1)
exp(log |z|| at.s) + Σj=N exp(log |x| ans) j=1
N-1
Σj=N exp(log |x| ajs Vi,ny 11-1)
(1.h)
2j=1 exp(log æ ais) + Σj=N exp(log |x| at.))
N-1
Alice thus needs to communicate the green terms. More formally, for every set r I..... ..... K, Alice communicates
1. the number of relevant positions, |A,1 E [N....,NN -13 13
2. ΣiE,. Vin.y (-
For each r, communicating (1) takes Oloog N) bits. The vectors in (2) are bounded in norm by the 1-th power of the maximum spectral norm of any parameter matrix, times the maximum & norm of any parameter vector. Overall, this is bounded in terms of R (T), thus O(1) for fixed T. Further, each yj (1-1) is expressed in Olog N) precision as shown above. Expressing (2) requires Ollog N) fractional bits (as the sum will not need more fractional bits than the individual vectors) and O(log N) integer bits (due to the bound on the norm). Overall, Alice needs to communicate K. Olog N) bits. As I. is independent of N, this is Ollog N) for fixed Limit Transformer T.
Alice can partition the positions into a bounded number of partitions, and for each of them needs to transfer the number of positions in that partition.
The following problems are not expressible by Limit Transformers satisfying PERiODIC and LoCAL: (I) copying strings with repeated n-grams, (2) addition of n-digit numbers.
Corollary 20 (Restated from Corollary 13
Proof. Formally, we define copying as the task of, given prefix Sa autoregressively predicting Copying with repeated n-grams means that there is no restriction on the repetition of consecutive subspans x of any length; this is in contrast to copying tasks with restrictions on the repetition of n-grams (for some n) in (Jelassi et al. 2024: Zhou et al. 2024a), which study separately (Appendix E.2)
Formally, define addition as the task of, given prefix Sa y =, where x, y are binary strings, to output the sum of the numbers denoted by x, y in binary.
The communication complexity lower bound for copying follows from standard communication complexity lower bound for determining string equality. The bound follows for addition since the special case of adding to number amounts copying.
24

---

Published as a conference paper at ICLR 2025
Remark 21. Analogous bounds follow for various other algorithmic and formal language problem. For instance, the special case of multiplying with amounts to copying; hence, such a bound holds for multiplication. For the unbounded-dens depth Dyck over two bracket types, we can consider word of the form (i....6xx) (6x ii -x.......
....... Jjy, which is in the Dyck language if and only if = jis for all k, again allowing reduction to the communication complexity lower bound for determining string equality.
B.4 STATEMENT OF MAIN THEOREM FOR ARBITRARY TRAINING LENGTHS
Our main theorem considers generalization from length 7 to length n. Here, we discuss an alterna- tive version applying arbitrary scaling of training vs testing lengths. In partieular, in such setup, we explicitly obtain failure of length generalization for inexpressible functions, though potentially requiring testing on lengths more than twice the lengths used in training. We use the following definition:
Definition 22. A training length is a function t N + N sattisfying lim, t(n) +oo and ((n) S for all n.
If (f)( is training length, then the (in)-enfeeecee Procedure determines T, (())) match f at all inputs of lengths S t(n)) while minimizing R(T,) up to n'
The special case of t(n) nt is the Inference Procedure from Definition 6
We then state: Theorem 23. Let f E F(E). The following are equivalent:
1. f is expressible by Limit Transformer satisfying PERIODIC and LOCAL.
2. Let t(n) be any training length. Then the Iiff--nfeeence Procedure will output solutions Tí, Ti.T..... such that, for some No. for all m > No. Tom matches all lengths S m.
Intuitively, this says that, when selected to fit the behavior of f on sufficiently long inputs of length tn)). the output of the Inference Procedure will generalize to unboundedly longer inputs of length n. where n can be arbitrarily larger than t(n).
Corollary 24. Assume E F(E) is not expressible by a Limit Transformer satisfying PERIODIC and LOCAL. Then, for some training length t(n), the t(n))-Iferene Procedure outputs a sequence Tn where infinitely many Tr, fail to match I at length n.
Remark 25. There are two important differences compared to Theorem 7 First, the second condi- tion refers to length generalization for all arbitrary training lengths t(n). not specifically training length? 5. Second, the second condition does not ask for sup; R(T.) < oc, but simply asks for Tr to ultimately length generalize.
Proof of Theorem 23
1=2 The proof of Theorem 7 remains valid in this direction without any changes, it does not specifically rely on the training lengths being half the overall context size.
2 1 We show the contrapositive. Assume f is not expressible by a Limit Transformer satisfying PERIODIC and LOCAL. Then, using the same arguments as in the proof of Lemma 17 any sequence T, E θ, that matches f will have lim inf R(T,) oc (t). Now consider t E N; we will O. For each n > h. there is Pr.m E O, that
assign every l a number ne > k, starting with matches I up length k while U3 = sup,, R(Tr..)) < oo for every fixed k. Now select mıg 74k-1 such that no T E On, with R(T)) < UR + 1 matches f at length ny; this is possible because of (t). We thus obtain sequence (k, nk)) E N N. By construction, there are infinitely many distinct
different values nıg. Then define
((n) == max ((k n& S zn))
(29)
Then t(n) is a training length. By definition, the t ((m) Inferenne Procedure will, whenever n is one of the n& ss find a transformer Ta, with R(TT.) UR + 1 that fails to match f length n nik- O
mh
"Assume there is sequence T., O., that matches and has lim in RT,,) co. Translating each element to a Limit Transformer leads to sequence where, except perhaps for the functions ΦL., only a finite number of settings will be traversed. Now, as in the proof of Lemma 17 one can use (T) to construct a sequence of Limit Transformers that are local for single 7. The important difference to Lemma 17 is that here we are not assuming the sequence (T,), to be constructed by the inference procedure, hut nonetheless obtain such sequence.
25

---

Published as a conference paper at ICLR 2025
B.5 COROLLARY ABOUT EXPRESSIVITY
We have introduced Limit Transformers as formalism for distilling computations of transformers performing on longer and longer sequences into a single limiting object, helping understand length generalization. Here, we show that they also provide a simple lower bound for the expressiveness of causal transformers across input lengths:
Corollary 26. Let f E F(E). Assume J is expressible by Limit Transformer satisfying PERIODIC and LOCAL. Then at each input length N, there exists a transformer Tn performing f on all inputs of length up to N such that:
1. The parameters TN are expressed at p bit precision, with independent of N
2. The number of heads and layers of N y is bounded independently of N.
3. The width d of TN is bounded as O(N).
We note that an important aspect is that TN performs correctly not just at length N, but at all lengths up to N. This distinguishes the result from constructions guaranteeing the existence of a transformer at a fixed length. For instance. Bhattamishra et al. (2024) provide a transformer for testing equality between length N-strings (which could also be used for copying), but this construction uses specific positional encodings that depend on the input length. In contrast, the result here provides conditions under which transformer can perform a task at all lengths up given bound; in this stronger setup, no APE transformer for copying with uniform complexity bounds as provided by Corollary [26 known, and the problem is indeed not expressible by Limit Transformers satisfying PERIODIC and LOCAL (Corollary 13 In contrast, Corollary 26 provides APE constructions performing correctly up to any given length for a wide class of problems including G.RASPPperiodicc.oclll
Another important feature is that the construction provides fixed precision for the parameters, as the case in real-world implementation. We note that, if parameters are at fixed precision, it is generally not possible to find a single transformer across all input lengths in the APE setting: hence, is unavoidable that the width of the transformers will need to increase as the input length increases. Importantly, many other aspects of the transformer's complexity, such as the number of heads and layers, remain bounded.
Proof. The statement is an immediate corollary of Lemma 47 which provides transformers T1, ..... with bounded R(Tx), which by Definition entails a uniform bound on precision, heads, and layers. The construction provided in the proof of Lemma 47 provides width bounded as O(N).
B.6 FROM C-RASP TO LIMIT TRANSFORMERS
The proofs are adaptations of the proofs from Yang Chiang 2024).
Theorem 27 (Restated from Theorem 9p. For every C-RASP & v program P with local functions I and any periodic functions & there exists a Limil Transformer Toe that satisfies PERIODIC and LOCAL such that for all E Σ", P accepts w iff Toe accepts Sw. If uses no local or periodic relations, then T requires no functions 01 or positional encodings p.-
Remark 28. We note that the Limit Transformer' Tox provided by the proof of Theorem 27 emulates the C-RASP program P at zero offset: That is, P accepts iff a predeternined entry in the last output dimension of To ($w, 0) is above some threshold. In principle, its computations may not be offset-invariant, i.e., for the constructed T Too, the output Tox (Sw, 0) may depend o. Importantly, the proof of Theorem does not require a Limit Transformer computing I to be offset-invariane but just requires it to compute I when the offset zero. This is because Lemma 47 ensures that, for any Limit Transformer Toe satisfying LOCAL and PERIODIC, even if it is not offset-invariant, there are transformers T,, Or whose behavior matches (:.(-.))
C-RASP has two sorts of operations, a Boolean sort and a Count sort. We will simulate each operation in the transformer by storing the Boolean values as {0, 1). and storing the counts as 1 That is, say that Limit Transformer To. simulates C-RASP program P if for every operation Ps of P there is dimension de in T such that when (e) when run to is true iff
Proof of Theorem 27
26

---

Published as a conference paper at ICLR 2025
Too ($w):+1,4 (and otherwise) for Boolean operation and (t) iff &o (Sw) :F1 for count operations.
The theorem will be shown by induction on the length of As a clarifying note, we use O-indexing everywhere in this proof. If P is of length O, we only have initial Qo (i) vectors, which can be simulated by appropriately setting the word embedding. Otherwise, assume all programs of length < k are simulated by some transformer, and we have cases for each type of operation Pe+1(i) can be. All cases are identical to Yang & Chiang (0024 except for comparison, conditional, and counting.
First, we must address the SOS token S. There exists an transformer layer which sets the entire vector 0 in the initial position, while leaving all other layers untouched. For instance, may a conditional operation, as described later in the proof.
If Pk+1(0) (8) <(1), periodic positional function in o, then it is simulated in Too by appropriately setting p; in the positional encoding.
If Pk+1 (i) P(t) ? (1) C2(1), can implement the following function: for P E {0, 1) and
V E [0,1
P = 0 0
V
S(P.V)
P=
This is achieved by f(P.V) ReLUVV-P)) Thus, the desired Conditional Output can be defined PP,VV)), V2), where the first layer and ReLU compute each f term and
single FFN as ((. + f(-P, the second layer adds them together.
(1). By the inductive hypothesis C (i) and C2 are stored in dimensions dj and d2 as the value (1)
(1) == C
++1 and Cz(f) It suffices to check that C2(i) Ci(()
i+1 6+1 2 0.
i+1
To compute this, we use the heaviside activation function, which we used in our model of MLPs as discussed in D.I.
0
X
Thus, there exists MLP which, letting .1 and 22 be the values in dimensions d, and d2, computes (hs(r2 x1) 1)/2 in the dimension reserved for Pat1, which will be the Boolean value in {0, 1} corresponding to C1 (i) Ci)..
If C(i) # < i] P(j) (using (ii,)) = T), then the desired sum is computed using uniform attention, since the boolean representation of P(j) is just 0 or 1. We enforced that P(O) is false, so it does not contribute to the sum. This is described in more detail in Yang & Chiang (2024), though the case here is simpler.
If C(i) = # Lj < i, (i.j)) P(j), we can think of it as implementing # [j S (i.,) A P(). Suppose z is a local function of the following form
(i. = {
j=i-L
else
Then C(1) will either be 1 or 0 depending P(i E) is true or false. If we set the query and key matrices to O we get
8ij = log N (i.
27

---

Published as a conference paper at ICLR 2025
We assume the log is base 2, but the argument is similar for others. Then can have attention compute
Σ exp (log N (bi,j)) P())
Σ NO (
P(i)
jSi
55$
Ci,k
exp (log N- vi.)))
Σ JS
N
in
If P(i - and -P(j) for j + e, then we have lower bound:
N m
S Ci.
N पक
+i-1
If-P(i - E) and P()) for j # then we have an upper bound:
4 S
N
mmz
+ 1
Since N N 2 i, and we know that P(i- - Ci.b 2 2. can construct an th.t computes the correct value. It will output either 0 1 in the dimension reserved for (1) for instance
by using a conditional operation that checks that the output the attention layer c 2 1.2 which was shown in an earlier case.
C EXPRESSIVITY PROOFS FOR C-RASP
C.I C-RASP CONSTRUCTIONS
C.1.1 MAJORITY
MAJORITY is the language of strings over E = [0, with at least as many I's as 0's.
MAJORITY
Ci(1) # < 1 ()
(I)
Co(1) # | Q0(1)
(2)
M(1) (1))) Co(1)
C.1.2 DYCK-1
Dyck-1 is the language strings over {0,1) with least as many 1's as O's.
Dyck-1
C((1) # [ < (())
The number of ( (up to position (1)
C,(1) [j < 0,))
The number of up to position
(2)
V() = (())
Violation: there are more than
(3)
Cv(1) = =
The number Violations
(4)
M(1) == Cv()==0
Matched: zero Violations
(5)
B(1) C((1)= C)(
Balanced: same number of ( and (6)
D(1) M(3) A B(I)
String is Matched and Balanced
(7)
28

---

Published as a conference paper at ICLR 2025
C.1.3 c"
Let Σ = ba. This is another example of a counter language which C-RASP can express and which transformers have been observed to length generalize on (Bhattamishra al. 2020).
C.(1) = # 5 Q-())
(1)
C(1) = # ( Q+(1)
(2)
Cc(i) :- # $ Q+()
(3)
A(1) Cc())+
(4)
B(1) = =0
Cx(1) := [ ( Qa()) A(I) AG)
Cb(1) : $1 (6(1) BG)
(1) = Ca(t) = CC.()
(1(1) = Cs(() = -C)())
(9)
G1 Cz(2) C.(() Ca(1)
(10)
[(1) (t( Gb(t) (1)
(11)
C.1.4 EXISTENTIAL. QUANTIFICATION
This is generally useful primitive, so to save little space can add macro for existential quantification towards the left in C-RASP. This is easily defined using counting:
P(i) AA()
C(i) = # i A()) P()) C()) 2
(I)
And we abbreviate this using P(i) == ' A(i.. We demonstrate its use below.
C.1.5 PIECEWISE TESTABLE LANGUAGES
Piecewise testable languages are Boolean combinations of languages of the form E' Eta'E"aa "."""..."a... 2* This allows to check for the presence of noncontiguous sub- strings, which contrasts with the proof in C.3.2 that implies the presence of contiguous substrings cannot be expressed in C-RASP(0).
suffices to show programs for languages of the form L = Σ' ... E',, since Boolean combinations recognizable using Boolean operations of C-RASP. For L we have the following C-RASP program which has the final accepting operation I.n:
L' D',
(1 5Q. (i)
a1 occurred
I2(1= = (Qa A (i)
occurred, preceded by aj
(2)
(3)
L.. 5Qa. (1) Ln-1(1)
an occurred, preceded by an-1...., preceded by a, (4)
29

---

Published as a conference paper at ICLR 2025
C.2 LOLASPI CONSTRUCTIONS
C.2.1 INDUCTION HEAD (ARGMAX VERSION)
As an example consider Σ {a. b, c}. Predicate NEXT. is true iff the next token should be an First we can define predecessor
CPa(t) = ((j= Qx(i) PRED. = CP.()) 21
Then we can count bigram occurence by counting
C.b # i Qa(i) A PRED.())
Then each NEXT, (i) predicate can be defined by checking the current symbol and finding the most frequently occuring bigram.
NEXT, (Argmax) over E = {a, b,
MORF ab (1) Cca (1) (i)
MORE (1) = Coa 2 (i)
(EX = Qi( A MO MOREan.uo())
(4)
This corresponds to testing, for the in Equation 10, for which the entry f(11 ... NN. is maximal.
C.2.2 INDUCTION HEAD (ALL POSSIBLE NEXT SYMBOLS)
Consider Σ. For E Σ, predicate NEXT, true iff the next token can possibly an a. As in Section C.2.1
first, we can define predecessor
CPa(t) = #bi Q.(i) PRED.()) = CP.()) 21
Then we can check for bigram occurence by counting
CBIGRAM # S Qo(i) PRED.U) EXISTS == (BIGRAM 21
If a bigram occured previously in the string, nonzero probability is assigned to predicting when at symbol a. Then each N EET,,
(EXT(() (i) predicate can be defined as follows
NEXT, (i) (All Possible) over D {a. b, c}
NEXT. = V aED
(2)
where V V can be expressed using the Boolean operations and as defined in Section 4.2 corresponds to testing, for the in Equation 10 for which have f( ... N.a
This
0.
30

---

Published as a conference paper at ICLR 2025
Generating based on this program Consider input prefix of the form #2#, where # denotes a separator symbol. If we iteratively generate the next symbol a by selecting a E Σ where N NEXT, holds at the last position, we generate string #ø#y y where all bigrams in #y had already occurred in #o, a simple version of the in-context Markov chains studied by (Edelman et al. 2024
Unique Copying In the special case of input prefix where each symbol occurs at most once in the generation procedure defined above will copy z, and (assume we stop at #) resulting in overall string of the form #r#2# This essentially the RASP-L construction of unique copying noted by Zhou et al. (2024a).
Special Case:
Necessity of Positional Relations Intuitively, an induction head circuit requires positional in- formation; indeed, we observe length generalization in unique copying with APE but not with NoPE (Figure [T.. Formally, we can prove as follows that the predicate N EET,, defined above for each
Σ, while definable in C-RASP [ocal)/ is not definable in C-RASP(0). Consider = {a, b): then the predicate N EXT, can be used to define the (disjoint) union the languages L'ab""" 66b
6. As the first one is definable in C-RASP (0 and the union is disjoint, the sec- ond would be definable if NEXT, is. This contradicts the fact that E bbE" & C-RASP(j), because
E "6= & 2AJ2 <<]
(Lemmaa 6.11 11 in Krebs (2008) and the inclusion C-RASP [)] C MAA2[<] [<]
(see Section C.3.1
C.2.3 (aa)*
The following function that checks parity of a position mod 2 a periodic function.
<(i) = i 0 mod
So the following program recognizes (aa)*
(aa)*
C-a(i) = $ < -Qa()) A(1) (f) =0
D(1) (11) A(i)
The Boolean value of the last operation in the last position of the string is the accepting value. This is true if the string is of even length and contains only a's. Overall, we have constructed a program C-RASP periodic, local).
C.3 EXPRESSIBILITY OF REGULAR LANGUAGES IN C-RASP[PERIODCCLLOCAA]
Lemma 29 (Restated from Lemma 11 Consider the alphabet Σ ba
1. PARITY := aab" & C-RASPiperiodic,.e locall
2. (aa)* C-RASPiperiodic, local] and (aa)* & C-RASP(0)
3. (alble)*be" be & C-RASPIperiodic, local]
4. L C-RASP(0) for piecewise testable L
Proof. 1-3 are shown in Lemmas 36 (for 3.), 38 (for 2T) (for 1.), and Appendix C.2.3 (for 2.). 4.
is shown in Appendix C.I.5
It is sufficient to check whether and b both present, and whether one b has in its preceding context;
Σ {a, 6), this is equivalent ab being substring
31

---

Published as a conference paper at ICLR 2025
C.3.1 LINK TO MAJORITY LOGIC
In understanding the exressiveness of C-RASP, we draw on an established body of work log- ies using MAJORITY quantifiers. Merrill & Sabharwal (2023a); [ttobl (2023) show that the ex- pressiveness of transformers is upper-bounded by uniform TC", which can be defined as the logic FOM[BIT] This logic is defined in terms of MAJORITY quantifiers and various predicates. C- RASPiperiodic. local] can be viewed as a highly restricted fragment of this logic. Specifically, it is contained in M A +1, MOD), which results about that logic help understand the expressiveness of C-RASP:
studied by Krebs (2008); Behle al. 2007
2009);
Definition 30. M MAJ2[<, + MOD) is the logic defined by the constructs
1. The construct
Maj (01,-...
2. The predicates Qa(z) E
3. Numerical predicates Succly, and Modm, (2) for m, E N:
4. Boolean connectives
5. First-order quantifier
such that only two variables (say, x and y) can appear within a formula. We define the semantics, when E E" by defining
1. for the majority quantifier:
if if - 03
ト= Maj (01,..., +0 <
else
1=1
2. for the predicates:
z= F Qa(z)
W
w z= - Modm, (x)
+ = r (mod m)
:= F Succ(y,
i+l=i
Semantics of Boolean connectives and first-rrder quantifiers follow the standard definition.
A language C _ E"" definable in MAJ2[<,+1, +1, ifthere a formula & without free variables such that w E if and only if } Φ.
The logic M M results by omitting the numerical predicates defined under (3).
straightforward to convert C-RASP programs into formulas of MI, MOD]. As we shall see later in Section C.3.3 the inclusion is strict because PARITY is expressible even in M MAJ2[<].
Proposition 31. C-RASP local] C +1,
We make remarks about corollaries of the result:
Remark 32. First, the proof. simply by omitting the positional relations, also yields a corresponding inclusion without positional relations: C-RASP(0) C M 2]
Second. the result implies that C-RASP pperiodic local) defines subclass of TC in fact, all C-RASPIperiodic, local programs translate into uniform TC circuits with linear number of gates by results in Krebs 22088 Theorem 4.33 and Figure 4.4). The inclusion is strict, e.g., PARITY has size TC" circuit but is not definable by C-RASPiperiodic, local), as we show below.
"These be simulated by majority quantifiers with two variables by Proposition 5.5 in Krebs 2008 which is based on Corollary 3.3 in Lange (2004). Nonetheless, simulation is unobvious, they are useful for writing formulas in M AJ2 [ +1, MOD).
32

---

Published as a conference paper at ICLR 2025
Proof of Proposition 37 First, every periodic positional function Φ(i) is Boolean function M oodmr (i) >
= r mod m. For local functions ((..j). suffices to only consider func-
tions of the form (i.j) = j i for Z. This is because the counting operation
C(i) = # S i,
S [c] P(j) is equivalent C(i) where
1)V = # j cV -
P()
And it is possible to further reduce this by distributing the disjunctions over many counting op- erations that each only contains single disjunct positional function. It helps that a predicate fst(i) is definable in +1, which true iff 0. For instance fst(i) == -aaj j si
For each Boolean C-RASP operation P()). there exists a MA MOD] formula P(i) with one free variable that is equivalent to P(i) at all positions of all words. By induction, all cases straightforward except for comparisons of counts.
-1,
For comparison operations, will first show formula that is equivalent for all nonempty strings. Accounting for the empty string is easy, depending on the constants in the comparison. WLOG we able to rewrite the formula (not in standard C-RASP notation) as the following, where ag. 3 Z
< MSM
Σ au (# P&(i)) KSK
+
Σ
am (#
M SJSi, i.j = Cml Pm((i)) +
We've ve grouped the uniform counting operations that have & = together. Then using case dis- junction, rewrite it all the local counting operations the following (using I[ø] notational convenience to turn Φ())= E {L, T} to the corresponding value in {0, 1}):
V
Σ Eai- (Hb PAO)) RSK
+
Σ MSM
am
+ +8>0
= IP em))=m
We can see that for nonempty strings within each case, the additive constant / can be reformulated
B + Emsas am [ fis(j)), and can just add it to the summation using ax+1
(8+ (++Emsn Emsm Om Tm Then, it is possible define formulas for each case disjunction using series of existential quantifiers and sucelj, i). For instance:
*(j 2) 3i. (Succ(i, A 3j. (Suce(j, A +()))
Thus, we are able to rewrite the entire formula where we only ever compute sums of C-RASP counts without any positional functions. This means it now suffices to focus on the summations of counting terms
Σ a (# < P())
and simulate these that using a Maj formula. For < (K + 1), if as > O consider the list of formulas
L = (P.0). (AO))
PAO). ... Pa() T.,,...,
Ogg many
many
33

---

Published as a conference paper at ICLR 2025
Intuitively, the Maj j quantifier can only check if the total count is greater than half the possible positions, so to check a count is > we need to pad the quantifier with a bunch of trivially true formulas to ensure the total count least half by default. And if ag we use
L = (PP((), -PA(), Pk(()) L.
Org many
CC many
Let = + + be the concatenation of all these lists, and let (01 92: ........ PIL list out the formulas in L. Then we claim the following formula will compute the correct value of the comparison for nonempty strings.
Φ1 Maj j(pl P2. ................................ (P())
For empty strings, if (8 [ Emsm Om mm then define co == -Maj (T) AT. Otherwise,
use do(i) == -Maj j (T) A Then we can define
P()) = :- vzl
C.3.2
INEXPRESSIBILIIY OF E*
Krebs 2008); Behle et al.
2007
2009) used infinite groups to establish results about the expres-
siveness of M 2 by Corollary these results entail results on C-RASP p-RiAS/perioddi,, local]. In particular, Lemma 6.11 in Krebs (2008) shows that Lis &f MAJ2[<]: this result turns out to have profound consequences for C-RASP expressiveness.
Definition 33. Les E = {a, b, e}. Define Lis == b"
As minor note, the exact statement of Lemma 6.11 used Lis >' 66E", but the addition of the neutral letter is inconsequential.
Lemma 34. Let be M1 formullaa and a M M ub such that for every w E ,", h(w) F - w wF
formula. There exists morphism h(o) 00
Proof. Let M be the least common multiple of all occurring moduli in yo. Let be the maximum nesting depth of Suco(r, y) predicates (which must be bounded by the quantifier depth of yp) In- tuitively, we can think of C' as the largest number where a subformula sp(r + C*) occurs şp. Let .MC, and define the morphism (((r) e -- for E Σ. Here we will use the notation (x) which will be true at position & in w whenever ó is true at position x + c in h(w), for c E --s,6 1].
We will show that for every formula p(x) of M MA22|<, +1, MOD] with at most one free variable,
we can define * (p (x-1)) (() such that for all i E [0, |w| - 1] and e E [-8,
h(w) F giti c) - (1)
Intuitively, what this does is it takes every interval of [x s, + (s 1)] around each position in h(w) and stores a "vector" at that position in w. We will induct on the complexity of ş. If (px)) is (x)), then (
(z), and then (x) = T for every other + 0, since the morphism h pads neutral symbols e in h(w) between every symbol from w. If (()) is (x(x)) for a + e, we have that 6 (x) and y (x*) 1 for every other e * O. If (p())) is M Mod (z), the yp" can also be "hardcoded" similarly, as every position in h(w)) that has a symbol from w is going to be = mod
Boolean formulas are also straightforward. The only hard case if we have a formula spxx) =
M AJ y (p v)... (x( v)). We can think of &p specifying the constraint
34

---

Published as a conference paper at ICLR 2025
k- wl
Σ # y (z, w)1 isc
Where # e indicates the number of positions in the string satisfying ő (with variables bound appropriately). The idea here to rewrite 1/( y) in terms of its unary formulas (which we can apply the inductive hypothesis to) and then split l(w) into some intervals, upon which evaluating (p=te()) will be simpler. First we can rewrite each (x, y) as
(,()))))...,,(()))))))))))) ... Br(()) x1(2, ")..)..,.((.... v)
Where F; is Boolean function, the unary in æ, the B are unary in y, and the x(r, are in- equalities of x and y, possibly with +1's, of the form x S + 1, for example. To save space, will abbreviate the above expression by grouping the a, B, X formulas together notationally F. (2, v), (x),,,
The formulas are not unary, but we can "eliminate" the X terms by casework over intervals of the string. We will show this by example for summation with only one # y term. This argument works identically if we had many of # y terms, but would add notational clutter. So if we had formula ((x) = MAJ y (11(2.)) v)) we could think of it in the form
x(x)= = (y)== (())) 2 [w|
Then we can construct the formula (x) for e E [-s, 1] by using the following partition of intervals of the string. Let be the set of inequalities
= {y < x s,y = x s....,y x,
2..... ... = x 1), x (s-1))
And we define some notation. For & E E, let ((r E [T evaluate x in the case & holds. For instance if (xx, y) is y < x + 1, then x>> y) I. Since the intervals defined by & E disjoint and cover the entirety of the string, every X can be evaluated in this manner. Then, we can essentially compute the sum in each interval, and only precision is needed in the interval [xr 8, x + (s 1))} (xx)) is equivalent to
35

---

Published as a conference paper at ICLR 2025
# y < a D CA (2.) (v))
*# <
+# 1 8 X (a.) [w)
+# V
+# y
+# y x
## x y F(x
[v)
+#
##
+# 1
+# v x (CA (+)
## y < (2.
w
2
By the inductive hypothesis, all a and S are definable solely in terms of MAJ2[< so the entire formula is equivalent MAJ y formula that quantifies over all the bracketed formulas above, as well as equally many trivially true formulas, as described more clearly in Proposition C.3. As mentioned before, since this argument also applies to a summation of # terms, this completes the proof. Then for any (p() in MAJ2[<, +1, MOD), after performing the above translation the resulting formula (x)x) is our desired formula in M MA22[<].
Lemma 35. Los & M1
Proof. Assume for sake of contradiction that Lus definable by a formula ip of M MAJ2 +1, MOD] Let h and sa be guaranteed by the above lemma. Then for E Σ" E Lus h(w) E Los This means tb defines Lis which contradicts Lemma 6.11 in Krebs (2008), which has shown that Lis & MAJz[<].
Lemma 36. For Σ ba e}, holds that
be & C-RASPlperiodic, local]
(4)
Proof. To get a contradiction, note that periodic, local] program & for be" could be used construct one for Lab, as:
36

---

Published as a conference paper at ICLR 2025
G(1) =
2())
PREV(() C10)21
C2(1) = # Q.6) A PREV())
Lu = C2(1)
C.3.3 INEXPRESSIBILIIY OF PARITY
First, let the depth of a C-RASP operation be the maximum depth of nesting of counting operations in it. For instance if ((i) = # [ P(j), the depth of the C' is depth of P(t) plus one. None of
the other operations are greater than the depth of its dependencies. We will induct on program depth for the following proof:
Lemma 37. Let Σ {a}. For any C-RASP program P there exists an such that for all
where w 2 n, either all such w are accepted by P or all are rejected
Proof. If depth 0, it is equivalent either Qa(t) or -Qa(1), which either rejects every string or accepts every string.
Otherwise, let all C-RASP programs of depth & give constant output for strings above length n, and then consider program P of depth & + 1. P will be equivalent to Boolean combination of linear constraints. We will see that each linear constraint becomes constant for strings above certain length. Consider any linear constraints over X many counts C₂ of depth k:
L(1)
a Cattiis S Cz(i) ( 20
For string of length i 2 n. this is equivalent to
L(1)= = Σ
ou ((i 1 ([- #
# f n] c.601) 20
xSX
Where [n)] denotes the truth value of (z(n) E {0, 1). Rearrange this to
L(1) = (i-n) Σ as (I(C(()))) + [aa (# < n| C2()) 2c xEX
aSx
The sums C1 = E ag (n)C) and C2 = Easx ag (# < n] C₂ are constants depend- ing on the formula and n.
(i n)a + 02 2
Depending on if C1, C2 are positive or negative, we either derive a lower bound m after which the linear constraint L(i) is always true, or always false for 2 Since any formula of depth & + a Boolean combination of these linear constraint, we take the max all the m's from them, and any string larger than this will always be accepted or always rejected by P.
Lemma 38. (aa)" & C-RASP(0)
That is, no C-RASP program can determine if a general string has even length. The same proof applies testing whether the string length is multiple of any other fixed integer.
37

---

Published as a conference paper at ICLR 2025
Proof. Using the previous lemma, for every C-RASP(0] program there exists such that the program accepts (aa)" iff accepts (aa)"a. a. So no program can recognize (aa)*.
We will use this to show that C-RASP/periooee local] program cannot recognize PARITY, as the extra positional operations do not give sufficient expressive power. We start with an observation that simplifies the proof
Proposition 39, As syntactic sugar we allow j < i as mask in C-RASP counting operations.
Proof. Consider the counting operation C(i) == [ P(j). We can define the program
[(i) := P(i) ?1:0 C(i) # [j 1 P(j)
C² C(1) - 1(1)
And essentially, this operation will compute the count
C² -( P())
Lemma 40. Let P be a C-RASPiperiodee local] program over E {a, b). There is and a morphism h(a) by ab" and a C-RASP(0) program P over {a} such that for all w E a", if P accepts h(w) iff P accepts w.
Proof. Choose to be the least multiple of all moduli occurring in P that is also greater than all the |c] in local functions itcc. For every operation P(i) of P, we will define Po(() for 1-8,8-1] such that po(i) when run on w is equivalent ((s i(2s) + c) when run on h(w).
P(i) is (i) or Qi),), it is straightforward, as (i) is true iff c also capable of being "hardcoded", positions in are always 0 mod in h(w), and so the offset e determines the value modulo. All other kinds of operations are also straightforward using the inductive hypothesis. The only ones that need care counting operations. First, consider counting operation without positional functions:
Modular predicates
C(1) = # S A()
We can define each (i) using a program like the following. The idea is that the entire window of [j - =,j + (s 1)] around each j < i can be counted up completely, but around i we only consider interval [-8, + cj:
( A :0)==)33
C ((- < (-
(1-1) $5< (0-
(.(1) = A-"
I((1) = A())
(0()== == Σ C.11+ + Σ 461
[8|-8,811 :E(-A.c]
38

---

Published as a conference paper at ICLR 2025
Otherwise, if we have counting operation that involves local positional function
= : (
A(j)
Then the operation returns either the count 1 or 0 and we can just use
= (c (c= dA A 21:0
Since will not exceed t.s, Ad exists. Using these constructions we can see that is accepted by operation P(t) in P iff a" is accepted by the constructed operation p(a- (t).
Lemma 41. PARITY & C-RASP ppriodic, local]
Proof: If such a program existed, it would be able to distinguish between (babb=1)) and (b"ab=-1jant1 for all n (using the s guaranteed by the previous lemma). However, this implies the existence of C-RASP [8] program over Σ {a} that recognizes (aa)". This contradicts Lemma
D DISCUSSION OF DESIGN CHOICES
D.1 MLP ACTIVATION FUNCTIONS
Our analysis allows ReLU and the Heaviside function as activation functions in MLPs. ReLU is standard choice theoretical studies neural networks and transformers (e.g. Bhattamishra et al,
2024 Sanford al. 2023). Modern LLMs also other functions such as SwiGLU (Shazeer 2020 but universal approximation theorems guarantee that ReLU networks can approximate smooth functions bounded domains well. While the choice of ReLU not necessarily key to our results, is important that the number of active units provides a meaningful upper bound on the complexity of the function expressed. Our results would continue go through if an arbitrary activation function but operates at p-bit precision.
We also allow the Heaviside function as second activation function. Heaviside allows exactly performing threshold computations at arbitrary input lengths, which is relevant to simulating C- RASP arbitrary input lengths. This includes simple problems such as MAJORITY, on which transformers empirically do well. Real-world transformers generally do not include this function, though ReLU MLPs can approximate arbitrarily closely.
D.2 FIXED PRECISION
As described in Section 2 we assume that attention logits and the exponentials inside softmax are rounded to p fractional bits of precision before further processing. This allows to cluster keys and queries into finite numbers of clusters, and compute all activations at logarithmic precision, used for proving the logarithmic communication complexity bound (Theorem [2}. We note that logarithmic precision of the intermediate activations also key upper bounds of transformers in terms TC shown by Merrill & Sabharwal (2023)).
We also assume that the parameters in transformers and Limit Transformers are expressed at fixed precision (Definitions 4 and 2). and penalize the precision p used of representing the parameters as part of the regularizer used in our inference procedure (Definition 5). Indeed, penalizing unbounded precision of parameter values is necessary to enable full identification of a transformer algorithm from behavior finite lengths. For any real number a 0, one-layer transformer with real-valued parameters can express the function
{1
a #1(x) 2 #o
Fa(x) = { clse
39

---

Published as a conference paper at ICLR 2025
Grammar
Star-Free
Dehmition
Yes
2
Yes
(10)*
3
No
strings without odd-length strings of ones followed by odd-
length strings zeros (i.c., 01 substrings)
4
Yes
strings without any 000's substrings
5
No
strings even length with an even number of 1's strings where number of 0's number of I's is divisible by 3 0 1+0**1
6
No
7
Yes
Table 1: Tomita Grammars (originally due to Tomita 1982). following Bhattamishra et al. 2020
For any two distinct a, B, the functions Fa and Fg distinct sufficiently long inputs (though, when a and 3 are close, very long inputs will be needed to distinguish them). Thus, there are un- countably many distinct functions implemented by transformers; however, their distinction relies on infinite precision. In an infinite precision setup, one cannot hope to identify algorithms imple- mented by transformers from finite data, no matter the input length and the regularization applied to the model size. In contrast, when parameters are representable in finite precision (as in real computers), the number of distinct algorithms expressed by Limit Transformers is countable, and ultimate identification from long inputs is possible when the precision required for representing the parameters penalized.
D.3 LAYER NORM
Real-world transformers use Layer Norm or RMSNorm, whereby activations y are rescaled to have norm or standard deviation vd. Layer norm can be incorporated into the translation to Limit Transformers (Lemma 52) by recording terms of the form
T
II SES
S
II SEE
T
(5)
when v E VOI, and u VOi, and S1 E We can record these products in further dimen-
sions of y, that || (1) [ is recoverable from y The simplest approach is then to modify the definition of Limit Transformers by normalizing y, based on this recovered norm.
The original translation from C-RASP to fixed-precision transformers (Yang & Chiang, 2024 capi- talized on layer norm; it would be no problem to translate from C-RASPiperiodic..oo to version of Limit Transformers incorporating layer norm, and would be able remove the Heaviside function from Limit Transformers.
E ADDITIONAL DETAILS FOR EXPERIMENTS
E. REGULAR LANGUAGES FROM THE BHATTAMISHRA ET AL 2020 BENCHMARK
E.1.1 LANGUAGE DEFINITIONS
Descriptions follow Bhattamishra et al. (2020).
Tomita Grammars. Definitions shown in Table
Dn are defined on the alphabet Σ {a, b) by the recursion D, = (a),-1b)*.
PARITY. PARITY is 5" (ab" ab*) " It contained in the set of algorithmic tasks.
Others. Other languages: (aa)*. (aaaa)" and (abab)" (not star-free), an cc dd ce", ((b)"d(b,c c)" and (0, 1, *02* (star-free).
40

---

Published as a conference paper at ICLR 2025
C-RASP expressiveness
#
Language
[0]
[periodic, local]
Star-Free? Dot-Depth AC yes yes ycs
1
Tomita
yes
yes yes no
yes
2
Tomita
yes
yes
3
Tomita 3
no
yes
4
Tomita
yes no
1
yes
5
Tomita 5
no n0
6
Tomita 6
no
no
no
7
Tomita 7
yes
yes
yes
1
yes
8
D2
yes
yes
yes
2
yes
9
Da
yes
yes
yes
3
yes
10
Da
yes
yes
yes
4
yes
11
D12
yes
yes
yes
12
yes
PARITY
no
no
no
no
12
(aa)*
no
yes
no
yes
13
(aoaa)*
no
yes
yes
14
(abab)*
no
yes
no
yes
15
aa"bb" ce" ddd ee*
yes yes
yes
yes 1
yes
16
{a. dbb [0.1.2)'02
yes
yes 1
yes
17
yes 2
yes
Table 2: The finite-state languages in the benchmark from Bhattamishra et al. (2020), with the num- bering from Figure C-RASP expressiveness properties, and three established notions of complex- ity (star-freeness, dot depth, and membership in the circuit complexity class AC In the C-RASP columns, "yes" means we found C-RASP program; "no" means we proved that no C-RASP pro- gram can exist. Note that {0, 1, 20"02 is equivalent the language be from Lemma 11 Note also that we discuss PARITY in the algorithmic benchmark, as it is included in (hoo et al. (2024a) See discussion in Appendix E. 1.1.2 labeled.
See Figure for a version of Figure (right) with languages
1.1.2 C-RASP EXPRESSIVENESS
All languages in the benchmark are in TC and all are expressible in principle by transformers (Liu et al. 2023). We were able provably settle the C-RASP expressiveness for all languages, with results shown in Table 2 We compare C-RASP expressiveness with the standard notions of complexity of finite-state languages considered by Bhattamishra et al. (2020): whether languages are star-free, and (among the star-free ones) their dot-depth. While many star-free languages in the sample show geggth-gnneaalzztionn nar-freeness does not overall account for the observed behavior (Figure 4 Within the star-free languages, a standard complexity metric is dot- (Figure 2): this again does not accurately predict length-genen seggth-enneralzation: it succeeds for a language with dot depth 12 but fails for language with dot depth 2. We also considered circuit complexity of regular languages
(Barrington al. 1992). All regular languages included in the sample are in the class TC most
are also in AC a smaller class sometimes compared to transformers (Hao et al. 2022 Barcelo et al. 2024 Transformers show poor length generalization on the non-AC" regular languages but also fail on various languages that are in AC On algorithmic problems, transformers succeed on some non-AC" problems such as Majority (Table 3). Overall, C-RASP expressiveness is much more successful than previously considered notions of complexity in accounting for empirical length generalization behavior of transformers.
Proof Sketches for Membership Claims We sketch proofs for all C-RASP expressiveness claims We first note that C-RASP (-RiSP(periodic, local] closed under the inverse images of mor- phisms where each symbol is mapped to a string of the same length. That is:
in Table 2
Lemma 42. C-RASP periodic, local is closed under the inverse images of morphisms where each symbol is mapped to a string of some fixed length n. That is, if h Σn - En (for some
1992 regular languages outside of AC are all, informally speaking, least hard PARITY, and indeed they provably not in C-RASP periodic, local).
By the results of Barrington al.
41

---

Published as a conference paper at ICLR 2025
fixed n) is extended to map Σj + Eg and L C-RASP local), then h (C)
C-RASPlperiodic, local].
Proof. Let h be such morphism. We take any C-RASPiperiodic, locall program operation P(i) that operates on h(w) into an equivalent program which operates on w. We use similar notation to Lemma 40 In this case for every operation P(i), we create an operation (i) that, evaluated on word w. evaluates P(i + c) on the word h(w).
For P(i) = (t),, we can use (1) == V Qa(1), (1()) =o Qr and so on.
For P(t) = (i)., then for e S n we can define (relying on the fact that m, r are fixed). This boils down to defining Modm,- + c) in terms of od terms which only reference i. This is simple, despite being lengthy to write out, because we can simply "hard-code" what needs to happen for all S m. The cases will repeat after that, since M Modm, (ni c) = Modm, (n(m i) c). so we can check mod m, and enumerate the cases from there.
For P(i) # i S i, (i. V(j), where (ii. T, then like before define (
( #jj <1 ( ()()) # < <1 (())
Cm- # $5<{ <i] (ー
(()) = (
7(1) = 710)1::0
(((1 ('())
Pc(1) Σ c(()+ Σ 1(()
1.n tE(0.c]
Otherwise, as described before, we only need to consider the case of (i. := = d since counts any local function can be rewritten counts over local functions with this form. Here it takes little bit more care, as the single position j upon which to check V(j) may occur far behind the window of n around each symbol.
So for e S d, we need to find the value of some V() at position j ni d, where we can check the value of V (nj + e) using Ve(j). Intuitively, the idea is a # [j < i] d(j) operation order to find j < such that nz c ni d. We can use a local positional function to find the right modulo n, and then find the correct to retrieve ()()).
This be done by looking pack position i - | using a local positional function. Then, need to find the offset which is equal to the position (ni + d. Thus following summation, where only one of the count terms will be nonzero. Let T, = I[[c = (n (d mod n)))] (T, 1) be boolean value indicating we' we've found the correct value.
write the
42

---

Published as a conference paper at ICLR 2025
d
(i) #
j S i, - j+
To A (
d
( = #
j
TAV10)
C1-1(1) = -
Tn- ^ ()-
P=(1) Σ (i(i)
NE x0(00=-1)
For с > d, the position to check occurs in the same window as i, so we only need to check the finitely many cases up to c.
-0)=c-d=1A
(1)) = c d= cn 21:0
p=(1= Σ (())
100
All other cases are straightforward.
Tomita E C-RASP ( flag violation.
A C-RASP program can detect the presence symbol other than and
Tomita 2 E C-RASP[0] A C-RASP program expresses: At each position, either the current sym- bol is and the count of ones and zeros is balanced; the current symbol is and the count of ones is one more than the count of zeros.
Tomita & C-RASP(0] For given string of the form 010 the outputs will converge as K + co by the same argument as for (aa)* in Lemma 38 Hence, Tomita 3 & C-RASP
Tomita 3 & C-RASP periodic, local] Informally, the only way periodic and local predicates are likely to help is if the lengths of contiguous blocks of zeros and ones were bounded (local), or the parity the lengths of 1 and substrings were globally linked to the parity of the positions of transitions 10 and 01 (periodic), but neither is the case. Sketching formal proof, assume C-RASPiperiodic, local) program is given for Tomita First, we eliminate the periodic predicates by labeling every symbol with the position modulo 8, where is multiple of 2 and all moduli appearing in periodic functions; giving an extended alphahet II...., 1,;01,- 0,, O,. For sufficiently large that co-prime with s, we can then also climinate local functions by merging an adjacent block of length e around every transition between ones and zeros into a single symbol A; indexed by the first symbol inside the block and whether the transition happens the floor(s/ (s/2)-th (second part has even length) or ceil(s/2)-th (second part has odd length) position in the block. The resulting language, over an extended alphabet, is recognized by a C-RASP(0) program capable of determining whether string of the form
A A 11422)
(6)
contains a substring of the form
Ag. A even Ag... Ag.....eee even
Ao odd 1.. odd add
43

---

Published as a conference paper at ICLR 2025
This is impossible for the same reasons that bbbb""" (Tomita-4) is not in C-RASP
Tomita E C-RASP(O) By Lemma 6.11 in Krebs 2008 (discussed in Appendix C.3.2
En & MAJ2[<] In analogy, b"bbb"" & <
(-RASPiperiodic, Tomita 4 E C-RASP periodic, local] A C-RASP program tests whether there is position with O where the preceding position also holds O and the position preceding that also holds a O.
Tomita 5 & C-RASP local] This language is the intersection of PARITY with the strings of even length. C-RASP (priioie,,, local] inexpressiveness follows from the same arguments as for PARITY (Lemma
Tomita 6 & C-RASPiperiodics local Consider first the language L3 where the number of I's is divisible by 3. This is not in C-RASP periodic, local] in analogy to PARITY. Now consider the length-preserving morphism (11 = 001, (0) 000. Then h(w) LTomita 6 & w E Lg.
Tomita 7 & C-RASP Tomita 7 is equivalent to {e} U Ub+ Uatbt Ubtat Uatbta" a U a+bta a= b- It can shown this equivalent Σ" \ b' o.'E""0"" and this was constructed in section C.1.5 Interestingly, directly implementing this C-RASP [0] construction in a transformer appears to require least four layers; this is in contrast to the (periodic,, local) construction @
discussed next, where two layers are sufficient!
Tomita e C-RASP C-RASPiperiodic, local] the bigrams 01, 10 to detect a violation.
A C-RASP program can count the number positions with
D, E C-RASP [0] Similar to Tomita 2.
PARITY & C-RASP/periodic, local)
See Lemma 41
(aa)" g C-RASP ())
See Lemma 38
(aa)" E C-RASP periodic, local]
See Example C.2.3
(aaaa)* & C-RASP(0), e C-RASP/periodic, local]
Analogous to (aa)*.
(abab)" & C-RASP p-RisPiperiodic, local]
Analogous to (aa)".
cb" ced""" de" E (-RASP(0) A C-RASP program indicates, first, the presence of "a", "b", "c", "d", "e", and, second, that every "a" preceded only by "a"; every "b" preceded only by "a" or "b";every" "c" is preceded only by "a", "b", "c"; and analogously for "d", "e".
(a, c(b, C-RASP(0) after it.
There is a single can only appear before it; can only appear
(0. 022 & C-RASPiperiodic. local] See Lemma 36 Note that this is equivalent to the lan- guage be over the alphabet Σ = {a, [a, b)..
Formally, Theorems 6.10 and 6.12 in Krebs 2008 show that the regular languages in M MAJ2[<] are contained in DA G. The second component in this product can capture the first subscript of each A, but the second. Since the language D' "oa2" U n b662"* over V = {a, is not in DA (shown, e.g., via the Theorem 2c in Tesson Thérien (2002), which would entail syntactic congruence of (aabb)""b((aabbll and (aabb)"), claimed C-RASP [6] program cannot exist.
9The first layer collects bigrams, the second layer compares the count of each bigram the count of SOS tokens (which known be one) count the bigrams.
44

---

Published as a conference paper at ICLR 2025
E.2 ALGORITHMIC TASKS
E.2.1 TASK DEFINITIONS FOR ALGORITHMIC PROBLEMS
The tasks are generally from Zhou al. (024a), except for Binary Majority Interleave. Here, we define each formally.
Binary Majority. The binary majority problem identifies the most frequent bit in sequence of random bits. An example is S0S the sequence of random bits. We define LEN to be the length of this part. We constrain the sequences such that the number of and Is are always not equal. The model is trained with the language modeling loss on the part bit and EOS token. The minimum length mmsn of this task 1.
0
0 SEP BOS The part 3
is
ROS in other words, it is only trained to predict the most frequent
Binary Majority Interleave. The sequences in this problem are created by interleaving multiple binary majority (see ahove) inputs while avoiding repeating special tokens (e.g., SOS). We use binary majority sequence to compose one sequence in this task. Formally speaking, given binary sequences of the same length, xf.-..2. .f. .f.....r. u and 2 ......... 22. and their corresponding labels (most frequent bits) y², y² y", the interleaved input is SOS #i, æi: oi mz 2. xz SEP 1 y² y EOS.
I x xx
An example is length between SOS SEP (excluding). The model trained with the language modeling loss on the part 1 0
S03
SEP
0 E0S
LEN in this problem refers to
0 EOS
and 4min = 3.
Majority. This problem is similar to binary majority problem except that the vocabulary is bigger. example is [OS a b a b SEP b EGS where c
is a sequence of random tokens, each of which is sampled independently from alphabet of 26 symbols. The LEN is defined as the length of of this part. We constrain the sequences such that there is always a unique answer. The model is trained with the language modeling loss the part
[OS]
Imin 1.
Sort. In sort problem, the model outputs sorted version of the given sequence. An example is sos 14 23 6 9 SEP 6 14 23 ROS where 14 |4 6 is a sequence of unique numbers. LEN this problem refers to length this part. The model is trained with the language modeling loss on the part
6 9 14 23 BOS In this problem, 4min 1. The total vocabulary size of tokens except for special tokens equal the maximum testing length, i.e., 150.
Copy (unique). In this problem, the model outputs the same sequence as the given sequence, which consists of unique tokens. An example is SOS 14 23 SEP 14 23 9 EOS where the first to length this part. The model is trained with the language modeling loss on the second part 14 23 6 9 BOS] In this problem, 4min = 1. The total vocabulary size of tokens except for special tokens is equal to the maximum testing length, i.e., 150.
23 | 5 9]
a sequence unique numbers. LEN in this problem refers
Copy (repeat). In this problem, the model outputs the same sequence the given sequence, which can contain repeated tokens. An example is SOS b a b SEF b a b EOS where the first [b] b] is sequence of random symbols. As in Zhou et al. (024a), we use an alphabet of only 2 symbols. LEN in this problem refers to length this part. Each symbols is sampled independently and uniformly. The model is trained with the language modeling loss on the second part b a EOS] In this problem, Imin =
Parity. In the parity problem, the model recognizes whether the given sequence contains even number SOS 0 1
Is and outputs corresponding token. An example is SEP BOS The bits before SEP and after SOSis random sequence of bits. LEN in this problem refers to length this part. The token between SEP and EOS is the label, it can be either "e" or "o", meaning even odd number of 1s. The model is trained with the loss on the part
ee EOS]] 4min = 0 for this problem. The bits are randomly sampled in a way such that the number of 1s is distributed uniformly given fixed LEN.
45

---

Published as a conference paper at ICLR 2025
C-RASP 0
C-RASP periodic, local
AC yes no yes no yes no yes
Binary Majority
yes
Binary Majority Interleave
none found
Majority
yes
Sort
yes
yes
Copy (unique)
no
ycs
yes
Copy (repeat)
no
yes
Parity
no
no
no
Addition
yes
Table 3: Expressiveness properties of algorithmic tasks as defined in Appendix E.2.1 and discussed Appendix [2..2] In the C-RASP columns, "yes" means we found a C-RASP program: "no" means we proved that no C-RASP program can exist; "none found" means that we found no program despite best efforts. All problems are expressible in TC the tightest known upper-bound on the expressiveness of transformers. We also show membership in the circuit complexity class AC smaller class sometimes compared transformers (Hao al. 2022 Barcelo al., 2024] ; is not predictive of length generalization either here or in the regular languages benchmark (e.g., Addition is in AC but Majority is not).
Addition. In addition problem, the model does binary addition. An example is BOS The two operands are sampled randomly. LEN in this problem refers to the total length of them, including "+" and "=". The model trained with the loss on the part [1 1 EOS| Imin = 4 for this problem. Note that we do not pad zeros in the front of operands to make them of equal length. The length of first operand is sampled uniformly in [1, LEN-2], and the remaining length is for the second operand. After determing the lengths, random bits are sampled uniformly.
sos
1
E.2.2
LIMIT TRANSFORMERS AND C-RASP EXPRESSIVENESS ON ALGORITHMIC TASKS
See Table We provide proof sketches
Binary Majority E C-RASP[0] A single count operation is sufficient.
Binary Majority Interleave and C-RASP[0] We did not find a C-RASP program, though we do not have a rigorous proof of nonexistence. Note that, by Lemma 38 even the (seemingly casier) task of determining whether given input is well-formed (input length is a multiple of the number of different majority sequences) cannot be solved by C-RASP
Binary Majority Interleave e C-RASPiperiodii,, local] rately implement each count operation.
Periodic functions can be used to sepa-
Majority E C-RASP[0] Similar to Binary Majority.
Copy (unique) C-RASPiperiodic, local] If character (or n-gram) repetition is prevented, then the sequence length is bounded by the alphabet, so that the space of possible inputs becomes finite, seemingly precluding the asymptotic analysis done in Theorem 7 To overcome this (apparent) challenge, we consider two formalizations of this task as operating unbounded-lenghh inputs.
First, as explained Zhou et al. (2024a) (and relatedly by Jelassi al. (2023), ), the unique copy- ing task can be realized with an induction head circuit (Section 4. and Appendix C.2.2 More
specifically, each position first records whether SEP has already appeared. An induction circuit then predicts new tokens in proportion to how frequently they have previously followed appearances of the current token before SEP (Section 4.I.. Copying without repetition a special case where each token occurs at most once, the output of f in (IO) is always 0 or 1. We show in Appendix C.2.2 that the induction head construction from Section is expressible C-RASP (pesoipe,iodii,, local but not in C-R C-RASP(0).
46

---

Published as a conference paper at ICLR 2025
Another formalization of the task is in terms of repeated copying, where, given an imput such sOs a b SEP, the model repeatedly copies the string, always predicting the next character, lead- ing to an unbounded sequence SOS the copying task into a function f E F(E) that operates on unboundedly long sequences, out- putting next-token predictions at each position. This alternative formalization is also expressed in C- C-RASP(periodic, local], by essentially the same induction head algorithm.
C bo SEP
bo SEP b SEP.... This turns
Copy (repeat) E C-RASPiperiodic, local One proof proceeds via communication complexity: By Corollary 13 copying of general strings is not expressible by Limit Transformers and hence not in C-RASP C-RASPiperiodic, local]. While valid, this proof does not make transparent why length generalization is much easier if repetition avoided. A different approach, not using communi- cation complexity and crucially using the presence of repetition proceeds from the fact that, over the alphabet Σ 2 {a, b, e) the language beb""bE" & C-RASPIperiodic local] (Lemma (35). b'*
and uses it to deduce that, given an input of the form bu ube (v, E Σ*, k large), no C-RASP(perioddi.local program can reliably determine whether a should follow.
Sort E C-RASP[0] As explained Zhou et al. (2024a). this can be realized by selecting the smallest number in the input that is larger than the last output symbol. This algorithm does not require local or periodic positional information.
Note that, as in COPY (unique), the input length is bounded by the alphabet size in this case, but we can view it as a task defined with unbounded length by the same trick as for COPY (unique), whereby an initial sequence such SOS
b SEP is repeatedly sorted, leading to unbounded se- quence SOS a c b SEP a b C SEP a b SEP....
Parity & C-RASPiperiodic, local] See Lemma
Addition & C-RASP/periodic, local] Addition is at least as hard as copying, because the special case of adding zero to number amounts to copying (Corollary 13
E.3 DETAILS OF EXPERIMENTAL SETUP
As mentioned in the main paper, at train time, we add random offsets position indices so that all position embeddings are trained. The offsets are sampled uniformly at random in the range [0, N [=|]] (see Section 2 Like Zhou et al. (2024a), we sample independent training batches the fly instead of using a finite-size training set. In contrast, each test set contains 2000 samples that are sampled at the beginning of each experiment.
For the problems where we train models with language modeling loss, the length of inputs is sampled uniformly from minimum up maximum length in the specified range. This is true for training data and all test sets. As mentioned before, we also use predictive modeling. At each step, the model outputs label indicating the set of possible next characters, including EOS. The models are trained on whole sequence of tokens. In decoder-only models, standard predictive modeling approaches are less straightforward. Therefore, we assess predictions by combining the input and output spaces. For every position in the sequence, we evaluate the predicted character by comparing the output space (where each embedding represents a subset possible next tokens) against the expected value.
We train decoder-only transformer from scratch, using implementations from Hugging Face Trans- formers 10 We train models for maximum 30k steps with a batch size of 64. We stop training early once the model's accuracy reaches 100% on the in-distribution test set (the one in range [Lmin 50]. The model is trained with dropout rate of 0.0. We use AdamW, with weight decay rate of 0.01.
In preliminary experiments, we found that different model architectures, while achieving 100% ac- curacy in in-distribution data, may perform differently on out-of distribution data. To draw a clusion about how the model performs on a problem in general, we determine the hyperparameters as follows: We consider configurations of (1, 4) layers, (1, 2, 4) heads and model dimension of
/
trans Toansoorme GPP.T22MeeeMeeedeee
47

---

Published as a conference paper at ICLR 2025
Problem
Model Size
LR
Max Steps
Tomita-1,
layer; 1 head; 16 dim
le-3
30k
D2. Ds, Da. D12
layer; 4 head; 128 dim
le-4
30k
Tomita-4,7
4 layer; 2 head; 64 dim
le-3
30k
{a, beddd)dddbbb. cf an" tabbb" cc* "eddddes ee"
6 layer: 4 head; 64 dim
le-4
30k
(aa)". (aaaa)* (abab)*
layer; 4 head; 256 dim
le-4
60k
5o (0, 1, 202", Parity
6 layer; 4 head; 256 dim
le-4
60k
layer; 4 head; 256 dim
le-4
60k
Table 4: Experimental Hyperparameters for testing NoPE on the Regular Languages
Problem
Model Size
LR
Max Steps
Tomita-1,
layer; I head; 16 dim
le-3
30k
D2, D3, D1. D12
layer; 4 head; 128 dim
lc-4
30k
Tomita-4,
layer; 2 head; 128 dim
lc-3
30k
{a, {a, bbbdd c)", aa" cb" (aa)". (aaaa)" " (abab)", Parity {0, 1,2)-02", Tomita-3, 6
ec dd ee*
4 layer: 4 head; 64 dim
lc-4
30k
layer; 4 head; 128 dim
le-4
40k
6 layer; 4 head; 128 dim
le-3
30k
Table 5: Experimental Hyperparameters for testing APE on the Regular Languages.
{16, 64, 256), and learning rate of {0.001, 0.0001}. We sweep all the configurations by iterating over every combination and choose the one that achieves the highest accuracy on [51, 100) among those configurations whose accuracy on [lmin 50] is 100%. When there are multiple such options, e.g., their accuracy on [51, 100] is 1 100%, the one with the simplest architecture is selected (when estimating complexity, we assume the following priority: number of layers >> number of heads > model dimension). The final hyperparameters we used for each task are shown in Table6land]
When no configuration from the search space defined above can achieve accuracy of 100% on [mmnn 50]. e.g., in the case of ADDITION, we use an extra configuration, where the number of layers is 12. number of heads is 12, model dimension is 768, learning rate is le-4 or 3e-5 (if le-4 does not work), and a bigger maximum number of iterations, 60k, we also use the first 3k steps as warm-up steps.
After we determine the hyperparameter configuration, we run the experiments with multiple random seeds and report the average accuracy of 5 successful runs (those runs where the model achieves 100% accuracy on in-distribution data). We do not select successful runs in cases where we use the biggest architecture (the 12-layer configuration), because we find in many cases the accuracy on in-distribution data stops at around 99%.
The random baseline plotted for the algorithmic tasks (Figure I left) is computed using 2-layer MLP with token embedding layer; hence, the model predicts the next token solely based on the current token. is trained with the same hyperparameters as transformers, the learning rate is 1e-3.
Problem
Model Size
LR
Max Steps
Binary Majority
layer; 1 head; 16 dim
le-3
30k
Binary Majority Interleave
layer; head; 256 dim
le-4
30k
Majority Sort
layer; 2 head; 256 dim
le-3
30k
layer; head; 256 dim
le-4
30k
Copy (unique)
layer; 1 head; 64 dim
le-3
30k
Copy (repeat)
4 layer; 4 head; 256 dim
le-3
30k
Parity
4 layer; 2 head; 256 dim
le-4
30k
Addition
12 layer; 12 head; 768 dim
le-4
60k (3k)
Table 6: Experimental hyperparameters for testing APE on each problem. In the last column, num- bers in parenthesis mean the warm-up steps, which is 0 when there is no number in parenthesis.
48

---

Published as a conference paper at ICLR 2025
Problem
Model Size
LR
Max Steps
Binary Majority
layer; 1 head; 16 dim
1e-3
30k
Binary Majority Interleave
12 layer; 12 head; 768 dim
le-4
60k (3k)
Majority
layer; 1 head: 64 dim
le-3
30k
Sort
layer:
head; 256 dim
le-3
30k
Copy (unique)
4 layer; 4 head; 256 dim
1e-3
30k
Copy (repeat)
4 layer; 4 head; 256 dim
1e-3
30k
Parity
12 layer; 12 head; 768 dim
3e-5
60k (3k)
Addition
12 layer; 12 head; 768 dim
le-4
60k (3k)
Table 7: Experimental hyperparameters for testing NoPE on each problem. In the last column, numbers parenthesis mean the warm-up steps. which is 0 when there no number in parenthesis.
Found CRASP|Periodis, Local] Program
No CRASPiPeriodk, Local] Program
Found CRASPI] Program
No CRASPI Program
(sa)*
(sssa))
(abab)
Tomita-3
Tornita-5
Tomiia-4
180
109
160
Bin
Bin
Bin
Bin
Bin 2
Bin 5
Bin
Bin
Bin 3
Bin
Bin
Bin
Bin
Bin
Bin
Bin
Bin 2
Bin
D-12
Tomiita22
Bin
Bin
Bin Bin
Bin
Bin
Bin
Bin
Bin Bin Bin
Tomita
Tomita-7
"d"ob"oc"dd"ee"
(o.b)"d(bbo) o)"
(0,1,2)'02"
Figure 2: Detailed results for regular languages with language names, corresponding to the right part of Figure but with individual languages labeled.
F TRANSLATING BETWEEN TRANSFORMERS AND LIMIT TRANSFORMERS
Here, formally introduce the product parameterization, formally state the hypothesis class, and state and prove the technical lemmas establishing the correspondence between ordinary transformers and limit transformers.
F.1 PRODUCT PARAMETERIZATION
This parameterization defined as follows:
Definition 43 (Product Parameterization). For l = I,..., set
VO, (p: :)) [E, o)
VO; = (Bi)
: =1,-.. .....d) VIo -0
VI, = ={(A)s,
:8 1
dU,, 0 : E
Vo
U VO,
10.1.....
VI VII
E0.1....L
P = -[[(i,, Vi
O h.... 1sh SH)
49

---

Published as a conference paper at ICLR 2025
Algorithmic Problems
In ACO
Not In ACO
Binary Majority
Binary Majority Interleave
Majority
100
100
100
50
Bin
Bin 2
Bin 3
Bin 1
Bin 2
Bin
Bin
Bin 2
Bin
Bin 1
Bin
Bin 3
Copy
Copy
Unique
Repeat
Parity
Addition
100
50
50
50
Bin
Bin 2
Bin
Bin 1
Bin 2
Bin
Bin
Bin 2
Bin
Bin 1
Bin
Bin 3
Regular Languages
ACD
Not In ACO
(aa)*
(aaaa)*
(abab)*
Tomita-3
Tomita-5
Tomita-6
100
100
100
100
100
100
Bin
Bin
Bin Bin
Bin
Bin
Bin
Bin
D-2
D-3
D-4
D-12
Tomita 1
Tomita-2
100
100
100
100
100
Bin 1
Bin
Bin
Bin
Bin Bin
Bin
Bin Bin
Bin
Bin 1
Bin
Bin
Tomita-4
Tomita-7
ddbb)"((b,c""
(0,1,2)'02*
100
Bin 1 Bin 2 Bin
Bin
Bin 2
Bin
Bin
Bin 2 Bin
Bin Bin 2
Bin
Bin 1
Bin
Bin
Figure 3: Membership in the circuit complexity class AC does not predict transformers' length generalization algorithmic problems (top) regular languages (bottom). Prior work has often linked the expressiveness of transformers to circuit complexity (e.g. Hahn 2020: Hao et al.] [202]]
Merrill & Sabharwal, 2023c Strobl 2023 Barcelo al., 2024). All tasks included in our exper- iments are the class TC". the tightest known upper bound on transformers' expressiveness. A well-known circuit complexity class within TC is AC known upper-bound bound the power of cer- tain hard-attention models transformers (Hao et al. 2022 Barcelo et al. 2024), which may raise hopes that it helps understand transformers' practical abilities. However, membership in this class does not predict transformers' length generalization behavior. On the algorithmic problems, there no apparent correlation all; majority-type problems, which the attention mechanism can easily implement, are not in AC but problems with super-logarithmic communication complexity such copying and addition (Corollary 13) are contained. On the regular languages, AC exactly covers the class FO[reg]. This class can be proven to include all regular languages in C-RASP, but also includes various languages that transformers tingth-generale
poorly on, such Tomita-3. A nat- ural subclass, obtained by restricting the size of AC circuits to linear number of wires, yields the class FO, Reg] (Cadilhac & Paperman 2022), which does not match transformers' behavior well either, e.g. it includes {0, 2,
"02" (bottom right, equals be from Lemma 11] but does not in- clude D-12. Taken together, established circuit complexity classes do not account for Transformers'
length generalization behavior. Compare to C-RASP results in Figures and
50

---

Published as a conference paper at ICLR 2025
(A) Star-Free vs Non-Star-Free Languages
Star
NoPE
Star NoPE
(na)*
(aaaa)*
(abab)"
Tomita-3
Tomita-5
Tomita-6
100
Bin 1
Bin 2
Bin 3
Bin
Bin
Bin
Bin
Bin
Bin
Bin
Bin 2
Bin 3
Bin Bin 2 Bin
Bin 1
Bin
Bin
D-2
D-3
D-4
D-12
Tomita 1
Tomita-2
100
100
100
100
100
100
Bin
Tomita-4
Tomita-7
as bb ee"
(ebbed((,e)'
00.1.2y02²
100
100
100
100
100
1
Bin
Bin
Bin
Bin
Bin
Bin Bin
Bin
Bin
Bin
Bin Bin
(B) Dot-Depth
Dot Depthe1
Dot Depth
Dot Dopthe3
Dot Depthm4
Dot Depthe12
(aa)'
(asas)"
(abab)*
Tomita-3
Tomita-5
Tomita-6
100
100
100
100
100
100
D-2
D-3
D-4
D-12
Tomita 1
Tomita-2
Bin 1 Bin 2 Bin 3
Bin
Bin
Bin
Bin
Bin
Bin
Bin
Bin
Bin 5
Bin
Bin
Bin
Bin 1
Bin
Bin
Tomita-4
Tomita-7
aa"bb"cd "d"""""""""""
(bbb)'((b.c)"
(0,1,2)'02*
100
100
100
100
Bin 1 Bin 2 Bin
Bin
Bin
Bin
Bin
Bin 2 Bin
Bin Bin
Bin
Bin 1 Bin
Bin
Figure 4: (1) Comparing length-generalization with standard notion of the complexity of finite- state languages: Star-free languages (green) do not require modular counting (McNaughton & Pa-
pert 1971), have simpler algebraic representations in terms of group-free monords (Schützenbergerr) 1965 are easily represented by modern state-space models (Sarrof et al., 2024). and match the ex- pressiveness of formal model hard attention Transformers (Yang al.) 2023). However, they do not consistently lead to length generalization in transformers, which on the other hand length- generalize on some non-star-fin languages such (aa)*. The expressiveness C-RASP correctly accounts for the observed behavior. (2) Within the star-free languages, standard complexity metric dot-depth, with increased dot-depth indicating increased complexity (non-star-Fie languages are plotted in gray color). Dot-depth does not predict length generalization, which succeeds on some languages at dot depths 1 and 12 and fails at some languages at intermediate depth. See Figure for further discussion regarding another existing notion of complexity, circuit complexity, also much less successful than C-RASP expressiveness at predicting length generalization. Compare to C- RASP results in Figures and
51

---

Published as a conference paper at ICLR 2025
Given transformer T with (T) < cc, define:
S2, :
II S BES;
K Q1
II S E
E
SESa
for SIS 1,
1 1 h < H;
VO; VO; S1 E
8s =
II S E
SES
for ;In;
w VOL; SEP
where the matrix product over a set S E P
II S
(8)
SES
is computed in descending order of layers; with the S associated with the lowest layer at the right.
For instance,
II
S Va, V1. V1,
(9)
Remark 44. Here, exemplify the Product Parameterization (Definition 43
01..0.0..p.. E, =p, KT,,, Q1
V PP; Vi K2,1 Q2.PP;
03,6, N.V H.E.E E, = =E" VT,W" VL K. 2,h Q2 Vi, E,
(0,(A)).. = =AAI),,p. P: (a).. E. -(As),,
Vi,
V.N.N. -UT Va. V1,1 E,
BLVEN. -U: Va. (2,x(B1).
For ease of notation, we have not restricted the layers from which different vector parameters are taken in the definition of and B; hence, they will also include products that are not relevant to actual computations, such as
Remark 45.
(10) where a vector of the form V3, Pj cannot actually feed into the computation of queries the first layer. This is simply for simplicity of notation; such products will not impact results, though one could explicitly exclude them if one wants to obtain tighter quantitative bounds on the parameter
T TV KT p 2. 1.k Q1, Va,
count of Limit Transformers in Lemma 52
F.2 FORMAL DEFINITION OF HYPOTIIESIS CLASS
Definition 46 (Hypothesis Class, corresponds to Definition 4. Let E N be fixed. For each n 1,2, 3, 3..., define the hypothesis class O, as the set of transformers T (as defined in Section 2 where
1. ((TT)
2. each parameter vector and matrix Tf is represented at p bits of precision
3. each product function (Definition involving positional encodings is translation- invariant. That is, every product function involving exactly one positional encoding is constant across positions, and for every 1 iij,i A.j
for all 1, S1, S2 making these objects well-defined.
52

---

Published as a conference paper at ICLR 2025
F.3 FROM LIMIT TRANSFORMERS TO TRANSFORMERS
We give a translation from Limit Transformers to standard transformers for every finite context window N. The translation is uniform in the sense that R(Tv) from (8) is bounded across all Tv. though the width may need to increase. More intuition is provided further in the proof of the translation.
Lemma 47.
Let Too be Limit Transformer satisfying PERIODIC and LOCAL, Then there transformers Ti, Ti.T..... (T' & (2)) such that, for all N G {O....,i i |21}:
Ti(2,0) o) = Too (z. 0) when o+ o+1 S
(11)
and
sup (T;)) <0
(12)
Proof. We hats indicate the parameters of the constructed transformers. Fix N N; construct TN-
Let A be the periodicity of p.- The construction sets L L 2 and H max(1, H, A}. Each activation has d == N 3A dimensions, which can be partitioned into six regions:
d dimensions (Region I: main region)
dimensions (Region II: position region)
A dimensions (Region III: periodic region I)
(13)
A dimensions (Region IV: periodic Region II)
1 dimension (Region sOS Region)
A + dimensions (Region VI: Copied SOS Region)
Region I directly emulates the computations of the Limit Transformer. Region II carries absolute positional information, used for simulating the positional functions Φ1,
We define the token and positional encodings as
O Rd e, E TR ((%A)-1 RA OE RA OER 0 RA+1
E. E Rd O E R.N O E RA O E RA 1 1 E IR E RA+1
p:
É.
where e; is the i-th unit vector. Region holds token information. Region holds exact position information. Region III holds modular position information. Region V indicates whether the to- ken is sfaruecf (SOS) or not. Content will be written to Regions IV and VI by attention components.
Intuition At first sight, a simple intuitive translation just uses Regions and II, placing all param- eters of Too into Region I, and taking one-hot vectors e; for Region II encode exact positional information, so that the functions ΦI,, can implemented by products p, Qpyz One would thus use the simpler encoding É, = [ 0] and µ; := [pt, ei]. Such a translation would be able to reproduce the input-output behavior of T However, it would fall short in two ways: First, the positional encodings p; can give rise to patterns whereby p KT Qp,, is periodic in - when large. and thus bounded away from zero at unboundedly many distances bounded. We will avoid this by routing modular positional information through value matrix V1,1 before making it available to attention computations; intuitively, this is possible because the vectors span. Modular positional information starts out in Region III of p., and is copied by V1, I into Region IV: no K" Q matrix the construction will directly address Region III. Second, transformers in O must satisfy the requirement that all product functions are cunslation-invariane differently to different p, is), and thus also not the simple translation sketched. We overcome this by adding different attention heads, each assigned to some e {o..... - 1}. each of which primarily attends the SOS symbol (based Region V), with stronger weight in the k-th head
making (8) un-
p, have
translation invariant; such a requirement need not be implemented by Txo (e.g., MLPs could respond
53

---

Published as a conference paper at ICLR 2025
falling SOS if the distance between the query position and the SOS position is congruent to modulo (based on Region IV). These attention weights are written, via the value matrix, to Region VI. An MLP then compares each of these attention weights the weights resulting from uniform attention, thereby determining the head giving rise to the highest attention weight, and places the matching encoding p; into Region I. This construction maintains translation-invarinnce of all prod- uct functions; most importantly it makes all / functions involving positional encodings equal to zero: The MLP reads from Region VI, whose entries are linear combinations of entries from Region V, which is zero in all fs. Crucially, the dependence of the positional encoding written to Region I on the original positional information P; is mediated entirely through attention weights, which do not enter the definition of the product functions. Once these computations are completed, Region I matches the activations To at offset and direct simulation of To can proceed based on Regions and II. Taken together, we expand the intuitive simple construction to make rigorous the intuition that hounded-ranks positional information can be utilized by transformers even under the constraints that (8) be bounded and that product functions be canslation-invariaan
Layer 1: Copying Periodic Positional Information to Region IV In the lowest layer, each po- sition attends to itself and moves the periodic positional information from Region III to Region IV. Formally:
Ω
I IN
0
0
0
0
0
K1,1
Q1,1
0
0
0
0
100
0
0
0
0
0
0
0
0
0
0
0 0
0
V1.1
0
0
0
0
1
0
1000
I
0
0
0
for some Ω > 0 to be chosen later. After attention (the MLP does nothing, B1, b, = 0), the
output will be
E, e, ((%A)+1 (1 ()E(AA))+
(14)
18
where e < 0.1 when Q2 is sufficiently large. Region IIII will not be addressed by any further down- stream matrices or vectors. The idea behind this operation to ensure no KT Q matrix will directly have read from Region III rather, any dependence of attention logits on modular positional in- formation is mediated by the V1,1 matrix. This allows us to keep (8) bounded even in the presence of such dependence, as detail below. Note that this strategy importantly relies A Rice (T so that ran,(Vi.1) is bounded independently of N. Intuitively, modular positional information (unlike the full positional information encoded Region can be routed through bounded-rank compo- nents, which enables keeping (8) bounded.
Layer 2: Determining Position Relative to SOS We now add a second layer, in which we attend with + different heads, where the s-th head tests whether the distance to SOS is congruent to modulo A, and the A + 1-st head attends uniformly. By determining which head attends most strongly to SOS, we can read out the relative position with an MLP without breaking the translation invariance of product functions.
54

---

Published as a conference paper at ICLR 2025
For h 1..... A, let Q2 be such that
Q2,h
(15)
Ci
C++A%A
0
Let n2, (h I...., A) be the identity matrix restricted to Regions IV and V. Further, let
Q2 = 12A+1
(16)
Then, for h I....,
of RT 12n0 i-jzh (mod)
(17)
and
K 1 Q2,4+19, =0
(18)
Intuitively, heads I..... A attend preferentially positions given distance modulo A; head A + 1 attends everywhere. Define 22,1 for h = I,..., A by
2,h
(19)
Cb.
As the only vector parameter with an entry in Region V is the token embedding for the SOS token, the outcome of this attention block effectively writes the attention falling on the SOS token for each of the A + attention heads. We then use a Heaviside MLP with number of hidden units bounded A to determine for which opposed to smaller) entry than entry A + 1. The MIP, via the B matrix, then writes p. to Region special case oceurs at SOS, where Region V is (it is everywhere else); here, the MLP units described above disabled (a 1 in Region V causes large negative number to be added to their inputs) and the MLP instead writes P1 to Region I. Overall, + MLP units with Heaviside activation sufficient for this construction. Overall, after the MLP, the i-th position in the string has P((i- ()(1)))))++ added to Region I. Overall,
1, ....... A it holds that entry s in Region VI has greater
Ez, + Pi-ot1 eito
y
Ei-o
0
(20)
where o is the offset, and the second equality holds if the Limit Transformer is run at = 0. In
layers 2,...,,, L, only Regions I and II will receive any consideration.
Higher Layers: Emulating T Next, for 2 define K
Q E dRdxd
1+2,
KEA
Qla
0
W
0
KT
0
0
0
0
0
(21)
0
0
0
0
0
0
0
where i j:
(Win)i, (i.
(22)
satisfy
p WT.P; 1i.n
(23)
55

---

Published as a conference paper at ICLR 2025
Then W is sum of matrices each of which has the value @1 (E-j.j) for some i (off- ooff-)aiagonal and zeros elsewhere; hence
WEa lla
Σ 10
(24)
Overall, [| Q1+1, can be bounded, independently of N, in terms of K Qt,al and || 1|1- As Φi is local, this 1-norm is finite.
We construct other parameter matrices and vectors by placing the parameter from the Limit Transformer into the Region I and leaving all other regions zero. Now, by induction, the first d dimensions of any activation will match those the Limit Transformer, but shifted by two layers:
(1) y1
Cito
(4+2)
(25)
As the U matrix only reads from Region I, the output will also be the same for the Limit Trans- former.
For the excess heads, the matrices just to 0 in the first or the higher layers depending whether H or A is larger than the other.
Bounding Norms and Ranks Atl 2 2, now the ranks of Vi, and the norms of A,, Bt, U and the l2 norms of b, will be the same they were in the Limit Transformer. The increases from the first and second layer are bounded in terms of and hence (Txo)
Verifying Boundedness of ( By construction, P. KT Q = 6: and K.K.K.KK Q2, 1. 0. For the higher layers, the boundedness follows because Too satisfies LOCAL.
Verifying Translation Invariance We need to verify that all product functions are translation- invariant. Each Pi contains entries in Regions and III. the first layer, we have 01.1,0.0.p...;; d.j, hence, these are translation-invariant In the second layer, we have
0
0
C
02.s00.0.p..pp
e(%%))+1
0
2,a
Q2,a
E0%AJ+1
0
0
(26)
0
0
0
0
(V)...V..
(27)
0
T
e,
(2.s
e(%%))1
0
V K Q2 V1,1
eu%A)+1
(28)
0
0
0
T
0
0
KT. Q2
O
(29)
((%4)+1
CURA)+1
O
O
1 - A)
(30)
(31)
56

---

Published as a conference paper at ICLR 2025
These all translation- invariant. All 02+t2.0000pp.p equal function (1,(i,)) and hence translation invariant. No V matrix ever reads from Region II. Overall, all products are translation- invariant. In higher layers, K" Q matrices read from Regions and II. The positional encodings p; write to Region II but not not even when mediated directly through value matrices Region I, and the products are translation-invaaiint because the functions 01,a
Consider
Pp.
because the first layer MI.P does nothing. Second,
Sp.(Aala...P
because the second layer MLP only reads from Region VI, and none of Ps. V1P, contain any entries in Region VI. Also,
US.U..p. 0
{(v))U,,..
((V.V.
B(va),
since none of ps. ViP, V/Vip, V2p; contain any entries in Region I, where U, has its entries.
Since V2,, all read only from Region V, whose entries have connection pr, also have:
B ((va... ). = 0
B(Va...) U.U.P. = 0
V... h(A))...
Biva, P.U.P.
Overall, all 8 products involving p; are translation-invariant,
F.4 FROM TRANSFORMERS TO LIMIT TRANSFORMERS
We first establish various smaller lemmas. The first lemma informally says that, when f(i p. Ap, is translation invarraan in (i,j), and has bounded rank, then fi, is periodic. This lemma is key the prominent role of the PERIODIC property in Theorem 7
Lemma 48. Let p E N, and let N E N. Let PI...., ,PN E T such that pillz < C; let A E R
Let ((i.j) == pt Apj be translation invariant, in the sense that
v0 v0sis VM 2 0:j++ M N = f(i.j) f(i M.j + M) Further assume that, for < j. f(,j) can expressed with p fractional bits 11
(32)
Define for n 2 0
G(n) f(, (1,1+n)
(33)
Then there is N upper- in terms rank( A), p. C, and ||A]| (but not N) such that
Vn n n N G(n) G(n
(34)
Proof. Let := rank( A); is > 0 without loss of generality. We write the singular value decom-
position of as
A-UTyM
(35)
II particular, this is satisfied if p:, A each expressed fixed precision q, where p 2 3q.
57

---

Published as a conference paper at ICLR 2025
where E Roxo, U, V Roxd where |U]|, [ I 1. Then write
(VD))
(pp (VDi)
T
Upi Vpj)
p Ap
(Ipxp 0pxp) E (0pxp Ipxp)
(36)
We will henceforth replace A by pxp 0pxp) E
D (0pxp pxp) E Roxp and p; by
Up: Vp:
E
I² 22 rank(A); note that this increases the norms of these objects at most by multiplicative constant while preserving the products p Ap,,
As ||p:122 < C' for all i, we find that, when N is sufficiently large, for each 0, there p.. Pj < j) such that:
p: pylla
(37)
Take == The minimum required distance A can be upper bounded by considering the e-packing number of (v ||e||| S C} and applying the pigeonhole principle. Hence, overall, A can be upper-bounded bounded in terms of c, tank(A), and C. Importantly, this bound is independent of N. Hence, Ak E {i N).
|G(k - i) G(k - i- A) If(i, k) - f(i + A))
1f(i, k) -f(i+ (j -), k)
Ip. Apx - -D Apxl
S lpp: 1/1 |2/lApill1
S E. Appll2
Equivalently, using the substitution I : k - A, we have, for any EE fl...., - A}:
IG(L A) G(I) - | Apall2
(38)
Take c then
2- T
G(I) A)
(39)
due to the assumption about fxxe-prreiisio outputs.
Lemma 49. Assume each parameter transformer is represented at p bits of precision. Then each product function is exactly represented at 2L)p bits of precision.
Proof. Each product function consists at most of two vectors, a key and query matrix, and up to 2L value matrices. This results in sum of numbers that each product of up 4+ 2L numbers that each are individual parameters. As each number represented at p bits of precision, each product represented (4 + 2L)p bits of precision.
It will be useful to define complexity metric applicable to Limit Transformers: Definition 50. For Limit Transformer T, define Res (T) as the sum of
1. H
2. the precision p used for expressing the parameters (Definition 2) and the precision p used for rounding attention logits and the output of exp(-) (Section
3. the maximum 8e norm of all parameter vectors and matrices (including positional encod- ings)
4. the minimal periodicity A of the positional encoding
5. maxLa E 16 (1, (short: maxi, || ll2).
Formally, plus the supremum of the of A's for which p. P.+A-
58

---

Published as a conference paper at ICLR 2025
Proposition 51. Let A R4. Let U be the of Limit Transformers T such that Re (T) S A. Then the set of parameter settings in U, other than the 0L functions, is finite.
Proof. Immediate.
We now state the key lemma translating ordinary transformers Limit Transformers using the product parameterization:
Lemma 52. Let T E On. at bits of precision. Let the alphabet E. be fixed 13 Then there is a Limit
Transformer Toe such that T= Tox at length S n and
Rx (Tx) S F (R(T))
(40)
for some universal functtionn F R4 R. and
p. K QLPP, (i,))
(41)
for the pi, Ki,h: Qt parameters Tf; for each h. In particular, Too satisfies PERIODIC and each
oL translation cinslation-iivariantt
We prove the lemma in the remainder of the section.
F.4.1 PROVING LEMMA 52 (I): PRELIMINARIES
We discuss various preliminaries, before presenting the construction, explaining its intuition, and explaining how its soundness is formally proven.
Basic Idea We will construct xox so that the entries in every parameter are 0, 1, or one of the prod- uet functions from Definition 43 This will automatically ensure that its parameters are represented at fixed precision p bounded in terms of R(T), and with each entry bounded in terms of the spectral norms of parameter matrices and the & norms parameter vectors, hence, also bounded in terms of RT)... Importantly, will use the definition of RTT) and the definition of O,, restrict attention to number of product functions that are bounded only in terms of R(T), independently of n.
Bounding Active MLP Units First, given ||Ar] < co, the number of nonzero entries is bounded ||A: which bounded in terms of RTT). Similarly, the number of nonzero entries by is as < bounded as < of the maximum number of nonzero entries in b, and the maximum number of nonzero rows in A, Without loss of generality, by reordering rows in A, and columns in Bi, we may assume that, in each layer, these entries are in the first dMLP dimensions. Then dMLP is upper-bounded in terms of these (or d, if the bounds exceed d); this is bounded in terms of R(T) and independent of n. In each layer, only < dMI.P of the MLP units have nonzero input weights Ar, output weights Bi, or biases b, Removing product functions belonging to the inactive units, set:
2-2p
2 2p and similarly for Bi. Let dMLP S be, across / = l..... L the maximum
VI, :I {(Ai),, dMLP I....,d)
VI = U VI
Then, the size of VZ is bounded in terms of R(T).
Periodicity of Bounded-Rand Positional Functions By Lemma 48 all products p. ... where the intervening material has bounded rank are periodic in with period bounded in terms of the rank of the intervening material, and hence R(T). Let A be the least common multiple of the periods obtained from Lemma 48 across the (finitely many) different products of the form St. Sp
The bound Roo (Tx)) depends but during the inference procedure, the alphabet is assumed fixed.
59

---

Published as a conference paper at ICLR 2025
where S₁ U + 0. Define
VO, = (p: 1....,,, ... A (Eo :0)
VO, = (Bi)., :8 dMLP), 1= 1=1..... L
VO =v0 u U VO
1=1
Then, the size of VO is bounded in terms of R(T).
F.4.2 PROVING LEMMA 52 (II): CONSTRUCTION OF To
Translation in Terms of Regions We use hats (i.e., ") to mark the parameters and activations of the Limit Transformer, distinguishing those from the parameters and activations of the original transformer T.
Each d-dimensional parameter vector and activation (residual streams and attention outputs) is trans- lated to a vector consisting of three regions, each having a fixed number of dimensions bounded in terms of RT)), That is, each vector parameter activation (e.g., Ps, E., y is translated to parameter or activation 8 (e.g.. Pi, E., V: vector consisting of the following three regions:
s ( S P; E VI
8 = A...T..T...h. an (v) :1:1 L; < h < H1 C Tí Tí, T2 w1, W2 E Vo
Oga, T... (v)
I, H;S T Tı, T2 E
11, 1, W2 VO
(42)
Intuition of the Construction The first region, denoted I Tw (ū). has one entry for every choice of S P; E VII,- Intuitively, the entry Is, s. (8) describes the outcome of applying all value matrices in S and then finally the vector w
Is, 1 "
I S UER
(43)
SES
(Recall Definition 43 for the notation IL S.) The second and third regions each have entry for every choice of 1 < < S2 S T2; T1, P, w1. E VO. These regions contain the information necessary for computing attention logits. Intuitively, Ti. Tz describe the value matrices through which wi and w2, respectively, pass before the computation of attention logits in layer For parameter vectors wi, W2 (e.g., token embeddings or columns of a Bi matrix positional encodings are somewhat special), we simply expect (note the duplicated arguments T, T2 these will be explained in the next paragraph):
T
ATiTi, TT..T,TT...ww..ee wy (w) Ti..aa. (w2) wf
II SETI
K Qla
II SET
S
W2
(44)
Thus, can he viewed as holding key parameters, whereas S can be viewed as holding query param- eters, for the contribution that the pair of wi, wy makes to attention logits in layer 1, after passing through the value matrices in Ti, T2, respectively. As convention, at the level of parameter vectors, the A component will hold the attention logit contribution (the RHS of this equation), whereas the component will just hold zeros and ones. At the level of intermediate activations (y. or ( the situation is slightly more complex: here,
As, Ta.k we (g)
(45)
denotes the contribution to attention logits for head h at layer & arising from multiples of (IISET, 8) wi in activation y, (k-1) interacting with multiples of (IISET, S) Wh in an activa-
tion y (k-1), similar idea applies Ω However, additional care is needed to ensure that only
60

---

Published as a conference paper at ICLR 2025
contributions from value matrices are counted that actually passed through. The additional argument S1 serves as a "to-do-list": it records which of the value matrices in Ti still have to be traversed; whenever activation passes through value matrix Vi,e,, the value matrix Vi. of the Limit Transformer moves entries from As, Ti kT,,T,,,,.... to - (. J. T.T..T,. - ef- fectively removing itself from the "to-do-list". The same prineple applies 52, which maintains to-do-list S2 for 72. In the end, only those components where the to-do-lists are empty (formally, S S 0) will enter attention logit computations of the Limit Transformer:
(i.j) +
Σ
A.
Y
(y: () K Qu, (46)
v.w.7i.72
where the sum runs over all w E VO, and Ti, T2 runs over all sets of value matrices from layers < I.
In the remainder of the proof, we present a detailed formal construction implementing this intuition.
We first define, for each vector {pi, Es 1, its translation ら; throughout, we will define each of the three regions.
Vector Parameters by Vo We take (bi)s = (b)), for s = -.....,dri dMLP.
Vector Parameters E, VO The first region provides products with other vectors appearing at higher layers (rows/columns of the A, matrices and the unembedding matrix). The second and third regions provide products leading up to keys and values.
Bs w. E.
if w E VI
Ts. w E.) =
else
01, W1
if E, wi, S1 Tı
(Ea)
0
else
1
E, = 222 S2 = T2
En
else
Vector Parameters: P. For v = Ps. the construction is analogous, however, we zero out the entries for ppp.. and Rgp.n..i.p..pp as these will be taken care of by the Φ1, functions. For- mally:
if E P, E VZ
rs. =
else
if P.x
wi; (w2 &
#
A.. (pi)
S Ti
0
else
1
if Pix Wz; (wi & (p:: V T Ta #1)
(p:)
S₂ T2
0
else
We need to establish that T satisfies PERIODIC with the period A given above. First, B8 es.ep, is independent by translatooniinvaiine thus trivially periodic Second, the A and Ω entries periodic in with period A by construction.
61

---

Published as a conference paper at ICLR 2025
Matrix Parameters: Vi. Each entry in the VI, matrix is zero one. We define it implicitly, in terms of its action on the three different regions:
us (1 )1)
J. (v)))
VL,1 & S else
As, Ti, T...aa..... (Vi (1)
75 (V)
VI, & St. Vi, E Ti else
F1.. (v(l
(B)
VI,6 $ S2, Vt,1 E T2 else
Matrix Parameters: A,, B Let E (I,..., dMLP). For the s-th unit in the MLP at layer I, we first define the s-th row of A, by setting
(A)),
(A)).. y-(1)
E R
and define the s-th column of B, as follows writing X E RR for the s-th hidden unit activation:
s X) = (s,w,(B)...
Ta. (Bi, =
(1 else
wi (Bi) T
(0
{1
if ww -B:i) T2
(B ()) =-8
00 else
This defines the A, and B, matrix parameters, and we can write, letting vhr, denote the activation function (ReLU or Heaviside) applying to the s-th hidden MLP unit:
dMLP
5 Y
(Bi).. 11. (AA)).. +bb))
(47)
or equivalently
y
B (A Y. b))
(48)
matching the formulation of MLPs for our model of transformers (Equation 4).
Note that the hidden dimension the MLP the Limit Transformer now dMLP. which will be smaller than d. We thus pad the remaining rows/columns of A,, B,, and the remaining entries b with zeros.
partial order on sets value matrices For S, E P, we write 2: S to denote that
1. T2S
2. YI' E (1..... L}: ((V E SS=+'>1
3. VL' (I....,L) [(Vi E -T-8)
Intuitively, "T 2: S" says that "among the value matrices in T, the activation has already passed through all value matrices layer and below". For example:
(V V2, Va,ao, Vs, 22 (Va,n", Vs
(Vi, V2, Va.a", Vs.",) Z2 { [V4, m
(Vi Va, Vana, Vo Z1 (Va,"", Vo,
{ (V. V2 Va, V Za (Va,e,, Vs.wr
62

---

Published as a conference paper at ICLR 2025
Matrix Parameters: KT,,, Q1, We again define them implicitly in terms of regions; this can be realized using matrices K Qi. where all entries are 0 1. Importantly, sum only those entries where the "to-do-lists" S1 are empty, and the sets Ti. T2 only contain value matrices at layers S
v ) T V
Σ
Ta. (y)
(49)
v.w. 72200.72220
Matrix Parameters: U
The U matrix is translated as follows:
0 y ( = T',.,, (y, (
(50)
Positional Function
Define for I 1,.... and = 1,..., H, when isisjs N(T):
(i,(i, P KÝ,, Quaep
(51)
As T E On (1,55 only depends on
Bounding (Txx) First, we showed above that d's upper-bounded in R(T). Second, all param- eters are represented at precision bounded terms of RT)::: those parameters that are taken from product functions have precision I 4.p bits; those involving the SVDs of KT Q matrices also have bounded precision. Third, the no norm of all parameter vectors is bounded terms of R(T) by construction. Fourth, A is bounded in terms of R(T") as discussed above. The boundedness of the fifth term is immediate.
Summary
We have constructed Limit Transformer Too such that
Ro S (R(())
(52)
for some universal function F: R R, and
d K Qu.hP (1,
(53)
for the p., Ki,h, Qia parameters T; for each h. By assumption T. each Φr, is translation- invariant, We have also constructed p. with period A, so that Too satisfies PERIODIC.
F,4.3 PROVING LEMMA 52 (III): PROVING CORRECTNESS
In order conclude Lemma 52 remains establish the correctness of the translation; that is, T' = Too at length < (T). To do this, it suffices to show that both transformers provide the same next-token predictions for each i 1, N(T.:
0T Vi (L)
Ta. (1) U. y (L)
(54)
Informally, proving this requires showing that the attention logits and MLP activatiio in Txx match those in T; the result then follows from the linearity of To,u, and the way r... is defined for the vec-
tor parameters and how value matrices Ví move information. Formally, we prove the correctness of the translation inductively, by showing the following equalities. Recall (from Definition (3) that, when
set of value matrices, we write Ises for the product these matrices, ordered by layers, with the matrix associated with the lowest layer at the right. Then
{0,1....,L) L}, for any S,S,, E P for any > for any m 2 and for any w VZ, by induction over the lay-
Lemma 53 (Preservation of Products by Translation). For layer
ers 1:
63

---

Published as a conference paper at ICLR 2025
(A)
Preservation of Products with Vector Parumeters
Ts (v: ) w²
II SES
y
if'l' E {l,.... L}: [(V E E Preservation of Attention Logits (I)
+ >
(B)
Σ
Ts. A. ) 1o
v.w. SI.
w
II
S
K K.
Qu,
II s v)
9ES,
SES,
S US +
(C)
Preservation of Attention Logits (II)
(v.n(i,5)+
+
Σ
T. (v. Sa... DaT
(55)
0.00 T:2.0.22100
(y. (T K AK
(
(D)
Preservation of Attention Logits (III)
Σ
T.a. (Bm).s) Us TI Ta (1) 1
v.w. S.W.T:21S..T220 T22
BBm)
II
S
KE
II SESa
s
yj
!
SES,
(E)
Preservation of Attention Logits (IV)
Σ
I2s Tathh... ((Bn) (Bm)).s)
w,w, S T22iS,
T
II S
Qu,
II s (Bm)..
SES,
SES,
and analogous statements with the post-MLP activations y, y replaced by the pre-MLP activa- tions Y (1)
From (A), we in particular obtain the correctness of the translation by noting that next-token predic- tions replicated:
(L) = Tu.u U.!!"" v4 V.
(56)
Proof of Lemma 53 The formal proof proceeds by induction over I. It is conceptually straight- forward, consisting of expanding definitions and taking care of the special treatment positional encodings. We show it in considerable detail to build intuition. For the inductive base, at 0. where (0) a sum of a word embedding and a positional encoding, the claims are immediate from the definitions. For expository purposes, and for building intuition for the more complex inductive step. we show them in more detail. Starting from (for simplicity, we are taking the offset to zero here):
(0)
y Er, Pi (0)
(57)
y; = E,, + P:
64

---

Published as a conference paper at ICLR 2025
first, for (A), write
s Ex, + p::) = s Exi)) s (Pi)
30 A.,.E.. BS.w.P.n
w²
y;
LSES
proving case (A) of the inductive base. Second, for (B) and (C), write using the linearity of A Q
Σ
Ta + Di) Taakhh. (Ez, P:)
0,u, 21. To2o8a
Σ
Takhowon T...
wsw, T. 11 To2nSp
A...F.TT...h.... Ex,) F. 0,30 T12001
Σ
Σ
A...T.TT. Us. Ta Ex.))
0,00 212 T200.,
Σ
AS. Tah....
0. S..2Si.TT220
The only way satisfying T 2o S for T equal S, After plugging in the definitions, the sums collapse due to the indicator terms in the definition of the token and positional encodings, and we obtain after simplifying:
Sa. B.,
S.s.S S...
Sg..
+ a, Pyna 1s
By translationiivaaianne,, the second and third term are independent of the positional encod- ing arguments. By our choice of A at the beginning of the proof, the fourth term equals this is periodic in (i.j) with periodicity A. We can thus rewrite as
18 S.h.p..p Ls,
St. Eay
as, S. Er,
S. 18,
Applying the definition of a..., the above equals
- yT (y (0) (k.,(i,))
S U ()
- (0, (0) (IIses, 5) Qu,k (Tsess, S) (,,
S Sg / ()
This establishes cases (B) and (C) of the inductive base. The proof cases (D) and (E) in the inductive base is analogous.
For the inductive step, the intuition is that each activation y, linear combination of vector parameters, with different sets of value matrices acting on those:
Σ Σ Ao.iis
(58)
BEVOSET
SEE
where the coefficients determined by attention weights and the activations of MLP hidden units. Importantly, the attention weights and MLP activations turn out to be the same in the Limit Trans- former in the original transformer, provided prove that attention and MLPs faithfully
65

---

Published as a conference paper at ICLR 2025
simulated (which indeed follows from cases A and C of the inductive claim). Hence, the same decomposition is valid the Limit Transformer.
y = -
II SEES
S
(59)
BEVO SEP
with the same X.,i.I. coefficients in the original transformer. Then, case (A) of the inductive claim follows intuitively by the calculation:
11) w yi
Σ vEVO SEP
Σ
II SES
S
Σ vEVO SEP
Σ
II SES
S
0
Σ
II S
vEVO SEP
NES
w y;
(1)
which warranted provided that, when E Vo and w VI, have that TT (IsEs 3)
equals w (IIses S) v - this is ensured because the way the vector parameters and the value matrices VI, are defined. The same idea establishes cases (D-E). A similar, though somewhat more complex (due to the bilinear nature of attention) calculation establishes cases (B-C). Formalizing this reasoning essentially amounts inductively proving cases (A-E); it will not be necessary to keep track of an explicit decomposition using A., coefficients; rather, one can mechanically verify these conditions inductively by plugging in definitions and applying the inductive hypothesis.
Formally proving the inductive step consists in mechanically expanding definitions and applying the inductive hypothesis. First, (C) applied to layer / entails that the attention logits for attention heads operating in layer / match those of the original transformer. We start by establishing the inductive step for the pre-MLP activations Y Starting from:
H
11-1)
(LA)
VLNN
(1-1) 11-1)
y;
tg
==
(60)
H
y;
((.h)
V. 1g
show the inductive step first for (A) in the case of the pre-MLP activation y, For S satisfying Al' E {1...., [(Vr,N E S) = 1'
(61)
we consider
H
x(
s,
S,w
Vi
(1-1)
(L.))
Vinny (1-1)
h=
j=1
(1-1)
(t.b)
y 11-1)
I
yi
Di.j
SsuiVis
where ãiاة denotes attention weights. The claim here now follows from the inductive hypothesis for (A):
S
y
1)
(1h) bij
II
Vi.no, (1-1
j=l
JEES
=
II SES
S
(
66

---

Published as a conference paper at ICLR 2025
where the last step used (60). Next, consider (B) and (C). First, for (B), assuming T1 U T2 # 0, we first find using (60) and the linearity of A... and f (portions changed marked in blue):
Σ
Ta YY
S. T.k. (Y)
0,w, Ti
Σ
As A...F....kk.k....
y
aiw
(1.h')
Vi 11-1)
T.
Ss. T1. T.T.h.h
yj
U,hh")
VI. Yan!
(1-1)
(--1)
y.
Vj
n,w,
H
Σ
(1-1)
(1.1 aju
Vi (1-)
y:
Ti.2
h
w=1
H
Σ
(L,")) aiw
Vi. 11-1)
(1-1)
Vj
0,M. T1:T2 h"m w=1
H
Σ
(1,H')
As T.
Vi
kw
0,M0 TT.Ta 2 h
1==1
H
(1,1
S..sg Ta,
1==1
=1=1
Now the definition of VT, allows us to rewrite this as:
Σ
yi
(1-1)
Us. Tad.hh..
Vi
11-1)
w. 215 T2213
H
+
Σ
AS, Aaa.h.a
Y 1111)
(L.1') sw
y
0,30 NT T2
Σ
Σ
(L,N)
y (
11-1)
As)
TT.....TT
y
v.w. T1: S2 W
Σ
ΣΣ
(LA) a
y (1-1)
2:
-=
H Σ
(1-1)
Y
W=lw=
67

---

Published as a conference paper at ICLR 2025
In order to directly apply the inductive hypothesis, rearrange the summations:
Σ
(1-1)
(1-1)
y:
TI
yj
u,
To T221s
(1,N
Σ
yi
(-11)
Rlsu(V (.T.
Y
11-1)
w,w, 2:SI,.2220
(1,N)
Σ
(1-1)
(1-1)
yj
w,w,Ti S
(
Σ
(LA"
Σ
y
(1-1)
jw
Wm w=1
Ti
(1-1)
Ywu
Note that, above, S1, S2 are fixed and the sums over T1, Tz. We can rewrite the above
Σ
(1-1)
(1-1)
Aa....TT.d.......
yi
TT
H
(LA))
Σ
(1-1)
jm
T.
y
w=1
w.u. Ti2 T22--
1-1)
you
(1A)
Σ
(1-1
Vj
W=lw=l
y (1-1)
H Σ
(LK')
(1.b") ju
Σ
(1-1)
Y
w=1
R"=
w
v.w, Ti 772--SS 122:-18u(V,,.)
(-1))
DSau J.T. Ta
We are now ready to apply the inductive hypothesis: Directly plugging the inductive hypothesis for (B) into the second through fourth terms gives us:
Σ
Ast T.
y 11-1)
SSa Tal.h...
11-1)
S1.
T:2--12
T
T
(1,1')
11 -1yr
II
QEA
II S
V
Vi 11-1)
SES,
SES,
T
(1,h') (1-
yj
ViT
II
K,A,A Qui
II AEES
y
(1-1)
J ==1
SES
H
H
T
(L Exo
(a.)")
( 11 (11))TT
II S SES,
Q
II S
ViN-y (1-1)
1.6
#= w=1
68

---

Published as a conference paper at ICLR 2025
We now distinguish cases, for proving (B) and (C). The first one is that Si S2 = 0. In this case, by case (C) of the inductive hypothesis:
- a- D QuNy (1 (i.)
H
(L.))) ju (Ui
) K Qui V.ny
hv
===
(L.1') (1-1)
Vilh Ki,, QLAy
yj
H
H
Σ
(1
KI, Qu ViN (1-1)
h
m==1
wf=1
Now, applying (60
again, we rearrange to sums to obtain the conclusion
-x,"")
(i,j)
(62)
proving (upon rearranging) the inductive step for (C) in the case of y. In the second case, S U S₂ + 0: here, use case (B) of the inductive hypothesis instead rewrite
= -3y
II s SES
K R.
Qkih
II LEES
S
(v)
D
T
jiv
(1,h')
11 11)
II
KT
QUAN
II S
ViNyy-
SEE
SES,
T
(1,h')
y
(1
Vi
II SES,
S
Ki, Qthh
II .S88
S
(1-1)
T
(1,h')
(L,h")
y
1111)=
11
VT.
II
K.
Q1
II
s
610
#=1 w=1
# ur
SES,
SES,
Now, applying (60)
again, we rearrange to sums to obtain the conclusion
T
= OF
II
QK.Q
II SYO
Y 11)
(63)
SES,
SES,
This proves the inductive step for (B) in the case of Y We next address the inductive step for (D) the case of the pre-MLP activation:
Σ
AS..T..T.k....... Bmn)
T...,T. (Y,
0.00 Ti 2:S To2:8a
T
=(Bm)²
II SES,
s
K Qk.
II S ( SESS
By unfolding y using (60) and using the linearity of Q.s. T..Ta.k.h.naa the claim follows directly from the inductive hypothests for (D). The same reasoning applies to (E). Overall, we have proven the inductive step (A-E) for the pre activations y,(")
We now need to show that the inductive step also holds for the post-MLP activations. Recall that the MLP acts as
dxeLP
4 Y
11
(Bi di. (AA)),, + (bi)..
(64)
dMLP
1
Y 7 +
Bi)., t1.s (Ai)s, + (61)s
y
69

---

Published as a conference paper at ICLR 2025
The proof proceeds by expanding this equation and reducing the claim to the already-provee induc- tive step for pre-MLP activations (for handling the direct contribution from the pre-MLP activation), and cases (D) and (E) (for handling the contributions of the MLP units). First, note that, for each I s, by the case (A) of the inductive hypothesis and by the definition of b,.
V1. (XA)), + (bi).) = 11.. (X,)), + (Bi)..
(65)
We will abbreviate this number as Er,a, R. We now prove the case (A) of the inductive step for the post-MLP activation:
darp
Ts. (v: (1)
=I (Y, +
Σ s=1
(Bi).. -(,,,)
dAeLP
=., (x,
+
s s (Bi))..) El,s,
dACLP
=
II SES
Y
un"
II
(Bi) Et,,,
II S
(1)
w
y;
SES
(
To prove cases (B) and (C) for the post-MLP activations yi we now consider
Σ
y:
(1)
QS.. F...
(1)
0, D.0.T12:S..T22.6.
dMLP
Σ
As J.T.h.
Y (1)
Σ
E
(Bi)
T
dMeP
Y
E
(Bi).i
Σ
Y!! !1)
Us. T,k.
y(
dMLP
E
Σ
As Ta.
y:(1)
S.s. To. Ta.kh,
(Bi))..)
U.W. Ti 2:8,,72218
dMLP
Σ
As, A.T.
(Bi)..e
USy. Ta.. (())
#
dMoP
dACLP
Eus
Σ
AS..T.TT.k....... (Bi)..)
-=1
M. T2215,
P.S. T.T.k.h...
(Bi)..)
70

---

Published as a conference paper at ICLR 2025
We apply the inductive step for the pre-MLP activation in cases (D), and (E) rewrite the second and third term, and apply the definition of B, to rewrite the fourth term:
E
AS A.T.TT.TT.kkbbu..
Y
(1)
Us TI T.T.h.hh....
Y
T22
daco
T
Σ Blas : (Y."))T
II S
K Qu.h
II S
(B))..
SESI
SES
daLP
T
Σ B (Br)..
II SES,
K Qua
πI S
Y
SES;
dMPP
dMLP
B
E
(Bi),,
II
S) K Q M
()
SES,
SES2
In the case where S = S2 = 0. we obtain using case (C) of the inductive hypothesis for the pre-MLP activation:
-(Y,"1)
KT Qk.h Y, ox.n
dMeoo
Σ Eisss (Y:10) k. ( (Bi)s,
darz.
+ B (Bi) K X
darzp
dMLP
+
Σ E
t=1
Using 664 and the definition of Ei,,,s, this rewrites to
-y (3) KT QK du (i.5)
from which case (B) of the inductive hypothesis follows by rearranging. If instead S1 U * 0, the same reasoning leads to case (C) of the inductive hypothesis. Analogous reasoning establishes cases (D) and (E) for the pLPt-MLP activations. Overall, we have established the inductive step for cases (A-E) for the post-MLP activations.
G ADDITIONAL SUPPORTING RESULTS
G.1 REGULARIZER AT INITIALIZATION
Here, we provide evidence that the additional regularizer plausible initializations of parameters. Recall
8
bounded independently of N under
L
H N(T)
8
of KT Quap
(66)
Intuitively, and formalized in Proposition when independently initializing the positional en- codings Pt, their inner products as mediated through KT, Q1 will tend to be small. As long as the width grows linearly with N, the aggregate value of (8) will tend to be bounded independently of N. Note that (8) only includes products involving position 1, which due translation invariance for E θ, places bound on all products. As standard training does not enforce translation invari- ance of the products p KP, Qt.PPj. one may also be interested in variant that takes all pairs of
71

---

Published as a conference paper at ICLR 2025
positions into account, the extent that they can enter causal attention:
L H N(T)
ΣE p
( 2
(67)
N(T) 1=1
Here, the conclusion holds. We describe it formally, at the example of the second variant, in Proposition 54
Proposition 54. Assume d = ((N). Assume the entries of each P1.... PN E Rd and K Qi, E
Raxd (1 (1=11 1..... L; h = ,,..., H) are initialized ii.d. from NO, 2)) The number of layers L and heads H are constant with respect to N. Then
E
NE
E h= LSIIISN
K. QuAPH! O(1)
(68)
N
Proof. We begin by showing that the expectation of each term the sum is O(1/d) and hence the sum is bounded by a constant. There are two cases for the expectation of terms: (i) The first is i # when the vectors pt and pj are independent and the second = when pt and pj are dependent.
For this section, let K, Q denote the matrices K Qi for any fixed 1, h. Let Kij and Qi denote the entry of the corresponding matrices ith column and jth row. Let A = KTQ Iddx Note that the expectation of any entry A,
d E A.) = K Q₁ = E Σ
K 2 = =0
Further,
d
d-1 d
E[A = E K 21,n) E E
K2
22 2E
Σ
Σ
Kim Ki Qjml
1,
1=1
m=1 n=m++1
E
K 1.k Q7 do =
k=1
For products of
different
entries
Ar, Amn
note that E[A Am,)
E E d
Ed K.,, Qj Km,, 2n which is when * m or j # n.
For each term Ip. Ap,1? 12 we have
Elpp AQP, =B
P A., (Pf.))
u=1 u=1
d
P 4 )
1 2E Σ
Am.
since all terms of the form Elps. Pi. A. A Am. n..
Pi.n) are 0 due to independence of and p.
For i + j, we have
d
d
d
d
D
E
E
A m.
E.P = 2oo d
11
72

---

Published as a conference paper at ICLR 2025
For i = J, we have
E
Pi = E Σ
Pi un 1..1+ + E
A
P
4 u
Pi,
u=1
u=1 1/
=(330)) + (df - d)o <
Since d ((V) and each term is less than 3 have that the sum in Eg 68 is O(1).
G.2 EMPIRICAL LENGTH GENERALIZATION OF POSITIONAL FUNCTIONS
Here, we show empirically that, when directly fitting parameters so that a product p, K Qp; re- produces some function -) at smaller distances, it will length generalize when these are local or periodic, but under different conditions matching the role of local and periodic functions in our theory. Specifically, we show that they length-generalize well at large d when they are LOCAL: whereas, when d is smaller, length generalization works well when they are PERIODIC. Length generalization is poor functions that neither local nor periodic.
Experimental Setup We randomly initialize 200 position embeddings {p: E R4 <i< 201}, well query and key matrices, Q, K Rdxd We experiment with d (32, 256). We optimize the mean square error (MSE) between p. K Qp, and 6(:,-) on length of 50, and test on length (50, 100, 150). Concretely, during training, we sample random offsets from [0, 150] and take the sequence of Pi+o:-.. P50+t to compute the loss. When testing on length we compute the average loss over all offsets in [0, 200-n]. We ignore the loss on those entries where j < i to mimic causal masking. The o(.,-) use in experiments (except for the one combined from two o): only takes two values, when condition is false and 2 log 50 when condition true. We thus different condition to describe different ():,-). For example, following function:
j=i-c to denote the
j=i-c ((. = 0 elsc
2 log 50
(69)
where e css a constant number.
The embeddings and weight matrices are trained with Adam optimizer, using batch size of 64, learning rate of 1e-3, for 15k steps. Additionally, we add mean squared weights (i.e., squared Frobenius norm divided by number of elements) to the loss to mimic training regularizer, with coefficient of 0.01.
Results are in Figure 5 and 6 Note that in both figures, y axis is using logarithmic scale above 1.0 and stays linear scale below T.O. the last column of "combined" denotes functions that combine two functions as follows: & Φi + d2, where Φ1 j-i-c and Φ2 (i-j) =02 mod C₁.
G.3 BOUND FOR ENCODINGS NORM IN TERMS OF FUNCTION COMPLEXITY
Recall that our regularizer includes a penalty s on attention dot products. Here, we discuss conjecture:
Conjecture 55. The term (8)
be removed from the regularizer while maintaining (potentially weaker) length generalization guarantee for Limit Transformers.
To provide a heuristic argument for this, assume that for each upper bound on the input length, we have configuration of positional encodings and the matrix A, such that the following property holds: For any indices N <j>i>> 0, let
p. Ap, F(j i)
(70)
where F: N + R is function that maps to numbers representable in p-bit precision. The function F and the precision p chosen globally, across the different N's. Boundedness of R(T,.) across
73

---

Published as a conference paper at ICLR 2025
30'
R- de32
12
6B--] a modi) cx22
0=56=2
385
18-
186
188
10e
Lmngh
Length
lengh
B: 111--11- I-c:
05-55 C--25-55
#: Ci-ff - by mod di :d-256
0
331
331
12
Lenghh
Length
Length
Figure 5: Appendix G.2 MSE loss in fitting (length 50) and generalizing (higher lengths) func- tions -) with products p. K" Qp,, show local functions testing j i-c (leff,,,,, if j > i-c (center), periodic functions testing whether i-j = 02 (modc1) (right). We show result at small (top, d 32) and high (bottom, d 256) dimensionality. Local functions length-generalize well when dimensionality is high (bottom left, bottom center); generalization is more successful with functions concentrated on few pairs (bottom left is nonzero at only one value of j- i; bottom center is nonzero at different values of j v). Periodic functions length-generalize well when dimensionality is low (top right). The results match the distinct roles played by local and periodic functions in our theo- retical constructions: Periodic functions are mediated by bounded-rank products (Lemma 48) local functions are mediated by the products p" K" Qp.
1/ geimee 1lm32
combrodl: :l=32
331
332
135
m-00 mam
pit reslt
p2 Drpeet moo
leigh
lengh
seggh
4- is
5-256
combined 5-256
640
10 jwe mod
42'
Figure 6: Appennix G.2
MSE loss in fitting (length = 50) and generalizing (higher lengths) func-
tions <b(;))) with products p K" Qp: We show functions that are neither local nor periodic, which tests if j < i - e (left), if i j is prime number (center), and a function created by adding a local and a periodic function (right). We show result at small (top, 32) and high (bottom, d = 256) dimensionality. Compared with results in Figure 5| we can see that such functions, neither local nor periodic, ength-generraize poorly.
74

---

Published as a conference paper at ICLR 2025
entails ||p:ll2. |||||
C. for C global constant. We also know that supzeN [F(x)
We conjecture that one can use these assumptions, and Lemma (56 to prove that cannot be "too conjecture that F will be ultimately periodic: when z exceeds some threshold, F(x + A) = F(x) for some period A. For, if F is not ultimately periodic, we hope to construct matrix G whose nuclear norm can be made arbitrarily large, large to give a superconstant lower bound on |||| which is a contradiction. First note that Lemma 56 even holds if G Y" AX where X Y are different matrices with n unit-norm columns. That is, we can consider a matrix G5j pI, APy, where we conjecture that one can choose 2....., Zn and y1..... yn, to give an arbitrarily large lower bound on || under the assumption that F is not ultimately periodic. Here, it is important that F maps to fixed-precision output; otherwise, one could get functions that have irrational periods and thus are not periodic when restricted to N.
complicated". Specifically,
Lemma 56. Let ; Jn E IRd be vectors with ||ll112 = 1, and let RRddd arbitrary. Let G' E Rax= such that Gig xu Axz. Then
|G|.
||||| 2
(71)
where ||A|| denotes the spectral norm.
Proof. First, note that for any matrix B UEV, we have
|B| tr(2) " =tr(Br
(72)
where VT has each singular value bounded by (in fact, it's orthogonal). In other words, |B]| = tr(BM) where M is orthogonal matrix.
For any two real-valued and possibly non-square matrices, have
tr(A" < |||
(73)
and by submultiplicativityy have
AB r & ||||||| B|
(74)
Using Eq. 72 and the above two properties, it follows that,
tr(x AXM) = tr & A |
||AX|| || S
||
G.4 POSITIONAL ABILITIES NOPE VS APE
A recent study by Kazemnejad et al. (224)) found NoPE to work better than APE at length gener- alization and to theoretically simulat late positional information an apparent contrast to our findings, which find APE to be more powerful than NoPE both theoretically and empirically (Figure 1). There are a few important aspects that resolve this apparent contradiction.
1. The APE setting in Kazemnejad et al. 2024 is different from ours, as they used fixed sinu- soidal functions (Vaswani et al. 2017) whereas follow Zhou al. (2024a) in examining the potentially more expressive case of arbitrary learnable positional encodings.
2. Kazemnejad et al. 2024) trained APE transformers only set of positions, so that the positional encodings at higher positions did not appear during training. This inherently puts APE at potential disadvantage compared to setting, where (in line both with Zhou et al. (2024a) and standard LLM training) all positional encodings appear during training.
initial segment of the full
75

---

Published as a conference paper at ICLR 2025
3. In support of their empirical findings, Kazemnejad et al. (2024) also showed theoretically that NoPE transformers can simulate positional information. Specifically, they found (their Theorem 1) that NoPE transformers can compute activation with value 1/t at position i, e.g. by attending uniformly and reading out the contribution coming from a BOS token. Importantly, this is weaker than the ways in which APE transformers can information. For instance, distinguishing close-by positions, say t 1 and f t- 2. in such encoding requires rapidly increasing parameter values arbitrarily close to O. In this sense, even a simple task such as an induction head, which requires attention from to f-1, requires parameter norms rapidly increasing with the input length[ not allowed under our inference procedure. In our theoretical framework, NoPE is not predicted to length-genent geath-eenerlizeeeee as well as APE on such a task. Indeed, empirically, we find NoPE transformers not to perform well on the induction head task, and variety other tasks not expressible in C-RASP []] (dotted lines in Figure despite extensive hyperparameter search (Figure D and Section G.7
positional
0o, as the values get
We further note that Kazemnejad et al. (2024) also report strong performance for NoPE on a copying task (their Figure 3), in apparent contradiction to our finding that COPY is hard even for APE. However, note COPY in [Kazemnejad et al. (2024) had three variants: The first two just asked the model to replicate the number of tokens but not their identities, task well in C-RASP(0), and indeed NoPE worked well (their Figure F.4). Their third variant matched our COPY task and is not in AAAPPppeiooiccooceeeeee
neither NoPE nor APE generalize to 2x training length (their Figure F.4), in line with both our empirical and theoretical findings.
G.5 CONCEPTUAL RELATION TO SOLOMONOFF INDUCTION
standard approach to studying learning in algorithmic information theory, specifically Solomonoff Induction (Li & Vitányi 2008), does not specifically ask for identifying the correct function some point, but rather aims to bound the overall number mistakes. In the case of Solomonoff Induction, computability of the underlying function guarantees that this number is finite. Here, show that our length generalization guarantee can also be viewed as bounding the number of mistakes made by the inference procedure:
Definition 57. When applying the Inference Procedure from Definition oo a target function we define the Number of Errors as the summed numbers of inputs on which Tn makes mistake:
ErrorCount(Ti, (2,.,T,.....
Σ
(T,
(75)
== =
Then show the following variant of Theorem 7
Theorem 58. Let E F(E). Then the following are equivalent:
1. f is expressible by Limit Transformer satisfying PERIODIC and LOCAL.
2. (Guaranteed Length Generalization) Applying the Inference Procedure from Defini- tion generates sequence Tı, Ti,..... with S1pm=1,223... R(T,)) and
Proof. In view of Theorem 7 it suffices to note that the following two conditions are equivalent:
1. ErrorCount(Ti, .2,...)
2. There is some No such that, for all m > No. Tm matches on all inputs of any length k < m.
Kazemnejad et al. 2004) use an MLP to convert 1/t to Such an MLP would need an increasing num- ber of hidden units the maximum context size grows, hence, || Bl]r growing with n. Hence, R( + no by Definition 5 Such construction is thus not predicted to length-generalize under our theoret- ical framework.
76

---

Published as a conference paper at ICLR 2025
G.6 THE ROLE OF TRANSLATION INVARIANCE
The hypothesis class (Definition assumes that product functions involving positional encodings are translation invariant: That is, every product function involving exactly one positional encoding is constant across positions, and for every 1 & i, + A. j + A n,
p. M. M.P; Mi
MaPj+A
(76)
whenever M1... Mr is product of parameter matrices linking the input layer, such as K Q1.h 3. Vi K2, Q3,v' Vi,a", and similar.
Translation invariance formalizes the idea that the algorithm employed by the transformer is the same independently of the offset. However, it is not explicitly enforced in standard training. Here, justify this assumption follows:
1. We theoretically show that translation invariance is beneficial for length generalization, by describing a sequence of transformers T, that violate and that fail length generalize on simple induction head task (Section (Section(..6.))
2. We empirically show that trained transformers often exhibit translation invariance, both in transformers that we trained from scratch on algorithmic problems, and GPT-2 (Sec- tion ....2....2..
We conjecture that On the algorithmic problems, our theoretical and experimental setups assume that each training example presented with random offset; hence, the target function is translation-invarint. In the case of language modeling, the task is also approximately translation-invariant because ex- cept for the beginning of document the structure of language (c.g.. its grammar) is likely to be largely independent of absolute position. Hence, we expect that the behavior of the model will be approximately canslation-invariant, Thus, with an offset-invariant target function, we conjec- ture that standard training implicitly favors translation-invariance of the transformer's 's algorithm. Understanding this theoretically. in theoretical account of SGD dynamics and generalization on multi-layer transformers, is an interesting problem for future research.
happens when the training signal itself is offset-invariant:
G.6.1 NON-OFFSET INVARIANT TRANSFORMERS FAILING TO LENGTH- LENGTH-GENERAN GENERALIZE
Here, theoretically show simple induction head task how offset invariance is beneficial for length generalization. We construct sequence (Ta), )n of transformers violating offset invariance that each compute the induction head task lengths < n2/2, but fail to compute
length
Proposition 59. There is a function E F and a sequence To of transformers violating offset- invariance, where n operates at lengths S. n, each product function p: K QtpP; is local for i.
T 2 where sup,, R(Tx) < oo and each Tn matches f at lengths S n/2, but no Ta matches f at length n.
This is important contrast the panslation-invariaan setup, where such a sequence Ta where (i) sup,, R(T.) < oo and (ii) all p K" Qp, are local for single < oo, will necessarily match f at length n when is large. This property used in showing our length generalization guarantee. This property is not available when translation invariance is violated, exemplifying that offset invariance theoretically beneficial for length generalization.
Proof. We take to compute a simple induction head task (Section There is simple cansllaiio-invariian construction: In Layer each position collects the token appearing at the previous condition; in Layer 2, each position j attends to previous positions that had followed the token also appearing at j. This construction performs correctly across input lengths, reflecting length generalization.
Here, we describe transformer performing this task while violating translation invariance, and failing to
We use two heads, one performing "correctly" at smaller indices; the other one performing "correctly" at large indices. We note that this version is more complex and not minimal; we conjecture that translation-invariant solutions will generally tend to be simpler for
77

---

Published as a conference paper at ICLR 2025
C-RASP-expressible expressible problems. We consider an alphabet Σ {SOS, (50S,00,.... .....,, ok). For each define a transformer Tn as follows. We define the encodings:
C-RASP
0
0
0 R
R
0
0 E R
0 E R
0
esos
0 e R
Ca,
E R
P
0
0 R
E R
0 R
0 E IR"
0 E IR'
E/ E IR
where ej E R is the i-th one-hot vector. We define p; and K 1,hs Q1,h by:
[2
15j <
K4,
120
else
[20 1 15i5! 3
T K 11,201.P3 Q12P)
120
elsc
This is not translation-invartt Informally, one of the two heads takes the role of copying from the preceding position for smaller indices; the other one takes for large indices. We set
e
Vi,
E1
e,
V1,2
ei
Now, given input of the form 21
Σ* (where x
8), and offset o, we have
Cx
ex
ez
exp-1
n ifto<
6z;-1
3n
Cxa-2
3n
y,
<
sitos
if <itosn
6zi-2
4
6zi-1
4
exi-1
4
(
0
0
Csto
eito
Cito
Then, we set K2,1 Q2,1 and 22,2 to satisfy:
10
x; = Soj+00 3n
1 (y) (1 (11
Kr 2.1 12
0
else
0 else
( 2.2
22
10
I =
$tj + 3n
(y (2) = (21)))2
0
elsc
0 else
The value matrices are given (h 1, 2):
E
0
V2,A
(77)
C:
78

---

Published as a conference paper at ICLR 2025
By design, sup,, (TT.)) <
Due to the design of the token embeddings, attention to the SOS token contributes a zero output. Hence, query position j. the first head provides the output
exp (20
24 = 8 else
3n +
10
(y: = (0
else
Σ
V2,
Normalization
20
i = 1; + < In 4
10
Ex Ex₁ i + <
3n
exp
10
Ex; = Exgr + 0
in
0
else
Σ
V2,1,, (2)
Normalization
i=1+,,...
whereas the second head provides the output:
{00
10 3; = $
- o
3n
(v.
(20
exp
else
0
else
V2,11 (2)
Normalization
1=
20
= 1;j + 3n
10
Ex E z
exp
10
6z ez
0
else
V2,13 (2)
Normalization
n. this simplifies as follows: f 3r the first head's contribution is dominated by SOS (which leads to zero value vector), and overall near-zero contribution. The second head contributes the frequencies of symbols appearing immediately after prior occurrences of zz (10). On the other hand, if j + o 2 the reverse situation holds; the second head makes near-zero contribution, and the first head contributes (10). Hence, T, computes (IO) when the input length is 3
If the input length is I 2.
2
However, for longer inputs, this does not hold any more: if, say, == and j 3r, the second head additionally has contributions counting, at positions where i J. how often symbol appeared two positions after a symbol matching zy. Hence, Tn performs correctly at lengths I 2. but not at longer lengths.
G.6.2 TRANSLATION-INVARIANGC IN TRAINED TRANSFORMERS
Here, we provide empirical evidence that translation invariance, even though it is not explicitly enforced standard training, may be upproximately satisfied in trained transformers. In this section, we aim to check, empirically, how often or how much the product
p KT 1.8 Qt.PP
(78)
is ierislationiivvaiinn as function of (i,j). We conduct experiments for both models trained on algorithmic problems and a transformer language model trained on real-world data.
Transformers trained on algorithmic problems We select five small transformers which gen- eralize well on algorithmic tasks. They are trained on BINARY MAJORITY, BINARY MAJOR- ITY INTERLEAVE, MAJORITY, SORT, and COPY UNIQUE (defined in Section E.2. For
given head h). we assemble each product p. KT, QL.P, into a matrix M == PT Q KI.PP e
Raxn [5
Then such product is
if and only if the entries are constant along
Our experiments use standard transformer implementation including layer norm, whereas our theoretical analysis disregards layer (see Appendix [.3) Layer norm can in principle have nontrivial impact on
79

---

Published as a conference paper at ICLR 2025
each sub-diagona 16
P S
(79)
Hence, quantified the deviance from translation-invariann by calculating the offset variance / the average variance along each sub- dibgona,,,,,, as follows:
N --1
Diag.
((-o)
(80)
N
N-1 (M. - Diag
Varoffact
Σ
Σ 20 ==0
(81)
N(N +1)
We calculate the f for each head these models, and show histogram of the values across heads in Figure Most of the heads have very small variance, and single head across these models has variance around 8.
We next investigated the behavior of these heads in greater detail (Figure ( Figure [8] provides examples for the first two bins in Figure The head in (a) shows entirely uniform pattern, translation Innraition-nvvriiant by definition. More interestingly, the head (b), from the transformer trained on BINARY MAJORITY INTER- LEAVE, shows a perfectly periodic pattern reflecting the parity j
12-
=
i even j i odd
p: K QP
(82)
1.5
Intuitively, this pattern allows the head to specifically attend to po- sitions at an even distance from the query position, which is impor- tant for solving BINARY MAJORITY INTERLEAVE. As it only depends on j i, this satisfies (79) and the pattern is translation- invariant, in accordance with hypothesis class in Definition 4 Finally, in Figure we study the single head which has Var Subfigure (a) shows the overall pattern of PT KI,, It is not invariinnt but still shows similarity to a compara- ble cranslationiivvaiian pattern in (b): P.K Qp, is large when order to
Figure 7: Product functions across five small transformers trained on algorithmic tasks. Histogram of heads by their offset variance measured by Varoffset (Eq. [8]) for all heads from five small trans- formers trained on algorith- mic problems. Most heads have very low Offset Vari- ance; we investigate these in Figure 8 One head across the five models has a higher vari- ance; investigate it in Fig- ure
"PK"Qp,
j - is small or very large, and small in between. understand the variability of the contributions that inner products Qp, make to attention weights across different offsets, we measure the variance of post-softmax weights across context win- dows. Specifically, given a window size w < N, we apply soft- [.ooou Qi,,, PI..i together with causal masking. where o S N w is the offset. We denote the post-softmax matrix when offset is o as ( Subfigure (c) shows this matrix at dif- ferent offsets Throughout, the softmax output is focused on the immediately preceding position:
p. "TQP;
max to PT
2 0.8 i-1
(M )13
(83)
0.2 else
the attention logit dot products. We accounted for this, by fixing the variance term in layer norm as its average value across a big amount of imput data (around 240k tokens small transformers and 400k tokens for GPT-2), thus making a linear operation. Effectively, we are thus able to account for layer norm by applying it as a linear operation to the columns of P.
Due causal masking, super-diagonal entries are irrelevant, see Definition
IIn the asymptotic regime of - oo, our Inference Procedure prefers transformers where product functions unbounded distances. Such periodic relations
o K" Qp, local, and thus cannot be periodic instead, asymptotically, predicted to be covered by product functions additionally involving components whose rank is penalized by R(T,),, such as p K' QVp,- Our theory applies in the asymptotic limit, and thus predicts that as + oo (and thus d + oc), this periodic pattern might instead be taken over by such products. An extension of our theory that accounts for training dynamics, beyond idealized inference pracedure, may he able predict in which settings which kind of product will represent periodic relations.
80

---

Published as a conference paper at ICLR 2025
20
12
10.00
-0.75
140
-10
-1.25
key
(b)
Figure Product functions across five small transformers trained on algorithmic tasks. (a) pd Qf, Kr, P of head whose variance 0.001 (Figure 7 a). (b) PT Ki,, of head whose variance is 0.098 (second bin in Figure 7 (a)). This head represents an almost perfectly periodic pattern, depending only on the parity of j - All heads with Offset Variance close to look quali- tatively like (a) or (b). We investigate the higher-variance head in Figure
Thus, the product function makes an approximately translation inntaatiooninvariantt contribution to attention weights. Overall, the transformers trained algorithmic problems show approximate translation- invariance even though this not enforced as part of standard initialization or training.
Results on an LM: GPT-2 Small We conduct the same calculation on GPT-2 Small (Radford et al. 2019). lan- guage model with 12 layers, and 12 heads per layer, which has served a common object of study in the mechanistic analysis of language models (Conmy et al. 2023). The results are shown in Tigure[T0pa ao] Again, there are heads producing near-constant products, and heads producing focus positions i with small dis- tance i. In addition to products of the form p, KT Qp,, also inspected more complex products including value matrices finding these to generally be close to zero and thus also translation-invarian.. Overall, have found product functions in GPT-2 Small to display approxi- mately offset-invariant behavior, again even though this is not enforced in training or initialization.
142
385
43
140
Figure 10: Product Functions in GPT- 2 Small: Histograms of Offset Variance measured. Heads with variance close have approximately uniform values (Figure [Tp). Heads with higher vari- ances are shown in Figure [1 (b-d).
G.7 COMPARING
APE AND NOPE ON INDUCTION HEAD TASKS
We further conduct more experiments comparing the gen- cralization ability of transformers with APE and NoPE. We have already found that APE performs better NoPE at a variety task that are not expressible in C-RASP(0), such as COPY UNIQUE (Figure l}. Here, we further bol- ster these results by (i) considering parametric family of further such tasks, and (ii) conducting much broader hyperparameter search for NoPE.
2, t 3 respectively. Here, " means the problem is naturally solved with an attention pattern where each token attends to the c-th last previous token. The t problem is identical to the COPY UNIQUE task we described before; asks the model to copy string in which each token appears at most once (hence, "UNIQUE"), and is naturally solved using an induction head circuit (Section 4.1 The t 22
We introduce 3 problems, and refer them COPY UNIQUE t 1. t
G&GPT-2 Small uses additional output matrices, e.g. OL V.a. corresponding to the value matrices in thcoretical analysis.
81

---

Published as a conference paper at ICLR 2025
(a)
(b)
18-
kiy
Figure 9: Head 0,0 in a small transformer trained for COPY UNIQUE. This the head whose variance is 8.39 (the single head in the largest bin in Figure 7. (a) pd Qf Kt,,P Values are high when i is small very large, and low in between. (b) For comparison, but perfectly translation-invarian
show similar matrix. We replace values pd Q. KI,PP with their average value along the diagonal. The pattern qualitatively similar to (a), highlighting how (a) similar to though does not fully satisfy wransltton-iivariinne matrices (o), where o = 0, 40, 80, 120. 160 respectively, and at context window w = 50. Across offsets, the largest contribution at position
(c) Heatmaps showing the post-softmax
immediately preceding position / 1- 1; that is, the entries of the post-sofimax matrix (o) largely determined by the relative distance j-i. Hence, while the overall function is not exactly vranslation-invariin the resulting attention behavior is approximately offset- indsee-indeeendent, and implements attention to the immediately preceding position.
82

---

Published as a conference paper at ICLR 2025
(a)
(b)
(c)
(d)
(e)
0
100
200
100
300
50
129
24
35
0 300
400
20
40
150
Figure 11: Product functions in GPT-2 small. Heatmaps showing the product PT PT K P of heads in different bins in Figure I0 (a) A head whose Offset Variance is 0.6. The pattern close to uniform, making it trivially translation invariant. (b-d) Heads with Offset Variances 66.0 (b), 87.9
(c), 142.1 (d). These heads (b-d) produce high products at small distances, and distances 300. The first aspect is exactly cranslatio-invvariant;; the second one is approximately
comsslation-nvvaiinn
in the middle of the range, though not when closer to the boundaries. (e) Heatmaps showing the post- softmax matrices (0)) for Head 0,3, the head with largest variance in Figure 10] where 0. 100, 200, 300, 400 respectively, and window size w 128. With the exception of positions very close to the beginning (o = 0), the weights from query position are focused on key positions with small j i (note the green/yellow diagonal). Note that the green/yellow diagonal is faint as it is spread over multiple small distances j - i, but is consistently present and of consistent width. Hence, the contribution of p, K QP, to attention patterns is largely independent of the offset here, even in the head with the numerically largest Offset Variance.
83

---

Published as a conference paper at ICLR 2025
APE
NoPE
S 50
[51, 100]
[101, 150]
S 50
[51, 100]
[101. 150]
t-1
1.000
1.000
0.986
1.000
0.770
0.044
1-2 1,000
1.000
0.977
0.999
0.232
0.000
1-3
1.000
1.000
0.990
1.000
0.116
0.000
Table 8: Experimental results for transformer with APE and NoPE, on the three problems we de- fined. The models trained on data where LENS 50, and tested all three length ranges. Accu- racy is averaged over 5 successful runs (accuracy on LEN Σ 50 is greater than 0.99). We find the set of hyperparameters that generalizes best in each case, shown Table I0
APE
NoPE
128
[129, 256]
[257, 384]
128
[129, 256]
[257, 384]
1-1
1,000
1.000
0.989
1.000
0.602
0.000
1-2
1.000
1,000
0,998
1.000
0.241
0,000
1-3
1.000
1.000
0.997
0.997
0.058
0.000
Table 9: Experimental results for transformer with APE and NoPE, the three problems we de- fined. The models are trained on data where LENS 128, and tested on three length ranges. Accuracy is averaged over 5 successful runs (accuracy on LEN < 128 is greater than 0.99). We find the set of hyperparameters that generalizes best each case, shown in Table
problem consists inputs such as the problem is tasked with copying every second token from the input, which can be naturally solved using attention from position to position 2. Finally, the 3 problem consists of inputs such EOS
808
23
SEP
EOS
That is,
as SOS
14 23 6
18 SEP
14
In general, for and then continues with k unique tokens, where & E Z+ is a positive integer, finally the output sequence after SEP, which consists of every token the input sequence. We introduce the extra special token # so that the task is easily solved using induction head-like construction attending from position t to position
problem, each input sequence starts with SOSand c c- special tokens #,
c. The model trained to output the tokens after SEP. In these problems, LEN (recall Section E.2. refers to the length of the portion between SOSand SEP. The minimum LEN is bmin 2c I. The total vocabulary size of tokens except for special tokens is equal the maximum number of unique tokens needed, i.e., 150.
As before, the models are trained on sequences of LEN Σ 50, and we optimize hyperparameters for accuracy lengths [51, 100] For APE transformers, we fixed the architecture to have layers and head per layer, and the searching space is: learning rate = {0.001, 0.0001}, model dimension = search in a much larger space: number of layers = {2. 3. 4, 5J. number of heads = {1, 2, 4J, learning rate {0.001, 0,0001 model dimension [64. 256. 512), dropout rate = {0. 0.1}. Other hyperparameters are fixed and same as before; the attention dropout is still 0. We sweep all hyperparameter combinations and select the combination with highest accuracy on on [51, 100), shown in Table 10 The selected combination is then used to train 5 models with different random seeds. The average accuracy the test set (different from before, each now 5,000 examples, more than before) is shown Table g We can that, even though model according to accuracy on on [51, 100). APE's performance still far stronger than NoPE across the board. We also change the length range, that is, train model on sequences of LEN < 128, and we optimize hyperparameters for accuracy on lengths [129, 256], and test the model's performance (257,384] as well the previous two ranges. Results are shown in Table We see that, again, APE's performance is superior than NoPE. These problems are easily expressed in C-RASP(periodic local] but not C-RASP(0), and our theory thus predicts length generalization for APE but not NoPE, in line with the empirical results.
(64, 256, 512), dropout rate {0, 0.1). For NoPE transformers,
search in much larger space for NoPE and select the most generalizable
84

---

Published as a conference paper at ICLR 2025
APE
NoPE
Model Arch
LR
Dropout
Model Arch
LR
Dropout
[-1
2 layer;
head; 64 dim
le-3
0.1
5 layer; head; 512 dim
le-3
0.1
t-2 layer; 1 head; 256 dim
le-4
0.1
5 layer; 4 head; 256 dim
le-3
0.1
t-3
layer; 1 head; 256 dim
1e-3
0.1
5 layer; head; 256 dim
1e-3
Table 10: The best configuration of hyperparameters stands for fixed hyperparameter. Because we know 2 layers with head can solve these problems when using APE, do not perform further search there. On the other hand, for NoPE, we perform hyperparameter search over larger space.
found for each in Table Gray text
APE
NoPE
Model Arch
LR
Dropout
Model Arch
LR
Dropout
t-1
2 layer; head; 64 dim
lc-3
0.1
5 layer; head; 512 dim
le-3
0.1
t-2
layer; 1 head; 256 dim
le-3
0.1
5 layer; 2 head; 512 dim
le-3
0.1
t-3
layer; head; 256 dim
le-3
0.1
5 layer; head; 512 dim
1e-3
0.1
Table 11: The best configuration of hyperparameters we found for each case in 9
85


Reviews:
[{"review_id": "1ehrSNl582", "reviewer": "Reviewer_Gpiw", "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.", "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?\n* 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?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n* It's encouraging to see that, under certain conditions (as shown in Theorem 7), they identify cases where length generalization is achievable.\n* 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.\n* The practical impact of this paper feels somewhat limited. It would be valuable if the authors could identify practical applications that leverage their findings.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oq3Jzp08SY", "reviewer": "Reviewer_Vn9i", "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.", "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?\n\n[2] Kazemnejad, Amirhossein, et al. \"The impact of positional encoding on length generalization in transformers.\"", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "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.\n- The FAQ section in the appendix effectively conveys the paper's intuition and enhances the reader’s understanding.\n- Overall, the paper is well-structured and provides a detailed analysis to present their findings.\n\n[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.\n\n- The scope of the paper is limited to algorithmic tasks and does not cover length generalization problems in natural language processing tasks.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P3W3FtWGm4", "reviewer": "Reviewer_6ZTg", "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.", "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? \n2. 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?\n\n[1] The Impact of Positional Encoding on Length Generalization in Transformers\nAmirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, Siva Reddy", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n2. 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.\n3. 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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8x83XrtdWm", "reviewer": "Reviewer_odFA", "summary": "**Update after rebuttal:**\nThe 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.\n\n---\n\nThis 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).", "questions": "**Improvements:**\n(I consider all of them optional suggestions, not strict requirements)\n 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).\n2. 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.\n3. 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.\n\n**Minor questions**\n\n1. 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.\n2. 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?\n3. What is the relation of Theorem 7 to standard learnability / language identifiability results (language identifiability is generally not possible from positive examples only)?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n* 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.\n* 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.\n* 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.\n* 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).\n\n**Verdict:**\nOverall 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PLKezvI7D2", "reviewer": "Reviewer_H3pw", "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. \n\nThe 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.", "questions": "Please see weakness section, where I list both the weaknesses and questions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "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. \n2. 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.\n3. 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. \n\n1. **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. \nThe 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\nTheorem 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). \n\n2. **About invariance to offsets and regularization** \n     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.  \n     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. \n  Since there is quite some gap between the theory and expmts, what do you think is the explanation for this gap? \n\n3. **Regarding the definition of limit transformers**\n     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. \n\n   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. \n\n   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? \n\n \n4. **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. \n\n5. **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?\n\n6. **On the regularizer in definition 5** \n    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. \n\n   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? \n\n7. **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? \n\n8. **Minor remark on line 326/327** Shouldn't the Q_a in the RHS be Q_a(j) and not Q_a(i)?\n\n9. **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. \n\n10. 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?\n\n11. 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?\n\n\n12. **Concerns on the proof of Lemma 17**:  \n    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?\n\n      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).\n\n     c) In line 995, you say that lim D_v_i(v_i) is D_0. Why does this limit exist? \n\n     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. \n\n      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?\n\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. 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? \n\n      g) I do not follow the inequality in line 1044?  \n\n      h) In line 1049-1052, you say that set of functions traversed becomes stationary, what do u precisely mean here? \n\n13. 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?\n\n\n14. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)