# Sparse attention

> Sparse attention lets each query score only a fixed subset of keys, such as a local window, every l-th position or a block, instead of all n. With l ≈ √n and patterns chosen so any position reaches any other in two hops, cost falls from O(n²) to O(n√n) (Child et al., 2019).

Source: https://www.mlfoundry.in/learn/sparse-attention  
Section: Deep Learning › Attention and Transformer Architectures  
Level: advanced · 13 min read · updated 2026-10-12

**Sparse attention:** restricts each query $i$ to a **connectivity set** $S_i\subset\{1,\dots,n\}$ of keys and computes the usual softmax attention over $S_i$ only. Scores outside $S_i$ are never computed. In the **fixed-pattern** family the sets come from position alone: a local window, a stride, a block structure, or a few global tokens. Cost becomes $O\big(\sum_i|S_i|\big)$ instead of $O(n^2)$. The Sparse Transformer of Child, Gray, Radford and Sutskever (2019) chose two patterns with $|S_i|=O(\sqrt n)$ that together connect every pair of positions in two steps, which gives $O(n\sqrt n)$.

Dense self-attention stores and computes an $n\times n$ matrix in every head of every layer. At the lengths where attention is most attractive, such as images flattened to pixels, raw audio or long documents, this is the bottleneck. A $64\times64$ RGB image is $12{,}288$ tokens, and one second of 16 kHz audio is $16{,}000$. Rewon Child, Scott Gray, Alec Radford and Ilya Sutskever, "Generating Long Sequences with Sparse Transformers" (OpenAI, arXiv 2019), looked at the attention maps of a dense 128-layer model trained on CIFAR-10. Many heads learned sparse, structured patterns: attention to nearby pixels, to the same column, or to a few positions. They built such patterns in by hand, wrote block-sparse GPU kernels for them, and reached state-of-the-art density modelling of images, text and audio with sequence lengths up to tens of thousands. In their words, the work showed "it is possible in principle to use self-attention to model sequences of length one million or more".

## Factorized self-attention

$$
\mathrm{Attend}(X,S)=\Big(a(x_i,S_i)\Big)_{i=1}^{n},\qquad a(x_i,S_i)=\mathrm{softmax}\!\Big(\frac{(W_qx_i)\,K_{S_i}^\top}{\sqrt d}\Big)V_{S_i},\qquad K_{S_i}=\big(W_kx_j\big)_{j\in S_i},\ V_{S_i}=\big(W_vx_j\big)_{j\in S_i}
$$

- $S_i$: the keys query $i$ may use. Dense causal attention is $S_i=\{j:j\le i\}$
- $A^{(m)}_i$: in a **factorized** layer, $p$ separate heads or steps use subsets $A^{(1)}_i,\dots,A^{(p)}_i$, each of size about $\sqrt[p]{n}$
- $\text{validity}$: the paper requires that every $j\le i$ can reach $i$ along a path of at most $p+1$ positions through the $A^{(m)}$, so information can still flow between any pair within $p$ layers

## Strided and fixed patterns

$$
\textit{strided:}\ \ A^{(1)}_i=\{t,\dots,i\},\ t=\max(0,i-l),\qquad A^{(2)}_i=\{j:(i-j)\bmod l=0\}\qquad\qquad \textit{fixed:}\ \ A^{(1)}_i=\{j:\lfloor j/l\rfloor=\lfloor i/l\rfloor\},\qquad A^{(2)}_i=\{j:j\bmod l\in\{l-c,\dots,l-1\}\}
$$

- $l$: the stride, chosen close to $\sqrt n$ so that both sets have $O(\sqrt n)$ elements
- $\textit{strided}$: one head looks at the previous $l$ positions, the other at every $l$-th earlier position. For an image of width $l$ these are "the row so far" and "the column above"
- $\textit{fixed}$: one head attends within the current block of $l$ positions; the other attends to $c$ "summary" positions at the end of every block, which carry information forward
- $c$: summary width; the paper found $c\in\{8,16,32\}$ with $l\in\{128,256\}$ to work well

