Inference Internals · Part 2 of 5
What is PagedAttention?Stop roping off the whole table.
Every chat on a GPU keeps a pile of notes, and nobody knows how big each pile will get. PagedAttention is vLLM's answer to where to put them all: small identical trays, handed out only when needed. It's a big part of why vLLM serves so many more people per GPU.
This is the second half of what I wanted to understand. Once the KV cache made sense, the next question was obvious. If every chat needs a growing pile of notes, and you can't know in advance how big each pile will get, where do you put them all?
We'll stay in the same restaurant kitchen as Part 1. The cook writes one index card per word, and each table's cards sit in a tray. Look at the banner and you'll see the two ways to manage the space. On the left, a ten-seat table roped off for one party, just in case friends turn up. On the right, a glass shelf of small identical trays, and a host with a pegboard showing which trays belong to which table. The right side is PagedAttention.
01 / The stakes
Why does it matter where the notes go?
Because the notes decide how many people you can serve. A GPU's memory holds two big things: the model's weights, which never change, and the KV cache of every chat, which grows with every word. When the PagedAttention team served a 13-billion-parameter model on a 40 GB NVIDIA A100, about 65% of memory held the weights and close to 30% held these per-request notes. [1]
Part 1 showed why you want lots of chats on the GPU at once: each decode step is slow because of fetching from memory, so you share every fetch across many requests. The paper makes the link directly: how you manage the KV cache decides the maximum batch size, and so the throughput. [1]
So every gigabyte wasted in that 30% is people you can't serve.
- In the kitchen
- The recipe books take most of the room. What's left is shelf space for trays, and the number of trays decides how many tables you can seat.
- In the model
- Weights are fixed. The KV cache memory left over sets the batch size, and the batch size sets throughput.
02 / The old way
Where did the memory go before PagedAttention?
Two facts collide here. The usual way to store data on a GPU is in one unbroken stretch of memory. And a chat's notes grow one token at a time, to a length nobody knows in advance. One person wants "yes or no". Another wants an essay.
So older serving systems did the safe thing. When a request arrived, they reserved one unbroken chunk big enough for the longest answer allowed, such as 2,048 tokens. [1] That wastes memory in three ways:
- Reserved for later. Slots the answer will fill eventually sit empty now, and nobody else can use them while the request runs. [1]
- Never used. The answer stops at 300 tokens, and the other 1,748 reserved slots were never needed.
- Gaps. Chunks of different sizes come and go, leaving holes between them that are too small for the next request. [1]
The result was shocking. The paper found that in existing systems, only 20.4% to 38.2% of KV cache memory held actual notes. [1] The vLLM team's launch post puts it the other way round: those systems "waste 60% – 80% of memory due to fragmentation and over-reservation". [2] That's the roped-off ten-seat table, booked for a party of two.
Figure 1 · Same memory, two ways to hand it out
Reserve a whole table
Each chat gets 16 slots the moment it arrives.
Trays on demand
Each chat gets 4-slot trays, one at a time, from anywhere.
- A chat's notes (A to G)
- Taken, but empty
- Free
- In the kitchen
- The host ropes off a long table for every party that walks in, in case friends turn up. Most chairs stay empty, and the next party waits at the door.
- In the model
- Each request's KV cache is pre-allocated as one contiguous chunk for the maximum length. Reserved, unused and fragmented space is wasted.
03 / The idea
How does PagedAttention fix it?
With an idea your laptop has used for decades: virtual memory with pages. Every program on your laptop believes it has one tidy, unbroken stretch of memory. Underneath, the operating system cuts memory into small pages of the same size, scatters them wherever there's room, and keeps a table that maps one to the other.
The PagedAttention paper applies exactly that to the notes. In its own words: "one can think of blocks as pages, tokens as bytes, and requests as processes." [1] Each chat's KV cache is cut into blocks that hold a fixed number of tokens, 16 by default in vLLM. [6] Three simple rules follow:
- A chat gets a new block only when its last one is full.
- Any free block, anywhere in memory, will do.
- Every block is the same size.
Now look at the three kinds of waste again. Nothing is reserved far ahead, only the current block. Gaps can't form, because every block is the same size; the paper says this "eliminates external fragmentation". [1] And unused space can only sit in a chat's last block, at most 15 empty slots. The vLLM team measured the total waste at "under 4%". [2]
- In the kitchen
- Small identical trays of 16 cards on a shared shelf. A table gets a new tray only when its current one is full, from wherever there's a free slot.
- In the model
- The KV cache is split into fixed-size blocks, allocated on demand from a pool of identical physical blocks.
04 / The pegboard
If a chat's notes are scattered, how does the model find them?
With a list. Each chat keeps a block table: its blocks, in order, and which physical tray each one lives in. "My first 16 tokens are in tray 7, the next 16 in tray 1, the rest in tray 3." [1] That's the pegboard the host holds in the banner.
When the model needs to read a chat's notes, it follows that list. The paper wrote a new attention kernel, the GPU code for the look-back step, that reads keys and values block by block instead of expecting them side by side. [1] Step through one chat's life:
Figure 2 · One chat's block table
Chat A's block table
- Block 0 → tray 716/16
- Block 1 → tray 116/16
- Block 2 → tray 35/16
- Empty: the chat has ended
The shelf (GPU memory)
- 0other chat
- 1A · 16/16free
- 2other chat
- 3A · 5/16free
- 4free
- 5other chat
- 6free
- 7A · 16/16free
- 8free
- 9other chat
- 10free
- 11other chat
- 1. Your prompt is 16 tokens. Its notes fill block 0, and the host hands out a free tray: tray 7. The table now says block 0 → tray 7.
- 2. Token 17 arrives. Block 0 is full, so the host grabs another free tray: tray 1. It's nowhere near tray 7, and that's fine.
- 3. Token 33 gets a new tray, tray 3. By token 37, tray 3 holds 5 notes and 11 empty slots. That's the only waste this chat makes.
- 4. To write the next token, the model follows the table, tray 7, then 1, then 3, and reads all 37 notes in order, as if they sat side by side.
- 5. The chat ends. Trays 7, 1 and 3 go back on the free list, ready for anyone.
- Chat A's 37 tokens live in trays 7, 1 and 3, scattered across the shelf. The block table keeps them in order, and only the last tray has empty slots.
- In the kitchen
- The host's pegboard says "Table A: trays 7, 1, 3". The cook reads the trays in that order and never cares where they sit on the shelf.
- In the model
- A per-request block table maps logical blocks to physical blocks. Attention reads keys and values through that table.
05 / The cost
Isn't reading scattered trays slower?
Yes, a little, and the paper is upfront about it. Looking things up in the block table and handling chats of different lengths cost extra work. The paper measured its attention kernel at "20–26% higher attention kernel latency" than FasterTransformer's highly tuned version. [1]
But that's one step inside the model. The whole system got much faster, because far more chats fit in each batch. vLLM improved throughput "by 2-4× with the same level of latency" compared with FasterTransformer and Orca, and the gains grew with longer sequences, larger models and fancier decoding. [1]
Why 16 tokens per block? It's a balance. Very small blocks make the GPU read memory in tiny, inefficient pieces. Very big blocks bring back the empty space in each chat's last block. The paper found 16 "large enough to efficiently utilize the GPU and small enough to avoid significant internal fragmentation in most workloads", and made it the default. [1]
To me this is the best part of the whole idea. You pay a little on one operation to gain a lot on the whole system.
- In the kitchen
- Fetching trays from different shelves costs the cook a few extra steps, but the restaurant seats far more tables each evening.
- In the model
- The paged attention kernel was 20–26% slower, yet end-to-end throughput rose 2–4× because batches got much bigger.
06 / Sharing inside a request
Can two answers share the same notes?
Sometimes you ask a model for several answers to one prompt, and pick the best. Beam search, a way of exploring several candidate answers at once, does something similar. All those answers start from the same prompt, so the prompt's cards are identical. Copying them for every answer would be pure waste.
Once blocks have a block table, sharing is easy: point several block tables at the same trays. The paper adds a reference count to each block, the number of chats using it. And when one answer needs to write into a shared block that isn't full yet, vLLM first copies just that one block. That's called copy-on-write, another idea borrowed from operating systems. [1]
Figure 3 · Two answers, one prompt
Block tables
Answer 1tray 7tray 1tray 3
Answer 2tray 7tray 1
- 7The chef tasted thecount: 2
- 1dal and said ·dal and said hmmcount: 2count: 1
- 3freedal and said wowcount: 1
- 1. One 7-token prompt, two answers. Both block tables point at the same trays: tray 7 is full, tray 1 has 3 notes and one empty slot. Each tray's count is 2.
- 2. Answer 1 wants to add "wow" to tray 1, but tray 1 is shared. So vLLM copies tray 1 into a free tray, tray 3, points answer 1 at it, and drops tray 1's count to 1.
- 3. Answer 2 adds "hmm". Tray 1's count is now 1, so it writes straight in. No copy needed.
- Both answers still share tray 7. Only one tray was ever copied, and only because someone needed to write into it.
In the paper's tests, this sharing saved up to 30.5% of KV cache memory for multiple answers per prompt, and up to 66.3% for beam search. [1] Today's vLLM organises sharing around prefix caching, which works on full blocks only. [3] That's the next chapter.
07 / Sharing between users
What if a thousand users send the same instructions?
They often do. Most apps send the same system prompt, tool list or reference document at the start of every request. Part 1 said different chats can't share cards, because a card depends on everything before it. But a word-for-word identical beginning produces identical cards. vLLM takes advantage of that with automatic prefix caching, which is on by default. [6]
Here's how it works. When a block fills up, vLLM gives it a fingerprint, a hash built from the tokens in the block and all the tokens before it. A new request's prompt is fingerprinted block by block and looked up. Every match is reused as is, and the model skips working those tokens out again. [3] Only full blocks are cached. [3] When a chat ends, its blocks go back on the free list but keep their notes, and the least recently used ones are cleared first when space is needed. [3]
Figure 4 · Two users, the same instructions
- 2Instructions, part 1in usefree, notes kept
- 5Instructions, part 2in usefree, notes kept
- 8User 1's questionfree
- 4User 2's questionfree
User 1 · fingerprints saved for trays 2 and 5 User 1 has gone · trays 2 and 5 wait on the free list User 2 · trays 2 and 5 matched, prefill skipped for them
- 1. User 1 sends the app's instructions plus a question. The instructions fill two full trays, 2 and 5, and each gets a fingerprint.
- 2. User 1's chat ends. Trays 2 and 5 go on the free list, but their notes and fingerprints stay.
- 3. User 2 sends the same instructions and a different question. vLLM matches the fingerprints, reuses trays 2 and 5, and only works out the new question.
- User 2 got the instructions' notes for free: no prefill for them, and no extra memory. The question's tray is user 2's own.
vLLM's own docs call prefix caching "almost a free lunch" that "won't change model outputs". [3] Two catches, though.
Privacy. If a reused prefix makes a response come back faster, someone
could time requests to guess what other users sent. vLLM lets you add a
cache_salt to each request, which is mixed into the first block's
fingerprint, so only requests with the same salt share blocks. The docs say this
"prevents timing-based attacks". [3] If different customers
share your servers, I'd give each customer its own salt.
Routing. The cache lives on one server. With several vLLM servers behind a load balancer, a request only gets a hit if it lands where its prefix is already cached. That's why inference-aware routers, like Kubernetes' Gateway API Inference Extension, look at prefix cache status when they pick a server. [8]
- In the kitchen
- Every table starts with the same house rules, so the cook keeps one set of cards for them and points each new table's pegboard at it.
- In the model
- Full KV blocks are hashed with their prefix. Requests with a matching prefix reuse those blocks and skip their prefill.
08 / Under pressure
What happens when the shelf is full?
Blocks are handed out as answers grow, so a busy server can run out halfway through. When that happens, vLLM preempts: it pauses some requests and frees their blocks so the others can finish. Paused requests are worked out again when space comes back. [4]
The paper evicts all of a request's blocks or none, because a request needs every one of
its notes to continue. It preempts the most recently arrived requests first, so the
earliest ones finish. [1] It also described two ways to
bring a request back: copy its blocks out to CPU memory and back (swap), or throw them
away and redo them (recompute). In today's vLLM, "the default preemption mode is
RECOMPUTE rather than SWAP". [4]
Redoing is quicker than you'd think, because the prompt and the words written so far
can be processed together in one parallel pass, like prefill.
[1]
When it happens, your logs show a warning like this one from vLLM's docs:
WARNING 05-09 00:49:33 scheduler.py:1057 Sequence group 0 is preempted by PreemptionMode.RECOMPUTE mode because there is not enough KV cache space. This can affect the end-to-end performance. Increase gpu_memory_utilization or tensor_parallel_size to provide more KV cache memory. total_cumulative_preemption_cnt=1
For the person on the other end, the answer stalls. vLLM's docs say preemption and recomputation "can adversely affect end-to-end latency". [4]
- In the kitchen
- When the shelf is full, the host clears the newest table's trays. Later, that order is re-read from the slip and the cards are written again.
- In the model
- Preemption frees all of a request's blocks. With recompute, its KV cache is rebuilt from the prompt plus the tokens generated so far.
09 / The limits
What doesn't PagedAttention fix?
It's easy to oversell this, so here's what it leaves alone.
| Fixed | Not fixed |
|---|---|
| Reserving space for answers that never come | The size of the notes. A 128K-token chat on Llama 3.1 8B still needs about 16 GiB. Use the tools from Part 1. |
| Gaps between chunks of different sizes | The extra work in attention: the paper's kernel was 20–26% slower than a contiguous one. [1] |
| Copying prompts for every answer | The privacy and routing catches of sharing between users (chapter 7). |
| Fitting far more chats per GPU | Running out under heavy load. Preemption still happens (chapter 8). |
There's also a hidden cost: every attention kernel has to understand blocks and block tables. That's more complex GPU code to write and keep fast. You never see it if you use vLLM, but it's real engineering.
10 / Hands-on
How do you use it in vLLM?
The nice surprise: you don't switch it on. Paged blocks are simply how vLLM stores the KV cache, and prefix caching is on by default. [6] What you do tune is how much room the blocks get and how many requests compete for them.
| Setting | What it does | In the kitchen |
|---|---|---|
--gpu-memory-utilization |
Share of GPU memory vLLM may use. If you don't set it, current vLLM docs give 1.0 with the extensible KV cache and 0.92 otherwise, so check the docs for your version. The KV cache gets what's left after the weights and working memory. [6] | How much of the room is shelving |
--max-num-seqs |
How many requests run at once. Lower it if preemptions are constant. [4] | How many tables you seat |
--kv-cache-dtype fp8 |
Store keys and values in 8 bits, half the space per token. [7] | Write the cards in shorthand |
--block-size |
Tokens per block. vLLM's default is 16. [6] | Cards per tray |
And watch two things. The metric vllm:kv_cache_usage_perc shows the share
of KV cache blocks in use, from 0 to 1. [5] And your logs
show the preemption warning from chapter 8.
- Leave the block size alone. The default was chosen with care.
- Alert when KV cache usage sits near 1 and preemption warnings keep appearing. One without the other is usually fine.
-
When you hit that, give the cache more room first: FP8 KV cache, or more GPUs.
Otherwise, lower
--max-num-seqsso fewer requests compete. [4] - Put your shared instructions at the very start of every prompt, word for word, so prefix caching can find them.
- Use a
cache_saltper customer if customers share servers.
Inference Internals series
Keep going
- Part 1: KV cache. What the notes are, why they exist, and how big they get.
- Part 3: Continuous batching. How the host decides who sits down, every single step, and what happens to prompts and preemption.
- Part 4: Speculative decoding. How a small model guesses ahead so the big one writes several words per trip.
- Inference Masterclass: the whole kitchen, including continuous batching, chunked prefill and speculative decoding.
Glossary
The words, in one place
- KV cache
- The stored keys and values for every token of a chat. Part 1 explains it.
- Block (page)
- A fixed-size piece of the KV cache, 16 tokens by default in vLLM.
- Logical and physical block
- A chat's blocks in order (logical) and where each actually sits in GPU memory (physical).
- Block table
- Each chat's list mapping its logical blocks to physical blocks.
- Internal fragmentation
- Space set aside but never filled. With paging, only in a chat's last block.
- External fragmentation
- Gaps between chunks of different sizes. Same-size blocks can't leave any.
- Reference count
- How many chats are using a block right now.
- Copy-on-write
- Copying a shared block only when someone needs to write into it.
- Automatic prefix caching
- Reusing the blocks of an identical prompt beginning across requests, matched by hash.
- Cache salt
- A per-request value mixed into the hash so only requests with the same salt share blocks.
- Preemption
- Pausing a request and freeing its blocks when memory runs out.
- Recompute and swap
- Two ways back from preemption: redo the notes, or copy them to CPU memory and back. vLLM recomputes by default.
Quiz
Check your understanding
Older servers reserved space for the longest possible answer. Name two ways that wasted memory.
Any two of: slots reserved for later that nobody else could use, slots never used because the answer stopped early, and gaps between chunks of different sizes.
Why can't gaps form between PagedAttention blocks?
Every block is the same size, so any free block fits any request.
A chat has 37 tokens and blocks hold 16. How many blocks does it use, and how many slots are empty?
Three blocks, 48 slots, so 11 empty slots, all in the last block.
The paged attention kernel was slower. Why was the system faster?
Wasting almost no memory let far more requests share each batch. Throughput rose 2–4×, which more than paid for a 20–26% slower attention step.
Two customers send the same 2,000-token system prompt to your vLLM server. What gets reused, and what's the risk?
The full blocks of the shared prompt are reused and their prefill is skipped. The risk
is a timing side channel between customers. A per-customer cache_salt
stops it.
Sources
Sources
All checked 30 October 2026.
- Kwon et al., "Efficient Memory Management for Large Language Model Serving with PagedAttention", SOSP 2023
- vLLM blog: "vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention" (20 June 2023)
- vLLM docs: Automatic Prefix Caching (design)
- vLLM docs: Optimization and Tuning
- vLLM docs: Metrics
- vLLM source: CacheConfig (vllm/config/cache.py)
- vLLM docs: Quantized KV Cache
- Kubernetes Gateway API Inference Extension (README)
Written with AI assistance. Every technical claim was checked against the original sources listed above and reviewed by Supraj.