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ₜ.

13 min read819 wordsadvanced0 viewsupdated 2026-10-12

Definition

Linear attention is attention whose similarity function is a dot product of feature maps, sim(q,k)=ϕ(q)⊤ϕ(k)\mathrm{sim}(q,k)=\phi(q)^\top\phi(k), instead of exp⁡(q⊤k/d)\exp(q^\top k/\sqrt d). Output ii is ϕ(qi)⊤(∑jϕ(kj)vj⊤)/ϕ(qi)⊤∑jϕ(kj)\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 jj do not depend on ii, so they are computed once. Time and memory become linear in the sequence length nn. With a causal mask the sums become running sums: a recurrent state Si∈Rd×dvS_i\in\mathbb R^{d\times d_v} and a normaliser zi∈Rdz_i\in\mathbb R^{d}.

Scaled dot-product attention builds the n×nn\times n matrix QK⊤QK^\top, so its time and memory grow as n2n^2. At n=4096n=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 ϕ(x)=elu(x)+1\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)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

Vi′=∑jsim(Qi,Kj) Vj∑jsim(Qi,Kj),simsoftmax(q,k)=exp⁡ ⁣(q⊤k/d),simlinear(q,k)=ϕ(q)⊤ϕ(k)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)
Qi,Kj,VjQ_i,K_j,V_j
row ii of the queries and row jj of the keys and values (each head separately)
sim\mathrm{sim}
any non-negative similarity; the paper's generalised attention. Softmax attention is the case sim=exp⁡(q⊤k/d)\mathrm{sim}=\exp(q^\top k/\sqrt d)
ϕ:Rd→RC\phi:\mathbb R^d\to\mathbb R^{C}
a feature map with non-negative outputs, so every weight is ≥0\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=dC=d features and ϕ(x)=elu(x)+1\phi(x)=\mathrm{elu}(x)+1, applied elementwise. It equals x+1x+1 for x>0x>0 and exe^x for x≤0x\le 0. It is positive everywhere and, unlike relu\mathrm{relu}, has a non-zero gradient for negative inputs.

Associativity: the whole trick

V′=(ϕ(Q) ϕ(K)⊤)⏟n×nV  =  ϕ(Q)(ϕ(K)⊤V)⏟d×dv,Vi′=ϕ(Qi)⊤ Sϕ(Qi)⊤z,S=∑j=1nϕ(Kj)Vj⊤,z=∑j=1nϕ(Kj)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)
ϕ(K)⊤V\phi(K)^\top V
a d×dvd\times d_v summary of all keys and values, computed in O(n d dv)O(n\,d\,d_v)
zz
sum of the key features; ϕ(Qi)⊤z\phi(Q_i)^\top z is the row normaliser that softmax would provide
cost\text{cost}
O(n d dv)O(n\,d\,d_v) time and O(d dv)O(d\,d_v) extra memory, against O(n2d)O(n^2 d) time and O(n2)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 4n2d4n^2d FLOPs per head, the right one about 4nd24nd^2. The right one is cheaper once n>dn>d. For d=64d=64 and n=4096n=4096 the ratio is 63×, and at n=65,536n=65{,}536 it is about 1000×. For short sequences (n<dn<d) softmax attention is cheaper, and linear attention is no help.

Causal masking turns it into an RNN

Si=Si−1+ϕ(Ki)Vi⊤,zi=zi−1+ϕ(Ki),Vi′=ϕ(Qi)⊤Siϕ(Qi)⊤zi,S0=0, z0=0S_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
SiS_i
the hidden state: a d×dvd\times d_v matrix, the same size at every step
ziz_i
running normaliser, a dd-vector
Vi′V'_i
output at position ii; it uses only j≤ij\le i, exactly as a causal mask would (see Causal attention)

