LLM & VLM courseBlog
117Track 5: LLM inference and serving · session 40 of 65

Sparse attention 2 (dynamic): Reformer, Routing Transformer, SpAtten, H2O

Static sparse attention fixes the pattern before it sees the input. Dynamic sparse attention looks at the content: it groups similar queries and keys by hashing (Reformer) or by learned clusters (Routing Transformer), prunes tokens and heads that receive little attention (SpAtten), or keeps only recent tokens and heavy hitters in the KV cache (H2O). This session builds each method with its math, and shows the main risk: once a token is evicted, it is gone.

Time: 2.5 to 3.5 hours (reading 2 hours, exercises 1 hour)Level: IntermediateBefore this: Sessions 80 (the KV cache), 116 (static sparse attention) and 26 (attention variants)

What you will learn

  • Static versus dynamic sparse attention, and why trained attention is sparse enough to skip most pairs
  • How Reformer’s angular LSH, shared queries and keys, sort-and-chunk and multiple hash rounds work, and what they cost
  • Why k-means on unit vectors finds large dot products, and why the best number of clusters is the square root of n
  • How SpAtten prunes tokens and heads with cumulative attention, and why flat softmaxes need more bits
  • How H2O keeps recent tokens and heavy hitters in a fixed KV budget, and what the paper reports
  • Why eviction can fail for good on needle-type questions, how to bound the error, and how later methods reduce the risk

Why this matters

Attention compares every token with every other token. Most of these comparisons give a probability close to zero. If we knew in advance which pairs matter, we could skip the rest. Static sparse attention (the last session) fixes the pattern before it sees the input. Dynamic sparse attention looks at the content and decides, for each input, which pairs to compute, which tokens to drop, and which keys and values to keep in the cache.

Session 116 used fixed patterns: a sliding window, strided positions, a few global tokens, and in StreamingLLM the first tokens plus a recent window. These patterns are cheap and easy to put on a GPU, but they are blind. If the important word is 3,000 tokens back and is not a global token, a fixed window cannot see it. The efficient-inference survey states the difference in one line each: “Static sparse attention removes activation values independently of specific inputs”, while “Dynamic sparse attention adaptively eliminates activation values based on varying inputs”. [Certain, survey Section 5.2.2]

This session studies four dynamic methods. They ask the same question, “which pairs matter?”, and answer it in four different ways:

  • Reformer (Kitaev et al., ICLR 2020): put similar queries and keys into the same bucket with a random hash, and attend only inside buckets.
  • Routing Transformer (Roy et al., TACL 2021): put them into the same cluster with k-means, using centroids that are learned during training.
  • SpAtten (Wang et al., HPCA 2021): measure how much attention each token and each head receives, and prune the weak ones on the fly, layer after layer.
  • H2O (Zhang et al., NeurIPS 2023): during generation, keep only the recent tokens and the heavy hitters (tokens with large accumulated attention) in the KV cache, and evict the rest.

The first two change the model and are mostly about training and prefill on long sequences. The last two work at inference time on a trained model. SpAtten was designed with a hardware accelerator; H2O is a cache policy for GPU serving. H2O and its successors (Scissorhands, SnapKV, and the H2O-style options in serving libraries) are where this idea is alive today. [Likely]

Interview questions on this topic: “How does LSH attention work and why share Q and K?”, “Why is the best number of clusters \(\sqrt{n}\)?”, “What is a heavy hitter?”, “Why can KV eviction fail on needle-in-a-haystack tests?”. By the end of the session you can answer each with a formula and a number.

From fixed patterns to content-based patterns

One formula for all sparse attention

Write the output of one query \(i\) as a softmax over a set \(P_i\) of key positions:

\[ \mathbf{o}_i = \sum_{j \in P_i} \frac{\exp(\mathbf{q}_i \cdot \mathbf{k}_j / \sqrt{d})}{\sum_{j' \in P_i} \exp(\mathbf{q}_i \cdot \mathbf{k}_{j'} / \sqrt{d})}\, \mathbf{v}_j , \qquad P_i \subseteq \{1, \dots, i\} \tag{117.1} \]
Read the symbols
\(\mathbf{q}_i, \mathbf{k}_j, \mathbf{v}_j\)
query of token \(i\), key and value of token \(j\), each of size \(d\) (one head)
\(P_i\)
the set of keys that query \(i\) is allowed to see. Full causal attention: \(P_i = \{1, \dots, i\}\).
static
\(P_i\) depends only on positions (window, stride, global tokens)
dynamic
\(P_i\) depends on the vectors themselves: on hashes, clusters or attention scores

The cost of attention is the total size \(\sum_i |P_i|\) times \(d\). Full attention has \(\sum_i |P_i| \approx n^2/2\). Every method in this session tries to make \(|P_i|\) small while keeping the keys that carry most of the softmax mass.

Why it can work: attention is sparse

Softmax is dominated by its largest inputs. H2O measured this on OPT models: if every entry smaller than 1% of the largest entry in its row is counted as zero, the attention matrices are more than 95% sparse in almost all layers, even though the model was trained with dense attention. [Certain, H2O paper Section 3.1] So most of the \(n^2\) products are wasted. The hard part is to find the few important keys without computing all the products first.

There are two families of answers:

  • Find the neighbors cheaply (Reformer, Routing Transformer). Large \(\mathbf{q} \cdot \mathbf{k}\) means \(\mathbf{k}\) is close to \(\mathbf{q}\) in angle. Use a fast approximate nearest-neighbor method to group close vectors. Nothing is deleted; each query just skips far keys.
  • Use the scores you already computed (SpAtten, H2O). Attention probabilities of earlier layers or earlier decoding steps tell you which tokens are important. Drop the others for the rest of the computation. Here tokens are really removed.

This difference decides the main risk. A missed neighbor in Reformer costs a little accuracy for one query in one layer. An evicted token in H2O is gone for every later query. We come back to this in the last part.

Reformer: buckets by hashing

Locality-sensitive hashing

A locality-sensitive hash (LSH) is a hash function that gives the same value to close vectors with high probability, and different values to far vectors with high probability. Reformer uses the angular LSH of Andoni et al. (2015). Fix a random matrix \(R\) of size \(d \times b/2\). Then

\[ h(\mathbf{x}) = \argmax \big( [\, \mathbf{x} R \,;\, -\mathbf{x} R \,] \big) \in \{0, 1, \dots, b - 1\} \tag{117.2} \]
Read the symbols
\(R\)
a random matrix with \(b/2\) columns; each column is a random direction
\([\mathbf{u} ; \mathbf{v}]\)
concatenation: the \(b/2\) projections and their negatives, \(b\) numbers in total
\(b\)
the number of buckets (Reformer writes \(n_{\text{buckets}}\))
\(h(\mathbf{x})\)
the bucket: the signed random direction that \(\mathbf{x}\) points to most

Two vectors with a small angle between them usually point most to the same signed direction, so they share a bucket. Two vectors at 90° rarely do.

Worked example: hashing three vectors into 4 buckets

Take \(d = 2\), \(b = 4\), and \(R = \begin{bmatrix} 0.6 & -0.8 \\ 0.8 & 0.6 \end{bmatrix}\) (a rotation).

\(\mathbf{x} = (1, 0.5)\): \(\mathbf{x}R = (1.0, -0.5)\), so \([\mathbf{x}R; -\mathbf{x}R] = (1.0, -0.5, -1.0, 0.5)\) and \(h = 0\).

\(\mathbf{y} = (0.9, 0.7)\): \(\mathbf{y}R = (1.1, -0.3)\), the vector is \((1.1, -0.3, -1.1, 0.3)\), \(h = 0\). Same bucket as \(\mathbf{x}\): the angle between them is about 11°.

\(\mathbf{z} = (-1, 0.2)\): \(\mathbf{z}R = (-0.44, 0.92)\), the vector is \((-0.44, 0.92, 0.44, -0.92)\), \(h = 1\). Different bucket: \(\mathbf{z}\) points the other way. [Certain, computed in Python]

How likely is a collision? We simulated (117.2) with Gaussian \(R\) in \(d = 64\). With \(b = 8\) buckets, two vectors share a bucket with probability about 0.73 at 20°, 0.46 at 45°, 0.32 at 60° and 0.13 at 90°. With \(b = 32\) the numbers drop to about 0.63, 0.31, 0.17 and 0.03. [Certain, Monte Carlo with 20,000 random matrices] More buckets make the hash sharper: far pairs almost never collide, but close pairs are also missed more often.

Shared queries and keys

