Length Generalization Bounds for Transformers

Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, Anthony W. Lin · 2026

Read Length Generalization Bounds for Transformers by Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, Anthony W. Lin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-02238.txt.

Introduction

Andy Yang, Pascal Bergsträßer, Georg Zetzsche, and colleagues settle an open question about transformers in this 2026 paper. A model shows length generalization if it handles inputs of any length after finite training. For trust, one needs a bound past which success is guaranteed. The authors ask whether such bounds can be computed for a language class tied to transformers.

For the full class, already at two layers, no computable bound exists. That negative answer covers transformers themselves. For a positive fragment of the class, a bound can be computed. That fragment matches fixed-precision transformers, models with limited numeric detail. Its length cost grows exponentially, and the authors prove that growth cannot be improved in general.

Catalog record

CREATORAndy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, Anthony W. Lin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90075
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.02238

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Length Generalization Bounds for Transformers Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, Anthony W. Lin Abstract Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a guarantee, one needs to be able to compute a length generalization bound, beyond which the model is guaranteed to generalize. This paper concerns the open problem of the computability of such generalization bounds for 𝖢 ​ - ​ 𝖱𝖠𝖲𝖯 \mathsf{C\textsf{-}RASP} , a class of languages which is closely linked to transformers. A positive partial result was recently shown by 6 for 𝖢 ​ - ​ 𝖱𝖠𝖲𝖯 \mathsf{C\textsf{-}RASP} with only one layer and, under some restrictions, also with two layers. We provide complete answers to the above open problem. Our main result is the non-existence of computable length generalization bounds for 𝖢 ​ - ​ 𝖱𝖠𝖲𝖯 \mathsf{C\textsf{-}RASP} (already with two layers) and hence for transformers. To complement this, we provide a computable bound for the positive fragment of 𝖢 ​ - ​ 𝖱𝖠𝖲𝖯 \mathsf{C\textsf{-}RASP} , which we show equivalent to fixed-precision transformers. For both positive 𝖢 ​ - ​ 𝖱𝖠𝖲𝖯 \mathsf{C\textsf{-}RASP} and fixed-precision transformers, we show that the length complexity is exponential, and prove optimality of the bounds. 1 Introduction The past few years have witnessed intensive research efforts to provide theoretically sound analyses of transformers ( 34 , e.g.) . While initial efforts focused primarily on transformer expressivity, more recent efforts ( 36 ; 37 ; 6 ; 14 ) have delineated what is efficiently learnable by transformers, particularly in terms of length generalization . Intuitively, length generalization is when a model can be trained to accurately process strings of any length , given only a finite training sample of strings with bounded length . Understanding when transformers can length generalize has important practical implications. On the one hand, computational and data constraints limit the sequence lengths that are seen during training; on the other hand, processing large contexts and reasoning over long chains-of-thought create a need for strong capabilities even on long inputs. To study this formally, we consider transformers as formal language recognizers, that is, binary classifiers of strings, and ask when they can length-generalize. Empirical studies have found that length generalization in transformers can vary significantly from language to language ( 44 ) through mechanisms that remain unclear. Furthermore, length generalization appears quite sensitive to the particular parameters of the model, such as the weight initialization, learning rate, and positional encodings used ( 18 ; 45 ) . To help alleviate these issues, researchers have developed methods to improve length generalization by incorporating positional information ( 31 ; 35 ) or refining the presentation format of the language ( 27 ; 5 ; 16 ) . While we can, to some degree, influence the ability of transformers to length generalize, we lack a theoretical basis for these methods. Theoretical work has begun to provide some characterizations of the formal languages which transformers length-generalize on. These characterizations are largely based on the expressivity of \mathsf{RASP} , a programming language which was designed to capture the expressive power of transformers ( 38 ) . 44 conjectured that transformers would length-generalize on a language if and only if it had a short solution in the \mathsf{RASP} variant \mathsf{RASP} -l, and provided empirical evidence to support this claim. Later, 14 formalized this conjecture using {\mathsf{C\textsf{-}RASP}} , a \mathsf{RASP} variant expressively equivalent to transformers with fixed precision outside of attention ( 39 ) . 14 proved that transformers are guaranteed to length-generalize on languages which had a {\mathsf{C\textsf{-}RASP}} program, under an idealized inference procedure. However, as pointed out by 6 , the results of 14 only guarantee learnability in the limit ( 9 ) , that is, without providing any quantitative bounds on the training resources needed to learn a given language. For an example of how quantitative bounds lead to real-world impacts, we can look at scaling laws for language models. Language models are known to reliably follow scaling laws, which are quantitative equations that describe how the test loss of a model relates to the size of the model and the training data ( 17 ) . These laws can be used to derive the optimal model size and dataset size to minimize loss, given a fixed compute budget ( 13 ) . As an instance of their practical usage, 24 used scaling laws to optimally train the (at time of publication) most capable differentially private language model. While these scaling laws may effectively predict loss, they fail to predict length generalization. A growing body of evidence shows that length generalization is often wholly independent of conventional scaling laws; in many cases increasing the model size or number of training examples are not the critical factors which determine length generalization ( 2 ; 29 ) . As an example, 28 find that models ranging from 50M to 3B parameters could not add numbers of 20 digits, when trained on addition over 15 digits. At the same time, length generalization could be observed after training on 30 digits and testing on 60 digits, but increasing the amount of data past a critical threshold did not make much of a difference. A distinct theoretical framework is thus needed to provide quantitative guarantees for length generalization in transformers. To provide a framework for these formal guarantees, 6 formulated the notion of non-asymptotic length generalization , which asks for a computable bound N such that a learning algorithm only requires labeled training data consisting of strings of length up to N in order to correctly classify any test data containing strings of length greater than N . Such a learner is guaranteed to terminate, since N is computable and there are finitely many strings of length up to N . This notion of non-asymptotic length generalization is connected to the classical framework of exact learning ( 1 ) with only membership queries, as well as learning minimal hypotheses, which was already studied by Gold for finite automata ( 10 ) . In fact, 6 show that non-asymptotic length generalization is equivalent to the previously studied finite identification ( 9 , p. 457) when the latter is allowed to take into account the complexity of the ground-truth hypothesis. To study the non-asymptotic length generalization of transformers, 6 studied {\mathsf{C\textsf{-}RASP}} , a class of formal languages, for which transformers were proven to length-generalize ( 14 ) . They proved computable length generalization bounds for {\mathsf{C\textsf{-}RASP}} with one layer and two layers with additional restrictions (see Appendix B ). These bounds are (respectively) polynomial and exponential in the maximum absolute value of constants appearing in the {\mathsf{C\textsf{-}RASP}} program. For example, using this, one can surmise that learning the \mathsf{MAJORITY} language \{w\in\{a,b\}^{*}:\text{$w$ has more $a$'s than $b$'s}\} using restricted {\mathsf{C\textsf{-}RASP}} programs of depth 1 requires only strings up to length quadratic in the absolute value of constants. Similarly 15 studied bounds for 1 and 2 layer limit transformers (a limiting object that captures what transformers length generalize on ( 14 ) ) with finite and infinite precision, deriving a bound which scales with the parameter norms and other quantities of the

Read the complete text