Performer

Performer (Choromanski et al., ICLR 2021) approximates softmax attention with FAVOR+. Random features φ(x) = exp(ωᵀx − ‖x‖²/2)/√m, with ω Gaussian and orthogonal, give an unbiased, always-positive estimate of exp(qᵀk), so attention is computed linearly as φ(Q)(φ(K)ᵀV).

14 min read881 wordsadvanced0 viewsupdated 2026-10-12

Definition

Performer is a Transformer whose attention is computed by FAVOR+ (Fast Attention Via positive Orthogonal Random features). The softmax kernel exp⁡(q⊤k)\exp(q^\top k) is written as an expectation over Gaussian vectors ω\omega. It is estimated with mm random features ϕ(x)∈Rm\phi(x)\in\mathbb R^m, so that ϕ(q)⊤ϕ(k)≈exp⁡(q⊤k)\phi(q)^\top\phi(k)\approx\exp(q^\top k). Attention is then computed as in Linear attention, ϕ(Q)(ϕ(K)⊤V)\phi(Q)\big(\phi(K)^\top V\big) with the matching normaliser, in O(n m d)O(n\,m\,d) instead of O(n2d)O(n^2d). The estimate of each kernel value is unbiased and positive.

Linear attention makes attention linear by changing the kernel, so it computes a different function from softmax. Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Łukasz Kaiser, David Belanger, Lucy Colwell and Adrian Weller asked whether softmax attention itself could be approximated with provable accuracy, in "Rethinking Attention with Performers" (ICLR 2021). Random Fourier features (Rahimi and Recht, 2007) already approximate Gaussian kernels, and through them the softmax kernel. Their weights can be negative, though, and their error is largest where it hurts attention most. The paper's contribution is a positive random-feature map with orthogonal samples, a variance analysis that explains why positivity matters, and experiments on long sequences such as proteins.

The softmax kernel as an expectation

SM(x,y)=exp⁡(x⊤y)=Eω∼N(0,Id)[exp⁡ ⁣(ω⊤x−∥x∥22)exp⁡ ⁣(ω⊤y−∥y∥22)],x=qd1/4, y=kd1/4\mathrm{SM}(x,y)=\exp(x^\top y)=\mathbb E_{\omega\sim\mathcal N(0,I_d)}\Big[\exp\!\big(\omega^\top x-\tfrac{\lVert x\rVert^2}{2}\big)\exp\!\big(\omega^\top y-\tfrac{\lVert y\rVert^2}{2}\big)\Big],\qquad x=\frac{q}{d^{1/4}},\ y=\frac{k}{d^{1/4}}
SM(x,y)\mathrm{SM}(x,y)
the unnormalised softmax kernel; with the d−1/4d^{-1/4} rescaling, exp⁡(x⊤y)=exp⁡(q⊤k/d)\exp(x^\top y)=\exp(q^\top k/\sqrt d)
ω\omega
a standard Gaussian vector in Rd\mathbb R^d
why\text{why}
E[eω⊤s]=e∥s∥2/2\mathbb E[e^{\omega^\top s}]=e^{\lVert s\rVert^2/2} for s=x+ys=x+y, and ∥x+y∥2−∥x∥2−∥y∥2=2x⊤y\lVert x+y\rVert^2-\lVert x\rVert^2-\lVert y\rVert^2=2x^\top y
ϕ+(x)=e−∥x∥2/2m(eω1⊤x,…,eωm⊤x),ϕtrig(x)=e∥x∥2/2m(sin⁡ω1⊤x,cos⁡ω1⊤x,…,sin⁡ωm⊤x,cos⁡ωm⊤x)\phi^{+}(x)=\frac{e^{-\lVert x\rVert^2/2}}{\sqrt m}\big(e^{\omega_1^\top x},\dots,e^{\omega_m^\top x}\big),\qquad \phi^{\mathrm{trig}}(x)=\frac{e^{\lVert x\rVert^2/2}}{\sqrt m}\big(\sin\omega_1^\top x,\cos\omega_1^\top x,\dots,\sin\omega_m^\top x,\cos\omega_m^\top x\big)
ϕ+\phi^{+}
FAVOR+ positive features: every entry is >0>0, so every estimated weight and every normaliser is positive
ϕtrig\phi^{\mathrm{trig}}
classic random Fourier features applied to the softmax kernel; also unbiased, but entries and estimates can be negative
mm
number of random vectors; ϕ+∈Rm\phi^{+}\in\mathbb R^m, ϕtrig∈R2m\phi^{\mathrm{trig}}\in\mathbb R^{2m}

