Quantitative Bounds for Length Generalization in Transformers
Authors: Zachary Izzo
Eshaan Nichani
Jason D. Lee
Venue: ICLR 2026 Oral (2026)
Keywords: transformers
theory
length generalization
Primary area: learning theory
TL;DR: We provide an upper bound on the length of training sequences required for a transformer to generalize to sequences of arbitrary lengths.

Abstract: We study the problem of length generalization (LG) in transformers: the ability of a model trained on shorter sequences to maintain performance when evaluated on much longer, previously unseen inputs. Prior work by Huang et al. (2024) established that transformers eventually achieve length generalization once the training sequence length exceeds some finite threshold, but left open the question of how large it must be. In this work, we provide the first quantitative bounds on the required training length for length generalization to occur.
Motivated by previous empirical and theoretical work, we analyze LG in several distinct problem settings: $\ell_\infty$ error control vs. average error control over an input distribution, infinite-precision softmax attention vs. finite-precision attention (which reduces to an argmax) in the transformer, as well as for one- or two-layer transformers. In all scenarios, we prove that LG occurs when the internal behavior of the transformer on longer sequences can be ``simulated'' by its behavior on shorter sequences seen during training. Our bounds give qualitative estimates for the required length of training data required for a transformer to generalize, and we verify these insights empirically. These results sharpen our theoretical understanding of the mechanisms underlying extrapolation in transformers, and formalize the intuition that richer training data is required for generalization on more complex tasks.

QUANTITATIVE BOUNDS FOR LENGTH GENERALIZATION IN TRANSFORMERS
Zachary Izzo
Eshaan Nichani
Jason D. Lee
NEC Labs America
Princeton University
Princeton University
zle i izzzl gma com
eshni chêpri ceh@prinneton. nceton. edu
jasondl ee 8808gmaall com
ABSTRACT
We study the problem of length generalization (LG) in transformers: the ability of a model trained on shorter sequences to maintain performance when evaluated on much longer, previously unseen inputs. Prior work by Huang et al. (2025) established that transformers eventually achieve length generalization once the training sequence length exceeds some finite threshold, but left open the question of how large it must be. In this work, we provide the first quantitative bounds on the required training length for length generalization to occur. Motivated by previous empirical and theoretical work, we analyze LG in several distinct problem settings: foo eπror control vs. average error control over an input distribution, infinite-precision softmax attention vs. finite- snite-precision attention (which reduces to argmax) in the transformer, as well as for one- or two-layer transformers. In all scenarios, we prove that LG occurs when the internal behavior of the transformer on longer sequences can be "simulated" by its behavior shorter sequences seen during training. Our bounds give qualitative estimates for the required length training data required for transformer to generalize, and verify these insights empirically. These results sharpen our theoretical understanding of the mechanisms underlying extrapolation in transformers, and formalize the intuition that richer training data is required for generalization on more complex tasks.
INTRODUCTION
An important problem in the training of large language models (LLMs) is length generalization (LG), which is the ability of a model to generalize to input sequences longer than those encountered during training. Prior works have studied the ability of transformers to length generalize on simple testbed tasks (Anil et al. 2022 Kazemnejad et al. (023). yet the success of LG varies widely from task to task. Recent theoretical work has thus sought to characterize which tasks admit LG. In particular, Zhou et al. (2023) introduced the RASP-L conjecture, which states that transformers can length generalize on tasks which are expressible by "simple" RASP-L program (a variant of the RASP language introduced in Weiss et al. (02T)). Huang et al. (2025) later formalized and partially proved this conjecture, showing that tasks expressible by a limiting object called a "limit transformer." which includes tasks expressible by C-RASP program (Yang & Chiang 2024). admit LG at some finite training length. These results, however, are asymptotic nature and rely on "identification in the limit" (Gold 1967 Angluin 1980) style arguments, where the inference procedure can eventually rule out all hypotheses except for the ground truth. In particular, for fixed task f on which LG is possible, it is not specified what the minimum training length is for LG to occur.
Our goal in this paper is to characterize how long training sequences need to be in order for a transformer to generalize to sequences of arbitrary length. Specifically, we adopt the limit transformer formulation from Huang et al.] (2025), and aim to provide quantitative bounds on the minimum N such that two limit transformers f.9 which agree on inputs of length < N approximately agree on inputs of arbitrary length.
We study this question in two distinct regimes. In Section we consider limit transformers operating at finite- precieprecision, which matches the setting of Huang et al. (025)) This results in a hard attention
Equul contribution, order determined by coin flip.

---

