# Linear attention

> Linear attention (Katharopoulos et al., 2020) replaces exp(qᵀk) with a feature-map product φ(q)ᵀφ(k), φ(x) = elu(x) + 1. Associativity gives φ(Q)(φ(K)ᵀV) in O(n d²) instead of O(n² d), and causal attention becomes an RNN with a d×d state Sₜ.

Source: https://www.mlfoundry.in/learn/linear-attention  
Section: Deep Learning › Attention and Transformer Architectures  
Level: advanced · 13 min read · updated 2026-10-12

**Linear attention:** is attention whose similarity function is a dot product of feature maps, $\mathrm{sim}(q,k)=\phi(q)^\top\phi(k)$, instead of $\exp(q^\top k/\sqrt d)$. Output $i$ is $\phi(q_i)^\top\big(\sum_j\phi(k_j)v_j^\top\big)\big/\phi(q_i)^\top\sum_j\phi(k_j)$. The sums over $j$ do not depend on $i$, so they are computed once. Time and memory become **linear** in the sequence length $n$. With a causal mask the sums become running sums: a recurrent state $S_i\in\mathbb R^{d\times d_v}$ and a normaliser $z_i\in\mathbb R^{d}$.

**Scaled dot-product attention** builds the $n\times n$ matrix $QK^\top$, so its time and memory grow as $n^2$. At $n=4096$ that is 16.8M scores per head and layer. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas and François Fleuret, "Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention" (ICML 2020), noticed that the softmax is the only thing that forces this matrix to exist. Replace the exponential kernel with any kernel written as an explicit feature-map product, and the matrix product can be reassociated. They chose $\phi(x)=\mathrm{elu}(x)+1$. They also showed that the causal version is exactly a recurrent network, which makes autoregressive generation cost $O(1)$ per token in the sequence length. The abstract reports up to 4000× faster autoregressive prediction on very long sequences.

## From softmax to a kernel

$$
V'_i=\frac{\sum_{j}\mathrm{sim}(Q_i,K_j)\,V_j}{\sum_{j}\mathrm{sim}(Q_i,K_j)},\qquad \mathrm{sim}_{\text{softmax}}(q,k)=\exp\!\big(q^\top k/\sqrt d\big),\qquad \mathrm{sim}_{\text{linear}}(q,k)=\phi(q)^\top\phi(k)
$$

- $Q_i,K_j,V_j$: row $i$ of the queries and row $j$ of the keys and values (each head separately)
- $\mathrm{sim}$: any non-negative similarity; the paper's generalised attention. Softmax attention is the case $\mathrm{sim}=\exp(q^\top k/\sqrt d)$
- $\phi:\mathbb R^d\to\mathbb R^{C}$: a feature map with non-negative outputs, so every weight is $\ge 0$ and the denominator is positive

The exponential kernel is itself a dot product of feature maps, but of infinite-dimensional ones, so it cannot be reassociated exactly. **Performer** keeps the softmax and approximates those features with random ones. Linear attention gives up the softmax and picks a cheap finite map. The paper uses $C=d$ features and $\phi(x)=\mathrm{elu}(x)+1$, applied elementwise. It equals $x+1$ for $x>0$ and $e^x$ for $x\le 0$. It is positive everywhere and, unlike $\mathrm{relu}$, has a non-zero gradient for negative inputs.

## Associativity: the whole trick

$$
V'=\underbrace{\big(\phi(Q)\,\phi(K)^\top\big)}_{n\times n}V\;=\;\phi(Q)\underbrace{\big(\phi(K)^\top V\big)}_{d\times d_v},\qquad V'_i=\frac{\phi(Q_i)^\top\,S}{\phi(Q_i)^\top z},\quad S=\sum_{j=1}^{n}\phi(K_j)V_j^\top,\quad z=\sum_{j=1}^{n}\phi(K_j)
$$

- $\phi(K)^\top V$: a $d\times d_v$ summary of all keys and values, computed in $O(n\,d\,d_v)$
- $z$: sum of the key features; $\phi(Q_i)^\top z$ is the row normaliser that softmax would provide
- $\text{cost}$: $O(n\,d\,d_v)$ time and $O(d\,d_v)$ extra memory, against $O(n^2 d)$ time and $O(n^2)$ memory for softmax

