Definition
Linear attention is attention whose similarity function is a dot product of feature maps, , instead of . Output is . The sums over do not depend on , so they are computed once. Time and memory become linear in the sequence length . With a causal mask the sums become running sums: a recurrent state and a normaliser .
Scaled dot-product attention builds the matrix , so its time and memory grow as . At 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 . They also showed that the causal version is exactly a recurrent network, which makes autoregressive generation cost per token in the sequence length. The abstract reports up to 4000× faster autoregressive prediction on very long sequences.
From softmax to a kernel
- row of the queries and row of the keys and values (each head separately)
- any non-negative similarity; the paper's generalised attention. Softmax attention is the case
- a feature map with non-negative outputs, so every weight is 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 features and , applied elementwise. It equals for and for . It is positive everywhere and, unlike , has a non-zero gradient for negative inputs.
Associativity: the whole trick
- a summary of all keys and values, computed in
- sum of the key features; is the row normaliser that softmax would provide
- time and extra memory, against time and memory for softmax
Both forms give the same numbers. Only the order of the matrix products changes. The left form costs about FLOPs per head, the right one about . The right one is cheaper once . For and the ratio is 63×, and at it is about 1000×. For short sequences () softmax attention is cheaper, and linear attention is no help.
Causal masking turns it into an RNN
- the hidden state: a matrix, the same size at every step
- running normaliser, a -vector
- output at position ; it uses only , exactly as a causal mask would (see Causal attention)
A causal mask restricts the sums to , so and become prefix sums. In training they can be computed for all positions in parallel, like a transformer. In generation each new token updates and in and reads them out, like an RNN. Softmax decoding instead keeps a key–value cache of floats at step and reads all of it to produce one token (see Transformer decoder). Linear attention keeps 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
- , elementwise, features; a degree-2 polynomial kernel is also discussed, with features
- Complexity
- time, 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
Worked example: three causal steps
Take and keys , , , values , , , and the query at step 3, . Then .
| 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
- 1Numerator .
- 2Denominator . Output .
- 3Check with explicit weights: the similarities normalise to , and . The state already held everything needed.
- 4Softmax with scaling: scores , weights , output . The two attentions are different functions. Linear attention is not an approximation of softmax.
1import torch, torch.nn.functional as F23def phi(x):4 return F.elu(x) + 1 # positive feature map56def 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^T10 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)1213def 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 it15 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 i17 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)1920def 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_t25 out = torch.einsum("bhd,bhdm->bhm", q_t, S) / (torch.einsum("bhd,bhd->bh", q_t, z)[..., None] + eps)26 return out, S, z2728B, H, N, D = 2, 4, 16, 829q, 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 agree38print(S.shape, z.shape) # torch.Size([2, 4, 8, 8]) torch.Size([2, 4, 8])Use when
- + time and state instead of and ; wins once
- +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 memory cannot hold more than about separate associations
- −No gain for , 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: with ; cost instead of .
- ✓Causal form is an RNN: , , so generation keeps a fixed state instead of a growing KV cache.
- ✓Reassociation is exact; it pays off only when .
- ✓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.