Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

Prefill and decode in LLM inference

After this lesson: I can explain why decode is limited by reading memory while prefill is not.

60 min lesson2 commandsLLM inference lab: a tiny language model on a CPU, with a KV cache, batching and int8

Why does the first word take longest?

LLM inference is the work a trained language model does to answer you. It happens in two phases: prefill reads your whole prompt, then decode writes the answer one token at a time.

The two phases use a computer very differently. Knowing which one is slow, and why, is the start of every speed-up in this module.

By the end of this lesson

Note

I can explain why decode is limited by reading memory while prefill is not.

Key words

WordWhat it means
Inferencerunning a trained model to get an output
Passone run of the model over some tokens
Prefillthe first pass, which reads the whole prompt
Decodethe later passes, one new token each
Multiply-addone multiplication and one addition, the unit of model work
Memory-boundlimited by reading memory, not by arithmetic

The cells students fill in are left blank in this preview.

Generation is a loop of passes

A model only ever answers one question: what comes next? To write a reply, it runs in a loop. The first pass reads the prompt and gives the first new token. This is prefill.

Every later pass reads the token just made and gives one more. This is decode. A reply of 100 tokens needs one prefill pass and 99 decode passes.

Watch prefill, then decode, in the lab

Command
docker exec jupyter python3 steps/generate.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

What the Run printed

LineWhat it shows
prefill: read 12 tokens of the prompt in one passAll of "the cat sat " in one go
decode step 1 chose 'o'The first new character
decode step 10 chose 't'The text is now "the cat sat on the mat"

The cells students fill in are left blank in this preview.

Try it: count the passes

Code: python
# A stand-in model: a table of which word follows which.
NEXT = {"the": "cat", "cat": "sat", "sat": "on", "on": "the"}

prompt = ["the", "dog", "sat"]
passes = 1  # prefill reads the whole prompt in one pass
words = [NEXT[prompt[-1]]]
while len(words) < 5:
    passes = passes + 1  # each decode pass reads one new word
    words.append(NEXT[words[-1]])
print("new words:", words)
print("passes:", passes)
# Change 5 to 10. How many passes now?

Every pass reads every weight

A model is mostly big tables of numbers called weights. A pass must read every one of them from memory. It does about one multiply-add per weight for each token it reads.

Prefill reads the weights once for the whole prompt, so a 24-token prompt does 24 tokens of work for one read. Decode reads all the weights again to do the work of a single token.

Count the work of each phase

Command
docker exec jupyter python3 steps/phases.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Worked example: the two phases in the lab

PhasePassesMultiply-addsBytes readWork per byte
Prefill, 24 tokens130,29150,5080.6
Decode, 24 tokens24100,680402,7200.2

The cells students fill in are left blank in this preview.

A common mistake

Warning

Many people think decode is slow because it does more arithmetic. Each decode pass does less arithmetic than prefill. It is slow because every pass must read all the weights to make one token. Ask how many bytes a pass reads, not only how many sums it does.

Memory speed sets the best decode speed

A big model has billions of weights. A 7B model has 7 billion. At 2 bytes each, that is 14 GB to read on every decode pass.

If memory delivers 50 GB a second, the best possible is about 3.6 passes a second, however fast the arithmetic is. This is what memory-bound means. This lab's model is only 12 KB, so its counts show the shape, not real speeds.

Try it: the best decode speed

Code: python
# Each decode pass reads every weight once, so memory sets the best speed.
READ_GB_PER_SECOND = 50

models = [["7B at 2 bytes", 7, 2], ["7B at 1 byte", 7, 1], ["1B at 2 bytes", 1, 2]]
for name, billions, bytes_each in models:
    gb_per_pass = billions * bytes_each
    best = READ_GB_PER_SECOND / gb_per_pass
    print(name, "reads", gb_per_pass, "GB a pass, at most", round(best, 1), "tokens a second")
# Change READ_GB_PER_SECOND to 100. What happens to every speed?

About this lab and its source: LLM inference lab: a tiny language model on a CPU, with a KV cache, batching and int8

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.