Story of Attention — Part 4: Sparse Attention, Then and Now

Part 4 of 6 in the Story of Attention series.

1. Before the Transformer — how n-gram counting and RNN memory hit their ceilings, and how additive/multiplicative attention first let a decoder look back.
2. Attention All You Need — scaled dot-product attention, multi-head attention, and the four-year search for a way to encode position.
3. KV-Cache Bottleneck: MQA and GQA — sharing and grouping key/value heads to shrink inference memory.
4. Sparse Attention, Then and Now (this post) — fixed, windowed, hashed, and learned sparsity patterns, from 2019 to 2025.
5. Linear Attention: Kernels, Decay, and Gating — replacing softmax with decomposable kernels, decay, and gated recurrent state.
6. Where Attention Stands Today — latent compression, differential attention, and what frontier LLMs actually ship.

---

Sparse attention starts with a simple observation. When researchers looked at the attention maps of trained Transformers, most heads were not using their full $n \times n$ matrix. The weight was actually concentrated in structured patterns. So the obvious question becomes: why compute the parts nobody looks at? In the six years since the Sparse Transformer, that one question has gotten better answers: first a fixed stride pattern, then windows with a few global tokens, then content-based hashing, and finally a pattern the model learns for itself.

In the previous part, MQA and GQA shrank the KV cache, but every head still computes the full $n \times n$ attention matrix, so for long contexts that computation is still expensive. This part is about not computing most of that matrix in the first place.

---

1. Sparse Transformer

The very first version of this idea came from Child, Gray, Radford, and Sutskever in 2019 [1]. They looked at the attention maps of trained models and observed that most heads do not actually use their full receptive field, the attention concentrates in structured patterns. So they factorize attention into two complementary sparse patterns, one that strides across the sequence at fixed intervals and one that covers the local context, and stack them so that any position can reach any other in at most two hops.

Formally, let $S_i$ be the set of key indices query position $i$ may attend to.

Strided attention (periodic heads): position $i$ attends to keys at multiples of stride $s$:

$S_i^{(1)} = \{j \mid (i - j) \bmod s = 0\}$

Typically $s \approx \sqrt{n}$.

Local attention (fixed heads): position $i$ attends within its block of size $c$:

$S_i^{(2)} = \{j \mid \lfloor j/c \rfloor = \lfloor i/c \rfloor\}$

The softmax runs only over the permitted set, and the rest of the attention is unchanged:

$\text{Sparse-Attention}(Q, K, V)_i = \sum_{j \in S_i} \frac{\exp(q_i k_j^T / \sqrt{d_k})}{\sum_{m \in S_i} \exp(q_i k_m^T / \sqrt{d_k})} \, v_j$

With $|S_i| \approx \sqrt{n}$, total complexity drops from $O(n^2)$ to $O(n\sqrt{n})$.

Key result: Sparse attention does not change the attention formula; it changes the domain softmax runs over. Restricting each query to $|S_i| \approx \sqrt{n}$ keys cuts complexity from $O(n^2)$ to $O(n\sqrt{n})$, and every mechanism in this post is a different answer to the same question: which pairs can be skipped so that the quality of the response does not degrade?

Worked example

$n = 4$, $d_k = 4$, stride $s = 2$, $\sqrt{d_k} = 2$.

$Q = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 \end{bmatrix}, \quad K = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 2 & 1 \\ 1 & 0 & 0 & 1 \end{bmatrix}, \quad V = \begin{bmatrix} 2 & 0 & 1 & 1 \\ 1 & 3 & 0 & 0 \\ 0 & 1 & 4 & 2 \\ 1 & 2 & 0 & 5 \end{bmatrix}$

Raw scores $QK^T$:

$QK^T = \begin{bmatrix} 1 & 1 & 2 & 1 \\ 2 & 2 & 1 & 1 \\ 2 & 1 & 0 & 1 \\ 0 & 1 & 4 & 2 \end{bmatrix}$

