Module 3 · Inference engineering · Chapter 35 · Free
How an LLM generates text: prefill, decode and the KV cache
- A chatbot reads your whole question first, then writes the answer one small piece at a time.
- Long questions make the first word slow. Long answers make the whole reply slow.
- The model keeps saved notes about the text so far, and those notes eat memory.
The one picture to remember: a reader who puts a sticky note on every page, so no page is read twice.
- A lawyer pastes in a 30-page contract. She waits a long time for the first word.
- Later, ten colleagues join. The small GPU runs out of memory for their chats.
- Kavish must explain why one system is slow in two different ways.
- Learn the basic idea: the model guesses one piece at a time.
- See why it saves sticky notes (the KV cache) instead of re-reading.
- Follow one guess through the model, step by step.
- See the two phases of an answer: prefill and decode.
- Watch one answer being written in a small animation.
- Do the memory maths: how many chats fit on one GPU?
- Go back to Kavish's law firm and fix both problems.
After this chapter you can:
- Explain why a chatbot has a slow start and a slow finish.
- Say what the KV cache is, and why it eats memory.
- Ask a customer three questions before you size any hardware.
Next: you will see these five words on every page below, so here they are once. Other words are explained where they first appear.
Words you'll meet
- Token
- A small chunk of text, like a short word or part of one. Example: "unhappy" may be two tokens, "un" and "happy".
- Prompt
- The text you send in: your question and any pasted pages. Example: a contract plus "Summarise this".
- Prefill
- The reading phase. The model reads the whole prompt first. Example: reading a 30-page contract before answering.
- Decode
- The writing phase. One new token at a time. Example: an answer of 800 tokens means 800 decode steps.
- KV cache
- Saved notes about the text so far. KV means key and value. Example: a short note for every token already read.
- Context
- Everything the model is holding in view for this request: your prompt plus its own answer so far. Example: a 30-page contract plus 3 lines of reply.
- Latency
- How long you wait. Example: the pause before the first word appears.
- GPU memory
- The fast memory on the graphics chip that holds the model and its notes. Example: an 80 GiB card. When it is full, new requests wait.
- Batch
- Several chats served by the GPU at the same time. Example: 8 people asking at once share one pass.
Next: the first idea. How does a model write text at all? Think of the keyboard on your phone.
Step 1: The model guesses one piece at a time
Your phone suggests the next word from what you typed. A language model does the same, far better.
- It guesses one token.
- It adds that token to the text.
- It guesses again, using the longer text.
This loop is the whole story of text generation. Everything else in this chapter is about doing the loop fast, and about what it costs.
Where the phone-keyboard picture breaks down:
- A phone looks only at your last word or two.
- An LLM looks back over everything in the chat.
- A phone offers three guesses. The model picks one, and that pick becomes part of its next input.
Next: looking back over everything sounds slow. Step 2 shows the trick that makes it fast, and the price of the trick.
Step 2: Sticky notes, so no page is read twice
Imagine a reader who must write one new word, using six pages as background.
- Without notes, the reader re-reads all six pages for every new word.
- With notes, the reader puts one short sticky note on each page, once. After that, only the notes are read.
The saved notes are the KV cache. Click through the picture.
- To write one word the reader goes through all 6 pages. For the next word, all 6 again. The work repeats and the delay grows.
- The reader puts a short note on each page the first time through. The pages never change, so the notes stay correct.
- For the next word, the reader reads only the 6 short notes and adds one more. Nothing is read twice.
- Every note must be kept. More pages and more readers mean more notes, which means more memory. Step 6 puts numbers on this.
What you are looking at: two readers side by side. Click Next to move from the slow way to the fast way, and then to its cost.
Where the sticky-note picture breaks down:
- Notes are far cheaper than re-reading, but they still take memory.
- Real notes are lists of numbers, not words you could read.
- Real models keep one set of notes per layer, not just one per page.
Next: now you know the idea. Step 3 follows one single guess through the model, so you see where the notes are saved and read.
Step 3: Follow one guess through the model
The model is a chain of boxes. Words go in at the left. One new word comes out at the right.
Then that word goes back in, and the chain runs again. Every box here runs once per token.
The middle box does attention. The new token looks back at earlier ones and decides which matter. Then the model rates each possible next word with a score. The top score wins. Click through one round.
- "See you" is cut into tokens. Each becomes a list of numbers, because a GPU can only do arithmetic.
- The layers let the newest token look back at the earlier ones. They read the saved notes and add one new note for this token.
- Each possible next word gets a score. The top one ("soon") is picked and shown to you.
- The picked word goes back in as new input, and the loop starts again. This same trip runs for each prompt token in prefill, and for each new word in decode (Step 4).
What you are looking at: one trip through the model. The arrow along the bottom is the loop that repeats it for every new word.
Next: the loop above runs once per new word. But the very first trip is special, because the whole prompt must be read. Step 4 splits the work into two phases.
Step 4: Two phases, a slow start and a slow finish
This is the answer to Kavish's puzzle. The work comes in two phases.
- Prefill reads the prompt. All prompt tokens are known, so they are handled together.
- Decode writes the answer. Each new token needs the one before it, so they come one by one.
A long prompt delays the first word. A long answer delays the last word.
- All 8 prompt tokens exist before anything is written. Nothing has to be guessed yet.
- Because no token depends on a guess, the GPU reads all 8 in one big pass. It also writes a note for each one. A longer prompt means a longer pass.
- The first answer word ("Fast") appears only after prefill is done. This is why a long contract delays the first word.
- Each new word needs the word before it as input. The steps cannot run at the same time. A long answer means many steps.
What you are looking at: the same eight prompt tokens as in the animation below. Wide box means "together". Small boxes in a row mean "one after another".
Next: you have read the story. Now watch it happen in a small animation.
Step 5: Try it: watch one answer being written
Why this exercise: to see prefill and decode with your own eyes, and to see the notes (KV cache) fill up one slot at a time.
The model behind it is a toy. It follows two made-up rules, in milliseconds (ms):
- Prefill time = 40 + 0.9 x prompt tokens. That is 40 ms fixed set-up, plus 0.9 ms for each prompt token.
- One decode step = 30 + 0.01 x prompt tokens. That is 30 ms fixed set-up, plus only 0.01 ms for each prompt token.
- At 4,000 tokens: prefill = 40 + 3,600 = 3,640 ms. One decode step = 30 + 40 = 70 ms.
The numbers are illustrative, not a real measurement. The boxes show 8 tokens as a sample. The clock uses your slider value.
Do this (the lab is right below):
- Press Next step once. This is prefill. In the row "KV cache", all 8 slots fill at once. Expect a short bar (about 47 ms).
- Keep pressing. Each press is one decode step. One more KV cache slot fills each time. Each bar is about 30 ms.
- Press Reset. Drag the slider to 4,000. Press Next step once. Expect a prefill bar of about 3,640 ms.
- Press Next step again. The decode bar is only about 70 ms. Compare the two bars.
Autoplay presses Next step for you, about once a second, until the answer ends.
Generation animation (all times illustrative)
Drag to make the prompt longer and watch the prefill bar grow. The boxes stay the same.
Row 1: prompt tokens, then generated tokens
Row 2: KV cache (one sticky note per token held)
Row 3: time per step (illustrative milliseconds)
- The prefill bar grows with prompt length. The decode bars barely move.
- Each decode step adds one new note to the cache.
- The cache only grows. Nothing is removed while the chat goes on.
Optional: the lab's numbers without the lab
Check the toy formulas by hand, in milliseconds (ms):
- Prefill = 40 + 0.9 x prompt tokens.
- Each decode step = 30 + 0.01 x prompt tokens.
| Prompt tokens | Prefill | One decode step |
|---|---|---|
| 8 | 47 ms | 30 ms |
| 400 | 400 ms | 34 ms |
| 4,000 | 3,640 ms | 70 ms |
A longer prompt makes the first word slower. It barely changes each later word.
Nearly all the time goes to the 800 decode steps. Shorter answers remove steps directly.
Next: that explains the slow start and the slow finish. The law firm's other problem was memory, and the notes (KV cache) are the cause. Step 6 does the maths.
Step 6: Do the maths: how many conversations fit?
Weights are loaded once. The notes grow with every token of every chat. So the notes decide how many people fit on one GPU.
Let's work it out together. All numbers are made up to show the method.
- The GPU has 80 GiB of memory.
- The model's weights take 16 GiB.
- Left for notes: 80 - 16 = 64 GiB.
- One token's notes: 2 x 32 x 8 x 128 x 2 bytes = 131,072 bytes. That is 128 KiB (1 KiB is 1,024 bytes, 1 GiB is about a million KiB).
- One 8,000-token chat: 8,000 x 128 KiB = about 1 GiB.
- Chats that fit: 64 GiB / 1 GiB = 64.
So the answer is about 64 chats, and fewer in practice. The model also needs some working space, and real chats vary in length.
The five factors in step 4, in order:
| Factor | Meaning |
|---|---|
| 2 | a key note and a value note |
| 32 | layers |
| 8 | KV heads (separate ways of looking back) |
| 128 | numbers in each list |
| 2 | bytes per number |
Where does 2 x 32 x 8 x 128 x 2 come from?
- 2: one key note and one value note.
- 32: layers, each keeps its own notes.
- 8: KV heads. Each head is one separate way of looking back at earlier tokens.
- 128: numbers in each list.
- 2: bytes per number.
- The model must be loaded before it can work. Its 16 GiB is the same for 1 chat or 100.
- 80 - 16 = 64 GiB. Only this part can grow with people and chat length.
- One chat of 8,000 tokens adds about 1 GiB of notes. The first chat takes a thin slice.
- At 64 chats, 64 GiB is used. In practice fewer fit, because the model needs working space and chats vary in length.
- When the room is used up, new requests fail or must wait. A faster GPU with the same memory would not help.
What you are looking at: one memory bar. The dashed part is room for notes, and the orange part fills one chat at a time.
Next: now we use these numbers to decide whether a faster GPU would have saved Kavish. It helps with one of his two problems, and not the other.
Step 7: Back to Kavish: fixing both problems at the law firm
The firm's GPU is small: 24 GiB (made up). Weights take 16 GiB, so only 8 GiB is left for notes.
- Slow first word: prefill. A 30-page contract is a long prompt.
- The crash: the lawyer plus ten colleagues is 11 chats. At about 1 GiB each, they need 11 GiB. Only 8 GiB is free.
- Situation: one lawyer ran fine. Ten more join with 8,000-token chats.
- Decision: buy a faster GPU, or check memory first?
- Answer: check memory first. 11 chats need about 11 GiB of notes, and the GPU has 8 GiB. A faster chip has the same 8 GiB.
- Fix for memory: fewer or shorter chats at once, or a GPU with more memory. An 80 GiB GPU holds about 64 such chats.
- Fix for the slow first word: send only the relevant pages instead of the whole contract, or use a smaller model. Prefill time follows prompt length.
Mix-ups to avoid
- "The model reads my prompt one word at a time." No. Prefill reads the whole prompt together. Only writing is one at a time.
- "The KV cache is what the model knows." No. What it knows is the weights. The cache is just notes on this chat.
- "A faster GPU fixes everything." No. A full memory or a very long answer needs other fixes.
Recap
- The model writes one token at a time.
- Prefill reads the prompt and delays the first word. Decode sets the total time.
- The KV cache saves work but grows with chat length and people connected.
- Fixes: trim the prompt for a faster first word. Cap chats or add memory for a full cache.
That is why the lawyer waited (prefill) and why ten colleagues broke it (the cache needed 11 GiB and only 8 GiB was free).
- Imagine a customer says "the bot feels slow".
- You ask the three questions. Prompts are short, answers are long, and 50 people chat at once.
- Now you know where to look: the many decode steps, and the memory for 50 sets of notes.
Optional: why these three
- Prompt length drives prefill, the wait for the first word.
- Answer length drives decode, the wait for the rest.
- People at once drives how much cache memory you need.
Sources and a disclaimer
This chapter follows the topic order of the book Inference Engineering by Philip Kiely (Baseten Books): sections 2.1 Neural Networks and 2.2 LLM Inference Mechanics (2.2.1 to 2.2.4). The book is at baseten.co/inference-engineering. This course is independent material, not endorsed by the author or Baseten, and all explanations and numbers here are our own. For the engine view, see the vLLM documentation and its design notes on paged attention.Next in the course: why batching makes this cheaper, and what to do when memory runs out. Get the full course.
Next: Chapter 36, "Compute-bound vs memory-bound: finding the bottleneck", shows why prefill and decode run into different limits, and how to tell which one you hit. First, check what you learned.
Chapter quiz
Four questions. Score 70% or more to mark this chapter complete.