# Quantitative Bounds for Length Generalization in Transformers arXiv: https://arxiv.org/abs/2510.27015 · HTML: https://mlsanity.com/paper/2510.27015/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 33 of its 38 references that are in the map. - First posted on arXiv 30 Oct 2025. ## Builds on (most cited first, 30 of 33) - [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021) - [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022) - [A Primer in BERTology: What we know about how BERT works](https://mlsanity.com/paper/2002.12327/) (2020) - [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023) - [Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer](https://mlsanity.com/paper/2203.03466/) (2022) - [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024) - [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022) - [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023) - [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021) - [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023) - [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023) - [How Transformers Learn Causal Structure with Gradient Descent](https://mlsanity.com/paper/2402.14735/) (2024) - [Looped Transformers for Length Generalization](https://mlsanity.com/paper/2409.15647/) (2024) - [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024) - [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022) - [Positional Description Matters for Transformers Arithmetic](https://mlsanity.com/paper/2311.14737/) (2023) - [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024) - [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024) - [Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges](https://mlsanity.com/paper/2502.01612/) (2025) - [Understanding and Improving Length Generalization in Recurrent Models](https://mlsanity.com/paper/2507.02782/) (2025) - [On Provable Length and Compositional Generalization](https://mlsanity.com/paper/2402.04875/) (2024) - [Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot](https://mlsanity.com/paper/2406.06893/) (2024) - [Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count](https://mlsanity.com/paper/2410.15787/) (2024) - [Extrapolation by Association: Length Generalization Transfer in Transformers](https://mlsanity.com/paper/2506.09251/) (2025) - [Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms](https://mlsanity.com/paper/2505.17190/) (2025) - [Knee-Deep in C-RASP: A Transformer Depth Hierarchy](https://mlsanity.com/paper/2506.16055/) (2025) - [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025) - [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025) - [The Role of Sparsity for Length Generalization in Transformers](https://mlsanity.com/paper/2502.16792/) (2025) - [Non-Asymptotic Length Generalization](https://mlsanity.com/paper/2506.03085/) (2025) ## Built on by (most cited first, 8 of 8) - [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025) - [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026) - [When Does Sparsity Mitigate the Curse of Depth in LLMs](https://mlsanity.com/paper/2603.15389/) (2026) - [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026) - [Universal priors: solving empirical Bayes via Bayesian inference and pretraining](https://mlsanity.com/paper/2602.15136/) (2026) - [Tracing LLM Behavior to the Training Data with Empirical Next-Token Distributions](https://mlsanity.com/paper/2607.14306/) (2026) - [Hierarchical Domain Generalization](https://mlsanity.com/paper/2607.16528/) (2026) - [Distance generalization in transformers: why bother with positional encoding?](https://mlsanity.com/paper/2609.11913/) (2026) ## Abstract (arXiv) 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: ℓ_∞ 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, and one- vs. 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 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.