Strided mask with $s = 2$ (1-indexed): Row 1 sees $\{1\}$, Row 2 sees $\{2\}$, Row 3 sees $\{1, 3\}$, Row 4 sees $\{2, 4\}$. Masked entries become $-\infty$:

$\text{Masked} = \begin{bmatrix} 1 & -\infty & -\infty & -\infty \\ -\infty & 2 & -\infty & -\infty \\ 2 & -\infty & 0 & -\infty \\ -\infty & 1 & -\infty & 2 \end{bmatrix}$

After scaling by 2 and applying softmax:

$A_\text{sparse} = \begin{bmatrix} 1.000 & 0 & 0 & 0 \\ 0 & 1.000 & 0 & 0 \\ 0.731 & 0 & 0.269 & 0 \\ 0 & 0.378 & 0 & 0.622 \end{bmatrix}$

Output:

$\text{Output} = A_\text{sparse} \times V = \begin{bmatrix} 2.000 & 0.000 & 1.000 & 1.000 \\ 1.000 & 3.000 & 0.000 & 0.000 \\ 1.462 & 0.269 & 1.807 & 1.269 \\ 1.000 & 2.378 & 0.000 & 3.110 \end{bmatrix}$

The paper evaluated on density estimation, measured in bits per byte on Enwik8 (a text-compression benchmark, lower is better) and bits per dimension on CIFAR-10 (image modeling, measured the same way) [1]:

The paper's own Table 2 ablation runs dense and sparse attention at the same context length: 12,288 tokens on Enwik8, 3,072 on CIFAR-10. Dense attention scores 1.00 bits/byte on Enwik8 there, barely behind the fixed sparse pattern's 0.99, and actually ahead of the strided pattern's 1.13. On CIFAR-10, dense scores 2.82, again close to the strided pattern's 2.80 and ahead of the fixed pattern's 2.85. So at matched context, the quality gap from sparsity alone is thin. The fixed pattern helps more on text, and the strided pattern helps more on images.

Context length matters on its own too. The paper's Table 3 shows bits-per-byte on Enwik8 dropping from 0.9952 to 0.9908 as the minimum evaluation context grows from 6,144 to 12,160 tokens, with the attention pattern unchanged. So longer context alone buys part of the improvement in the headline table above.

Sparsity's real advantage here shows up in compute. The fixed sparse pattern reaches its 0.99 score at 0.55 time per iteration, versus 1.31 for dense attention, using 95M parameters versus Transformer-XL's 277M for the same tied score. That efficiency is what let the sparse model reach 12,288 tokens of context in the first place.

But the sparse attention was not widely adopted. Using a fixed stride assumes the data has periodic structure. That is true of images, where a stride equal to the image width captures column relationships, but language does not have that kind of regularity. The two-hop routing through the factorized pattern can also dilute information over long distances. And the jagged index patterns are hardware-hostile. GPUs are optimized for dense matrix multiplies, and sparse indexing adds significant memory-access overhead. Sparsity reduces the compute, but the KV cache still stores every position, so the memory problem from Part 3 carries over unchanged, and every mechanism later in this post inherits it too.

The paper showed a very interesting point, that the quadratic calculation can be avoided and we do not have to compute most of the matrix. The next step was to find a pattern with fewer geometric assumptions.

---

2. Sliding-Window + Global Attention — Longformer

In 2020, Longformer [2] replaced the stride with a pattern that fits language better. Each token attends to a local window of $w$ neighbors, and some designated tokens called global tokens attend to and are attended by everything. So the local syntax and the global structure of the document are handled by two separate channels.

For a query at position $i$:

$\text{Attention Score}(Q_i, K_j) = \begin{cases} \text{softmax}\!\left(\frac{Q_i K_j^T}{\sqrt{d_k}}\right) & \text{if } |i - j| \leq w/2 \\ 0 & \text{otherwise} \end{cases}$

The result is a banded matrix: each token matches exactly $w$ others, for $O(n \cdot w)$ cost, and stacking $L$ layers grows the receptive field to $L \times w$, the same way CNNs see globally through stacked local filters. Adding $g$ global tokens costs $O(g \cdot n)$:

