Why is standard attention O(n²) in sequence length, and what specifically is the n²?

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.