The n² is the size of the attention score matrix QKᵀ: every query key pair gets one entry. Both compute and memory scale quadratically with sequence length.
Imagine a roomful of people where everyone has to shake hands with everyone else and remember each handshake. With 10 people you get 100 handshakes; with 100 people you get 10,000. The work grows with the square of the headcount, not the headcount itself. Attention does the same thing, every token has to look at every other token, so the bookkeeping for a length-n sequence is shaped like an n by n grid. That n by n grid is the n² you keep hearing about.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
The O(n²) scaling is the single biggest architectural cost in modern transformers, and most of what's interesting about long context serving, FlashAttention, PagedAttention, ring attention, sparse layouts, exists to manage it.
The goal of this deep dive is to pin down exactly where the n² lives, separate compute complexity from memory complexity (FlashAttention is built on that split), and then walk the production hierarchy of fixes from kernel-level tiling all the way up to multi-million token serving on TPU pods.
A cleanly understood n² is what lets you reason about whether a 128k context is cheap, whether a 1M context is achievable, and which knobs (kernel, layout, sparsity, recurrence) you'd actually turn first.
Where the n² lives inside the attention block
Q is shape (n, d), K is shape (n, d), and the matmul QKᵀ produces an (n, n) matrix. Each entry is one d-dimensional dot product, so the matmul alone is n² · d FLOPs and n² · 2 bytes in BF16.
The softmax is also O(n²), it normalizes every row of an n by n matrix. The value weighted sum, scores times V, is another O(n² · d) of compute, though its output is only (n, d) so the output memory is linear.
The three costs that compound
- QKᵀ matmul: n² · d compute, n² memory for the score matrix.
- Softmax: n² compute and memory in place.
- scores · V: n² · d compute, but only n · d of new output memory.
The score matrix from step 2 must stay alive in memory during step 3, so peak memory is governed by the n² intermediate, not by any single sub-step.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| Approach | Compute | Memory | Exact? |
|---|---|---|---|
| Standard attention | O(n²·d) | O(n²) | Yes |
| FlashAttention | O(n²·d) | O(n) | Yes |
| Sliding window (w) | O(n·w·d) | O(n·w) | Within window only |
| Linear attention | O(n·d²) | O(n·d) | No (kernel approx) |
| Mamba / SSM | O(n·d²) | O(n·d) | No (recurrence) |
Real products, models, and research that use this idea.
- FlashAttention v2 and v3 are the default attention kernels in PyTorch SDPA and JAX as of 2026 and underlie every major training run.
- vLLM's PagedAttention is the standard KV-cache manager for high-throughput serving of Llama 4 Maverick, DeepSeek V4, and Qwen 3.5.
What an interviewer would ask next. Try answering before peeking at the approach.
QIf FlashAttention has the same O(n²) compute but is 2-4× faster wall clock, what does that tell you about where attention's bottleneck actually was?
Attention was memory bandwidth bound, not compute-bound, on modern GPUs. The HBM-to-SRAM round trip for the n² intermediate dominated wall clock. FlashAttention tiles Q, K, V into SRAM-resident blocks and fuses score + softmax + value-sum, slashing HBM traffic. FLOP count unchanged; bytes-moved count drops by orders of magnitude.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Confusing the n² compute cost with the parameter count. Attention has O(d²) parameters per layer (the projection matrices), independent of sequence length. The n² is purely about the sequence-axis interaction.
60 second bullets to scan on the way to the call.
Where the n² lives inside the QKᵀ matmul
Compute complexity versus memory complexity for standard attention
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.