Both maps satisfy E[ϕ(x)⊤ϕ(y)]=exp⁡(x⊤y)\mathbb E[\phi(x)^\top\phi(y)]=\exp(x^\top y) exactly. Plugging either into ϕ(Q)(ϕ(K)⊤V)\phi(Q)(\phi(K)^\top V) and dividing by ϕ(Q)ϕ(K)⊤1\phi(Q)\phi(K)^\top\mathbf 1 gives an estimate of softmax attention in O(nmd)O(nmd) time and O(nm+md)O(nm+md) memory. The attention weights are a ratio of two unbiased estimates, so they are only approximately unbiased. They converge to the exact softmax as mm grows. With a causal mask, the same prefix-sum construction as in linear attention applies.

Variance: why positive features

MSE(SM^m+)=1m e∥x+y∥2 SM2(x,y)(1−e−∥x+y∥2),MSE(SM^mtrig)=12m e∥x+y∥2 SM−2(x,y)(1−e−∥x−y∥2)2\mathrm{MSE}\big(\widehat{\mathrm{SM}}^{+}_m\big)=\frac1m\,e^{\lVert x+y\rVert^2}\,\mathrm{SM}^2(x,y)\big(1-e^{-\lVert x+y\rVert^2}\big),\qquad \mathrm{MSE}\big(\widehat{\mathrm{SM}}^{\mathrm{trig}}_m\big)=\frac1{2m}\,e^{\lVert x+y\rVert^2}\,\mathrm{SM}^{-2}(x,y)\big(1-e^{-\lVert x-y\rVert^2}\big)^2
SM^m\widehat{\mathrm{SM}}_m
the mm-feature estimate of exp⁡(x⊤y)\exp(x^\top y) (Lemma 2 of the paper)
SM2 vs SM−2\mathrm{SM}^{2}\ \text{vs}\ \mathrm{SM}^{-2}
the positive estimator's error vanishes as SM→0\mathrm{SM}\to0; the trigonometric one's blows up as SM→0\mathrm{SM}\to0
relative\text{relative}
for positive features, RMSE/SM=(e∥x+y∥2−1)/m\mathrm{RMSE}/\mathrm{SM}=\sqrt{(e^{\lVert x+y\rVert^2}-1)/m}, independent of SM\mathrm{SM} given ∥x+y∥\lVert x+y\rVert

Most entries of a softmax row are small: a query attends strongly to a few keys and weakly to many. Trigonometric features estimate these small kernel values badly. They can return negative values, and a row's estimated normaliser can come out near zero or negative. That gives huge or sign-flipped attention weights and unstable training, which the paper observed. Positive features estimate small values accurately, and they can never produce a negative weight. They are worse than trigonometric features on the largest kernel values (the figure shows this). FAVOR+ trades some accuracy on a few large entries for accuracy and stability on the many small ones.

Orthogonal random features

Instead of mm independent Gaussians, FAVOR+ draws ω\omega's in blocks of dd that are exactly orthogonal. Each block comes from Gram–Schmidt (or QR) on a Gaussian matrix. Each direction is then rescaled to the length of an independent Gaussian vector (a χd\chi_d sample), so every ωi\omega_i is still marginally N(0,Id)\mathcal N(0,I_d) and the estimator stays unbiased. Orthogonality removes redundancy between samples, and the paper proves it strictly lowers the MSE of the positive estimator for any d>0d>0. The features are also periodically redrawn during training, so that no single unlucky draw persists.

In the paper

