Life of a prompt: a walk through LLM inference and vLLM

Every time I type something into ChatGPT or Claude, the same small question goes through my head. What actually happens between the moment I press enter and the moment the tokens start scrolling? I have spent a lot of time on the post-training side of language models, mostly LoRA fine-tuning, quantization, distillation, pruning, and DPO. But the inside of the inference engine has always been a place I waved my hands at. The forward pass, you know, the GPU does its thing, tokens come out. That was honestly the level I was operating at.

The closed engines that OpenAI, Anthropic and Google run are not something we get to look inside. So the only way to really understand modern inference is to study an open source one. The most popular open inference engine in production today is vLLM, and it ships an alphabet soup of features whose names have always slightly intimidated me. PagedAttention. Continuous batching. Speculative decoding. Chunked prefill. Prefix caching. For a long time these felt like jargon I could not unpack.

So for the last two days I have been quietly disappearing into vLLM, gathering information from every resource I could find and stitching it together until the picture finally clicked. What follows is the writeup I wish I had read first. We are going to put ourselves in the shoes of a prompt and follow it all the way through the engine. We will need to spend some time at the matrix level, because that is the only way to really see why the KV cache exists. After that, the rest of vLLM falls out naturally.

One small admission before we dive in. Most of us, most of the time, do not actually need to understand any of this at the ground-zero level a researcher building a new engine would. You can ship perfectly good products on top of vLLM the same way you can drive a car without knowing how a transmission is machined. I am writing this for the other reason, the one that does not really need a justification. Curiosity. Once the fundamentals click, the whole flow stops looking like a wall of jargon and reveals itself as a series of fairly reasonable decisions, and that shift is the whole point.

Pretend you are the prompt

I want you to imagine you are a prompt. Someone has just typed "hi my name is" into a chat box. You are about to be sent into the inference engine, and the goal of the rest of this post is to give you a clear mental picture of everything that happens to you on the way in, and everything that has to be true behind the scenes for tokens to start streaming back.

You will not be travelling alone. To see the interesting parts of vLLM you really need more than one user on the GPU at once, so we are going to send three small prompts in together. You are "hi my name is". Travelling with you are "today is a beautiful summer day" and "hello there". Someone calls llm.generate on the three of you at once with TinyLlama, the smallest LLaMA-style model that is easy to run end to end, and three completions come back. What we want to understand is everything that happens between that Python call and those completions.

Step zero is the easy one, you arrive. Someone has typed you into a chat box and pressed enter. The next step is where things start to get interesting.

Step one, tokenization

Language models do not understand English. They understand integers. So the very first thing the engine does is run each of your three prompts through the model's tokenizer, almost always a byte-pair encoding tokenizer that came with the model on Hugging Face. After this step "hi my name is" is no longer English. It is a list of five integer token IDs. The second prompt becomes seven token IDs, and "hello there" becomes two. From this moment on, the engine never sees English again. Everything that happens downstream operates on integers.

Step two, the waiting queue

You do not get to walk straight into the model. Think of it like a cinema, there is a queue before the hall. The three tokenized prompts are wrapped into request objects and dropped into a waiting area, and inside this waiting area there are two kinds of requests.

The first kind is a prefill request. This is a request whose tokens have not yet been seen by the model at all. A prompt that has just arrived is always a prefill request first. The second kind is a decode request. This is a request that has already had its first token produced and is now asking the model for the next one, and the one after that, and so on. The scheduler tends to give priority to decode requests over prefill requests, because a user who is already watching their reply stream really notices when the stream stalls, while a new request waiting an extra millisecond does not.

Before we go any further we need to take a short detour, because the words "prefill" and "decode" are about to do a lot of work, and to really feel what they mean we have to actually look at the matrix math inside one transformer layer. Bear with me, this is the bit that makes everything else click.

The detour, what really happens inside one forward pass

Forget vLLM for a moment. Suppose the prompt you are working with is just three tokens, "a sunset is". Each token gets turned into a small vector. To keep the picture clean let us pretend each vector has four dimensions. Stack the three of them and you have a tiny input matrix X that is three rows by four columns.

