This is an explainer of the 2020-2021 Performer by Choromanski and colleagues. Its central idea is that attention is order n squared because the softmax couples every query with every key before you can normalize, but exp of q dot k is a kernel, and any kernel can be written as a dot product of feature maps phi of q dot phi of k, and once the query part and key part separate, matrix-multiply associativity lets you sum over all keys once and have every query read the result, collapsing n squared to n without ever forming the attention matrix. It first shows that plain Q K transpose V, without softmax, is associative so you can compute it as Q times K transpose V where K transpose V is only d by d, giving order n d squared which is linear in n; the only reason real attention cannot do this is the softmax, a nonlinear function of the whole n by n matrix that must be built before normalizing, so the softmax is what blocks the reassociation. The kernel trick finds a feature map phi from R d to R m with phi of q dot phi of k approximating exp of q dot k, so the unnormalized attention matrix factorizes as phi of Q times phi of K transpose, and the attention output with normalizer D becomes D inverse times phi of Q times the quantity phi of K transpose V, an m by d summary summed over all keys once, then each query reads it; total cost is order n m d equals order n with memory order n m plus m d and no n by n anywhere. FAVOR plus, Fast Attention Via positive Orthogonal Random features, builds phi by drawing m random projection vectors omega from a standard normal and setting phi of x to exp of minus half norm x squared over root m times the vector of exp of omega i dot x; this is an unbiased estimator because the expectation of phi of q dot phi of k equals exp of q dot k exactly. Two design choices matter: positive features, the exponentials are always positive, avoiding the catastrophic cancellation that earlier trigonometric random-Fourier features cause when approximating a strictly positive kernel with sign-changing terms which can make attention weights negative and destabilize training; and orthogonal features, making the omega mutually orthogonal provably lowers the estimator variance so the same accuracy needs fewer features. Because it is a random estimate, accuracy improves with the number of features m, with error shrinking like one over root m. Caveats: it is an approximation with variance so sharp high-contrast attention distributions are hardest to approximate and may need many features; causal autoregressive attention needs the sum over all keys to become a running prefix sum, linear but with a sequential dependence; and linear attention can lag full attention in quality on tasks needing precise recall, which together with FlashAttention making exact attention cheap kept softmax dominant for mainstream models. In the lineage Performer is the kernel or linear-attention branch, sibling to Linformer’s low-rank compression, both reaching order n by approximating; its lasting contribution is the reassociation trick, replace softmax with a feature map, contract keys and values into a fixed-size state, let queries read it, which is linear attention itself and the direct ancestor of modern linear-attention designs, state-space models like Mamba, and the linear-attention core of Kimi K3. Two interactive widgets let the reader drag the sequence length to compare the exact softmax path that forms the n by n matrix against the kernel path that skips it with their costs, and set a true dot product and number of features to watch the FAVOR plus estimate of exp of q dot k converge as m grows, with a resample button showing the estimator variance.