Definition
Performer is a Transformer whose attention is computed by FAVOR+ (Fast Attention Via positive Orthogonal Random features). The softmax kernel is written as an expectation over Gaussian vectors . It is estimated with random features , so that . Attention is then computed as in Linear attention, with the matching normaliser, in instead of . 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
- the unnormalised softmax kernel; with the rescaling,
- a standard Gaussian vector in
- for , and
- FAVOR+ positive features: every entry is , so every estimated weight and every normaliser is positive
- classic random Fourier features applied to the softmax kernel; also unbiased, but entries and estimates can be negative
- number of random vectors; ,
Both maps satisfy exactly. Plugging either into and dividing by gives an estimate of softmax attention in time and memory. The attention weights are a ratio of two unbiased estimates, so they are only approximately unbiased. They converge to the exact softmax as grows. With a causal mask, the same prefix-sum construction as in linear attention applies.
Variance: why positive features
- the -feature estimate of (Lemma 2 of the paper)
- the positive estimator's error vanishes as ; the trigonometric one's blows up as
- for positive features, , independent of given
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 independent Gaussians, FAVOR+ draws 's in blocks of 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 sample), so every is still marginally 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 . 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 + optional feature redrawing; time, space
- Guarantees
- unbiased (or nearly unbiased, for the normalised attention) estimation of softmax attention; uniform-convergence bounds with of order features; lower MSE with orthogonal features
- Other kernels
- the same framework gives generalised attention with other feature maps, e.g. Performer-ReLU with
- 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
Worked example: one pair, two random features
Take (already rescaled) , , so and . Use fixed directions , . Then and , with and .
| quantity | positive φ⁺ | 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.2995 | 1.1050 |
| relative RMSE, m = 1, this pair (SM = 0.9802) | 0.8054 | 0.4159 |
| relative RMSE, m = 1, pair a = (1, 0.5), b = (−1, −0.6) (SM = 0.2725) | 0.1003 | 9.5158 |
Reading the numbers
- 1; likewise for the other entries. Every entry is positive.
- 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.
- 3For this pair, and . Lemma 2 gives relative RMSE (positive) and 0.4159 (trig) at . Trig wins here, because the kernel value is near 1.
- 4For a pair pointing apart, , : , , . Positive features: . Trig: 9.5158, about 95 times worse. Attention rows are full of such small entries.
- 5Both errors shrink as . Getting trig's 9.5 down to 0.1 would need about 9000 times more features.
1import math, torch23def orthogonal_gaussian(m, d):4 blocks = []5 for _ in range(math.ceil(m / d)):6 Qm, _ = torch.linalg.qr(torch.randn(d, d)) # orthonormal columns7 blocks.append(Qm.T) # d orthonormal rows8 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) marginally1011def 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 ratio13 return torch.exp(x @ W.T - (x ** 2).sum(-1, keepdim=True) / 2) / math.sqrt(W.shape[0]) # (..., n, m)1415def 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 attention20 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) summary25 den = qf @ kf.sum(2).unsqueeze(-1) # (B, H, n, 1)26 den = den.squeeze(-1)27 return num / (den.unsqueeze(-1) + eps)2829B, H, n, d, m = 1, 2, 256, 16, 12830q, k, v = (0.5 * torch.randn(B, H, n, d) for _ in range(3))31W = orthogonal_gaussian(m, d) # redraw periodically during training32approx = favor_attention(q, k, v, W)33exact = torch.softmax(q @ k.transpose(-1, -2) / d ** 0.5, -1) @ v34print(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])Use when
- +Unbiased estimate of the softmax kernel; converges to exact attention as
- +Positive features: no negative weights, no near-zero normalisers, stable training
- +Linear 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 , the draw and the query and key norms (exponentially)
- −Needs in the hundreds; no gain unless
- −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+: with , , ; attention normalised, .
- ✓MSE: positive , trigonometric ; positive features are accurate on small kernel values and never negative.
- ✓Orthogonal blocks with 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 : large query and key norms (peaked attention) are the hard case.