Both forms give the same numbers. Only the order of the matrix products changes. The left form costs about $4n^2d$ FLOPs per head, the right one about $4nd^2$. The right one is cheaper once $n>d$. For $d=64$ and $n=4096$ the ratio is 63×, and at $n=65{,}536$ it is about 1000×. For short sequences ($n<d$) softmax attention is cheaper, and linear attention is no help.

## Causal masking turns it into an RNN

$$
S_i=S_{i-1}+\phi(K_i)V_i^\top,\qquad z_i=z_{i-1}+\phi(K_i),\qquad V'_i=\frac{\phi(Q_i)^\top S_i}{\phi(Q_i)^\top z_i},\qquad S_0=0,\ z_0=0
$$

- $S_i$: the hidden state: a $d\times d_v$ matrix, the same size at every step
- $z_i$: running normaliser, a $d$-vector
- $V'_i$: output at position $i$; it uses only $j\le i$, exactly as a causal mask would (see **Causal attention**)

A causal mask restricts the sums to $j\le i$, so $S$ and $z$ become prefix sums. In training they can be computed for all positions in parallel, like a transformer. In generation each new token updates $S$ and $z$ in $O(d\,d_v)$ and reads them out, like an RNN. Softmax decoding instead keeps a key–value cache of $2\,t\,d$ floats at step $t$ and reads all of it to produce one token (see **Transformer decoder**). Linear attention keeps $d\,d_v+d$ floats, however long the context is. That fixed state is the source of the 4000× generation speed-up. The same fact limits what the model can recall, as the callouts explain. The paper also derives the gradient of the causal form as cumulative sums, so training needs only constant extra memory per position, with a custom CUDA kernel.

**In the paper**

- **Authors, venue:** Katharopoulos, Vyas, Pappas, Fleuret, ICML 2020
- **Feature map:** $\phi(x)=\mathrm{elu}(x)+1$, elementwise, $C=d$ features; a degree-2 polynomial kernel is also discussed, with $O(d^2)$ features
- **Complexity:** $O(n\,d^2)$ time, $O(n\,d)$ memory for the outputs; causal gradients via cumulative sums with constant extra memory per step
- **Tasks:** synthetic sequence duplication; autoregressive image generation on MNIST (784 pixels) and CIFAR-10 (3072 pixels); speech recognition on WSJ with CTC
- **Baselines:** softmax attention and Reformer's LSH attention (see **Reformer**)
- **Headline:** similar quality to softmax on these tasks; up to 4000× faster autoregressive prediction for very long sequences

> Figure: Twelve tokens with d = 4 random queries, keys and values. Left: softmax attention weights. Middle: linear attention φ(Q)φ(K)ᵀ, normalised row by row. With the causal mask (default), a softmax row puts on average 0.721 on its largest weight, and a linear-attention row only 0.346. Without the mask the averages are 0.530 and 0.168 (uniform would be 1/12 = 0.083). The elu+1 kernel is much flatter than exp, which is the main quality cost of linear attention. Right: the state S_t = Σ_{j≤t} φ(k_j)v_jᵀ (4×4) and z_t after reading t tokens. Slide t: the state grows by one outer product per token, yet stays 20 floats. The output computed from the state alone matches the row of the matrix to about 2e-16 (rounding). Bottom: FLOPs per head for d = 64. The curves cross at n ≈ d. At n = 4096, softmax needs 4.3 GFLOPs and a 16.8M-entry score matrix, and linear attention needs 68.2 MFLOPs (63× less) and a 4.2k-float state. A softmax decoder would hold a 524k-float KV cache at that length. Switch d to 128 to move the crossover right.

## Worked example: three causal steps

Take $d=d_v=2$ and keys $K_1=(1,0)$, $K_2=(0,1)$, $K_3=(-1,1)$, values $V_1=(1,0)$, $V_2=(0,1)$, $V_3=(1,1)$, and the query at step 3, $Q_3=(0.5,-0.5)$. Then $\phi(Q_3)=(1.5,\ e^{-0.5})=(1.5,\ 0.6065)$.

Building the state (checked numerically in Node)