Inside one transformer layer, the very first thing that happens to X is that it is multiplied by three weight matrices the model learned during pre-training, which are W_Q, W_K, and W_V. The result is three matrices of the same shape as X, the queries Q, the keys K, and the values V. Each of them is three rows by four columns, one row per token.

Now Q gets multiplied by K transposed, which gives a small square of attention scores three by three. The entries in this square are the only place in the whole network where tokens get to learn anything about their neighbours. A score at position (sunset, is) is the model's measure of how much the word sunset should pay attention to the word is. That square gets softmaxed into attention weights, also three by three. We multiply the weights by V and we get the context matrix, three by four, one row per token again.

Now here is the part you really need to see, because the entire idea of the KV cache lives or dies on it. To predict the next token, we do not need the whole context matrix. We only need its last row. We feed that one row into the language modelling head, which is just one more matrix multiplication into vocabulary space, take an argmax, and out pops the next token. Watch the video below. Wait for the bottom row of the context matrix to glow. The first two rows are doing nothing useful at all.

What I have just walked you through is what people mean when they say prefill. The whole prompt goes in at once, all the attention is computed in parallel across every pair of tokens, and one token comes out. The GPU loves prefill because there is a lot of dense arithmetic to do. The user feels prefill as the wait for the first token to appear.

The decode stage, and how to spot the waste

Prefill gave us our first new token, extremely. So our sequence is now "a sunset is extremely", which is four tokens. To predict the fifth token we need to run another forward pass, and the obvious way to do it is to glue the new token onto the prompt and redo everything from scratch. Build a new four-by-four X, multiply by W_Q, W_K, W_V again, get a new Q, K, V, each four by four now, compute a four-by-four attention scores square, softmax, multiply by V, get a four-by-four context, take its last row, predict the next token.

This works. The next token would be something like beautiful. And what is funny is that if you put the prefill picture and this picture side by side, the decode stage is just a slightly bigger copy of the prefill stage. So you sit back, satisfied, and the obvious takeaway is that the model just keeps running this loop until it hits the end-of-sequence token.

But there is something deeply wasteful happening in this loop, and the rest of this post lives in the gap between noticing the waste and not noticing it. The first clue I gave you in the animation above. To predict the next token, we only need the last row of the context matrix. The first three rows were computed and never used. Hold onto that. Now let us walk backwards from "last row of the context" and ask, what do we actually need to compute it?

The context matrix is the attention weights times V. To get only its last row, we only need the last row of the attention weights, multiplied by the entire V. The last row of the weights comes from the last row of the attention scores. And the last row of the attention scores comes from the last row of Q times the entire K transposed. So the strict shopping list of things we need for one decode step is short. We need only one query vector, the one for the new token. And we need the full K and the full V.

That last sentence is where everything turns. Look at what is in the full K and full V during this decode step. The first three rows of each one are the keys and values for the tokens a, sunset, and is. The prompt has not changed since prefill. The weights W_K and W_V have not changed since pre-training. The keys and values for those three tokens are bit-for-bit the same numbers we computed five seconds ago during prefill. There is no honest reason to compute them again.

And that is the whole idea of the key-value cache. After prefill, do not throw K and V away. Store them. When the next decode step rolls around, take only the embedding of the newest token, compute just one new query vector, one new key vector, and one new value vector. Append the new key and the new value to the cached ones. Now you have the full K and full V ready, almost entirely from cache, with one new row appended. Multiply the new query by the cached K transposed, softmax that thin strip of attention scores, multiply by the cached V, and you have the one row of context you actually wanted. Send it through the language modelling head and the next token pops out.

A small puzzle that confused me for an embarrassing minute. Why do we cache K and V but not Q? Look back at the shopping list. The query vector of the newest token is the only query we ever need. The queries of older tokens were each used at their own decode step and then never asked for again. There is simply nothing to cache. Caching K and V is the right amount of caching.

Two key realisations to keep, because they are the two halves of the whole idea. First, to predict the next token we only need the last row of the context, not the whole context. Second, even though we need the full K and V, we do not need to recompute them. The previous rows are already sitting in memory from prefill, and every step only adds one new row. Without these two realisations, decoding is quadratic in the sequence length. With them, decoding is linear.