Bucketing works only if a query and its important keys land in the same bucket. If queries and keys come from different projections, a bucket can have many queries and no keys. Reformer makes them the same vectors. One linear layer gives the queries; the keys are the normalized queries:

\[ \mathbf{k}_j = \frac{\mathbf{q}_j}{\lVert \mathbf{q}_j \rVert}, \qquad P_i = \{\, j \le i : h(\mathbf{q}_i) = h(\mathbf{k}_j) \,\} \tag{117.3} \]
Read the symbols
shared-QK
one projection for \(Q\) and \(K\); the value projection stays separate
\(P_i\)
the keys in query \(i\)’s bucket that are not in the future

Sharing has a side effect: \(\mathbf{q}_i \cdot \mathbf{k}_i = \lVert \mathbf{q}_i \rVert\) is almost always the largest score, so a token would mostly attend to itself. Reformer masks the diagonal, except when a token has no other target (the first token). The paper reports that shared-QK attention does not train worse than normal attention on enwik8 and imagenet64. [Certain, Reformer Section 5]

Figure 1 runs formulas (117.2) and (117.3) in the browser on 10 tokens in two dimensions. First it hashes every token, one at a time: it projects the unit key on the signed directions of \(R\) and takes the largest. Then it sorts the tokens by bucket. Then each query computes scores and a softmax only over the earlier tokens in its own bucket.

  1. draw \(R\): \(b/2\) unit directions, turned by a random angle \(\theta\)
  2. for each token \(j\): \(\mathbf{k}_j \leftarrow \mathbf{q}_j / \lVert \mathbf{q}_j \rVert\) // shared-QK (117.3)
  3. \(h_j \leftarrow \argmax([\mathbf{k}_j R \,;\, -\mathbf{k}_j R])\) // (117.2)
  4. sort the tokens by \((h_j, j)\)
  5. for each query \(i\): \(P_i \leftarrow \{ j \lt i : h_j = h_i \}\), or \(\{i\}\) if empty
  6. \(s_{ij} \leftarrow \mathbf{q}_i \cdot \mathbf{k}_j / \sqrt{d}\) for \(j \in P_i\)
  7. \(p_{ij} \leftarrow \softmax\) of \(s_{ij}\) over \(P_i\) only
Figure 1. Angular LSH (117.2) with shared queries and keys (117.3), computed step by step on 10 tokens with \(d = 2\). Left: each arrow is a query \(\mathbf{q}_j\) (its length is the norm); the colored sectors are the buckets. In 2D we let \(R\) hold \(b/2\) evenly spaced directions turned by \(\theta\), so each bucket is a sector of \(360°/b\); Reformer draws \(R\) with random Gaussian entries (Figure 3 does that). Middle: the tokens of each bucket in sorted order. Right: the attention weights \(p_{ij}\); a filled cell is a computed score, a small dot is a past key the query never sees. “Kept mass” is the part of the full softmax (over all earlier tokens) that falls on \(P_i\).
How to read Figure 1

Press Play or Step. The highlighted lines of the algorithm box run in this step, and the box next to it shows the same formulas with the real numbers. With 4 buckets and \(\theta = 20°\), token 0 is \(\mathbf{q}_0 = (2.90, 0.78)\), its unit key is \((0.97, 0.26)\), and \([\mathbf{k}_0 R; -\mathbf{k}_0 R] = (1.00, -0.09, -1.00, 0.09)\), so \(h_0 = 0\). The buckets get 4, 3, 2 and 1 tokens. In the attention phase, query 9 shares bucket 0 with tokens 0, 3 and 5: scores \(2.05, 2.21, 2.21\), weights \(0.30, 0.35, 0.35\), and these three keys hold 70.4% of query 9’s full attention. Query 7 is alone in bucket 3, so it attends only to itself and keeps none of its real attention. In total 14 scores are computed instead of the 55 of causal attention, and the average kept mass over queries 1 to 9 is 45.5%. Try 8 buckets: 11 scores, 32.8% kept. Turn \(\theta\) to 70° with 4 buckets: one bucket grows to 6 tokens, 20 scores, 41.0% kept. Small buckets are cheap but blind; this is why Reformer uses several rounds (Figure 3).

Sort, chunk, attend

Buckets have different sizes, which is bad for a GPU or TPU: you want equal blocks. Reformer sorts the tokens by bucket (and by position inside a bucket), cuts the sorted list into chunks of \(m\) tokens, and lets each chunk attend to itself and to the chunk before it:

\[ \tilde P_i = \Big\{\, j : \Big\lfloor \frac{s_i}{m} \Big\rfloor - 1 \le \Big\lfloor \frac{s_j}{m} \Big\rfloor \le \Big\lfloor \frac{s_i}{m} \Big\rfloor \,\Big\}, \qquad m = \frac{2\,l}{n_{\text{buckets}}} \tag{117.4} \]
Read the symbols
\(s_i\)
the position of token \(i\) after sorting
\(\tilde P_i\)
the window that is computed: the own chunk and the previous chunk. Pairs inside the window but in a different bucket, or in the future, are masked.
\(l\)
sequence length; the average bucket has \(l / n_{\text{buckets}}\) tokens, so a chunk is twice the average bucket

If no bucket is larger than \(m\), then every pair of \(P_i\) is inside \(\tilde P_i\). The paper assumes that a bucket rarely grows to twice the average size. [Certain, Reformer Section 2] Figure 2 walks through the four steps on 16 tokens.

Figure 2. LSH attention on 16 tokens with 4 buckets and chunks of \(m = 4\). The grid is the attention matrix: rows are queries, columns are keys. In steps 1 and 2 a colored cell means “same bucket and not in the future”. Step 2 reorders rows and columns by bucket. Step 3 draws the chunk window (light cells). Step 4 shows the pairs that are really used.
How to read Figure 2

Step 1 shows the tokens in their original order; the same-bucket pairs (25 of the 120 causal pairs, self not counted) are spread over the matrix. Step 2 sorts by bucket: the pairs become square blocks on the diagonal, of sizes 4, 4, 5 and 3. Step 3 cuts the sorted list into 4 chunks; each chunk computes its own block and the block to its left, 112 scores instead of 256. Step 4 keeps the same-bucket, causal, non-self pairs inside the window: 29 pairs used (25 plus 4 tokens that are alone in their bucket so far and attend to themselves), and no same-bucket pair is lost, because bucket 2 (5 tokens) spans two chunks but they are neighbors.

Several rounds of hashing

A hash can put two close vectors on two sides of a border. To lower this risk, Reformer hashes \(n_r\) times with independent matrices \(R^{(1)}, \dots, R^{(n_r)}\) and lets the query see the union of its buckets:

\[ P_i = \bigcup_{r=1}^{n_r} P_i^{(r)}, \qquad \Pr[\text{a neighbor is missed in all rounds}] = (1 - p)^{n_r} \tag{117.5} \]
Read the symbols
\(P_i^{(r)}\)
the bucket of query \(i\) in round \(r\)
\(p\)
the collision probability of one round for this pair (it depends on the angle and on \(b\))
\(n_r\)
number of hash rounds (the paper writes \(n_{\text{rounds}}\))

With \(b = 32\) and a pair at 45° (\(p \approx 0.31\)), one round finds the pair 31% of the time; four rounds find it about 77% of the time, eight rounds about 95%. [Certain, from the simulated \(p\)] Each round is a separate attention over its own sorted chunks. The rounds are combined with their softmax normalizers, and a pair that appears in several rounds is counted once (the paper subtracts \(\log N_{i,j}\), where \(N_{i,j}\) is the number of rounds that contain the pair):

\[ \mathbf{o}_i = \sum_{r=1}^{n_r} \exp\big( z(i, P_i^{(r)}) - z(i, P_i) \big)\, \mathbf{o}_i^{(r)} \tag{117.6} \]
Read the symbols
\(z(i, P)\)
the log of the softmax denominator of query \(i\) over the set \(P\) (log-sum-exp of its scores)
\(\mathbf{o}_i^{(r)}\)
the attention output of round \(r\) alone, normalized over its own set

This is the same rescaling trick that FlashAttention uses to merge blocks (session 124): outputs over different key sets can be merged exactly if you keep the log-sum-exp of each.

Figure 3 shows hashing in two dimensions. Each ring is one round; the bright arc is the query’s bucket. Change the number of buckets and rounds and watch how many keys the query sees and how much attention mass it keeps.

Figure 3. Angular LSH (117.2) on 40 unit vectors in 2D, drawn from 5 topics. The score of a key is \(5 \cos(\text{angle to the query})\); the softmax over all 39 other keys is the “full” attention. Candidates are the keys that share the query’s bucket in at least one round (117.5). Click any point to make it the query. Chunking is not shown.
How to read Figure 3

