Performer and Random-Feature Attention

Standard softmax attention needs the full $n \times n$ matrix of pairwise query-key similarities, which is why its cost scales quadratically with sequence length — every one of the $n$ queries must be compared against every one of the $n$ keys. Performer avoids ever forming that matrix by noting that softmax attention's exponential similarity function can be approximated as a dot product in a different, higher-dimensional feature space: each query and key vector is passed through a random nonlinear projection (a "random feature map"), chosen so that the dot product of two projected vectors approximates the exponential similarity of the two originals, in expectation.

Once queries and keys are replaced by these random features, attention can be rearranged using the associative property of matrix multiplication — computing (keys × values) first, then multiplying by queries — rather than (queries × keys) first, then by values. That reordering is the entire trick: it turns an $n \times n$ intermediate matrix into a much smaller fixed-size matrix, so the total cost becomes linear in sequence length instead of quadratic, at the price of the similarity scores being an unbiased random approximation rather than the exact softmax value.