Sparse attention 1 (static): Sparse Transformer, Longformer, BigBird, StreamingLLM
Full attention compares every token with every other token, so its cost grows with the square of the length. Static sparse attention fixes in advance which pairs are computed: a local window, a few global tokens, some random links, a stride. This session builds these patterns one by one (Sparse Transformer, Longformer, BigBird), then shows how StreamingLLM and sliding-window models such as Mistral use the same idea to keep the KV cache at a fixed size during decoding.
What you will learn
- How to describe any sparse attention as a set of allowed keys per query, and how to count its cost
- The four building blocks: local window, dilated window, global tokens and random links, and what each one adds
- Sparse Transformer: strided and fixed patterns, and why a stride near the square root of n gives O(n√n) cost
- Longformer: sliding and dilated windows, receptive field growth over layers, and global attention on task tokens
- BigBird: why local + global + random keeps the expressive power of full attention, and the blocked implementation
- StreamingLLM: why removing the first tokens breaks a model (attention sinks), and how a sink + window cache streams millions of tokens
- How static patterns cap the KV cache during decoding (Mistral rolling buffer, Gemma 2 local and global layers), with real memory numbers
Why this matters
In full attention, every query compares itself with every key. With \(n\) tokens that is \(n^2\) scores per head and per layer. At \(n = 4096\) this is 16.8 million scores; at \(n = 131{,}072\) it is 17.2 billion. The cost of the table grows four times each time the text gets twice as long.
But a trained model does not use most of that table. Most attention weight goes to nearby tokens, plus a few special tokens that everybody looks at. Sparse attention uses this fact: it computes only some of the query-key pairs and treats the others as if their weight were zero. This session is about static sparse attention: the set of computed pairs is fixed before the model sees the input. (In session 117 the pairs are chosen from the input itself.)
The efficient-inference survey of Zhou et al. puts sparse attention under model compression, in its sparsification section (5.2.2). It splits it into static patterns, which "remove activation values independently of specific inputs", and dynamic ones. Its static examples are exactly the four of this session: Sparse Transformer, Longformer, BigBird and StreamingLLM. [Certain]
- Sparse Transformer (Child et al., 2019): a local window plus a stride, which gives cost \(O(n\sqrt n)\) instead of \(O(n^2)\).
- Longformer (Beltagy et al., 2020): a sliding window, a dilated window, and "global" attention on a few task tokens. Cost \(O(n)\).
- BigBird (Zaheer et al., 2020): window + global + random links, with a proof that this keeps the power of full attention.
- StreamingLLM (Xiao et al., 2023): a window plus the first four tokens, the "attention sinks". It lets an unchanged pretrained LLM generate millions of tokens with a fixed-size KV cache.
The last point is why this topic matters so much for serving. During decoding, a static pattern that only looks back a fixed distance means old keys and values can be deleted. Mistral 7B and Gemma 2 use sliding windows partly for this reason. [Certain]
Sparse attention as a set of allowed keys
We need one language for all patterns. For each query position \(i\), let \(S_i\) be the set of key positions it is allowed to see. Attention is then the usual formula, but the softmax runs only over \(S_i\):
- Read the symbols
- \(\mathbf{q}_i, \mathbf{k}_j, \mathbf{v}_j\)
- query of token \(i\), key and value of token \(j\), each with \(d\) numbers
- \(S_i\)
- the allowed keys of query \(i\): the "pattern". Full causal attention uses \(S_i = \{0, 1, \dots, i\}\)
- \(\alpha_{ij}\)
- attention weight; it sums to 1 over \(S_i\), and is 0 for every \(j\) outside \(S_i\)
- \(\mathbf{o}_i\)
- the output for query \(i\): a weighted average of the allowed values
This is the same as writing a mask with \(-\infty\) for forbidden pairs before the softmax. The cost is the number of scores we compute, which is the size of all the sets together:
A good pattern has two properties. First, small sets: \(|S_i|\) should not grow with \(n\) (or only slowly). Second, information must still be able to travel. One layer may only connect \(i\) to its set, but after several layers, token \(j\) can reach token \(i\) through a chain of tokens. If we draw an arrow \(j \to i\) for every \(j \in S_i\), the number of layers needed is the length of the shortest path. Full attention needs 1 layer for every pair. A sparse pattern needs more, and the question is how many.
The four building blocks
Almost every static pattern is a union of four simple sets. Let \(r\) be the window radius, \(d_{\text{il}}\) the dilation, \(G\) a small set of global positions and \(R_i\) a few random positions chosen once, before training:
- Read the symbols
- \(r\)
- how many neighbors on each side a token sees (Longformer writes the full window as \(w = 2r\))
- \(d_{\text{il}}\)
- the gap between attended tokens in a dilated window; \(d_{\text{il}} = 1\) is the normal window
- \(G\)
- global tokens: they see every token, and every token sees them
- \(r_{\text{rand}}\)
- number of random keys per query (BigBird)
For a decoder (causal model), we also remove every \(j \gt i\). Each block adds something different:
- Local keeps the strongest signal: neighbors. But information moves only \(r\) positions per layer.
- Dilated covers \(d_{\text{il}}\) times more distance for the same cost, but alone it is blind: with \(d_{\text{il}} = 2\), even positions never talk to odd ones.
- Global tokens act as hubs: any token reaches any other in 2 steps (token \(\to\) hub \(\to\) token). In a causal model this does not work for a hub at the start of the text: position 0 can only see itself, so it cannot collect information from later tokens.
- Random links act like shortcuts in a social network: a few of them make paths short everywhere.
Build the patterns yourself in Figure 1. The readout counts the cost (116.2) and the number of layers that information needs to travel between the two most distant tokens.
How to read Figure 1
Start with "Window" (radius 3, bidirectional): 324 pairs, 14.1% of the grid, but information needs 16 layers to cross the 48 tokens, because it moves 3 positions per layer. Add 2 global tokens (the Longformer preset): 498 pairs, and the worst path drops to 2 layers. Set the dilation to 2 with no global tokens: the readout says "never", because even and odd positions are never connected. Turn on "Causal" with global tokens: the path length does not improve, because a causal hub at position 0 cannot read later tokens. Click a cell to inspect its query row.
All numbers are from the pattern rules above, counted exactly (Figure 1 gives the same values).
Window radius 2, bidirectional: every query sees at most 5 keys, and the longest path is \(\lceil 47/2 \rceil = 24\) layers. Add 2 random keys per query: 320 pairs in total (13.9% of the grid), and the longest path falls to 4 layers. A few random shortcuts shorten every path.
Window radius 3 + 2 global tokens: 498 pairs (21.6%), longest path 2. Window radius 6 + stride 7, causal (the Sparse Transformer shape): 456 pairs (19.8%) and longest path 2, compared with 8 for the same window without the stride.
Figure 1 shows which cells are computed. Figure 2 does the computation itself, one query at a time, on 12 tokens with real 4-dimensional vectors. For each query it builds the set \(S_i\) from the blocks of (116.3), then computes the scores, the softmax and the output of (116.1) only over that set. The live panel puts the current numbers into the formulas.
- for each query \(i = 0, \dots, n-1\):
- \(S_i \leftarrow \varnothing\)
- add window keys: \(|i - j| \le r\,d_{\text{il}}\) and \((i-j) \bmod d_{\text{il}} = 0\)
- add global keys \(j \in G\); if \(i \in G\), add all keys
- add \(r_{\text{rand}}\) random keys not yet in \(S_i\) // fixed table
- \(z_{ij} \leftarrow \mathbf{q}_i^\top \mathbf{k}_j / \sqrt d\) for \(j \in S_i\)
- \(\alpha_{ij} \leftarrow e^{z_{ij}} / \sum_{j' \in S_i} e^{z_{ij'}}\)
- \(\mathbf{o}_i \leftarrow \sum_{j \in S_i} \alpha_{ij} \mathbf{v}_j\) // formula (116.1)
- cost \(\leftarrow \sum_i |S_i|\) // formula (116.2)
How to read Figure 2
Press Play, or Step to move one line of the algorithm at a time; the highlighted line is the one being run. In the current row the cells first show which block added each key, then the score \(z_{ij}\), then the weight \(\alpha_{ij}\). With the BigBird preset (radius 1, 1 global token, 1 random key, bidirectional), query 5 gets \(S_5 = \{0, 4, 5, 6, 10\}\): the window gives 4, 5, 6, the global token gives 0 and the random table gives 10. Its weights are 0.129, 0.322, 0.173, 0.101 and 0.275, and they sum to 1 over these 5 keys only. Row 0 is a global token, so it uses all 12 keys. The whole layer computes 65 scores instead of 144. Change the sliders at any step: the same row is recomputed with the new set.
Sparse Transformer: a window and a stride
The Sparse Transformer (Child et al., 2019, OpenAI) was built to generate images, audio and text as very long byte sequences: up to 12,288 bytes for text and 65,536 for audio. [Certain] Its idea is factorized attention: split the work across two heads (or two layers) so that any position can reach any earlier position in 2 steps, while each head looks at only about \(\sqrt n\) keys.
The strided pattern uses a stride \(l\). Head 1 sees the last \(l\) positions; head 2 sees every \(l\)-th position before \(i\):
Why 2 steps are enough: take any \(j \le i\). Let \(m\) be the first position at or after \(j\) with \(i - m\) a multiple of \(l\). Then \(0 \le m - j \lt l\), so \(m\) sees \(j\) through its window (head 1), and \(i\) sees \(m\) through the stride (head 2). One hop in each head: this is the "2 layers" you saw in Figure 1.
The strided pattern works well when the data has a natural period, like the rows of an image. For text, the authors found that the network "can fail to properly route information" with it. [Certain] So for text they use the fixed pattern: tokens attend inside their own block of length \(l\), and every token also attends to the last \(c\) positions of every earlier block, which act as summary cells:
(both with \(j \le i\)). The paper used \(c \in \{8, 16, 32\}\) with \(l \in \{128, 256\}\). [Certain]
Why the stride should be about \(\sqrt n\)
For the strided pattern, a query sees about \(l\) keys from the window and about \(i/l\) keys from the stride. Summed over all queries:
A larger \(l\) makes the window expensive; a smaller \(l\) makes the stride expensive. The balance point gives cost \(O(n\sqrt n)\). The paper simply says \(l\) is "chosen to be close to \(\sqrt n\)", which is the same order. [Certain] Explore the trade-off in Figure 3.
How to read Figure 3
The horizontal line is full causal attention, \(n(n+1)/2\). The curve is the strided pattern; the dot is your stride. At \(n = 16{,}384\) and \(l = 128\), the pattern computes 3,129,408 scores instead of 134,225,920: 42.9 times fewer. The best stride is 91 (close to \(\sqrt{8192} = 90.5\)), with 2,953,579 scores. Move \(n\) up: the saving grows like \(\sqrt n\), about 362 times at one million tokens.
The paper trained on enwik8 with context 12,288, stride 128 and \(c = 32\). [Certain] Full causal attention computes \(12288 \times 12289 / 2 = 75{,}503{,}616\) scores per head per layer. By formula (116.4), the strided pattern needs 2,148,416 (35.1 times fewer). The fixed pattern (116.5) with \(c = 32\) needs 19,470,336 by our count (3.9 times fewer): the summary cells cost more, but they route text better.
Measured in the paper on enwik8 at 12,288 context (Table 2): dense attention 1.00 bits per byte at 1.31 s per iteration, fixed 0.99 at 0.55 s, strided 1.13 at 0.35 s. [Certain] So the fixed pattern was both faster and not worse on text, while the strided one was fastest but lost quality.
Longformer: sliding windows, dilation and global tokens
Longformer (Beltagy, Peters and Cohan, 2020) targets long documents for BERT-style encoders: classification, question answering, and summarization with its encoder-decoder version (LED). Its pretrained models read up to 4,096 tokens, 8 times BERT's 512. [Certain]
The sliding window and its receptive field
Each token attends to \(\tfrac12 w\) tokens on each side, so the cost is \(O(n \times w)\): linear in \(n\). One layer sees only \(w\) tokens, but layers stack. After \(\ell\) layers, information from \(\ell \times w\) positions away can arrive, like the growing receptive field of a convolutional network. With dilation \(d_{\text{il}}\) in every layer, it grows to \(\ell \times d_{\text{il}} \times w\):
[Certain] (both from the paper). The paper's choices are practical. For character-level language modeling, lower layers use small windows and no dilation, to learn local details. Higher layers use larger windows, and only 2 heads get a small dilation, so the model can look far without losing local context. [Certain] Different heads with different dilation are the fix for the "blind" dilated pattern of Figure 1.
The pretrained Longformer uses window \(w = 512\), "the same amount of computation as RoBERTa". [Certain] Each query sees \(256 + 1 + 256 = 513\) keys. Scores per head per layer: \(4096 \times 513 = 2{,}101{,}248\), compared with \(4096^2 = 16{,}777{,}216\) for full attention: 7.98 times fewer. With 12 layers, the receptive field (116.7) is \(12 \times 512 = 6{,}144\) tokens: more than the whole 4,096-token input.
Global attention on task tokens
Windows are not flexible enough for tasks such as classification, where one token ([CLS]) must collect the whole document, or question answering, where every document token must compare itself with the question. So Longformer adds global attention on a few chosen positions: [CLS] for classification, all question tokens for QA. [Certain] It is symmetric: a global token attends to every token, and every token attends to it. Since the number of global tokens does not grow with \(n\), the total cost stays \(O(n)\).
Global attention gets its own projection matrices \(Q_g, K_g, V_g\), separate from the \(Q_s, K_s, V_s\) of the window, initialized as copies of them. The paper reports that these extra projections are "critical for best performance" on downstream tasks. [Certain]
BigBird: local + global + random
BigBird (Zaheer et al., 2020, Google) looks at attention as a graph: tokens are nodes, and every computed pair is an edge. Full attention is a complete graph. Making attention cheap means replacing it with a sparse graph that still behaves like the complete one. Graph theory gives two hints:
- Random graphs with only about \(n\) edges already have short paths between all nodes (logarithmic in \(n\)), so information mixes fast.
- Language has strong locality: much of what a token means comes from its neighbors. Random graphs lack this, so a window is added.
A small experiment in the paper at length 512 shows that random and window alone are not enough. Masked language model accuracy: BERT-base 64.2, random only 60.1, window only 58.3, random + window 62.7. [Certain] The last piece, found from the theory, is a set of global tokens. The final pattern for query \(i\) is the union:
There are two kinds of global tokens. BigBird-ITC (internal transformer construction) makes some existing tokens global. BigBird-ETC (extended transformer construction) adds extra tokens such as [CLS], which gives the model extra memory slots. [Certain]
Why the theory matters
BigBird proves two things about its pattern. First, a sparse encoder that contains a few global tokens (a "star graph") is a universal approximator of sequence-to-sequence functions, as full attention is. Second, a sparse encoder-decoder is Turing complete, under the same idealized assumptions used for full attention. [Certain] In plain words: with enough layers, nothing is lost in principle.
The paper is also honest about the cost: "enough layers" can be many. It gives a task (for each vector, find the one furthest from it) that one full-attention layer solves, but that any sparse pattern with about \(n\) edges needs roughly \(n\) layers for, under a standard complexity assumption. [Certain] Sparse patterns save compute per layer, but some tasks need many more layers.
The blocked implementation
GPUs are bad at gathering scattered single keys. So BigBird works with blocks of \(b\) tokens: a block of 64 queries attends to whole blocks of 64 keys. Each set in (116.8) is made of blocks. The encoder settings used in the paper are \(b = 64\), \(g = 2b\), \(w = 3b\), \(r_{\text{rand}} = 3b\), with sequence length 4,096. [Certain] So a query block computes scores with \((2 + 3 + 3) \times 64 = 512\) keys, one eighth of the 4,096, and the random blocks are drawn once and fixed. With the same hardware, BigBird handles sequences up to 8 times longer than before. [Certain]
- input: \(Q, K, V \in \R^{n \times d}\), block size \(b\), global blocks \(g_b\), window blocks \(w_b\) (odd), random blocks \(r_b\), a fixed random table
- split \(Q, K, V\) into \(n_b = n / b\) blocks
- for each query block \(u = 0, \dots, n_b - 1\):
- if \(u \lt g_b\): \(\mathcal{B} \leftarrow\) all key blocks // a global block attends to everything
- else: \(\mathcal{B} \leftarrow \{0, \dots, g_b - 1\} \cup \{u - \tfrac{w_b - 1}{2}, \dots, u + \tfrac{w_b - 1}{2}\} \cup \text{random}[u]\) // formula (116.8)
- gather \(K_{\mathcal{B}}, V_{\mathcal{B}}\) (about \((g_b + w_b + r_b)\,b\) rows)
- \(O_u \leftarrow \softmax(Q_u K_{\mathcal{B}}^\top / \sqrt d)\, V_{\mathcal{B}}\) // formula (116.1), dense inside the gathered set
- return \(O\) // cost \(O(n\,(g_b + w_b + r_b)\,b\,d)\): linear in \(n\)
StreamingLLM: a window plus attention sinks
So far the patterns were chosen before training. StreamingLLM (Xiao et al., 2023) asks a different question: can we take a normal LLM, trained with full attention on 4K tokens, and make it generate forever with a fixed-size KV cache, without any training?
The obvious answer is a sliding window: keep the KV of the last \(R\) tokens and drop older ones. It fails badly. On the first PG19 book (65K tokens), Llama-2-13B with a 1,024-token window reaches perplexity 5,158 once the first tokens are evicted. Keep the first 4 tokens plus the last 1,020, and perplexity is 5.40. [Certain] Even more surprising: replacing those 4 tokens with 4 line-break tokens gives 5.60. [Certain] So the first tokens matter because of their position, not their meaning.
Why: attention sinks
Softmax weights must sum to 1. When a head has nothing useful to look at, it still has to put its weight somewhere. Models learn to dump this extra weight on the first tokens, which every later token can see during training. Their values are small, so the dumped weight changes the output very little. The paper calls these tokens attention sinks. [Certain] Consider a query that gives the sink a score \(z_s\) and \(m\) other cached tokens a score of 0:
If the sink took 95% of the weight, removing it multiplies every other weight by about 20. The output of the head, which was a small mix of real values, suddenly becomes 20 times larger. Every later layer receives inputs it never saw in training, and the model breaks. Try it in Figure 4.
How to read Figure 4
With \(z_s = 6\) and \(m = 20\), the sink takes 95.3% of the weight and each other token gets 0.0024. Tick "Evict the sink": each other token now gets 0.05, 21.2 times more, and the size of the head output grows by the same factor. With \(z_s = 4\) the factor is only 3.7. A long cache (large \(m\)) also dilutes the sink, which is one reason models learn several sinks rather than one.
The StreamingLLM cache
The fix is simple: never evict the sinks. The cache keeps \(s\) sink tokens (4 is enough for the tested models) and a rolling window of the \(R\) most recent tokens:
One detail is critical. Positions are given by the place inside the cache, not in the original text. If the cache holds tokens [0, 1, 2, 3, 6, 7, 8] and the model decodes token 9, it uses positions 0 to 7, not [0, 1, 2, 3, 6, 7, 8, 9]. [Certain] With RoPE (session 14), this means keys are cached before the rotation, and rotated again at each step for their current cache slot. So the model never sees a distance larger than it saw in training.
- \(\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t \leftarrow\) projections of \(x_t\) // no rotation yet
- append \(\mathbf{k}_t, \mathbf{v}_t\) to the cache \(K, V\)
- if \(|K| \gt s + R\): delete entry \(s\) (oldest non-sink) // (116.10)
- \(p \leftarrow (0, 1, \dots, |K|-1)\) // positions inside the cache
- \(z_c \leftarrow \text{RoPE}(\mathbf{q}_t)^\top \text{RoPE}(\mathbf{k}_c) / \sqrt d\)
- \(\alpha \leftarrow \softmax(z)\), \(\ \mathbf{o}_t \leftarrow \sum_c \alpha_c \mathbf{v}_c\)
How to read Figure 5
Press Play or Step. Until the cache is full, it simply grows. After that, every new token pushes the cache one entry over the capacity \(s + R\), and step 3 deletes the oldest token of the window (red), never a sink. At the last token with \(s = 4\), \(R = 6\), the cache holds tokens 0 to 3 and 14 to 19, which get positions 0 to 9, and the sink takes 0.804 of the weight. Set \(s = 0\) to get a plain sliding window: token 0 is evicted when token 6 arrives. The panel then computes the weight token 0 would have received (0.884) and shows that every remaining weight is now 8.6 times larger than with the sink, the effect that makes a real model's perplexity explode.
- input: new token \(x_t\), cache of pre-RoPE keys \(K\) and values \(V\) (list), sinks \(s\), window \(R\)
- compute \(\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t\) from \(x_t\) // no rotation yet
- append \(\mathbf{k}_t\) to \(K\), \(\mathbf{v}_t\) to \(V\)
- if \(|K| \gt s + R\): delete entry number \(s\) (the oldest non-sink) from \(K\) and \(V\) // formula (116.10)
- \(p \leftarrow (0, 1, \dots, |K| - 1)\) // positions inside the cache
- \(\tilde K \leftarrow \text{RoPE}(K, p)\), \(\tilde{\mathbf{q}} \leftarrow \text{RoPE}(\mathbf{q}_t, |K| - 1)\)
- \(\mathbf{o}_t \leftarrow \softmax(\tilde K \tilde{\mathbf{q}} / \sqrt d)^\top V\)
- return \(\mathbf{o}_t\) // memory and time per step are constant: \(O(s + R)\)
The results reported in the paper: with StreamingLLM, Llama-2 (7B, 13B, 70B), MPT (7B, 30B), Falcon (7B, 40B) and Pythia (2.9B to 12B) model up to 4 million tokens with stable perplexity, and StreamingLLM runs up to 22.2 times faster per token than the only baseline that also works, a sliding window that recomputes the KV of the window from scratch at every step. [Certain] On 400K tokens of PG19, Llama-2-7B with a 4,096-token cache has perplexity 3,359.95 with no sink, 11.88 with 1, 9.59 with 4 and 9.54 with 8. [Certain]
The paper also pretrains small models with one extra learnable sink token at the start of every sample. Such a model needs only that one token as a sink when streaming. [Certain]
Static patterns shrink the KV cache during decoding
During generation, each new token needs the keys and values of every token it may attend to. With full attention, that is all previous tokens, so the KV cache grows without limit (session 80). With a pattern that only looks back \(W\) tokens, older entries are never read again and can be deleted. The cache size per sequence becomes:
- Read the symbols
- \(2\)
- one key and one value per token
- \(L, H_{kv}, d_h\)
- number of layers, key-value heads per layer and dimension per head
- \(b_{\text{el}}\)
- bytes per number: 2 for BF16
- \(\min(n, W)\)
- tokens kept: all \(n\) for full attention, at most \(W\) for a window (\(W = s + R\) for StreamingLLM)
Mistral 7B stores this as a rolling buffer: the key and value of position \(i\) go to slot
so new tokens overwrite the oldest ones and the cache stops growing at \(W\) entries. [Certain] Mistral 7B has \(L = 32\), \(H_{kv} = 8\), \(d_h = 128\) and \(W = 4096\). [Certain]
Mistral 7B, BF16: \(2 \times 32 \times 8 \times 128 \times 2 = 131{,}072\) bytes = 128 KiB per token. At 32K tokens with full attention: \(32768 \times 128\) KiB = 4 GiB per sequence. With the 4,096 window: 512 MiB, 8 times smaller, which is exactly the number in the Mistral paper. [Certain]
Information still travels further than the window: one layer moves it up to \(W\) tokens, so after 32 layers the "theoretical attention span" is \(32 \times 4096 = 131{,}072\), about 131K tokens. [Certain] As with Longformer (116.7), this is an upper bound, not a guarantee that the model uses it.
Gemma 2 9B alternates sliding-window layers (window 4,096) with full-attention layers: 42 layers, 8 KV heads, head size 256 (from its config.json). [Certain] Per token: \(2 \times 42 \times 8 \times 256 \times 2 = 344{,}064\) bytes. At its 8,192-token context, full attention in all layers would need 2.625 GiB; with 21 window layers it needs 1.969 GiB, 25% less. The saving grows with context because only the 21 global layers keep growing.
Not every static pattern helps decoding. A causal stride (116.4) needs every \(l\)-th old token, so it keeps about \(l + n/l\) entries: smaller, but still growing. Random links to any past token and Longformer-style global tokens inside the generated text need the whole history. Only patterns with a bounded look-back (window, window + fixed sinks) give a fixed-size cache. Compare in Figure 6.
How to read Figure 6
Both axes are logarithmic. The full-attention line grows forever. The window line becomes flat at \(n = W + \text{sinks}\). The hybrid line keeps growing at half the speed. Mistral 7B at 32K with \(W = 4096\): 4 GiB full, 0.5 GiB window. Llama-2-7B has 32 KV heads instead of 8, so it costs 512 KiB per token: at 4,194,304 tokens (the right end), full attention would need 2 TiB, while a window of 2,048 plus 4 sinks needs a constant 1.00 GiB.
PyTorch: masks, gathered attention and a sink cache
The code builds the four blocks as boolean masks, checks that masked dense attention equals attention computed only on the gathered keys (what a real sparse kernel does), and runs the StreamingLLM cache of Algorithm 2 with RoPE applied at cache positions. It runs on CPU in about a second.
import torch, math
torch.manual_seed(0)
# ---- 1) static patterns as boolean masks (True = this pair is computed), formula (116.3) ----
def window(n, radius, causal=False):
i = torch.arange(n)[:, None]; j = torch.arange(n)[None, :]
m = (i - j).abs() <= radius
return m & (j <= i) if causal else m
def dilated(n, radius, d, causal=False):
i = torch.arange(n)[:, None]; j = torch.arange(n)[None, :]
dist = i - j
m = (dist.abs() <= radius * d) & (dist % d == 0)
return m & (j <= i) if causal else m
def global_tokens(n, g): # first g tokens see all and are seen by all
m = torch.zeros(n, n, dtype=torch.bool)
m[:g, :] = True; m[:, :g] = True
return m
def random_blocks(n, b, r, gen): # BigBird-style: r random key blocks per query block
nb = n // b; m = torch.zeros(n, n, dtype=torch.bool)
for qb in range(nb):
for kb in torch.randperm(nb, generator=gen)[:r].tolist():
m[qb*b:(qb+1)*b, kb*b:(kb+1)*b] = True
return m
def masked_attention(q, k, v, mask): # formula (116.1): softmax only over allowed keys
s = (q @ k.T) / math.sqrt(q.shape[-1])
s = s.masked_fill(~mask, float("-inf"))
return torch.softmax(s, dim=-1) @ v
n, d = 64, 16
q, k, v = torch.randn(n, d), torch.randn(n, d), torch.randn(n, d)
gen = torch.Generator().manual_seed(116)
bigbird = window(n, 4) | global_tokens(n, 2) | random_blocks(n, 8, 1, gen) # formula (116.8)
print("density of the BigBird-style mask:", round(bigbird.float().mean().item(), 3)) # 0.312
out = masked_attention(q, k, v, bigbird)
# ---- 2) the same result, computing only the allowed scores (gather per query) ----
out2 = torch.empty_like(out)
for i in range(n):
idx = bigbird[i].nonzero().squeeze(1) # the set S_i
w = torch.softmax(q[i] @ k[idx].T / math.sqrt(d), dim=-1)
out2[i] = w @ v[idx]
print("max difference, dense-masked vs gathered:", (out - out2).abs().max().item()) # about 4e-7
# ---- 3) StreamingLLM: s sink tokens + a rolling window of R recent tokens (Algorithm 2) ----
def rope(x, pos): # x: (T, d), pos: (T,)
half = x.shape[-1] // 2
freq = 10000 ** (-torch.arange(half) / half)
ang = pos[:, None].float() * freq[None, :]
x1, x2 = x[:, :half], x[:, half:]
return torch.cat([x1 * ang.cos() - x2 * ang.sin(), x1 * ang.sin() + x2 * ang.cos()], -1)
class SinkCache:
def __init__(self, s, R):
self.s, self.R, self.k, self.v = s, R, [], [] # keys stored BEFORE RoPE
def append(self, k, v):
self.k.append(k); self.v.append(v)
if len(self.k) > self.s + self.R: # evict the oldest non-sink token
del self.k[self.s]; del self.v[self.s]
def attend(self, q):
K, V = torch.stack(self.k), torch.stack(self.v)
pos = torch.arange(len(K)) # positions INSIDE the cache
Kr = rope(K, pos); qr = rope(q[None], pos[-1:])[0]
w = torch.softmax(Kr @ qr / math.sqrt(q.shape[-1]), -1)
return w @ V
T, s, R = 40, 4, 8
Q, K, V = torch.randn(T, d), torch.randn(T, d), torch.randn(T, d)
cache = SinkCache(s, R)
for t in range(T):
cache.append(K[t], V[t])
o = cache.attend(Q[t])
keep = list(range(s)) + list(range(T - R, T)) # what the last step should see
pos = torch.arange(len(keep))
w = torch.softmax(rope(K[keep], pos) @ rope(Q[T-1][None], pos[-1:])[0] / math.sqrt(d), -1)
print("cache size:", len(cache.k), " match with direct formula:", (o - w @ V[keep]).abs().max().item()) # 12, 0.0
Note what the dense-masked version costs: it still builds the full \(64 \times 64\) score table and throws 69% of it away. Speed only comes from kernels that never compute the masked blocks, such as block-sparse kernels or FlashAttention with a sliding-window option (session 124).
Where this is used
| Setting | Pattern | Why |
|---|---|---|
| Decoder LLMs: Mistral 7B | Sliding window \(W = 4096\) in every layer, rolling buffer cache [Certain] | 8 times less KV memory at 32K; 2 times faster attention at 16K than a vanilla baseline (paper) [Certain] |
| Decoder LLMs: Gemma 2 | Window layers (4,096) alternating with full layers [Certain] | Keeps full-range recall in half the layers while the other half stay cheap |
| Streaming chat and assistants | StreamingLLM: 4 sinks + recent window, positions inside the cache | Endless generation with constant memory, no retraining |
| Long-document encoders: classification, QA, summarization | Longformer / LED (window + global on [CLS] or question), BigBird (window + global + random) [Certain] | 4,096-token inputs at a cost close to a 512-token model; summarization of papers and reports |
| Genomics | BigBird on long DNA sequences [Certain] | The paper reports gains on promoter-region prediction with longer context |
| Video classification and action recognition | Factorized space-time attention: a token attends along time, then within its frame (TimeSformer "divided" attention) [Certain] | The same idea as the Sparse Transformer: two cheap sparse steps replace one dense step over all frames × patches |
| Long-video key-moment detection, Video-RAG indexing | Local window over frame tokens + a few global query tokens (Longformer shape) [Likely] | Hours of frames are too many for full attention; local motion needs neighbors, the query needs everything |
| Streaming video understanding | Sink tokens + a rolling window of recent frame tokens [Likely] | A live camera stream never ends; the cache must stay bounded |
Common mistakes
- Masking instead of skipping. A dense \(n \times n\) mask with \(-\infty\) is correct but not faster and not smaller. Sparse attention needs a kernel that skips whole blocks.
- Thinking the window limits what the model can use. Stacked layers spread information over \(\ell \times W\) tokens (116.7). The reverse mistake is also common: the receptive field is only an upper bound; signals fade over many hops.
- Evicting the first tokens. A plain sliding window cache on a model trained with full attention breaks once the first tokens leave (perplexity in the thousands). Keep sinks.
- Using original positions after eviction. In StreamingLLM, RoPE positions must be the positions inside the cache, so keys must be cached before rotation. Using text positions gives distances the model never saw.
- Expecting StreamingLLM to remember evicted text. It gives stable generation, not long-term memory.
- Dilation in every head. A pure dilated pattern never connects some positions (even versus odd). Mix dilated and normal heads, as Longformer does.
- Global tokens in a causal model at the wrong place. A "global" token at position 0 can only read itself in a decoder. It works as a sink, not as a summary hub.
- Changing the pattern after training without checking. A model trained with full attention can lose quality when you switch it to a window at inference, beyond what perplexity on short text shows. Test long-context tasks.
Interview questions
What is the difference between static and dynamic sparse attention?basic
Sliding-window attention with \(W = 4096\): can a token use information from 20,000 tokens back?core
Why does the Sparse Transformer choose a stride near \(\sqrt n\)?core
Why did BigBird need global tokens, when window + random already connects the graph?advanced
What are attention sinks, and why do they appear?core
Why does a plain sliding-window KV cache fail on Llama 2, and how does StreamingLLM fix it?core
How do you implement RoPE correctly with a StreamingLLM cache?advanced
Compute the KV cache of Mistral 7B at 32K tokens, with and without its window.core
Which static patterns reduce the KV cache during decoding, and which do not?advanced
Longformer uses separate projections for global attention. Why?basic
Your masked sparse attention is no faster than full attention. Why, and what do you do?core
Exercises
- For a bidirectional window of radius 2 on 48 tokens (no other blocks), what is the largest number of layers needed for information to go from token 0 to token 47?
- Show that \(f(l) = l + n/(2l)\) is smallest at \(l = \sqrt{n/2}\), and give the value of \(f\) there for \(n = 65{,}536\).
- A Longformer has 12 layers, window \(w = 512\) and dilation 2 in every layer. What is the receptive field by formula (116.7)?
- BigBird-ITC with \(b = 64\), \(g = 2b\), \(w = 3b\), \(r = 3b\) on \(n = 4096\). How many scores does one non-global query block compute, and what fraction of full attention is that?
- In Figure 4, a sink with score \(z_s = 4\) and \(m = 20\) other tokens with score 0. What weight does the sink get, and by what factor do the others grow if it is evicted?
- Llama-2-7B (32 layers, 32 KV heads, head size 128, BF16) with StreamingLLM, 4 sinks and a 1,020-token window. How much KV memory per sequence? How much would full attention need at 4 million tokens?
Answerscheck
Key takeaways
- Any sparse attention is a set of allowed keys \(S_i\) per query (116.1); its cost is \(\sum_i |S_i|\) (116.2), and its reach is the number of hops between distant tokens.
- Four blocks (116.3): local windows, dilated windows, global tokens and random links. Windows give locality, global tokens give 2-hop paths, random links shorten all paths.
- Sparse Transformer: window + stride (116.4) or fixed blocks with summary cells (116.5); a stride near \(\sqrt n\) gives \(O(n\sqrt n)\) (116.6).
- Longformer: sliding and dilated windows with receptive field \(\ell \times d_{\text{il}} \times w\) (116.7), plus symmetric global attention on task tokens with separate projections.
- BigBird: window + global + random (116.8), in blocks of 64; proven as expressive as full attention, but some tasks need many more layers.
- StreamingLLM: models dump extra attention on the first tokens (116.9); keep 4 sinks + a rolling window (116.10) with positions inside the cache, and generation stays stable for millions of tokens.
- Bounded look-back patterns cap the KV cache (116.11, 116.12): Mistral 7B at 32K uses 512 MiB instead of 4 GiB.
Key formulas
References for this session
- Child et al. (2019). Generating Long Sequences with Sparse Transformers
- Beltagy et al. (2020). Longformer: The Long-Document Transformer
- Zaheer et al. (2020). Big Bird: Transformers for Longer Sequences
- Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
- Child et al. (2019). Generating Long Sequences with Sparse Transformers
- Beltagy et al. (2020). Longformer: The Long-Document Transformer
- Zaheer et al. (2020). Big Bird: Transformers for Longer Sequences
- Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Jiang et al. (2023). Mistral 7B
- Gemma Team (2024). Gemma 2: Improving Open Language Models at a Practical Size
- Zhang et al. (2023). H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models
- Su et al. (2021). RoFormer: Enhanced Transformer with Rotary Position Embedding
- Bertasius et al. (2021). Is Space-Time Attention All You Need for Video Understanding?