Start with 16 buckets and one round: the query (token 3) sits near a bucket border. It sees 17 keys but finds only 2 of its 5 best keys and keeps 49.9% of the attention mass. Move to 4 rounds: the union of buckets now contains all 5 best keys and 100.0% of the mass (to one decimal), at the price of looking at 28 of 39 keys. With 8 buckets and one round it keeps 81.9%. In 2D the buckets are wide, so many keys are candidates; in 64 dimensions with hundreds of buckets a bucket is a small fraction of the sequence. Click other points: a query in the middle of a bucket needs fewer rounds than a query on a border.

What it costs and what it bought

Per round, each query computes scores against one window of \(2m\) keys. With (117.4):

\[ \text{scores per layer and head} \approx n_r \cdot l \cdot 2m = n_r \cdot \frac{4\, l^2}{n_{\text{buckets}}} \tag{117.7} \]

The paper writes the cost as \(\max(b\, n_h\, l\, d_k,\ b\, n_h\, n_r\, l\, (4l/n_c)^2)\) per layer, with \(n_c\) the number of chunks, plus the sort, which is \(O(l \log l)\). If the chunk size \(m\) stays fixed as \(l\) grows (more buckets for longer inputs), the attention part grows like \(l\), and the sort gives the \(O(l \log l)\) of the title. [Certain, Reformer Table 1]

Worked example: 64K tokens

Reformer’s enwik8 task uses \(l = 2^{16} = 65{,}536\) tokens. The full attention matrix of one head in 32-bit floats is \(65{,}536^2 \times 4 = 17.2\) GB (16 GiB; the paper says 16GB). With the typical chunk of \(m = 128\), formula (117.4) gives \(n_{\text{buckets}} = 2 \times 65{,}536 / 128 = 1{,}024\) buckets of 64 tokens on average.

One round computes \(65{,}536 \times 256 = 16.8\) million scores, \(256\times\) fewer than the 4.29 billion of the full matrix. Eight rounds compute \(134\) million, still \(32\times\) fewer. [Certain, computed in Python]

The results. On a synthetic copy task (the second half of each sequence repeats the first half, length 1024), a model trained with 4 hash rounds reaches 100% accuracy when evaluated with 8 rounds, and 91.9% with one round. A model trained with full attention and evaluated with 1-round LSH gets only 52.5%. [Certain, Reformer Table 2] So the model must be trained with hashing; you cannot simply switch a trained dense model to LSH. On imagenet64, 8 rounds “almost” match full attention, and LSH speed stays flat as the length grows while full attention slows down. A 12-layer Reformer reached 1.05 bits/dim on enwik8 after more tuning. [Certain, Reformer Section 5]

Algorithm 1: LSH attention, one head, one layer (Reformer)
  1. input: shared queries/keys \(Q \in \R^{l \times d}\), values \(V\), number of buckets \(b\), rounds \(n_r\), chunk size \(m = 2l/b\)
  2. \(K \leftarrow Q / \lVert Q \rVert\) row by row // shared-QK, formula (117.3)
  3. for \(r = 1, \dots, n_r\):
  4.   draw a random \(R^{(r)} \in \R^{d \times b/2}\); \(h_j \leftarrow \argmax([\mathbf{k}_j R^{(r)}; -\mathbf{k}_j R^{(r)}])\) for all \(j\) // (117.2)
  5.   sort positions by \((h_j, j)\); cut the sorted list into chunks of \(m\)
  6.   for each chunk \(c\): scores \(\leftarrow Q_c\, [K_{c-1}; K_c]^{\top} / \sqrt{d}\) // \(m \times 2m\) block
  7.     mask: other bucket, future position, self (unless no other target), and \(\log N_{i,j}\) for repeats
  8.     \(\mathbf{o}^{(r)}, z^{(r)} \leftarrow\) softmax-weighted sum of \([V_{c-1}; V_c]\) and the log-sum-exp
  9.   un-sort \(\mathbf{o}^{(r)}\) and \(z^{(r)}\) back to the original order
  10. return \(\mathbf{o}_i = \sum_r \exp(z_i^{(r)} - \operatorname{logsumexp}_r z_i^{(r)})\, \mathbf{o}_i^{(r)}\) // formula (117.6)

Routing Transformer: clusters by k-means

From random hashes to learned centroids

Random hyperplanes do not know where the data is. If most queries live in a few directions, many buckets are empty and a few are crowded. The Routing Transformer learns the partition instead: \(k\) centroid vectors \(\boldsymbol\mu_1, \dots, \boldsymbol\mu_k\) (model parameters, shared by all sequences) and an assignment of each query and key to its nearest centroid. Query \(i\) attends only to earlier keys in its own cluster. [Certain, Routing Transformer Section 4.1]

Why the nearest centroid? Put queries and keys on the unit sphere (the paper uses LayerNorm without scale and bias, which puts them on a sphere of radius \(\sqrt{d}\)). For unit vectors,

\[ \lVert \mathbf{q} - \mathbf{k} \rVert^2 = \lVert \mathbf{q} \rVert^2 + \lVert \mathbf{k} \rVert^2 - 2\, \mathbf{q} \cdot \mathbf{k} = 2 - 2\, \mathbf{q} \cdot \mathbf{k} \tag{117.8} \]
Read the symbols
left side
squared distance, which k-means minimizes
\(\mathbf{q} \cdot \mathbf{k}\)
the attention score (before scaling)

So a small distance is the same as a large score: nearest-neighbor search and maximum inner-product search become one problem. If \(\mathbf{q}\) and \(\mathbf{k}\) are both within \(\varepsilon\) of the same centroid, the triangle inequality gives \(\lVert \mathbf{q} - \mathbf{k} \rVert \lt 2\varepsilon\) and so \(\mathbf{q} \cdot \mathbf{k} \gt 1 - 2\varepsilon^2\). Pairs in one cluster have high scores. [Certain, Routing Transformer eq. 10 to 13] k-means on unit vectors is called spherical k-means.

The cost and the best number of clusters

Two parts cost work. Assigning \(n\) vectors to \(k\) centroids costs \(nkd\). Attention inside balanced clusters of size \(n/k\) costs \(n \cdot (n/k) \cdot d\). The sum, and its minimum over \(k\):

\[ C(k) = n k d + \frac{n^2 d}{k}, \qquad \frac{dC}{dk} = 0 \ \Rightarrow\ k^{*} = \sqrt{n}, \qquad C(k^{*}) = 2\, n^{1.5} d \tag{117.9} \]
Read the symbols
\(n k d\)
routing: compare every vector with every centroid
\(n^2 d / k\)
attention: each query against the \(n/k\) keys of its cluster
\(k^{*}\)
the best number of clusters; then each cluster also has \(\sqrt{n}\) tokens

Relative to full attention (\(n^2 d\)) the cost is \(k/n + 1/k\). At the optimum this is \(2/\sqrt{n}\). The same \(\sqrt{n}\) appeared for the strided patterns of the Sparse Transformer in session 116: one term grows with the block count, the other shrinks.

Worked example: PG-19 length

The PG-19 model trains on \(n = 8{,}192\) tokens. \(k^{*} = \sqrt{8192} = 90.5\). With \(k = 91\) clusters of about 90 tokens, the relative cost is \(91/8192 + 1/91 = 0.0221\), about 45× less than full attention. At \(n = 65{,}536\), \(k^{*} = 256\) and the saving is \(\sqrt{n}/2 = 128\times\). [Certain, computed in Python]

In practice the paper often uses fewer clusters with bigger windows: on Wikitext-103, \(k = 16\) and an attention window of 256 tokens. [Certain, Routing Transformer Section 5.2]

Figure 4. The two parts of the Routing Transformer cost (117.9), divided by the cost of full attention: routing \(k/n\) (dashed, rising) and attention inside clusters \(1/k\) (dashed, falling). Their sum (solid) has its minimum at \(k = \sqrt{n}\). Both axes are logarithmic.
How to read Figure 4

The default is \(n = 8{,}192\) and \(k = 91\), close to \(\sqrt{n} = 90.5\): clusters of 90 tokens and a relative cost of \(2.21 \times 10^{-2}\), 45.3× less than full attention. Move \(k\) to 16 (the Wikitext-103 setting): clusters of 512 tokens and 15.5× less work. Move \(n\) to 131,072: the best saving grows to 181×, because \(2/\sqrt{n}\) falls as \(n\) grows. Very many clusters is also bad: at \(k = n/2\) routing costs as much as half of full attention.

