# Linformer

> Linformer (Wang et al., 2020) observes that the n×n attention matrix is approximately low-rank. It projects keys and values along the sequence axis with learned k×n matrices E and F, so attention is softmax(Q(EK)ᵀ/√d)·FV: n×k scores, O(nk) time and memory, but not causal.

Source: https://www.mlfoundry.in/learn/linformer  
Section: Deep Learning › Attention and Transformer Architectures  
Level: advanced · 12 min read · updated 2026-10-12

**Linformer:** is a self-attention layer that compresses the **sequence** dimension of the keys and values before attending. Learned matrices $E,F\in\mathbb R^{k\times n}$ map the $n$ keys and values to $k\ll n$ rows. Each query then attends over $k$ mixed "summary" keys: $\mathrm{softmax}\big(Q(EK)^\top/\sqrt d\big)(FV)$. The score matrix is $n\times k$ instead of $n\times n$, so time and memory are $O(nk)$, linear in $n$ for a fixed $k$.

Sinong Wang, Belinda Li, Madian Khabsa, Han Fang and Hao Ma (Facebook AI) proposed it in "Linformer: Self-Attention with Linear Complexity" (arXiv 2020). The argument starts from an observation about trained models. They took the context-mapping matrix $P=\mathrm{softmax}(QK^\top/\sqrt d)$ from pretrained RoBERTa and computed its singular values. The normalised cumulative spectrum rises steeply: most of the mass is in the first few singular values of 512, followed by a long tail. Higher layers were more concentrated still. If $P$ is close to low-rank, storing all $n^2$ entries wastes memory. A rank-$k$ factorisation should suffice.

## Projecting along the sequence

$$
\mathrm{head}_i=\underbrace{\mathrm{softmax}\!\left(\frac{QW_i^Q\,\big(E_iKW_i^K\big)^\top}{\sqrt{d_k}}\right)}_{\bar P\ \in\ \mathbb R^{n\times k}}\cdot\underbrace{F_iVW_i^V}_{k\times d_k},\qquad E_i,F_i\in\mathbb R^{k\times n}
$$

- $E_iKW_i^K$: $k$ projected keys; each one is a learned weighted mix of all $n$ original keys
- $F_iVW_i^V$: $k$ projected values, mixed with $F_i$
- $\bar P$: $n\times k$ attention weights; each row still sums to 1, but over summaries, not tokens
- $k$: projected length, a fixed hyperparameter (e.g. 128 or 256 for $n=512$ in the paper)

The projection acts on the **sequence** axis ($n\to k$), not on the feature axis. That is the difference from the usual $W^K,W^V$, which act on $d$. Seen from the full model, the layer computes $\bar P(FV)=(\bar PF)V$, where $\bar PF$ is an $n\times n$ matrix of rank at most $k$. Linformer is standard attention with a learned low-rank attention matrix that is never formed. Projecting $K$ and $V$ costs $2knd$ multiply–adds, and the attention itself $2nkd$. The total is $O(nkd)$ against $O(n^2d)$. At $n=4096$ and $k=256$ the score matrix shrinks 16× (16.8M → 1.0M entries) and the FLOPs 8×.

## The low-rank argument

$$
\textbf{Thm 1: }\ \exists\,\tilde P,\ \mathrm{rank}(\tilde P)=\Theta(\log n):\ \Pr\!\big(\lVert\tilde Pw^\top-Pw^\top\rVert<\epsilon\lVert Pw^\top\rVert\big)>1-o(1)\qquad\textbf{Thm 2: }\ k=O\!\big(d\log d/\epsilon^2\big)\ \text{suffices}
$$

- $P$: the full context-mapping matrix $\mathrm{softmax}(QK^\top/\sqrt d)$
- $w$: any column vector, e.g. a column of $V$
- $\text{Thm 1}$: a Johnson–Lindenstrauss argument: a random projection of rank $\Theta(\log n)$ preserves $Pw$ up to $1\pm\epsilon$ with high probability
- $\text{Thm 2}$: there exist $E,F$ such that the Linformer head is within $\epsilon$ of the full head with a $k$ that depends on $d$, not on $n$

Theorem 1 is about $P$ itself. Its proof uses a random projection, but computing $PR^\top R$ would still need $P$, so it says nothing yet about speed. Theorem 2 moves the projection inside the softmax, onto $K$ and $V$, which is what gives the linear cost. Both are existence statements. In the model, $E$ and $F$ are **learned** parameters. The figure shows that an untrained random projection placed inside the softmax does not work. The paper also tries structured alternatives with the same shape, such as mean or max pooling and strided convolutions with kernel and stride $n/k$.

**Setup in the paper**

