Introduction
Large Language Models (LLMs) are typically trained on fixed-length sequences (e.g., 2k or 4k tokens) but are often expected to perform on much longer contexts at inference time. This "length generalization" is notoriously difficult; even state-of-the-art models often fail at simple arithmetic or logic tasks when the input exceeds their training window. While various modifications to positional embeddings (like RoPE or ALiBi) have helped, a principled understanding of why some tasks generalize and others do not has been missing.
This paper identifies sparsity—the property where a predicted token depends on only a small, fixed number of previous tokens—as the fundamental driver of length generalization in LLMs. The authors provide a formal theoretical framework for this "sparsity hypothesis" and introduce Predictive Position Coupling (PPC), a novel architectural modification that allows models to dynamically manage positional information for complex, input-dependent tasks.
Methods and Theoretical Framework
The authors approach the problem through three main lenses:
- Theoretical Framework: They define a new class of data distributions called $k$-sparse planted correlations. In these distributions, the next token depends on exactly $k$ "relevant" tokens hidden within a sea of "background" noise. They then define Sparse Functional Attention, an idealized version of a transformer head, and prove that if $k$ is small and fixed, the model can achieve provable length generalization.
- Position Coupling (PC) Justification: They provide a theoretical basis for "Position Coupling," a technique where tokens are assigned position IDs based on task structure rather than raw sequence index. They show that PC effectively removes the "locality" requirement, allowing models to attend to very distant but relevant tokens as if they were nearby.
- Predictive Position Coupling (PPC): Standard Position Coupling requires a fixed, known task structure. PPC extends this by training the transformer to predict the next "coupled" position ID alongside the next token. This allows the model to handle tasks where the relevant dependencies are dynamic and input-dependent.
Key Insights and Results
The core finding is that length generalization isn't about the total sequence length, but the dependency length. If a model only needs to "look" at $k$ tokens to make a prediction, and $k$ remains constant as the sequence grows, generalization is possible.
The paper validates its findings using synthetic tasks (Sparse Parity, Variable Assignment) and real-world natural language data (C4).
Sparsity vs. Generalization and PPC Success
In synthetic tests, models trained on sequences of length 50 showed near-perfect generalization up to length 500, but only when the sparsity $k$ was low. As $k$ increased, generalization performance collapsed. Furthermore, on complex logic tasks involving chains of assignments, PPC allowed models to generalize to contexts 3x longer than their training length, whereas standard methods failed.
Natural Language Evidence
Does this hold for real human language? By "unmasking" influential tokens in the C4 dataset, the authors found that LLM predictions for later tokens often relied on just a few ($k \approx 5$) specific tokens from earlier positions. This suggests that natural language itself exhibits the sparse structure their theory predicts.
Limitations and Future Work
- Idealized Models: The mathematical proofs rely on an "idealized" transformer. Real-world multi-layer transformers are far more complex.
- Computational Overhead: PPC requires predicting an additional set of IDs, adding a small amount of computational cost to the output layer.
- Background Noise Assumption: The theoretical model assumes "background" tokens are independent noise. In reality, natural language has complex local structures (grammar, syntax). Extending the theory to Markov chains or Hidden Markov Models is a promising direction for future work.
Summary updated