$\text{Total Complexity} = \underbrace{O(n \cdot w)}_\text{sliding window} + \underbrace{O(g \cdot n)}_\text{global tokens} = O(n)$

Since $w$ and $g$ are constants, the whole thing is linear in sequence length.

In case of a long-document tasks, seeing the full document beat truncating it [2]. The baseline is RoBERTa (Robustly Optimized BERT Pretraining Approach), a BERT variant capped at 512 tokens; the three columns are IMDB (binary movie-review sentiment classification, scored by accuracy), WikiHop (multi-hop question answering over Wikipedia, where the model picks the correct answer from a candidate set, scored by accuracy), and TriviaQA (reading-comprehension question answering, scored by F1, the overlap between the predicted answer and the ground truth answer):

We can see the improvement from context length almost immediately, because RoBERTa reads only 512 tokens of a document that Longformer reads completely in one go.

_{Each token attends to a local window of neighbors; a small set of global tokens attend to and are attended by the entire sequence. Redrawn from Beltagy et al., 2020 [2].}

Beyond Longformer and its encoder-decoder variant LED [2], the biggest adoption of this mechanism came later, in a stripped-down form. Mistral [3] ships sliding-window attention, without the global tokens, in a mainstream production LLM.

The limitation of this mechanism comes from its geometry. The receptive field is bounded by $L \times w$, so a 32-layer model with $w = 256$ tops out at around 8,192 tokens of effective reach. The global tokens must be chosen in advance by the engineer, and the model cannot promote a token to global status even if it is a very important one. And inside the window itself, the attention computation has not changed. It is still the full softmax, but applied over fewer keys.

Then the authors of BigBird looked at this pattern and asked, what does it take for a sparse attention graph to provably lose nothing?

---

3. BigBird

BigBird [4] keeps Longformer's window and global tokens, and adds a third ingredient, random connections. For query position $i$:

$S_i = \underbrace{S_i^\text{local}}_{\{j : |i-j| \leq w\}} \cup \underbrace{S_i^\text{global}}_{\{g_1, \ldots, g_g\}} \cup \underbrace{S_i^\text{random}}_{\text{r random indices}}$

Each row has $w + g + r$ non-zeros, all constants, so complexity stays $O(n \cdot (w + g + r))$, which is linear. Now why add random edges at all? They make the attention graph an expander with high probability, so information can flow between any two positions in $O(\log n)$ hops. From this, the authors prove that a sparse Transformer built this way is a universal approximator of sequence-to-sequence functions [4], which means sparsity does not cost the model anything in what it can represent.

_{Random attention has no structure; window attention is a local band; global attention is a few full rows and columns; BigBird combines all three. Redrawn from Zaheer et al., 2020 [4].}

The benchmark results on long-document QA supported this [4]:

So on long-document QA, BigBird clearly beats both RoBERTa and Longformer while scaling to 4,096 tokens, and the same pattern holds in summarization. BigBird-Pegasus reaches 46.63/19.02/41.77 ROUGE-1/2/L on Arxiv and 60.64/42.46/50.01 on BigPatent, ahead of base Pegasus on both [4].

And still no major production LLM adopted the random pattern. Random attention indices are scattered across the sequence, and that kind of irregular access can lead to poor GPU execution, which is why BigBird's own implementation blocks the random component into chunks rather than sampling individual token indices [4]. Mistral kept the local window and dropped the random and global parts. The universality theorem did not help either, because dense attention satisfies the same guarantee with better constants. The field learned about hardware from this, and later sparse designs kept their sparsity aligned with GPU block sizes.

All three mechanisms used so far share a common assumption. The model has its pattern fixed without even seeing the data. It does not matter if the pattern is a stride, a window, or a random graph; the choice is made in advance. So which tokens can attend to which comes from the geometry of the pattern. The actual words in the text do not play any role at all. The Reformer was the first to break this assumption.

---

4. LSH Attention — Reformer

