Transformer theory · Transfer & distribution shift / Open question
Why Transformers Generalize to Longer Sequences
A model that learns an algorithm should be able to apply it to larger inputs, rather than memorize the sizes used during training.
Seed catalog · Showing the bundled record.
Problem statement
Use deterministic state-tracking tasks formed by composing symbols from a fixed alphabet of maps on S states. A causal softmax transformer receives the initial state and map sequence and predicts the final state; training sequences have length at most L, and test symbols follow the same full-support product law at lengths up to T greater than L. Determine finite-data SGD conditions for test error at most epsilon, with explicit dependence on S, L, T, model width/depth, arithmetic precision and the positional encoding.
Assumptions and scope
- Fix the task generator, state complexity, sequence distribution and test-length range; do not quantify over arbitrary programs or languages.
- Specify architecture, positional scheme, arithmetic precision, initialization and stochastic update rule. An existence or identification theorem is not a training theorem.
- Account for attention dilution and accumulated numerical or rollout error as length increases. A fixed network need not succeed on every length.
What would settle it?
A finite-sample optimization-and-extrapolation guarantee for a declared nontrivial task family, with quantitative failure boundaries or a lower bound identifying a necessary architectural or data condition.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Huang et al. give idealized identification and state-tracking training results; Izzo et al. give quantitative length bounds. Yang et al. rule out general computable bounds, and Zetzsche et al. sharpen restricted compression bounds. The residual target couples finite-data SGD, precision and robust extrapolation in a specified family. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Huang et al. — A Formal Framework for Understanding Length Generalization in Transformers ↗partial theory · source checked 2026-11-19
Abstract checked: identifiability in the limit for causal transformers with learnable absolute positions under an idealized norm-regularized inference scheme, not standard gradient training.
- Izzo, Nichani and Lee — Quantitative Bounds for Length Generalization in Transformers ↗partial theory · source checked 2026-11-19
Abstract checked: first quantitative training-length bounds for one- and two-layer settings, via simulation of long-sequence behavior by short sequences.
- Yang et al. — Length Generalization Bounds for Transformers ↗partial theory · source checked 2026-11-19
Abstract checked: no computable length-generalization bounds for general C-RASP, already at two layers; positive restricted fixed-precision results. These are identifiability bounds, not convergence guarantees for SGD.
- Zetzsche et al. — Length Generalization for Transformers via Compression ↗partial theory · source checked 2026-11-19
Abstract checked: exponentially tighter bounds for C-RASP fragments than earlier double-exponential bounds; polynomial bounds for compressed strings.
- Huang et al. — Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization ↗partial theory · source checked 2026-11-19
Abstract checked: gradient-descent guarantees on synthetic state-tracking tasks, including NC1-complete problems with chain of thought, and recursive self-training extending length.
- Zhou et al. — What Algorithms can Transformers Learn? A Study in Length Generalization ↗empirical motivation · source checked 2026-11-19
Abstract checked: the RASP-Generalization Conjecture, an empirical heuristic for which tasks length-generalize.