| step i | φ(Kᵢ) | Sᵢ = Sᵢ₋₁ + φ(Kᵢ)Vᵢᵀ | zᵢ | φ(Q₃)ᵀφ(Kᵢ) |
| --- | --- | --- | --- | --- |
| 1 | (2, 1) | [[2, 0], [1, 0]] | (2, 1) | 3.6065 |
| 2 | (1, 2) | [[2, 1], [1, 2]] | (3, 3) | 2.7131 |
| 3 | (0.3679, 2) | [[2.3679, 1.3679], [3, 4]] | (3.3679, 5) | 1.7649 |

**Reading out step 3, and the softmax comparison**

1. Numerator $\phi(Q_3)^\top S_3=1.5\,(2.3679,\,1.3679)+0.6065\,(3,\,4)=(5.3714,\ 4.4779)$.
2. Denominator $\phi(Q_3)^\top z_3=1.5\cdot3.3679+0.6065\cdot5=8.0845$. Output $V'_3=(0.6644,\ 0.5539)$.
3. Check with explicit weights: the similarities $(3.6065,\,2.7131,\,1.7649)$ normalise to $(0.4461,\,0.3356,\,0.2183)$, and $0.4461V_1+0.3356V_2+0.2183V_3=(0.6644,\,0.5539)$. The state already held everything needed.
4. Softmax with $1/\sqrt2$ scaling: scores $(0.3536,\,-0.3536,\,-0.7071)$, weights $(0.5437,\,0.2681,\,0.1882)$, output $(0.7319,\,0.4563)$. The two attentions are different functions. Linear attention is not an approximation of softmax.

```python
import torch, torch.nn.functional as F

def phi(x):
    return F.elu(x) + 1                                         # positive feature map

def linear_attention(q, k, v, eps=1e-6):
    # q, k: (B, H, N, D); v: (B, H, N, M)
    q, k = phi(q), phi(k)
    S = torch.einsum("bhnd,bhnm->bhdm", k, v)                   # (B, H, D, M)  sum_j phi(k_j) v_j^T
    z = torch.einsum("bhnd,bhd->bhn", q, k.sum(2))              # (B, H, N)     phi(q_i)^T sum_j phi(k_j)
    return torch.einsum("bhnd,bhdm->bhnm", q, S) / (z[..., None] + eps)

def causal_linear_attention(q, k, v, eps=1e-6):
    # prefix sums; this materialises (B, H, N, D, M), the paper uses a CUDA kernel to avoid it
    q, k = phi(q), phi(k)
    S = torch.einsum("bhnd,bhnm->bhndm", k, v).cumsum(2)        # (B, H, N, D, M)  S_i for every i
    z = torch.einsum("bhnd,bhnd->bhn", q, k.cumsum(2))          # (B, H, N)
    return torch.einsum("bhnd,bhndm->bhnm", q, S) / (z[..., None] + eps)

def step(q_t, k_t, v_t, S, z, eps=1e-6):
    # RNN form: q_t, k_t (B, H, D); v_t (B, H, M); state S (B, H, D, M), z (B, H, D)
    q_t, k_t = phi(q_t), phi(k_t)
    S = S + torch.einsum("bhd,bhm->bhdm", k_t, v_t)
    z = z + k_t
    out = torch.einsum("bhd,bhdm->bhm", q_t, S) / (torch.einsum("bhd,bhd->bh", q_t, z)[..., None] + eps)
    return out, S, z

B, H, N, D = 2, 4, 16, 8
q, k, v = (torch.randn(B, H, N, D, dtype=torch.float64) for _ in range(3))
print(linear_attention(q, k, v).shape)                      # torch.Size([2, 4, 16, 8])
y = causal_linear_attention(q, k, v)
S, z = torch.zeros(B, H, D, D, dtype=torch.float64), torch.zeros(B, H, D, dtype=torch.float64)
outs = []
for t in range(N):
    o, S, z = step(q[:, :, t], k[:, :, t], v[:, :, t], S, z)
    outs.append(o)
print(torch.allclose(y, torch.stack(outs, 2)))              # True: parallel and recurrent forms agree
print(S.shape, z.shape)                                     # torch.Size([2, 4, 8, 8]) torch.Size([2, 4, 8])
```

Linear attention in PyTorch: non-causal, causal (parallel prefix sums) and the recurrent step used for generation

