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).

13 min read1036 wordsadvanced0 viewsupdated 2026-10-12

Definition

Sparse attention restricts each query ii to a connectivity set Si⊂{1,…,n}S_i\subset\{1,\dots,n\} of keys and computes the usual softmax attention over SiS_i only. Scores outside SiS_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(∑i∣Si∣)O\big(\sum_i|S_i|\big) instead of O(n2)O(n^2). The Sparse Transformer of Child, Gray, Radford and Sutskever (2019) chose two patterns with ∣Si∣=O(n)|S_i|=O(\sqrt n) that together connect every pair of positions in two steps, which gives O(nn)O(n\sqrt n).

Dense self-attention stores and computes an n×nn\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×6464\times64 RGB image is 12,28812{,}288 tokens, and one second of 16 kHz audio is 16,00016{,}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

Attend(X,S)=(a(xi,Si))i=1n,a(xi,Si)=softmax ⁣((Wqxi) KSi⊤d)VSi,KSi=(Wkxj)j∈Si, VSi=(Wvxj)j∈Si\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}
SiS_i
the keys query ii may use. Dense causal attention is Si={j:j≤i}S_i=\{j:j\le i\}
Ai(m)A^{(m)}_i
in a factorized layer, pp separate heads or steps use subsets Ai(1),…,Ai(p)A^{(1)}_i,\dots,A^{(p)}_i, each of size about np\sqrt[p]{n}
validity\text{validity}
the paper requires that every j≤ij\le i can reach ii along a path of at most p+1p+1 positions through the A(m)A^{(m)}, so information can still flow between any pair within pp layers

Strided and fixed patterns

strided:  Ai(1)={t,…,i}, t=max⁡(0,i−l),Ai(2)={j:(i−j) mod l=0}fixed:  Ai(1)={j:⌊j/l⌋=⌊i/l⌋},Ai(2)={j:j mod l∈{l−c,…,l−1}}\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\}\}
ll
the stride, chosen close to n\sqrt n so that both sets have O(n)O(\sqrt n) elements
strided\textit{strided}
one head looks at the previous ll positions, the other at every ll-th earlier position. For an image of width ll these are "the row so far" and "the column above"
fixed\textit{fixed}
one head attends within the current block of ll positions; the other attends to cc "summary" positions at the end of every block, which carry information forward
cc
summary width; the paper found c∈{8,16,32}c\in\{8,16,32\} with l∈{128,256}l\in\{128,256\} to work well

All sets are intersected with j≤ij\le i for autoregressive models (see Causal attention). Two hops reach everything. In the strided pattern, ii reaches k=i−mlk=i-ml through A(2)A^{(2)}, and kk covers k−l,…,kk-l,\dots,k through A(1)A^{(1)}. In the fixed pattern, ii 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 hh layers it reaches only hlhl 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 ii.

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),…A^{(1)},A^{(2)},A^{(1)},\dots. A single merged head can attend to ⋃mAi(m)\bigcup_m A^{(m)}_i. Or the pp 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⊤QK^\top into b×bb\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.

query i (rows) attends key j (cols) · n = 64 · ■ A¹ ■ A² (not in A¹)j = 0 → 63 · grid = 4×4 kernel tiles · click a rowrow 45: ■ 1 hop ■ 2 hops ■ unreachable in 2stride l = 8 (√n = 8)pattern stridedrow i 45|A¹(i)| 9|A²(i) \ A¹(i)| 4keys scored by i 13 of 46reachable in 2 hops 46 of 46whole patternpairs scored 708 / 2080density vs causal 34.0%max keys per row 15pairs reached in 2 hops 100.0%hops to reach all 24×4 tiles touched 87 / 136▬ scored pairs ▬ tiles a block kernel runsstrided at n = 16384, l = 128:3.13M vs 134.2M pairs (43× fewer)= 1.49 · n√n
pattern
fig.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=16n=16 positions 0,…,150,\dots,15, stride l=4l=4 and summary width c=1c=1, and look at query i=10i=10. Strided: A10(1)={6,7,8,9,10}A^{(1)}_{10}=\{6,7,8,9,10\} and A10(2)={10,6,2}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}\{8,9,10,11\}, so A10(1)={8,9,10}A^{(1)}_{10}=\{8,9,10\}, and the summary cells j mod 4=3j\bmod4=3 before ii are {3,7}\{3,7\}, giving 5 keys.

