Research map / Architectures and efficiency / Attention and transformers
A Formal Framework for Understanding Length Generalization in Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a formal framework that characterizes length generalization of causal transformers with absolute or no positional encodings as identifiability in the limit under an idealized norm-regularized inference procedure, linking success to C-RASP and Limit Transformer expressiveness.
Problem
Lack of theoretical understanding of when transformers generalize to sequences longer than those seen in training, which varies across tasks empirically.
Approach
Model length generalization as identification in the limit: an idealized inference procedure fits transformers with growing context windows while minimizing a norm-based regularizer; the authors introduce Limit Transformers (bounded-width objects with translation-invariant, periodic, local positional functions) and C-RASP with positional relations to characterize which tasks are guaranteed to gene
Key results
- Theory predicts length generalization success/failure on 13 of 17 regular languages via C-RASP[periodic, local] programs, with generalization succeeding where programs exist and failing e.g. for Σ*be*.
- NoPE transformers succeed on tasks expressible in C-RASP[∅] such as MAJORITY, DYCK-1, a^nb^nc^n.
- Copying with arbitrary (repeated) strings and n-digit addition are proven not expressible by Limit Transformers via logarithmic communication complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use APE transformers on tasks with a C-RASP[periodic, local] program | Transformers · Algorithmic tasks and regular languages | length generalization accuracy | Helped |
| Use NoPE transformers on tasks with a C-RASP[empty] program | Transformers · Algorithmic tasks and regular languages | length generalization accuracy | Helped |
| Test copying with repeated substrings rather than avoiding repetition | Transformers · COPY | length generalization accuracy | Hurt |
| Apply length generalization to PARITY | Transformers · PARITY | length generalization accuracy | Hurt |
| Apply length generalization to Σ*be* | Transformers · Σ*be* | length generalization accuracy | Hurt |
| Use positional relations to recognize (aa)* | Transformers · (aa)* | length generalization accuracy | Helped |
| Remove positional relations when recognizing (aa)* | Transformers · (aa)* | length generalization accuracy | Hurt |
Surprising findings
- Generalization fails on simple regular languages such as Σ*be* despite their simplicity for recurrent models.
Limitations
- Analysis is idealized: assumes global minimizer of regularized objective with perfect fit to training distribution, ignoring SGD dynamics and data subsampling.
- Only absolute positional encodings are covered; other positional encodings left for future work.
- Threshold N_0 after which length generalization occurs is not bounded practically.
Experimental setup
Datasets: 8 algorithmic tasks (e.g., COPY, BINARY MAJORITY INTERLEAVE) 17 regular languages from Deletang et al. benchmark
Benchmarks: 8 algorithmic tasks 17 regular languages benchmark
Metrics: accuracy on test lengths 101-150
Baselines: NoPE transformers LSTM
Builds on: RASP-L Conjecture C-RASP Induction Head
Closest papers by meaning
- Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count (ICLR 2025 · similarity 0.93)
- What Algorithms can Transformers Learn? A Study in Length Generalization (ICLR 2024 · similarity 0.92)
- Length Generalization for Transformers via Compression (NeurIPS 2026 · similarity 0.92)
- Universal Length Generalization with Turing Programs (ICML 2025 · similarity 0.91)
- Extrapolation by Association: Length Generalization Transfer In Transformers (NeurIPS 2025 · similarity 0.91)
- Looped Transformers for Length Generalization (ICLR 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.