Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones

Marius Henry; Michael Rizvi-Martel; Michael Hahn

cs.LGOct 26, 2026

Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones

Authors: Marius Henry, Michael Rizvi-Martel, Michael Hahn

Organizations: LaCoCo, Saarland University, Saarland Informatics Campus · Zuse School ELIZA · Mila & Université de Montréal

Abstract

Transformer-based language models exhibit an astonishing capacity to generalize to longer and more difficult problem instances than those seen in training. However, theoretical understanding of this phenomenon still lags behind. Unlike most machine learning models, the generalisation abilities of transformers inherently require considering two axes. On one hand, one must examine in-distribution statistical generalisation, which concerns the ability of a model to broaden a function from training samples to novel samples of the same distribution. On the other hand, given the sequential nature of language data, one must also consider length generalisation, which reflects whether a model trained on inputs of a given length can extrapolate to longer ones.These two notions have mostly been studied separately, leaving open how they interact. In this work, we give a joint treatment of both axes for fixed-precision transformers. We give generalisation guarantees in terms of the parameter sizes of the involved models, as well as the quantization space and the alphabet size that supply the sequences. Finally, we illustrate how the requirements in the sample count and training length trade off. In particular, we find that increasing training length can be exponentially more efficient than increasing the sample size. Experiments support predictions of the theory.

Figures & tables

Figure 1: Our results predict that increasing the length of the training words can be much more token-efficient than increasing their number; test accuracy for the language $A_{15}$ (Sec. 5 ) on words five times longer than the training length. We highlight in red the highest-accuracy cell at five different training token budgets.

Panel of Figure 2 — Figure 2: Examples of poDFAs; the vertices are the states and the arrows are the transition functions $\delta$ . Figure (a) represents the transformer that outputs “1” as soon as the input word has entered the language $L_{2}\coloneqq a\Sigma^{*}b\Sigma^{*}$ with (b) being the associated poDFA. Similarly, (c) depicts the transformer that recognizes the language $L_{3}\coloneqq a\Sigma^{*}b\Sigma^{*}a\Sigma^{*}$ and (d) is its corresponding poDFA. Figure (e) is the poDFA $\mathcal{A}_{\Delta}$ of the difference function between these two transformers. Any disagreement sends the run to the absorbing final state $\bot$ .

Panel of Figure 3 — Figure 3: Schematic error-budget limit lines with linear axes. At $K=C$ , every budget can be respected with $N\sim\mathcal{O}(s^{C})$ training samples. By length $K=sC$ , at least half of the words have reached their terminal absorbing states, so each curve is within a factor $2$ of its floor; further length gains saturate.

Figure 4: Left: Impact of teacher’s size on length complexity. Larger teachers require training samples to be longer. The abscissa scale is linear, as suggested by theory. Right: Impact of teacher’s size on data complexity. Larger teachers require more training samples for similar length generalization performance. The abscissa scale is logarithmic, as suggested by theory. On both sides, the plotted tasks are respectively the Alternating

L_{4},L_{5},L_{6},L_{7}

, the Alphabet

A_{10},A_{12},A_{15},A_{20}

and the Induction Head

\mathit{IH}_{5},\mathit{IH}_{6},\mathit{IH}_{7},\mathit{IH}_{8}

Figure 5: Tradeoff between the training length and the sample size for one task of each language class: Alternating $L_{6}$ , Alphabet $A_{15}$ and Induction Head $\mathit{IH}_{7}$ . Evaluation at length 5 times the training length. Brown contouring around all cells with accuracy $\geq 0.75$ . Under this condition, the $3$ cells with the smallest token-budget are framed.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Figure 6: Impact of teacher’s size on data complexity . $L_{k}$ probes teacher depth $L_{t}$ ; $A_{k}$ jointly varies $H_{t}$ , $D_{t}$ , and $|\Sigma|$ ; $\mathit{IH}_{k}$ varies alphabet size, width requirements, and output dimension. Student backbones are fixed within each family, while $K$ follows the task-specific coverage criterion.

Panel of Figure 7 — Figure 7: Impact of teacher’s size on length complexity . $L_{k}$ probes teacher depth $L_{t}$ ; $A_{k}$ jointly varies $H_{t}$ , $D_{t}$ , and $|\Sigma|$ ; $\mathit{IH}_{k}$ varies alphabet size, width requirements, and output dimension. Tasks are compared at shared values of $K$ , with $N$ and student backbones fixed. For relative evaluations, early accuracy is sometimes high for tasks that are trivial on short words: words of length $3K$ or $5K$ might still be short and have a trivial target.

