The Quadratic Cost of Attention

Doubling the length of the text you feed a transformer does not double the work it has to do — it roughly quadruples it. That single fact explains why early transformers were capped at a few hundred or a couple thousand tokens of context, why "long-context" models were a genuine research problem rather than a solved detail, and why an entire family of alternative attention mechanisms exists purely to work around it. The cause is structural, not a bug: self-attention is defined as every token comparing itself against every other token, and the number of pairs in a sequence of length $n$ grows as $n^2$.

The analogy: a round-robin conversation versus a broadcast

If 10 people are in a room and everyone wants to have a private one-on-one conversation with everyone else at some point, that's $\binom{10}{2} = 45$ conversations. With 20 people it's $\binom{20}{2} = 190$ — not double, more than quadruple. That is exactly the shape of attention: every token "talks to" every other token by computing a similarity score, so the number of scores to compute doesn't scale with how many tokens there are, it scales with how many pairs of tokens there are.

Where the $n^2$ actually comes from

$$S = QK^\top$$

In words: $Q$ is an $n \times d_k$ matrix of query vectors (one row per token), $K$ is an $n \times d_k$ matrix of key vectors. Multiplying $Q$ by $K^\top$ produces an $n \times n$ matrix $S$ — one entry for every possible (query token, key token) pair. That matrix has $n^2$ entries no matter how you compute it, and it must be fully formed (or tiled through, as in FlashAttention and IO-Aware Attention) because attention needs every token's relevance to every other token before it can decide how much to weight each one.

The compute cost of forming $S$ is $O(n^2 d_k)$ multiply-adds, and the memory cost of storing it — even briefly — is $O(n^2)$ numbers. Everything downstream (softmax, multiplying by $V$) inherits that same $n^2$ shape.

Worked example 1: counting entries directly

At $n = 512$ tokens, the attention matrix has $512^2 = 262{,}144$ entries per head. Double the sequence to $n=1{,}024$: $1{,}024^2 = 1{,}048{,}576$ entries — exactly 4×, not 2×, confirming the quadratic relationship directly by counting. At $n = 8{,}192$ (a modest "long context" length): $8{,}192^2 \approx 67$ million entries, per head, per layer — for a 32-layer, 32-head model, that's over 68 billion entries if every one were materialised simultaneously.

Worked example 2: compute cost scaling in a table

Fixing $d_k = 64$ and counting multiply-adds for forming $S$ alone ($n^2 d_k$):

Sequence length $n$	$n^2$	Multiply-adds ($n^2 \times 64$)
512	262,144	16.8 million
2,048 (4×)	4,194,304	268 million (16×)
8,192 (4× again)	67,108,864	4.3 billion (16×)

Each time sequence length quadruples, the compute for this one step increases by 16×, not 4× — confirming that cost scales as the square of length, so a model handling documents instead of paragraphs pays a punishing, accelerating tax on every doubling of context.

Drag the coefficient above and watch how steeply the curve bends upward — that shape, compute or memory plotted against sequence length, is literally what the $n^2$ term in attention looks like; a linear-cost method would instead trace a straight line on the same axes.

What this means in practice

The $n^2$ cost is why "just feed the whole document in" was infeasible for years, and why a whole ecosystem of fixes exists at different layers: FlashAttention and IO-Aware Attention makes the existing $O(n^2)$ computation run fast without changing its asymptotic shape, while Sparse Attention: Longformer and BigBird and Linear Attention and Kernel Feature Maps change the algorithm itself to avoid computing all $n^2$ pairs in the first place. Choosing between them is an active engineering decision every team serving long-context models has to make, trading off exactness, memory, and latency.

Practice

1. If forming the attention matrix at $n=1{,}000$ takes 1 second, roughly how long would you expect it to take at $n=10{,}000$, assuming pure $O(n^2)$ scaling with no other bottlenecks?
2. Why does restricting attention to a fixed-width local window (as in worked example's right-hand diagram) change the cost from $O(n^2)$ to $O(n)$?