The dark side of the cache

The cache is a beautiful trick and it has a cost. The cost is memory. For every token you have ever processed, for every transformer layer in the model, you have to keep a key vector and a value vector alive in VRAM. The numbers get real surprisingly quickly.

Take TinyLlama, the 1.1B-parameter model from the vLLM tutorials. It is a small model, but the arithmetic is the same shape for bigger ones. The relevant constants are these:

Pause on grouped-query attention for one second. Standard multi-head attention has as many K and V heads as it has Q heads. Grouped-query attention shares each K and V head across several Q heads, so the cache for K and V is much smaller than the cache for Q would have been. TinyLlama has many more attention heads than its 4 KV heads, and that is on purpose. With those constants in hand, the KV state for one token across the whole network is:

Twenty-two kilobytes per token sounds tiny. It is not. A chat that runs for four thousand tokens eats almost ninety megabytes of cache for one conversation on a tiny model. Move to a real production model with forty layers and eight KV heads and you can easily land near a megabyte per token, which is a gigabyte for every thousand tokens of context, per concurrent user. This is the line on the budget that bites you. Weights are paid for once. The KV cache scales with every user and every conversation length, and it lives on the same VRAM as the weights.

Now we have everything we need to walk back into vLLM and watch what it actually does with this cache.

Back to the queue, and into vLLM proper

You had been sitting in the waiting queue with the other two prompts. We left you there because we needed to understand what "prefill" and "decode" really meant. Now that we do, we can pick up the story.

Once the scheduler decides it is your turn, the engine needs to find a home in GPU memory for your KV cache, because over the next few hundred decode steps you are going to be writing more and more key and value vectors into it. This is where vLLM's signature idea shows up. vLLM manages the KV cache the way an operating system manages virtual memory. Most of what makes vLLM fast follows from that one decision.

Think of GPU VRAM as a piece of land. Several tenants want to build on it. The model weights take up a corner. CUDA needs some workspace for its kernels and activations, that is another few gigabytes. After everyone else has taken their spot on a 16 GB GPU, the remainder is what every KV cache for every concurrent user has to live in. For TinyLlama, the rough partition looks like this:

That last piece of land is where every KV cache for every concurrent user has to live, and the rest of this post is really about how vLLM divides it up without wasting any of it.

vLLM does not hand out this land in arbitrary shapes. Before the engine starts taking traffic, it slices the leftover land into fixed-size pieces called blocks. Each block holds the K and V state for a fixed number of tokens, defaulting to sixteen, across all the transformer layers. Allocating one block for TinyLlama costs:

Divide the free pool by the block size:

This is exactly the number vLLM prints in its startup log under "CUDA blocks", and the first time I saw where that number actually comes from I felt a little dumb and a lot more comfortable with the engine. There is also a smaller "CPU blocks" number, which is the same calculation applied to a 4 GB pool of pinned host memory that vLLM keeps in reserve for sequences it might need to swap out under pressure.

Now back to your prompt. The scheduler measures how many tokens you have, rounds up to the nearest multiple of sixteen, and grabs that many blocks from the free queue for you. The other two prompts in the batch grab their own blocks. The forward pass runs for all three of you in a single fused kernel, prefill happens in parallel, and your first output token is produced. Your blocks now contain the K and V state for every token of your prompt.

From here you switch from being a prefill request to being a decode request. Every iteration of the scheduler you get one more token decoded, and that one new key vector and value vector gets appended into the next free slot inside your blocks. Every sixteen new tokens, you fill up another block, and vLLM grabs you a fresh one from the free queue. When you eventually hit the end-of-sequence token or your max-tokens limit, all the blocks you ever held fly back into the free queue immediately, ready to be picked up by whoever asks next.

The bookkeeping that makes this work is a small data structure on the CPU side called the page table. For each active sequence, the page table is an ordered list of which physical block IDs that sequence owns. There is also the free block queue, which is exactly what it sounds like. Two genuinely beautiful properties fall out of this design.