All sets are intersected with $j\le i$ for autoregressive models (see **Causal attention**). Two hops reach everything. In the strided pattern, $i$ reaches $k=i-ml$ through $A^{(2)}$, and $k$ covers $k-l,\dots,k$ through $A^{(1)}$. In the fixed pattern, $i$ reaches the summary cells of every earlier block, and each summary cell has seen its whole block. A plain local window does not have this property: after $h$ layers it reaches only $hl$ positions back. The strided pattern suits data with a period, such as images and music. For text, which has no period, the fixed pattern worked better, because a position can then use a summary cell no matter how far it is from $i$.

The patterns enter the network in one of three ways. One pattern can be used per residual block, alternating $A^{(1)},A^{(2)},A^{(1)},\dots$. A single merged head can attend to $\bigcup_m A^{(m)}_i$. Or the $p$ patterns can be different heads of one **Multi-head attention** layer whose outputs are concatenated. The patterns are fixed in advance, so their tile structure is known when the kernel is compiled. A **block-sparse** kernel splits $QK^\top$ into $b\times b$ tiles and runs dense matrix products only on tiles that contain allowed entries. Patterns aligned with the tiles waste almost nothing. Patterns that scatter single entries across many tiles pay for whole tiles.

**Sparse Transformer: setup and results (Child et al., 2019)**

- **Patterns:** strided for CIFAR-10, ImageNet 64×64 and audio; fixed for Enwik8 text
- **CIFAR-10:** 2.80 bits per dim, against 2.85 for PixelSNAIL
- **Enwik8:** 0.99 bits per byte with 95M parameters and a context of 12,288 bytes, matching a Transformer-XL with 277M parameters
- **ImageNet 64×64:** 3.44 bits per dim
- **Engineering:** block-sparse GPU kernels, recomputation of attention and feed-forward activations in the backward pass, pre-activation residual blocks with depth-scaled initialisation, mixed precision; networks hundreds of layers deep

Fixed patterns became a standard tool. GPT-3 (Brown et al., 2020) alternates dense and locally banded sparse attention between layers, "similar to the Sparse Transformer". **Longformer** combines a sliding window, dilated windows and a few global tokens. **BigBird** adds random keys to window and global ones and proves the result is still a universal approximator of sequence functions. Other models learn the sparsity from content instead, such as **Reformer** with locality-sensitive hashing. **Linear attention**, **Linformer** and **Performer** keep every pair but approximate the softmax with low-rank or kernel features.

> Figure: 64 causal positions, stride l = 8 = √64. The strided pattern scores 708 of the 2080 causal pairs (34.0%), at most 15 keys per row, and two hops already reach 100% of the pairs. The local window alone (the previous l positions) scores 540 pairs (26.0%), but two hops reach only 45.8% of the pairs, and covering everything takes 8 hops. Narrow the window to l = 4 and 12 hops are still not enough. Fixed with c = 1 is the sparsest valid pattern here: 512 pairs (24.6%), all reachable in 2 hops; c = 2 raises it to 736. The strip under the grid shows, for the selected row, which keys are scored directly, which are reached through one intermediate position, and which cannot be reached. The tile counter shows the cost of a block-sparse kernel with 4×4 tiles. The local window touches 45 of 136 tiles. Strided touches 87, because its column entries land in many tiles; with l = 4 or 2 it touches all 136, so a block kernel saves nothing. The panel bottom right gives the exact count at a realistic size: n = 16384 with l = 128 is 3.13M pairs against 134.2M dense causal ones, 43× fewer and 1.49·n√n.

## Worked example: 16 positions, l = 4

