supraj.dev

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.

Supraj Maripeddi · · Updated · 15 min read

An isometric restaurant: on the left, a long ten-seat table sits empty behind a velvet rope. On the right, a host stands at a pegboard next to a glass shelf of small identical trays, some filled and some empty.
Start hereRead Part 1, or just know that a model keeps notes for every word.
Leave knowingWhere the memory went, how pages fix it, how notes get shared, and what happens when memory runs out.
Checked againstThe 2023 PagedAttention paper and vLLM's docs and code, 30 October 2026.

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:

  1. Reserved for later. Slots the answer will fill eventually sit empty now, and nobody else can use them while the request runs. [1]
  2. Never used. The answer stops at 300 tokens, and the other 1,748 reserved slots were never needed.
  3. 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

Toy sizes: 64 slots, chats of up to 16 tokens, trays of 4. Seven chats arrive over time and each grows by one token per step until it's done. Real vLLM uses 16-token trays, thousands of them.
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

  1. Block 0 → tray 716/16
  2. Block 1 → tray 116/16
  3. Block 2 → tray 35/16

The shelf (GPU memory)

  1. 0other chat
  2. 1A · 16/16
  3. 2other chat
  4. 3A · 5/16
  5. 4free
  6. 5other chat
  7. 6free
  8. 7A · 16/16
  9. 8free
  10. 9other chat
  11. 10free
  12. 11other chat
All 5 steps
  1. 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.
Tray numbers follow the example in the PagedAttention paper. Blocks hold 16 tokens, the vLLM default.
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 3

Answer 2tray 7tray 1

  1. 7The chef tasted thecount: 2
  2. 1dal and said hmmcount: 1
  3. 3dal and said wowcount: 1
All 3 steps
  1. Both answers still share tray 7. Only one tray was ever copied, and only because someone needed to write into it.
Toy blocks of 4 tokens, as in the paper's own example. Tray numbers follow the paper's figure; the sentence is ours.

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

  1. 2Instructions, part 1in use
  2. 5Instructions, part 2in use
  3. 8free
  4. 4User 2's question

User 2 · trays 2 and 5 matched, prefill skipped for them

All 3 steps
  1. 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.
Simplified: real fingerprints cover 16-token blocks, and the question's partly filled block is never shared.

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.

What PagedAttention changes, and what it doesn't.
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.

The knobs that matter for KV cache space, from vLLM's docs and code.
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.

What I'd do
  1. Leave the block size alone. The default was chosen with care.
  2. Alert when KV cache usage sits near 1 and preemption warnings keep appearing. One without the other is usually fine.
  3. When you hit that, give the cache more room first: FP8 KV cache, or more GPUs. Otherwise, lower --max-num-seqs so fewer requests compete. [4]
  4. Put your shared instructions at the very start of every prompt, word for word, so prefix caching can find them.
  5. Use a cache_salt per customer if customers share servers.

Inference Internals series

Keep going

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.

  1. Kwon et al., "Efficient Memory Management for Large Language Model Serving with PagedAttention", SOSP 2023
  2. vLLM blog: "vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention" (20 June 2023)
  3. vLLM docs: Automatic Prefix Caching (design)
  4. vLLM docs: Optimization and Tuning
  5. vLLM docs: Metrics
  6. vLLM source: CacheConfig (vllm/config/cache.py)
  7. vLLM docs: Quantized KV Cache
  8. 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.