Research map / Architectures and efficiency / Attention and transformers
From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers
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.
Theoretically analyzes how pretraining sequence-length diversity (measured by a max-sum ratio) steers a one-layer transformer trained by a single gradient step toward an induction head (OOD-generalizing) or a positional shortcut.
Problem
Understanding when a pretrained transformer learns a generalizable induction-head mechanism versus a positional shortcut that fails out-of-distribution, as a function of pretraining data structure.
Approach
Introduces a max-sum ratio of trigger-distance length probabilities as a diversity measure that determines which mechanism gradient-based training selects; shows a Theta(1/N_trg) threshold in both population and finite-sample regimes, and derives a linear-in-length optimal pretraining distribution minimizing compute.
Key results
- Theory predicts a transition at a max-sum ratio threshold of order Theta(1/N_trg): low ratio yields induction head with OOD generalization, high ratio yields positional shortcut.
- Optimal pretraining distribution minimizing average forward cost under the OOD constraint is linear in length: q_l proportional to l for l<=N_trg.
- In synthetic experiments, wider length diversity (larger l_max) increases OOD accuracy and reduces pseudo-trigger and leftmost errors; the transition is less sharp for a 3-layer AdamW-trained transformer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Broaden the pretraining distribution over trigger distances to lower the max-sum ratio | Single-layer transformer on trigger-output copying · OOD trigger-output sequences | OOD generalization | Helped |
| Use a pretraining distribution with a large max-sum ratio | Single-layer transformer on trigger-output copying · OOD trigger-output sequences | OOD generalization: Θ(N_\mathrm{trg}^{-1}) | Hurt |
| Increase the maximum pretraining context length while keeping the minimum fixed | Single-layer transformer on trigger-output copying · OOD trigger-output sequences | OOD accuracy | Helped |
| Increase the number of trigger types | Single-layer transformer on trigger-output copying · OOD trigger-output sequences | OOD accuracy | Hurt |
| Increase pretraining-distribution diversity | Three-layer transformer trained with AdamW · OOD trigger-output sequences | OOD accuracy | Helped |
Surprising findings
- Widening the length distribution alone is an inefficient way to lower the max-sum ratio; shifting mass toward longer contexts is more effective.
Limitations
- Analysis restricted to a single-layer transformer with tied key-query, absolute positional embeddings, and a single early-phase gradient step.
- Transition is less sharp in the practical 3-layer experiments.
Experimental setup
Datasets: synthetic trigger-output copying sequences
Benchmarks: synthetic OOD trigger-output test sets
Metrics: OOD accuracy pseudo accuracy rate leftmost rate
Builds on: induction heads early-phase gradient dynamics analysis
Closest papers by meaning
- Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities (NeurIPS 2025 · similarity 0.90)
- Algorithmic Capabilities of Random Transformers (NeurIPS 2024 · similarity 0.89)
- Transformers Converge to Invariant Algorithmic Cores (NeurIPS 2026 · similarity 0.89)
- When can in-context learning generalize out of task distribution? (ICML 2025 · similarity 0.88)
- Linear Transformers Implicitly Discover Unified Numerical Algorithms (NeurIPS 2025 · similarity 0.88)
- Selective Induction Heads: How Transformers Select Causal Structures in Context (ICLR 2025 · similarity 0.88)
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.