Linear Attention
Definition
Linear attention replaces the softmax kernel with a separable feature-map similarity , so that matrix-multiplication associativity lets the score matrix be dissolved entirely — giving time and a constant-size recurrent state at inference instead of a growing KV cache. Introduced by Katharopoulos et al., “Transformers are RNNs” (2020; arXiv:2006.16236).
Key math / How it works
Softmax attention forces the order because the nonlinearity couples each score row. Replace with (, e.g. ) and pull out of the sum:
= \frac{\phi(q_i)^\top S}{\phi(q_i)^\top z}.$$ Computing $S=\phi(K)^\top V\in\mathbb{R}^{r\times d_v}$ (and $z$) **first** contracts the sequence dimension into a state whose size is independent of $s$; then $O = (\phi(Q)(\phi(K)^\top V))\oslash(\phi(Q)(\phi(K)^\top\mathbf 1))$ costs $O(s\,r\,d_v)$ — **linear in $s$**. **Recurrent form (causal).** With $j\le t$ the accumulators become running sums — a linear RNN with matrix-valued state: $$S_t = S_{t-1}+\phi(k_t)v_t^\top,\quad z_t=z_{t-1}+\phi(k_t),\quad o_t=\frac{\phi(q_t)^\top S_t}{\phi(q_t)^\top z_t}.$$ Inference is **constant memory and compute per token** ($O(rd)$), no growing cache. Cousins: **Performers/FAVOR+** (Choromanski et al., 2020; [arXiv:2009.14794](https://arxiv.org/abs/2009.14794)) use positive **random features** for an unbiased estimate of the true softmax kernel; **Linformer** (Wang et al., 2020; [arXiv:2006.04768](https://arxiv.org/abs/2006.04768)) projects $K,V$ along the sequence dim to $k\ll s$, exploiting the empirical low-rank of the attention matrix. ## Why it matters Linear attention beats softmax on FLOPs once $s>r$ (essentially always at long context) and, more importantly, replaces the $O(s)$ KV cache with an $O(1)$ state — the same win as [[concepts/state-space-models|SSMs]]. But the **recall gap is real**: a cheap $\phi$ cannot produce softmax's sharp near-one-hot distributions, and a fixed $r\times d_v$ state is a lossy summary, so it underperforms on exact recall / copying / in-context lookup. This asymmetry — cheap but lossy — is why the field moved toward selective SSMs ([[concepts/mamba|Mamba]]) and hybrids rather than plain linear attention. ## Taught in - [[learn/attention/07-linear-and-subquadratic]] — §3.1 kernel + associativity + recurrent form; §3.2 Performer/Linformer. ## See also - [[concepts/state-space-models]] · [[concepts/mamba]] — the recurrent-state alternative line - [[concepts/sparse-attention]] — thinning the matrix vs. dissolving it - [[concepts/kv-cache]] · [[concepts/flash-attention]] — the exact-attention baselines - [[concepts/attention-glossary]] · [[topics/attention-mechanisms]]