Deployed Lab

Module 3 · Inference engineering · Chapter 35 · Free

How an LLM generates text: prefill, decode and the KV cache

10 min4 clickable pictures1 generation animation3 checks
In 30 seconds

The one picture to remember: a reader who puts a sticky note on every page, so no page is read twice.

The problem Kavish sets up AI tools at customer sites. A law firm runs an AI model on its own GPU computers (a made-up example).
The plan for this chapter
  1. Learn the basic idea: the model guesses one piece at a time.
  2. See why it saves sticky notes (the KV cache) instead of re-reading.
  3. Follow one guess through the model, step by step.
  4. See the two phases of an answer: prefill and decode.
  5. Watch one answer being written in a small animation.
  6. Do the memory maths: how many chats fit on one GPU?
  7. Go back to Kavish's law firm and fix both problems.

After this chapter you can:

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.

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:

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.

The saved notes are the KV cache. Click through the picture.

Re-reading versus sticky notes Left: without notes, the reader re-reads all six pages for every new word. Right: with a sticky note on each page, the reader reads six short notes and writes one new note. Without sticky notes 6 full pages Need one new word? Read all 6 pages again. Slow, and the work repeats. With sticky notes Need one new word? Read the 6 notes, add 1. Fast, and nothing repeats. + 1 short note per page
  1. 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.
  2. The reader puts a short note on each page the first time through. The pages never change, so the notes stay correct.
  3. For the next word, the reader reads only the 6 short notes and adds one more. Nothing is read twice.
  4. 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:

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.

WordsNumbersModel computePicking
One guess of the next word Words go in and become lists of numbers. The model's layers work on them and read and write the sticky notes, which are the KV cache. One next word is picked, shown to you, and fed back in for the next guess. Words in"See you" Numbersword to list Look back (layers)attention, many rounds Pick a word"soon" scores top New wordshown to you KV cachesticky notes in memory save / read notes
  1. "See you" is cut into tokens. Each becomes a list of numbers, because a GPU can only do arithmetic.
  2. 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.
  3. Each possible next word gets a score. The top one ("soon") is picked and shown to you.
  4. 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.

A long prompt delays the first word. A long answer delays the last word.

Prefill reads together, decode writes one by one Eight prompt tokens are read together in one prefill pass. The pass ends with the first answer word, Fast. Then the words chips and wait are produced one after another in decode steps. Your prompt (8 tokens, made-up) Write a short poem about GPU memory . Prefill: all 8 read together, one pass Fast chips wait ... the wait for the first word one step per word Time runs left to right
  1. All 8 prompt tokens exist before anything is written. Nothing has to be guessed yet.
  2. 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.
  3. The first answer word ("Fast") appears only after prefill is done. This is why a long contract delays the first word.
  4. 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):

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):

  1. 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).
  2. Keep pressing. Each press is one decode step. One more KV cache slot fills each time. Each bar is about 30 ms.
  3. Press Reset. Drag the slider to 4,000. Press Next step once. Expect a prefill bar of about 3,640 ms.
  4. 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.

Ready

Row 1: prompt tokens, then generated tokens

Row 2: KV cache (one sticky note per token held)

Row 3: time per step (illustrative milliseconds)

What to notice (check these against your run)
Optional: the lab's numbers without the lab

Check the toy formulas by hand, in milliseconds (ms):

Prompt tokensPrefillOne decode step
847 ms30 ms
400400 ms34 ms
4,0003,640 ms70 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.

  1. The GPU has 80 GiB of memory.
  2. The model's weights take 16 GiB.
  3. Left for notes: 80 - 16 = 64 GiB.
  4. 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).
  5. One 8,000-token chat: 8,000 x 128 KiB = about 1 GiB.
  6. 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:

FactorMeaning
2a key note and a value note
32layers
8KV heads (separate ways of looking back)
128numbers in each list
2bytes per number
Where does 2 x 32 x 8 x 128 x 2 come from?
One GPU's memory: weights, then room for notes that fills chat by chat A bar for an illustrative 80 GiB GPU. 16 GiB holds the model weights. The other 64 GiB is room for notes. Each chat adds about 1 GiB until the room is full at about 64 chats. One GPU with 80 GiB of memory (illustrative) Weights16 GiB Room for notes: 80 - 16 = 64 GiB 1 chat = about 1 GiB About 64 chats x 1 GiB = 64 GiB of notesnotes fill the roomspare Each new conversation adds about 1 GiB of notes. When the room is gone, new requests fail or must wait.
  1. The model must be loaded before it can work. Its 16 GiB is the same for 1 chat or 100.
  2. 80 - 16 = 64 GiB. Only this part can grow with people and chat length.
  3. One chat of 8,000 tokens adds about 1 GiB of notes. The first chat takes a thin slice.
  4. At 64 chats, 64 GiB is used. In practice fewer fit, because the model needs working space and chats vary in length.
  5. 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.

Scenario: ten colleagues join

Mix-ups to avoid

Recap

That is why the lawyer waited (prefill) and why ten colleagues broke it (the cache needed 11 GiB and only 8 GiB was free).

In the field Ask for three numbers before quoting hardware: prompt length, answer length and how many people are active at once.
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.
Go deeper
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.

Review