Why is attention O(n²)? What are FlashAttention and other long-context techniques?

30-second answerSay your answer out loud first, then reveal.

Every token attends to every other token, so the score matrix is n × n: compute and naive memory grow quadratically with sequence length. FlashAttention computes exact attention without materialising the full n × n matrix in slow GPU memory, by tiling the computation in fast on-chip SRAM. That gives large speed and memory gains for the same result. Other approaches change the attention itself (sliding window, sparse, linear attention or state-space models), trading exactness for scalability.

Cost of standard attention

Compute: O(n² · d) per layer.
Memory for scores: O(n²) per head. At n = 128K, 128K² ≈ 16 billion entries per head per layer, which is impossible to store naively.

FlashAttention (Dao et al. 2022; v2, v3)

Key insight: attention is memory-bandwidth bound. The bottleneck is moving data between HBM (large, slow) and SRAM (small, fast).
Tiles Q, K and V into blocks, computes the softmax incrementally (online softmax), and never writes the full score matrix to HBM.
Exact attention, not an approximation. Memory is linear in n, and it's several times faster.
Standard in modern training and inference stacks.

Other long-context techniques

Technique	Idea	Trade-off
Sliding-window attention	Each token attends to the last W tokens	Loses direct long-range links (stacking layers extends reach)
Sparse / block-sparse attention	Attend to selected positions	Pattern design; may miss information
Linear attention / SSMs (Mamba) / hybrids	O(n) recurrent-style mixing	Recall over long contexts can be weaker; hybrids help
Ring attention / context parallelism	Split long sequences across GPUs	Communication overhead
RoPE scaling (YaRN etc.)	Extend positional range (Q40)	Needs some fine-tuning

PreviousWhat is the KV cache? Why is it needed, and how do you calculate its memory?

This is what real progress feels like.

Why is attention O(n²)? What are FlashAttention and other long-context techniques?

Cost of standard attention

FlashAttention (Dao et al. 2022; v2, v3)

Other long-context techniques

Related