How do linear attention variants (Performer, Linformer) achieve O(n) complexity, and what's the quality cost?
Linear attention swaps softmax for a kernel feature map so (φ(K)ᵀV) can be computed first, making total cost O(n·d²) instead of O(n²·d).
Imagine a party where you want to know how much each guest should pay attention to every other guest. The slow way builds a giant grid of every pair and reads from it; the grid grows fast and is awkward to handle. Linear attention rearranges the order of work. Each guest writes a small summary card about themselves. Combining all the summary cards is cheap and gives a single pocket sized notebook. Each guest then peeks at the notebook instead of the giant grid. The shortcut keeps the work small, but the summary cards round off some detail, so the answers are a touch less precise than the full grid would give.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Linear attention looks like a clean win on paper: rearrange a matrix product, drop a complexity class, scale to arbitrary context. The reason it has not displaced softmax attention in mainstream LLMs is more interesting than the trick itself, and it sits at the intersection of approximation theory, optimization stability, and GPU hardware utilization.
The sections below walk the associativity rearrangement that makes the cost reduction possible, the main feature map and low rank choices the literature explores, the structural reason softmax keeps winning on quality, the role FlashAttention played in resetting the comparison, and where the linear time crown actually went in 2024-2026.
The associativity trick
Standard attention is softmax(QKᵀ) V. The score matrix is n × n and the kernel costs O(n² · d) in both compute and memory. At n = 100k with d = 128, that is 10¹⁰ · 128 operations per head per layer, which is what kills the naive approach at long context.
Suppose softmax(QKᵀ) factors as φ(Q) φ(K)ᵀ for some row-wise feature map φ. Matrix multiplication is associative, so:
Evaluating right to left, φ(K)ᵀ V is a (d' × n) times (n × d) product that yields a small (d' × d) matrix in O(n · d' · d). The final φ(Q) multiply costs another O(n · d' · d). The total is linear in n and the n × n matrix never appears.
The whole linear attention research program is variations on how to make the factorization actually exist. Each variant picks a different point on the bias variance cost frontier.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| Method | Mechanism | Complexity | Approximation? |
|---|---|---|---|
| Standard attention | softmax(QKᵀ) V | O(n²·d) | Exact |
| FlashAttention | Same math, tiled I/O | O(n²·d) compute, O(n) memory | Exact |
| Performer | Random feature softmax kernel | O(n·d²) | Yes (unbiased) |
| Linformer | Low rank K,V projection | O(n·k·d) | Yes (low rank) |
| Linear Transformer | elu+1 feature map | O(n·d²) | Yes (kernel) |
| Mamba (SSM) | Selective recurrent state | O(n·d²) | Different math, not attention |
Real products, models, and research that use this idea.
- Performer demonstrated linear time attention with FAVOR+ random features.
- Linformer low rank projected K, V from n to k=256 for sequences up to 4k.
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy is the softmax kernel exp(q · k) hard to approximate with a separable feature map?
exp(q · k) is positive and grows fast with q · k. To approximate it as φ(q) · φ(k), you need feature maps that handle the exponential's heavy tails without high variance. Performer's FAVOR+ uses positive random features for an unbiased approximation, but variance grows with query norms, a structural difficulty.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Saying linear attention 'just drops softmax', it doesn't; it replaces softmax with a different separable kernel approximation, and the choice of approximation is what determines quality vs cost.
60 second bullets to scan on the way to the call.
The associativity trick and why multiplying right to left gives O(n times d squared)
Role of the feature map phi as a kernel approximation to softmax
Primary sources. Browse if you want the original framing.
- Choromanski et al. 2020 — Rethinking Attention with Performers
- Wang et al. 2020 — Linformer: Self-Attention with Linear Complexity
- Katharopoulos et al. 2020 — Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
- Gu & Dao 2023 — Mamba: Linear-Time Sequence Modeling with Selective State Spaces
Same topic, related formats. Practice these next.