performer
**Performer** is an efficient Transformer architecture that approximates softmax attention using random feature maps through the FAVOR+ (Fast Attention Via positive Orthogonal Random features) mechanism, achieving linear O(N·d) complexity in sequence length while providing an unbiased estimator of the full softmax attention matrix. Performer decomposes the softmax kernel into a product of random feature maps, enabling the attention computation to be rearranged for linear-time execution.
**Why Performer Matters in AI/ML:**
Performer provides a **theoretically principled approximation to softmax attention** with provable approximation guarantees, enabling linear-time Transformer training and inference without sacrificing the softmax attention's non-negative weighting and normalization properties.
• **FAVOR+ mechanism** — Softmax attention is approximated via random features: exp(q^T k/√d) ≈ φ(q)^T φ(k), where φ(x) = exp(-||x||²/2)/√m · [exp(ω₁^T x), ..., exp(ω_m^T x)] uses m random projection vectors ω_i ~ N(0, I_d); the positive random features ensure non-negative attention weights
• **Orthogonal random features** — Using orthogonal (rather than i.i.d.) random projection vectors reduces the variance of the kernel approximation, providing tighter approximation bounds with fewer features; orthogonalization is achieved via Gram-Schmidt on the random vectors
• **Linear complexity derivation** — With feature maps φ(·) ∈ ℝ^m, attention becomes: Attn = diag(φ(Q)·(φ(K)^T·1))^{-1} · φ(Q) · (φ(K)^T · V); computing φ(K)^T · V first (m×d matrix) then multiplying with φ(Q) (N×m) costs O(N·m·d) instead of O(N²·d)
• **Bidirectional and causal modes** — The FAVOR+ mechanism supports both bidirectional (encoding) and causal (autoregressive) attention; causal mode uses prefix sums to maintain the causal mask while preserving linear complexity
• **Approximation quality** — The quality of approximation improves with more random features m; typically m=256-512 provides good accuracy for d=64-128 dimensional heads, with the error decreasing as O(1/√m)
| Parameter | Typical Value | Effect |
|-----------|--------------|--------|
| Random Features (m) | 256-512 | More = better approximation, higher cost |
| Orthogonal Features | Yes | Lower variance, better quality |
| Complexity | O(N·m·d) | Linear in N |
| Memory | O(N·d + m·d) | Linear in N |
| Softmax Approximation | Unbiased | Converges to exact with m→∞ |
| Causal Support | Yes (prefix sums) | Autoregressive generation |
**Performer provides the theoretically rigorous framework for linear-time attention through random feature decomposition of the softmax kernel, demonstrating that softmax attention can be approximated with provable guarantees while enabling linear complexity in sequence length, making it a foundational contribution to efficient Transformer design.**