Research map / Architectures and efficiency / Attention and transformers
What Algorithms can Transformers Learn? A Study in Length Generalization
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 the RASP-Generalization Conjecture, that Transformers trained to completion length-generalize on algorithmic tasks when the task has a short RASP-L program, and uses it to design scratchpads and data sampling that enable length generalization on parity and addition.
Problem
Understanding when and why decoder-only Transformers trained from scratch length-generalize on algorithmic tasks such as arithmetic and parity, which typically fail to generalize.
Approach
Predict length generalization from the minimum length of a RASP-L program (a learnable, uniform, restricted subset of RASP) that solves the task on all input lengths; use this to design scratchpads (index hints, running-parity scratchpad) and balanced carry sampling that make tasks easier to generalize on.
Key results
- Models trained on count generalize near-perfectly to double the training lengths (e.g., length 100 after training up to 50).
- Index hints plus reverse-order output let addition length-generalize on easy carry; balanced carry sampling unlocks generalization on forward addition, reported as first strong length generalization on decimal addition from scratch.
- A running-parity scratchpad lets some runs trained up to length 30 generalize perfectly to length 50; with training length 40 all models generalize to length 50.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train count examples across a range of lengths instead of using sequences all of the same length (ablation) | Count · Length generalization | exact match | Helped |
| Add index hints to the prompt and answer (ablation) | Addition · Easy-carry addition | length generalization | Helped |
| Format the answer in reverse order (ablation) | Addition with index hints · Hard-carry addition with carry chains longer than training | length generalization | Helped |
| Use balanced carry sampling instead of independently sampled summands (ablation) | Forward addition with index hints · Hard-carry addition | length generalization | Helped |
| Add index hints and a running-parity scratchpad (ablation) | Parity · Parity, length 50 | exact match | Helped |
| Use a sum-mod-10 scratchpad instead of the running-parity scratchpad (ablation) | Parity · Length generalization | exact match | Hurt |
| Add a frequency-count scratchpad that orders counts by frequency (ablation) | Mode · Length generalization | exact match | Hurt |
| Add a frequency-count scratchpad with tokens in order of appearance (ablation) | Mode · Length generalization | exact match | Hurt |
| Use rotary positional embeddings instead of learned positional embeddings (ablation) | Count, mode, addition, and parity · Length generalization | length generalization performance | Hurt |
Surprising findings
- Scratchpad with sorted frequencies hurts generalization on mode, despite seeming natural.
- Trained Transformers on boolean AND ignore the last 5 bits that are constant in training, achieving 100% on unseen test, contrary to min-degree-interpolator predictions.
Limitations
- RASP-L is not complete; some efficiently representable algorithms (e.g., numerical ones) lack RASP implementations.
- Conjecture is phenomenological and not formal; minimum RASP-L program length is likely intractable to compute.
- Length generalization is imperfect and degrades with length; RASP program length does not perfectly match Transformer complexity.
Experimental setup
Datasets: synthetic algorithmic tasks (count, mode, copy, sort, addition, parity, boolean-AND)
Benchmarks: count mode copy sort addition parity boolean-AND
Metrics: exact match accuracy
Baselines: min-degree-interpolator no scratchpad forward addition naive addition
Builds on: RASP min-degree-interpolator induction heads scratchpads
Closest papers by meaning
- Length Generalization for Transformers via Compression (NeurIPS 2026 · similarity 0.94)
- A Formal Framework for Understanding Length Generalization in Transformers (ICLR 2025 · similarity 0.92)
- Looped Transformers for Length Generalization (ICLR 2025 · similarity 0.92)
- Universal Length Generalization with Turing Programs (ICML 2025 · similarity 0.92)
- Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count (ICLR 2025 · similarity 0.91)
- Extrapolation by Association: Length Generalization Transfer In Transformers (NeurIPS 2025 · similarity 0.91)
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.