How do Performer / Linformer / linear attention reduce $O(n^{2})$ ?

hard

Answer

$\operatorname{exp}(q \cdot k\; / \;\mathrm{sqrt}(d))$
$Linformer: project the sequence-length dimension of K, V from n to a small constant k \to O(n * k * d).$
$Trade-offs: approximation error, sometimes worse quality on long-range benchmarks vs full attention.$

Check yourself — multiple choice

Same as vanilla attention
Kernel approximation (Performer) or low-rank projection (Linformer) → $O(n \cdot d^{2})$ or O(n·k·d) but with approximation
Removes softmax exactly
No trade-offs

Performer / Linformer: kernel or low-rank tricks → linear-in-n attention with approx error.

#attention#efficient-attention#transformers

214 interview questions in this topic.