Linear attention (Linformer, Performer, kernel methods)

Summary

Linear attention avoids materializing the $n \times n$ softmax matrix by projecting the sequence axis or approximating the softmax kernel with a low-dimensional feature map. The per-layer cost drops from $O (n^{2} d)$ to $O (nk d)$ or $O (n r d)$ for $k, r ≪ n$ .

Sparse attention (see sparse attention) keeps the softmax exact but on fewer pairs. Linformer instead uses a learned low-rank projection along the sequence dimension; Performer approximates the softmax kernel with random features and changes the order of multiplication.

In practice, modern decoder LLMs do not use linear attention. Quality drops are non-trivial at scale and FlashAttention has made dense attention competitive in wall-clock. Linear attention is most relevant in domains with extreme $n$ (genomics, time series of millions of steps) or in research on sub-quadratic alternatives.

Two main families

Project the sequence axis (Linformer, Wang et al., 2020)

Learn fixed projection matrices $E, F \in R^{k \times n}$ with $k ≪ n$ . Replace $K, V \in R^{n \times d}$ with $E K, F V \in R^{k \times d}$ :

Attn = softmax (\frac{Q ( E K ) ^{⊤}}{d}) (F V) .

The softmax is now $n \times k$ . Cost: $O (nk d)$ , linear in $n$ . Caveat: $k$ is fixed at training time, so you cannot extrapolate to longer sequences without re-training.

Replace softmax with a kernel (Performer, Choromanski et al., 2020)

Softmax can be written as a kernel $K (q, k) = exp (q^{⊤} k / d)$ . Approximate this kernel with random features $ϕ : R^{d} \to R^{r}$ such that $E [ϕ (q)^{⊤} ϕ (k)] \approx K (q, k)$ .

Write $Q^{'} = ϕ (Q)$ and $K^{'} = ϕ (K)$ . Because softmax attention is row-normalized, the approximation needs both a value summary and a normalizer. For query row $i$ ,

Attn_{i} \approx \frac{ϕ ( q _{i} ) ^{⊤} ( K ^{'⊤} V )}{ϕ ( q _{i} ) ^{⊤} ( K ^{'⊤} 1 )} .

Compute the right-hand contractions first: $K^{'⊤} V$ is $r \times d$ and $K^{'⊤} 1$ is $r \times 1$ . Each transformed query reads these summaries, so no $n \times n$ matrix is formed. Cost: $O (n r d)$ , linear in $n$ , and the feature map works for arbitrary $n$ at inference (no fixed sequence-length projection).

Learning objective

Where does each method remove the n × n matrix?

Read it this way: follow the shapes, not the colors. Linformer reduces the token axis from n to k before queries meet keys, so its weight matrix is n × k. Performer keeps all n tokens but contracts transformed keys with values first, leaving an r × d summary and an r × 1 normalizer for each query to read. Both routes avoid n × n, but by compressing different axes. Original schematic based on Linformer and Performer.

When to use linear attention in 2026

Sequence length $n ≫ 32, 000$ where FlashAttention is still too slow or doesn’t fit memory.
Encoder-only models on very long inputs.
Real-time inference with strict latency budgets and tolerable quality loss.

For chat-style decoder LLMs, dense attention with FlashAttention + GQA + KV cache remains the production default.

Common pitfalls

Comparing FLOPs without measuring wall-clock. Linear attention’s $O (n)$ scaling only beats $O (n^{2})$ FlashAttention at large $n$ ; the crossover is implementation-dependent and often higher than naive analysis suggests.
Forgetting the constants. Linformer’s $k$ and Performer’s $r$ may need to be hundreds for good quality, so the linear scaling has a large constant.
Assuming all softmax-replacement schemes preserve the autoregressive mask trivially. Kernelized attention requires careful handling for causal masking (recursive cumulative sums).