Take $n=16$ positions $0,\dots,15$, stride $l=4$ and summary width $c=1$, and look at query $i=10$. Strided: $A^{(1)}_{10}=\{6,7,8,9,10\}$ and $A^{(2)}_{10}=\{10,6,2\}$, so row 10 scores 6 of its 11 causal keys. Fixed: the block of 10 is $\{8,9,10,11\}$, so $A^{(1)}_{10}=\{8,9,10\}$, and the summary cells $j\bmod4=3$ before $i$ are $\{3,7\}$, giving 5 keys.

Whole-pattern counts for n = 16, l = 4, c = 1 (enumerated in Node). Dense causal has 136 pairs.

| pattern | keys for i = 10 | pairs scored | pairs reached in 2 hops | hops to reach all |
| --- | --- | --- | --- | --- |
| dense causal | 11 | 136 | 100% | 1 |
| local window (l = 4) | 5 | 70 | 79.4% | 4 |
| strided | 6 | 82 | 100% | 2 |
| fixed (c = 1) | 5 | 64 | 100% | 2 |

**Why row 10 of the strided pattern reaches every earlier position in two hops**

1. Positions $6,\dots,10$ are scored directly by $A^{(1)}_{10}$.
2. Positions $3,4,5$: route through $k=6\in A^{(2)}_{10}$, whose window $A^{(1)}_6=\{2,\dots,6\}$ contains them.
3. Positions $0,1$: route through $k=2\in A^{(2)}_{10}$, whose window is $\{0,1,2\}$.
4. Local window only: from 10, one hop reaches 6, two hops reach 2. Positions 0 and 1 need a third layer, and in general the window needs about $i/l$ layers. At $n=16$ it needs 4 hops for the full matrix.
5. Counting: strided rows have $\min(i,l)+1$ window entries plus $\lfloor i/l\rfloor$ new strided ones, about $l+n/(2l)$ on average. At $l=\sqrt n$ the total is about $1.5\,n\sqrt n$; for $n=16384$, $l=128$ it is exactly $3{,}129{,}408$ pairs.

```python
import torch, torch.nn.functional as F

def strided_mask(n, l):
    i, j = torch.arange(n)[:, None], torch.arange(n)[None, :]
    a1 = (i - j) <= l                     # previous l positions and i itself
    a2 = (i - j) % l == 0                 # every l-th earlier position
    return (j <= i) & (a1 | a2)           # (n, n) bool, True = may attend

def fixed_mask(n, l, c):
    i, j = torch.arange(n)[:, None], torch.arange(n)[None, :]
    a1 = (i // l) == (j // l)             # same block of l
    a2 = (j % l) >= l - c                 # last c cells of every block
    return (j <= i) & (a1 | a2)

ms, mf = strided_mask(16, 4), fixed_mask(16, 4, 1)
print(ms.sum().item(), mf.sum().item(), 16 * 17 // 2)    # 82 64 136
print(ms[10].nonzero().flatten().tolist())                # [2, 6, 7, 8, 9, 10]

causal = torch.ones(16, 16, dtype=torch.bool).tril()
reach2 = (ms.float() @ ms.float()) > 0                    # paths i -> k -> j
print(bool((reach2 | ~causal).all()))                     # True: every j <= i in two hops

B, H, n, d = 2, 4, 16, 32
q, k, v = (torch.randn(B, H, n, d) for _ in range(3))
out = F.scaled_dot_product_attention(q, k, v, attn_mask=ms)  # bool mask: True = keep
print(out.shape)                                          # torch.Size([2, 4, 16, 32])
```

Strided and fixed causal masks, their size, two-hop reachability, and use as an attention mask

> **A mask is not a sparse kernel:** The last lines of the code give the right *outputs* of sparse attention, but dense SDPA with a boolean mask still computes and stores all $n^2$ scores. Some backends even fall back to a slower path when a mask is passed. The $O(n\sqrt n)$ saving appears only with a kernel that skips the masked entries, in practice tile by tile: OpenAI's blocksparse kernels, Triton or DeepSpeed block-sparse attention, or block-sparse **FlashAttention**. Design patterns at the kernel's tile size, otherwise a few scattered entries force whole tiles to be computed.

