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.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
The question is a classic interview trap because it pits two intuitions against each other. The first is that O(seq^2) attention must be expensive and must therefore be the bottleneck. The second is that bottlenecks on a GPU are about memory bandwidth, since HBM is the scarce resource. The resolution is that these intuitions are about different quantities. O(seq^2) describes how many floating point operations grow with prompt length. Whether you are compute-bound or bandwidth-bound is decided by arithmetic intensity, the ratio of FLOPs performed to bytes moved.
The key realization is that prefill reuses its bytes heavily. The whole prompt flows through the model in one parallel pass, so every weight you load from HBM is applied to all seq tokens, and every key and value you load is dot-producted against all the query rows. High reuse means high intensity, and high intensity puts you on the compute side of the roofline. Decode does the opposite: one token per step, no reuse, low intensity, bandwidth-bound.
This deep dive builds the roofline picture, computes intensity for both the weight matmuls and the attention block, shows how FlashAttention keeps the quadratic term off HBM, and then draws out the serving consequences for time to first token and chunked prefill.
Arithmetic intensity and the roofline
The roofline model plots achievable performance against arithmetic intensity, defined as FLOPs divided by bytes moved from memory. There are two ceilings. A sloped line is the bandwidth roof: at low intensity you are limited by how fast you can stream bytes. A flat line is the compute roof: at high intensity you are limited by raw FLOPs per second.
The two roofs cross at the ridge point, which equals peak FLOPs divided by peak bandwidth. On an H100 with bf16 tensor cores at roughly 1000 teraFLOPs and HBM bandwidth around 3.35 terabytes per second, the ridge sits near 300 FLOPs per byte. The exact figure shifts with precision: fp8 doubles the FLOP roof and pushes the ridge higher, while fp32 lowers it. Any kernel whose intensity sits above the ridge is compute-bound; below it, bandwidth-bound.
The shape of the curve matters as much as the numbers. A kernel far below the ridge wastes the tensor cores entirely, because they sit idle waiting for HBM. A kernel far above the ridge wastes nothing on the memory side but is gated by the arithmetic units. Real kernels live somewhere on this curve, and an optimization that moves a kernel rightward, toward higher intensity, only helps if the kernel was bandwidth-bound to begin with.
This is the lens for the whole question. We are not asking how many FLOPs prefill does. We are asking how many FLOPs it does per byte it reads, and where that number falls relative to the ridge.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| 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.
- vLLM and SGLang ship chunked prefill in 2026, slicing long prompts so compute-bound prefill interleaves with bandwidth-bound decode and time to first token stays low.
- FlashAttention 3 on H100 keeps the seq^2 score matrix in SRAM, which is exactly why prefill attention stays compute-bound rather than HBM-bound.
What an interviewer would ask next. Try answering before peeking at the approach.
QAt what context length, if any, does prefill flip to bandwidth-bound?
Push on the intensity expression for the attention block. Weight matmul intensity is order seq and grows. Attention intensity with FlashAttention stays bounded by the SRAM tile size but never falls below the ridge for realistic seq. Discuss whether HBM traffic from reading K and V grows faster than FLOPs, and why tiling keeps the ratio compute-side.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases 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.
60 second bullets to scan on the way to the call.
Definition of arithmetic intensity and the roofline ridge point
Why O(seq^2) is a FLOP count and not a byte count
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.