Panel of Figure 8 — Figure 8: Impact of the student’s depth on length generalization . We vary $L_{s}$ while holding $D_{s}$ and $H_{s}$ fixed.

Panel of Figure 9 — Figure 9: Impact of the student’s embedding dimension on length generalization . We vary $D_{s}$ while holding $L_{s}$ and $H_{s}$ fixed.

Panel of Figure 10 — Figure 10: Impact of the student’s head count on length generalization . We vary $H_{s}$ while holding $L_{s}$ and $D_{s}$ fixed.

Panel of Figure 11 — Figure 11: Tradeoff between training length and data complexity . One task of each family: $L_{6},A_{15}$ and $\mathit{IH}_{7}$ to study the tradeoff between the two quantities.

Figure 12: Control experiment for $L_{6}$ , $A_{15}$ , and $\mathit{IH}_{7}$ , with evaluation at relative test length 5 $K$ . The axis labelled $N$ gives the total token budget of the dataset rather than the number of words.

Panel of Figure 13 — Figure 13: Tradeoff between training length and data complexity: evaluation on absolute lengths, from length $50$ to length $500$ with additive incrementation of $50$ .

Panel of Figure 14 — Figure 14: Tradeoff between training length and data complexity: evaluation on relative lengths $1K,2K,3K,4K,5K$ , with $K$ the training length of the involved cells configuration.

Panel of Figure 15 — Figure 15: Tradeoff between training length and data complexity: evaluation on absolute lengths, from length $50$ to length $500$ with additive incrementation of $50$ . Red contouring for accuracy $\geq 0.75$ ; highlighted in red are the 3 configurations under this constraint that have the smallest token-budget.

Panel of Figure 16 — Figure 16: Tradeoff between training length and data complexity: evaluation on relative lengths $1K,2K,3K,4K,5K$ , with $K$ the training length of the involved cells configuration. Red contouring for accuracy $\geq 0.75$ ; highlighted in red are the 3 configurations under this constraint that have the smallest token-budget.

Panel of Figure 17 — Figure 17: Tradeoff between training length and data complexity: evaluation on absolute lengths, from length $50$ to length $500$ with additive incrementation of $50$ . For their respective maximum token-budget threshold, highlighted in red are the 3 configurations that achieve the best accuracy.

Panel of Figure 18 — Figure 18: Tradeoff between training length and data complexity: evaluation on relative lengths $1K,2K,3K,4K,5K$ , with $K$ the training length of the involved cells configuration. For their respective maximum token-budget threshold, highlighted in red are the 3 configurations that achieve the best accuracy.

Language Model Generalization

See all 29 papers

Sep 8, 2026

Length Generalization for Transformers via Compression

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.

Georg Zetzsche, Hongjian Jiang, Andy Yang +4

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

Transformer Expressivity Transformer Length Generalization Generalization Bounds

Ask PDF

Oct 6, 2026

Exact-Solution Volume and Length Generalization in Transformers

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.

Yijia Jessica Zhu, David Chiang

University of Notre Dame

Transformer Expressivity Transformer Length Generalization

Ask PDF

Feb 20, 2026

On the "Induction Bias" in Sequence Models

Despite the remarkable practical success of transformer-based language models, recent work has raised concerns about their ability to perform state tracking. In particular, a growing body of literature has shown this limitation primarily through failures in out-of-distribution (OOD) generalization, such as length extrapolation. In this work, we shift attention to the in-distribution implications of these limitations. We conduct a large-scale experimental study of the data efficiency of transformers and recurrent neural networks (RNNs) across multiple supervision regimes. We find that the amount of training data required by transformers grows much more rapidly with state-space size and sequence length than for RNNs. Furthermore, we analyze the extent to which learned state-tracking mechanisms are shared across different sequence lengths. We show that transformers exhibit negligible or even detrimental weight sharing across lengths, indicating that they learn length-specific solutions in isolation. In contrast, recurrent models exhibit effective amortized learning by sharing weights across lengths, allowing data from one sequence length to improve performance on others. Together, these results demonstrate that state tracking remains a fundamental challenge for transformers, even when training and evaluation distributions match.

M. Reza Ebrahimi, Michaël Defferrard, Sunny Panchal +1

Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.

Transformer State Tracking Inductive Bias Data-Efficient Learning Recurrent Neural Networks Length Generalization

Ask PDF

Abstract

Language Model Generalization

Explore similar work

Length Generalization for Transformers via Compression

Exact-Solution Volume and Length Generalization in Transformers

On the "Induction Bias" in Sequence Models