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.
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:
- 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
- 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.
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:
- 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.
- draw \(R\): \(b/2\) unit directions, turned by a random angle \(\theta\)
- for each token \(j\): \(\mathbf{k}_j \leftarrow \mathbf{q}_j / \lVert \mathbf{q}_j \rVert\) // shared-QK (117.3)
- \(h_j \leftarrow \argmax([\mathbf{k}_j R \,;\, -\mathbf{k}_j R])\) // (117.2)
- sort the tokens by \((h_j, j)\)
- for each query \(i\): \(P_i \leftarrow \{ j \lt i : h_j = h_i \}\), or \(\{i\}\) if empty
- \(s_{ij} \leftarrow \mathbf{q}_i \cdot \mathbf{k}_j / \sqrt{d}\) for \(j \in P_i\)
- \(p_{ij} \leftarrow \softmax\) of \(s_{ij}\) over \(P_i\) only
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:
- 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.
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:
- 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):
- 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.
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):
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]
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]
- input: shared queries/keys \(Q \in \R^{l \times d}\), values \(V\), number of buckets \(b\), rounds \(n_r\), chunk size \(m = 2l/b\)
- \(K \leftarrow Q / \lVert Q \rVert\) row by row // shared-QK, formula (117.3)
- for \(r = 1, \dots, n_r\):
- 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)
- sort positions by \((h_j, j)\); cut the sorted list into chunks of \(m\)
- for each chunk \(c\): scores \(\leftarrow Q_c\, [K_{c-1}; K_c]^{\top} / \sqrt{d}\) // \(m \times 2m\) block
- mask: other bucket, future position, self (unless no other target), and \(\log N_{i,j}\) for repeats
- \(\mathbf{o}^{(r)}, z^{(r)} \leftarrow\) softmax-weighted sum of \([V_{c-1}; V_c]\) and the log-sum-exp
- un-sort \(\mathbf{o}^{(r)}\) and \(z^{(r)}\) back to the original order
- 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,
- 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\):
- 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.
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]
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:
- 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]
- input: \(Q, V \in \R^{n \times d}\), centroids \(\mu \in \R^{k \times d}\), decay \(\lambda\)
- \(K \leftarrow Q\); \(Q \leftarrow \operatorname{LayerNorm}(Q)\), \(K \leftarrow \operatorname{LayerNorm}(K)\) // no scale or bias: vectors on a sphere
- \(S \leftarrow \mu Q^{\top}\) // \(k \times n\): closeness of every token to every centroid
- \(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
- gather \(Q', K', V'\) of shape \(k \times w \times d\) with idx
- \(A \leftarrow \softmax(\text{causal mask}(Q' K'^{\top}))\); \(X' \leftarrow A V'\) // \(k\) small attentions of size \(w \times w\)
- scatter \(X'\) back to token positions
- 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:
- 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.
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:
- 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
- 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\)
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
- 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\).
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
- 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]
Five tokens, five queries. The attention rows (each sums to 1) are
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.
- for each step \(t\): append \((\mathbf{k}_t, \mathbf{v}_t)\) to the cache \(S\)
- \(p_j \leftarrow \softmax_{j \in S}(\mathbf{q}_t \cdot \mathbf{k}_j / \sqrt{d})\)
- \(A_j \leftarrow A_j + p_j\) for every \(j \in S\) // (117.15)
- if \(|S| \gt k\): \(R \leftarrow\) the \(k/2\) newest tokens
- evict \(j^{*} = \argmin_{j \in S \setminus R} A_j\); delete its key and value
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.
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
- 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\)
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
| Reformer | Routing Transformer | SpAtten | H2O | |
|---|---|---|---|---|
| How pairs are chosen | random angular hash, \(n_r\) rounds | learned centroids, spherical k-means | cumulative attention of tokens and heads | accumulated attention + recency |
| What is skipped | pairs in other buckets | pairs in other clusters | whole tokens and heads, for all later layers | K and V of evicted tokens, for all later steps |
| Needs training with it | yes (shared-QK, LSH) | yes (centroids, half routing heads) | no (works on trained BERT / GPT-2) | no |
| Main phase | training and prefill on long inputs | training and prefill | prefill and decode, on an accelerator | decode (cache memory) |
| Cost | \(O(l \log l)\) with fixed chunk size | \(O(n^{1.5} d)\) | cut by the pruning ratios | cache fixed at \(k\) tokens |
| Can it lose information for good? | no, only per query and layer | no | yes | yes |
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
| Setting | Method | Why it fits |
|---|---|---|
| Long-document language modeling and long generative tasks (books, music, images as pixels) | Reformer, Routing Transformer | Training on 8K to 64K tokens where full attention does not fit [Certain, the papers’ tasks] |
| Chat and long-generation serving with limited GPU memory | H2O-style eviction, SnapKV for long prompts | The cache is fixed at \(k\) tokens, so batch size or context can grow (117.14) |
| Offloaded inference on small GPUs (FlexGen-style) | H2O | Less cache to move over PCIe; the 29× throughput results are in this setting [Certain] |
| Edge accelerators for BERT/GPT-2-size models | SpAtten | Fewer DRAM reads; top-k in hardware |
| Near-duplicate video detection and video fingerprinting | LSH (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 clips | k-means routing / inverted-file search | The same nearest-centroid idea as (117.8); search only the closest clusters [Likely] |
| Streaming video LLMs, live captioning | Sinks + recent window + heavy hitters | Unbounded frame tokens; the cache must stay fixed in size [Likely] |
| Video QA, key-moment detection, Video-RAG | Attention-based token pruning (SpAtten-like) on frame tokens | Thousands 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 classification | Token pruning or clustering of patch tokens | Many 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
How does LSH attention work in Reformer?core
Why does Reformer share Q and K, and what problem does that create?core
Why are several hash rounds needed? Give a number.core
Derive the best number of clusters in the Routing Transformer.core
Why does k-means on unit vectors approximate maximum inner-product search?advanced
How does SpAtten decide which tokens and heads to prune?core
Why does SpAtten fetch more bits only when the attention is flat?advanced
What is H2O and why does it need both recent tokens and heavy hitters?basic
Your H2O cache passes the average benchmarks but fails needle-in-a-haystack. Why, and what do you do?advanced
How would you implement H2O in a production engine with FlashAttention, GQA and paged memory?advanced
Exercises
- 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)\)?
- 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?
- One hash round finds a pair with \(p = 0.2\). How many rounds are needed to find it with probability at least 0.9?
- Routing attention with \(n = 32{,}768\). What is \(k^{*}\)? What is the cost relative to full attention at \(k^{*}\) and at \(k = 32\)?
- In the H2O worked example, the budget is \(k = 3\) (1 recent, 2 heavy). Which tokens stay when token 6 arrives?
- 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?
- The kept mass is \(M = 0.8\) and \(\max\lVert\mathbf{v}\rVert = 3\). Give the bound (117.16) on the output error.
Answerscheck
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
References for this session
- Kitaev et al. (2020). Reformer: The Efficient Transformer
- Roy et al. (2020). Efficient Content-Based Sparse Attention with Routing Transformers
- Wang et al. (2020). SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning
- Zhang et al. (2023). H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models
- Kitaev et al. (2020). Reformer: The Efficient Transformer
- Roy et al. (2020). Efficient Content-Based Sparse Attention with Routing Transformers
- Wang et al. (2020). SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning
- Zhang et al. (2023). H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Child et al. (2019). Generating Long Sequences with Sparse Transformers
- Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
- Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
- Gomez et al. (2017). The Reversible Residual Network: Backpropagation Without Storing Activations
- Li et al. (2024). SnapKV: LLM Knows What You are Looking for Before Generation
- Tang et al. (2024). Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference
- Liu et al. (2023). Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time