Research map / Architectures and efficiency / Attention and transformers
The Role of Sparsity for Length Generalization in LLMs
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 a theoretical framework showing length generalization in next-token prediction holds when each token depends on a small fixed number of previous tokens (sparsity), and introduces Predictive Position Coupling to extend position coupling to input-dependent position IDs.
Problem
Length generalization of decoder-only transformers beyond training context length lacks a principled explanation; it is unclear which structural properties of data enable it.
Approach
Models next-token prediction with k-sparse planted correlations and sparse functional attention; proves length generalization when sparsity is fixed and hypothesis class is local, shows position coupling removes the locality requirement, and proposes Predictive Position Coupling where the transformer predicts its own coupled position IDs.
Key results
- Sparse parity: transformers trained with Ktrain<=8 generalize near-perfectly up to length 500 for test sparsity <= Ktrain, while larger test sparsity degrades rapidly.
- Parity with scratchpad: smaller jump lengths (less sparsity) give better out-of-distribution accuracy at lengths up to 175.
- Variable assignment with Predictive Position Coupling generalizes to test lengths up to 3x training length for depths 2-5, while RoPE with PoSE performs significantly worse.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Keep test sparsity at or below the training sparsity | GPT-NeoX with RoPE and PoSE on sparse parity · Sparse parity, lengths up to 500 | accuracy | Helped |
| Increase test sparsity beyond the training sparsity | GPT-NeoX with RoPE and PoSE on sparse parity · Sparse parity, lengths up to 500 | accuracy | Hurt |
| Increase sparsity while holding training sparsity fixed | GPT-NeoX with RoPE and PoSE on sparse parity · Sparse parity | accuracy | Hurt |
| Use shorter scratchpad jumps | Predictive Position Coupling on parity with scratchpad · Parity with scratchpad | accuracy | Helped |
| Predict input-dependent coupled position IDs | GPT-NeoX on variable assignment with scratchpad · Variable assignment | exact sequence accuracy | Helped |
| Remove position coupling (ablation) | GPT-NeoX on variable assignment with scratchpad · Variable assignment | exact sequence accuracy | Hurt |
| Remove the scratchpad (ablation) | GPT-NeoX on variable assignment · Variable assignment | exact sequence accuracy | Hurt |
| Use RoPE with PoSE instead of Predictive Position Coupling (ablation) | GPT-NeoX on variable assignment · Variable assignment | exact sequence accuracy | Hurt |
| Use 5 influential tokens from the first 64 positions instead of all tokens in those positions | Short-context transformer with PoSE · C4, context length 128 | cross-entropy loss difference | No clear effect |
Surprising findings
- Shorter scratchpads (larger jump length) do not help; sparsity matters more than output sequence length for length generalization.
Limitations
- Theoretical assumptions (i.i.d. background tokens, fixed sparse position distribution) are unrealistic for natural language
- Locality assumption is strong and only relaxed via position coupling, which requires structured tasks
- Natural language experiments are small-scale (context length 64 to 128)
Experimental setup
Datasets: C4 synthetic sparse parity synthetic scratchpad parity variable assignment synthetic task
Benchmarks: C4 perplexity synthetic sparse parity synthetic parity with scratchpad variable assignment with scratchpad
Metrics: accuracy cross-entropy loss perplexity
Baselines: RoPE with PoSE position coupling without prediction ignore-distant-tokens baseline
Builds on: position coupling PoSE RoPE Abacus embeddings
Closest papers by meaning
- Long-Short Alignment for Effective Long-Context Modeling in LLMs (ICML 2025 · similarity 0.91)
- How Do Position Encodings Affect Length Generalization? Case Studies On In-Context Function Learning (AAAI 2025 · similarity 0.91)
- Beyond Single-Task: Robust Multi-Task Length Generalization for LLMs (NeurIPS 2025 · similarity 0.90)
- Extrapolation by Association: Length Generalization Transfer In Transformers (NeurIPS 2025 · similarity 0.90)
- Understanding and Improving Length Generalization in Recurrent Models (ICML 2025 · similarity 0.90)
- A Formal Framework for Understanding Length Generalization in Transformers (ICLR 2025 · similarity 0.90)
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.