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.
Detailed answer & concept explanation~6 min readEverything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Everything important, quickly.
Walk the associativity trick, derive the cost reduction, contrast Performer (kernel approximation) with Linformer (low rank K,V), discuss why softmax is hard to approximate cleanly, note that Mamba is the modern linear time successor via different math.
| 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.
- Linear Transformer used elu(x)+1 as the feature map; one of the earliest linear attention papers.
- Reformer used LSH bucketing as a different sparsity flavored linear approximation.
- Mamba and Mamba-2 (Gu and Dao, 2023-2024) and hybrid Transformer-SSM stacks shipping by 2026 are the modern linear time successors, distinct math from kernel feature map linear attention.
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?
QLinformer assumes the attention matrix is approximately low rank. When is this true?
Don't say thisRed flags and common mistakes that signal junior thinking. Click to expand.
Red flags and common mistakes 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.
The night-before-the-interview bullets. Scan these on the way to the call.
Primary sources. Skim 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.