- **Pretraining:** masked-language-model pretraining as in RoBERTa (BookCorpus + English Wikipedia), $n=512$, $k\in\{64,128,256\}$; validation perplexity close to the standard Transformer, closer as $k$ grows
- **Parameter sharing:** separate $E_i,F_i$ per head; **headwise** (one $E,F$ per layer); **key–value** ($E=F$ per layer); **layerwise** (one matrix for all layers and heads); even layerwise sharing kept perplexity close
- **Longer inputs:** with $n$ increased and $k$ fixed, perplexity after convergence stayed about the same, consistent with $k$ not needing to grow with $n$
- **Downstream:** fine-tuned on IMDB, SST-2, QNLI and QQP; results comparable to RoBERTa-base
- **Non-uniform k:** higher layers, whose spectra are more concentrated, can use smaller $k$

> Figure: A 32-token head with d = 8. Keys and values drift slowly along the sequence (neighbours are similar), queries are random. Left: the full 32×32 attention matrix P. Middle: Linformer's 32×k matrix P̄ when E = F mean-pools contiguous segments. Top right: the singular values of P. The first 8 hold 92.1% of the energy (σ₁ = 1.283, σ₈ = 0.375), and the first 16 hold 99.3%. Bottom: relative output error ‖PV − P̄FV‖/‖PV‖ against k. At the default k = 8, mean pooling stores 256 scores instead of 1024 and has error 0.304. Replacing P by its best rank-8 approximation gives 0.138. At k = 16 the errors are 0.171 and 0.048. The pooling curve is not monotone (0.208 at k = 24) because the segments become uneven. An untrained random Gaussian E (rose) is worse than outputting zero at every k: its error never falls below 1.386 for this draw. Projected keys are signed random mixtures, so the softmax over them means nothing, and this is why E and F are learned. The readout below scales up: at n = 4096 with the paper's k = 256 the score matrix has 16.8M → 1.0M entries and FLOPs fall 8× (n/2k). At n = 512 the FLOPs are equal.

## Worked example: n = 4, k = 2 with mean pooling

One query $q=(1,\,0.5)$, $d=2$. Keys $K_1=(1,0)$, $K_2=(0.8,0.2)$, $K_3=(-0.5,1)$, $K_4=(-0.7,0.9)$, values $V_1=(1,0)$, $V_2=(1,0.2)$, $V_3=(0,1)$, $V_4=(0.2,1)$. Neighbouring tokens are similar, as in the figure. Take $E=F=\begin{pmatrix}0.5&0.5&0&0\\0&0&0.5&0.5\end{pmatrix}$ (pool pairs).

Full attention vs Linformer for one query (checked numerically in Node)

| attention | keys attended | scores qᵀk/√2 | weights | output |
| --- | --- | --- | --- | --- |
| full P | K₁ … K₄ | 0.7071, 0.6364, 0.0000, −0.1768 | 0.3524, 0.3283, 0.1737, 0.1456 | (0.7098, 0.3850) |
| Linformer | EK = (0.9, 0.1), (−0.6, 0.95) | 0.6718, −0.0884 | 0.6814, 0.3186 | (0.7132, 0.3868) |

**What happened**

1. $EK$ averages keys 1–2 and 3–4, and $FV$ averages the values: $(1,\,0.1)$ and $(0.1,\,1)$.
2. Softmax over the two summaries gives $(0.6814,\,0.3186)$. Summing the full weights over the same pairs gives $(0.6807,\,0.3193)$: the summaries received almost the right total mass.
3. Output $0.6814\,(1,0.1)+0.3186\,(0.1,1)=(0.7132,\,0.3868)$, against $(0.7098,\,0.3850)$ for full attention: relative error $0.48\%$. Two scores replaced four.
4. The approximation is good because the keys and values inside each pooled block are similar. If $K_1$ and $K_2$ pointed in opposite directions, their average would match the query poorly, and the block would lose mass it deserves. That is the job of learned $E$ and $F$.

```python
import torch, torch.nn as nn

class LinformerSelfAttention(nn.Module):
    def __init__(self, d_model, n_heads, seq_len, k, share_kv=False):
        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, seq_len) / k ** 0.5)          # sequence projection n -> k for keys
        self.F = self.E if share_kv else nn.Parameter(torch.randn(k, seq_len) / k ** 0.5)

    def forward(self, x):                                   # x: (B, n, d_model), n == seq_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("kn,bhnd->bhkd", self.E, k)        # (B, h, k, dh)  k summaries of n keys
        v = torch.einsum("kn,bhnd->bhkd", self.F, v)        # (B, h, k, dh)
        att = (q @ k.transpose(-1, -2) / self.dh ** 0.5).softmax(-1)   # (B, h, n, k), not (B, h, n, n)
        y = (att @ v).transpose(1, 2).reshape(B, n, -1)     # (B, n, d_model)
        return self.out(y), att

layer = LinformerSelfAttention(d_model=768, n_heads=12, seq_len=512, k=128)
y, att = layer(torch.randn(2, 512, 768))
print(y.shape, att.shape)       # torch.Size([2, 512, 768]) torch.Size([2, 12, 512, 128])
print(512 * 128 / 512 ** 2)     # 0.25: a quarter of the attention scores per head
```

