Research map / Label-efficient and robust learning / OOD and anomaly detection
How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad
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.
Introduces the globality degree to characterize which distributions Transformers can weakly learn from scratch, argues high-globality tasks (cycle task, syllogism chains) are unlearnable, and proposes inductive scratchpads that break the barrier and improve length generalization on cycle, parity and addition tasks.
Problem
Which target distributions can regular Transformers trained from scratch efficiently (weakly) learn, given that they are expressive enough for many tasks; in particular, whether syllogism/graph-path composition over long chains is learnable, and how scratchpads can help.
Approach
Defines the globality degree of a distribution as the least number of input tokens (beyond the token histogram) needed to correlate non-trivially with the label; conjectures weak learnability by Transformers iff constant globality, and proposes inductive scratchpads that reindex positions and attention-mask so each step is an induction function of only the last state.
Key results
- Shift-method inductive scratchpad generalizes addition from 4 to 26 digits, and random-space method from 10 to 18 digits, versus 10 to 12 for prior recursive scratchpad work.
- Inductive scratchpad for parity, trained on up to 30 bits, generalizes to 50-55 bits depending on seed.
- Cycle task with DFS scratchpad is learned by GPT2-style models as n grows, while plain training fails for n >= 7 with 10M parameters; DFS scratchpad fails OOD while inductive scratchpad generalizes to longer DFS paths.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an inductive scratchpad with random spaces in the input | Addition · Addition length generalization | generalization length: 10 \rightarrow 18 | Helped |
| Use an inductive scratchpad with shifted operands | Addition · Addition length generalization | generalization length: 4 \rightarrow 26 | Helped |
| Use an inductive scratchpad with random spaces in the input | Parity · Parity length generalization | generalization length: From 30 bits to 55 bits | Helped |
| Replace the fully educated DFS scratchpad with an inductive scratchpad (ablation) | Cycle task · Cycle task OOD | OOD generalization | Helped |
| Use a fully educated DFS scratchpad rather than an inductive scratchpad (ablation) | Cycle task · Cycle task OOD | OOD generalization | Hurt |
Surprising findings
- Plain Transformers reach over 80% test accuracy on random-graph syllogism composition, but this is attributed to degree-based shortcuts rather than genuine path composition.
- Fully educated (DFS) scratchpads overfit the number of reasoning steps seen in training and fail OOD even while fitting in-distribution perfectly.
Limitations
- Conjecture linking constant globality to weak learnability is largely unproven; the theorem covers only one cycle-task variant under population gradient descent with idealized assumptions.
- Results on the agnostic scratchpad and globality-to-learnability link rely on conjectures and additional technical assumptions.
- Comparisons with prior length-generalization works are rough because input formats, model sizes and training setups differ.
Experimental setup
Datasets: synthetic cycle task graphs synthetic parity bit strings synthetic addition problems random directed graphs for implications task
Benchmarks: cycle task (n-cycle graph connectivity) parity length generalization addition length generalization
Metrics: accuracy iterations to reach 95% accuracy maximum length generalized to
Baselines: DFS scratchpad fully educated scratchpad NoPE (Kazemnejad et al.) RASP-L index hints recursive scratchpad (Shen et al.)
Builds on: scratchpad (Nye et al.) chain-of-thought RASP-L Universal Transformers
Closest papers by meaning
- What Algorithms can Transformers Learn? A Study in Length Generalization (ICLR 2024 · similarity 0.88)
- From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers (NeurIPS 2025 · similarity 0.88)
- Algorithmic Capabilities of Random Transformers (NeurIPS 2024 · similarity 0.87)
- Towards Understanding Inductive Bias in Transformers: A View From Infinity (ICML 2024 · similarity 0.86)
- A Formal Framework for Understanding Length Generalization in Transformers (ICLR 2025 · similarity 0.86)
- Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models (NeurIPS 2025 · similarity 0.86)
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.