> **Sparsity trades width for depth:** A sparse layer is a sparse graph over positions, and stacking layers composes the graph. Dense attention connects everything in one hop. The strided and fixed patterns connect everything in two hops with $O(\sqrt n)$ edges per node, so a deep network loses no reach. The local window has diameter $n/l$, which is why window-only models such as **Longformer** add global tokens and models such as **BigBird** add random edges, which shrink the graph's diameter.

> **Fixed versus learned sparsity:** Fixed patterns are cheap and known before the forward pass, so they compile to efficient kernels. The model cannot attend to a relevant token that lies outside the pattern except through intermediate positions, and each hop adds information loss. Content-based schemes (LSH in **Reformer**, clustering in the Routing Transformer) choose keys per query at the cost of irregular memory access. Kernel and low-rank methods (**Performer**, **Linformer**) avoid sparsity altogether.

**Strengths**

- $O(n\sqrt n)$ compute and memory with $l\approx\sqrt n$, exact softmax over the chosen keys
- Strided and fixed patterns keep two-hop paths between all positions
- Patterns are known in advance, so block-sparse kernels can exploit them
- Matches the structure dense models often learn (local, row and column attention in images)

**Limitations**

- Fixed patterns ignore content; a key outside the pattern is reachable only indirectly
- Requires specialised kernels; dense masking gives no speed-up
- Pattern hyperparameters ($l$, $c$, window, global tokens) depend on the data's structure
- The strided pattern assumes periodic data and works worse on text than the fixed one

**Question:** In a causal strided pattern with stride l, why can every position j ≤ i influence position i after two layers?

- A. Because the local window covers all earlier positions
- B. Because i reaches k = i − ml through the strided head, and k's local window covers k − l … k, so the windows of the strided positions tile the whole prefix
- C. Because softmax spreads weight to all positions
- D. Because the residual stream carries all tokens to every position

**Answer:** B. Because i reaches k = i − ml through the strided head, and k's local window covers k − l … k, so the windows of the strided positions tile the whole prefix — The strided head of $i$ hits $i,\,i-l,\,i-2l,\dots$; each of those windows covers the $l$ positions before it. Together they cover $0,\dots,i$. A window-only model needs about $i/l$ layers for the same reach.

**Question:** You apply a strided boolean mask with F.scaled_dot_product_attention at n = 16384. What do you gain?

- A. About 43× fewer FLOPs, since only 3.1M of 134M pairs are allowed
- B. The outputs of strided sparse attention, but no compute or memory saving: all n² scores are still formed
- C. Linear memory, because the mask is boolean
- D. Nothing; boolean masks are ignored

**Answer:** B. The outputs of strided sparse attention, but no compute or memory saving: all n² scores are still formed — The mask only replaces disallowed scores with $-\infty$ after a dense $QK^\top$. Savings need a kernel that never computes the masked tiles, such as a block-sparse kernel or block-sparse FlashAttention.

**Key points**

- Sparse attention: query $i$ scores only keys in $S_i$; cost $O(\sum_i|S_i|)$, which is $O(n\sqrt n)$ when $|S_i|=O(\sqrt n)$ with stride $l\approx\sqrt n$.
- Sparse Transformer (Child et al., 2019): strided $A^{(1)}=\{i-l,\dots,i\}$, $A^{(2)}=\{j:(i-j)\bmod l=0\}$; fixed $A^{(1)}$ = same block, $A^{(2)}$ = last $c$ cells of every block. Both connect all pairs in two hops.
- Local windows alone need about n/l layers to connect distant tokens; global or random tokens (Longformer, BigBird) shorten the paths.
- Speed-ups require block-sparse kernels; a dense masked attention gives the same outputs at full O(n²) cost.
- Results: CIFAR-10 2.80 bits/dim, Enwik8 0.99 bits/byte with 95M parameters, ImageNet 64×64 3.44 bits/dim.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