In 2020, Kitaev, Kaiser, and Levskaya [5] started from an observation about what softmax actually does. After the exponential, each query's output is dominated by the few keys it scores highest against. The rest of the scores are computed and then ignored. So if those few high-scoring pairs could be found without computing all the scores, then a quality drop can be avoided. And finding approximate nearest neighbors quickly is a solved problem in computer science; the standard tool for it is locality-sensitive hashing.

The construction has three steps. First, queries and keys share projection weights ($W^Q = W^K$) and are L2-normalized onto a unit sphere:

$q_i = k_i = \frac{h_i W^Q}{\|h_i W^Q\|_2}$

Second, a random projection $R \in \mathbb{R}^{d_k \times b/2}$ partitions the sphere into $b$ buckets:

$h(q_i) = \arg\max_{j \in \{0, \ldots, b-1\}} [p_i,\; -p_i]_j \quad \text{where } p_i = q_i R$

Similar vectors land in the same bucket with probability proportional to their similarity:

$P[h(q_i) = h(q_j)] = 1 - \frac{\theta(q_i, q_j)}{\pi}$

Third, attention runs only within buckets:

$\text{LSH-Attention}(Q, K, V)_i = \sum_{j \in P_i} \frac{\exp(q_i k_j^T / \sqrt{d_k})}{\sum_{m \in P_i} \exp(q_i k_m^T / \sqrt{d_k})} v_j$

where $P_i = \{j \mid h(q_i) = h(q_j) \text{ and } j \in C_i\}$ and $C_i$ is the sorted chunk containing $i$.

On quality, the approximation held up [5]:

So the quality is identical, in far less memory. The Reformer's real contribution was that much longer sequences could fit on a device.

Even after that, adoption was very limited. Sharing $Q = K$ costs the model asymmetric attention. A question can attend to its answer, but with tied projections the reverse relationship is forced to look the same. Hashing is also probabilistic, so similar tokens sometimes land in different buckets. Pushing that error down requires multiple hashing rounds, and that brings back the overhead the method was built to remove. Both problems come back to the same wall the Sparse Transformer ran into. The bucketed, sorted, chunked access patterns fight the GPU.

In the year 2023, an observation explains why the windowed models above cannot simply forget their oldest tokens, and any sparse or windowed deployment has to design around it.

---

5. Attention Sinks

Xiao et al. [6] found this while trying to make windowed inference work on streaming inputs. In autoregressive Transformers, the first few tokens of the sequence accumulate outsized attention weights, regardless of what those tokens actually say. Why does this happen? Softmax has to put its probability mass somewhere, its weights always sum to one. So when a head finds nothing relevant in the context, the early positions, which are visible to every later token, become the default place for that mass to go. These heavily attended early tokens are called attention sinks.

The practical consequence shows up immediately. Suppose we run a sliding-window cache that prunes the oldest tokens. The moment the sink tokens slide out of the window, generation quality collapses. Perplexity spikes on content the model was handling fine moments earlier, even though it lost only a few tokens that carried almost no meaning. One of the simplest possible fixes could be:

$\text{KV cache at step } t = \{\underbrace{h_1, \ldots, h_k}_\text{sink tokens}\} \cup \{\underbrace{h_{t-w+1}, \ldots, h_t}_\text{recent window}\}$

Keep the first $k$ tokens forever (typically $k = 4$ is enough), keep the recent $w$ tokens, and prune everything in between. The total cache is $k + w$, a constant, so the model can keep generating for effectively unbounded length. And with the sinks preserved, perplexity tracks the full-cache baseline at any length [6].

This is a deployment observation rather than an architecture. Attention within the window is still quadratic, and not all the tokens are there; the model cannot remember the fact from a position it already dropped. Every pattern in this post so far, strided, windowed, random, hashed, or sink-preserving, is a rule imposed from outside the model, not something the model learned. The most recent generation of sparse attention finally moves that decision inside the model.

---

6. Native Sparse Attention — NSA

Native Sparse Attention, introduced by Yuan et al. in 2025 [7], turns the architecture of everything above upside down. Instead of choosing a sparsity pattern and training a model under it, NSA makes the pattern learnable and lets pre-training discover it, while keeping every block aligned to how GPUs actually read memory. The name comes from this: sparsity is a native property of the trained model.