Venue
Choromanski et al., ICLR 2021
Mechanism
FAVOR+: positive random features + orthogonal ω\omega + optional feature redrawing; O(nmd)O(nmd) time, O(nm+nd+md)O(nm+nd+md) space
Guarantees
unbiased (or nearly unbiased, for the normalised attention) estimation of softmax attention; uniform-convergence bounds with mm of order dlog⁡dd\log d features; lower MSE with orthogonal features
Other kernels
the same framework gives generalised attention with other feature maps, e.g. Performer-ReLU with ϕ(x)=relu(Wx)\phi(x)=\mathrm{relu}(Wx)
Experiments
protein sequence modelling on TrEMBL (single and concatenated sequences up to length 8192), ImageNet64 image generation, and transfer from a pretrained softmax Transformer with a short fine-tune
exp(qᵀk/√d) ≈ φ(q)ᵀφ(k), ω ~ N(0, I) · φ(x) = e^(−‖x‖²/2)/√m · exp(ωᵢᵀx)query 1: exact softmax □ vs estimate ■ (m = 16)k1k2k3k4k5k6k7k8k9k10k11k12k13k14k15k16row TV distance 0.403mean TV (16 rows) 0.208negative φ(q)ᵀφ(k) 0 / 256rows with Σ ≤ 0 0features 16 (m = 16)ω orthogonal blocks of 4relative RMSE per (q, k) pair, Lemma 21e-21e-111e11e21e31e-111e1positivetrigtrue kernel exp(qᵀk/√d) · positive wins 111/256mean TV vs m (24 draws)0.00.51.0248163264128solid orthogonal · dashed i.i.d.this setting 0.252random features m (trig clipped at 1)n = 16, d = 4 · TV = ½Σⱼ|Âᵢⱼ − Aᵢⱼ| · rose bars: negative weights
featuresω
fig.Sixteen queries and keys with d = 4, so exp(qᵀk/√d) ranges from 0.065 to 12.4. Top: one query's exact softmax row (outlines) against the FAVOR+ estimate (filled bars). Bottom left: the theoretical relative error of each of the 256 (q, k) pairs (Lemma 2) against its true kernel value. Positive features (blue) beat trigonometric ones (orange) on 111 of 256 pairs: all 64 pairs with the smallest kernel values and none of the 64 largest. Trigonometric error rises steeply as the kernel value shrinks. Bottom right: mean total-variation distance between estimated and exact rows over 24 draws of ω. With positive features it falls from 0.415 (i.i.d.) / 0.409 (orthogonal) at m = 2 to 0.152 / 0.143 at m = 128, and orthogonal is lower at every m. Trigonometric features are far off at small m (2.94 at m = 2, i.e. weights far outside [0, 1]). At m ≥ 64 they catch up in this small d = 4 example (0.136 at m = 128), because they use 2m features. In the default draw (positive, orthogonal, m = 16) no estimate is negative, and the mean TV is 0.208. Switch to trigonometric: 60 of 256 estimates are negative (rose bars). At m = 8 with orthogonal ω, one row's normaliser goes negative and the mean TV jumps to 8.4. That is the instability FAVOR+ removes.

Worked example: one pair, two random features

Take (already rescaled) x=(0.5, 0.3)x=(0.5,\,0.3), y=(0.2, −0.4)y=(0.2,\,-0.4), so x⊤y=−0.02x^\top y=-0.02 and SM=e−0.02=0.9802\mathrm{SM}=e^{-0.02}=0.9802. Use m=2m=2 fixed directions ω1=(1,0)\omega_1=(1,0), ω2=(0.3,−1.2)\omega_2=(0.3,-1.2). Then ω⊤x=(0.5, −0.21)\omega^\top x=(0.5,\,-0.21) and ω⊤y=(0.2, 0.54)\omega^\top y=(0.2,\,0.54), with ∥x∥2=0.34\lVert x\rVert^2=0.34 and ∥y∥2=0.2\lVert y\rVert^2=0.2.

quantitypositive φ⁺trigonometric
φ(x)(0.9836, 0.4836)4 entries (sin, cos per ω)
φ(y)(0.7815, 1.0979)4 entries
φ(x)ᵀφ(y), this draw (true 0.9802)1.29951.1050
relative RMSE, m = 1, this pair (SM = 0.9802)0.80540.4159
relative RMSE, m = 1, pair a = (1, 0.5), b = (−1, −0.6) (SM = 0.2725)0.10039.5158
Estimates and theoretical errors (checked numerically in Node)

Reading the numbers

  1. 1ϕ+(x)1=e−0.17e0.5/2=0.9836\phi^{+}(x)_1=e^{-0.17}e^{0.5}/\sqrt2=0.9836; likewise for the other entries. Every entry is positive.
  2. 2One draw with two features gives 1.2995 for a true 0.9802. Unbiasedness is a statement about the average over draws, not about one draw.
  3. 3For this pair, ∥x+y∥2=0.5\lVert x+y\rVert^2=0.5 and ∥x−y∥2=0.58\lVert x-y\rVert^2=0.58. Lemma 2 gives relative RMSE e0.5−1=0.8054\sqrt{e^{0.5}-1}=0.8054 (positive) and 0.4159 (trig) at m=1m=1. Trig wins here, because the kernel value is near 1.
  4. 4For a pair pointing apart, a=(1,0.5)a=(1,0.5), b=(−1,−0.6)b=(-1,-0.6): SM=0.2725\mathrm{SM}=0.2725, ∥a+b∥2=0.01\lVert a+b\rVert^2=0.01, ∥a−b∥2=5.21\lVert a-b\rVert^2=5.21. Positive features: e0.01−1=0.1003\sqrt{e^{0.01}-1}=0.1003. Trig: 9.5158, about 95 times worse. Attention rows are full of such small entries.
  5. 5Both errors shrink as 1/m1/\sqrt m. Getting trig's 9.5 down to 0.1 would need about 9000 times more features.
