Definition
Linformer is a self-attention layer that compresses the sequence dimension of the keys and values before attending. Learned matrices map the keys and values to rows. Each query then attends over mixed "summary" keys: . The score matrix is instead of , so time and memory are , linear in for a fixed .
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 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 is close to low-rank, storing all entries wastes memory. A rank- factorisation should suffice.
Projecting along the sequence
- projected keys; each one is a learned weighted mix of all original keys
- projected values, mixed with
- attention weights; each row still sums to 1, but over summaries, not tokens
- projected length, a fixed hyperparameter (e.g. 128 or 256 for in the paper)
The projection acts on the sequence axis (), not on the feature axis. That is the difference from the usual , which act on . Seen from the full model, the layer computes , where is an matrix of rank at most . Linformer is standard attention with a learned low-rank attention matrix that is never formed. Projecting and costs multiply–adds, and the attention itself . The total is against . At and the score matrix shrinks 16× (16.8M → 1.0M entries) and the FLOPs 8×.
The low-rank argument
- the full context-mapping matrix
- any column vector, e.g. a column of
- a Johnson–Lindenstrauss argument: a random projection of rank preserves up to with high probability
- there exist such that the Linformer head is within of the full head with a that depends on , not on
Theorem 1 is about itself. Its proof uses a random projection, but computing would still need , so it says nothing yet about speed. Theorem 2 moves the projection inside the softmax, onto and , which is what gives the linear cost. Both are existence statements. In the model, and 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 .
Setup in the paper
- Pretraining
- masked-language-model pretraining as in RoBERTa (BookCorpus + English Wikipedia), , ; validation perplexity close to the standard Transformer, closer as grows
- Parameter sharing
- separate per head; headwise (one per layer); key–value ( per layer); layerwise (one matrix for all layers and heads); even layerwise sharing kept perplexity close
- Longer inputs
- with increased and fixed, perplexity after convergence stayed about the same, consistent with not needing to grow with
- 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
Worked example: n = 4, k = 2 with mean pooling
One query , . Keys , , , , values , , , . Neighbouring tokens are similar, as in the figure. Take (pool pairs).
| 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 averages keys 1–2 and 3–4, and averages the values: and .
- 2Softmax over the two summaries gives . Summing the full weights over the same pairs gives : the summaries received almost the right total mass.
- 3Output , against for full attention: relative error . Two scores replaced four.
- 4The approximation is good because the keys and values inside each pooled block are similar. If and 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 and .
1import torch, torch.nn as nn23class 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_heads7 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 keys10 self.F = self.E if share_kv else nn.Parameter(torch.randn(k, seq_len) / k ** 0.5)1112 def forward(self, x): # x: (B, n, d_model), n == seq_len13 B, n, _ = x.shape14 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 keys16 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), att2021layer = 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 headUse when
- + 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 and 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 ; padding and masking are awkward
- −Saving is only in FLOPs; no gain at
- −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: with learned ; scores are , cost instead of .
- ✓Justification: trained attention matrices are close to low-rank; a rank- approximation exists (JL), and suffices independently of .
- ✓Equivalent to standard attention with the rank- matrix , which is never formed.
- ✓Projected keys mix all positions, so Linformer is not causal and is tied to a fixed maximum length.
- ✓ and are learned (or structured, e.g. pooling) and can be shared across heads and layers; untrained random projections do not work inside the softmax.