Attention is quadratic in sequence length. Why is FlashAttention still a major win without changing that?

hard

Answer

$Because the practical bottleneck is memory traffic, not arithmetic.$
$A naive implementation materializes the full attention matrix in high-bandwidth memory, so the cost is dominated by writing and reading a quadratic-sized intermediate.$
$FlashAttention tiles the computation, keeps blocks in on-chip memory, and computes the softmax in a streaming, numerically stable way, so the quadratic matrix never exists in memory at all.$
$Complexity stays quadratic in time but memory becomes linear in sequence length, and wall-clock speed improves several-fold because the kernel is no longer memory-bound.$
$It is exact, unlike sparse or low-rank approximations, which is why it was adopted universally rather than as a quality tradeoff.$

Check yourself — multiple choice

It approximates attention
It removes the memory bottleneck by tiling and streaming the softmax so the quadratic matrix is never materialized — exact results, linear memory, much faster wall clock
It makes attention linear in time
It only helps at inference

The win is in memory traffic and exactness, not in reducing asymptotic arithmetic.

#attention#efficient-attention#transformers

214 interview questions in this topic.