Attention's Quadratic Tax
Lesson 2 of 3 in Architecture in Production: Design Choices Set Your Bill.
Serving a Transformer is two different jobs stapled together. Prefill ingests the prompt: every prompt token is already known, so the model processes them in parallel — one giant dense pass that computes attention scores between every pair of prompt positions and fills the KV cache. Decode then generates: one token per step, strictly sequential, each new token attending (under Causal masking) over everything before it by reading that cache.
The two phases stress opposite hardware limits, and the modern serving playbook (Pope et al., 2022) is built on the asymmetry. Prefill is compute-bound: thousands of tokens’ worth of matrix multiplies saturate the accelerator’s arithmetic units. Decode is memory-bandwidth-bound: each step performs comparatively little arithmetic but must stream the Weights and the entire cache past the compute units to emit a single token. An accelerator that is FLOPs-starved during prefill sits arithmetic-idle during decode, waiting on memory.
Log–log line chart of FLOPs per layer versus sequence length, from 1,024 to 131,072 tokens. Two lines: the linear projection-and-FFN term starts about 24 times higher and grows with slope 1; the quadratic attention term grows with slope 2, crossing the linear term at about 24,600 tokens and ending roughly 5 times higher at 131,072 tokens.
Read the chart the way a capacity planner would. The linear term — the weight matmuls: projections plus FFN — dominates at everyday prompt lengths. The quadratic term — building and applying the attention matrix — starts roughly 24× lower and overtakes only around n = 6 × d_model tokens (about 24k for the 4096-wide configuration shown). Two practical readings follow.
First, the quadratic tax is real, but it is not why your 2,000-token prompt feels slow — at short lengths prefill cost is essentially proportional to prompt length, because weight work dominates. Second, at genuinely long context the tax compounds fast: past the crossover, doubling the prompt roughly quadruples the attention work — and this, together with the large cache the prompt leaves behind, is the mechanical reason long-context requests are treated as a different workload class everywhere: separate queues, separate limits, and, as the next lesson shows, separate prices.
Attention FLOPs, counted
Count one multiply–accumulate as 2 FLOPs, let n be sequence length and d the model width, and assume the usual 4× FFN expansion. Processing an n-token sequence, one layer costs:
- Q, K, V, and output projections — four
d × dmatrices applied to n tokens →8·n·d² - FFN — two matrices of shape
d × 4d→16·n·d² - Attention scores (Q·Kᵀ) — n² query–key dot products whose lengths sum to
dacross all heads →2·n²·d - Applying scores to values (A·V) — the same shape again →
2·n²·d
Total ≈ 24·n·d² + 4·n²·d per layer; softmax, norms, and biases are lower-order. The ratio of quadratic to linear work is (4·n²·d) / (24·n·d²) = n / 6d — the quadratic term wins once n > 6·d_model, which is the crossover in the figure. This is the same accounting behind the per-token estimate used in the scaling-law literature, C_forward ≈ 2·N + 2·n_layer·n_ctx·d_attn (Kaplan et al., 2020, Table 1 — their d_attn equals d_model in the standard configuration): 2 FLOPs per parameter, plus a context-dependent attention term.
Decode pays the same totals in installments. Generating the token at position t computes one new row of attention — roughly 4·t·d FLOPs per layer — plus the fixed 24·d² of weight work. Sum over t and you reproduce the quadratic total: generation never escapes the tax, it amortizes it one step at a time, which is why the pain surfaces as bandwidth (re-reading a growing cache every step) rather than one compute spike.
The two terms also answer to different levers. MoE shrinks the linear term — active parameters drop, so the d² work falls — and leaves the quadratic term alone. GQA barely changes FLOPs at all, since scores are still computed for every query head; what it slashes is the bytes each decode step must read. FLOPs levers and bandwidth levers are different tools for different phases.
In production
Once you see prefill and decode as different workloads — parallel FLOPs versus sequential bandwidth — several cloud pricing and product mechanics stop looking arbitrary.
AWS
Separate input- and output-token rates are the asymmetry made visible: an input token is prefill work — parallel, amortizable, compute-shaped — while an output token is a decode step that re-reads weights and cache. Prompt caching is the same insight productized: when many requests share a long prefix (a system prompt, a document), its computed KV entries can be stored and reused, skipping that prefix’s prefill entirely — the mechanism behind discounted cached-input tokens. Self-hosting, publish two latency SLOs, TTFT and inter-token latency, because they are set by different resources and tuned by different knobs.
Azure
Provisioned capacity drains asymmetrically. Prompt-heavy traffic — retrieval pipelines stuffing fat contexts, document analysis — consumes the compute side; generation-heavy traffic — long answers, many turns — consumes bandwidth and cache. Two tenants with equal token totals can stress the same deployment in opposite ways. And streaming is a perception tool, not a prefill tool: tokens flow as decode produces them, but nothing flows before prefill ends, so a long prompt still buys a long silent pause.
Google Cloud
Context caching on managed endpoints is stored prefill: pay once to compute a long shared prefix’s KV entries, then reference them across requests. Batch and offline serving modes exist because prefill-heavy work with no TTFT constraint is the cheapest utilization there is — the scheduler can pack prompts wall to wall. For latency-sensitive decode, memory bandwidth per accelerator, not peak FLOPs, is the spec that predicts tokens per second.
Interactive checkpoint quiz (2 questions) — open this page in a browser to take it.