patternkeys for i = 10pairs scoredpairs reached in 2 hopshops to reach all
dense causal11136100%1
local window (l = 4)57079.4%4
strided682100%2
fixed (c = 1)564100%2
Whole-pattern counts for n = 16, l = 4, c = 1 (enumerated in Node). Dense causal has 136 pairs.

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

  1. 1Positions 6,…,106,\dots,10 are scored directly by A10(1)A^{(1)}_{10}.
  2. 2Positions 3,4,53,4,5: route through k=6∈A10(2)k=6\in A^{(2)}_{10}, whose window A6(1)={2,…,6}A^{(1)}_6=\{2,\dots,6\} contains them.
  3. 3Positions 0,10,1: route through k=2∈A10(2)k=2\in A^{(2)}_{10}, whose window is {0,1,2}\{0,1,2\}.
  4. 4Local 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/li/l layers. At n=16n=16 it needs 4 hops for the full matrix.
  5. 5Counting: strided rows have min⁡(i,l)+1\min(i,l)+1 window entries plus ⌊i/l⌋\lfloor i/l\rfloor new strided ones, about l+n/(2l)l+n/(2l) on average. At l=nl=\sqrt n the total is about 1.5 nn1.5\,n\sqrt n; for n=16384n=16384, l=128l=128 it is exactly 3,129,4083{,}129{,}408 pairs.
python
1import torch, torch.nn.functional as F
2
3def strided_mask(n, l):
4 i, j = torch.arange(n)[:, None], torch.arange(n)[None, :]
5 a1 = (i - j) <= l # previous l positions and i itself
6 a2 = (i - j) % l == 0 # every l-th earlier position
7 return (j <= i) & (a1 | a2) # (n, n) bool, True = may attend
8
9def fixed_mask(n, l, c):
10 i, j = torch.arange(n)[:, None], torch.arange(n)[None, :]
11 a1 = (i // l) == (j // l) # same block of l
12 a2 = (j % l) >= l - c # last c cells of every block
13 return (j <= i) & (a1 | a2)
14
15ms, mf = strided_mask(16, 4), fixed_mask(16, 4, 1)
16print(ms.sum().item(), mf.sum().item(), 16 * 17 // 2) # 82 64 136
17print(ms[10].nonzero().flatten().tolist()) # [2, 6, 7, 8, 9, 10]
18
19causal = torch.ones(16, 16, dtype=torch.bool).tril()
20reach2 = (ms.float() @ ms.float()) > 0 # paths i -> k -> j
21print(bool((reach2 | ~causal).all())) # True: every j <= i in two hops
22
23B, H, n, d = 2, 4, 16, 32
24q, k, v = (torch.randn(B, H, n, d) for _ in range(3))
25out = F.scaled_dot_product_attention(q, k, v, attn_mask=ms) # bool mask: True = keep
26print(out.shape) # torch.Size([2, 4, 16, 32])
Strided and fixed causal masks, their size, two-hop reachability, and use as an attention mask

Use when

  • +O(nn)O(n\sqrt n) compute and memory with l≈nl\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)

Avoid when

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

Check yourself

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

Check yourself

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

Remember

  • ✓Sparse attention: query ii scores only keys in SiS_i; cost O(∑i∣Si∣)O(\sum_i|S_i|), which is O(nn)O(n\sqrt n) when ∣Si∣=O(n)|S_i|=O(\sqrt n) with stride l≈nl\approx\sqrt n.
  • ✓Sparse Transformer (Child et al., 2019): strided A(1)={i−l,…,i}A^{(1)}=\{i-l,\dots,i\}, A(2)={j:(i−j) mod l=0}A^{(2)}=\{j:(i-j)\bmod l=0\}; fixed A(1)A^{(1)} = same block, A(2)A^{(2)} = last cc 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.
← back to Deep Learning roadmap