Why does quadrupling a transformer's context length raise attention cost roughly 16x?

## The derivation Self-attention asks, for every token, how much it should read from every token. That is n times n questions. Concretely, for a single head with head dimension d_k: - Computing Q, K and V costs on the order of n * d_model * d_k each — **linear** in n. - Computing Q K^T costs on the order of n * n * d_k — **quadratic** in n. - The softmax touches all n^2 entries — quadratic. - Multiplying the weights by V costs on the order of n * n * d_v — quadratic. - The feed-forward sublayer after attention costs on the order of n * d_model^2 — linear in n. So the block as a whole is linear-plus-quadratic. Double n and the quadratic terms go up 4x; quadruple n and they go up 16x. That is the whole answer, and it is worth being able to say it in that shape rather than by reciting "O(n^2)". ## Making the memory concrete The number that surprises people is not FLOPs, it is activation memory during training. One score matrix at 16-bit precision costs 2 * n^2 bytes, per head, per layer. At n = 1024 with 32 heads that is 64 MB per layer — annoying. At n = 32768 with the same 32 heads it is roughly 64 GB per layer if materialized naively. The model's weights have not changed at all; the activations dwarf them. This is why long context was, for years, a memory problem before it was a speed problem, and why the first serious fixes were about never writing the full matrix to memory rather than about doing less arithmetic. Inference is a different regime. During generation, one new token attends over all previous positions, so per-token attention work is linear in the current length and the total over a full generation is again quadratic — but the memory pressure shifts from score matrices to the stored per-position state, which is a separate subject. ## Why the quadratic term is invisible at short lengths A useful sanity check, and a good senior-level detail: the quadratic term does not dominate immediately. Compare the attention score work, roughly proportional to n^2 * d_model, against the per-token linear work of the projections and feed-forward, roughly proportional to n * d_model^2. The quadratic term overtakes only once n grows to a substantial multiple of the model width. For a model several thousand dimensions wide, that means the block is dominated by the feed-forward and projection matmuls at 2K tokens and by attention at long context. So "attention is the bottleneck" is a statement about a regime, not a universal truth — a candidate who says it unconditionally is over-generalizing. ## The operational consequences This scaling explains several things you see in production: **Pricing and latency are not linear in prompt length.** A prompt four times longer does not cost four times as much time to process; the prefill step grows superlinearly once the context is long enough for the quadratic term to matter. **Long-context training runs hit memory walls that short ones do not.** Sequence length interacts multiplicatively with batch size, head count and depth, so extending context often forces batch size down and changes the optimization setup, not just the compute bill. **Advertised context length is a capability, not a recommendation.** Because cost grows superlinearly while usable quality does not grow proportionally, stuffing a window to its limit is usually the wrong default. Retrieval, summarization and pruning of what actually enters the window are cost decisions as much as quality ones. ## Why this shapes architecture research Every major direction in long-context work is a response to this one term. Broadly: avoid materializing the n-by-n matrix by fusing the computation so it never leaves fast memory; skip pairs entirely with sparsity or locality so the matrix is never dense; compress what each query has to read against; or replace some attention layers with mechanisms whose cost is linear in sequence length. The specifics of those families are their own subject — the point here is that they all exist because of the n^2 term, and being able to name that lineage is what separates a mechanical answer from an architectural one. ## How to answer well Do the arithmetic out loud: n^2 entries, 4x on n gives 16x, both in compute and in activation memory, per head, per layer. Then add the qualifier that shows judgment — the other terms in the block are linear, so the quadratic term only dominates past a length that depends on model width. Then land on the consequence: long context is priced superlinearly and the design question is what deserves to be in the window at all.