The first step and all the others: prefill and decode

Last post ended with something odd left sitting in the code. The first call takes the whole prompt and fills the square in one go. Every call after it takes a single token and fills one row. Same model, same weights, same code path, two completely different shapes of computation.

That difference is new. It did not exist one post ago.

Without a cache, every step ran the whole sequence from the beginning. Step one processed one position, step two processed two, step two hundred processed two hundred. Each step was bigger than the one before it, but they were all the same shape: take everything, run it through, keep the last row. There was no first step. There was a series of steps that grew.

The cache is what split the run in two. It made the first call the only one with any work to do on the prompt, and it made every call after it a single row against a store that already exists. Two kinds of work, out of one change.

They have names. The first call is the prefill. Everything after it is decode.

Two shapes

Both pictures are one step of the same block. What changed is where the work sits.

The horizontal edges are the same width in both, because the sentence is the same length in both. What collapses is everything on the vertical axis. Prefill sends six rows through: six queries, six rows of the square, six outputs, six trips through the MLP. Decode sends one.

Count the newly computed cells on the top and bottom edges and you get the same number as the rows. Six in prefill, one in decode. That is last post’s invariant seen from the other side. A step computes a key and a value for each token it is processing, and it processes exactly as many tokens as it has rows.

There is one more asymmetry, which the pictures do not show. Prefill happens once. Decode happens once per generated token. Last post counted a twenty token prompt and two hundred generated tokens: one prefill, one hundred and ninety nine decodes. Whatever decode costs, it is the cost that gets multiplied.

Most of the model does not know the other tokens exist

To price either shape we need to know what the model actually spends itself on, and the second post answered that already without meaning to.

Attention is the one place in the block where a token’s output depends on other tokens. Everywhere else, each token is handled on its own. Its vector goes into a matrix and comes out the other side, and it would come out the same if the rest of the sentence were deleted.

“Everywhere else” is worth listing, because it is more than it sounds like:

• The four projections. W_q, W_k, W_v and W_o each take one token’s vector and multiply it by a matrix. Two posts ago they were three summaries of one vector plus a way of writing the result back into the stream. Not one of them looks at anything except that vector.
• The MLP. The same thing, wider.

The exception is the square in the middle: q @ k.transpose(-2, -1), and then the multiplication by v. That is the part where tokens meet. It is also the part with no weights in it at all.

The shapes for the model we have been printing:

Qwen3-0.6B    hidden 1024 · 28 blocks · 16 query heads · 8 key and value heads
              head width 128 · MLP width 3072 · vocabulary 151,936

15.73 M parameters in one block, and every one of them sits in a matrix that gets applied once per token. The part of the block that behaves differently contributes none of them.

Which is convenient, because it means a single rule covers essentially the whole parameter budget.

Which makes a step easy to price

For a matrix applied once per token, the arithmetic is one multiply and one add per parameter per token. So for a model with P parameters, in a step carrying T tokens:

arithmetic  =  2 · P · T
bytes read  =  2 · P            (two bytes per parameter)

Read those two lines next to each other. P is in both. T is in only one of them.

The weights come out of memory once per step no matter what. A step carrying one token reads exactly the same bytes as a step carrying a thousand. The arithmetic is the only part of the bill that knows how many tokens turned up.

How many tokens turn up

So what is T?

In prefill, T is the whole prompt. Every token of it goes through every matrix. A five hundred token prompt gives T = 500.

In decode, T is one. A sequence produces one token per step and it cannot produce two, because the second one needs the first. Causality, doing a third job.

Which leaves exactly one way to make T bigger during decode: run more than one sequence at a time. If B sequences are all generating, each contributes its single row and the step carries T = B tokens. Call B the batch.

So the two phases are not two formulas. They are two values of T.

What a step costs on real hardware

A GPU is doing two things at once. It is pulling bytes out of HBM and it is doing arithmetic, and it does not stop one to do the other. So a step cannot finish sooner than whichever of the two takes longer, which gives a floor:

