Exact-Solution Volume and Length Generalization in Transformers

Yijia Jessica Zhu; David Chiang

cs.LGOct 6, 2026

Exact-Solution Volume and Length Generalization in Transformers

Authors: Yijia Jessica Zhu, David Chiang

Organizations: University of Notre Dame

Abstract

Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through normalized exact-solution volume (NESV): the fraction of a bounded parameter region that achieves an exact solution on every input of length $n$ . For fixed-width, single-layer transformers with $\log n$ -scaled attention, we establish asymptotic bounds on NESV for four tasks: FIRST ( $Θ(1)$ ), MAJORITY ( $Θ(1/(n\log n))$ ), INDEX ( $Θ(1/n^3)$ ), and PARITY ( $0$ ). These results are consistent with previous empirical results: the faster the exact-solution volume decays with input length, the harder it is to length-generalize on that task. Looking deeper into INDEX, our volume analysis reveals two error sources that grow with $n$ . Consequently, we study a transformer model that would structurally eliminate one of the terms, theoretically improving the NESV bound to $Θ(n^{-1})$ , and empirically achieving 85% accuracy when tested at $10\times$ the training length, compared with the 60% accuracy of the original model. We conclude that volume analysis may be a useful approach to identify concrete sources of length sensitivity and thus provide insights into task-specific model refinements.

Figures & tables

Task	Model
	Positional ( $\mathcal{A}_{\mathrm{pos}}$ )		General ( $\mathcal{A}_{\mathrm{gen}}$ )		Sinusoidal ( $\mathcal{A}_{\mathrm{sin}}$ )		Normalized ( $\mathcal{A}_{\mathrm{norm}}$ )
	NESV	Acc. (%)	NESV	Acc. (%)	NESV	Acc. (%)	NESV	Acc. (%)
First	$\Theta(1)$	100.0	$0$	51.12	$0$	55.06	$\Theta(1)$	100.0
Majority	—	92.7	$\Theta((n\log n)^{-1})$	82.6	$\Theta(({n^{3}\log n})^{-1})$	87.5	—	92.7
Index	$\Theta(n^{-3})$	59.6	$0$	51.9	$0$	50.2	$\Theta(n^{-1})$	85.1
Parity	$0$	—	$0$	—	$0$	—	$0$	—

Table 1: NESV bounds and mean accuracy at

10\times

the maximum training length for the four tasks. The models

\mathcal{A}_{\mathrm{gen}}

\mathcal{A}_{\mathrm{sin}}

, and

\mathcal{A}_{\mathrm{pos}}

are described in Section 2.2 , while

\mathcal{A}_{\mathrm{norm}}

is described in Section 4.2 .

Figure 1: Scale-normalized drift coefficients and mean OOD accuracy for trained positional Index models. Markers indicate the maximum training length

N

Figure 2: Length generalization on Index for the positional and

\mathcal{A}_{\mathrm{norm}}(h)

models trained up to

N=51

. Shading shows

95\%

bootstrap confidence intervals.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

$N$	$L$	First ( $\mathcal{A}_{\mathrm{pos}}$ )	Majority ( $\mathcal{A}_{\mathrm{gen}}$ )	Index ( $\mathcal{A}_{\mathrm{pos}}$ )	Index ( $\mathcal{A}_{\mathrm{norm}}$ )
11	111	100.0 (100.0–100.0)	83.8 (78.0–89.4)	57.2 (55.9–58.6)	63.4 (62.7–64.1)
21	211	100.0 (100.0–100.0)	91.3 (86.2–95.3)	55.2 (54.1–56.5)	74.1 (68.8–79.9)
31	311	100.0 (100.0–100.0)	87.1 (82.6–91.5)	59.2 (58.3–60.0)	90.6 (85.6–95.4)
41	411	100.0 (100.0–100.0)	88.5 (84.2–92.2)	55.1 (54.5–55.8)	84.4 (78.1–90.6)
51	511	100.0 (100.0–100.0)	82.6 (77.6–87.5)	59.6 (58.6–60.6)	85.1 (80.2–90.1)

Appendix

Table 2: Accuracy at the longest tested length

L=10N+1

. Entries are percentages, with pointwise

95\%

seed-bootstrap intervals in parentheses.

$N$	NoPE General	Sinusoidal General
11	91.6 (88.1–95.0)	95.3 (93.6–96.8)
21	95.1 (91.8–97.6)	93.8 (91.5–95.9)
31	92.9 (90.0–95.6)	91.2 (88.2–94.0)
41	93.4 (90.6–95.8)	91.5 (88.7–94.1)
51	89.8 (86.2–92.9)	92.9 (90.0–95.6)

Appendix

Table 3: Mean OOD accuracy on Majority for

\mathcal{A}_{\mathrm{gen}}

and

\mathcal{A}_{\mathrm{sin}}

general models. Entries are percentages, averaged equally over the five test lengths above

N

, with

95\%

confidence intervals in parentheses.

Explore similar work

Length Generalization for Transformers via Compression
Sep 8, 2026Georg Zetzsche, Hongjian Jiang, Andy Yang +4Transformer Architectures Generalization Bounds
Max Planck Institute for Software Systems (MPI-SWS) · RPTU Kaiserslautern-Landau · University of Notre Dame
Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers
Aug 31, 2026Takuya Ito, Ruchir Puri, Murray Campbell +1Transformer Architectures
IBM Research
On Generalisation Error Bounds for Transformers
Oct 15, 2024Lan V. TruongGeneralization Bounds Transformer Architectures
Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology (HCMUT), Vietnam

Sep 8, 2026, cs.LGJ/K move · Enter open · S save

Length Generalization for Transformers via Compression

Georg Zetzsche, Hongjian Jiang, Andy Yang, Pascal Bergsträßer+3

Max Planck Institute for Software Systems (MPI-SWS) · RPTU Kaiserslautern-Landau · University of Notre Dame

Transformer Architectures Generalization Bounds Data Compression Methods Open Problems Sample Size

Open paper AskPDF arXiv

Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a formalized version of the so-called RASP-l conjecture) posits that transformers length-generalize on a task if and only if a solution is expressible in the C-RASP language. While this hypothesis has strong empirical validation, theoretical problems arise from the fact that no computable length generalization bounds exist for C-RASP, alongside the discovery of seemingly contradictory experiments. To address these problems, we refine the C-RASP hypothesis utilizing the recently-proposed fragments C-RASP+ and C-RASP1. These fragments have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether these sample size bounds are tight. In this paper, we resolve this open question by providing an exponentially tighter bound. In doing so, we show a polynomial length generalization bound for transformers if we adopt compressed strings, via a novel connection to power words. As an application, we show how this yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.

Abstract

Explore similar work

Length Generalization for Transformers via Compression

Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers

On Generalisation Error Bounds for Transformers