The Role of Sparsity for Length Generalization in LLMs

Noah Golowich, Samy Jelassi, David Brandfonbrener, Sham M. Kakade, Eran Malach

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:

  1. 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.
  2. 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.
  3. 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.

Performance on synthetic tasks demonstrating the impact of sparsity and the success of PPC.

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.

Scatter plot showing the correlation between cross-entropy loss differences, supporting the sparsity hypothesis in natural language.

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

Abstract

Training large language models to predict beyond their training context lengths has drawn much attention in recent years, yet the principles driving such behavior of length generalization remain underexplored. We propose a new theoretical framework to study length generalization for the next-token prediction task, as performed by decoder-only transformers. Conceptually, we show that length generalization occurs as long as each predicted token depends on a small (fixed) number of previous tokens. We formalize such tasks via a notion we call k-sparse planted correlation distributions, and show that an idealized model of transformers which generalize attention heads successfully length-generalize on such tasks. As a bonus, our theoretical model allows us to provide justifications for techniques to modify positional embeddings which have been introduced to improve length generalization, such as position coupling. We support our theoretical results with experiments on synthetic tasks and natural language, which confirm that a key factor driving length generalization is indeed a ``sparse'' dependency structure of each token on the previous ones. Further, inspired by our theory, we introduce Predictive Position Coupling, a generalization of position coupling which trains the transformer to predict the position IDs used in a positional coupling approach. Predictive Position Coupling thereby allows us to broaden the array of tasks to which Position Coupling can successfully be applied to achieve length generalization.
BibTeX
@inproceedings{golowich2025role,
  author = {Noah Golowich and Samy Jelassi and David Brandfonbrener and Sham M. Kakade and Eran Malach},
  title = {{The Role of Sparsity for Length Generalization in LLMs}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=S9LkB0UBKb},
}
Figure