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 justifies certain 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 a "sparse" dependency structure of each token on the previous ones. Inspired by our theory, we introduce Predictive 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.
Introduction
Large Language Models (LLMs) are typically trained on fixed-length sequences, such as 2,048 or 4,096 tokens. However, at inference time, these models are increasingly required to reason over much longer contexts, including long-form Chain-of-Thought (CoT) reasoning or massive document analysis. Standard Transformers often fail at this "length generalization," struggling with even simple tasks once the input exceeds the training window.
While empirical techniques like Rotary Positional Embeddings (RoPE) or Position Skip-Wise (PoSE) training provide some relief, the underlying principles that enable or inhibit context scaling have remained unclear. This research identifies "sparsity" as the fundamental structural property of data that drives length generalization.
Theoretical Framework: $k$-Sparse Planted Correlations
We propose that length generalization is possible when each target token depends on only a small, fixed number of previous tokens ($k$), regardless of the total sequence length. To formalize this, we introduce $k$-sparse planted correlation distributions, where a target token is determined by $k$ "relevant" tokens hidden within a sea of background noise.
By defining an idealized class of Transformers—Sparse Functional Attention—we prove that if $k$ is small and fixed, length generalization is theoretically guaranteed. This suggests that the primary challenge in long-context tasks is not the distance between tokens, but the model's ability to isolate these $k$ dependencies from the surrounding noise.
Predictive Position Coupling (PPC)
One major hurdle in length generalization is the "locality bias" of standard attention mechanisms. Even with relative embeddings, models struggle to attend to tokens far outside their training window. Existing "position coupling" techniques address this by mapping structurally related tokens to specific position IDs to make them appear "local." However, these usually require a fixed, known structure.
To overcome this, we introduce Predictive Position Coupling (PPC). PPC modifies the Transformer to predict two values at each step:
- The next token ID.
- The next coupled position ID.
This allows the model to dynamically manage its internal "map" of the sequence. By predicting its own position IDs, the model can maintain structural relationships even when the dependency structure is input-dependent and extends far beyond the training context.
Experimental Results
We validated our theory and the PPC method across three distinct experimental setups:
1. Synthetic Sparse Parity
In a task requiring the model to compute the parity of $k$ specific bits, we observed a clear sparsity threshold. Models trained with low sparsity ($k \leq 8$) achieved near-perfect accuracy on sequences up to 10x longer than their training context. When $k$ was increased, generalization collapsed, confirming that the dependency degree is the primary driver of context scaling.
2. Variable Assignment (Pointer Chasing)
This complex logic task requires following a chain of assignments (e.g., $a \to b, b \to c$). Standard methods like RoPE with PoSE failed as the chains grew beyond the training length. PPC, however, allowed models to generalize to lengths 3x longer than training by successfully predicting the necessary position IDs to bridge the logical distance between assignments.
3. Natural Language (C4)
To determine if natural language follows these sparse principles, we analyzed the OLMo model on the C4 dataset. We found that for a model trained on a context of 64, adding just 5 influential tokens from the distant past (up to length 128) allowed the model to nearly match the perplexity of a model trained on the full 128-length context. This suggests that the $k$-sparse planted correlation model is a highly effective approximation of real-world language structure.
Conclusion
Our research demonstrates that length generalization in Transformers is fundamentally tied to the sparsity of the task's dependency structure. By focusing on the dependency degree $k$, we can better understand why models succeed or fail at long-context reasoning. Predictive Position Coupling (PPC) offers a promising path forward for dynamically managing these dependencies, broadening the range of tasks where Transformers can successfully scale their context.
Summary updated