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.

12 min read797 wordsadvanced0 viewsupdated 2026-10-12

Definition

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

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=softmax(QK⊤/d)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 PP is close to low-rank, storing all n2n^2 entries wastes memory. A rank-kk factorisation should suffice.

Projecting along the sequence

headi=softmax ⁣(QWiQ (EiKWiK)⊤dk)⏟Pˉ ∈ Rn×k⋅FiVWiV⏟k×dk,Ei,Fi∈Rk×n\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}
EiKWiKE_iKW_i^K
kk projected keys; each one is a learned weighted mix of all nn original keys
FiVWiVF_iVW_i^V
kk projected values, mixed with FiF_i
Pˉ\bar P
n×kn\times k attention weights; each row still sums to 1, but over summaries, not tokens
kk
projected length, a fixed hyperparameter (e.g. 128 or 256 for n=512n=512 in the paper)

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

The low-rank argument

Thm 1:  ∃ P~, rank(P~)=Θ(log⁡n): Pr⁡ ⁣(∥P~w⊤−Pw⊤∥<ϵ∥Pw⊤∥)>1−o(1)Thm 2:  k=O ⁣(dlog⁡d/ϵ2) suffices\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}
PP
the full context-mapping matrix softmax(QK⊤/d)\mathrm{softmax}(QK^\top/\sqrt d)
ww
any column vector, e.g. a column of VV
Thm 1\text{Thm 1}
a Johnson–Lindenstrauss argument: a random projection of rank Θ(log⁡n)\Theta(\log n) preserves PwPw up to 1±ϵ1\pm\epsilon with high probability
Thm 2\text{Thm 2}
there exist E,FE,F such that the Linformer head is within ϵ\epsilon of the full head with a kk that depends on dd, not on nn

Theorem 1 is about PP itself. Its proof uses a random projection, but computing PR⊤RPR^\top R would still need PP, so it says nothing yet about speed. Theorem 2 moves the projection inside the softmax, onto KK and VV, which is what gives the linear cost. Both are existence statements. In the model, EE and FF 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/kn/k.

Setup in the paper

Pretraining
masked-language-model pretraining as in RoBERTa (BookCorpus + English Wikipedia), n=512n=512, k∈{64,128,256}k\in\{64,128,256\}; validation perplexity close to the standard Transformer, closer as kk grows
Parameter sharing
separate Ei,FiE_i,F_i per head; headwise (one E,FE,F per layer); key–value (E=FE=F per layer); layerwise (one matrix for all layers and heads); even layerwise sharing kept perplexity close
Longer inputs
with nn increased and kk fixed, perplexity after convergence stayed about the same, consistent with kk not needing to grow with nn
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 kk
P = softmax(QKᵀ/√d) (n×n) → P̄ = softmax(Q(EK)ᵀ/√d) (n×k), output P̄·FVfull P (32×32), d = 8Linformer P̄ (32×8)scores stored: 1024 → 256 (25%) · shade ∝ √weightsingular values σᵢ of Pσ₁ 1.283σ8 0.375energy top 8 92.1%rank-8 ‖P−Pₖ‖/‖P‖ 0.281relative output error ‖PV − P̄FV‖ / ‖PV‖ vs k0.00.51.01.518162432random E (clipped at 1.5)mean-pool EP → best rank-k Pₖ (SVD)projected length kk 8Linformer err 0.304SVD rank-k err 0.138 n = 4096, k = 256 scores n² 16.8Mscores nk 1.0MFLOPs ratio 8.0×blue: PₖV with Pₖ the truncated SVD of P · a trained Linformer learns E and F
projection E = F
fig.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)q=(1,\,0.5), d=2d=2. Keys K1=(1,0)K_1=(1,0), K2=(0.8,0.2)K_2=(0.8,0.2), K3=(−0.5,1)K_3=(-0.5,1), K4=(−0.7,0.9)K_4=(-0.7,0.9), values V1=(1,0)V_1=(1,0), V2=(1,0.2)V_2=(1,0.2), V3=(0,1)V_3=(0,1), V4=(0.2,1)V_4=(0.2,1). Neighbouring tokens are similar, as in the figure. Take E=F=(0.50.500000.50.5)E=F=\begin{pmatrix}0.5&0.5&0&0\\0&0&0.5&0.5\end{pmatrix} (pool pairs).

attentionkeys attendedscores qᵀk/√2weightsoutput
full PK₁ … K₄0.7071, 0.6364, 0.0000, −0.17680.3524, 0.3283, 0.1737, 0.1456(0.7098, 0.3850)
LinformerEK = (0.9, 0.1), (−0.6, 0.95)0.6718, −0.08840.6814, 0.3186(0.7132, 0.3868)
Full attention vs Linformer for one query (checked numerically in Node)

What happened

  1. 1EKEK averages keys 1–2 and 3–4, and FVFV averages the values: (1, 0.1)(1,\,0.1) and (0.1, 1)(0.1,\,1).
  2. 2Softmax over the two summaries gives (0.6814, 0.3186)(0.6814,\,0.3186). Summing the full weights over the same pairs gives (0.6807, 0.3193)(0.6807,\,0.3193): the summaries received almost the right total mass.
  3. 3Output 0.6814 (1,0.1)+0.3186 (0.1,1)=(0.7132, 0.3868)0.6814\,(1,0.1)+0.3186\,(0.1,1)=(0.7132,\,0.3868), against (0.7098, 0.3850)(0.7098,\,0.3850) for full attention: relative error 0.48%0.48\%. Two scores replaced four.
  4. 4The approximation is good because the keys and values inside each pooled block are similar. If K1K_1 and K2K_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 EE and FF.
python
1import torch, torch.nn as nn
2
3class LinformerSelfAttention(nn.Module):
4 def __init__(self, d_model, n_heads, seq_len, k, share_kv=False):
5 super().__init__()
6 self.h, self.dh = n_heads, d_model // n_heads
7 self.qkv = nn.Linear(d_model, 3 * d_model)
8 self.out = nn.Linear(d_model, d_model)
9 self.E = nn.Parameter(torch.randn(k, seq_len) / k ** 0.5) # sequence projection n -> k for keys
10 self.F = self.E if share_kv else nn.Parameter(torch.randn(k, seq_len) / k ** 0.5)
11
12 def forward(self, x): # x: (B, n, d_model), n == seq_len
13 B, n, _ = x.shape
14 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)
15 k = torch.einsum("kn,bhnd->bhkd", self.E, k) # (B, h, k, dh) k summaries of n keys
16 v = torch.einsum("kn,bhnd->bhkd", self.F, v) # (B, h, k, dh)
17 att = (q @ k.transpose(-1, -2) / self.dh ** 0.5).softmax(-1) # (B, h, n, k), not (B, h, n, n)
18 y = (att @ v).transpose(1, 2).reshape(B, n, -1) # (B, n, d_model)
19 return self.out(y), att
20
21layer = LinformerSelfAttention(d_model=768, n_heads=12, seq_len=512, k=128)
22y, att = layer(torch.randn(2, 512, 768))
23print(y.shape, att.shape) # torch.Size([2, 512, 768]) torch.Size([2, 12, 512, 128])
24print(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

Use when

  • +O(nk)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 EE and FF across heads and layers costs almost no quality and few parameters

Avoid when

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

Check yourself

In Linformer, which dimension do E and F reduce?

Check yourself

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

Remember

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