PagedAttention and vLLM, annotated
How to read this page
- Any dotted word explains itself on hover, focus or tap, and so does every symbol in every equation.
- The memory simulator after §4.2 runs the same stream of requests through the old way and the paged way. Press Play on both.
You'll get the most from this page after the attention companion and the KV-cache section of the inference lesson. Every idea climbs the ladder: everyday picture, tiny example, diagram, the math, why it matters today.
Abstract · original
“…we propose PagedAttention, an attention algorithm inspired by the classical virtual memory and paging techniques in operating systems.”Kwon et al. (2023), Abstract
Everyday picture
A restaurant seats walk-in groups without knowing how long they'll stay or how many friends will join. The old policy: give every group a table for twelve, just in case. Most seats sit empty, and the restaurant turns people away while half the chairs are unused. The new policy: seat people at small four-seat tables, anywhere in the room, and add another small table whenever a group grows. The same room serves many more groups.
What the paper claims
- Existing serving systems waste most of the GPU memory set aside for the KV cache: only 20% to 38% of it holds real data.
- PagedAttention stores each request's KV cache in small fixed-size blocks that need not sit next to each other, cutting the waste to nearly zero and letting requests share blocks.
- vLLM, the serving system built on it, delivers 2 to 4 times the throughput of the best existing systems at the same latency.
Why it matters today
vLLM became one of the most widely used open-source engines for serving large language models, and paged KV-cache management is now standard across serving systems. When a hosted model answers you quickly and cheaply, ideas from this paper are very likely involved.
1 Introduction · original
Everyday picture
Serving a model is like running a busy kitchen: the more orders cooked together, the cheaper each one gets, because every order shares the same trip to fetch the model's weights. The limit on how many orders fit at once is not the chefs but the counter space, and on a GPU the counter space is mostly taken by the model's weights and, for every request in flight, its KV cache.
Tiny example: how big is one token's KV cache?
For every token, every layer stores a key vector and a value vector. The paper's example is OPT-13B.
In words: “one key and one value, each as wide as the model, for every layer, at so many bytes per number.”
With the numbers: 2 × 5,120 × 40 × 2 = 819,200 bytes ≈ 800 KB per token. A single request at the model's maximum length of 2,048 tokens needs 2,048 × 800 KB ≈ 1.6 GB. On a 40 GB A100, the paper finds about 65% of memory goes to the weights and close to 30% to KV caches, so a few badly packed requests can fill it.
In Python:
# hidden size, layers, bytes per number
h, L, b = 5120, 40, 2
# one key and one value, for every layer
per_token = 2 * h * L * b
per_token # → 819200
# in KB
per_token / 1024 # → 800.0
# a full 2,048-token request: KB to GB
round(2048 * 800 / 1e6, 1) # → 1.6Why it matters
Throughput is capped by how many requests' KV caches fit on the GPU at once. Wasting that memory directly wastes money. The inference lesson does the same arithmetic for a modern model shape.
2 Background: how serving works · original
Everyday picture
Every request goes through two phases. In the prompt phase the whole prompt is processed at once and its keys and values are written into the KV cache. In the generation phase one token is produced per step, each adding one more key and value to the cache. Nobody knows in advance how long the answer will be.
To keep the GPU busy, servers run many requests together. The older way, static batching, waits for the whole batch to finish. The better way, continuous (iteration-level) batching, lets finished requests leave and new ones join at every step. That makes memory the real limit: every joining request needs KV space right away.
Why it matters
This is the setting the whole paper lives in: many requests, unpredictable lengths, a cache that grows by one token per step per request.
3 Memory challenges · original
“…our profiling results in Fig. 2 show that only 20.4% - 38.2% of the KV cache memory is used to store the actual token states in the existing systems.”Kwon et al. (2023), §3.1
Everyday picture
Existing systems store each request's KV cache in one unbroken stretch of memory, because the standard attention code expects that. Since the final length is unknown, they reserve room for the maximum length up front. That wastes memory in three ways:
- Reserved: space for tokens that will be generated later, held empty for the request's whole lifetime.
- Internal fragmentation: space for tokens that will never be generated, because the answer stopped early.
- External fragmentation: small leftover gaps between reservations, each too small for a new request.
Tiny example
A request with a 100-token prompt that produces a 200-token answer, under a 2,048-token reservation, uses 300 slots and wastes 1,748: 85% of its reservation. With 16-token pages allocated on demand, it would use 19 pages (304 slots) and waste 4.
Why it matters
The paper also points out a second, less obvious loss: techniques that produce several answers from one prompt (parallel sampling, beam search) could share the prompt's KV cache, but contiguous storage makes sharing impossible, so it is duplicated.
4 Method · original
4.1 PagedAttention · original
“…one can think of blocks as pages, tokens as bytes, and requests as processes.”Kwon et al. (2023), §1
Everyday picture
A library does not keep every series of books on one continuous shelf. A series can be spread across shelves all over the building, and a catalogue card lists where each volume is. Reading the series in order just means following the card. PagedAttention splits a request's keys and values into fixed-size blocks (each holding, say, 16 tokens), puts each block wherever there is free space, and computes attention block by block, following a list of where the blocks are.
In words: “exactly ordinary attention, just organized by block: score the query against each block of keys, normalize by the total over all blocks so far, and blend each block of values by its share.”
With the numbers: the query for token i = 40 with block size B = 16 needs ⌈40 / 16⌉ = 3 blocks: tokens 1 to 16, 17 to 32 and 33 to 40 (a partly filled block). The kernel fetches those three blocks from wherever they sit in memory; the result is identical to attending over one contiguous array.
In Python:
import math
i, B = 40, 16
# ⌈i/B⌉ blocks to visit
math.ceil(i / B) # → 3
# tokens in each
[(j * B + 1, min((j + 1) * B, i)) for j in range(math.ceil(i / B))] # → [(1, 16), (17, 32), (33, 40)]Why it matters
The maths does not change at all, which is why vLLM's outputs match other systems. What changes is the memory layout, which needs a new GPU kernel that can gather keys and values from scattered blocks.
4.2 Block tables: logical and physical blocks · original
Everyday picture
From the request's point of view, its cache is a tidy numbered list of blocks: block 0, block 1, block 2 (its logical blocks). Behind the scenes, each lives in some arbitrary slot in GPU memory (a physical block). A small lookup table per request, the block table, translates one into the other, exactly like an operating system's page table.
Hover or tap a block: start with block 0 on the left.
Reading it: on the left, request A's cache as the request sees it: three consecutive blocks of 4 tokens each, the last one only a quarter full. In the middle, its block table: each row maps a logical block to a physical block number and records how many of its 4 slots are filled. On the right, GPU memory: A's blocks live at 7, 1 and 3, out of order and interleaved with request B's blocks and free space. Nothing requires them to be adjacent. The only waste is the 3 empty slots at the end of block 3, and no request can ever waste more than one partly filled block.
Why it matters
Waste per request is bounded by a single block (fewer than B slots), and because every physical block is the same size, there is no external fragmentation at all: any free block fits any request.
Try it: the memory simulator
Reading it: the grid is a tiny GPU's KV-cache memory: 256 token slots. Ten requests (illustrative prompt and answer lengths, the same for both policies) arrive in order and each generates one token per step. Solid squares hold real tokens; pale squares are reserved or allocated but empty. Under the contiguous policy every request grabs a 64-slot stretch for its maximum length, so only 4 fit at once and most of each stretch stays pale. Under the paged policy each request takes 8-slot blocks only as it grows, scattered anywhere, so more requests run side by side and almost nothing is pale. Compare the utilization and the number of steps needed to finish all ten: with this workload the contiguous policy needs 67 steps at about 41% average utilization, while the paged policy runs all ten requests at once and finishes in 40 steps at about 88%, after pausing one request briefly when memory ran out (§4.5).
4.4 Sharing and copy-on-write · original
Everyday picture
Two students share one photocopied set of lecture notes until one of them wants to scribble in the margin; only then does that student get their own copy of the page they're changing. The paper applies this to requests that produce several answers from the same prompt: they point at the same physical blocks for the shared part, with a reference count on each block, and a block is copied only when one of them needs to write into it (copy-on-write).
Reading it: step through the four stages. The boxes at the bottom are physical blocks, each showing its reference count (how many samples point at it). In stage 2 both samples point at the same two prompt blocks, so each has a count of 2 and nothing is duplicated. In stage 3 sample A needs to add a token to the shared, partly filled last block: that block is copied first, A's pointer moves to the copy, and the original's count drops to 1. The full first block is never copied. In stage 4 each sample grows into its own new blocks.
The same machinery handles beam search, where candidate answers share long histories and branch often, and shared prefixes, where many requests start with the same system prompt or few-shot examples. The paper measures memory savings of 6.1% to 9.8% for parallel sampling and 37.6% to 55.2% for beam search on one dataset (up to 66.3% on another).
Why it matters today
Shared-prefix caching is the server-side cousin of the prompt caching that API providers offer: keep the processed form of a common prefix and reuse it across requests.
4.5 Scheduling and preemption · original
Everyday picture
If the restaurant fills up because groups keep growing, someone has to wait outside. vLLM serves requests first-come-first-served and, when memory runs out, pauses the most recently arrived request. Its blocks are either swapped out to the CPU's memory (like moving a group's coats to the cloakroom) or simply thrown away and recomputed from the text when the request resumes, which is cheap because the prompt and the tokens so far can be reprocessed in one parallel pass. Because a request needs all its blocks to continue, a paused request's blocks are evicted all together.
The paper also covers running one model across several GPUs (§4.6), where every GPU shares the same block tables and holds its slice of each block.
6 Evaluation · original
Everyday picture
The test: serve realistic streams of chat and instruction requests and see how many requests per second each system can sustain before response times blow up.
| Model size | 13B | 66B | 175B |
|---|---|---|---|
| GPUs | A100 | 4 × A100 | 8 × A100-80GB |
| Total GPU memory | 40 GB | 160 GB | 640 GB |
| Parameter size | 26 GB | 132 GB | 346 GB |
| Memory for KV cache | 12 GB | 21 GB | 264 GB |
| Max. # KV cache slots | 15.7K | 9.7K | 60.1K |
Check the 13B column yourself: 12 GB (12 × 230 bytes) divided by 800 KB per token is about 15,700 tokens: the whole server can hold only about seven or eight maximum-length requests at a time, which is why wasting that space hurts so much.
The headline results, restated: on the ShareGPT chat workload vLLM sustains 1.7 to 2.7 times the request rate of the best configuration of Orca (a strong earlier system), 2.7 to 8 times that of Orca's standard configuration, and up to 22 times that of FasterTransformer, at similar latency. For OPT-13B it keeps 2.2 times as many requests in flight as the best Orca configuration. With a shared few-shot prefix, throughput rises to 1.67 times (one example) and 3.58 times (five examples) that of Orca.
Why it matters today
These gains come from memory management alone, with the model and its outputs unchanged. Cheaper serving is what makes large models affordable to use at scale.
7.2 Choosing the block size · original
“In practice, we find that the block size 16 is large enough to efficiently utilize the GPU and small enough to avoid significant internal fragmentation in most workloads.”Kwon et al. (2023), §7.2
Everyday picture: tables that are too small make the waiters run back and forth; tables that are too big leave empty seats. Small blocks waste less memory but give the GPU kernel less to do per fetch; big blocks are efficient to read but waste more space at the end of each request and are less likely to be shareable. vLLM's default is 16 tokens per block.
8 Discussion · original
The authors note when the idea does not apply: paging pays off because LLM serving allocates memory dynamically (unknown output lengths) and is limited by memory capacity. Training, with its fixed tensor shapes, and serving small models that are limited by compute, would gain little and pay the overhead of looking up scattered blocks.
What happened next
| Development | Why it matters |
|---|---|
| vLLM, open source at github.com/vllm-project/vllm, became a widely used serving engine | Paged KV caching is available to anyone serving an open model |
| Automatic prefix caching across requests | Block-level sharing extends naturally to reusing any repeated prefix, the server-side form of prompt caching |
| Combined with other serving techniques | Paged memory sits alongside continuous batching, speculative decoding, quantization and FlashAttention-style kernels in modern servers |
The inference lesson simulates continuous batching and computes KV-cache sizes from scratch.
Glossary
Every term with hover guidance on this page, in one place.