The first is that the blocks one sequence owns do not have to be next to each other in VRAM. When you outgrow your current block, vLLM just grabs whatever block is at the head of the free queue, and the attention kernel reads through your page table to know where to look. The fragmentation problem that traditionally haunts long-context inference simply disappears.

The second is that when a sequence finishes, its blocks return to the free queue immediately. Not at the end of a batch. Not at some periodic cleanup. Immediately. The very next request that arrives can pick up those blocks and start its own prefill. Which is exactly what makes the last idea in this post possible.

Continuous batching, or why the old way wasted so much

Before paged attention, the standard way to batch inference was called static batching. You collect, say, four prompts. You run them through the model together. They decode tokens together. The batch ends only when the longest sequence in it finishes. Any shorter sequence that completes early just sits there occupying its slot, doing nothing, blocking that slot from being given to anyone else. This is fine if all your requests happen to be exactly the same length. They never are.

Continuous batching, the second pillar that vLLM rests on, fixes this. The idea is exactly what the name says. The batch is not a fixed slate of requests anymore. It is a flowing river. Every iteration the scheduler looks at which sequences are active, decodes one token for each of them in a single fused kernel, then immediately checks whether any of them just finished. Anything that finished returns its blocks to the free queue. Anything from the waiting queue that fits in the newly freed capacity is admitted on the spot. No sequence ever waits for an unrelated sequence to finish.

Continuous batching only really works because the paged KV cache already exists. Without paging, you cannot return memory mid-batch without a fight, because each sequence's cache is a fixed contiguous arena. With paging, freeing a sequence is just pushing some block IDs back onto a queue, which takes nanoseconds. The two ideas are independently sensible and jointly devastating, and together they are the reason vLLM can serve hundreds of concurrent users on a single GPU.

The whole life of a prompt, in one breath

Close your eyes for a second and trace the trip you have just taken. You arrived as a string of English. The tokenizer turned you into integers. You went to the waiting queue as a prefill request. The scheduler picked you up the moment there were enough free blocks to fit you. Your blocks were allocated, the forward pass ran across all the prompts in the current batch in parallel, and your first output token came out. You moved into the running pool as a decode request. Every iteration one more token was decoded for you and one more row was appended to your K and V blocks. Every sixteen tokens you grew another block. When you finally hit your end-of-sequence token, every block you ever held flew back into the free queue. Meanwhile seventy-three other prompts were doing exactly the same dance in parallel, borrowing whatever blocks were free, completely unaware that any of the others existed.

That is the whole picture. Once you have it, the strange numbers vLLM logs at startup stop being mysterious. The preemption messages that show up under load become readable. The difference between time-to-first-token and inter-token latency lines up with prefill and decode. You also start being able to reason about what each of the remaining innovations is actually for.

What is on the horizon

I am saving the rest of the rabbit hole for a follow-up post, but the ideas that get interesting once you have the foundation above are roughly these:

• Prefix caching. If two requests share the same system prompt, their prefill produces identical K and V for the shared tokens. vLLM can detect that and reuse the cache across requests, which is most of the cost of a long system prompt going to zero.
• Speculative decoding. A small draft model cheaply produces several tokens, the large model verifies them in a single forward pass, and accepts the ones that match. When the draft is good, you get several tokens for the price of one.
• Chunked prefill. Instead of doing prefill for a long prompt in one giant compute-heavy step, vLLM splits the prompt into chunks that can be interleaved with ongoing decodes. Users already streaming tokens do not feel the long prompt arriving behind them.
• Multi-node serving. When the model is too big for one GPU, vLLM tensor-parallels the matrix multiplies across several GPUs in a node, and beyond that pipeline-parallels layers across nodes. The cache still works the same way, just sharded.

Every one of these is a small modification of the picture above. The picture above is the part that took me two days to internalise, and it is the part I wish someone had drawn for me the day I first heard the words "KV cache". If you remember nothing else from this post, remember three things. Generation splits cleanly into prefill and decode. The KV cache exists because the last row of the context matrix is the only row that matters. And vLLM treats your GPU like an operating system treats RAM. Everything else is careful implementation on top.

Thanks for reading. Comments, corrections, and counter-examples are welcome, especially if you maintain an inference engine yourself and I have flattened something I should not have.