Why is standard self-attention $O(n^{2})$ in sequence length?

medium

Answer

$n^{2}$
$Then a softmax over n weights per query.$
$O(n^{2}\; \cdot \;d)$
$Fine at n = 512-2048; painful at n = 32k+.$
$Motivates efficient / sparse / linear-attention variants and paging tricks (Flash Attention doesn't reduce complexity but cuts memory dramatically via tiling).$

Check yourself — multiple choice

Attention is O(n)
Every query attends to every key → $n^{2}$ dot products → $O(n^{2} \cdot d)$ compute and memory
Attention is O(1)
Attention is O(n log n)

Self-attention: n queries × n $\mathrm{keys}\; = \;O(n^{2} \cdot d)$ compute + memory.

#attention#transformers#efficient-attention

214 interview questions in this topic.