python
1import math, torch
2
3def orthogonal_gaussian(m, d):
4 blocks = []
5 for _ in range(math.ceil(m / d)):
6 Qm, _ = torch.linalg.qr(torch.randn(d, d)) # orthonormal columns
7 blocks.append(Qm.T) # d orthonormal rows
8 W = torch.cat(blocks)[:m] # (m, d)
9 return W * torch.randn(m, d).norm(dim=1, keepdim=True) # chi_d lengths: each row ~ N(0, I) marginally
10
11def positive_features(x, W): # x (..., n, d), W (m, d)
12 # production code also subtracts a max over the features for stability; the constant cancels in the ratio
13 return torch.exp(x @ W.T - (x ** 2).sum(-1, keepdim=True) / 2) / math.sqrt(W.shape[0]) # (..., n, m)
14
15def favor_attention(q, k, v, W, causal=False, eps=1e-6): # q, k (B, H, n, d); v (B, H, n, e)
16 d = q.shape[-1]
17 qf = positive_features(q / d ** 0.25, W) # (B, H, n, m)
18 kf = positive_features(k / d ** 0.25, W)
19 if causal: # prefix sums, as in linear attention
20 S = torch.einsum("bhnm,bhne->bhnme", kf, v).cumsum(2) # (B, H, n, m, e)
21 num = torch.einsum("bhnm,bhnme->bhne", qf, S)
22 den = torch.einsum("bhnm,bhnm->bhn", qf, kf.cumsum(2))
23 else:
24 num = qf @ (kf.transpose(-1, -2) @ v) # (B, H, n, e) via an (m, e) summary
25 den = qf @ kf.sum(2).unsqueeze(-1) # (B, H, n, 1)
26 den = den.squeeze(-1)
27 return num / (den.unsqueeze(-1) + eps)
28
29B, H, n, d, m = 1, 2, 256, 16, 128
30q, k, v = (0.5 * torch.randn(B, H, n, d) for _ in range(3))
31W = orthogonal_gaussian(m, d) # redraw periodically during training
32approx = favor_attention(q, k, v, W)
33exact = torch.softmax(q @ k.transpose(-1, -2) / d ** 0.5, -1) @ v
34print(approx.shape) # torch.Size([1, 2, 256, 16])
35print(((approx - exact).norm() / exact.norm()).item()) # relative error; shrinks roughly like 1/sqrt(m)
36print(favor_attention(q, k, v, W, causal=True).shape) # torch.Size([1, 2, 256, 16])
FAVOR+ attention in PyTorch: orthogonal Gaussian directions, positive features, causal and non-causal

Use when

  • +Unbiased estimate of the softmax kernel; converges to exact attention as m→∞m\to\infty
  • +Positive features: no negative weights, no near-zero normalisers, stable training
  • +Linear O(nmd)O(nmd) time and memory; works causally via prefix sums
  • +Compatible with softmax-pretrained weights after a short fine-tune; the framework also covers other kernels

Avoid when

  • −Stochastic: error depends on mm, the draw and the query and key norms (exponentially)
  • −Needs mm in the hundreds; no gain unless n≫mn\gg m
  • −Sharp, near one-hot attention is the hardest case to approximate
  • −Feature redrawing and numerical stabilisation add implementation complexity

Check yourself

Why does FAVOR+ use exp(ωᵀx − ‖x‖²/2) instead of sin/cos random Fourier features?

Check yourself

Orthogonal random features in FAVOR+ are rescaled by independent χ_d lengths. What does this preserve?

Remember

  • ✓FAVOR+: exp⁡(x⊤y)=Eω[ϕ+(x)⊤ϕ+(y)]\exp(x^\top y)=\mathbb E_\omega[\phi^+(x)^\top\phi^+(y)] with ϕ+(x)=e−∥x∥2/2(eωi⊤x)i≤m/m\phi^+(x)=e^{-\lVert x\rVert^2/2}(e^{\omega_i^\top x})_{i\le m}/\sqrt m, ω∼N(0,I)\omega\sim\mathcal N(0,I), x=q/d1/4x=q/d^{1/4}; attention =ϕ(Q)(ϕ(K)⊤V)=\phi(Q)(\phi(K)^\top V) normalised, O(nmd)O(nmd).
  • ✓MSE: positive ∝SM2(1−e−∥x+y∥2)\propto\mathrm{SM}^2(1-e^{-\lVert x+y\rVert^2}), trigonometric ∝SM−2\propto\mathrm{SM}^{-2}; positive features are accurate on small kernel values and never negative.
  • ✓Orthogonal ω\omega blocks with χd\chi_d lengths keep unbiasedness and strictly lower the variance; features are redrawn during training.
  • ✓Approximates softmax itself, so pretrained softmax weights transfer with a short fine-tune, unlike elu+1 linear attention.
  • ✓Error grows like e∥x+y∥2/2/me^{\lVert x+y\rVert^2/2}/\sqrt m: large query and key norms (peaked attention) are the hard case.
← back to Deep Learning roadmap