Definition
Sparse attention restricts each query to a connectivity set of keys and computes the usual softmax attention over only. Scores outside 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 instead of . The Sparse Transformer of Child, Gray, Radford and Sutskever (2019) chose two patterns with that together connect every pair of positions in two steps, which gives .
Dense self-attention stores and computes an 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 RGB image is tokens, and one second of 16 kHz audio is . 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
- the keys query may use. Dense causal attention is
- in a factorized layer, separate heads or steps use subsets , each of size about
- the paper requires that every can reach along a path of at most positions through the , so information can still flow between any pair within layers
Strided and fixed patterns
- the stride, chosen close to so that both sets have elements
- one head looks at the previous positions, the other at every -th earlier position. For an image of width these are "the row so far" and "the column above"
- one head attends within the current block of positions; the other attends to "summary" positions at the end of every block, which carry information forward
- summary width; the paper found with to work well
All sets are intersected with for autoregressive models (see Causal attention). Two hops reach everything. In the strided pattern, reaches through , and covers through . In the fixed pattern, 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 layers it reaches only 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 .
The patterns enter the network in one of three ways. One pattern can be used per residual block, alternating . A single merged head can attend to . Or the 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 into 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.
Worked example: 16 positions, l = 4
Take positions , stride and summary width , and look at query . Strided: and , so row 10 scores 6 of its 11 causal keys. Fixed: the block of 10 is , so , and the summary cells before are , giving 5 keys.
| 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
- 1Positions are scored directly by .
- 2Positions : route through , whose window contains them.
- 3Positions : route through , whose window is .
- 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 layers. At it needs 4 hops for the full matrix.
- 5Counting: strided rows have window entries plus new strided ones, about on average. At the total is about ; for , it is exactly pairs.
1import torch, torch.nn.functional as F23def 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 itself6 a2 = (i - j) % l == 0 # every l-th earlier position7 return (j <= i) & (a1 | a2) # (n, n) bool, True = may attend89def 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 l12 a2 = (j % l) >= l - c # last c cells of every block13 return (j <= i) & (a1 | a2)1415ms, mf = strided_mask(16, 4), fixed_mask(16, 4, 1)16print(ms.sum().item(), mf.sum().item(), 16 * 17 // 2) # 82 64 13617print(ms[10].nonzero().flatten().tolist()) # [2, 6, 7, 8, 9, 10]1819causal = torch.ones(16, 16, dtype=torch.bool).tril()20reach2 = (ms.float() @ ms.float()) > 0 # paths i -> k -> j21print(bool((reach2 | ~causal).all())) # True: every j <= i in two hops2223B, H, n, d = 2, 4, 16, 3224q, 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 = keep26print(out.shape) # torch.Size([2, 4, 16, 32])Use when
- + compute and memory with , 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 (, , 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 scores only keys in ; cost , which is when with stride .
- ✓Sparse Transformer (Child et al., 2019): strided , ; fixed = same block, = last 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.