The Quadratic Cost of Attention

"Attention is quadratic in sequence length" gets repeated so often it becomes background noise, a fact you know without necessarily knowing why. The quadratic term is not a vague scaling law; it comes from one specific step in the attention computation, it shows up in both compute and memory, and understanding exactly where it lives is what makes the entire family of long-context and efficient-attention techniques legible as targeted fixes rather than unrelated tricks.

Where the n-squared actually comes from

For a sequence of length n, computing Q K^T multiplies a (n, d_k) matrix by a (d_k, n) matrix, producing an (n, n) matrix of pairwise scores, one score for every pair of positions. That matrix has n^2 entries. Every subsequent step, the softmax, the multiplication by V, operates on or produces something of that same n^2 shape. Double the sequence length and the score matrix has four times as many entries, so both the arithmetic to fill it and the memory to store it roughly quadruple, not double. This is genuinely different from the rest of the transformer: the feed-forward network (see feedforward-swiglu) and the linear projections that build Q, K, V all scale linearly in n, because they process each position independently. Attention is the one operation in the block that looks at every pair of positions, and that pairwise structure is exactly what produces the quadratic term.

Two separate quadratic costs

The n^2 term shows up twice, and the two instances hurt differently:

• Compute (FLOPs). Filling and processing the (n, n) score matrix takes O(n^2 * d_k) floating point operations per head. At short sequence lengths this is dwarfed by the FFN's compute; at long sequence lengths it comes to dominate, because the FFN's linear-in-n cost cannot catch up to attention's quadratic growth no matter how large n gets.
• Memory. Materialising the full (n, n) score matrix, one row per query position, at 16- or 32-bit precision, per head, per layer, is what actually causes out-of-memory errors on long sequences well before compute becomes the binding constraint. Dao et al., 2022 (FlashAttention, see flash-attention) attacks specifically this memory cost, using a blockwise, online-softmax computation that never materialises the full matrix, while still computing the exact same mathematical result. It reduces memory pressure and, by avoiding repeated reads and writes to slow GPU memory, often reduces wall-clock time too, but it does not change the underlying O(n^2) FLOP count; the compute cost is still quadratic, just executed more efficiently.

Why this matters more at inference than training might suggest

During training, sequences are typically capped at a fixed length and processed as fixed-size batches, so the quadratic cost, while real, is a known, budgeted quantity. At inference, especially for models advertised with 100k or 1M token context windows, users push sequence length far past typical training lengths, and the quadratic cost of the prefill step, encoding the entire prompt before generation begins, becomes the dominant latency and memory cost of a request. A 10x longer prompt is not 10x more prefill compute; it is roughly 100x more.

The response: attack n, not the exponent

Nobody has found a way to make exact softmax attention over all pairs sub-quadratic; the n^2 term is a direct consequence of computing every pairwise interaction, and computing every pairwise interaction is definitionally an O(n^2) amount of work. So the field's response has mostly been to avoid computing all n^2 pairs at all: sliding-window-attention restricts each position to a fixed-size local window, making the cost linear in n at the price of unbounded direct lookback; sparse attention patterns compute only a structured subset of pairs; and linear-attention and state-space approaches (Mamba and relatives) replace the pairwise comparison with a different mechanism entirely, trading some quality or generality for genuinely linear scaling. See context-windows-long-context for how these tradeoffs play out at the level of a full model's advertised context length.

When it falls down

• "Quadratic" understates short-sequence reality. At the sequence lengths most requests actually use, a few hundred to a few thousand tokens, the FFN's linear cost, not attention's quadratic cost, is often the larger share of total compute. The quadratic term dominates specifically at long lengths; treating attention as the bottleneck for every workload is a common overgeneralisation.
• FlashAttention fixes memory, not the FLOP count. It is easy to conflate "FlashAttention makes attention fast" with "FlashAttention makes attention sub-quadratic." It does the former by avoiding memory-bound overhead, not the latter; the number of floating point operations required is unchanged.
• Approximate long-context methods trade away guarantees. Sliding windows and sparse patterns make the cost linear by simply not computing some pairwise interactions. That is a real information loss, not a free optimisation, and which interactions get dropped determines what the model can and cannot still do well.

Further reading

• Vaswani et al., 2017, Attention Is All You Need, arXiv:1706.03762 - the original scaled dot-product attention whose pairwise score matrix produces the quadratic term.
• Dao et al., 2022, FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, arXiv:2205.14135 - attacks the memory side of the quadratic cost without changing the FLOP count.