Balanced clusters and online centroids

Real k-means gives clusters of different sizes. GPUs want equal sizes. The paper makes them equal: for each centroid it takes the \(w = n/k\) tokens closest to it (a top-\(w\)), sorted by position. A token can then be in two clusters or in none. This adds an \(O(n \log n)\) term. [Certain, Routing Transformer Section 4.1]

The centroids are trained by an exponential moving average of the vectors assigned to them, not by gradient descent:

\[ \boldsymbol\mu \leftarrow \lambda\, \boldsymbol\mu + \frac{1 - \lambda}{2} \sum_{i:\, \mu(Q_i) = \mu} Q_i + \frac{1 - \lambda}{2} \sum_{j:\, \mu(K_j) = \mu} K_j \tag{117.10} \]
Read the symbols
\(\lambda\)
decay, usually 0.999
\(\mu(Q_i)\)
the nearest centroid of query \(i\)

For causal language models a query in a cluster could be matched with a key from the future. As in Reformer, the paper shares queries and keys in the causal case, and reports that this works as well or better than separate Q and K with an extra mask. [Certain] Half of the heads use routing attention and the other half use local attention (except on PG-19): local attention is “a great inductive bias”, and the routing heads add the long-range content links. [Certain, Routing Transformer Section 5]

The results: 15.8 perplexity on Wikitext-103 against 18.3 for Transformer-XL, 33.2 on PG-19 against 33.6 for the Compressive Transformer, and 0.99 bits per byte on enwik8, equal to Transformer-XL. [Certain, Routing Transformer Tables 2, 3, 5]

