← All AI/ML open problems

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.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.