A causal mask restricts the sums to j≤ij\le i, so SS and zz become prefix sums. In training they can be computed for all positions in parallel, like a transformer. In generation each new token updates SS and zz in O(d dv)O(d\,d_v) and reads them out, like an RNN. Softmax decoding instead keeps a key–value cache of 2 t d2\,t\,d floats at step tt and reads all of it to produce one token (see Transformer decoder). Linear attention keeps d dv+dd\,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
ϕ(x)=elu(x)+1\phi(x)=\mathrm{elu}(x)+1, elementwise, C=dC=d features; a degree-2 polynomial kernel is also discussed, with O(d2)O(d^2) features
Complexity
O(n d2)O(n\,d^2) time, O(n d)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
softmax: exp(qᵢᵀkⱼ/√d) · linear: φ(qᵢ)ᵀφ(kⱼ), φ(x) = elu(x) + 1 · n = 12, d = 4softmax attention Arow 6 max 0.573mean row max 0.721linear attention φ(Q)φ(K)ᵀrow 6 max 0.252mean row max 0.346state S6 = Σⱼ≤6 φ(kⱼ)vⱼᵀS (d×d)ztokens read 6 of 12φ(qₜ)ᵀz 77.963oₜ −0.17 0.32 1.00 −0.16|state − map| 2.2e-16state floats 20 (fixed)FLOPs per head vs n (d = 64), log–log642561.0k4.1k16.4k65.5k1e61e81e101e12softmax 4n²dlinear 4nd² + 4ndn 4096softmax FLOPs 4.3Glinear FLOPs 68.2Mratio 63.0×n×n scores 16.8Md×d state + z 4.2kKV cache at n 524.3kclick a row · break-even at n ≈ d; linear wins for n > d, softmax for n < d
maskcost d
fig.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=dv=2d=d_v=2 and keys K1=(1,0)K_1=(1,0), K2=(0,1)K_2=(0,1), K3=(−1,1)K_3=(-1,1), values V1=(1,0)V_1=(1,0), V2=(0,1)V_2=(0,1), V3=(1,1)V_3=(1,1), and the query at step 3, Q3=(0.5,−0.5)Q_3=(0.5,-0.5). Then ϕ(Q3)=(1.5, e−0.5)=(1.5, 0.6065)\phi(Q_3)=(1.5,\ e^{-0.5})=(1.5,\ 0.6065).

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
Building the state (checked numerically in Node)

Reading out step 3, and the softmax comparison

  1. 1Numerator ϕ(Q3)⊤S3=1.5 (2.3679, 1.3679)+0.6065 (3, 4)=(5.3714, 4.4779)\phi(Q_3)^\top S_3=1.5\,(2.3679,\,1.3679)+0.6065\,(3,\,4)=(5.3714,\ 4.4779).
  2. 2Denominator ϕ(Q3)⊤z3=1.5⋅3.3679+0.6065⋅5=8.0845\phi(Q_3)^\top z_3=1.5\cdot3.3679+0.6065\cdot5=8.0845. Output V3′=(0.6644, 0.5539)V'_3=(0.6644,\ 0.5539).
  3. 3Check with explicit weights: the similarities (3.6065, 2.7131, 1.7649)(3.6065,\,2.7131,\,1.7649) normalise to (0.4461, 0.3356, 0.2183)(0.4461,\,0.3356,\,0.2183), and 0.4461V1+0.3356V2+0.2183V3=(0.6644, 0.5539)0.4461V_1+0.3356V_2+0.2183V_3=(0.6644,\,0.5539). The state already held everything needed.
  4. 4Softmax with 1/21/\sqrt2 scaling: scores (0.3536, −0.3536, −0.7071)(0.3536,\,-0.3536,\,-0.7071), weights (0.5437, 0.2681, 0.1882)(0.5437,\,0.2681,\,0.1882), output (0.7319, 0.4563)(0.7319,\,0.4563). The two attentions are different functions. Linear attention is not an approximation of softmax.
