# 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).

Source: https://www.mlfoundry.in/learn/performer  
Section: Deep Learning › Attention and Transformer Architectures  
Level: advanced · 14 min read · updated 2026-10-12

**Performer:** is a Transformer whose attention is computed by **FAVOR+** (Fast Attention Via positive Orthogonal Random features). The softmax kernel $\exp(q^\top k)$ is written as an expectation over Gaussian vectors $\omega$. It is estimated with $m$ random features $\phi(x)\in\mathbb R^m$, so that $\phi(q)^\top\phi(k)\approx\exp(q^\top k)$. Attention is then computed as in **Linear attention**, $\phi(Q)\big(\phi(K)^\top V\big)$ with the matching normaliser, in $O(n\,m\,d)$ instead of $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

$$
\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}}
$$

- $\mathrm{SM}(x,y)$: the unnormalised softmax kernel; with the $d^{-1/4}$ rescaling, $\exp(x^\top y)=\exp(q^\top k/\sqrt d)$
- $\omega$: a standard Gaussian vector in $\mathbb R^d$
- $\text{why}$: $\mathbb E[e^{\omega^\top s}]=e^{\lVert s\rVert^2/2}$ for $s=x+y$, and $\lVert x+y\rVert^2-\lVert x\rVert^2-\lVert y\rVert^2=2x^\top y$

$$
\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$, so every estimated weight and every normaliser is positive
- $\phi^{\mathrm{trig}}$: classic random Fourier features applied to the softmax kernel; also unbiased, but entries and estimates can be negative
- $m$: number of random vectors; $\phi^{+}\in\mathbb R^m$, $\phi^{\mathrm{trig}}\in\mathbb R^{2m}$

Both maps satisfy $\mathbb E[\phi(x)^\top\phi(y)]=\exp(x^\top y)$ exactly. Plugging either into $\phi(Q)(\phi(K)^\top V)$ and dividing by $\phi(Q)\phi(K)^\top\mathbf 1$ gives an estimate of softmax attention in $O(nmd)$ time and $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 $m$ grows. With a causal mask, the same prefix-sum construction as in linear attention applies.

## Variance: why positive features

$$
\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
$$

- $\widehat{\mathrm{SM}}_m$: the $m$-feature estimate of $\exp(x^\top y)$ (Lemma 2 of the paper)
- $\mathrm{SM}^{2}\ \text{vs}\ \mathrm{SM}^{-2}$: the positive estimator's error **vanishes** as $\mathrm{SM}\to0$; the trigonometric one's **blows up** as $\mathrm{SM}\to0$
- $\text{relative}$: for positive features, $\mathrm{RMSE}/\mathrm{SM}=\sqrt{(e^{\lVert x+y\rVert^2}-1)/m}$, independent of $\mathrm{SM}$ given $\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 $m$ independent Gaussians, FAVOR+ draws $\omega$'s in blocks of $d$ 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 $\chi_d$ sample), so every $\omega_i$ is still marginally $\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>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)$ time, $O(nm+nd+md)$ space
- **Guarantees:** unbiased (or nearly unbiased, for the normalised attention) estimation of softmax attention; uniform-convergence bounds with $m$ of order $d\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 $\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

> Figure: 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)$, $y=(0.2,\,-0.4)$, so $x^\top y=-0.02$ and $\mathrm{SM}=e^{-0.02}=0.9802$. Use $m=2$ fixed directions $\omega_1=(1,0)$, $\omega_2=(0.3,-1.2)$. Then $\omega^\top x=(0.5,\,-0.21)$ and $\omega^\top y=(0.2,\,0.54)$, with $\lVert x\rVert^2=0.34$ and $\lVert y\rVert^2=0.2$.

Estimates and theoretical errors (checked numerically in Node)

| 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. $\phi^{+}(x)_1=e^{-0.17}e^{0.5}/\sqrt2=0.9836$; likewise for the other entries. Every entry is positive.
2. One 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. For this pair, $\lVert x+y\rVert^2=0.5$ and $\lVert x-y\rVert^2=0.58$. Lemma 2 gives relative RMSE $\sqrt{e^{0.5}-1}=0.8054$ (positive) and 0.4159 (trig) at $m=1$. Trig wins here, because the kernel value is near 1.
4. For a pair pointing apart, $a=(1,0.5)$, $b=(-1,-0.6)$: $\mathrm{SM}=0.2725$, $\lVert a+b\rVert^2=0.01$, $\lVert a-b\rVert^2=5.21$. Positive features: $\sqrt{e^{0.01}-1}=0.1003$. Trig: 9.5158, about 95 times worse. Attention rows are full of such small entries.
5. Both errors shrink as $1/\sqrt m$. Getting trig's 9.5 down to 0.1 would need about 9000 times more features.

