Sparse Attention Patterns › The Sparsity Principle
Language AI HandbookAll chapters Sparse Attention Patterns › The Sparsity PrincipleOne section · Sections in this chapter2 / 13 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Before diving into specific patterns, let's understand why sparsity works. In natural language, most dependencies are local: a word is most strongly influenced by nearby words. Long-range dependencies exist but are relatively rare. Consider the sentence "The cat that the dog chased ran away." The verb "ran" primarily depends on "cat" (its subject), not on every intervening word. A sparse attention pattern that captures this key dependency while ignoring irrelevant pairs can achieve similar quality to full attention at a fraction of the cost.
The sparsity principle rests on an empirical observation that researchers confirmed early in the development of transformers: trained attention heads are rarely uniformly distributed. When you inspect the attention weight matrices of a trained BERT or GPT model, you find that most entries are very close to zero. The softmax distribution is concentrated, not flat. Some query-key pairs receive nearly all the probability mass, while hundreds of other pairs share a tiny residual. This concentration reflects the structure of language: meaning is local, syntactic dependencies are bounded, and truly global relationships are rare.
Think of a full attention matrix as a complete graph where every node is connected to every other node. A sparse attention pattern is like a sparser graph where each node connects only to its immediate neighbors and a small set of "highways" for long-distance travel. The graph does not need to be complete for information to flow everywhere. If you choose the sparse connections carefully, you can guarantee that any two nodes are still connected through a short path. The transformer's depth, its multiple stacked layers, does the rest: information missing from one layer's direct connections can be picked up indirectly through intermediate positions in subsequent layers.
Sparse attention restricts each query to attend only to a subset of keys. If each query attends to keys instead of all , complexity drops from to , where is the sequence length and is the number of keys each query attends to. When is constant or grows slowly with , this achieves effective linear scaling.
The quadratic bottleneck in transformer attention was recognized almost as soon as the architecture was proposed in 2017. Early attempts to address it included memory-efficient implementations and gradient checkpointing, but these were engineering workarounds rather than algorithmic improvements. The first principled sparse attention approach appeared in 2019 with the Sparse Transformer paper from OpenAI, which demonstrated that factorized sparse patterns could match full attention quality on language modeling benchmarks while processing sequences four to eight times longer. This opened a research wave that produced Longformer (2020) and BigBird (2020), each combining local windows with global tokens in different ways. The sparse attention patterns in this chapter represent the foundational ideas from this period: the basic building blocks that more sophisticated architectures compose and extend.
Let's visualize how attention weights are distributed in practice to motivate sparsity.
import numpy as np
# Simulate attention weights for a 64-token sequence
# In real transformers, weights tend to be concentrated on nearby tokens
seq_len = 64
# Create simulated attention pattern with local bias
# Each row sums to 1 (softmax output)
attention_weights = np.zeros((seq_len, seq_len))
for i in range(seq_len):
# High attention to nearby positions, decaying with distance
for j in range(seq_len):
distance = abs(i - j)
# Exponential decay with distance, plus small baseline
attention_weights[i, j] = np.exp(-distance / 5) + 0.01
# Normalize to sum to 1
attention_weights[i] /= attention_weights[i].sum()
Attention sparsity analysis (threshold=0.01): Positions below threshold: 66.5% Coverage from top-10 positions per query: 64.8% Full attention computes: 4,096 scores Top-10 sparse attention: 640 scores (15.6%)
The analysis reveals a key insight: attention weights are highly concentrated. Most of the attention mass falls on a small number of positions per query, while the majority of positions receive negligible weight. This natural sparsity suggests we can skip computing many attention scores without significantly affecting the output.
Notice that even our simulated distribution, which uses a simple exponential decay rather than real transformer weights, shows dramatic concentration. The top 10 positions per query capture the vast majority of total attention mass. In real trained transformers, the concentration is often sharper because the model learns to focus attention even more precisely through training. This observation is what gives researchers confidence that sparsity won't break the model: if you only skip positions that would have had near-zero weight anyway, the output changes very little.
In practice, this principle has a direct implication for engineering. You do not need a perfectly optimal sparse mask that always selects exactly the positions that would have had high weight. You need a mask that reliably covers the positions that matter for most inputs. Local attention, strided attention, and block-sparse attention are all heuristics in this sense: they do not know in advance which positions a given query will want to attend to, but they bet that nearby positions and a few strategic long-range anchors will cover most of the important cases.