Algorithm 2: routing attention, one head (Routing Transformer, causal case)
  1. input: \(Q, V \in \R^{n \times d}\), centroids \(\mu \in \R^{k \times d}\), decay \(\lambda\)
  2. \(K \leftarrow Q\); \(Q \leftarrow \operatorname{LayerNorm}(Q)\), \(K \leftarrow \operatorname{LayerNorm}(K)\) // no scale or bias: vectors on a sphere
  3. \(S \leftarrow \mu Q^{\top}\) // \(k \times n\): closeness of every token to every centroid
  4. \(w \leftarrow n / k\); for each centroid, \(\text{idx}_c \leftarrow\) sort(top-\(w\) of row \(c\) of \(S\)) // balanced clusters, kept in time order
  5. gather \(Q', K', V'\) of shape \(k \times w \times d\) with idx
  6. \(A \leftarrow \softmax(\text{causal mask}(Q' K'^{\top}))\); \(X' \leftarrow A V'\) // \(k\) small attentions of size \(w \times w\)
  7. scatter \(X'\) back to token positions
  8. if training: \(\mu \leftarrow \lambda \mu + (1 - \lambda)\, (\text{onehot}(\argmax S)\, Q) / 2 + (1 - \lambda)\, (\text{onehot}(\argmax S)\, K)/2\) // (117.10)

SpAtten: prune tokens and heads on the fly

Cascade token pruning

Reformer and the Routing Transformer change the model. SpAtten (Wang, Zhang and Han, HPCA 2021) works with a trained BERT or GPT-2 and an accelerator chip. The starting point is a measurement: on GPT-2, attention takes more than 50% of the latency on several platforms while it has about 10% of the FLOPs, and on a TITAN Xp GPU about 73% of the attention time is data movement (splitting heads, concatenating K and V, reshapes, transposes). [Certain, SpAtten Section II-B] So the goal is to fetch less data, not only to do less math.

Idea: a token that receives little attention has little influence on the outputs, so stop processing it. The importance of token \(t\) is the sum of the attention probabilities it receives, over all heads and all queries, accumulated over the layers seen so far:

\[ s_t \leftarrow s_t + \sum_{h=1}^{H} \sum_{i} P^{(h)}_{i, t} \tag{117.11} \]
Read the symbols
\(P^{(h)}_{i,t}\)
attention probability from query \(i\) to token \(t\) in head \(h\) of the current layer
\(s_t\)
the cumulative importance score of token \(t\): the column sums of the attention matrices, added up layer after layer

After the layer, SpAtten keeps the top \((1 - p_t)\) fraction of the remaining tokens by \(s_t\), with a pruning ratio \(p_t\) per layer. Cascade means that a pruned token is removed for all later layers: its Q, K and V are never computed or fetched again, and it also leaves the FFN. That is why token pruning saves work outside attention too. Longer sentences are more redundant, so the ratio grows with the length. [Certain, SpAtten Sections I and III-A] For GPT-2, the scores are also accumulated across generation steps, “because intuitively, the unimportant tokens for one token generation should also be unimportant to others”. [Certain, SpAtten Section III-A] This sentence is the seed of H2O.

The paper’s Figure 1 shows BERT-Base on a sentiment example: “As a visual treat, the film is almost perfect.” goes from 11 tokens to 6 tokens after the first layer and to 2 tokens (“film perfect”) after the second, while the heads go from 12 to 10 to 8, and the prediction stays correct. [Certain, SpAtten Figure 1] Figure 5 below runs the same kind of cascade on a toy model.

attention (sum of 2 heads)score, keptscore, pruned after this layer
Figure 5. Cascade token pruning (117.11) in a toy model with 4 layers and 2 heads. The attention of each head comes from a fixed “salience” per word (head 2 also prefers nearby words). Bars are the cumulative scores \(s_t\); after each layer the lowest \(p_t\) fraction is removed for all later layers. The attention numbers are made up for the demonstration; only the pruning rule is SpAtten’s.
How to read Figure 5

At 30% per layer the token count goes \(11 \to 8 \to 6 \to 5\). Layer 1 prunes “a”, “the” and “is”; layer 2 prunes “almost” and “.”. Summed over 4 layers, attention does 51% of the unpruned work (it scales with the square of the token count) and the FFN does 68%. Raise the ratio to 50%: \(11 \to 6 \to 3 \to 2\), attention work 35%, and the two tokens left for layer 4 are “film” and “perfect”, the same two words as in the paper’s example. Note that “,” survives layer 1: punctuation often collects attention, just as in the paper’s example where the comma survives too.

Cascade head pruning and local value pruning

Heads are pruned the same way. The importance of head \(h\) is the accumulated magnitude of its output, because the output projection mixes the heads and a head with large outputs moves the result more:

\[ s_h \leftarrow s_h + \sum_{i} \sum_{c=1}^{D} \big| E^{(h)}_{i, c} \big| \tag{117.12} \]
Read the symbols
\(E^{(h)}\)
the attention output of head \(h\) (before the output projection), one row per query, \(D\) numbers per row
\(s_h\)
cumulative head importance; the top \((1 - p_h)\) fraction is kept, and a pruned head stays pruned in later layers

SpAtten also has local value pruning: inside one head, after the softmax, the V vectors with the smallest probabilities are not fetched. This is per head and not cascaded. [Certain, SpAtten Section III-C] On eight GPT-2 models, token pruning cuts DRAM access by 3.8× and head pruning by 1.1×. [Certain, SpAtten Section I] Head pruning gives less because GPT-2 heads are less redundant than tokens.

Progressive quantization

The third trick decides the bit width per input. SpAtten first fetches only the most significant bits (MSBs) of Q and K and computes the probabilities. If the largest probability is below a threshold (typically 0.1), the distribution is flat and the error matters, so it fetches the least significant bits (LSBs) and computes again. [Certain, SpAtten Sections III-D and V] Why does flat mean sensitive? The derivative of softmax is

\[ \Delta p_i \approx p_i \Big( \Delta s_i - \sum_j p_j\, \Delta s_j \Big), \qquad \frac{\partial p_i}{\partial s_i} = p_i (1 - p_i) \tag{117.13} \]
Read the symbols
\(\Delta s\)
the error in the scores caused by quantized Q and K
\(p_i(1 - p_i)\)
small when \(p_i\) is close to 0 or 1 (one token dominates), largest at \(p_i = 1/2\)
Worked example: the same error on two distributions

Add the score error \(\Delta s = (0.1, -0.1, 0.1, -0.1)\) to two rows of 4 scores.

Flat row \(s = (0, 0, 0, 0)\): \(p = (0.25, 0.25, 0.25, 0.25)\) becomes \((0.275, 0.225, 0.275, 0.225)\). The total change \(\sum_i |\Delta p_i|\) is 0.100.

Peaked row \(s = (4, 0, 0, 0)\): \(p = (0.948, 0.017, 0.017, 0.017)\) becomes \((0.954, 0.014, 0.017, 0.014)\). The total change is 0.012, about 8× smaller. [Certain, computed in Python] So a peaked row tolerates coarse inputs and a flat row does not.

The MSB+LSB settings in the paper are 4+4, 6+4, 8+4, 10+4 and 12+4 bits; 6+4 and 8+4 are common. Progressive quantization saves another 5.1× of memory access. [Certain, SpAtten] Over 30 benchmarks the full system reduces DRAM access by 10.0× with no accuracy loss and reports speedups of 1.6×, 3.0×, 162× and 347× over the A3 accelerator, the MNNFast accelerator, a TITAN Xp GPU and a Xeon CPU. [Certain, SpAtten abstract] These are hardware results: the pruning needs a fast top-k, which SpAtten builds as a special engine. On a GPU, removing tokens of different counts per sequence makes batching harder.

H2O: keep recent tokens and heavy hitters

The KV cache is the new bottleneck

During generation, every layer stores the keys and values of all earlier tokens (session 80). For one sequence of \(T\) tokens the cache takes

\[ M_{\text{KV}} = 2 \cdot L \cdot d_{\text{model}} \cdot b \cdot \min(T, k), \qquad k = \text{budget (tokens kept per head and layer)} \tag{117.14} \]
Read the symbols
2
one key and one value per token
\(L, d_{\text{model}}\)
number of layers and the model width (for MHA, \(n_h d_h = d_{\text{model}}\))
\(b\)
bytes per number (2 in fp16)
\(k\)
the cache budget. Without eviction \(k = \infty\) and the cache grows with \(T\).
Worked example: OPT-30B

OPT-30B has \(L = 48\) layers and \(d_{\text{model}} = 7168\) (from its config.json). In fp16 one token needs \(2 \times 48 \times 7168 \times 2 = 1{,}376{,}256\) bytes. A batch of 128 sequences of 1,024 tokens needs \(1{,}376{,}256 \times 128 \times 1024 = 180.4\) GB, the 180 GB in the H2O paper. With a 20% budget the cache is 36.1 GB. [Certain, computed in Python]

Heavy hitters

H2O (Zhang et al., NeurIPS 2023) makes two observations on OPT, LLaMA and GPT-NeoX. First, attention is very sparse (the 95% above). Second, the accumulated attention score of each token, the sum of the probabilities it receives from all later queries, follows a power law: a small set of tokens collects most of the attention. These are the heavy hitters (H\(_2\)). They correlate with tokens that co-occur often in the text, and masking them out makes accuracy drop sharply. [Certain, H2O Section 3.2]

The ideal policy would keep the tokens that future queries will need, but the future is unknown. H2O’s finding is that the local statistic, the sum of the attention a token has received so far, works about as well. [Certain, H2O Section 4.1] The score is

\[ A_j(i) = \sum_{t = j}^{i} p_{t, j} \cdot \mathbb{1}[\, j \in S_t \,], \qquad S_i = \text{the } k/2 \text{ most recent tokens} \ \cup\ \text{the } k/2 \text{ others with the largest } A_j(i) \tag{117.15} \]
Read the symbols
\(p_{t, j}\)
attention probability from the query at step \(t\) to token \(j\), computed over the tokens in the cache at that step
\(A_j(i)\)
accumulated attention of token \(j\) up to step \(i\); only steps when \(j\) was in the cache count
\(S_i\)
the cache after step \(i\), of size \(k\); H2O splits the budget evenly between recent tokens and heavy hitters

The paper writes the policy as a greedy step: at each decoding step add the new token, and if the cache is larger than \(k\), evict the one token whose removal loses the least score. It frames this as a “dynamic submodular” problem and proves, under assumptions, that the greedy set reaches \((1 - \alpha)(1 - 1/e)\) of the best possible score minus a constant. [Certain, H2O Theorem 4.4, informal]

Worked example: who stays in the cache

Five tokens, five queries. The attention rows (each sums to 1) are

\[ \begin{array}{l|ccccc} & t_1 & t_2 & t_3 & t_4 & t_5 \\ \hline q_1 & 1 & & & & \\ q_2 & 0.6 & 0.4 & & & \\ q_3 & 0.5 & 0.1 & 0.4 & & \\ q_4 & 0.4 & 0.05 & 0.35 & 0.2 & \\ q_5 & 0.35 & 0.05 & 0.3 & 0.1 & 0.2 \\ \hline A_j & 2.85 & 0.60 & 1.05 & 0.30 & 0.20 \end{array} \]

Token 6 arrives and the budget is \(k = 4\): 2 recent and 2 heavy. Recent: \(t_5, t_6\). Heavy, among \(t_1 \dots t_4\): \(t_1\) (2.85) and \(t_3\) (1.05). Evicted: \(t_2\) and \(t_4\). [Certain, column sums in Python] Note that \(t_1\) has a large score partly because it was there for every query: early tokens have more chances to collect attention. This is also the “attention sink” of StreamingLLM (session 116).

Figure 6 runs this greedy policy step by step on a toy decoding of 14 tokens with \(d = 2\). Each step computes the real softmax of the new query over the cached keys, adds the probabilities to the scores \(A_j\), and, if the cache is over budget, evicts the old token with the smallest score.

in the cacheadded in this step (\(p_j\))recent, protectedevicted
  1. for each step \(t\): append \((\mathbf{k}_t, \mathbf{v}_t)\) to the cache \(S\)
  2. \(p_j \leftarrow \softmax_{j \in S}(\mathbf{q}_t \cdot \mathbf{k}_j / \sqrt{d})\)
  3. \(A_j \leftarrow A_j + p_j\) for every \(j \in S\) // (117.15)
  4. if \(|S| \gt k\): \(R \leftarrow\) the \(k/2\) newest tokens
  5. evict \(j^{*} = \argmin_{j \in S \setminus R} A_j\); delete its key and value
Figure 6. The H2O policy (117.15) computed in the browser. Top: the 14 tokens; orange tokens are in the cache, blue frames mark the \(k/2\) newest tokens (protected), evicted tokens are gray with a red cross, dashed tokens are in the future. The small numbers are the current query’s probabilities \(p_j\), computed only over the cache. Bars: the accumulated scores \(A_j\); the green top of a bar is what this step added. Bottom: the share of the full attention (over all tokens so far) that the cache still holds. The vectors are made up; token 0 acts as a sink, tokens 4 and 8 as topic words, and the last query points to token 2. “Local” evicts the oldest token instead.
How to read Figure 6

Press Play or Step. With \(k = 6\) the cache fills up until step 6; from then on every step adds one token and evicts one. At step 6, the recent set is \(\{4, 5, 6\}\) and the scores of the others are \(A_0 = 4.16\), \(A_1 = 0.92\), \(A_2 = 0.32\), \(A_3 = 0.41\), so token 2 is evicted. The sink (token 0) gets between 22% and 40% of each query’s attention from step 4 to step 12 and is never evicted; token 4 reaches \(A_4 = 2.57\) by step 12. The last query (step 13) points to token 2, which was deleted 7 steps earlier: the cache holds only 19.2% of its full attention, against 86.5% on average over all 14 steps. Switch to \(k = 8\): token 2 is evicted at step 8 and the last step keeps 29.8%. “Local” with \(k = 6\) evicts the sink first and keeps 78.0% on average. The policy is good on average and blind to a token that becomes important later, which is the risk of the next section.

Figure 7 runs the policy on a toy decoding of 48 steps. Most queries look at nearby tokens, at token 0 (a sink) and at four “topic” tokens. At steps 41 to 43 a question refers back to token 9, the needle, which got little attention before.

in the cache (darker = more attention)evictedthe needle (token 9)
Figure 7. Four cache policies on the same toy attention. Left: row \(i\) is decoding step \(i\), column \(j\) is key token \(j\); colored cells are in the cache, gray cells were evicted. Right: the full attention of the chosen step, with the bars of evicted tokens in gray, and the share of the full attention mass that the cache keeps. “H2 only” protects only the newest token; H2O protects \(k/2\) recent tokens (117.15).
How to read Figure 7

The default is H2O with \(k = 12\) at step 41, the first question step. Token 9 was evicted at step 16, when it was no longer recent and its score was low. The question’s attention goes mostly to token 9, so the cache keeps only 15.4% of the full mass (16.6% on average over steps 41–43). Raise the budget to 24: the needle survives and the cache keeps 95.8%. “Local” at \(k = 12\) loses the needle at step 22 and keeps only 9.1%. “H2 only” at \(k = 12\) keeps the needle (old tokens have had more steps to collect score) and keeps 90.2% at step 41, but over all 48 steps it keeps 80.2% of the mass on average, against 80.3% for H2O; at \(k = 8\) it also loses the needle. Move the step slider to see which tokens are in the cache earlier.

What H2O reports

  • With a 20% KV budget (5× less cache memory), H2O matches the full cache on many tasks, from 4% to 100% budgets on OPT, LLaMA and GPT-NeoX, including XSUM and CNN/Daily Mail summarization. [Certain, H2O Section 5.1]
  • Both parts are needed. On OPT-30B with PiQA: full cache 78.51, recent tokens only 55.82, heavy hitters only 67.25, both 78.45. [Certain, H2O Table 9]
  • Heavy hitters rescue static patterns: on COPA with OPT-30B and a 20% budget, a local window gets 48.00 (full: 85.00); the same window plus heavy hitters gets 84.00. [Certain, H2O Table 2]
  • System gains: with 20% heavy hitters, up to 29× more throughput than DeepSpeed Zero-Inference and Hugging Face Accelerate, and 3× more than FlexGen, on OPT-6.7B and OPT-30B; up to 1.9× lower latency at the same batch size. [Certain, H2O abstract] These are offloading settings on a T4 GPU, where a smaller cache means less transfer; do not expect 29× on a server that already fits its cache.
  • Combined with attention sinks and position rolling, streaming generation up to four million tokens, with lower perplexity than StreamingLLM. [Certain, H2O Section 5.3]

The risk: evicted means gone

Reformer and the Routing Transformer skip pairs, but every token still has its key and value; the next layer or the next query can find it. SpAtten and H2O remove tokens. H2O says it plainly: “once evicting important KVs, it could destroy the performance of LLMs due to the sequential dependency of LLM generation”. [Certain, H2O Section 3.2] Figure 7 shows the failure: a token that is unimportant for 30 steps becomes the most important one when the question arrives.

How much does a missing token cost? Let \(S\) be the kept set and \(M = \sum_{j \in S} p_j\) the kept mass of the full attention. The cache output renormalizes over \(S\). Then

\[ \Big\lVert \mathbf{o} - \mathbf{o}_S \Big\rVert \le 2\, (1 - M) \max_j \lVert \mathbf{v}_j \rVert, \qquad \mathbf{o}_S = \frac{1}{M} \sum_{j \in S} p_j \mathbf{v}_j \tag{117.16} \]
Read the symbols
\(\mathbf{o}\)
the output with the full cache
\(1 - M\)
the attention mass that fell on evicted tokens
why
split the difference into two parts (below); each part has norm at most \((1 - M)\max_j \lVert \mathbf{v}_j \rVert\)
\[ \mathbf{o} - \mathbf{o}_S = \sum_{j \notin S} p_j \mathbf{v}_j \;-\; \frac{1 - M}{M} \sum_{j \in S} p_j \mathbf{v}_j \]

With \(M = 0.95\) the error is at most \(0.1 \max \lVert \mathbf{v} \rVert\), small. With \(M = 0.15\) (the needle case in Figure 7) the output is mostly made of the wrong tokens. The average kept mass can be high while a few important steps fail completely. That is why averages such as perplexity hide eviction failures, and why needle tests and multi-hop retrieval (RULER, LongBench) are the right tests. [Likely]

Three ways to lower the risk, used by later work:

  • Bigger budget for the important parts of the input. SnapKV (Li et al., 2024) chooses which prompt tokens to keep using an observation window at the end of the prompt, where the question usually is, so the choice already knows the question. [Likely]
  • Do not delete; select. Quest (Tang et al., 2024) keeps the whole cache in memory and, for each query, loads only the pages whose keys can give large scores. Memory is not saved, but memory traffic is, and nothing is lost forever. [Likely]
  • Offload instead of evict: move cold tokens to CPU memory and bring them back if needed (session 130). Slower, but reversible.

The four methods side by side

ReformerRouting TransformerSpAttenH2O
How pairs are chosenrandom angular hash, \(n_r\) roundslearned centroids, spherical k-meanscumulative attention of tokens and headsaccumulated attention + recency
What is skippedpairs in other bucketspairs in other clusterswhole tokens and heads, for all later layersK and V of evicted tokens, for all later steps
Needs training with ityes (shared-QK, LSH)yes (centroids, half routing heads)no (works on trained BERT / GPT-2)no
Main phasetraining and prefill on long inputstraining and prefillprefill and decode, on an acceleratordecode (cache memory)
Cost\(O(l \log l)\) with fixed chunk size\(O(n^{1.5} d)\)cut by the pruning ratioscache fixed at \(k\) tokens
Can it lose information for good?no, only per query and layernoyesyes

A complete example in PyTorch

The code builds a toy LSH attention (shared-QK, several rounds, no chunking) and a toy H2O decoder, and compares them with full attention. It runs on a CPU in about a second and is deterministic.

import torch
torch.manual_seed(0)

def causal_softmax(s):
    T = s.shape[0]
    s = s.masked_fill(torch.ones(T, T).triu(1).bool(), float("-inf"))
    return torch.softmax(s, -1)

def lsh_buckets(x, n_buckets, n_rounds, gen):
    # angular LSH (117.2): h(x) = argmax([xR; -xR]), a new R for every round
    R = torch.randn(n_rounds, x.shape[-1], n_buckets // 2, generator=gen)
    xr = torch.einsum("td,rdb->rtb", x, R)
    return torch.cat([xr, -xr], -1).argmax(-1)              # (n_rounds, T)

def lsh_attention(qk, v, n_buckets, n_rounds, seed=0):
    # shared-QK attention inside the union of buckets (117.3, 117.5)
    T = qk.shape[0]
    k = qk / qk.norm(dim=-1, keepdim=True)                  # k_j = q_j / |q_j|
    gen = torch.Generator().manual_seed(seed)
    h = lsh_buckets(k, n_buckets, n_rounds, gen)
    allowed = (h[:, :, None] == h[:, None, :]).any(0)       # same bucket in some round
    allowed &= torch.ones(T, T).tril().bool()               # causal
    eye = torch.eye(T, dtype=torch.bool)
    lonely = (allowed & ~eye).sum(-1) == 0                  # nothing else to attend to
    allowed &= ~eye | lonely[:, None]                       # no self-attention otherwise
    s = (qk @ k.T).masked_fill(~allowed, float("-inf"))
    return torch.softmax(s, -1) @ v, allowed

def h2o_decode(q, k, v, budget, heavy=True):
    # one token per step; keep budget//2 recent tokens + heavy hitters (117.15)
    T = q.shape[0]
    cache, acc, outs = [], torch.zeros(T), []
    for i in range(T):
        cache.append(i)
        idx = torch.tensor(cache)
        p = torch.softmax(q[i] @ k[idx].T, -1)             # attention over the cache only
        outs.append(p @ v[idx])
        acc[idx] += p                                       # accumulated attention score
        if len(cache) > budget:                             # evict exactly one token
            old = cache[: len(cache) - budget // 2]         # not in the recent window
            victim = min(old, key=lambda j: acc[j].item()) if heavy else old[0]
            cache.remove(victim)
    return torch.stack(outs)

def rel_err(a, b):
    return ((a - b).norm(dim=-1) / b.norm(dim=-1)).mean().item()

T, d = 256, 64
# tokens come from 16 "topics": similar tokens share a direction
centers = torch.randn(16, d)
x = centers[torch.randint(0, 16, (T,))] + 0.5 * torch.randn(T, d)
qk = 8 * x / x.norm(dim=-1, keepdim=True)                   # scores = 8 cos(angle)
v = torch.randn(T, d)
k = qk / qk.norm(dim=-1, keepdim=True)
P = causal_softmax(qk @ k.T)
P = P * (1 - torch.eye(T)); P[0, 0] = 1; P = P / P.sum(-1, keepdim=True)  # no self (as in LSH)
ref = P @ v
print("LSH attention, 256 tokens, 16 topics")
for nb, nr in [(8, 1), (8, 4), (32, 1), (32, 4)]:
    out, allowed = lsh_attention(qk, v, nb, nr)
    # baseline: the same number of keys per query, chosen at random (still causal)
    g = torch.Generator().manual_seed(1)
    rnd = torch.rand(T, T, generator=g).masked_fill(torch.ones(T, T).triu().bool(), 2.0)
    rmask = rnd.argsort(-1).argsort(-1) < allowed.sum(-1, keepdim=True)
    rmask[0, 0] = True
    s = (qk @ k.T).masked_fill(~rmask, float("-inf"))
    e_rnd = rel_err(torch.softmax(s, -1) @ v, ref)
    print(f"  buckets={nb:2d} rounds={nr}: keys/query {allowed.sum(-1).float().mean():5.1f}, "
          f"error {rel_err(out, ref):.3f} (random keys: {e_rnd:.3f})")

# decoding with a few heavy-hitter tokens that many queries like
u = torch.randn(d); u = u / u.norm()
q = torch.randn(T, d) / d ** 0.25 + 1.5 * u
kd = torch.randn(T, d) / d ** 0.25
kd[torch.tensor([0, 3, 17, 40, 90])] += 3 * u                # heavy hitters
ref = causal_softmax(q @ kd.T) @ v
print("KV eviction, 256 decode steps")
for B in [16, 32, 64]:
    e_loc = rel_err(h2o_decode(q, kd, v, B, heavy=False), ref)
    e_h2o = rel_err(h2o_decode(q, kd, v, B, heavy=True), ref)
    print(f"  budget={B:2d}: local error {e_loc:.3f}, H2O error {e_h2o:.3f}")

Output (PyTorch 2.8, CPU):

LSH attention, 256 tokens, 16 topics
  buckets= 8 rounds=1: keys/query  18.7, error 0.963 (random keys: 1.838)
  buckets= 8 rounds=4: keys/query  56.2, error 0.152 (random keys: 1.146)
  buckets=32 rounds=1: keys/query   6.4, error 1.442 (random keys: 2.193)
  buckets=32 rounds=4: keys/query  21.4, error 0.377 (random keys: 1.853)
KV eviction, 256 decode steps
  budget=16: local error 1.224, H2O error 0.413
  budget=32: local error 1.025, H2O error 0.316
  budget=64: local error 0.783, H2O error 0.192

Read the numbers. LSH with the same number of keys is always much better than random keys: hashing finds the right keys. More rounds help a lot (8 buckets: error 0.963 → 0.152), more buckets alone hurt (fewer keys per query). Errors above 1 mean that many queries found no same-topic key and attended to unrelated tokens. For decoding, heavy hitters cut the error about 3× against a recent-only window at every budget. Toy data with built-in topics and heavy hitters makes both methods look good; real models are harder.

Where this is used

SettingMethodWhy it fits
Long-document language modeling and long generative tasks (books, music, images as pixels)Reformer, Routing TransformerTraining on 8K to 64K tokens where full attention does not fit [Certain, the papers’ tasks]
Chat and long-generation serving with limited GPU memoryH2O-style eviction, SnapKV for long promptsThe cache is fixed at \(k\) tokens, so batch size or context can grow (117.14)
Offloaded inference on small GPUs (FlexGen-style)H2OLess cache to move over PCIe; the 29× throughput results are in this setting [Certain]
Edge accelerators for BERT/GPT-2-size modelsSpAttenFewer DRAM reads; top-k in hardware
Near-duplicate video detection and video fingerprintingLSH (the hashing idea of Reformer)Hash frame or clip embeddings so similar clips fall into the same bucket; compare only inside buckets [Likely]
Video retrieval over many clipsk-means routing / inverted-file searchThe same nearest-centroid idea as (117.8); search only the closest clusters [Likely]
Streaming video LLMs, live captioningSinks + recent window + heavy hittersUnbounded frame tokens; the cache must stay fixed in size [Likely]
Video QA, key-moment detection, Video-RAGAttention-based token pruning (SpAtten-like) on frame tokensThousands of frame tokens, most of them redundant; but a short key moment may be the needle, so check with needle-in-the-video tests [Likely]
Action recognition and video classificationToken pruning or clustering of patch tokensMany patches are static background; dropping or merging them saves FLOPs [Likely]

Common mistakes

  • Switching a trained dense model to LSH attention. Reformer’s copy task: a full-attention model evaluated with 1-round LSH gets 52.5%. LSH and shared-QK must be part of training.
  • Forgetting the self-mask in shared-QK. \(\mathbf{q}_i \cdot \mathbf{k}_i\) is the largest score, so each token attends mostly to itself.
  • Using many buckets and one round. Sharp hashes miss close neighbors on borders. Add rounds (117.5) or use fewer buckets.
  • Expecting unbalanced k-means clusters to run fast. GPUs need equal blocks; the Routing Transformer uses top-\(w\) per centroid for this.
  • Calling H2O “lossless”. It matches the full cache on many benchmarks, but an evicted token cannot come back. Test with needle and multi-hop retrieval at production length, not only perplexity or averages.
  • Dropping the recent window. H2O’s ablation: heavy hitters alone lose up to 22.75% accuracy; both parts are needed.
  • Ignoring the age bias of accumulated scores. Early tokens have had more queries, so they collect more score. This helps keep sinks, but it can keep stale tokens and evict newer important ones.
  • Reading 29× throughput as a general speedup. It is measured with offloading on a T4. On a GPU where the cache already fits, the gain is a larger batch, not 29× per request.

Interview questions

What is the difference between static and dynamic sparse attention?basic
Both restrict each query to a set \(P_i\) of keys (117.1). Static methods choose \(P_i\) from positions only (windows, strides, global tokens, sinks), the same for every input. Dynamic methods choose it from the content: hash buckets (Reformer), learned clusters (Routing Transformer), or attention scores of earlier layers and steps (SpAtten, H2O). Static is cheap and GPU-friendly but blind to content; dynamic can find far, relevant tokens but costs extra work to decide, and the score-based ones can remove tokens for good.
How does LSH attention work in Reformer?core
Hash each key with \(h(\mathbf{x}) = \argmax([\mathbf{x}R; -\mathbf{x}R])\) for a random \(R\) (117.2); close vectors usually get the same bucket. Queries and keys are shared (\(\mathbf{k} = \mathbf{q}/\lVert\mathbf{q}\rVert\)) so a query and its keys hash together. Sort by bucket and position, cut into chunks of \(m = 2l/n_{\text{buckets}}\), and let each chunk attend to itself and the previous chunk, masking other buckets, the future and self. Repeat with \(n_r\) independent hashes and merge the rounds with their log-sum-exp (117.6). With a fixed chunk, the attention cost is linear in \(l\) plus an \(O(l \log l)\) sort.
Why does Reformer share Q and K, and what problem does that create?core
If Q and K were different, a bucket could contain queries but no keys, and chunks would not line up. With \(\mathbf{k}_j = \mathbf{q}_j/\lVert\mathbf{q}_j\rVert\), \(h(\mathbf{q}_j) = h(\mathbf{k}_j)\) and one sort serves both. The problem: \(\mathbf{q}_i \cdot \mathbf{k}_i = \lVert\mathbf{q}_i\rVert\) is the largest score, so tokens would attend to themselves. Reformer masks the diagonal unless a token has no other target. The paper reports no loss in quality from sharing on enwik8 and imagenet64.
Why are several hash rounds needed? Give a number.core
One hash can split two close vectors across a border. If one round finds a pair with probability \(p\), \(n_r\) rounds miss it with probability \((1-p)^{n_r}\) (117.5). With 32 buckets and a 45° pair, \(p \approx 0.31\): one round finds it 31% of the time, four rounds 77%, eight 95%. Reformer’s copy task: a model trained with 4 rounds gets 91.9% with 1 round at evaluation and 100% with 8. Cost grows linearly with \(n_r\).
Derive the best number of clusters in the Routing Transformer.core
Routing costs \(nkd\) (every vector against every centroid). Attention inside balanced clusters of size \(n/k\) costs \(n \cdot (n/k) \cdot d\). \(C(k) = nkd + n^2 d/k\); \(dC/dk = nd - n^2 d/k^2 = 0\) gives \(k = \sqrt{n}\) and \(C = 2n^{1.5}d\) (117.9). Relative to full attention: \(2/\sqrt{n}\), so about 45× less at \(n = 8192\) and 128× less at \(n = 65{,}536\).
Why does k-means on unit vectors approximate maximum inner-product search?advanced
For unit vectors \(\lVert\mathbf{q}-\mathbf{k}\rVert^2 = 2 - 2\mathbf{q}\cdot\mathbf{k}\) (117.8), so the nearest key is the key with the largest dot product. If \(\mathbf{q}\) and \(\mathbf{k}\) are both within \(\varepsilon\) of one centroid, \(\lVert\mathbf{q}-\mathbf{k}\rVert \lt 2\varepsilon\) and \(\mathbf{q}\cdot\mathbf{k} \gt 1 - 2\varepsilon^2\). Pairs in one cluster have large scores. The Routing Transformer uses LayerNorm without scale and bias to put Q and K on a sphere, and updates centroids by an EMA with \(\lambda = 0.999\).
How does SpAtten decide which tokens and heads to prune?core
Token importance is the column sum of the attention probabilities over heads and queries, accumulated over layers (117.11) and, for GPT-2, over generation steps. After each layer the lowest \(p_t\) fraction is pruned, and the pruning is cascaded: the token is gone for all later layers, including their FFNs. Head importance is the accumulated absolute value of each head’s output (117.12), also cascaded. On GPT-2, token pruning cuts DRAM access 3.8× and head pruning 1.1×. Nothing is trained; the choice depends on each input.
Why does SpAtten fetch more bits only when the attention is flat?advanced
The softmax derivative is \(\partial p_i / \partial s_i = p_i(1-p_i)\) (117.13): close to zero when one token dominates, large when probabilities are spread out. So a score error from coarse Q and K changes a peaked distribution little and a flat one a lot. Example: the same error \(\pm 0.1\) changes a flat 4-way softmax by 0.100 in total, a peaked one by 0.012. SpAtten computes with MSBs, and only if the max probability is below a threshold (about 0.1) fetches the LSBs and recomputes, saving about 5.1× memory access.
What is H2O and why does it need both recent tokens and heavy hitters?basic
H2O is a KV-cache eviction policy for decoding. The cache has a fixed budget \(k\): half for the most recent tokens, half for heavy hitters, the tokens with the largest accumulated attention so far (117.15). Recent tokens carry local syntax; heavy hitters carry tokens that many queries need (topic words, sinks). Each alone fails: on OPT-30B PiQA, recent only 55.82, heavy only 67.25, both 78.45, full 78.51. With a 20% budget it often matches the full cache.
Your H2O cache passes the average benchmarks but fails needle-in-a-haystack. Why, and what do you do?advanced
The needle got little attention before the question, so its accumulated score was low and it was evicted. Eviction is permanent: when the question comes, the key and value are gone, and the output is made from the wrong tokens (bound 117.16 with small kept mass). Averages hide this because most steps do not need old tokens. Fixes: a bigger budget; choose prompt tokens with a window that includes the question (SnapKV-style); keep the full cache and select per query (Quest-style); offload instead of evict; protect special regions (system prompt, documents). Test at production length with RULER or your own needle tasks.
How would you implement H2O in a production engine with FlashAttention, GQA and paged memory?advanced
The scores need the attention probabilities, but FlashAttention does not write them out; add column sums inside the decode kernel (cheap during decode, one query row per head) or recompute them for a sample of steps. With GQA, sum the scores of the query heads in each group so there is one decision per KV head. With PagedAttention, evicting single tokens leaves holes; evict in blocks, or compact pages from time to time. Keep an eviction budget per layer, since layers have different sparsity. Measure on long-context tasks, not only throughput. [Likely, engineering judgment]

Exercises

  1. Hash \(\mathbf{w} = (0.2, -1)\) with the \(R\) of the first worked example. Which bucket? Is it the bucket of \(\mathbf{x} = (1, 0.5)\)?
  2. A Reformer layer has \(l = 16{,}384\) tokens and chunks of \(m = 64\). How many buckets? How many scores per round, and how many times fewer than full attention? And with 4 rounds?
  3. One hash round finds a pair with \(p = 0.2\). How many rounds are needed to find it with probability at least 0.9?
  4. Routing attention with \(n = 32{,}768\). What is \(k^{*}\)? What is the cost relative to full attention at \(k^{*}\) and at \(k = 32\)?
  5. In the H2O worked example, the budget is \(k = 3\) (1 recent, 2 heavy). Which tokens stay when token 6 arrives?
  6. Llama 2 7B has 32 layers and \(d_{\text{model}} = 4096\), MHA, fp16. What is the cache of one 32,768-token sequence with a full cache, and with a 20% H2O budget?
  7. The kept mass is \(M = 0.8\) and \(\max\lVert\mathbf{v}\rVert = 3\). Give the bound (117.16) on the output error.
Answerscheck
1. \(\mathbf{w}R = (0.2 \cdot 0.6 - 1 \cdot 0.8,\ 0.2 \cdot (-0.8) - 1 \cdot 0.6) = (-0.68, -0.76)\); the vector \((-0.68, -0.76, 0.68, 0.76)\) has its max at index 3, so \(h = 3\), not the bucket 0 of \(\mathbf{x}\). 2. \(n_{\text{buckets}} = 2 \times 16{,}384/64 = 512\). One round: \(16{,}384 \times 128 = 2{,}097{,}152\) scores; full: \(268{,}435{,}456\); 128× fewer. Four rounds: 8,388,608 scores, 32× fewer. 3. Need \(1 - 0.8^{n_r} \ge 0.9\), so \(0.8^{n_r} \le 0.1\), \(n_r \ge \ln 0.1/\ln 0.8 = 10.3\): 11 rounds. 4. \(k^{*} = \sqrt{32{,}768} = 181.0\); relative cost \(2/181.0 = 0.0110\) (90.5× less). At \(k = 32\): \(32/32{,}768 + 1/32 = 0.0322\) (31.0× less). 5. Recent: \(t_6\). Heavy among \(t_1 \dots t_5\): \(t_1\) (2.85) and \(t_3\) (1.05). Evicted: \(t_2, t_4, t_5\). 6. Per token \(2 \times 32 \times 4096 \times 2 = 524{,}288\) bytes; \(\times 32{,}768 = 17.18\) GB; 20%: 3.44 GB. 7. \(2 \times 0.2 \times 3 = 1.2\).

Key takeaways

  • Dynamic sparse attention chooses the key set \(P_i\) from the content (117.1). Attention is very sparse in trained LLMs (over 95% of entries below 1% of the row max in OPT), so most pairs can be skipped if you can find the important ones cheaply.
  • Reformer: angular LSH (117.2), shared Q and K, sort and chunk into equal blocks (117.4), several rounds to fix border misses (117.5). Must be trained with hashing.
  • Routing Transformer: spherical k-means with learned centroids; unit vectors make distance and score the same (117.8); best \(k = \sqrt{n}\), cost \(O(n^{1.5} d)\) (117.9).
  • SpAtten: cascade pruning of tokens by cumulative attention (117.11) and of heads by output size (117.12), plus more bits only for flat softmaxes (117.13). A hardware co-design: 10× less DRAM access.
  • H2O: a fixed KV budget split between recent tokens and heavy hitters by accumulated attention (117.15). 20% budget often matches the full cache; both halves are needed.
  • Eviction is permanent. The output error grows with the evicted attention mass (117.16); a token that matters only later (the needle) breaks the policy. Test with needle and retrieval tasks, and prefer selection or offloading when loss is not acceptable.

Key formulas

\[ h(\mathbf{x}) = \argmax([\mathbf{x}R; -\mathbf{x}R]), \qquad \Pr[\text{miss}] = (1 - p)^{n_r}, \qquad m = \frac{2l}{n_{\text{buckets}}} \]
\[ \lVert\mathbf{q} - \mathbf{k}\rVert^2 = 2 - 2\,\mathbf{q}\cdot\mathbf{k}, \qquad C(k) = nkd + \frac{n^2 d}{k}, \quad k^{*} = \sqrt{n} \]
\[ s_t \mathrel{+}= \sum_h \sum_i P^{(h)}_{i,t}, \qquad A_j(i) = \sum_{t \le i} p_{t,j}, \qquad \lVert\mathbf{o} - \mathbf{o}_S\rVert \le 2(1 - M)\max_j\lVert\mathbf{v}_j\rVert \]

References for this session

  1. Kitaev et al. (2020). Reformer: The Efficient Transformer
  2. Roy et al. (2020). Efficient Content-Based Sparse Attention with Routing Transformers
  3. Wang et al. (2020). SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning
  4. Zhang et al. (2023). H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models
  5. Kitaev et al. (2020). Reformer: The Efficient Transformer
  6. Roy et al. (2020). Efficient Content-Based Sparse Attention with Routing Transformers
  7. Wang et al. (2020). SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning
  8. Zhang et al. (2023). H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models
  9. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  10. Child et al. (2019). Generating Long Sequences with Sparse Transformers
  11. Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
  12. Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
  13. Gomez et al. (2017). The Reversible Residual Network: Backpropagation Without Storing Activations
  14. Li et al. (2024). SnapKV: LLM Knows What You are Looking for Before Generation
  15. Tang et al. (2024). Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference
  16. Liu et al. (2023). Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time