```python
import math, torch

def orthogonal_gaussian(m, d):
    blocks = []
    for _ in range(math.ceil(m / d)):
        Qm, _ = torch.linalg.qr(torch.randn(d, d))            # orthonormal columns
        blocks.append(Qm.T)                                    # d orthonormal rows
    W = torch.cat(blocks)[:m]                                  # (m, d)
    return W * torch.randn(m, d).norm(dim=1, keepdim=True)     # chi_d lengths: each row ~ N(0, I) marginally

def positive_features(x, W):                                   # x (..., n, d), W (m, d)
    # production code also subtracts a max over the features for stability; the constant cancels in the ratio
    return torch.exp(x @ W.T - (x ** 2).sum(-1, keepdim=True) / 2) / math.sqrt(W.shape[0])   # (..., n, m)

def favor_attention(q, k, v, W, causal=False, eps=1e-6):       # q, k (B, H, n, d); v (B, H, n, e)
    d = q.shape[-1]
    qf = positive_features(q / d ** 0.25, W)                   # (B, H, n, m)
    kf = positive_features(k / d ** 0.25, W)
    if causal:                                                 # prefix sums, as in linear attention
        S = torch.einsum("bhnm,bhne->bhnme", kf, v).cumsum(2)  # (B, H, n, m, e)
        num = torch.einsum("bhnm,bhnme->bhne", qf, S)
        den = torch.einsum("bhnm,bhnm->bhn", qf, kf.cumsum(2))
    else:
        num = qf @ (kf.transpose(-1, -2) @ v)                  # (B, H, n, e) via an (m, e) summary
        den = qf @ kf.sum(2).unsqueeze(-1)                     # (B, H, n, 1)
        den = den.squeeze(-1)
    return num / (den.unsqueeze(-1) + eps)

B, H, n, d, m = 1, 2, 256, 16, 128
q, k, v = (0.5 * torch.randn(B, H, n, d) for _ in range(3))
W = orthogonal_gaussian(m, d)                                  # redraw periodically during training
approx = favor_attention(q, k, v, W)
exact = torch.softmax(q @ k.transpose(-1, -2) / d ** 0.5, -1) @ v
print(approx.shape)                                            # torch.Size([1, 2, 256, 16])
print(((approx - exact).norm() / exact.norm()).item())         # relative error; shrinks roughly like 1/sqrt(m)
print(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

> **Approximate softmax, not a new kernel:** **Linear attention** with $\mathrm{elu}+1$ defines a new model. FAVOR+ estimates the old one. That is why a Performer can start from a pretrained softmax Transformer and recover its accuracy with a short fine-tune, while a switch to $\mathrm{elu}+1$ would need retraining. The price is randomness: the attention is exact only in expectation, and its error depends on $m$, on $\lVert q\rVert,\lVert k\rVert$ through $e^{\lVert x+y\rVert^2}$, and on the draw.

> **Large query and key norms:** The positive estimator's relative error grows like $\sqrt{e^{\lVert x+y\rVert^2}/m}$, exponential in the squared norms. Very peaked attention, with large $\lVert q\rVert$ and $\lVert k\rVert$, needs many features or is badly approximated. Implementations normalise or clip queries and keys, and stabilise $\exp$ by subtracting a maximum. If FAVOR+ fails to match softmax, check the norms before raising $m$.

> **Cost in practice:** FAVOR+ costs $O(nmd)$ with $m$ typically a few hundred. It beats exact attention only when $n$ is well above $m$, and it does not cut the work by $n/m$ exactly because of the feature computation. On modern GPUs, exact attention with **FlashAttention** is often faster up to several thousand tokens. The causal prefix-sum form has the same memory issue as in **Linear attention**: it needs a chunked or fused kernel.

**Strengths**

- Unbiased estimate of the softmax kernel; converges to exact attention as $m\to\infty$
- Positive features: no negative weights, no near-zero normalisers, stable training
- Linear $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

**Limitations**

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

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

- A. Because sin/cos features are biased
- B. Because positive features never give negative weights and have small error exactly where the kernel value is small, which is most of each attention row
- C. Because positive features need fewer FLOPs per feature
- D. Because sin/cos features cannot be used with a causal mask

**Answer:** B. Because positive features never give negative weights and have small error exactly where the kernel value is small, which is most of each attention row — Both estimators are unbiased. By Lemma 2, the positive estimator's MSE scales with $\mathrm{SM}^2$, and the trigonometric one's with $\mathrm{SM}^{-2}$. Small kernel values, which dominate attention rows, are estimated well by the first and badly by the second. Trig estimates can also be negative, which can make a row's normaliser near zero and the weights explode.

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

- A. Exact orthogonality of different blocks
- B. That each ωᵢ is still marginally N(0, I_d), so the estimator stays unbiased
- C. That all ωᵢ have unit norm
- D. That the features sum to one

**Answer:** B. That each ωᵢ is still marginally N(0, I_d), so the estimator stays unbiased — A Gaussian vector is a uniformly random direction times an independent $\chi_d$ length. Orthogonalising changes the joint distribution of the directions (reducing variance) but not each one's marginal, so with Gaussian lengths every $\omega_i\sim\mathcal N(0,I_d)$ and $\mathbb E[\phi(x)^\top\phi(y)]=\exp(x^\top y)$ still holds.

**Key points**

- FAVOR+: $\exp(x^\top y)=\mathbb E_\omega[\phi^+(x)^\top\phi^+(y)]$ with $\phi^+(x)=e^{-\lVert x\rVert^2/2}(e^{\omega_i^\top x})_{i\le m}/\sqrt m$, $\omega\sim\mathcal N(0,I)$, $x=q/d^{1/4}$; attention $=\phi(Q)(\phi(K)^\top V)$ normalised, $O(nmd)$.
- MSE: positive $\propto\mathrm{SM}^2(1-e^{-\lVert x+y\rVert^2})$, trigonometric $\propto\mathrm{SM}^{-2}$; positive features are accurate on small kernel values and never negative.
- Orthogonal $\omega$ blocks with $\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^{\lVert x+y\rVert^2/2}/\sqrt m$: large query and key norms (peaked attention) are the hard case.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
