Research map / Architectures and efficiency / Attention and transformers
Universal Length Generalization with Turing Programs
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 Turing Programs, a universal scratchpad (CoT) strategy decomposing algorithmic tasks into modified-copy steps mimicking Turing Machine execution, combined with Hard-ALiBi, to achieve length generalization on addition, multiplication, SGD, and random Turing machines.
Problem
Transformers struggle to length-generalize (train on short sequences, test on long ones) on algorithmic tasks; prior fixes are task-specific data formats for addition.
Approach
Decompose any algorithmic task into a sequence of modified-copy steps mimicking a Turing Machine tape, and pair this scratchpad with Hard-ALiBi positional encoding so the model can exploit its copying ability; also show a RASP program that implements Turing Program execution.
Key results
- Hard-ALiBi with Turing Program scratchpad reaches 98% accuracy on addition at length 100 when trained on lengths up to 50.
- Multiplication by 1-digit and 3-digit operands generalizes 50->100 digits with 97.1% and 96.8% accuracy.
- SGD on linear regression trained on n<=50 examples generalizes with >95% accuracy to n=80; direct-answer training degrades significantly.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Turing Program scratchpads with Hard-ALiBi | Transformer · Addition (length 100; trained on lengths up to 50) | accuracy | Helped |
| Use Turing Program scratchpads with Hard-ALiBi | Transformer · Multiplication (n × 1; length 100) | accuracy | Helped |
| Use Turing Program scratchpads with Hard-ALiBi | Transformer · Multiplication (n × 3; length 100) | accuracy | Helped |
| Use Turing Program scratchpads with Hard-ALiBi | Transformer · SGD on linear regression (80 examples; trained on n ≤ 50) | accuracy | Helped |
| Replace the Turing Program scratchpad with direct final-answer prediction (ablation) | Transformer on SGD · SGD on linear regression | accuracy | Hurt |
Surprising findings
- Training to directly output the answer for SGD significantly degrades performance compared with the Turing Program scratchpad.
- Authors note that the Hard-ALiBi scratchpad addition results show considerable variance across seeds, though more robust than prior work.
Limitations
- Robust length generalization is not achieved on all tasks; degradation can appear shortly out of distribution.
- Turing Program CoT data is long and cumbersome, limiting practical use.
- RASP construction requires assumptions such as no repeated n-grams and in-memory operation.
Experimental setup
Datasets: synthetic addition examples synthetic multiplication examples synthetic linear-regression SGD examples random Turing machine simulations
Benchmarks: multi-digit addition (50->100 digits) multiplication by 1-digit and 3-digit operands (50->100) in-context SGD on linear regression (50->80 examples) random Turing machine 1-step prediction
Metrics: exact-match accuracy accuracy within 2 quantization units for SGD
Baselines: vanilla scratchpad direct answer training Zhou et al. addition formats ALiBi NoPE
Builds on: Hard-ALiBi scratchpad RASP GPT-NeoX
Closest papers by meaning
- What Algorithms can Transformers Learn? A Study in Length Generalization (ICLR 2024 · similarity 0.92)
- A Formal Framework for Understanding Length Generalization in Transformers (ICLR 2025 · similarity 0.91)
- Length Generalization for Transformers via Compression (NeurIPS 2026 · similarity 0.90)
- Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count (ICLR 2025 · similarity 0.90)
- Non-Asymptotic Length Generalization (ICML 2025 · similarity 0.90)
- Extrapolation by Association: Length Generalization Transfer In Transformers (NeurIPS 2025 · similarity 0.89)
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.