When we say attention is O(n²), the n is sequence length and the n² is specifically the size of the attention score matrix.
Here's where it comes from. Q has shape (n, d_k), one query vector per token. K has shape (n, d_k), one key vector per token. The product QKᵀ has shape (n, n): every Q row dotted with every K row. That's n² entries.
Computing those entries costs roughly `n² · d_k` floating point operations, and storing the matrix costs O(n²) memory. Softmax then runs over the same (n, n) matrix, also O(n²). Multiplying by V is another O(n² · d_v) of compute. The dominant cost in both dimensions is the n² attention matrix.
Doubling the sequence length doesn't double the cost, it quadruples it. At a million tokens, you're looking at 10¹² entries, which doesn't fit anywhere. That quadratic scaling is the entire reason long context attention has its own research lineage (FlashAttention, sparse patterns, linear attention).
The n² is the size of the QKᵀ score matrix, for a length-n sequence, every query key pair gets exactly one score, giving you n² entries.
The canonical formula is:
$$\text{Attn}(Q,K,V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d_k}}\right)V$$
Compute scales as roughly n² times the head dimension, memory scales as n² for storing the score matrix. Double the sequence and cost quadruples.
This is the bottleneck for long context modeling, and it's the motivation behind three different escape hatches: FlashAttention keeps the same arithmetic but kills the n² memory traffic by tiling into SRAM; sparse attention only computes a window of the n² entries; and linear attention approximates the softmax to avoid the n by n matrix entirely. The trade off across them is exactness versus asymptotic cost, FlashAttention is exact, sparse drops attention outside the window, linear is a kernel approximation.
Quick reference
TL;DR
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.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Reasoning about parameter count or model size The n² describes sequence-axis interaction; parameters are O(d_model²) per layer and have no n dependence at all.
Inference cost analysis for decode-stage autoregressive generation With a KV cache, each new token attends to a length-T cache in O(T·d) per layer; the n² shows up only on the prefill pass, not on per-token decode.
Sub-1k-token classification or short-form generation workloads At small n, the projection matmuls O(n·d²) dominate; the n² term is real but not the bottleneck, so optimizing for it adds complexity without throughput wins.
Architectures with structural O(n) attention swaps (Mamba, RWKV, state space hybrids) These replace the n² matrix with a recurrence; the quadratic-cost framing doesn't apply to the swapped layer, though hybrid stacks still pay it on the attention layers they keep.
Quick scan · 2–4 min
Everything important, quickly.
5 min: where the n² lives inside QKᵀ, the difference between compute and memory complexity, the production escape-hatch hierarchy (FlashAttention, PagedAttention, ring attention, sparse patterns), and the parameter count confound to avoid.
Side-by-side
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-world examples
Real products, models, and research that use this idea.
1FlashAttention v2 and v3 are the default attention kernels in PyTorch SDPA and JAX as of 2026 and underlie every major training run.
2vLLM's PagedAttention is the standard KV-cache manager for high-throughput serving of Llama 4 Maverick, DeepSeek V4, and Qwen 3.5.
3Mistral and Gemma 4 use sliding window attention to bound per-layer cost on long context workloads.
4Ring attention is the technique behind Gemini 3.1 Pro's multi-million token context window on TPU pods.
5DeepSeek V4's Native Sparse Attention interleaves local and global attention layers to keep the global-attention bill small.
Interviewer follow-ups
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?
Sign in or go Pro to see the approach for this follow-up.
QWhy don't linear attention variants replace softmax attention in production despite being asymptotically faster?
Sign in or go Pro to see the approach for this follow-up.
QWalk through the memory bill for a 128k-context Llama 4 Maverick forward pass with and without FlashAttention.
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
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.