step time  ≥  max( bytes ÷ bandwidth ,  arithmetic ÷ throughput )

Put Qwen3-0.6B on an H100 and both terms turn into numbers.

weights      0.6 B parameters × 2 bytes  =  1.19 GB
arithmetic   2 × 0.6 B × T               =  1.20 · T  GFLOP

H100 SXM     3.35 TB/s   →  1.19 GB comes out of memory in  356 µs
             989 TFLOPS  →  1.20 GFLOP is arithmetic for    1.2 µs

For one decoding token those two sides are 356 µs and 1.2 µs. The entire model was pulled out of memory in order to perform one and a fifth microseconds of arithmetic. The arithmetic units had nothing to do for 99.7% of the step.

Turn it around and ask when the two are equal:

T  =  356 µs ÷ 1.2 µs  ≈  295

The picture is those two lines and their upper edge. Left of the crossing the step time does not move. Whatever you add, the weights still take 356 µs and the arithmetic still finishes inside that. Right of the crossing, every token you add is a token you wait for.

The ratio those two lines are built from has a name. Divide the arithmetic by the bytes and you get how much work a step does for each byte it drags out of memory, which is called its arithmetic intensity. Do that division on the two lines from earlier and P cancels:

2 · P · T  ÷  2 · P   =   T

That is the whole post in one line. The arithmetic intensity of a step is the number of tokens in it. Not the size of the model, not which phase it belongs to, not how long the sentences are. The token count, and nothing else.

The machine has a matching number. Throughput divided by bandwidth, 989 over 3.35, is how much arithmetic an H100 can do per byte it delivers: about 295. Call it B*. Below it a step is memory-bound, because memory is what it is waiting on. Above it a step is compute-bound.

Now substitute.

• Prefill carries a prompt, and prompts run to hundreds or thousands of tokens. T > B*. Compute-bound.
• Decode carries B tokens, where B is however many requests happen to be generating at that moment. Unless that number is in the hundreds, T < B*. Memory-bound.

The familiar claim about the two phases falls out of the substitution. It was never something we had to assume.

What the flat stretch is worth

The flat part on the left deserves its own paragraph, because it is easy to take the wrong thing from it.

Batching does not make decode faster. The step still takes 356 µs. What batching does is make the extra tokens free: the second sequence, and the fiftieth, ride along inside a step that was going to take 356 µs anyway.

The distinction decides what actually improves. Cost per token falls by a factor of B. Latency per token does not move at all. Somebody watching their own text appear sees the same speed whether they are alone on the machine or sharing it with two hundred other people. What changed is how many people the machine can carry at that speed.

The rows gather. Four sequences each contribute one row, the MLP sees a matrix with four rows in it, and that is one matrix multiply over one reading of the weights.

The square does not gather

The squares do not.

Every sequence has its own keys and values and no other sequence can use them. Four sequences decoding is four separate small attention computations, each reading its own store. None of that gets divided by B.

So the two halves of the block behave differently as the batch grows. The weights are read once and split B ways. The caches are read B times and split no ways. And unlike the weights, which are a fixed size forever, every one of those caches gets one column longer on every step.

There are two memory bills, and batching only pays down one of them.

What this does not do yet

• Nothing was measured. Every number above is a datasheet figure and a multiplication. 356 µs is a floor and the real thing is slower: peak throughput is not reachable in practice, the arithmetic inside the square was left out of the count, and so was the cost of reading a sequence’s own cache.
• No account of where the requests come from. Making T = B large needs B requests generating in the same instant. They arrive at different times and they finish at different times, and nothing so far has said who decides which of them go through a step together.
• No account of whether they fit. B caches have to be somewhere, and last post already said what happens to a cache that does not fit.

And there is a third thing, sitting in the gap between the two shapes.

A step takes as long as its slowest part. A five hundred token prefill and a queue of single tokens waiting to decode both want a step. Give them one each and the ones decoding wait for the prefill. Give them one together and the step is as long as the prefill regardless.

Nothing here says which.