Quantitative Bounds for Length Generalization in Transformers

• URL: http://arxiv.org/abs/2510.27015v1
• Date: Thu, 30 Oct 2025 21:31:36 GMT
• Title: Quantitative Bounds for Length Generalization in Transformers
• Authors: Zachary Izzo, Eshaan Nichani, Jason D. Lee,
• Abstract summary: We study the problem of length generalization (LG) in transformers.<n>LG occurs when the internal behavior of the transformer on longer sequences can be "simulated" by its behavior on shorter sequences.
• Score: 58.175107357008876
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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: $\ell_\infty$ 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.

Related papers

• From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers [67.02076505996284]
  We study how the choice of pretraining data distribution steers a shallow transformer toward one behavior or the other.<n>Our results shed light on the algorithmic biases of pretrained transformers and offer conceptual guidelines for data-driven control of their learned behaviors.
  arXiv  Detail & Related papers  (2025-12-21T08:10:26Z)
• Memory Limitations of Prompt Tuning in Transformers [45.158621811869466]
  We show that the amount of information memorized by a transformer cannot scale faster than linearly with the prompt length.<n>We also present the first formal proof of a phenomenon empirically observed in large language models: performance degradation.<n>This finding offers a fundamental understanding of the intrinsic limitations of transformer architectures.
  arXiv  Detail & Related papers  (2025-08-30T09:08:00Z)
• Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities [58.742178800799614]
  We study a family of $textitretrieval$ and $textitcopying$ tasks inspired by Liu et al.<n>We observe an $textitinduction-versus-anti-induction$ asymmetry, where pretrained models are better at retrieving tokens to the right (induction) than the left (anti-induction) of a query token.<n>Mechanistic analysis reveals that this asymmetry is connected to the differences in the strength of induction versus anti-induction circuits within pretrained transformers.
  arXiv  Detail & Related papers  (2025-05-27T21:36:50Z)
• On Vanishing Variance in Transformer Length Generalization [23.706900145711913]
  We show that even for today's frontier models, a longer sequence length results in a decrease in variance in the output of the multi-head attention modules.<n>Our analyses attribute this improvement to a reduction-though not a complete elimination-of the distribution shift caused by vanishing variance.
  arXiv  Detail & Related papers  (2025-04-03T17:59:56Z)
• The Role of Sparsity for Length Generalization in Transformers [58.65997625433689]
  We propose a new theoretical framework to study length generalization for the next-token prediction task.<n>We show that length generalization occurs as long as each predicted token depends on a small (fixed) number of previous tokens.<n>We introduce Predictive Position Coupling, which trains the transformer to predict the position IDs used in a positional coupling approach.
  arXiv  Detail & Related papers  (2025-02-24T03:01:03Z)
• A Formal Framework for Understanding Length Generalization in Transformers [14.15513446489798]
  We introduce a rigorous theoretical framework to analyze length generalization in causal transformers.<n>We experimentally validate the theory as a predictor of success and failure of length generalization across a range of algorithmic and formal language tasks.
  arXiv  Detail & Related papers  (2024-10-03T01:52:01Z)
• Unveil Benign Overfitting for Transformer in Vision: Training Dynamics, Convergence, and Generalization [88.5582111768376]
  We study the optimization of a Transformer composed of a self-attention layer with softmax followed by a fully connected layer under gradient descent on a certain data distribution model. Our results establish a sharp condition that can distinguish between the small test error phase and the large test error regime, based on the signal-to-noise ratio in the data model.
  arXiv  Detail & Related papers  (2024-09-28T13:24:11Z)
• Transformers Can Achieve Length Generalization But Not Robustly [76.06308648699357]
  We show that the success of length generalization is intricately linked to the data format and the type of position encoding. We show for the first time that standard Transformers can extrapolate to a sequence length that is 2.5x the input length.
  arXiv  Detail & Related papers  (2024-02-14T18:18:29Z)
• From Interpolation to Extrapolation: Complete Length Generalization for Arithmetic Transformers [7.011373967209572]
  We show that transformer models are able to generalize to long lengths with the help of targeted attention biasing. We demonstrate that using ABC, the transformer model can achieve unprecedented near-perfect length generalization on certain arithmetic tasks.
  arXiv  Detail & Related papers  (2023-10-18T14:10:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.