Efficient attention 2: low-rank attention (Linformer, Luna, Set Transformer)
Full attention builds an n × n table for every head, so its cost grows with the square of the sequence length. This session shows that this table is often close to low rank, and how Linformer, the Set Transformer and Luna use that to make attention linear in n: project the keys and values to a fixed length, or let a few learned queries pack the sequence and then unpack it. You will also see why these methods are hard to use with causal masking and variable lengths, and where the pack idea lives on in vision-language models.
What you will learn
- Why full attention costs 4n²d FLOPs and an n × n matrix per head, and what FlashAttention does and does not fix
- What rank, the SVD and the Eckart–Young theorem tell us about approximating an attention matrix, and which heads are low rank and which are not
- Linformer: the learned projections E and F, the cost 8nkd, the ratio n/(2k), parameter sharing, and the measured results
- Set Transformer (ISAB, PMA) and Luna: pack a sequence into l learned summaries, then unpack, with cost linear in n and no dependence on the length
- Why causal masking and variable lengths break fixed projections, what a causal fix costs, and why decoder LLMs rarely use low-rank attention
- How the same pack idea appears in VLM connectors (Q-Former, Perceiver Resampler) and in video models
Why this matters
Full attention compares every token with every other token. For a sequence of \(n\) tokens, each head builds an \(n \times n\) table of scores. At \(n = 4096\), one head in one layer has 16.8 million scores; in FP16 that is 32 MiB, and with 32 heads it is 1 GiB per layer. Double the length and all of this grows four times.
In session 93 you saw that this square term takes over at long context, and in session 97 you made the KV cache smaller by sharing keys and values across heads. That did not touch the \(n^2\) term. This session attacks it directly with one idea: the attention matrix often carries much less information than its size suggests. If an \(n \times n\) matrix is close to a matrix of rank \(k\) (it can be written with only \(k\) independent directions), we never need to build the full matrix. We can work with an \(n \times k\) matrix instead, and the cost becomes linear in \(n\).
The efficient-inference survey of Zhou et al. puts this family under “efficient attention” in its model-level section (5.1.2), next to sparse attention and kernel-based attention. [Certain] We study three members:
- Linformer (Wang et al., 2020): project the keys and values from length \(n\) down to a fixed length \(k\) with a learned matrix.
- Set Transformer (Lee et al., 2019) and Luna (Ma et al., 2021): a small set of learned query vectors first reads the whole sequence (“pack”), and then every token reads that small set (“unpack”).
- A short look at Funnel-Transformer (Dai et al., 2020), which shrinks the sequence itself between blocks.
Low-rank attention is rarely used inside today’s large decoder-only LLMs, and this session explains why: causal masking and variable lengths are hard for it. But the pack-then-read idea is everywhere in vision-language models. BLIP-2’s Q-Former uses 32 learned queries, and Flamingo’s Perceiver Resampler turns any number of image or video features into 64 visual tokens. [Certain] So the same math you learn here explains how a VLM squeezes a video into a few dozen tokens.
The cost we want to remove
Recall scaled dot-product attention for one head (session 17). The queries \(Q\), keys \(K\) and values \(V\) are \(n \times d\) matrices, one row per token, where \(d\) is the head size:
- Read the symbols
- \(P\)
- the attention matrix (Linformer calls it the “context mapping matrix”). Row \(i\) holds the weights token \(i\) puts on all \(n\) tokens; each row sums to 1
- \(\softmax\)
- applied to each row separately
- \(O\)
- the output: each row is a weighted average of value rows
- \(4n^2 d\)
- \(2n^2 d\) FLOPs for \(QK^\top\) and \(2n^2 d\) for \(PV\) (a multiply plus an add counts as 2)
Both the compute and the size of \(P\) grow with \(n^2\). FlashAttention (session 124) removes the memory problem, because it never writes \(P\) to main memory, but it still does all \(4n^2 d\) FLOPs. The methods in this session try to remove the FLOPs too, by never forming an \(n \times n\) matrix at all. The price is that the result is an approximation of full attention, not the exact value.
Is the attention matrix low rank?
What rank means here
The rank of a matrix is the number of independent directions in it. A rank-1 matrix has every row equal to a multiple of one row vector. Any matrix can be split by the singular value decomposition (SVD) into a sum of rank-1 pieces, sorted from most to least important:
- Read the symbols
- \(\sigma_i\)
- the \(i\)-th singular value: how much of the matrix lies in the \(i\)-th piece
- \(\mathbf{u}_i, \mathbf{v}_i\)
- unit-length column and row directions of that piece
If we keep only the first \(r\) pieces we get \(P_r\), a rank-\(r\) matrix. The Eckart–Young theorem says no other rank-\(r\) matrix is closer to \(P\), and it gives the error exactly:
Here \(\lVert \cdot \rVert_F\) is the Frobenius norm, the square root of the sum of all squared entries. So the question “is \(P\) low rank?” becomes: do the singular values fall fast? If they do, a small \(r\) leaves a small error.
Why it can be low rank, and why not always
The score matrix \(QK^\top\) has rank at most \(d\) (for example 64), because it is a product of an \(n \times d\) and a \(d \times n\) matrix. But the softmax takes the exponential of each entry, and that breaks the rank: \(P\) can have full rank \(n\). What matters is how sharp the attention is.
- If attention is smooth (many tokens get similar weights), rows of \(P\) look alike and few directions are needed.
- If most rows put their weight on the same few tokens (for example a first token that collects attention, often called an “attention sink”), \(P\) is close to rank 1.
- If each token attends sharply to its own neighbours (a local or “previous token” head), \(P\) is close to a shifted identity matrix, and an identity matrix has full rank. Low-rank methods cannot copy this pattern well.
Linformer measured real models. They took RoBERTa-base (12 layers) and RoBERTa-large (24 layers) at \(n = 512\), ran an SVD of \(P\) for every layer and head, and averaged over 10,000 sentences of Wiki103 and IMDB. The spectrum had a long tail: most of the mass sat in the first singular values. They also found that higher layers were more low rank than lower layers. [Certain] Figure 1 lets you see all three cases on a small synthetic matrix.
How to read Figure 1
Darker cells mean larger weights. The right plot shows \(\sum_{i \le j} \sigma_i / \sum_i \sigma_i\) against \(j\); the dashed line marks your \(r\). A curve that jumps up fast means a low-rank matrix. Start with “Content” at \(\beta = 1\): rank 8 already gives a relative error of about 0.34. Raise \(\beta\): attention gets sharper and the error grows. Switch to “Attention sink” and raise \(\beta\): almost all rows look the same and rank 1 is enough. Switch to “Local”: the matrix becomes a band around the diagonal and you need almost all 48 directions. The readout also counts how many directions you need to keep 99% of \(\sum \sigma_i^2\).
Linformer also gives a theoretical reason. Their Theorem 1 uses the Johnson–Lindenstrauss lemma (a random projection to \(k\) dimensions keeps lengths and distances almost unchanged): for any value vector \(\mathbf{w}\), a random matrix \(R \in \R^{k \times n}\) with entries from \(\mathcal{N}(0, 1/k)\) gives \(\lVert P R^\top R \mathbf{w} - P\mathbf{w} \rVert \le \varepsilon \lVert P\mathbf{w} \rVert\) with high probability when
This grows only like \(\log n\). But the constant is large: for \(n = 512\) and \(\varepsilon = 0.5\) it gives \(k \approx 250\), and for \(\varepsilon = 0.1\) it gives \(k \approx 3{,}466\), larger than \(n\) itself. So the theorem tells us the direction (rank can be much smaller than \(n\)), and the experiments tell us the useful values (\(k = 128\) to \(256\)). [Certain]
Linformer: project keys and values from n to k
A low-rank \(P\) suggests computing an SVD, but an SVD of every attention matrix would cost more than it saves. Linformer’s trick is cheaper. Before attention, it multiplies the keys and the values by two learned matrices \(E, F \in \R^{k \times n}\). Each row of \(EK\) is a learned weighted sum of all \(n\) key rows, so \(EK\) is a short “summary sequence” of \(k\) keys. The same for \(FV\). Then normal attention runs between the \(n\) queries and the \(k\) summary rows:
- Read the symbols
- \(E, F\)
- learned projection matrices of shape \(k \times n\); \(E\) mixes the keys, \(F\) mixes the values. They are trained with the rest of the model
- \(EK, FV\)
- \(k \times d\) matrices: \(k\) summary keys and \(k\) summary values
- \(\bar P\)
- an \(n \times k\) attention matrix: each token distributes its weight over \(k\) summaries instead of \(n\) tokens
The queries are not projected, so the output still has one row per token. Linformer’s Theorem 2 says that with suitable \(E\) and \(F\), a \(k\) of order \(d \log d / \varepsilon^2\) is enough, independent of \(n\). [Certain] Note what is learned: \(E\) is a fixed matrix; it does not depend on the content of this particular sequence, only on positions.
The cost
Per head, we have four matrix products: \(EK\) and \(FV\) (\(2knd\) FLOPs each), \(Q(EK)^\top\) (\(2nkd\)) and \(\bar P (FV)\) (\(2nkd\)):
Linear in \(n\) for a fixed \(k\). The FLOP saving only starts when \(n \gt 2k\): with \(k = 256\), Linformer does more work than full attention below 512 tokens.
Figure 2 runs formula (98.5) in your browser on a tiny example and counts the FLOPs of (98.6) as it goes. Each step is one line of the loop: first the \(k\) summary keys, then the \(k\) summary values, then one row of \(\bar P\) and one output row per token.
- for \(j = 1, \dots, k\): \(\bar K_j \leftarrow \sum_t E_{jt}\, \mathbf{k}_t\) // (98.11), \(2nd\) FLOPs per row
- for \(j = 1, \dots, k\): \(\bar V_j \leftarrow \sum_t F_{jt}\, \mathbf{v}_t\) // \(2nd\) FLOPs per row
- for \(i = 1, \dots, n\): \(s_{ij} \leftarrow \mathbf{q}_i \cdot \bar K_j / \sqrt{d},\ j = 1, \dots, k\) // \(2kd\) FLOPs
- \(\bar P_i \leftarrow \softmax(s_i)\) // one row of the \(n \times k\) matrix
- \(\mathbf{o}_i \leftarrow \sum_j \bar P_{ij}\, \bar V_j\) // \(2kd\) FLOPs
How to read Figure 2
Step 1 shades the whole \(8 \times 8\) grid: that is what full attention would compute. Steps 2 to 4 build the three summary keys. With mean pooling, \(\bar K_1\) is the average of keys 1 to 3: (0.01, 0.61). The thick outlines on the left show which keys feed the current row, and line 1 of the code lights up. Steps 5 to 7 do the same for the values. Then each token computes only 3 scores (the grid row fills in) and one output row. Token 1 puts weights (0.337, 0.303, 0.360) on the 3 summaries. At the end the counter reads 384 FLOPs and 24 scores, against 512 FLOPs and 64 scores for full attention, so \(n/(2k) = 1.33\). Try \(n = 4, k = 3\): Linformer needs 192 FLOPs, more than the 128 of full attention, because \(n \lt 2k\). The last step also compares with exact attention. With this untrained pooling \(E\) the relative output error is 0.419 for \(n = 8, k = 3\); with the random \(E\) it is 2.517. A real Linformer learns \(E\) and \(F\) so that this error is small on its data.
Full attention: \(4 \times 4096^2 \times 64 = 4.29 \times 10^9\) FLOPs, and a score matrix of \(4096^2 = 16.8\) million entries (32 MiB in FP16).
Linformer: \(8 \times 4096 \times 256 \times 64 = 5.37 \times 10^8\) FLOPs, which is \(n/(2k) = 8\) times less, and a score matrix of \(4096 \times 256 = 1.05\) million entries (2 MiB), which is \(n/k = 16\) times less.
New parameters: \(E\) and \(F\) have \(256 \times 4096 = 1{,}048{,}576\) entries each. In a 12-layer, 12-head model without sharing that would be 288 such matrices. Linformer tried three kinds of sharing: headwise (one \(E\) and one \(F\) per layer: 24 matrices), key-value (\(E = F\) per layer: 12) and layerwise (one matrix for the whole model: 1). Even layerwise sharing gave almost the same validation perplexity. [Certain]
Figure 3 lets you move \(n\) and \(k\) and compare the theory with what Linformer measured on a V100 GPU.
How to read Figure 3
The orange line has slope 2 (it grows like \(n^2\)), the blue line has slope 1. They cross at \(n = 2k\); to the right, Linformer is cheaper. Compare the two speed-ups in the readout. At \(n = 65{,}536\) and \(k = 128\) the attention FLOPs drop 256 times, but the measured model is “only” 20 times faster, because the linear layers and the FFN do not get cheaper. The measured memory saving (60×) is larger than the time saving, because memory decides how large a batch fits.
What the experiments showed
Linformer pretrained masked language models (the RoBERTa recipe on BookCorpus plus English Wikipedia, 250k updates on 64 V100 GPUs). With \(n = 512, k = 128\) and \(n = 1024, k = 256\), validation perplexity was “nearly on par” with the standard Transformer. When they grew \(n\) from 512 to 4096 with \(k = 256\) fixed, the final perplexity stayed about the same. [Certain] On four fine-tuning tasks (SST-2, IMDB, QNLI, QQP), the average accuracy was:
| Model (\(n = 512\)) | Average of 4 tasks |
|---|---|
| RoBERTa-base (same corpus as BERT) | 92.25 |
| Linformer, \(k = 128\) | 91.75 |
| Linformer, \(k = 256\) | 92.08 |
| Linformer, \(k = 256\), one shared matrix for the whole model | 92.30 |
All numbers are from Linformer’s Table 2. [Certain] Two cautions. These are short-sequence, bidirectional encoder tasks, where low rank is easiest. And on the Long Range Arena benchmark (Tay et al.), whose tasks have 1K to 8K tokens, Linformer’s average was 51.36 against 54.39 for the standard Transformer, as reported in the Luna paper’s Table 1. [Certain]
Other ways to shrink n to k
The projection does not have to be a learned matrix. Linformer mentions mean or max pooling and a strided convolution with kernel and stride \(n/k\). [Certain] Pooling has one big advantage: it has no parameters that depend on \(n\), so it works for any length. It also has a clear meaning: summary \(j\) is the average of tokens \(j \cdot n/k\) to \((j+1) \cdot n/k - 1\). Nyströmformer (Xiong et al., 2021) builds the low-rank form in another way, from a few “landmark” rows and columns of the attention matrix (the Nyström method). [Certain] Linformer also suggests a non-uniform \(k\): a smaller \(k\) in higher layers, where the spectrum falls faster.
- input: \(X \in \R^{n \times d_{\text{model}}}\); weights \(W^Q_h, W^K_h, W^V_h\) per head, \(W^O\); projections \(E, F \in \R^{k \times n_{\max}}\) (shared by heads)
- for each head \(h\):
- \(Q, K, V \leftarrow X W^Q_h,\ X W^K_h,\ X W^V_h\) // each \(n \times d\)
- \(\bar K \leftarrow E_{[:, :n]}\, K\), \(\;\bar V \leftarrow F_{[:, :n]}\, V\) // \(k \times d\) summaries, cost \(4knd\)
- \(\bar P \leftarrow \softmax(Q \bar K^\top / \sqrt{d})\) // \(n \times k\), never \(n \times n\)
- \(O_h \leftarrow \bar P\, \bar V\) // \(n \times d\)
- return \(\operatorname{concat}_h(O_h)\, W^O\) // padding positions must be zeroed in \(K\) and \(V\) before the projection
Set Transformer and Luna: pack, then unpack
Linformer’s summaries are built with fixed weights \(E\). The weight of token 17 in summary 3 is the same for every input. A more flexible way is to let the summaries choose what to read, using attention itself.
Take \(l\) learned vectors, stacked in \(P_{\text{q}} \in \R^{l \times d}\) (for example \(l = 16\)). Use them as queries that attend over the \(n\) tokens. The output is \(l\) vectors that summarize the sequence. Then let every token attend over those \(l\) summaries. Luna calls these two steps pack and unpack:
- Read the symbols
- \(\operatorname{Attn}(A, C)\)
- ordinary softmax attention with queries from \(A\) and keys and values from \(C\) (each with its own learned projections)
- \(P_{\text{q}}\)
- the \(l\) learned query vectors (Luna writes \(P\); we add “q” so it is not confused with the attention matrix)
- \(Y_P\)
- the packed context: \(l\) summary vectors, each a softmax-weighted average of token values
- \(Y_X\)
- the output, one row per token, as in full attention
Both steps are normal attention, so both are exact softmax operations; only the route is different. Information goes from token \(j\) to token \(i\) through the \(l\) summaries. Written as one matrix, the effective token-to-token weights are \(A_{\text{unpack}} A_{\text{pack}}\), an \(n \times l\) times \(l \times n\) product, so its rank is at most \(l\). This is low-rank attention again, but now the factors depend on the content of the input.
Figure 4 steps through a tiny example with real numbers.
How to read Figure 4
Step 1 shows the tokens and the two learned queries. In the pack step, each learned query spreads weight 1 over the 8 tokens (the thick lines are where it looks). The two packed summaries are weighted averages of the token values. In the unpack step, every token spreads weight 1 over only 2 summaries. The last step multiplies the two weight matrices and shows the effective 8 × 8 attention: every row still sums to 1, but its rank is at most 2.
Set Transformer: inducing points
The Set Transformer was built for inputs that are sets (point clouds, a bag of image features), where the order of the items must not matter. Its basic block is the multihead attention block \(\operatorname{MAB}(X, Y) = \operatorname{LayerNorm}(H + \operatorname{rFF}(H))\) with \(H = \operatorname{LayerNorm}(X + \operatorname{Multihead}(X, Y, Y))\), where rFF is a row-wise feed-forward layer. Full self-attention on a set is \(\operatorname{SAB}(X) = \operatorname{MAB}(X, X)\), which costs \(O(n^2)\). The induced set attention block uses \(m\) learned inducing points \(I \in \R^{m \times d}\):
This is exactly pack (98.7) and unpack (98.8), two years before Luna. The paper itself calls it “analogous to low-rank projection or autoencoder models”. [Certain] To get one fixed-size output for the whole set (for example for classification), the Set Transformer uses pooling by multihead attention with \(k\) learned seed vectors \(S\):
PMA is a pack step without an unpack. Remember it: it is the same shape of computation as the Q-Former and the Perceiver Resampler in VLMs, where a fixed number of learned queries cross-attends to a variable number of image or video features (session 178).
Luna: carry the summary from layer to layer
Luna adds one more idea. In the Set Transformer the inducing points are fixed parameters, the same for every input. In Luna, only the first layer starts from learned vectors (learned positional embeddings). Each layer outputs the packed context \(Y_P\) as a second output, and the next layer uses it as its \(P_{\text{q}}\). So the summary is contextual: it is refined layer by layer, like a small side memory. [Certain] Luna also shares \(W^Q\) and \(W^K\) inside each layer to save parameters, following Linformer.
Luna points out two advantages over Linformer. First, pack attention does not depend on \(n\), so sequences of any length work; Linformer’s \(E\) has a fixed number of columns. Second, the contextual summary is more expressive. [Certain] On Long Range Arena, Luna with \(l = 16\) averaged 61.46, against 59.24 for the authors’ re-run of the standard Transformer and 51.36 for Linformer. Luna-16 trained 1.2× to 5.5× faster than the Transformer (from 1K to 4K tokens) and used 10% of its peak memory at 4K. [Certain] Note that the authors trained the Retrieval task for 20K steps instead of 5K, while the other baselines come from Tay et al.; their re-run Transformer most likely used the longer setting too (its Retrieval score is 79.14 against 57.46 in Tay et al.). [Likely]
- input: tokens \(X \in \R^{n \times d}\), packed memory \(P_{\text{q}} \in \R^{l \times d}\) (learned for layer 1, the previous layer’s \(P'\) otherwise)
- \(Y_P \leftarrow \operatorname{Attn}(P_{\text{q}}, X)\) // pack: \(l\) queries over \(n\) tokens, \(O(lnd)\)
- \(Y_X \leftarrow \operatorname{Attn}(X, Y_P)\) // unpack: \(n\) queries over \(l\) summaries, \(O(nld)\)
- \(X_A \leftarrow \operatorname{LayerNorm}(Y_X + X)\), \(\;P' \leftarrow \operatorname{LayerNorm}(Y_P + P_{\text{q}})\)
- \(X' \leftarrow \operatorname{LayerNorm}(\operatorname{FFN}(X_A) + X_A)\) // FFN only on the token stream
- return \(X', P'\) // both go to the next layer
A cousin: Funnel-Transformer
The methods above keep \(n\) tokens and shorten only the keys and values. Funnel-Transformer gradually compresses the sequence of hidden states itself to a shorter one as it goes deeper, so later blocks run on fewer tokens, and a decoder can recover a representation for every token when a task needs one. [Certain] The compression is done by pooling along the sequence, and within a block the attention is still full, but over a shorter sequence. [Likely] This is the same bet (much of a long sequence is redundant), placed on the token axis instead of the key axis. The same idea appears in VLMs as visual token pooling or merging (session 206).
The limits: causal masking and variable length
Why causal masking breaks Linformer
A decoder LLM must not let token \(i\) see tokens after \(i\) (session 18). In full attention this is easy: set the scores for \(j \gt i\) to \(-\infty\). In Linformer there is no score per token pair. Token \(i\) attends to the summary rows, and summary row \(j\) is
a mix of all keys, including those of future tokens. There is no entry to mask. If we train a decoder this way, every token can read the future through the summaries, the training loss becomes easy, and generation fails because the future does not exist yet. Figure 5 shows the leak and runs the fix as a loop.
The fix is to give each position its own summary of the past only:
This is correct, and the right-hand form even looks attractive for decoding: the state has a fixed size \(k \times d\), updated once per new token, like a KV cache that never grows. But it has three costs. (1) Training needs a different \(\bar K^{(i)}\) for every \(i\): either \(n\) states of size \(k \times d\) in memory, or a sequential scan, which loses the parallelism of transformers. For \(n = 4096\), \(k = 256\), \(d = 64\) those states hold 67.1 million numbers per head, four times the 16.8 million entries of the full score matrix we wanted to avoid. (2) For small \(i\) the summary holds only a few tokens, while the projection was designed for \(n\). (3) The softmax runs over \(k\) mixed summaries, so a decoder cannot reliably pick out one exact earlier token, which is what copying and “needle in a haystack” retrieval need. [Likely] Pooled summaries have a simpler causal version: a query can use only the summaries of blocks that have fully ended, plus exact attention inside its own block.
Luna faces the same problem. It states that causal attention is “not straight-forward” in Luna, because the packed sequence mixes all positions. Its causal version replaces the softmax in the pack step with \(\operatorname{elu}(\cdot) + 1\) or softplus (a softmax would normalize over future positions), uses cumulative sums over the prefix, and needs sequential computation for each time step, like the linear attention of the next session. [Certain]
- \(\bar K \leftarrow 0\) // \(k \times d\) state
- for \(i = 1, \dots, n\):
- \(\bar K \leftarrow \bar K + E_{:,i}\, \mathbf{k}_i^\top\) // (98.12), adds column \(i\) only
- store \(\bar K^{(i)}\) // training needs all \(n\) states
- token \(i\) attends over the \(k\) rows of \(\bar K^{(i)}\)
How to read Figure 5
Press Play to run the loop of (98.12): each position takes two steps, first the update (line 3), then storing the state (lines 4 and 5). Each cell is one weight \(E_{jt}\); stronger color means larger \(|E_{jt}|\). With “Linformer” the learned weights are spread over all columns, so for any \(i \lt 12\) a large share of the summary comes from the future. With “Mean pooling” each summary covers 3 tokens; only the summaries of finished blocks are safe. With “Causal fix”, the columns after \(i\) are zeroed, as in (98.12): no leak, but a new state is needed for every position, and the readout counts what that costs to store during training. The bottom row is the same in all three modes: it is the past-only state. At \(i = 5\) with the learned \(E\), it is still far from \(EK\) (relative distance 1.024), and 72.6% of the \(|E|\) weight comes from the future. The distance only reaches 0 at \(i = 12\). That gap is exactly what a decoder would leak if it used \(EK\). With mean pooling at \(i = 5\), summary 1 (tokens 1 to 3) is finished and already equals row 1 of \(EK\), (0.136, −0.775).
Why variable lengths are awkward
\(E\) has a fixed number of columns \(n_{\max}\). A shorter input must be padded and the padding keys and values must be set to zero before the projection, or the summaries absorb padding. In practice one uses only the first \(n\) columns, \(E_{[:, :n]}\). Then the summary for a 100-token input is built from weights that were trained to cover 4,096 positions, and its scale changes with \(n\). A longer input than \(n_{\max}\) cannot be processed at all without new weights. [Likely] Pooling (window \(n/k\)) or pack attention (Luna, Set Transformer) avoids this, which is one reason the pack idea survived and the fixed \(E\) did not.
And the KV cache?
For inference, the main pain of decoder LLMs at long context is the KV cache read in every decode step (session 80). Full attention keeps all \(n\) keys and values so that any one of them can be retrieved exactly later. A low-rank method keeps a fixed \(k\)-row summary and accepts that some details are lost. That is a real trade: you gain a constant-size state, and you lose exact recall. Today’s LLMs mostly prefer to shrink the cache in other ways (GQA and MLA in session 97, sparse and windowed attention in session 116) and keep exact softmax attention, computed with FlashAttention. [Likely] Low-rank and pack-style attention stay popular where the input is long but the output is short and bidirectional: encoders, perception and vision-language connectors.
Runnable code
A multi-head Linformer layer, a pack/unpack layer, and two checks: with \(k = n\) and \(E = F = I\) Linformer must equal full attention exactly, and pack/unpack must accept any length. The last block measures the best rank-\(r\) error (98.3) of a random softmax matrix.
import math, torch, torch.nn as nn, torch.nn.functional as F torch.manual_seed(0) class LinformerSelfAttention(nn.Module): """Multi-head Linformer attention, formula (98.5). One E and one F per layer (headwise sharing).""" def __init__(self, d_model, n_heads, max_len, k): super().__init__() self.h, self.dh = n_heads, d_model // n_heads self.qkv = nn.Linear(d_model, 3 * d_model) self.out = nn.Linear(d_model, d_model) self.E = nn.Parameter(torch.randn(k, max_len) / math.sqrt(k)) # projects keys: n to k self.F = nn.Parameter(torch.randn(k, max_len) / math.sqrt(k)) # projects values: n to k def forward(self, x): # x: (B, n, d_model), n at most max_len B, n, _ = x.shape q, k, v = self.qkv(x).view(B, n, 3, self.h, self.dh).permute(2, 0, 3, 1, 4) # each (B, h, n, dh) k = torch.einsum("jn,bhnd->bhjd", self.E[:, :n], k) # (B, h, k, dh) v = torch.einsum("jn,bhnd->bhjd", self.F[:, :n], v) # (B, h, k, dh) o = F.scaled_dot_product_attention(q, k, v) # scores are (n x k), not (n x n) return self.out(o.transpose(1, 2).reshape(B, n, -1)) def attn(q, k, v): # plain softmax attention, formula (98.1) return torch.softmax(q @ k.transpose(-1, -2) / math.sqrt(q.shape[-1]), -1) @ v class PackUnpack(nn.Module): """Luna / Set Transformer (ISAB) idea, formulas (98.7)-(98.9), single head, no FFN.""" def __init__(self, d, l): super().__init__() self.P = nn.Parameter(torch.randn(l, d)) # l learned queries (inducing points) self.q1, self.k1, self.v1 = nn.Linear(d, d), nn.Linear(d, d), nn.Linear(d, d) self.q2, self.k2, self.v2 = nn.Linear(d, d), nn.Linear(d, d), nn.Linear(d, d) def forward(self, x): # x: (B, n, d), any n P = self.P.expand(x.shape[0], -1, -1) Yp = attn(self.q1(P), self.k1(x), self.v1(x)) # pack: (B, l, d), cost O(l n d) Yx = attn(self.q2(x), self.k2(Yp), self.v2(Yp)) # unpack: (B, n, d), cost O(n l d) return Yx, Yp # 1) sanity check: with k = n and E = F = identity, Linformer is exactly full attention n, d = 16, 32 m = LinformerSelfAttention(d, n_heads=4, max_len=n, k=n) with torch.no_grad(): m.E.copy_(torch.eye(n)); m.F.copy_(torch.eye(n)) x = torch.randn(2, n, d) q, k, v = m.qkv(x).view(2, n, 3, 4, 8).permute(2, 0, 3, 1, 4) full = m.out(attn(q, k, v).transpose(1, 2).reshape(2, n, d)) print("k = n, E = I, max diff:", (m(x) - full).abs().max().item() < 1e-5) # True # 2) shapes and the size of the score matrix m = LinformerSelfAttention(d_model=512, n_heads=8, max_len=4096, k=256) x = torch.randn(1, 4096, 512) print(m(x).shape, "scores per head:", 4096 * 256, "instead of", 4096 * 4096) # 3) pack/unpack works for any length, because no weight depends on n pu = PackUnpack(d=64, l=16) for n in (100, 1000): Yx, Yp = pu(torch.randn(1, n, 64)) print(n, tuple(Yx.shape), tuple(Yp.shape)) # (1, n, 64) (1, 16, 64) # 4) best rank-r error of a random softmax matrix (Eckart-Young, formula 98.3) Q, K = torch.randn(512, 64), torch.randn(512, 64) P = torch.softmax(Q @ K.T / 8, -1) s = torch.linalg.svdvals(P) for r in (16, 64, 128): err = (s[r:] ** 2).sum().sqrt() / (s ** 2).sum().sqrt() print(f"rank {r}: relative error {err:.3f}") # about 0.670, 0.425, 0.291
Look at the last result. Attention between random 64-dimensional queries and keys is not very low rank: even rank 128 of 512 leaves an error of about 0.29. The low-rank property Linformer reports belongs to trained models, whose attention has structure. Always measure it on your own model before you rely on it.
Where this is used
| Setting | Which idea | Why it fits |
|---|---|---|
| Long-document encoders (classification, retrieval embeddings) | Linformer or pooling of \(K\) and \(V\) | Bidirectional, fixed maximum length, one output per document; no causal mask needed |
| Point clouds, sets of detections, multi-instance learning | Set Transformer (ISAB, PMA) | Order must not matter; set sizes vary; \(O(nm)\) instead of \(O(n^2)\) |
| Perception over huge inputs (Perceiver) | A small latent array cross-attends to the input | A 224 × 224 image has \(M = 50{,}176\) pixels; full self-attention over it is too expensive [Certain] |
| VLM connectors (BLIP-2 Q-Former, Flamingo Perceiver Resampler) | PMA-style pack: learned queries read image features | Fixed visual budget for the LLM: 32 query vectors in BLIP-2, 64 visual tokens in Flamingo [Certain] |
| Video classification and action recognition | Pack thousands of frame-patch tokens into a few latents, then classify | The input grows with frames; the output is one label [Likely] |
| Video retrieval and Video-RAG indexing | Pack each clip into a fixed number of vectors | Every clip costs the same to store and compare, whatever its length [Likely] |
| Key-moment detection and video segmentation | Pack, then unpack back to every frame or patch (ISAB, Luna) | Needs an output per time step, but global context can go through a small summary [Likely] |
| Decoder-only LLMs at long context | Rarely used; GQA/MLA, sparse attention and FlashAttention instead | Causal masking, variable lengths and exact recall (see the limits above) [Likely] |
Common mistakes
- Using Linformer in a decoder without a causal fix. The summaries (98.11) mix future tokens. Training loss looks great; generation is broken.
- Forgetting to zero padding before the projection. Masking padding in the scores is not enough, because there are no per-token scores: padded keys and values are already mixed into \(EK\) and \(FV\).
- Expecting fewer FLOPs at short length. The FLOPs only drop when \(n \gt 2k\) (98.6). At \(n = 512\), \(k = 256\) the attention math is the same as full attention. (Linformer still measured 1.3× there, probably because the smaller score matrix lets a larger batch fit. [Likely])
- Comparing attention FLOPs and calling it model speed. The FFN and projections are unchanged; Linformer’s measured 20× at 64K tokens is far below the 256× drop in attention FLOPs.
- Assuming low rank without measuring. Local, copying and induction heads are close to full rank (Figure 1, “Local”). Check the spectrum of your own model, per layer.
- Thinking FlashAttention and Linformer solve the same problem. FlashAttention gives the exact result with less memory traffic but the same \(n^2\) FLOPs; Linformer changes the result to reduce FLOPs.
- Feeding a longer sequence than \(n_{\max}\). \(E\) has no columns for it. Use pooling or pack attention if lengths vary a lot.
Interview questions
How does Linformer reach linear complexity in sequence length?basic
Is the attention matrix low rank? Give an argument for and against.core
Why can’t you drop Linformer into a GPT-style decoder?core
Linformer vs Luna: what does Luna change?core
What is an ISAB in the Set Transformer, and what is its cost?basic
What do Q-Former, the Perceiver Resampler and PMA have in common?core
Linformer’s theorem gives \(k = 5\ln n/(\varepsilon^2 - \varepsilon^3)\). Is that a useful number in practice?advanced
You measure Linformer at 64K tokens: attention FLOPs are 256× lower, but the model is only 20× faster. Why?advanced
How would you choose \(k\) per layer?advanced
FlashAttention or Linformer for a 16K-token encoder?core
Why does mean pooling of \(K\) and \(V\) have an easier causal version than a learned \(E\)?advanced
Exercises
- For \(n = 8192\), \(d = 128\) and \(k = 512\), compute the attention FLOPs per head of full attention and of Linformer, and the FLOP ratio.
- Below which sequence length is Linformer with \(k = 128\) more expensive (in attention FLOPs) than full attention?
- A model has 24 layers and 16 heads. How many \(E\) and \(F\) matrices does it have with no sharing, headwise sharing, key-value sharing and layerwise sharing?
- In Figure 1, find the smallest \(r\) that gives a relative error below 0.1 for “Content” at \(\beta = 0.5\). Then switch to “Local” with the same \(\beta\). What changes, and why?
- Pack/unpack with \(l = 16\) on \(n = 4096\), \(d = 64\): estimate the attention FLOPs of one layer (both steps, ignoring the linear projections), and compare with full attention.
- Show that the effective token-to-token matrix \(A_{\text{unpack}}A_{\text{pack}}\) of pack/unpack has rows that sum to 1.
Answerscheck
Key takeaways
- Full attention costs \(4n^2d\) FLOPs and an \(n \times n\) matrix per head (98.1). If \(P\) is close to rank \(k\), the SVD (98.2) and Eckart–Young (98.3) say a rank-\(k\) form loses little.
- Trained attention is often low rank (long-tail spectrum, more so in higher layers), but sharp local and copying heads are not. Measure before you rely on it.
- Linformer projects \(K\) and \(V\) from \(n\) to \(k\) with learned \(E, F\) (98.5): \(8nkd\) FLOPs, a ratio of \(n/(2k)\), and \(n/k\) less score memory (98.6). One shared matrix for the whole model works almost as well.
- Set Transformer (ISAB, PMA) and Luna use \(l\) learned queries: pack the sequence into \(l\) summaries, then unpack (98.7 to 98.10). Nothing depends on \(n\), and Luna keeps the summary contextual across layers.
- Limits: summaries mix future tokens (98.11), so causal decoding needs per-prefix states (98.12) and loses parallelism; fixed \(E\) ties the model to one length; a fixed summary cannot do exact recall. That is why decoder LLMs rarely use these methods, while VLM connectors use pack everywhere.
Key formulas
References for this session
- Wang et al. (2020). Linformer: Self-Attention with Linear Complexity
- Ma et al. (2021). Luna: Linear Unified Nested Attention
- Lee et al. (2018). Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks
- Dai et al. (2020). Funnel-Transformer: Filtering out Sequential Redundancy for Efficient Language Processing
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Wang et al. (2020). Linformer: Self-Attention with Linear Complexity
- Ma et al. (2021). Luna: Linear Unified Nested Attention
- Lee et al. (2018). Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks
- Dai et al. (2020). Funnel-Transformer: Filtering out Sequential Redundancy for Efficient Language Processing
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Jaegle et al. (2021). Perceiver: General Perception with Iterative Attention
- Li et al. (2023). BLIP-2: Bootstrapping Language-Image Pre-training with Frozen Image Encoders and Large Language Models
- Alayrac et al. (2022). Flamingo: a Visual Language Model for Few-Shot Learning
- Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
- Tay et al. (2020). Long Range Arena: A Benchmark for Efficient Transformers
- Xiong et al. (2021). Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention