Same topic, related formats. Practice these next.
At first glance, attention's O(seq^2) cost during prefill sounds like it should be the bottleneck. Explain why prefill is actually compute-bound (saturates the FLOP roof) rather than bandwidth-bound, even for long contexts.
Prefill's O(seq^2) cost is FLOPs, not bytes. Every weight and every K and V is reused across many tokens, so arithmetic intensity scales with seq, landing prefill right of the roofline ridge.
Imagine a chef cooking for a banquet. Reading the recipe once, from a far-away shelf, is slow, but the chef then uses that one recipe to cook hundreds of identical plates. The slow shelf trip is amortized over all the plates, so the chef's hands, not the shelf, set the pace. Prefill works like this. The model reads each weight from slow memory once, then applies it to every prompt token at the same time. The expensive bytes are reused many times, so the math units stay busy. Decode is the opposite, like cooking one plate per shelf trip. You keep running back and forth, and the shelf trip dominates. That is why prefill is limited by raw compute while decode is limited by memory speed.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Everything important, quickly.
4 min: arithmetic intensity and the roofline ridge, why O(seq^2) is FLOPs, weight reuse, K and V reuse with FlashAttention, decode as a GEMV, and time to first token plus chunked prefill.
| Property | Prefill | Decode |
|---|---|---|
| Tokens per step | All seq tokens at once | One token |
| Dominant op shape | GEMM (matrix times matrix) | GEMV (matrix times vector) |
| Byte reuse | High; weights and K, V reused across tokens | None; one token per weight read |
| Arithmetic intensity | Order seq, right of ridge | Order one, left of ridge |
| Bottleneck | Compute (FLOP roof) | Memory bandwidth (HBM) |
| Latency it sets | Time to first token | Inter token latency |
Real products, models, and research that use this idea.
What an interviewer would ask next. Try answering before peeking at the approach.
Red flags and common mistakes that signal junior thinking. Click to expand.
Assuming O(seq^2) FLOPs implies a memory bottleneck. Cost scaling is not intensity. The same bytes are reused across many tokens, so intensity scales with seq and prefill saturates compute.
The night-before-the-interview bullets. Scan these on the way to the call.
Primary sources. Skim if you want the original framing.