> **The state is a fixed-size associative memory:** $S=\sum_j\phi(k_j)v_j^\top$ is the classic outer-product (fast-weight) memory: reading with $\phi(q)$ returns a mix of values whose keys overlap with $q$. A $d\times d_v$ matrix can store at most about $d$ key–value pairs without interference, whatever $n$ is. Softmax attention keeps all $n$ keys and can pick one exactly. This is why linear attention is weak at precise recall and copying over long contexts. Later work adds decay or gating to the update $S_i=S_{i-1}+\dots$ to control what is forgotten.

> **Linear attention is not approximate softmax:** $\mathrm{elu}(q)+1$ dotted with $\mathrm{elu}(k)+1$ is a different, much flatter kernel than $\exp(q^\top k/\sqrt d)$ (see the figure and the worked example). A model trained with softmax cannot be switched to linear attention at inference without fine-tuning. If you need an unbiased approximation of softmax itself, that is **Performer**.

> **The denominator and precision:** $\phi(q_i)^\top z_i$ grows with $i$ because $z_i$ is a sum of positive vectors. In half precision both numerator and denominator can overflow on long sequences, and an $\epsilon$ that is too large biases short prefixes. Accumulate $S$ and $z$ in float32. The naive `cumsum` causal form also stores an $n\times d\times d_v$ tensor per head, which is often more memory than the $n\times n$ matrix it replaced for moderate $n$. Use a chunked or fused kernel.

**Strengths**

- $O(n\,d^2)$ time and $O(d^2)$ state instead of $O(n^2d)$ and $O(n^2)$; wins once $n>d$
- Causal form is an RNN: constant time and memory per generated token, no growing KV cache
- Parallel training like a transformer; exact (no sampling, no hashing)
- Drop-in: only the similarity function changes

**Limitations**

- Flatter attention than softmax; usually some loss in quality, especially on precise retrieval and copying
- Fixed $d\times d_v$ memory cannot hold more than about $d$ separate associations
- No gain for $n<d$, and the causal prefix-sum form needs a custom kernel to be memory-efficient
- Cannot reuse softmax-trained weights without fine-tuning

**Question:** Why can linear attention compute φ(Q)(φ(K)ᵀV) but softmax attention cannot compute an analogous product?

- A. Because softmax is not differentiable
- B. Because exp(qᵀk) does not factor into finite feature maps, and the row-wise normalisation needs every score
- C. Because softmax needs the causal mask
- D. Because φ(x) = elu(x) + 1 is linear

**Answer:** B. Because exp(qᵀk) does not factor into finite feature maps, and the row-wise normalisation needs every score — Reassociation needs $\mathrm{sim}(q,k)=\phi(q)^\top\phi(k)$ with a finite $\phi$. Then $\sum_j\phi(k_j)v_j^\top$ and $\sum_j\phi(k_j)$ can be shared by all queries. $\exp(q^\top k)$ is a kernel only with infinite-dimensional features. Note that $\mathrm{elu}+1$ is not linear: "linear" refers to the cost in $n$.

**Question:** A causal linear-attention decoder with d = d_v = 64 per head generates token 10,000. How much attention state does each head keep?

- A. 2 · 10,000 · 64 floats
- B. 64 · 64 + 64 = 4160 floats
- C. 10,000² floats
- D. 64 floats

**Answer:** B. 64 · 64 + 64 = 4160 floats — The state is $S\in\mathbb R^{d\times d_v}$ plus $z\in\mathbb R^d$, independent of position. A softmax decoder would keep a KV cache of $2\cdot10{,}000\cdot64=1.28$M floats per head and read all of it to produce the token.

**Key points**

- Linear attention: $V'_i=\phi(Q_i)^\top\sum_j\phi(K_j)V_j^\top\,/\,\phi(Q_i)^\top\sum_j\phi(K_j)$ with $\phi(x)=\mathrm{elu}(x)+1$; cost $O(n\,d^2)$ instead of $O(n^2d)$.
- Causal form is an RNN: $S_i=S_{i-1}+\phi(K_i)V_i^\top$, $z_i=z_{i-1}+\phi(K_i)$, so generation keeps a fixed $d\times d_v$ state instead of a growing KV cache.
- Reassociation $(\phi(Q)\phi(K)^\top)V=\phi(Q)(\phi(K)^\top V)$ is exact; it pays off only when $n>d$.
- The elu+1 kernel is flatter than softmax and is a different model, not an approximation of it.
- Katharopoulos et al., ICML 2020: similar quality on image generation and speech, up to 4000× faster autoregressive prediction on very long sequences.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
