Linear Attention and the Performer

The kernelization trick

The attention computation softmax(Q·Kᵀ)·V is O(n²) because of the n×n matrix in the middle. The Performer (Choromanski et al., 2021) and the broader linear attention family ask: what if you replace softmax with a kernel function φ such that softmax(Q·Kᵀ) ≈ φ(Q)·φ(K)ᵀ?

If you have such a φ, you can rewrite φ(Q) · φ(K)ᵀ · V as φ(Q) · (φ(K)ᵀ · V). The parenthesization matters: the right-hand side computes a d×d matrix first (cost O(n·d²)), then projects with φ(Q) (cost O(n·d²)). Total: O(n·d²). Linear in sequence length, quadratic in model dimension. For long sequences with reasonable model dim, this is a huge win.

Why it didn't dominate

The math works. The practical results were disappointing. Random feature maps approximate softmax, but the approximation gets worse at long context — the dimension of φ that you'd need to faithfully approximate softmax grows with the entropy of the attention distribution, and high-entropy distributions over many tokens (which is what long context produces) blow up the approximation cost.

Real benchmarks showed Performer-style models losing meaningful quality compared to standard attention at the lengths where the speedup mattered most. The community concluded: exact attention quality is hard to give up. Approximations need to be very good or they cost you more than they save.

The lasting contribution

Even though the Performer didn't win, it established the conceptual framework that later worked better in different forms: structured attention via clever factorization. Kimi Linear, MHLA, and gated linear attention all descend from this idea, with smarter choices of φ and richer state mechanisms that overcome the original Performer's quality issues.

Code

Linear attention factorization — the key trick·python

# Standard attention: O(n^2 * d)
# attn = softmax(Q @ K.T) @ V              # n x n matrix in the middle

# Linear attention with kernel phi: O(n * d^2)
# Numerator: phi(Q) @ (phi(K).T @ V)        # d x d matrix in the middle
# Denominator: phi(Q) @ (phi(K).T @ ones)
# Output: numerator / denominator

# The trick is the associativity:
# (phi(Q) @ phi(K).T) @ V   ==   phi(Q) @ (phi(K).T @ V)
# Left side: O(n^2 * d). Right side: O(n * d^2).

Exercise

Implement Performer-style linear attention with random feature maps in PyTorch. Compare its output to standard scaled-dot-product attention on a small (1, 8, 1024, 64) input. Measure both speed and the divergence between outputs. You'll see that for short sequences the divergence is small but the speed advantage is also small; for long sequences the speed advantage grows but the divergence does too. That tradeoff is why Performer didn't win.