Linformer self-attention (key–value sharing optional); the input length must equal seq_len

> **Not causal, so not for autoregressive decoding:** Every projected key $\sum_j E_{rj}K_j$ mixes **all** positions, including future ones. A causal mask (see **Causal attention**) cannot be applied after the projection, because no column of $\bar P$ belongs to a single position. So Linformer is an encoder-side layer. Using it in a decoder leaks future tokens unless $E$ is restricted, for example to the past, which removes most of the saving. For causal long-context models, look at **Linear attention**, **Sparse attention** or **Transformer-XL**.

> **Fixed maximum length and padding:** $E\in\mathbb R^{k\times n}$ is tied to one $n$. Shorter inputs must be padded to $n$ (or $E$ sliced), and padded positions must be zeroed in $K$ and $V$ **before** projection, because a key mask on $\bar P$ no longer makes sense. Longer inputs need a new $E$. Pooling or convolutional projections are less tied to one $n$ than a dense learned $E$.

> **Why learned E works when random E fails:** The output $PV$ is only $n\times d$, so it has rank at most $d$. A good $E$ needs to preserve only the directions of $P$ that matter for $V$, not all of $P$. Training finds those directions. A random Gaussian $E$ satisfies the JL lemma for vectors like $Pw$, but inside a softmax its signed, scaled mixtures of keys produce meaningless scores. Theorem 2 therefore guarantees that good $E,F$ exist, but not that a random draw is one of them.

**Strengths**

- $O(nk)$ time and memory with plain dense matrix products; no custom kernels, no hashing or sparsity patterns
- Keeps a real softmax over (summary) keys; drop-in for encoder self-attention
- Spectrum evidence: trained attention matrices are close to low-rank, more so in higher layers
- Sharing $E$ and $F$ across heads and layers costs almost no quality and few parameters

**Limitations**

- Not causal: unsuitable for autoregressive decoders as is
- Tied to a fixed sequence length $n$; padding and masking are awkward
- Saving is only $n/2k$ in FLOPs; no gain at $n=512,\ k=256$
- Low-rank mixing cannot represent sharp, token-specific patterns (copying, exact retrieval) as well as full attention

**Question:** In Linformer, which dimension do E and F reduce?

- A. The head dimension d_k of the keys and values
- B. The sequence dimension n of the keys and values, from n to k
- C. The number of heads
- D. The sequence dimension of the queries

**Answer:** B. The sequence dimension n of the keys and values, from n to k — $E,F\in\mathbb R^{k\times n}$ multiply $K,V\in\mathbb R^{n\times d}$ from the left, giving $k\times d$. Queries keep all $n$ rows, so the output still has one vector per token, and the score matrix is $n\times k$.

**Question:** Why can a standard causal mask not be used with Linformer?

- A. Because the softmax is applied over k instead of n
- B. Because each projected key is a mixture of keys from all positions, including future ones
- C. Because E and F are shared across heads
- D. Because Linformer has no queries

**Answer:** B. Because each projected key is a mixture of keys from all positions, including future ones — A causal mask hides key $j$ from query $i$ when $j>i$. After projection, column $r$ of $\bar P$ corresponds to $\sum_j E_{rj}K_j$, which mixes every $j$. There is no column to hide, so future information leaks.

**Key points**

- Linformer head: $\mathrm{softmax}\big(Q(EK)^\top/\sqrt d\big)\,(FV)$ with learned $E,F\in\mathbb R^{k\times n}$; scores are $n\times k$, cost $O(nkd)$ instead of $O(n^2d)$.
- Justification: trained attention matrices $P$ are close to low-rank; a rank-$\Theta(\log n)$ approximation exists (JL), and $k=O(d\log d/\epsilon^2)$ suffices independently of $n$.
- Equivalent to standard attention with the rank-$k$ matrix $\bar PF$, which is never formed.
- Projected keys mix all positions, so Linformer is not causal and is tied to a fixed maximum length.
- $E$ and $F$ are learned (or structured, e.g. pooling) and can be shared across heads and layers; untrained random projections do not work inside the softmax.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