python
1import torch, torch.nn.functional as F
2
3def phi(x):
4 return F.elu(x) + 1 # positive feature map
5
6def linear_attention(q, k, v, eps=1e-6):
7 # q, k: (B, H, N, D); v: (B, H, N, M)
8 q, k = phi(q), phi(k)
9 S = torch.einsum("bhnd,bhnm->bhdm", k, v) # (B, H, D, M) sum_j phi(k_j) v_j^T
10 z = torch.einsum("bhnd,bhd->bhn", q, k.sum(2)) # (B, H, N) phi(q_i)^T sum_j phi(k_j)
11 return torch.einsum("bhnd,bhdm->bhnm", q, S) / (z[..., None] + eps)
12
13def causal_linear_attention(q, k, v, eps=1e-6):
14 # prefix sums; this materialises (B, H, N, D, M), the paper uses a CUDA kernel to avoid it
15 q, k = phi(q), phi(k)
16 S = torch.einsum("bhnd,bhnm->bhndm", k, v).cumsum(2) # (B, H, N, D, M) S_i for every i
17 z = torch.einsum("bhnd,bhnd->bhn", q, k.cumsum(2)) # (B, H, N)
18 return torch.einsum("bhnd,bhndm->bhnm", q, S) / (z[..., None] + eps)
19
20def step(q_t, k_t, v_t, S, z, eps=1e-6):
21 # RNN form: q_t, k_t (B, H, D); v_t (B, H, M); state S (B, H, D, M), z (B, H, D)
22 q_t, k_t = phi(q_t), phi(k_t)
23 S = S + torch.einsum("bhd,bhm->bhdm", k_t, v_t)
24 z = z + k_t
25 out = torch.einsum("bhd,bhdm->bhm", q_t, S) / (torch.einsum("bhd,bhd->bh", q_t, z)[..., None] + eps)
26 return out, S, z
27
28B, H, N, D = 2, 4, 16, 8
29q, k, v = (torch.randn(B, H, N, D, dtype=torch.float64) for _ in range(3))
30print(linear_attention(q, k, v).shape) # torch.Size([2, 4, 16, 8])
31y = causal_linear_attention(q, k, v)
32S, z = torch.zeros(B, H, D, D, dtype=torch.float64), torch.zeros(B, H, D, dtype=torch.float64)
33outs = []
34for t in range(N):
35 o, S, z = step(q[:, :, t], k[:, :, t], v[:, :, t], S, z)
36 outs.append(o)
37print(torch.allclose(y, torch.stack(outs, 2))) # True: parallel and recurrent forms agree
38print(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

Use when

  • +O(n d2)O(n\,d^2) time and O(d2)O(d^2) state instead of O(n2d)O(n^2d) and O(n2)O(n^2); wins once n>dn>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

Avoid when

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

Check yourself

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

Check yourself

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

Remember

  • ✓Linear attention: Vi′=ϕ(Qi)⊤∑jϕ(Kj)Vj⊤ / ϕ(Qi)⊤∑jϕ(Kj)V'_i=\phi(Q_i)^\top\sum_j\phi(K_j)V_j^\top\,/\,\phi(Q_i)^\top\sum_j\phi(K_j) with ϕ(x)=elu(x)+1\phi(x)=\mathrm{elu}(x)+1; cost O(n d2)O(n\,d^2) instead of O(n2d)O(n^2d).
  • ✓Causal form is an RNN: Si=Si−1+ϕ(Ki)Vi⊤S_i=S_{i-1}+\phi(K_i)V_i^\top, zi=zi−1+ϕ(Ki)z_i=z_{i-1}+\phi(K_i), so generation keeps a fixed d×dvd\times d_v state instead of a growing KV cache.
  • ✓Reassociation (ϕ(Q)ϕ(K)⊤)V=ϕ(Q)(ϕ(K)⊤V)(\phi(Q)\phi(K)^\top)V=\phi(Q)(\phi(K)^\top V) is exact; it pays off only when n>dn>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.
← back to Deep Learning roadmap