Length Generalization Bounds for Transformers

Transformers and C-RASP programs define the exact same class of languages.

“because transformers and C-RASP programs define the exact same class of languages (cf.Yang et al., 2025, Theorem 3.1)”

• cites Yang et al., 2025, Theorem 3.1 sourcePartly supported

  Theorem 3.1 (Section 3, p. 5) establishes an exact, depth-preserving correspondence between the languages defined by TL[↼#]—which the introduction (p. 1) identifies as equivalent to C-RASP—and those recognized by a specified fixed-precision transformer. The claim omits that restriction: Section 2.1 (p. 3) specifies rounding except inside attention, future masking, and no positional encodings. The theorem also states the correspondence with a <BOS> prefix. (LLM, conf=0.90)

  Experimental — accuracy not yet measured

Chen et al. consider a restricted subset of programs, notated C-RASP 2,K,T.

“However, this is because they consider a restricted subset of programs, which they notate as C-RASP 2,K,T .”

• cites Chen et al. (2025) sourceSupported

Non-asymptotic length generalization is equivalent to the decidability of the language equivalence problem for any finite class of languages.

“we use the fact that non-asymptotic length generalization is equivalent to the decidability of the language equivalence problem for any finite class of languages (Chen et al., 2025, Lemma 3.4,Theorem 3.2).”

• cites Chen et al., 2025, Lemma 3.4,Theorem 3.2 sourcePartly supported

  Section 4.2 (Lemma 4.5; page unavailable) states that decidability of language equivalence is equivalent to non-asymptotic length generalization for the full class represented by an encoding system, provided the complexity measure satisfies Assumption 3.7. It does not state this equivalence for any arbitrary finite class of languages; the cited lemma and theorem numbers also do not match those in our copy. (LLM, conf=0.87)

  Experimental — accuracy not yet measured

There are finitely many positions where the weighted average of values by attention scores can be nonzero.

“As observed by Li & Cotterell (2025) and Merrill & Sabharwal (2023), there are finitely many positions where this can be nonzero.”

• cites Li & Cotterell (2025)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Merrill & Sabharwal (2023) sourcePartly supported

  Proposition 1 (Section 3, p. 5) bounds the number of nonzero entries in a rounded p-precision attention-weight vector by 2^(2p). This supports a bound on positions contributing through nonzero attention weights, but only under the stated finite-precision condition; the cited sentence leaves that condition unstated. (LLM, conf=0.86)

  Experimental — accuracy not yet measured

Dyck languages of bounded depth are not expressible in C-RASP 2,K,T, for any K and T.

“Dyck languages of bounded depth are not expressible in C-RASP 2,K,T , for any K and T .”

The exponential length complexity bounds for positive C-RASP and fixed-precision transformers are optimal.

“For both positive C-RASP and fixed-precision transformers, we show that the length complexity is exponential, and prove optimality of the bounds.”

C-RASP+ is equivalent to fixed-precision transformers.

“This is shown using the expressive equivalence between fixed-precision transformers and C-RASP + , which is a corollary of the equivalence between fixed-precision transformers and TL[-3] (cf.Li & Cotterell, 2025), and Proposition 4.4.”

• cites Li & Cotterell, 2025Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The length complexity of C-RASP programs of depth 2 is not computably bounded.

“This applies even to C-RASP programs of depth 2, as the formulas discussed above are all of depth 2.”

To perfectly learn a C-RASP+ program P, given an upper bound on the size of P, it is necessary and sufficient for training strings to have length exponential in the size of P.

“To perfectly learn a C-RASP + program P (given an upper bound on the size of P ), it is necessary and sufficient for training strings to have length exponential in the size of P .”

For fixed-precision transformers, a similar exponential length generalization bound exists in the size of the transformer.

“Similar exponential length generalization bound exists in the size of fixed-precision transformers.”

The exponential bound in Proposition 4.6 is optimal in the worst case.

“This bound is in fact optimal in the worst case.”

For every C-RASP+ program P with L(P) nonempty there exists a string w in L(P) of length at most exponential in the size of P.

“For every C-RASP + program P with L(P ) ̸ = ∅ there exists a string w ∈ L(P ) of length at most exponential in the size of P .”

It is undecidable whether a given C-RASP program defines the empty language or not.

“It is undecidable whether a given C-RASP program defines the empty language ∅ or not.”

In general, C-RASP can be reduced to C-RASP with two layers while preserving language nonemptiness.

“We remark that in general, C-RASP can be reduced to C-RASP with two layers while preserving language nonemptiness.”

For fixed-precision transformers, the length complexity is exponential.

“For both positive C-RASP and fixed-precision transformers, we show that the length complexity is exponential, and prove optimality of the bounds.”

Bounded-depth Dyck languages are straightforwardly expressed by C-RASP 2 with bounded size.

“On the other hand, bounded-depth Dyck languages are straightforwardly expressed by C-RASP 2 with bounded size, like in Example 2.3.”

There is no algorithm for perfectly learning a C-RASP program P, given an upper bound on the size of P, even if P only has depth two.

“There is no algorithm for perfectly learning a C-RASP program P (given an upper bound on the size of P ), even if P only has depth two.”

The length complexity of C-RASP is not computably bounded.

“The length complexity of C-RASP is not computably bounded.”

There is a computable length generalization bound for the positive fragment C-RASP+ of C-RASP.

“To complement this, we provide a computable bound for the positive fragment of C-RASP, which we show equivalent to fixedprecision transformers.”

For every C-RASP+ program of size n, depth d, precision p, and girth g there exists an equivalent TL[-3] program of size O(n^2 poly(p,g,d)).

“For every C-RASP + program of size n, depth d, precision p, and girth g there exists an equivalent TL[-3] program of size O(n2 poly(p,g,d) ).”

For every TL[-3] program P with L(P) nonempty there exists a string w in L(P) of length at most polynomial in the size of P.

“For every TL[-3] program P with L(P ) ̸ = ∅ there exists a string w ∈ L(P ) of length at most polynomial in the size of P .”

Any equation x = c, x + y = z, or x • y = z can be encoded by a language definable in regulated C-RASP.

“Any equation x = c, x+y = z, or x•y = z can be encoded by a language definable in regulated C-RASP.”

The length complexity of C-RASP+ is exponential in the size of the program.

“The length complexity of C-RASP + is exponential in the size of the program.”

There is no computable length generalization bound for C-RASP, already with two layers.

“Our main result is the non-existence of computable length generalization bounds for C-RASP (already with two layers) and hence for transformers.”

For every C-RASP+ program of size n, depth d, precision p, and girth g there is an equivalent decomposed C-RASP+ program of size O(n^2 poly(p,g,d)), depth O(d), and precision O(p).

“For every C-RASP + program of size n, depth d, precision p, and girth g there is an equivalent decomposed C-RASP + program of size O(n2 poly(p,g,d) ), depth O(d), and precision O(p).”

For positive C-RASP, the length complexity is exponential.

“For both positive C-RASP and fixed-precision transformers, we show that the length complexity is exponential, and prove optimality of the bounds.”

For any languages L1,...,Ln over Σ such that each Li is definable in regulated C-RASP, the language L1$L2$...$Ln is definable in C-RASP.

“Let Σ be an alphabet and $ ̸ ∈ Σ.For any languages L 1 , . . . , L n over Σ such that each L i for i ∈ [n] is definable in regulated C-RASP, the language L 1 $L 2 $ • • • L n is definable in C-RASP.”

Lemma B.3: Let Ψ be a set of C-RASP programs ψ of the form α_ψ ↼#a > β_ψ ↼#⊤. There exists a constant ε_{k,Ψ} such that for all ψ∈Ψ and all w∈D_k, either (↼#ψ)_{w,i}= i ± ε_{k,Ψ} for all i, or (↼#ψ)_{w,i}= ±ε_{k,Ψ} for all i.

“Lemma B.3. Let Ψ be a set of C-RASP programs ψ of the form α ψ ↼ #a > β ψ ↼ #⊤. There exists a constant ϵ k,Ψ such that for all ψ ∈ Ψ and all w ∈ D k , either ( ↼ #ψ) w,i = i ± ϵ k,Ψ for all i, or ( ↼ #ψ) w,i = ±ϵ k,Ψ for all i.”

Theorem B.4: For all k, D_k is not expressible in C-RASP_{2,K,T} for any K, T.

“Theorem B.4.For all k, D k is not expressible in C-RASP 2,K,T for any K, T .”

• AssumptionRests on an assumption: D_k is a proper subset of D_{k+1}.

Transformers, even with two layers, do not admit non-asymptotic length generalization.

“Transformers (even with two layers) do not admit non-asymptotic length generalization.”

C-RASP_2 has uncomputable length complexity.

“we show that C-RASP 2 has uncomputable length complexity.”

Proposition D.1: There is a satisfiability-preserving reduction from C-RASP to C-RASP with depth at most 2.

“Proposition D.1.There is a satisfiability-preserving reduction from C-RASP to C-RASP with depth at most 2.”

Fixed-precision transformers admit length generalization.

“In contrast, by bounding the precision within attention, we find that fixed-precision transformers do admit length generalization.”

Theorem C.11: Let φ be a C-RASP+ program with precision p, depth L, and size d. There exists a fixed-precision transformer T with precision O(p), depth O(L), and hidden dimension O(d) which simulates φ.

“Theorem C.11.Let ϕ be a C-RASP + program with precision p, depth L, and size d.There exists a fixed-precision transformer T with precision O(p), depth O(L), and hidden dimension O(d) which simulates ϕ.”

• AssumptionThe authors state this as an assumption: The constants in all defining functions of a transformer are given in binary and the precision is given in unary.
• AssumptionRests on an assumption: There exists a fixed-precision representation F containing 1/k, k, and a value x such that round(exp(x))=0.

Fixed-precision transformers admit length generalization with exponential length complexity.

“Fixed-precision transformers admit length generalization with exponential length complexity.”

Lemma C.9(b): There exists a TL[-3] program P_{x=y}, where y ∈ F^d not depending on w, such that w,i |= P_{x=y} iff x_i(w)=y, with size pd.

“(b) P x=y , where y ∈ F d (not depending on w) such that w, i |= P x=y ⇐⇒ x i (w) = y with size pd.”

• AssumptionThe authors state this as an assumption: The constants in all defining functions of a transformer are given in binary and the precision is given in unary.

Bounded Dyck languages are not expressible in C-RASP_{2,K,T}.

“We prove that bounded Dyck languages are not expressible in C-RASP 2,K,T using a geometric argument.”

C-RASP of depth 1 has an exponential lower bound.

“while we show an exponential lower bound for C-RASP of depth 1.”

Fixed-precision transformers can be converted to exponentially large equivalent TL[-3] formulas.

“Fixed-precision transformers can be converted to exponentially large equivalent TL[-3] formulas.”

The length complexity of fixed-precision transformer with precision p, dimension d, and depth L is O(2^{poly(p,d,L)}).

“The length complexity of fixed-precision transformer with precision p, dimension d, and depth L is O( 2 poly( p,d,L) ).”

The length complexity of fixed-precision transformer with precision p, dimension d, and depth L is Omega(2^{poly(p,d,L)}).

“The length complexity of fixed-precision transformer with precision p, dimension d, and depth L is Ω(2 poly(p,d,L) ).”

C-RASP_{2,K,T} is strictly distinct from the full class of depth 2 programs C-RASP_2.

“We will show that C-RASP 2,K,T is strictly distinct from the full class of depth 2 programs C-RASP 2 .”

The lengths of strings necessary for length generalization must grow faster than any computable function, including the Ackermann function.

“In particular, the lengths of strings necessary for length generalization must grow faster than any computable function, including even the very fast growing Ackermann function (OEIS Foundation Inc., 2026).”

• cites OEIS Foundation Inc., 2026Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

No algorithm exists for perfectly learning transformers at depth 2 and beyond.

“Thus, no such algorithm exists for transformers at depth 2 and beyond.”

There is no computable length generalization bound for transformers.

“Our main result is the non-existence of computable length generalization bounds for C-RASP (already with two layers) and hence for transformers.”

The restricted C-RASP of Chen et al. lacks constant bias terms.

“In essence, their restricted C-RASP lacks constant bias terms (e.g. ↼ #a - ↼ #b ≤ 4).”

Any Diophantine equation can equivalently be expressed as a system of equations of the form x = c, x + y = z, or x • y = z, where x, y, z are variables ranging over N and c is a constant in N.

“Any Diophantine equation can equivalently be expressed as a system of equations of the form x = c, x + y = z, or x • y = z, where x, y, z ∈ V are variables ranging over N and c ∈ N is a constant (Matiyasevich, 1993, p. 3).”

• cites Matiyasevich, 1993, p. 3Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

For any TL[-3] program P, if its language is nonempty, it accepts a word of length at most polynomial in the size of P.

“Thus, w is a word accepted by P of length at most polynomial in the size of P .”

For any k, all formulas of C-RASP_{2,K,T} will eventually output a constant value for sufficiently long strings from D_k.

“Intuitively, we show that all formulas of C-RASP 2,K,T will eventually output a constant value for enough strings from any D k for every k.”

No learning algorithm can decide if a transformer has seen enough data.

“This theorem implies that no learning algorithm can decide if a transformer has seen enough data.”