# A Formal Framework for Understanding Length Generalization in Transformers

arXiv: https://arxiv.org/abs/2410.02140 · HTML: https://mlsanity.com/paper/2410.02140/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2024.

## Built on by (most cited first, 30 of 45)

- [Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases](https://mlsanity.com/paper/2502.19249/) (2025)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Knee-Deep in C-RASP: A Transformer Depth Hierarchy](https://mlsanity.com/paper/2506.16055/) (2025)
- [The Counting Power of Transformers](https://mlsanity.com/paper/2505.11199/) (2025)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [The Role of Sparsity for Length Generalization in Transformers](https://mlsanity.com/paper/2502.16792/) (2025)
- [Quantitative Bounds for Length Generalization in Transformers](https://mlsanity.com/paper/2510.27015/) (2025)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures](https://mlsanity.com/paper/2510.05364/) (2025)
- [To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models](https://mlsanity.com/paper/2510.14826/) (2025)
- [Transformers are Inherently Succinct](https://mlsanity.com/paper/2510.19315/) (2025)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [On the Spatiotemporal Dynamics of Generalization in Neural Networks](https://mlsanity.com/paper/2602.01651/) (2026)
- [Sharper Generalization Bounds for Transformer](https://mlsanity.com/paper/2603.21541/) (2026)
- [Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalization](https://mlsanity.com/paper/2410.08898/) (2024)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)
- [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026)
- [The Role of Logic and Automata in Understanding Transformers](https://mlsanity.com/paper/2509.24024/) (2025)
- [From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs](https://mlsanity.com/paper/2512.12805/) (2025)
- [Rational Transductors](https://mlsanity.com/paper/2602.07599/) (2026)
- [Universal priors: solving empirical Bayes via Bayesian inference and pretraining](https://mlsanity.com/paper/2602.15136/) (2026)
- [Size-Transferability of Graph Transformers with Convolutional Positional Encodings](https://mlsanity.com/paper/2602.15239/) (2026)
- [Arithmetic OOD Failure Unfolds in Stages in Minimal GPTs](https://mlsanity.com/paper/2603.26828/) (2026)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [Length Generalization with Log-Depth Recurrent Units](https://mlsanity.com/paper/2605.26035/) (2026)
- [Compressing History into Memory: Distilling Transformers into Recurrent Transformers](https://mlsanity.com/paper/2606.21562/) (2026)

## Abstract (arXiv)

A major challenge for transformers is generalizing to sequences longer than those observed during training. While previous works have empirically shown that transformers can either succeed or fail at length generalization depending on the task, theoretical understanding of this phenomenon remains limited. In this work, we introduce a rigorous theoretical framework to analyze length generalization in causal transformers with learnable absolute positional encodings. In particular, we characterize those functions that are identifiable in the limit from sufficiently long inputs with absolute positional encodings under an idealized inference scheme using a norm-based regularizer. This enables us to prove the possibility of length generalization for a rich family of problems. We experimentally validate the theory as a predictor of success and failure of length generalization across a range of algorithmic and formal language tasks. Our theory not only explains a broad set of empirical observations but also opens the way to provably predicting length generalization capabilities in transformers.