pattern for sequences of a certain length. Our main results that for one-layer limit transformers, for both worst-case error control (Theorem[4.) 4.1) and average error control over a distribution (Theo- rem 4.2) the minimum such N scales monotonically with the parameter norms of the transformer, the positional embedding periodicity A, "locality" parameter т, token vocabulary size [X], and inverse emror e- In Section 5 we additionally study the setting where the parameters and forward pass computed at infinite precision. This allows us to establish results independent of the model precision, and is more suitable model for multi-layer transformers where the inputs later layers "mix" the first-layer inputs, and hence can be treated as continuous. In Theorem 5.2 we establish a quantitative LG bound for two-layer transformers, which scales with the transformer weight norms.
The proof' of our main results in both the finite- and infinite- prennisierriiionnn settings rely on the following high-level "simulation argument." Given two limit transformers f.9 and a long input string x, we construct a string 2 of length at most N such that f(x) ~ f(z) and g(x) ~ g(2); if and g agree on all inputs of length I N, then they must satisfy [(x Ri g(x)). The key step in this simulation argument is to construct which approximately preserves various sufficient statistics which are necessary for computing the forward pass of the model. The proof of Theorem 4. does this explicitly, by ensuring that approximates the empirical frequencies of each token in the hard attention pattern, while the proof of Theorem 5.2 does this randomly, sampling from a specially defined distribution and invoking the probabilistic method. Nevertheless, the unifying principle in both settings is that LGG is possible whenever the internal behavior of a transformer on a larger sequence can be simulated by its behavior on a shorter sequence.
Altogether, our results make progress towards both characterizing a natural hierarchy of "difficulty" amongst -egeraaanell tasks, and more practically speaking, developing a better understanding of how to scale training context length for LLMs.
RELATED WORK
number of works have empirically studied the ability of transformers to length generalize on various tasks. [Bhattamishra et al. (2020) studies the ability of transformers to length generalize various formal language tasks. /Anil et al. (2022) show that transformers fail to generalize on certain reasoning tasks, unless certain scratchpad prompting techniques are used. Kazemnejad et al. (2023)
study the role of various positional encoding schemes on LG. ZZou et al. (2023) study LG on various algorithmic tasks, and observe that tasks with a short RASP program (Weiss et al. (202T) have better LG, leading to their RASP-L conjecture. This is supported by works such as Jelassi et al. (2024), who observe that for the string copying task, transformers can length generalize when there are no repeated tokens, but fail once the string has repeats. LG has also been studied outside the context of transformers. For instance, Nerem et al. (2025) showed that trained graph neural networks can learn the Bellman-Ford algorithm which generalizes to shortest paths of arbitrary length. [Buitrago & Gu (202)) studied LG in the context of recurrent models such as state-space models or linear attention.
In light of these LG challenges, recent works have designed specific positional encoding schemes, such as Alibi (Press et al.] 2021) or Abacus (McLeish et al.] 2024) to improve LG. Other works have also considered modifying the input with a scratchpad, extra positional information, alternative training techniques to improve IG on arithmetic tasks (Lee et al., 22023] [hhn et al.) 2023] Cho al. 2025 Lee et al. 2025 Cai et al., 2025). Most recently, architectural modifications such as looping (Fan et al. (2024) or recurrence MMLLeihh et al. (022) have led to LG improvements. Other
approaches by Li et al. (2025); Anson al. (2025): Hashemi al. (0255) have considered making
modifications to the attention mechanism to improve LG.
On the theoretical front, Huang et al. (2025) partially resolves the RASP-L conjecture for tasks expressible by limit transformers. Yang et al. (2025) shows the equivalence of class of transformers to the C-RASP programming language and provide empirical evidence that their theory predicts the
depth of transformer which is required for LG to occur in practice. WWang et al. (2024) proves that 1-layer transformers trained with gradient descent length generalize on a sparse token selection task.
Ahuja & Mansouri (2024) show that model resembling a self-attention head can length generalize.
Golowich et al. (2025) show that an abstraction of the self-attention head can length generalize on
tasks which depend on a sparse subset of input tokens. Veitsman et al. (2025) studied transformer
LG related to copy and retrieval operations, and find that theoretical limitations do indeed transfer
to practice. The work Chen al. (2025) is at first glance the most similar to ours, as the authors
2

---

give nonasymptotic bounds for LG. However, they focus on general models of computation with variable-length input rather than on transformers, offering complementary insights.
3 PROBLEM FORMULATION
3.1 LIMIT TRANSFORMERS
We are interested in the ability of transformers to generalize to sequences of arbitrary length, but real transformer architectures are limited by bounded context length. To address this issue, HHang ct al. (2025) introduced the concept of a limit transformer. These objects have an infinite context length and generalized positional embeddings, allowing them to distinguish between arbitrarily many positions in their context. The computation of a limit transformer proceeds as follows:
y (0) Ex, + Ps. i= -.,,...,,1 |3/|
(1.b)
(y)
) K QuaV !- (i,
H Σj exp (log |x| - -a.s (1,b)
Vin.g) (1-1)
yi 111)
+
h=1 Σj=1 exp (log) |x|| ais (1,11)
yi
Y!
B BIAA + bi),
T(x), UV!
Here x is the input sequence with token E E in the i-th position, E,,, E IRd is the embedding of the i-th token, P; is the i-th (absolute) positional embedding vector. The super- and sub-scripts (1,b) (1, h) denote the 1-th layer of the transformer and the h-th attention head. dij is the (1. h) attention logit between token i and j. Kin., Q1, and V L, are the the (4, key, query, and value embedding matrices, respectively. The functions di i) do not allow for modifications to the attention pattern which cannot be captured by positional embedding vectors alone. Y denote the pre-activation features for layer at position i, and y denote the post-activation features which have been passed through a
MLP with 1-Lipschitz activation th, plus a residual connection; A and b, denote the hidden layer weights and bias term for this MLP, and B; denotes the output layer weights. Finally, T(x); denotes the output logits at position i which are computed via the unembedding matrix U.
Without additional constraints, a limit transformer cannot be recovered without seeing arbitrarily long input sequences. Thus, Huang et (2025) also make two additional assumptions. First, the limit transformers in question are assumed to be A-periodic, defined as = Pi+ for all i. Second, the limit transformers are also translation mranslation-imvarannt, defined as (1, i) = $1. (1 t, + for all f, and rllocal, defined as ( = O whenever i > +
3.2
ATTENTION
Huang et al. (2025) assume that all of the transformer parameters, as well as the softmax attention, are computed p finite bits of precision. This is motivated by Merrill & Sabharwal (2023). and indeed, finite precision is real constraint when LLMs are implemented in practice.
For our analysis, the precise instantiation of this assumption is that we will assume that all quantities of absolute value < 2 are rounded to 0 during each intermediate computation of the limit transformer. Even this definition requires further clarification, particularly for the computation of the softmax. This is because the softmax (at infinite precision) is invariant to a constant shift in all of the logits; thus, in principal, the softmax may be computed as a collection of terms each of which has absolute value less than 2 P, in which case it is unclear what to do. To avoid this problem, we take the usual step for improving the numerical stability of softmax and perform computations with the largest logit shifted O. Eguivalently, standardization, all terms in the softmax (post exponentiation) with absolute value at most 2 P are rounded to 0, then the computation proceeds as usual.
subtract the largest logit from every logit in the softmax. After this
3

---

The impact of this assumption is as follows. Let be single-layer limit transformer which r-local, A A-periodic, and translation invariant as defined above. We can define the attention matrix E TR. RAAEE indexed by pairs (y, i) for y Σ and E Z/A, where A(g.).(a.)) = (Eg + P.) K E + +py). For E E and E 2/A, define
A(g.i) == (A..)))(E.5-)) + o k + 1) |a E == .)..,
Note that Ay contains all of the possible attention logits that we can observe when processing a token I; y. We then define the logit margin (f)) of by
r(f)
min WEL
min a,a' (.a'EA()))
a a'd' a',
IEZ/A
a a-a' >0
where the minimum over an empty set is defined as +Oc. The quantity 7(f) is the smallest nonzero gap we can observe between a maximal attention logit and any non-maximal logit.
Now let be any input sequence and suppose that N = |x| 2 2P/1()) Consider individual term in the softmax, post-exponentiation but before the rounding procedure. These have the form
8y exp log N ((( + <bi, (A(ex.N)(e)- + "('", NN)))
exp log N N [((ENN + - j)+ (AEx + N + 1)I)
exp(log N (a-a"))
where j" E y (N) and 0, a" E N() are simply a renaming of the logits to emphasize that these are quantities in A(zx,N). The second equation follows by the translation invariance of d.
+ *G'", is an index with the largest attention logit
There are now two cases. If a = a" (i.e., the j-th position attains maximal attention for the input sequence), then sj exp(0) 1 and this contribution to the softmax will not be affected by the rounding procedure. On the other hand, if a # a" (i.e., the j-th position attains strictly sub- maximal attention for the input sequence), then by definition of ((f). a"
I -f() and we have
plog ( P
S exp(log N (a a²)) s exp
x(f)
r() [(())
Thus, this term will be rounded to O. It follows that for sequences æ of length N > 2P/T(f), softmax attention acts as a hardmax and the computation is performed as uniform average over the tokens with argmax attention.
As can be seen from this analysis, while these design choices may seem like minutiae, they have outsized effects on the analysis, and this fact has been observed in previous work (Jerad et al. 2025). There is also empirical evidence that attention does indeed concentrate on only few tokens (Bietti al. 2023 Rogers al. (22T) and that finite precision does have a noticeable impact on LLM
behaviors (He & Lab 2025).
3.3 INFINITE-PRECISION ATTENTION
Deviating from previous works, we also provide results when the transformer's attention computations (and indeed, all internal computations) are performed at infinite precision. In this case, do not need to make careful assumptions about rounding. Instead, however, there is an additional subtlety about the scaling of the attention logits. In partieular, given infinite precision and bounded weight matrices, the effect of the r-suffix on the LT's computation must always decay to 0 as the length of the input sequence diverges to infinity. This undesirable as it precludes important functions which transformers are empirically capable of learning, e.g., the induction head. To alleviate this shortcoming, we propose scaling only the r-suffi logits by a logarithmic factor:
(I,) iij
= =1y (1-1)) K.T,A Q
(1-1) + logg i- Ór,n i),
H Σ exp (1i
((hh)
VLLV, (1-1)
(1)
Y !!
(1-1)
Σj= exp
(1,h)
0i,5
4

---

Depending on the size of the r-suffix positional embeddings, this scaling increases the expressivity of LTs to give three different possible behaviors. Consider the computation of the hth attention head in the first layer. For j < i T, the contribution of the jth token will be proportional to
E KI,, B... Therefore for any E Σ, the total contribution of all tokens equal to will be exp E. K
exp
u( where u(ægi), ビj 1(z, s) is the empirical frequency of s in the first i tokens of æ. On the other hand, the contribution of the jth token for i S < i exp ETT Q Ez.) (or. This yields the following three regimes:
1. Token Dominant (maxegr 01 1, < I). For typical sequences, the empirical frequences s((=g:)s will be ((1) for large i. Therefore if Φ is bounded below 1, as + oo the contribution of the 7-suffix will grow negligible.
2. Balanced (maxigr (1,n(1 1, 1). Both the total contribution of all tokens equal to s, well as tokens in the T-suffix with &1, (i. = 1, will be proportional to i, and thus affect the output of self-attention in a constant fashion as + co.
3. Position Dominant (max 61,4 t, > 1). The contribution of the r-suffix dominates that of the rest of the sequence, with the self-attention weights concentrating those tokens
j which maximize 11,4 (j.
Thus, the proposed scaling allows us to consider the full range of possible relative importance for the local information (found in the r-suffix) and global information (found in the 7-prefix) of the input. In spite of these three qualitatively different regimes, we are able to provide a unified analysis which addresses LG in all three scenarios simultancously.
We will operate in the infinite precision setting for our results on multi-layer transformers (Theo- rem 5.2 Intuitively, in the first layer, the tokens are in fact discrete and hard attention to subset of these tokens may be desirable. Beyond the first layer, however, the token representations become continuous mixtures of these discrete objects and are in some sense more "inherently" continuous. This makes the infinite precision setup more suitable for this setting.
Lastly, we remark that the while the details of the finite- and infinite-precision analysis are quite different, the fundamental analysis technique is the same. Namely, we show that it is possible to simulate the behavior of the transformer on longer sequences using strings of bounded length. The implications of the theory for the data requirement vs. various parameters of the target function also align qualitatively for both precision regimes, and these insights match with our empirical results.
4 LENGTH GENERALIZATION WITH FINITE PRECISION
In this section, we give upper bounds on the length training data required for a single-layer limit transformer generalize to sequences of arbitrary length in the finite precision setting.
Let f and g be two single-layer limit transformers which are rllocal, A-periodic, translation invariant, and operate at p finite bits of precision as described in Section 3 Let V,. E', (A,, By) be the value matrix, token embedding, and MLP weights for (and analogously defined for g). and define
Ly = U /1(11 + +| |A | IIIl@ VIVIV , ( + p.)l + | + p.ll + 1b,l1) : s E),
Ty similarly for g. and T, I.f + L.g- Finally, 7 = min(>(/), with >()) and >(g) as defined in Section 3.2 We first establish LG for single-layer transformers in an loo setting.
Theorem 4.1. There exists N O maxx 22/7 [' }) such that [1[(x) g(x) S
for all [2]| < N implies that [x) - g(m)) = O()) for any sequence x.
Proof sketch. As discussed in Section 3.2 the output of each limit transformer depends roughly on the ratios between each token type entering hardmax attention. We construct a "simulation map" from string of arbitrary length to a string of length |z| < N which preserves these ratios up to O(s) error simultaneously for the tokens in attention in both f and g. Since f(2) = g(2) by assumption, this in turn implies that (x:) g(x).. The complete proof is given in Appendix A.2
5

---

shows that, assuming that the input sequences sufficiently long (NV 2 20/7), the desired training length scales polynomially in the periodicity parameter A, the parameter norms L, the vocabulary size [ and the inverse accuracy e- The N 2 2P/7 constraint ensures that the softmax attention behaves as hardmax as discussed in Section 3.2] Indeed, it possible for this hardmax behavior to occur at smaller training lengths, implying that the training length N need
Remarks. Theorem 4.1
only scale with 7 AAL² /E". See Section 6 for empirical support of this claim.
Theorem bounds the test error when we have foo bound on the error, i.e., when the error on every sequence of length at least N bounded by ε. practice, is more common have a bound on the average error. The following theorem establishes that can still achieve LG with respect to average error for a certain class of sequence distributions.
Theorem 4.2. For any probability distribution P (pe)sEx over the token vocabulary E, define
Il gll,,P=
Σ Pr(x))l((a)) g
|0/=n
where Pp -[ Pz, is the probubility of the sequence when the tokens are drawn i..d. from P. Let P = (pe)sez ~ Dir((as)sEz) be drawn from a Dirichlet distribution, and define
|lf glln = Ep--Di((o))essllll 91l,,p].
Let og minger: 0g. Then there exists
16 L 22+200
2200
A
EALL =0(=-2-200
})
No = =0 max 20/7
log
a0
200
g2+200
8
such that lff N S for all N No. we have that ||f g-l = (c21/2) for any T.
Proof sketch. We show that with high probability over the draw of (p=).e and the resulting sequence v, the fraction of (token, positional embedding) pairs is close to its mean. For such sequences, we further show that the output of the limit transformer is approximately constant. This allows us to define a simulation map sim ΣT + EN from longer sequences to shorter ones which (1) satisfies f(x) & (x) and (2) does not transfer a large probability mass of long sequences in Σ to low-probability subset of short sequences in Σ These two features of the simulation map allow us to control || g g terms of [[s دllx for any 2 N. The full proof given in Appendix A.3
Remarks. We make two remarks on this result. First, the form of the sequence distribution is meant to ensure some regularity between sequences of longer and shorter lengths. The need for some such regularity assumption inevitable. For instance, an obvious example would be where the distribution over shorter sequences has support only sequences with tokens in Exhon Ç Σ, while the distribution over longer sequences has support Σ Eshon- The switch can occur at an arbitrarily large sequence length, a bound on the required training length cannot exist in such setting. This counterexample can also be approximated without requiring the probability of certain sequences to be exactly equal to O. We expect similar result to hold for sequences with some form of regularity in terms of token ratios between shorter and longer sequences; e.g., if the sequences are drawn from a Markov chain, concentration of the token ratios the stationary distribution may be sufficient. is an interesting direction for future work to establish minimal conditions on the sequence distribution for LG to occur in the average case. Second, as a corollary to our proof technique, we can strengthen the error dependence of our bound when |I - g gll is controlled conditional on mingex P. = -2(1). In this case, the LG error does not suffer from the quadratic increase from to g//2 in Theorem 4.2 but the required training length to achieve (Es) error is longer. The proof for this setting can also easily be extended to the case where the tokens are drawn from fixed categorical distribution and the probability p. for each token is at least a constant.
5 SOFT ATTENTION TRANSFORMERS WITH INFINITE PRECISION
In this section, we provide upper bounds on the length of training sequences required for two-layer limit transformers operating at infinite precision to generalize to sequences of arbitrary length. Recall

---

that we have made the assumption that transformers which operate at infinite precision only have the T-suffix logits scaled by log (token index), and thus have forward pass given by (I). The key quantity which governs the minimum training length is the following complexity measure.
Definition 5.1 (Complexity and positional margin). Let F, be the class of depth 2 transformers transformers which are 7-local, translation invariant, operate at infinite precision, use no positional
information in the second layer, and have nonnegative di, [1] For transformer f E Fr. with
key, query and value matrices {(K 1.h Q1,t- 1,,))e U U 2,,, Q2,1, V 221)). J. MLP weights | S 1, and unembedding U, define the complexity C(f) as
{(At, Bi) (E..)) embeddings
C(f) exp poly (fIVisall
K 02.1 ))
K Q1.
||A Billop
hE(m)
-poly (VVellop AlAlllpp' [ lop |lUllop T, (-])
Moreover, define the positional margin 7(f) by
7f) == minn (max Pn max/p E Ph p max Px)) keH
where Ph. = (i - 1, jostsr (13 is the set of positional embedding values in the lihh head.
Theorem 5.2. Let f.g Fr. There exists N S C(g)) -1))mm/t/mm""/llla -(s)""" .3) such that (1 - g())ll s e for all |x| I N implies that [I g(x)] Oc)) for any sequence
Proof sketch. Similar to before, our goal is to, given an arbitrary string x, construct simulation which satisfies f(x) R f()) and g(x) As g(2). Our first observation is that Y y the output of the first layer of the transformer in the ith position, can be written as Lipschitz and bounded function of both the r-suffix ri-r:i and the empirical histogram up token i, p=(ggg))= := - oz
2 As
such, the output of the two-layer transformer depends continuously the empirical joint distribution of (< (( (iress)))e)) [e[[= We would thus like for the simulation & to approximately preserve this distribution. To do so, construct a random simulation z by randomly sampling a subset of the tokens in x, show in expectation that the outputs are preserved, and invoke the probabilistic method. In partieular, the following "key simulation lemma" shows that such subset does indeed exist.
Lemma 5.3. Let : [S]T+] x A + =h be fixed function, which is L Lipschitz in its second argument and uniformly bounded by G. Then, there exists a subset I C [T] such that, if = TT, then ||Z] - m| S + n//3 and
T
|x| Σ E(za-ra ((25s))
(G (G+ ((++)
p 2 pa ((x))))
T
1/3
The proof of Lemma T-suffices, we would like for the simulation to include large (i.c., (11 in size) contiguous blocks of z. To do so, we consider Markov chain (i1, f6..... iT) on the state space {0, 1}. with stationary
5.3 proceeds as follows. In order preserve the empirical distribution over
distribution P(i 1) n and transition P(1j+1 0 ú 1) < 1. Letting I = {jj : ig = 1]
one can show that the choice = æz yields a good simulation in expectation. The proof of Lemma 5.3
as well as the full proof of Theorem 5.2 are deferred to Appendix B
Remarks. The complexity measure in Definition scales exponentially in the first layer weight norms. This is unavoidable, as the Lipschitz constant of the first layer softmax scales exponentially in ||]] I. Q1 llop when considered as a function on the space of probability measures, which is necessary when considering LG as we must have a unified bound independent of the sequence length T. Other works (Kim et al. 2021; WWan et al.) 2023; Castin et al., 2024) achieve bounds on the Lipschitz constant of attention which do not scale exponentially in the model weights, but which
'A per the discussion in Section 3.3 all Φi,a < yield the same ""oken-dominan"" regime, and hence assuming ΦL. 2 0 does not affect expressivity.
Infinite precision attention is necessary here show that this function indeed Lipschitz.
7

---

Reepency
10-1
10
10
10-
20
12
longth
longth
Figure 1: Experiments on SimpleTask, Left:
Test loss as a function of test length and train length, for fixed For each fixed train length, test length increases, the test loss plateaus finite value. Right:
Final test loss as function of train length and w. The value the test loss plateaus at decreases monotonically with train length, and increases monotonically with w.
10
10
Ponid city
10
30
1004
10-3
length
Figure 2: Experiments ModPTask. Left:
Test loss function of test length and train length, for fixed A, For each fixed train length, as test length increases, the test loss plateaus at finite value. Right: Final loss function of train length and A. The value the loss plateaus decreases monotonically with train length, and increases monotonically with A.
depend on the sequence length and which are therefore not applicable to our setting. Moreover, for certain tasks which can naturally expressed by a two-layer transformer, the complexity is mild. Consider the following in-context k- gram task, which is generalization of the induction head (Olsson ict al. 2022): :
Definition 5.4. Let Σ = [S]. We say that f is an in-context k-gram estimator if its output on sequence x is the empirical distribution of the token following all occurrences of -r- L.
Eisryj
2T
Oz
(x
E ERS.
Ei 1iam1(aa 1(x 2T-1+17)
Nichani et al. (2024) show that f can be approximated by depth two transformer with k - heads in the hrst layer, and local, translational invariant positional embeddings with - In Appendix B.3 we show heuristically that f* can be approximated up error by transformer with complexity C(J) e and ((f)
training length of e e suffices for LG.
We also remark that in Theorem 5.2 the training length N scales exponentially with the inverse margin 1/y. This mimics the bound in T.eorem/411 which contains exp(>-1) dependence the logit-margin. Whether these margins matter for LG empirically or are simply an artifact of our analysis is interesting question for future work.
EXPERIMENTS
Single-layer Transformers. We next provide empirical support for the conclusions of Theorem 4.
and 4.2
We consider the following two synthetic tasks:
SimpleTask: The vocabulary is Σ 1,,1,22 1, Given input sequence F1.7 (Z1...., FT) ΣT, define c, (xx) T 1(x, = 8) count the number of tokens equal to s. The output f is given (x)))_c1()) where (2)) sin(wz) for some E R. One observes that f is by (x1r) (o(m)++((()
expressible by one-layer limit transformer with positional embeddings and L O(w).
'If there is such within z, the behavior of (a:) can be arbitrary.
8

---

10:0
10
10
164
50
1:0 150 langtt
230
6X10
10"
Thain length
Tanlangth
Test loss as function of test length and train length, for fixed & and S. For each fixed train length, test length increases, the test loss plateaus at finite value. Middle: Final test loss as a function train length and S, for fixed k. The value the test loss plateaus decreases monotonically with training length, and increases with S. Right: Final test loss as function of train length and k for fixed S. The value the test loss plateaus increases monotonically with k.
Figure 4: Experiments on the in-context k-gram task. Left:
ModPTask: The vocabulary is E = {0, 1.. Given a period and index k, the output is the average of all tokens in positions which k mod pt
('1TT) Els 1 k mod p)
Et= mod p)
One observes that f expressible by limit transformer with = p and T, (11)
We train depth transformers (consisting of single self-attention layer followed by an MLP layer) on Simplc for varying frequencies and ModPTaskk for varying periods p. For a fixed training length N, we train models sequences of length T S N, and compute the test loss sequences of length T" 2 N. More details on experimental methodology are presented Appendix C sketches for both constructions are provided in Appendix C.I
Results for Simple'Tass Task and ModPTaask are presented in Figure and Figure 2 respectively. In the lefimost panes of both figures, we observe that the test loss plateaus the test length increases. In the rightmost panes of both figures, we observe that the value at which the test loss plateaus at decreases monotonically with the training length. This provides qualitative support for the conclusions of Theorem 4.1 in particular that (i) given a target accuracy E, tasks expressible by a one-layer limit transformer have finite N such that model which fits the task sequences up length N acheives error on sequences of all length and (ii) the value of this N increases monotonically as e increases. Moreover, the rightmost pane in Figure shows that N scales with the parameter norm L, while the rightmost pane in Figure shows that N scales with the periodicity parameter A.
The proof of Theorem 4.1 relies on the "hardmax" attention behavior discussed in Section 3.2 To check the validity of this assumption, trained on the ModPTask with 5 for varying training lengths, and compute the post-softmax attention probabilities on batch of test sequences. In Fig-
Altancon pranccnnnraaaai probalittiic
0.08
0..4
9.52
0.00
ure we observe that the positions not equal to mod p receive near zero attention probabilities while those in po- sitions equal to mod receive nearly the same attention probability (the dashed black line). This provides evidence that, for large enough training length, the models are indeed operating in the hardmax regime.
10
15
20
25
Tra Length
Figure 3: For the ModPTask, the soft- max attention approximates uniform attention on all positions = k mod p.
Two-layer Transformers. We next provide empirical support for the conclusions of Theorem 5.2 We train depth 2 transformers on the in-context k-gram synthetic task, as defined in Definition 5.4 Additional experimental details are given in Appendix C Results are presented in Figure 4 In the leftmost pane, again observe that test loss plateaus as test length increases. Both the middle and rightmost plots show that as the training length increases, the limiting test loss decreases. Moreover, the middle plot shows the value of this limiting test loss increases with the alphabet size S (when fix = 2), while the rightmost plot shows that it increases with & (when we fix S = 2). This matches the qualitative dependence of the complexity measure C(J) on both S and

---

7 CONCLUSION
In this paper, provided quantitative bounds on the training length required for LG to occur, in settings including finite- and chinite-precision attention, one- and two-layer transformers, and &o and average error control. Our results show that this minimum training length scales with the parameter norms of the transformer, the periodicity A, locality т, alphabet size [Σ], and inverse error e- Unifying analyses is the high level argument that LG occurs whenever the forward pass of transformer on a longer string can be "simulated" by that of a shorter string contained in the training set. Qualitative support for the derived scalings are presented in Section
One interesting direction of future work is to extend our results to transformers with larger depth. In particular, it would be interesting to relate the minimum training length N other notions of complexity such as the length of the corresponding C-RASP program. Moreover, it would be interesting to extend our average-case analysis in Theorem 4.2 to broader classes of distributions over sequences. Finally, it is an important question to characterize how different positional embedding schemes, which empirically improve LG, affect the minimum training length N.
ETHICS STATEMENT
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
LLM Usage:
We used LLMs to check for grammatical errors in the paper.
REPRODUCIBILITY STATEMENT
Experimental details are provided in Appendix and code is attached to the submission.
REFERENCES
Kartik Ahuja and Amin Mansouri. On provable length and compositional generalization. arXiv preprint arXiv:2402.04875, 2024.
Dana Angluin. Inductive inference of formal languages from positive data. Information and control, 45(2):117-135, 1980.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546-38556 2022.
Ben Anson, Xi Wang, and Laurence Aitchison. arXiv:2505. 17083, 2025.
Scale-invariant attention.
arXiv preprint
Andrew Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions Information theory, 39(3):930-944 1993.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009, 1164,, 2020.
Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of transformer: A memory viewpoint. Advances in Neural Information Processing Systems, 36: 1560-1588, 2023.
Ricardo Buitrago and Albert Gu. Understanding and improving length generalization in recurrent models. In secoy International Conference on Machine Learning, 2025. URL https
//openreviee wwt.: htt.
10

---

Ziyang Cai, Nayoung Lee, Avi Schwarzschild, Samet Oymak, and Dimitris Papailiopoulos. Ex- trapolation by association: Length generalization transfer transformers. arXiv preprint 10Xi::2506.09251, 2025.
Valérie Castin, Pierre Ablin, and Gabriel Peyré. How smooth is attention? In International Conference on Machine Learning. PMLR, 2024.
Thomas Chen, Tengyu Ma, and Zhiyuan Li. Non-asymptotic length generalization. In Forty-second International Conference on Machine Learning, 2025. URL UR./tttsss//ppeeeeeeee Eorum? LDFTumm?ddW222225EWW
Hanseul Cho, Jaeyoung Cha, Srinadh Bhojanapalli,, and Chulhee Yun. Arithmetic transformers can length-generallin both operand length and count. The Thirteenth International Confer-
Learning Representations, 2025. URL htthh:tp///// http:////ppeeeeeeeeeeeeeeem net/ forum?id=
/
@IqGesYKLG
Ying Fan, Yilun Du, Kannan Ramchandran, and Kangwook Lee. Looped transformers for length generalization. arXiv preprint arXiv:2409.15647, 2024.
Mark Gold. Language identification in the limit. Information and control, 10(5):447-474 1967.
Noah Golowich, Samy Jelassi, David Brandfonbrener, Sham M Kakade, and Eran Malach. The role of sparsity for length generalization in transformers. arXiv preprint arXiv:25002.1673 2025.
Baran Hashemi, Kurt Pasque, Chris Teska, and Ruriko Yoshida. Tropical attention: Neural algorithmic reasoning for combinatorial algorithms. arXiv preprint arXiv:2505.17199, 2025.
Horace He and Thinking Machines Lab.
Defeating nondeterminism in Ilm infer- ence. Thinking Machines Lab: Connectionism, 2025. doi: 10.64434/ml.222500110
Xinting Huang, Andy Yang. Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. formal framework for understanding length generalization in transformers. In The Thirteenth International Conference on Learning Representations, 2025.
URL htttps://pperreiieeee wtwprreviiee..eee/oummiiiiiie.
Samy Jelassi, David Brandfonbrener, Sham Kakade, and Eran Malach. Repeat after me: Trans- formers are better than state space models at copying, arXiv preprint arXiv:2402.01032. 2024.
Selim Jerad, Anej Svete, Jiaoda Li, and Ryan Cotterell. Unique hard attention: A tale of two sides. arXiv preprini arXiv:2503. 14615, 2025.
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy, The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36:24892-24922. 2023.
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In International Conference on Machine Learning, pp. 5562-5571. PMLR, 2021.
Nayoung Lee, Kartik Sreenivasan, Jason D Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.033381, 2023.
Nayoung Lee, Ziyang Cai, Avi Schwarzschild, Kangwook Lee, and Dimitris Papailiopoulos. Self- improving transformers overcome easy-to-hard and length generalization challenges. In Forty- second International Conference on Machine Learning, 2025. URL /tRpstttp///ooeeeevieee net neet/Eormm? id 3=XOMBT6mm
Ruining Li, Gabrijel Boduljak, et al. On vanishing variance in transformer length generalization. arXiv preprint wtxXiv:2504.028277 2025.
Sean McLeish, Arpit Bansal, Alex Stein, Neel Jain, John Kirchenbauer, Brian Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Geiping, Avi Schwarzschild, et al. Transformers do arithmetic with the right embeddings. Advances in Neural Information Processing Systems, 37: 37: 108012-10804 2024.
11

---

William Merrill and Ashish Sabharwal. A logic for expressing Nog-precision transformers. Advances in neural information processing systems, 36:52453-524444 2023.
Robert R Nerem, Samantha Chen, Sanjoy Dasgupta, and Yusu Wang. Graph neural networks extrapolate out-of-distribution for shortest paths. arXiv preprini (.XXi:2503319173 2025.
Eshaan Nichani, Alex Damian, and Jason Lee. How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402. 2024.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads. Transformer Circuits Thread, 2022. html.
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.
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. A primer in bertology: What we know about how bert works. Transactions of the association for computational linguistics, 8:842 866, 2021.
Ruoqi Shen, Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, Yuanzhi Li, and Yi Zhang. Positional description matters for transformers arithmetic. arXiv preprint arXiv:2311 1.t::27771..777 2023.
Yana Veitsman, Mayank Jobanputra, Yash Sarrof, Aleksandra Bakalova, Vera Demberg, Ellie Pavlick, and Michael Hahn. Born wranformer--lwwag a transformer? arXiv preprint arXiv:2505.21775. 2025.
Yihan Wang. Jatin Chauhan, Wei Wang, and Cho-Jui Hsieh. Universality and limitations of prompt tuning. Advances in Neural Information Processing Systems, 36:75623-75643, 2023.
Zixuan Wang, Stanley Wei, Daniel Hsu, and Jason D Lee. Transformers provably learn sparse token selection while fully-connected nets cannot. arXiv preprint wwXiv:2406.06893, 2024.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. International Conference on Machine Learning, pp. 11080-11090. PMLR, 2021.
Andy Yang and David Chiang- Counting like transformers: Compiling temporal counting logic into softmax transformers. arXiv preprint arXiv:2404.04333 04393, 2024.
Andy Yang, Michaël Cadilhac, and David Chiang. Knee-deep in c-rasp: A transformer depth hierarchy. arXiv preprint arXiv:2506. 16055, 2025.
Greg Yang, Edward Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao. Tensor programs v: Tuning large neural networks via zero-shot hyperparameter transfer. arXiv preprint 2xXi:22033003666 2022.
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? study in length generalization. arXiv preprint ar1iv:2310. 16028, 2023.
12

---

A OMITTED PROOFS FROM SECTION
In all of the proofs and discussions for this section, we will assume that all sequences are of length at least 2P/ min()()))(9)),, As discussed in Section 3.2 this means that attention will operate as an argmax over tokens with maximal logits, and therefore the computations of the transformer will be performed over a subset of tokens determined by (token, position mod A) in the r-prefix as well as potentially some tokens in the r-suffix. As, such, it will be useful make the following definition.
Definition A.I. Define the loken counting function n Σ x & x Ex + Zgo by
n(s,i,x) # ..... |2| 2i and j i (mod A)}-
That is, nt,s, counts the number of times that token appears in position which is (mod A) in before the 7-suffix. In the case where there no positional embedding vectors, similarly define
n(s, x) # L, |-| |-|-
x;= s}.
The subset of (token, position mod A) pairs which enter the hard attention mechanism is determined by the final token and its positional embedding vector. Thus, in the constructions which follow, it will be important that the original long sequence x (|æ²] = 7) is simulated by a shorter string (|2l N) such that 2T = 2T and T N (mod A). This will ensure that the hard attention mechanism considers the same (token, positional embedding) pairs for both strings, and therefore that the output of the limit transformer can be approximated by preserving the ratios of these quantities.
With these concerns in mind, consider a single-head, single-layer limit transformer and an input string x with |a]] 2 2²(O), Let A(x) C Σ x [A] be the set of (token, position mod A) pairs in the T-prefix attended to by f when parsing the final token IT, and let (1 the set of (token, position) pairs attended to in the r-suffix. Then the internal state of f immediately after the attention layer is given by
f(x)) E(anEes iV S +P)) + + ((.))EAT())) VA +p,)
(2)
E(as)eA(a) ((,,,,)) + (T((r)
and the full computation is given by
f(x) U, (EE,, + f(x)) + BAbr(A, + +(x)))
+b))
(3)
A.1 HELPER LEMMAS
For both of the unite-precision theorems, the following lemma relating f and will useful.
Lemma A.2. Let and be sequences with |x| = T and |a| N. and suppose that the final
tokens are equal: 2T ZN. Then (=) - f())ll s L L.LPP [f(x)) f(2)]l, where
MLP 1U | B ,11
is a bound on the Lipschitz constant of the transformer MLP
Proof. We can write
((x) U, (EE), [(x)) (B)))+BBb)(App))) (A + +b,)
Because IT = 2N, we have ES_ = E Straightforward applications of the triangle inequality and the submultiplicaivee inequality for operator norms then yield the desired result.
The following lemma bounds the norm of the output of a limit transformer in terms of the norms of the weight matrices and activation function.
Lemma A.3. Define the following quantities:
L -||U,
|AI||BB
MY
max
IV VV,EE/ +p,Il
SEX, [E
13

---

Mf SE2
|E + P:ll.
Then setting
My L + My + ||b,11),
we have [[f(2))I & y for all x.
Proof. The proof is nearly identical to that of Lemma A.2 We begin by observing that f(x) is convex combination of terms of the form V E P,). in particular [f(())] S Mý. The results
follows by using the expression for f()) in terms of fxx) given in equation 4 the triangle inequality. and submaltipliaatiityy of the operator norm.
A.2 PROOF OF THEOREM
In this section, we give the proof Theorem 4.1 We will first prove another helper lemma which will aid in our simulation string constructions.
Lemma A.4. Let {p:) be an arbitrary finite probability distribution. For any integer N 2 1, there exist nonnegative integers {m4)==1 such that E m, N and |ma /N pal 1//N for all i == 1, ,,...,t. n. In particular, this also implies that the my satisfy \p,N- - m.l < for all i.
Proof. Define m. = P and let R = N i m, Note that 0 S R < n. For 1,...,R define m, m, + and for = R 1,..., n, define m, m, This choice of m, can easily be seen to have the desired properties.
,,,
L
We are now ready prove Theorem 4.1 which restate for convenience.
Theorem 4.1. There exists N 0 max 22//7, =
}} such that [lf(z) [1(())
for all |2|| < N implies that [f(x) ((x) = O any sequence x.
Proof. We will first give proof assuming there no positional embedding vectors P.. We will then show how to easily adapt the result to the case positional embedding vectors.
Consider two limit transformers I and y and an input string Let Py be the positions attended to by and Pg be the positions attended to by g in the T-prefix of x and assume WLOG that |Py S P. Let A = (z) {x, l e Py} be the set of tokens which f attends to and define Ag = Ay (z) similarly.
We construct the auxiliary string 2 follows. The 7-suffix of is always equal to the r-suffix of x;; in particular, this ensures that the final tokens of x and & are equal.
If [Pyl. P.l I 1/2, then the attention pattern in the r-prefix of x can be directly recreated simultane- ously for f' and using at most 2/e tokens by just copying the union of the tokens in attention for f and g into In this case, by formulas (2) and (3). will have (xx f=) and g(x) g(2) and therefore f g(x)]| (=) g(z) <. Thus, we will assume that at least PP, 2 1/e.
We first recreate the attention pattern of f. To simplify notation, let n. n= x) and m. n 2). If |Pyl < 1/e, then we simply set | = IP, (i.e., we set the first |Pl tokens of equal to the attention pattern of on the r-prefix of œ). The tokens which we will add later do not belong Ay; thus, we will clearly have f(x) = f22). Thus, in the following construction, we will assume that IP, 2 1/E.
We first proceed with slightly more fine-grained construction of Lemma define
A.4 For each s E Ay.
[//
m, =
ns
and let
[1/E]
R
Σ SEA,NA,
n2 Σ mg
Pp
SEA,nA,
14

---

We must have R < | n Agl. choose I S A, A.g with |r| R and define m, mg + 1 for
s E and m, = m, for E (Ay n Ag) I. This defines m, for all s E A n Ag with the following two properties:
[1/E]
[1/e] P2
m,
Ppyl
V A n Ag 0 S
Py n - E
ma <1 (5)
sEAynAp
We then turn to Ay Ag and define
| [P/
R' Σ
Σ
n
ma
ma
SEA;
SEAriA,
SEA,NA,
clear that S |A, \ Agl: so we can similarly choose A \ Ag with J = Rt and
define m, 1 for E J and m, = m. for E (As \ Ag) \ J. The defined in this way have the property that
[/6]]
[1/ PP3
m,
Ppy n
<
vs A5
P Pp
Σ BEA,
m2
1I
(6)
Combining results 5 and
6
we have the additional result that
[1/=]
[1/
[1/e]
Σ #EA,
<
Py
n Pgl
P3
P3
Σ
My 22
Py
PPs
*EA,nAg
SEAr
In particular, combining the results of inequalities satisfy
(6. and 7 we can conclude that the m,
m
n
O(e).
(8)
EdEA, my
Py
We can use these inequalities to bound the difference between f() and f(z). Define
(T(x) EVEA, Nid
to be the internal state of immediately after the attention layer, ignoring the r-suffix. Letting Pj be the set of positions attends to in the s-fuffi of x, observe that we can write
Eiepy V,EL EVEA, no + + EVEA, no + |P]|
EJEA, nly
(x)==f( f(()-
therefore follows that
1
TMY | EveA, nes
-(6))-(((M)))
(9)
IPFl
1 EveA,
2r MM + TMY
2 EVEA, nss
(10)
EvEA, nes!
< 3MY TE.
(11)
Inequalities 9 and 10 both use the fact that |P71 < t and [|V W S MY. Inequality 10
additionally uses that
2|
P
Σ E'EAY Ngg
+
ExleA a
15

---

provided that |PF// E Roy S 1/2. Since |Pyl EsEA, ns > 1/e and |P]] S T, this inequality holds for e small enough, The final inequality (35 simply uses the fact that Σ EsEA, n2
|Py > 1/e.
If we then define
[T) EFEA, my M.VEE EoEA msy ms
similar calculation will then yield
3TM
3rMY
1 EXEA, m,
S 4My TE
[1/e] -2
for small enough. By the triangle inequality. then have [f(x)) - f(=)ll - (lf(z) - (z))++++ ( (x))) (x) -x)
rS).
(12)
We can now bound [] fz](=) We have
ExEA, ns n.V, E!
EsEr, m. v EEE EsEA, my!
(())-
[Pyl
My Σ
11
m
Ppr
EVEA, ms
sEA,
= O {E|)).
(13)
Equation 13 uses the bound from 8 and the fact that |A,l N [Σ]. Plugging 13 into 12
we obtain
I1(xx) - [(=])=(>)]1=0000 O(M (( +))).
Applying Lemma A.2 we then have
ll(x)) f(=))l OLLYUP MU +
(14)
We will refer to the portion of which has been defined up to now as the f-prefix of 2.
remains to extend so that it can simulate the behavior of g without adding any tokens in Ay so as to preserve the previous calculations. There are now two cases depending on the size of Pf n Pg. First, suppose that P n P/l/|P, S e. By Lemma A.4 there exist m such that
[1/Ea]
m
nh
< 1
Vs Ag,
Σ m. [1/=7]. SEA,
[Pp
We now define m. = m, for s E Ag Ay. Combined with the earlier definitions of m, for E Ay O Ag above, this defines m, for all E Ag. Furthermore, we have
Σ AA
m. [1/E21
Σ
m.
SEA,nA,
[1/c2]
> [1/621
Σ
n. 1) [Pg]
AEAynA,
Py n Pa
[1/631
[1/E?] |A, n
PAP
> [1/E21(1 =) |
(15)
> [1/E?1 -2=)
16

---

for small enough. (Here, (55 uses the assumption that PyllPPl E.) Thus, using similar logic as the derivation for inequality we obtain
m
n2
O(s).
Σ ES My
Pa
We now show that the terms in the suffix and in A n Ag do not contribute much to g. Define
n1 V E
g ()) = Σ
SEAg (4,
We have the following bound:
EEEA, V g Eg + LiEP, V EgE%
n, V. E
10(z) (.)
Pg + |
[Pgl
SEA,IA
Eiep V E2,1
EOEA,nA, ns V E. EOEA,
n2 V E
P
iPgl Pr
Pgl + |
Pg
P.
PT
MY P S <M TE
P& \ PAIMY P|P
(16)
IP7l
Pa
PP
S My TS + My & 2M TE
S 4M 9 TE.
(17)
Inequality (16) used the fact that P2 2 1/e, |PT1 <., ,V, El S MY, and (P, | P2
>
1 - P///// whenever | Pgl is small enough (which it will be for small enough e).
If we define
m. V.VVEL E
(-)==)=
Σ
SEA, EvEARA, m.
then the same logic as used to derive 17 can be used to show that ((a))p((a) -at{) O(M This is because the critical facts that
EEEA,DA m ExEArs m.
O
analogous PP and
P = =
Σ EsEAprA
analogous to 1P]1/1,]=000)
We can now use inequality 177 the triangle inequality, and Lemma have
A.2 to bound the error for g. We
l0(x)) - -())) S (0(x)) g¹² (x)] + (1 ((=)] 11 vn (x) - 9 ( (=)1
SO(M TE)+ +
Σ
m,
nh P
M
EVEArA ms
#EAg AA
=O(M) (T+ (T+
17

---

Lemma A.2 then gives (19(x) g(=)l O My (T + (E)E).. This completes the when IPy n p S.. E.
Otherwise we have [P n p E. In this case, we have PP, < SP & |Pyl/e. We now consider two further subcases. Again if [py] S 1/E, we then have | $ 1/E². Thus, there are O(1/e²) tokens in the union of the attention patterns of / and g Thus, by setting 2 equal to the collection of all tokens in this union of attention patterns, we have f(z) = (z), g(x) g(z). (z) g(x)ll f g(=)ll (E)), and |a| O(1/=2) as desired.
most 1/8 + 1/e² +
Thus, we may assume that s > 1/E.
Lets* argmax n2 Note that since |pyl 2 1/E and |Ayl S
E we must have ns 2 |P/l/EE)
For E Ag \ Ay, we first define m by
m,
12g
N2."
Again similar to Lemma A.4
we define
R Σ
ns
mzJ.
Ng.
sEAg Ay
SEAg/Ap
We again have R < [g Ayl. so choose I I Ag \ A,, |1| R, and define m, m, + 1 for s and m, = mg for s E (Ag \ Ay) \ I. In this way, we have
mg
my
n2
$
Vs Ag As,
Σ SEA,
m
ng
Σ
mg
1..
(18)
n2.
Ng
(d,
sEA, \A,
Note that in addition, have
Σ
m <
mg + 1
(19)
R2
AAAg
#EAg AAy
[1/e]
Pr Ns + 1
ng +
(20)
sEAp\A AA
[1/e]
<
Pg
P/l+
+1
(21)
|pyl
n2-
< [1/e] (1/=) /
(22)
= 0(1/6)).
(23)
In particular, this implics that this construction can be completed by adding at most O(1/E?) tokens 2, in all cases the length of is (e2) desired.
18

---

We now proceed bound the approximation error. We first want extend the bound in (8 to all of Ag. To this end, we have
Σ M. R4 - Σ ms
M
Σ
M
R2
ma
+
Mg
SEAg
sEAg
AEAx\Ar
aEAg
SEAgDAy
sEAgnAg
my
[1/e]
< 1 +
Pg Fy
Pg PgNplt +1
+1
(24)
|Pyl
[1/l]
[Prl Nl.t
+1
[1/E]
2
Po fyl
(25)
74g
Ppl
P Pyl
2 +
< 2 + |=
(26)
Inequality 24 uses
18 and
again 5p: and (26 uses the fact that vi--
|P///E/|
We can now bound the error of the ratio of m, over all of Ag. We have
my
n2
(27)
EVEA, mss
L'E nre + 2 Σ
ne
EvEA, No + m../na
2+1
2s' ns
R₂
ns
m. /u,""
(28)
Σ e/ EAg nl
EvEA, Th.
m
n2
Σ
Σ EEA Nl
0(1E12))
(29)
v EAA Nu
Inequality 27 uses and 26
28 uses
(EeEA, / 1; and 29 again uses (5) and 2 (EEE). In a similar fashion, can be shown that
n₂ 2 P conclude m.-
m,
n
0(1))s)
EVEA, ms
Ever, n.
Now we compare g(x) and g(2). As before, the effect of the 7-prefix contributes at most O My TE) lg((z) - g(2))l, we have
(|o(z) |(x) < 1
MLP Σ
m.
n2
MY 9
+ OL
MLP My TE)
Σ Ev, my
Eves, Nly
SES,
=0 ( MLP MV (1 + T)E).
Let M, MML My and similarly for g. In every case, have constructed such that [[(z))
f()) = (M, +r))+ and [[g(x) - ==)) O(M, + +)=), and the length of 2 is 0(1/=2).
Making the crude bound [ + 7 7 for convenience. therefore have
[1[(x) .(>) O((M, + x))
19

---

whenever [lf(2) g(=)ll < for all inputs |2| < N, and N O(1/E²). Thus, by substituting + (M we have flf(z) - g(z)ll = (=)) for any string x provided that f and g differ by at most on inputs up to length
N - (My + 2 10
Including positional embedding vectors The setting with positional embedding vectors can be reduced to the general vocabulary case at the cost of increasing [>]] - A and an additional factor of A by considering each possible (token, position mod A) combination as its without positional embedding vectors. (This increases the vocabulary size from |Σ] to |X] A.) The construction without positional embedding vectors can then be used considering this expanded vocabulary; however, placing a "token" in the expanded vocabulary x [A] may require placing up A true tokens to ensure that the positional embedding is correct. Thus, this construction requires most an additional factor of A tokens. This gives a final bound
token
1O + Mg ( M,, A (
=
22
As discussed in the beginning of the section, it will also be critical that |=| = |ar] (mod A); this can always be accomplished by padding z with at most A additional tokens, which does not change the asymptotic length bound.
A.3 PROOF OF THEOREM 4.2
Lemma A.5. Let E ET and suppose that its constituent tokens 3y drawn i.idd. from categorical distribution, where Plx; = 8) for each E. Then with probability at least 1 we have that
n(s, i,
Ps
8
T/A
for all (s simultaneously provided that T 2
2 log
AEEA
We say that x E bulky when the
above inequality holds for all (s, E E x [A] simultaneously.
Proof. Fix and consider the subset of positions = (mod A) and let T" T/A be the length of each of these subsequences. (We will ignore the fact that this may not be an integer as it neither interesting nor important.) By Hoeffding's 's inequality, we have that (n(s, i, x) p.7 > cv with probability at most =o Setting we see that
//og
2|ti and taking union bound over (s, i) E Σx [A]
2/ log
n T
P
Ps
T"
2E log
with probability at least 1 Setting 8 result.
and solving for T = AT" yields the desired
T
Lemma A.6. Let A(x) C Ex [A] be the set of (token, position mod A) pairs in the T-prefix attended to by f when parsing the final token IT. Furthermore, suppose A(x) # 0, iee, some tokens in the T-prefix enter hard altention. Define
[( E(eNEA( ns +
E(s n1s', i',x)
to be the internal state of immediately after the attention layer, ignoring the T-suffix. Furthermore, define
f(x) E(S.)EA()) P&V V P.)
E(1DEA(())) Pe'
20

---

Finally suppose that minge Ps 2 y and that å is small enough such that |Σ| s 1/2. Then for any a E bulky, we have that
- f(x)) 3My AME((1)))
(x)
where Mÿ- = max,,e, IV + P.)II
Proof. Let A = A(x). Observe that
n(),i,))
(()))))(())1)
Σ (a.0)
Pa
MY.
(30)
Ees n(s', E(s Pat
We will proceed by bounding the terms in this summation. Let T" T/A. E bulkr, we have the following:
Observe that for
((),1,z)
(p. + +8TT
Coriennnnsss n(s',
Ps
8
Elerye Pos
E(ss)eA Ps Eiess
EigtyeAPo -
(31)
Ps
7/ 2) 1+
6)
2/2/40)
(32)
E(e
?
Pa
3/
Σ (st Ps
7
Inequality (31) holds because |.4| < AaAA. Incquality (3) holds because
S'EA Ps 27 (since A is
nonempty and all p 2 7) and 1/(1 - E A6/) < 1 1 2 Σ A5/y when
E Σ|45/y $ 1/22. A similar
argument with 8 + 55 and the inequalities reversed also shows that
n(8,x)
A
Ps
?
We therefore bound the terms in 30 and obtain
A/
3(
3(E
(x) -(0))
My
as desired.
Lemma A.7. Let A(x) be defined as in Lemma A.6 and again suppose A(x) + v. Let A (x) be the set of (token, position) pairs attended in the T-Suffix. Define
f(x) E(ADEACa n(s, VV (E! p.) + EISAEA (E! + p.)
E(S.) n(s, i, +|AT|
to be the internal state of f immediately after the attention layer, this time not ignoring the T-suffix. Then we have
1 (x))) 3TAMY
(7 8)T
provided that x E bulky.
Proof. We denote A(x) and AT Ax)).. Observe that we can write
E(ii)enn is), + Euner V, + p.) Eisieennss ((s,i,)) [AT]
((x)=)((x))) EieneA ((,, + [AT]
21

---

It therefore follows that
TMY
-f())
1x)( + Eisiees ((s,i,z)
(33)
1+
147
(iriee ((a(aa)
2r
-My
My
(34)
E(eNEE (s,,,,))
E(e.)Eanss, ((),
3rM
(355
6)T/A
Inequalities (33 and (4) both use the fact that |AT| S and |V, (V ( S My. Inequality (34)
additionally uses that 1/(1 + |AT|/ / n(s, x)) 2 1 -/ n i, x) provided
that |AT/ |ATI/E (o. n i) < 1/2. The final inequality (35) uses the fact that A + 0; that
bulky i, x) 2 (p. 8)T/A; and that Pe 2 ?
Lemma A.8. Suppose that x E bulky, 2 bulky, 2T ++11 = 2N ++N: and N T (mod A)
with N < T, and min Ps 7. Then
(E)A))8
7A
f())l s <6M) LMLP L
(7- 8
Here, T.M.P.P is the bound on the ML. Lipschitz constant from Lemma A.2
Proof. Observe that since z and & share a common r-suffix (and therefore a common final token) as well as common positional embedding vector on the final token, A(z) A(z) and AT (z))..
may now consider two cases. A(x) = A(z) = 0, then f(z) f(z) exactly (all of the calculations performed the shared r-suffix) and the desired inequality holds trivially.
Otherwise, we may assume that A(x) = A(2) + Ø. We may then apply Lemmas have
A.6 and A.7
We
< (1)()))))0-->>>)))))>)))))<>))>) ( -(x0I 3TA (7 8)T
3MY (E)))8
(36)
The analogous inequality holds for 2 with T replaced by N. Since f(xr) depends on only via A(x).
we have f(x) f(=). Thus we can again apply the triangle inequality to write [IÍ(z) f(=))| <
lx) f(x) + I1f(2) - f(x))l- Applying inequality (36) to each of these terms and using the fact
that N < T. we have
(77 T (E)))28)
[f(x)) f(2)) s 6MY
(7 (7-8)N
7
We then directly apply Lemma A.2 to obtain the final result.
Lemma A.9. Let {Px)sEx ((s)))))t(ass)eee)) be drawn from a Dirichlet distribution with parameters ag. Define a² = E.er as and co min.gg al Then have
2/ au
P( E E PS <)
4 ~00
Proof. Rather than dealing with the more complex joint distribution of the ps, we will bound the marginals and apply a union bound. The marginals of the Dirichlet distribution are ~ Beta(as. a* - ax), so suffices to provide lower tail bound for the beta distribution.
Let Beta(a, B), so has density f(x Ba
3-)-11 where B(a,33)
So xa--1(1 0-1 do is the beta function. We first give lower bound B(a, 33.. When a, B
22

---

have
3/4
Bia, 3) 2
za-1(11
-x)0-1 dx
1/4
1
1
8-1
2
4
22 22-
4a+9
When S 1, we have
B(a, 3) 2 /
(1-2) dx 3
30
Similarly, when 3 & 1, we have
( x xa-1dx dx dx=
B(a, 2
In particular, since 4 2 a, 3 for a, B > 0, we have that
B(a, B) 2 min 1 (a(-)) = (a+t0)
With this incquality, we can now establish the following bound for S 1/2:
P(r S t) = B(a,3)
x 1 (1 - (1=2) dx
<
xa (1 x)) da
B(a,8)
$ 1
2a-1 t) dx
B(a, 3)
10
a(1 t),( 3)
< 2 8
Now that have established the tail bound for a general beta distribution, can return to the original goal of bounding the Dirichlet. The marginal beta distribution for each p, has a a, and 3=a a- a. Thus, by a union bound, have
P(3s: Pe < <) <
Σ P(p. < <))
3EΣ
2
40.ta" -asn
SE>.
7000
00
desired.
U
Lemma A.10. Suppose that T > N 2
A8-2 2
-2og 2
and mitt, Ps 2 Then we huve
|| TT = o (M, (M,, (p+ (Σ)))²
AA
+ || - gl1 gll
( 8)N
Proof. Given an integer N, define the simulation map sim (x) = N = the last N' tokens of v, where N < N' < N A is chosen such that N' = T (mod A). Note that using this definition
23

---

and for N 2 7, we have 22-7+1:7 (simy (z)) --r+ir i... the r-suffixes coincide. Furthermore, by definition, .' ssmm (z) = (mod A) and the final tokens match, so A(simy(z)) = A(x).
By Lemma A.5 and union bound,
bulkr and (z) E bulky simultancously with
probability at least 2p provided that 2 Z 2d log A|ا|
The token independence means
that (s)) [xx) = P(z), so we have
Σ ((=))(((=))((1)) 1===
Σ
P(x) (M, M2)
P(x) g(>)))
-|==
xi=7 @buulky and simy Ez)Ebulk
ægbulkr or simy (z)
< 22p + M2)+
Σ
Σ P(x)
-()))) +1]( [(=) + +1((1)) - s(=)ll)
xEbulkx'
#Ehulker
(
< 22p + M2)+
Σ
- --(=-)+++++++0// - s(=)1I + (1g(()) (())ll)
sEbulky'
(E]
7A
2 + +1) + 1lf - 9 + 6(M LIP + My M
(37)
( 8).N
(MM, M₂) p (E)A))
A
+ +Iʃ 100--gllww gllv.
(38)
(7
N)N
Inequality (7) follows from Lemma A.8 similarly for g.
Inequality
38)
uses the fact that MY I.LPP < M and
We ready prove Theorem 4.2 which restate here for convenience.
Theorem 4.2. For any probability distribution P = (pe)sex over the token vocabulary E, define
Il gll,,P
Σ Pf(+))lf()) - -(())l.
|x|=n
where Pp(x)) -1 Pz, is the probability of the sequence when the tokens are drawn i.idd from P. Let P (pe)eex ~ Dir((ax)sEE)) be drawn from a Dirichlet distribution, and define
||ʃ g|ln EEp.Di((a.))e:)llll -glln,))
Let og = min.er 0g.. Then there exists
16 n0 2+00 +214+200
A5
EL }) =Ō(e -2-222000
No 00=00 max 20/7
log
20
224205'
8
a0
such that I| 81lN N S e for all N S No. we have that ||ʃ gll (25212)) for any T.
Proof. By Markov's inequality, Ep-Ditto - gllwip S & implies that || - gll > with probability at most e/n. When P is such that || gllN.P p > 7, we can use the bound Ilf gllz,p I M2 + Mg.
ا| 40 a0 On this event, we can again By Lemma A.9 min, Pe < y with probability at most
bound || ((x) TT < M, + Mg-
Conditional on min, Ps 2 7 and || gllv.P S n,
the bound from Lemma A.10
Thus, by marginalizing P over the previous three cases, we have that
E Ilf - 1 = ( + Mg)
[Σ|
4a
7 00 + C + p
( 2)
7A
(
8)N
+
(39)
24

---

provided that N 2 A6-2
280-1log
loog
To make the entire bound O choose the following:
P
22/2
000 1/2
1) =/12
7 4 (0 My - MMg) ggg)
M, + Mg
52/27 8 (My + ())
Og 20 e1
4 00 (My + Mg) 1+00" 1312t A
Note that with these settings, indeed have 7 6 and furthermore TA/((7 8)N) O /2) = o(e2/2). All other terms ((e! with
39 are O Thus, we arrive at an error of
N = (
16 "0 (M, + Mg) 22)22200" 44200 A
log E + Mg)
4g cl+00*
200
as desired. We make several remarks. First, we actually required that I g Ny S E, but since N' < + this does not change the final asymptotic bound on sequence length. Second, is interesting that up to leading order terms in E does not enter the bound.
final remark on the proof is that if we strengthen the assumption to f|f- -lll', S conditionally on P with min, Ps > y, the resulting error can scale as ε rather than gl/2, albeit with larger required No. In this case, (39) becomes
[ [p. 1ll1, o ((M,; + Mg)
4a' (12) 700 1o0++00 p+ (/2)))38
TA ( 5)N
) +0)- (40)
au
Setting p. 7, and according to
a
E
p Mj Mag"
7=
4aa E
(M₃ + Mq)
ap
0g 0000
8 gltr0""
87
8 = (M, + M1 (22
40 (M₃ Mg) 10
13/2t05 A
inequality
44
is (E)) with
16 (M, + M2)222m00
Σ 24220 A
Σ AM + Mg)
= 0
log
200 0
2+200
= 10(E-(222gg) log 1).
B OMITTED PROOFS FROM SECTION 5
Notation. We will assume WLOG that [S]. For a string I [|]|a], define μ(x)) to be the
empirical frequencies of the tokens in z, i.e (u(x) = Σ i=1 Cz., where e, E SR$ is the jth standard basis element. Moreover, let r'gi denote the substring of containing the first tokens, and for set A, A the substring of æ containing only those indices A. Finally, for integers a < define (a b) to be the set of integers (a, b.....b-111.. 1,
B.1 PROOF OF KEY SIMULATION LEMMA
In this section, we prove Lemma 5.3 which restate below for convenience.
25

---

Lemma 5.3. Let p [S] A - R be fixed function, which is L Lipschitz in its second
argument and uniformly bounded by G. Then, there exists a subset I C [T] such that, if 2 = 21, then ||Z|-n - nl
++++ 1/3
and
T
F= pz ra, (((S)))
(G ((++) n
Σ
p a r:t: (((SS)))=
T
Proof. Our proof proceeds via the probabilistic method. Let us sample I as follows. Let = n/T, and q (0, 1) be a parameter be chosen later. Let us define a Markov chain .i,.... fr on the state space {0, 1), with the following transition probabilities:
P(j++1 = 0 J: = 0) = - P(1+1 = 1 = 0) =r
PPi++1 0 j: 1) q
P(j++1 = jr = = 9
Letting r == 1-p the stationary distribution is P(j: = 1) = p.
We will let the subset I be I == {i = -
Computing the variance of [Z] The first step is to compute the variance of [Z]. By definition, (T 1)(1 p).
E|Z] (T r 1) p (T + 1)
Since the step transition kernel satisfies
Fli++ je 1]
q- (1=-(-)))((1pp)) (1p)++ +
we have that
2
B(ZZ)² E
Σ E(júvv]
T-r-1
(r + 1)2 + 2(T -1)(-=--11p +
Σ
(1- (1- r- p)p + +2²
;,'=1
(T+ + + 1D 2(T - 1)(1 - p)p > (1 9 r)
(T+
(E[Z))² 2T (1 p)
9 r
S ( 2Tp
(E 2n
Therefore [[[Z] - E|Z))² < 2n/q.
Decomposing the original expression. Next, bound the quantity
|=|
E
T Σ
pla. plan-rs
Σ pa ((zs())
Define Igap to be the of indices in I such that some index in {i Ty..., 13 is not in I, i.
Igap {i I 31 [ t I).
26

---

We write, denoting I = fdi,...,,zI
{ with 1 < i2 d.
|s|
|el
1
p ((gge) 1(i E (gap) +
p(a (( 1(e & Lgap)
7
|el
p p(a--ra
1(t E gapp) +
plo ((zg()) 1 & lgap)
pla ((zE 1le E I gap)
+
pa 1(l - T : CT).
n
7
Therefore we can decompose
F=
E
( 7 ((Fg))
Σ
plz rat ((zg)))
rat
T
t=1
r
a 1 (d- p(zg())
plagi)) 1(lt -1:1-7:00 ((t=):
n
T
T
(lt--na, (atti))-(((tttttttttt - c I) - - p(zz ((==-ra0 - 1([t 7 : CI)
1
E
GTE [gapl
(III)
Bounding (I):
Let us begin by defining the random variable
- T I T : c I)).
Z, = p(
The first term is then
E
Z
T Σ
T T-T-1
1
+
||
+ E
Σ
Z
i-T-T
1/2
G(2T 1)
1
T --T1 Σ
Z
n
T
1/2
G(27 +1)
1
T-r-1
Σ
|
2 + Σ
E(Z
Zj)
n1
T
t=7+1
441
First, see that
E| 2| < G²B
(1 (1- T
1(t - r ::(c
27
<
2T
p(1
-
9)T
T2
p(1 9)"
n²
G2T22
n²
G2T
27

---

Next, we have that
1 _ [[: - 7: (T) ( 11-2100- - }
T
B(Z;, 2,y1 G²
2T
T
=
p(1 q)" +
P([i r CZ
n²
= 1 - 2(1 - q)" +p 2 P(i : C Z, =z
Let's assume that <. First, consider the case where j 2 i + r. Then
P(l P( C [ - [: p(1 q)- PPj r - i E I) (1 ()-9)²
= pp(1 - 4) 25 (p + p1- - q - r) r))
and thus
2,,,, S Gº|1 - 2(1 - x)" + (1 - 9) + (1-
p)(1 -0)---))-0 ²)aT(1 q r)
(C- -) + (1 -1)
(1 -
s ( +p + (1-0) (tr)
Next, for j <itT, T, we have that
P(i - : - - c = P(( - -T: CI)
p(1 9)²
and thus
B,,,, S G 2(1 - q)= + (1 /)²-(t7|
< GPpp (1-9)-1 9)-tt
Altogether, (I) can be bounded as
1/2
11 G(2r +1)
G2T
+ +T Σ(1
(1-9)atr
+ T
n
n
ks0
G(2T + +1
GTT
1/2
TT2G2221 + 20TT2 1111)
+
n
n
G(T 1)
G
G
+
+Grg +
n
vn
vnq
Bounding (II): Let's next consider the (II) term. Since p is L-Lipschitz in its second argument, we have that
p(a--r.. 1(t-T: CI) 1 T 71
(II)
E 71
Σ
pla 1(t (1t--::0 T ([t-7:
[[] - p(zgnzz)) 1([ - T: : f] c I)]
Let's compute the fth term in this sum, for t E [ + 1,7 - 7 - 1] (for S r, the quantity is trivially zero, and for t 2 T
can bound by 0(1). We have that
E [[](((rge)
m( )|| 1[t 7 :] C [)]
Σl= Ez, 1(i Z)
E
((rra))
1(l [ CI)
In [t]]
u(age)) [I [t] - E Cz, I(E
1 7: CI)
p(1 E
I
28

---

The denominator is [ [t]] E 1(t I).
We first bound its conditional expectation:
ElIZn [t]l
[ =
Σ
P
2---1
(
Σ
(1 q - r))
pl.
Next, we can bound the conditional variance of the denominator:
Var( n [t] [(t = : C C))
Var(IZ - - 1([ - CT)
Cov(EZ,,EZIL-TEE
(1- (1-p)((11))) ",
+p)
E (1-9)²-)
1 (p+ + (1 - (1- - (1-1)) --
E (p+(1 (1 pp)(1 - ;)- i
(1-9)²-
jml
1-7-1
S5- Σ (p (1 - (1-)) -
SM (1---)) 1
Altogether, by Chebyshev's inequality, we can upper bound the conditional probability that the denominator small:
1 P(IZ n [4] S pt 1 ( < P(IzO [1] s 1 Bizz -00
2
4Var( n [t] [[t (((
B|I n |+]| [[)
pa *t+g"*
p²t²
pat + 12q212
A1
pqt
where the last inequality follows from the fact that the probability must be bounded by 1. Altogether, the éth term in the sum is
E [[]lu(age)) - u(manz)) I(l ( T : [I]
E ((=ss)) - Izn [t]l - ez, 1li E ED)
1[[ [[[t-r:oo CI)
(HAD)
t
The numerator the above expression can be written as
E
I) - p).; m(ag)))
1(t - [1]-r((c1)
E
Σ Z
1 T [(
29

---

where Z; () j<
- p)(e,, (((zs))). For i,j < t- have the bounds (assuming WLOG
-(1-p)(1 ||, ",
+ p) +
-T)))
S p(1 9)-
Therefore,
1/2
(-T-1
E
Z
1(t 1(ttr: cI)
ST +++1+E
Σ Zi
1[ T: T: II
i=1
1/2
11+1+
tp + (1
i
1 v vp//g.
Putting everything together, the tth term in the be bounded by
E (((x(( ((=))nz)) 1(t - CI) ( (1 Ap) q1
(1
1/2 +
A p.
qt
where the last line uses the fact that the entire expression be trivially bounded by O(p). Plugging back into the original expression for (II), this term can thus be upper bounded as
L t=
1/2 1 (T+ (1++)++2 +r+1)+t1/2p) 1/2
Lr
Apt
gt
<Tppq ++1++ - AD) n
Lr
L
(VTp/q + /Tp//+++++'+ log (=
L L(T + Llog Vng
Bounding (III): Finally, for fixed E [r +1+1 1), we have Pii E Igap) p- p(1 - z
pqr. Therefore we can bound (III) as
< GiElIgapl
G(T 2T) < +
MIII
n
n
Putting everything together.
Altogether, we have that
T
[x| plz p((a
(G (G+ L)
G+L
logn n
+
Grq +
T
n
/nq
n
(G+ L)+
1/3
where the last inequality follows from choosing
q -1/3
30

---

By the probabilistic method, there exists I such that [ 2n 133 and
E
I 2n
n $ (1+1+
1 |sl
1 T
pla m.
Σ
piz ((zs)))
x
(G +)+++) +1)
1/
For this choice of I, we have that
1=|
pl (0t (
pl 2 m m(zs)))
[2]
GG + L)(T +1)
|2|
V2
p ((=rr,)(((s))
n/3
(G + L)(T + 11
22
n 1/3
as desired.
B.2 PROOF OF THEOREM 5.2
The proof begins by showing that the output of the first layer of attention at position can only depend on the histogram of the first tokens u( along with the 7-prefix of zg1
Lemma B.I. Let be fixed transformer with key, query and value matrices {KK 1. Q1oo V VIN))eem U 2(K,,,1 Q2,1 22,1}. MLP weights {AA,, Bi) Be),2) embeddings
EEll S 1, and unembedding U. There exists a function qs : [S] x A x N. + Idd such that
y of (2. riiy i)
Moreover, f satisfies
(1( S
1+ Σ
V i. (1+ |B G₁
h=1
Σ exp (a| Q1.1 (1.)))))) =: H min(i.
11
19,( u4 i) ( m.ji S
11+ B
| 1lap (7²
(72 + min(i,)))
A=1
V 1,0 lpp exp [ll (2.l))
(1
[,g (1) 28
Σ
||+|BBnb B Alllop) Ls
Proof. Recall that the first layer self-attention logits are
(1.h)
B.g
K T
Q Ex, + logi (1.
31

---

and thus we can rewrite y!!)
y
Σ Zj=11 exp (i,)
(1,b1)
V in Esy
Ez, +
Σj=1 exp (/as)"
(1.1t)
j= exp Es, K,, Q 11, (ola(t.) VIA
Ez, +
Σj= exp Eyg K QI, (j0166.)
h=1
Exi+
H Σ
EvEls exxp
E K K Q1,1 V EongEl + EEjo- ((0r.(.))) - 1) exp
E K.K Q1,1 VInh
ExE[s] iexp E. K (1n p(agi)) + Ejoi.r (10Lu(6i)) - 1) exp
E K 1, 11,1
4=1
N₂
Ez, +
Dn
where for each h, we have
(x(x) = Σ
th exp E. KT,, Q1, VinhEs(EEsss
+E|S]
(o), -87 ) exp E KI,, Q1, VInEE
j=i-T
Dn(x) Σ
th exp E K.K,T Q1,1 p(agi))
Σ
(p exp E KI Q1,1
+E[S]
f=
Th = m1
max @i - 1, = max Ph
0515T
Therefore we can write y!") = (SA () i), where for wer E |S] . E AS (SA(W, (w, μl, i) is given by
H (4,
(sa(w, Em,
Da(w, (4,
where
(u(w,p,1) p1 :=
Σ
exp E K.K. 12n, Vi,nEsp
sE|S]
( - mm) exp E K.K. Q2,1 V Vi,nE...
+
t=
Dz(w,p, = Σ
2h exp E LIn Ms +
Qu,
Σ
- exp E K.T.I.. Q1 Eus.)
(
+E[S]
1=U
Each Na(w,, μ. i) Dr. (w, μ, i) term in the above sum is of the form of the expression in Lemma B.2 First, we see that each denominator can be lower bounded by exp (-I|KT,n Moreover,
we have
Σ || (T 1 loop exp [ ( (KI.Pranloo)
b
(
Bal S (T++1)
32

---

Altogether, since y := x(f) minkeR (m max (p Ph : # mm,)), we can bound
Igsa(w,14 14, gsalw, 14 S (1)++)) Σ exp
[T|KTTnQ.. QLn
h=1
Next, see that y/ QMI.P (.), where
(MLP(x) x B (A1x x b1).
Since 1 is I-Lipschitz, PMPP + Billop |Alllo Lipschitz. Altogether, since q, pr, i) (MLP(qSA(U)) ur ()) we have
(7 1)j exp #4|KTT.L.M. Pin l
lay(w, p, os (w, (.J, S (1 B1 llop A1 Aillop)
Next, for the uniform bound, observe that
Y (1)
11++h=1
II lop and therefore 1 10!01
(L+ (i (1 + | A op)
Finally, we compute the Lipschitz constant with respect to
Let Mr E Rdxs be the matrix with the sth column being exp
E K Q1, Bw, Vin
let by the vector with sth entry exp
E. 1, Q1 Bw.). and let Ch =
> 0. We have that Ex (johalie - mm) exp E we K 21 Eu.
H = V Vp9SA(w,,H.))
i1-98 Mn i1 (bi: p4) + Ch
22 mm Mnub] (i1-24 (bn. + Ch.)
h=1
01 (=
and since (bn, 11) 2 exp
and
[| and ||b1|| s vBexp (|KTT10..111))
|| op S V exp
we have that
H S
Σ Vinllop exp | Q1mll (1n
V (,,
Altogether,
H
KIIKAA... (1o) (1 (1
[[Vngs (n,s( il) < 25
V i.lllop exp
In order to prove the main theorem, it suffices to apply the key simulation lemma Lemma 5.3
Proof of Theorem 5.2 logits are given by
Let f.g E Fr be two transformers. In the forward pass of f, the second layer
(2.1) a j
(
KI (((=)-rs "e Metee
and therefore
y(2) of (MT
T exp qs ( ((D KJ, (0. (1n ((
+ V211
Σラ= cxp ((( T T
T
1=1
33

---

The analogous expression holds for the second layer logits in the forward pass of Let us define the following sequence of functions:
po(w, (1) Ev
Ps, (w, pi) (q,(w,,, 12, (el
Pf,a(w, p4) (r,l(,,))qq(u
along with the analogous Pa. P9.2 for the transformer We first see that |/pol| S and po is constant
jr.
Next, we have that we can uniformly bound Pf.1 by
Pr. p)1 S exp G7 K Q2,1 1.n)
and the Lipschitz bound
V vaPri(W.H) p1) exp exp(9)(u,,))) p. K2, Q2,19/ (1)- 1)) (u. (21 M(x).,
G3 K Qz 11n)
V (P exp
K2 Q2,1 G,L,
Finally, for PS.2 have the uniform bound
(, 10) exp (2))))))
and the Lipschitz bound
V TPPre(u.p) (r, V ,1 T) + VuPi(w: (w..))g((s m)
VPPr2 w1)l S exp G K _ 22 1,)) KK 22 G3
Define the quantity M,
My:=exp (0) K 22 kp)
| Q2,1 |
G
op
and analogously for Mg.
Let us define the function p by
MyMg po(w.
G,M, p)i(w,
p(w, n1)
Mg (s,((
MgGi (o,(
M, Po.2(w.
34

---

p is both uniformly bounded by and has a Lipschitz constant of My Therefore by Lemma 5.3 we have the following bounds:
1
T+1
E
Po Po(
po マリj (((S)))
T
n//3
(T
1
Pf.1 Pfa( ((
py. (2) (2 ((25)))
22
T
[2|
1/3
|=|
Σ
My MT +
T
|<|
1/3
==1
|e|
GgGgi g
(T +1)
Σ
py. (x.(
Pg. (2)- (2)-73
24
T
1/3
T
|=|
MT + 1)
Σ
2g.2 (T) (og
Pa. 2 Zz mリ Ml m(z5)))
2
T
n²/3
2=1
Let's first look at po. Observe that
T
T
Σ
po (())),)
1
Σ j=
Cay u(x))
7
T
and therefore
[1(x)) - -x(=)] =
1 T
Σ
T
Po ( (((
1=| po(Ej-ry m(3:))
S
++1 1//33
Next let's look at Pf.1. We have that
I
exp (xp())
"K ( T E Ennles-rs
1
T
exp
T Σ exp 07
K2 22.1 22)1(1))
K2 Q.
G H
op
= exp G2 K2 22 )
Kg K5,10211 22
G.. (T)
where we're letting (T) = Ex
35

---

Next, note that
exp
T K2, 10
p (3)
C7 K2 22.1 (0033--r)3s))))) / (a
exp
j=1
(z(
((
K (2
11
G7 K2 22 1l,)
K2 |
exp
J=1
+
|190(2
(3), (z1) - 91 -1
=1
Σ exp
c7
K2 22 Gr K 121 (H₂j + +,,1 + +syllu(=) - m(x)ll)
S exp G?
Sexp
K 22.1 22ul(o))
)
G, K2 K2,122.1 22.1
(1=) + L,(T (n(( + 1)n 1)m-1/3)
Altogether,
exp
|=|
1
exp as (((2)))))) K (12 (12))))))
|2|
S
exp
G
up |, KT Q2
G,
K2 22 Il,p (H]S)en(())) + [,((T 1)m 1/3
T
+
Σ
pl.
(0
1
P)a(3)-
12
j=1
exp
G
K 2,1 Q2
(T(
1/3
S exxp
c7| Kg.
22
)
( (H)Ssen())+ + Lg(T + 1)n=
Similarly, can bound the numerators by
exp (ep(a)(00--s
T
|=| exp
|
j=1
2 exp
G3
KJ 22 op
11. 03
|0/
K Q2,1
(H 1)m
Finally, we bound
(1T ((x),, T) - ((2))) < T.)ll(()) - -+=)) + H -))
S Ly(T + 11/3 + H Hnm))
36

---

Altogether, relate ( (x) and Y (=) by
r (2) (z) (x) exp 4G7 K2 2.1 Q 11m)
G3
K2 02.102111
Ly(T + 1)n 1)3)
Finally, we have that
(1(x)) [())1 < |0|| (1 B2llopp Azllop)
| 7 -Y - (=)
Plugging in the expressions for Gy. L H,, and noting that (n) 2 -1133mm)) yields
[lf(x) - f(=)ll 2 <c(fmm
where
2 V 1.lllp
)
C())
exp
c1 1+
C
Σ
(1+ ++1lBBllopp 1olIBBlloAAAill. Apllop )² K2 22.1 op
(1+ ||| (V2lop)))))
H
(4 [T[KT, Q0 (10T))
|1 |l Al (1+1Blllllll
x
IVV IV
exp
U op( + 1)S.
Repeating the above argument for the transformer g, we have that
(g(x)) g(>)ll S C(g)n ((())1(133776)))
Combining these together implies the desired result.
B.2.1 HELPER LEMMAS
Lemma B.2. Let f(1 be of the form
Ex Agi En BRi-T
f(1)
where As E TRd and Ee Bgi 2 8 for all i. Assume that O = 71 < 722 ... < Nk. Then, for
j <i, i,
(((--f01l 58 Σ |lelll
ΣlBal
Proof. One write
|1Ex Agt
1Ex BLj 1k)
(E Agj ) BBi )|
llf(() f(i1l
1<Ex -ai-m))) >) B
< 2
[A myg
< 8 2 2- -2
Σ |LAbIl
Σ |LRRl
B.3 IN-CONTEXT k-GRAM CONSTRUCTION
Below, we sketch the in-context k- B-gram construction, which closely follows Construction 2 in Nichani et al. 2024).
In the first layer, the h-th head will attend fully to the (i - h)-th token; this done by setting Φ1 A (i h, to be large, and the rest of the entries of ø. along with K1A h and Q equal to 0. By
37

---

choosing embedding dimension of d (r + 1)S, the value matrices V1,h 1,6 be chosen such that y Es, + Eu,-1 @ ... + E _ ; this accomplished via V1.5 being a block identity matrix, which thus satisfies IV
1, op 1. The first layer MLP is then set identically zero, that
( = Y
In the second layer, K2, 22, is equal to 3 times another block-identity matrix, which compares the E 4 ... Ex, subspace of y (1) to the Exy 2 ...0. Ezr- subspace of (1) This places an attention weight of e each token i with 2;-r:i-1 -r--++111 and weight of at most (3-311)
on all other tokens. Finally, the second value matrix 2,, copies from the Ez; subspace of y, while the second layer MLP is also zero.
Altogether, the output of the transformer is
ex E; 10
8) + EN..
[(IIT)
@ Σ 10 ED
where |Ev],, [Epl & TT Therefore
T
[If(z1T) - (f e² E, 121 = IT 27-7+1:7)
On a "typical" sequence x, E; ( = -1-7-1 = =((T), which case
[ - 5e 85
whenever B x log(1/s). Therefore
K K2 K2102.110 O(log(1/E)) Plugging in, this yields
complexity measure of
C(f) exp (Ck2 log (1/E)) = -B(3))
C
EXPERIMENTAL METHODOLOGY
Data Generation:
SimpleTask: Each sequence T1.T is generated by first sampling a probability vector E R uniformly random over the simplex, then sampling each r, ii.d, where S; with probability p.- This ensures that Var(f*) = (()). We vary between 2 and 5.5 in intervals of 0.5.
ModPTaak: Each sequence .1.7 generated by first generating 4o..... i.d uniformly from [0, 1]. Then, each x; is sampled from Bernoulli(pk), where k = mod This ensures that Var(f") (1), and also that attending incorrect positions mod p cannot help the model. We vary A from 3 to 8
In-context k-gram: The data generation follows that of Nichani et al. 2024 Each sequence vir is generated by first sampling k-wise transition tensor и [S] where for any 21:k-1 the distribution T(- (i:k-1) 1) is sampled uniformly at random over the simplex in S dimensions. Next, 21:k-1 are sampled uniformly at random. Finally, for > we sample T(. -i=kii-)- To ensure that -T-A- --1-7 occurs at least once in the sequence, we randomly select an index i E k T 1). and replace Ti-k+1s with - We fix
k = 2 and vary S from 3 to 8, and also fix S = 2 and vary ls from 2 to 4.
Training Procedure:
Single-layer transformers: The model architecture is one layer single self-attention head followed by MLP. The embedding dimension is d 16 and the MLP width is 256. We use the μP initialization Yang et al. (2022), and train using the Adam optimizer with learning rate 10 2 /d for the hidden layers and 10 for the embedding layers. We train all of the models using online SGD (sampling a fresh batch of size 1024 at each step), until the training loss crosses below 10-5 All results averaged over 8 random seeds.
38

---

Two-layer transformers: The model architecture is two-layer transformer, with i: heads in the first layer and one head in the second layer. The embedding dimension is either d = 32 (when &
is fixed and S ranges from 8) d 16 (when S 2 and k ranges from 2 to 4). We use the j&P initialization and train using the Adam optimizer with learning rate 1) 3 10-2 /d for the hidden layers and v 10-2 for the embedding layers, on a fresh batch of size 1024 at each step for 2 steps.
The k = results are averaged over results averaged over 14 random seeds.
8 random seeds, while the
C.I EXPRESSIVITY OF SYNTHETIC TASKS
We sketch the constructions for each of the synthetic tasks in Section 6
SimpleTask: Set p; and Eo. E,, E2 orthogonal. Choose K Q so that aij = oo when j = 0, and dijj 0 when j = 2. The attention probabilities will then be uniform over all
and tokens, and thus the output of self-attention becomes YT = Eur + co()){a)())
ep(x) VE
eol [x) VE We can then set V Eo - E1. It suffices to approximate the one-dimensional function - sin(wz) with MI.P; it well known (Barron 1993 that this be done with
(ar
weight norms (ww), as desired.
ModPTask: Let {q: (EE(A) be some fixed set of orthogonal embeddings, and let p; be equal to Jj where i + mod p. These are periodic embeddings with periodicity A = Choose K Q so that 0zj equals oo if j k mod p and otherwise. The attention probabilities will then be uniform over all positions which are &o mod p. Choosing V so that Vg. 0 for all j. the output of self-attention becomes Yr- yr + (*1rr) VEE + (1 (x(T)) V Eg. Choosing the readout layer appropriately, we can ensure that T(x)T f (ZITT) desired.
39


Reviews:
[{"review_id": "q4bjKk42tk", "reviewer": "Reviewer_F5Ex", "summary": "This paper focuses on the problem of length generalization (LG) of Transformers - i.e., the ability of a model to maintain its performance on unseen long sequences after being trained on short sequences - and for the first time gives quantitative bounds on the length of the training sequences required to achieve LG. The study covers a variety of scenarios, with the core logic that LG can be achieved when the internal behavior of long sequences can be “simulated” by short sequences in the training set. The paper clarifies the correlation between training length and model parameter paradigms, period Δ, locality T, etc. through theoretical derivation, and verifies the conclusions through synthetic tasks such as SimpleTask, ModPTask, etc., which provide theoretical references for scaling the length of training contexts of Large Language Models (LLMs).", "questions": "see Weakness", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The length of the training sequence required for LG is quantified for the first time, addressing the key issue that previous studies have only demonstrated the “existence of a threshold” but have not clarified the “size of the threshold”.\n- The conclusions are more broadly applicable by also considering a variety of variables such as the type of accuracy, the number of model layers, and the way the error is controlled. Covers many different types of theoretical scenarios and explores the quantitative issues regarding generalizability in a comprehensive and detailed manner.\n- The boundaries are established by rigorous mathematical derivation and then verified by a synthetic task with high confidence in the conclusions. The theory is paid to the experiment, and the correctness of the theory is effectively verified through the results.", "weaknesses": "- Very interesting paper that gives a quantitative analysis of length generalizability, based on the theoretical framework of the “limit transformer”, and therefore lacks an analysis of the transformer scheme with relative positional coding, which is currently more used in various methods.\n- The paper verifies the correctness of its theory on a small-scale transformer structure, and it is hoped that the paper will give further analysis on whether there are limitations in the analysis and experimentation of larger models.\n- Are the complex model parameters on which quantitative analysis relies also greater in more complex models? Does this create bottlenecks in analysis for larger models? Hopefully the paper will give at least a qualitative judgment.\n- Although I have the above doubts, I nevertheless think that the work in this paper is solid, informative, and importantly groundbreaking for the study of length generalizability, and I therefore hope that the authors will be able to give at least a qualitative judgment on the above doubts.", "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": "vQPrryYe30", "reviewer": "Reviewer_96HU", "summary": "The paper builds upon the theoretical constructions (Limit Transformer) and the conclusion in  Huang et al. (2024)  - that Limit Transformers can achieve Length Generalization if trained under sufficient length for at least (if not at most) class of problems that can be expressed by a C-RASP program. This paper attempts to go beyond that conclusion and also provide quantitative bounds for the required lengthts under different settings - such as infinite-precision vs finite-precision attention or different error controls, single-layer and 2-layer transformers. \n\nThe key level idea used for the proof is to construct a simulation map from strings of arbitrary length to strings of bounded length.", "questions": "n/a", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Generally well written and well connected with the literatur. \n* Provides theoretical proof to support quantitative bounds for required training length\n* Provides some empirical support that error rate at which test loss plateus decreases with increasing training length.", "weaknesses": "Not any significant blocker to acceptance to my awareness. One could question the practical impact or limited scope, but it is targeted as a theoretical paper under learning theory - and seems to sufficiently fulfill its targeted goal. There are precedents of papers with similar scope getting accepted. \n\nBesides this, one limitation is that the study is mainly tied to (periodic) absolute positional encodings (as far as I understand) - but the authors keep studies of other positional schemes for future work - which is fair enough.", "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": "rYHP4nmglJ", "reviewer": "Reviewer_77Hi", "summary": "The authors provide the first non-asymptotic quantitative theory of length generalization (LG) in transformers, establishing explicit bounds on the minimum training sequence length $N$ required for a model trained on short sequences to generalize to arbitrarily long ones. In the finite-precision (hardmax) regime, Theorem 4.1 shows that for one-layer $\\tau$-local, $\\Delta$-periodic limit transformers, if two models agree on inputs up to length $N = O(\\max{2^{p/\\gamma}, L^{2}\\Delta^{7}|\\Sigma|^{6}\\tau^{2}\\varepsilon^{-2}})$, then they agree within $O(\\varepsilon)$ on all longer sequences, with $L$ being a Lipshitz style upper bound, $\\gamma$ the attention logit margin, and $|\\Sigma|$ the vocabulary size. Theorem 4.2 extends this to average-case error control, showing that under regular input distributions, $|f-g|{T,P} = O(\\varepsilon^{1/2})$ for all $T \\ge N$, with $N$ scaling polynomially in $L, \\Delta, \\tau, |\\Sigma|$. In the infinite-precision (softmax) setting, Theorem 5.2 introduces a complexity measure $C(f)$ containing exp and poly factors in the norms, and and provides the equivalent characterization of the length $N$ for LG in two-layer transformers, implying exponential dependence on the inverse positional margin, which although will be huge in general. All proofs rely on a unified simulation argument constructing a short sequence $z$ that preserves the sufficient statistics of a long sequence $x$ so that $f(x)\\approx f(z)$. Empirical studies on synthetic tasks (SimpleTask, ModPTask, and in-context $k$-gram) validate these scalings: test loss plateaus at finite lengths, decreasing with training length. Collectively, the results establish that the capacity for LG in terms of the model parameters and the usual error tolerance, providing a rigorous quantitative framework linking transformer parameters to their extrapolation behavior.\n\nNote the questions and concerns I have raised below.", "questions": "1. What exact upper bound for the Lipshitz constant are the authors using to support the argument - “This is unavoidable, as the Lipschitz constant of the first layer softmax scales exponentially” - line 366 on page 7. To my understanding, there have been various proposals for the upper bound such as [1-3], some of which not scaling exponentially. \n\n2. Can the authors clarify the argument - “One observes that f ∗ is expressible by a one-layer limit transformer with no positional embeddings and L = Θ(ω).” from line 418? More specifically, how was this bound achieved for L and similarly in line 424 for the ModPTask? \n\n3. The left subfigure in Figure 1 on page 8 is interesting – the smaller values of ω exhibit larger test loss across all lengths. I am curious to understand the authors’ discussion on this, because either using the bounds from this paper, or using standard generalization bounds, for smaller ω, a smaller test loss across all lengths is expected. Looking forward to this response in case I made a mistake in my understanding. \n\n \n\n[1] Kim, H., Papamakarios, G., & Mnih, A. (2021). The Lipschitz Constant of Self-Attention. In Proc. ICML 2021, PMLR vol. 139 \n\n[2] Castin, V., Ablin, P., & Peyré, G. (2024). How Smooth Is Attention? (ICML 2024). Proceedings of Machine Learning Research vol. 235 \n\n[3] Wang, Y., Chauhan, J., Wang, W., & Hsieh, C.-J. (2023). Universality and Limitations of Prompt Tuning. In Advances in Neural Information Processing Systems 36 (NeurIPS 2023).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The Dirichlet assumption in Theorem 4.2 is a good choice, as classical NLP literature has worked with it for decades in many practical applications. This makes the contribution of this work more practical\n\n2. The authors' efforts in studying both finite and infinite precision and also providing bounds for L_{inf} and average case for finite setting is a good contribution to this line of research.\n\n3. I found Lemma 5.3 to be a useful addition. While I did not read the proof end to end, this is a good supporting lemma of independent interest - assuming that it does not exist in the literature in a similar form yet.", "weaknesses": "1. I have a concern about the value of N - $2^{\\frac{p}{\\min\\{\\gamma(f), \\gamma(g)\\}}}$ . While I understand the requirements for the proofs, I am curious if the authors have some thoughts on adapting equation 2 on page 13 – for say cases where the logit differences can be binned and perhaps some covering number arguments can be used? Please note this is just a rough guess and I have not put proper thought behind this statement, and I am just curious about the ideas from the authors’ end. \n\n2. In line 1024 of page 19, while the triviality of - |Σ|^3 + τ ≤ |Σ| ^ X τ , why was it even necessary to loosen the bound by such an extent. Furthermore, for a good number of practical datasets where |Σ| = O(τ), this unnecessarily loosens the bound. Again, curious about this situation.", "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": "zHsARy6Ygh", "reviewer": "Reviewer_dyQR", "summary": "The paper provides quantitative bounds on the required training sequence length for transformer models to achieve length generalization by proving that this occurs when the model's behavior on longer sequences can be \"simulated\" by its behavior on the shorter sequences it was trained on.", "questions": "Typos:\n- Line 133: “denote allow”.\n- Line 441: “value the test loss” -> “value of the test loss”", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper tackles an interesting and important aspect of length generalization, namely the minimum training length to enable it, given a task.\n2. The paper takes care of the finite-precision arithmetic that is used in practice, something often overlooked in theoretical work.\n3. Overall the paper is generally well-written and explained. Intuition and remarks are provided after most mathematical definitions and results which makes it easy to follow the reasoning and the motivation.", "weaknesses": "1. I am missing a comprehensive discussion on the limitations of the paper’s analysis, especially on all the technical assumptions and simplifications on both the class of tasks that is considered and on the architectural modifications. \n2. The introduction of the $\\phi_{l,h}(j,i)$ terms in the definition of the limit transformer appears to be a significant difference from standard attention. And contrary to what is said on line 133, it seems that they can only capture dependencies between the positions, not the content. At any rate, the paper would benefit from explaining why allowing for more expressive dependencies than the bilinear interaction of classic attention is negligible for the properties of the hypothesis class.\n3. The definition of translation invariance is also a bit strange as nothing prevents positional information to also flow through the $\\mathbf y_j \\mathbf K^\\top \\mathbf Q \\mathbf y_i$ term.  Perhaps it would be neater if you separate the input embeddings and the positional encodings as two separate components rather than adding them together.\n4. The experiments and the corresponding plots can be explained more clearly and in more detail. The subplots are missing captions which could clarify what is being plotted and the first subplot is missing indication on the legend as to what the different lines are showing.", "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 (Oral)