The mechanism combines three pathways, weighted by learned gates:

1. Compressed global attention — split the KV sequence into blocks and average each block into a rough summary:

$K_\text{global} = \text{BlockMean}(K, b)$

1. Selected sparse attention — score blocks against the coarse keys, keep the top-$k$, attend to those in full detail:

$\text{scores} = q \cdot K_\text{global}^T, \quad \text{selected} = \text{TopK}(\text{scores}, k)$

$A_\text{sparse} = \text{softmax}(Q K_\text{selected}^T / \sqrt{d_k})\, V_\text{selected}$

1. Sliding window — fine-grained local context.

$\text{Output} = g_1 \cdot A_\text{global} + g_2 \cdot A_\text{sparse} + g_3 \cdot A_\text{local}$

NSA was proposed by DeepSeek researchers and validated on their own pretrained models [7]. It is a separate line of work from MLA, the mechanism DeepSeek-V3 itself ships with [8].

NSA has its own costs. The pipeline runs in stages. It scores roughly, picks the blocks, loads them, and then attends, while dense attention does not have to go through any of these stages. Training is also awkward, because the top-$k$ block selection is discrete. The importance scores that decide which blocks get selected come from a differentiable softmax over the compressed blocks, so gradients do reach that scoring step, but the paper does not fully spell out how gradients are handled through the discrete selection itself. But a deeper limit remained untouched through six years of this line of work. Sparsity, whether a human designed it or the model learned it, only decides where attention looks. For the pairs that survive, the computation is still the same as it was in 2017, a softmax over $QK^T$. Changing that requires changing the formula itself.

---

What comes next

In this part, we went through the main ways of not computing the complete attention matrix. We saw fixed geometric patterns (Sparse Transformer, Longformer, BigBird), content-based hashing (Reformer), the attention-sink observation that makes windowed caching workable, and finally a learned pattern (NSA) that lets the model pick its own sparsity. But every one of them keeps softmax exactly as it was, and just skips most of the pairs.

The next part takes a completely different approach. Instead of skipping pairs, it changes what happens to the pairs that are kept. If softmax is replaced with a decomposable kernel, the $n \times n$ matrix never has to be built in the first place. That line of work runs from Katharopoulos's original linear attention, through cosFormer's decay and RetNet's dual recurrent form, to the gated linear-attention variants inside 2025's longest-context models.

Continue to Part 5: Linear Attention →

---

References

[1] Child, R., Gray, S., Radford, A., & Sutskever, I. (2019). Generating Long Sequences with Sparse Transformers. arXiv:1904.10509.

[2] Beltagy, I., Peters, M. E., & Cohan, A. (2020). Longformer: The Long-Document Transformer. arXiv:2004.05150.

[3] Jiang, A. Q., Sablayrolles, A., Mensch, A., et al. (2023). Mistral 7B. arXiv:2310.06825.

[4] Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontañón, S., Pham, P., Ravula, A., Wang, Q., Yang, L., & Ahmed, A. (2020). Big Bird: Transformers for Longer Sequences. NeurIPS 2020. arXiv:2007.14062.

[5] Kitaev, N., Kaiser, L., & Levskaya, A. (2020). Reformer: The Efficient Transformer. ICLR 2020. arXiv:2001.04451.

[6] Xiao, G., Tian, Y., Chen, B., Han, S., & Lewis, M. (2023). Efficient Streaming Language Models with Attention Sinks. arXiv:2309.17453.

[7] Yuan, J., Gao, H., Dai, D., Luo, J., Zhao, L., Zhang, Z., Xie, Z., Wei, Y. X., Wang, L., Xiao, Z., Wang, Y., Ruan, C., Zhang, M., Liang, W., & Zeng, W. (2025). Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention. arXiv:2502.11089.

[8] DeepSeek-AI (2024). DeepSeek-V3 Technical Report. arXiv:2412.19437.