This post works through Kwon et al., "Efficient Memory Management for Large Language Model Serving with PagedAttention" (arXiv:2309.06180). The paper starts from a waste problem: in the serving systems it measured, only 20.4% to 38.2% of the KV cache memory held real token states. It names three causes: reservation of room for the maximum length, internal fragmentation inside each reservation, and external fragmentation between reservations. Its answer, PagedAttention and the vLLM server built on it, borrows paging from operating systems. In short: instead of reserving one big contiguous stretch of memory per request, give each request small fixed-size blocks only when it needs them, keep a table that says where its blocks are, and let requests that share text point at the same blocks, copying one only when someone needs to change it. The abstract reports 2-4x higher throughput than FasterTransformer and Orca at the same latency. Below I work through one request by hand, then watch many requests share a fixed memory budget in a small playground. I spend the first half on the problem on purpose: the fix only makes sense once the waste feels real.
Want to poke at the playground first? It is a single HTML file with no install and no network calls: pagedattention-playground. You can switch between paged and contiguous allocation and change the number of requests, their sizes, the memory budget and the block size.
Words used below
- KV cache: the keys and values the model keeps for every token it has already read, so it does not recompute them for each new token.
- Prompt phase (prefill): the model reads the whole prompt in one go and builds the KV cache for it.
- Decode step: producing one new token. The model repeats this once per output token, and each step needs the KV cache of everything so far.
- Parallel sampling: asking the model for several different answers to the same prompt at once, then choosing among them.
- Beam search: growing several candidate answers together and, at each step, keeping only the most promising few.
- Reference count: a counter on a piece of memory saying how many users currently point at it; when it drops to zero, the memory can be freed.
- Copy-on-write: share something until someone needs to change it; then that one gets a private copy of just the part it changes.
The parking-row problem
Picture a car park where every car that arrives gets a whole row reserved, because it might turn out to be a long limousine. Most cars are ordinary. The row is mostly empty, nobody else can use the empty part, and the car park turns people away while looking nearly empty.
That is how a plain KV cache works. Every token a model has already processed leaves behind a key vector and a value vector in every layer, and the next token needs all of them. The usual way to store them is one contiguous tensor per request, which has real advantages: there are no pointers to chase, and finding any element costs the same, because its address is a simple formula of its position. The problem is that the tensor grows by one token per step, and you do not know where it will stop. So systems reserve room for the maximum length up front.
Reserved rows. Each car is given a whole row for the longest car it could become, so three park and three wait at the gate, while most of every row stays empty.
One request, worked through
Take the OPT-13B shape: 40 layers, a hidden size of 5120, and fp16 numbers (2 bytes each). Each token stores a K and a V vector in every layer:
bytes per token = 2 (K and V) x 40 layers x 5120 x 2 bytes = 819,200
That is 800 KiB, or about 0.82 MB.
Now a request with a 100-token prompt that has generated 50 tokens, so 150 tokens, with a maximum length of 2048:
- Reserved: 2048 x 819,200 = 1,677,721,600 bytes. That is 1.56 GiB (1.68 GB in decimal units). The paper says "as much as 1.6 GB", which is the GiB figure.
- Actually used: 150 x 819,200 = 122,880,000 bytes, 117.2 MiB.
- Unused: 1 - 150/2048 = 92.7%.
That 92.7% is a worst-case-style example for this setup, not a measured average: a short 150-token request sitting in a 2048-slot reservation on the OPT-13B shape. The paper's 20.4% to 38.2% is the share of KV cache memory that held real token states in the existing systems it measured, so about 61.8% to 79.6% waste (its Figure 2, the average over the three Orca baselines during its section 6.2 experiment; for vLLM the same figure shows 96.3%). It is lower than my figure because real requests are longer than 150 tokens, and the waste shrinks as requests get closer to the maximum length: a request that really reaches 2048 tokens wastes nothing.
Two kinds of waste
The 1,898 unused slots are one kind of waste, and there is a second kind that a single request cannot show. In the car park:
- The unused tail of the row: reservation while the car is running, internal fragmentation once it has left. These are the same slots, looked at at different times. While our request is at token 150 it may still grow, so the empty part of its row is a reservation: those slots might be filled later, but until then nobody else can have them. When the request ends at, say, token 200, the other 1,848 slots turn out never to have been used, and the same empty tail is now internal fragmentation. Nothing about the slots changed, only whether the car has left. The paper lists the two as separate sources of waste (slots that will be filled later, and slots never filled because of over-provisioning for the maximum length), but while a request is running nobody can tell which slots are which, so for the allocator they are one unused tail. The paper makes the related point that the never-used part is only realised after the request has finished.
- External fragmentation. Rows of different sizes come and go, and the free space ends up in pieces, none of which fits the next car. A small example in slots: a pool of 3000 holds four requests with reservations of 1000, 500, 1000 and 500, in that order. The two 500-slot requests finish. Now 1000 slots are free, but in two separate holes of 500. A new request that needs 800 slots does not fit, even though 1000 are free. Compaction (moving everything together) can cure this in principle, but it is too slow to do often.
In my playground the contiguous mode gives every request an equal-sized slab, so it can show the unused tail but never external fragmentation. That one is the paper's point, not something I simulated.
Why wasted memory slows everything down
Waste would be tolerable if memory were cheap. It is not the memory that hurts; it is what the memory was supposed to be doing. Auto-regressive decoding is memory bound: each step produces one token per request, and a step costs roughly the same whether it serves one request or several, because the model weights have to be read either way. So the way to get more tokens per second out of a GPU is to put more requests into each step. This holds only while reading the weights dominates the cost of a step. Every request in the batch also reads its own KV cache, and that part grows with each request added and with every token of context, so at large batches or long contexts the KV reads take over and the gain from batching levels off. This is my reasoning, not something I measured.
What limits the number of requests in a step is KV cache memory. Every request in the batch needs its KV cache resident, and the reserved-but-empty slots are memory that no other request can use. The paper makes this claim in its own words: reserved memory, though eventually used, occupies space that could otherwise be used to process other requests.
A rough capacity check. My first guess was that an 80 GB GPU holds about 40 requests "even with optimal use". That ignores the weights. OPT-13B in fp16 is 13e9 x 2 bytes = 26 GB (24.2 GiB), leaving about 55.8 GiB. Dividing by the 1.56 GiB reservation gives about 35 requests at most with contiguous 2048-token slabs, however short they really are. This ignores activations and everything else, so read it as arithmetic, not a benchmark. The paper reports, for a 40 GB A100 serving a 13B model, that roughly 65% of memory is weights and close to 30% is the dynamic request state. Its Figure 1 labels the parameters as 26 GB, 65% of the 40 GB, which matches the 26 GB I computed.
The playground shows the problem at small scale. With 2 GiB reserved for 8 requests (about 100 prompt tokens and 50 generated tokens each), contiguous mode fits one 2048-slot slab, so it serves one request at a time: 444 cycles, with 93.4% of the reserved slots empty on average. A cycle is a decode step, not a unit of time, so treat the cycle count as a shape and not a measurement. The same run with paged allocation is compared further down.
And a contiguous cache cannot share a prompt
The third problem is separate from waste. With parallel sampling (asking for several different answers to one prompt) or beam search (growing several candidate answers and keeping the most promising), one prompt fans out into several continuations that share the same prompt keys and values, but systems that keep one contiguous KV tensor per sequence cannot take advantage of that.
The cost is easy to count. A 100-token prompt is 100 x 819,200 bytes = 78.1 MiB of KV cache. Four parallel samples that each store their own copy hold 312.5 MiB, where one shared copy would hold 78.1 MiB; 234.4 MiB (75%) is duplicate. The same applies to separate requests that start with the same system prompt, and the paper's abstract claims sharing "within and across requests" as one of its two results.
There is also a structural reason. A contiguous tensor must be one unbroken run of slots. Two continuations that share a prompt both need to grow in the slots right after it, with different tokens, and only one of them can. The other has to be copied elsewhere. So the duplicate copies are not just wasted bytes. They are bytes that cannot be shared, which makes the capacity problem above worse.
Four parallel samples of one 100-token prompt with contiguous caches. Each keeps its own 78.1 MiB copy of the prompt's keys and values, 312.5 MiB in total, where one shared copy would take 78.1 MiB.
The fix: borrow paging from the operating system
An operating system does not give a process one giant contiguous slab of RAM. It cuts memory into fixed-size pages and keeps a page table per process that maps "the process's page 3" to "physical frame 812". The process sees a tidy contiguous space; the frames can be anywhere.
PagedAttention does the same for the KV cache:
- Cut the cache into fixed-size blocks of B tokens (K and V for B tokens).
- Allocate a block only when the sequence needs it.
- Keep a block table per request: logical block 0, 1, 2... mapped to whatever physical blocks were free.
Paged bays. The same six cars, each holding only the bays it is using. All six fit, their bays are scattered, and only the last bay of a car is partly empty. (The cars are drawn shorter than the 10-bay running example so that six fit in the picture.)
Both kinds of waste from above go away by different mechanisms:
- The unused tail shrinks to one block. A block is allocated only when the next token needs it, so nothing is reserved ahead. What is left of the old reservation, or of the internal fragmentation once the request ends, is the unused part of one last block per sequence, at most B - 1 slots.
- External fragmentation disappears because every block is the same size. In the earlier example, 800 slots is 50 blocks of 16, the 1000 free slots are 62 whole blocks, and it does not matter that they are in two places.
Running example, B = 16. The prompt of 100 tokens needs ceil(100/16) = 7 blocks, with 12 slots free in the last one. Each generated token fills the next slot; the 7 blocks hold 112 tokens, so the 113th token triggers an 8th block. After 50 generated tokens we are at 150 tokens: 150 / 16 = 9.4, so 10 blocks, 160 slots, 10 wasted slots. The 10 wasted slots are all in the last block, and they cost 10 x 819,200 bytes = 7.8 MiB, against 1.56 GiB reserved before. Nothing was reserved ahead of time.
Attention itself changes in one place. The kernel computes attention block by block, and the softmax denominator still sums across all blocks, so the result for the query token is the same as before. What changes is that the keys and values it reads no longer have to sit next to each other; it follows the block table. (So this is a change to the attention kernel, not just to the allocator.)
What that buys, using the same arithmetic as before: dividing the 55.8 GiB by 125 MiB (the 160 slots this request holds) gives about 457 requests at 150 tokens each, against about 35 with 2048-slot slabs. Same caveats: it ignores activations and everything else, so it is arithmetic, not a benchmark.
Two things to notice
- Blocks of one request need not be neighbours. In the playground you can see a request's table jump from physical block 5 to 21 and nothing breaks.
- Waste is capped, and it is a percentage of what was allocated. Only the last block of each sequence can be partly empty, so at most B - 1 slots per sequence. The other 1,888 slots of the old 2048-slot reservation are not wasted at all; another request can use them. That is the real win, more than the percentage.
Many requests, one fixed memory: first-come-first-served
One request is easy. The interesting part is several requests sharing a fixed budget. The playground runs 4 to 8 requests of the running example (mean 100-token prompt and 50 generated tokens, each varied by up to plus or minus 30%, all adjustable) against a fixed KV memory that you type in. One cycle is one decode step of the whole batch. Each cycle the scheduler does three things in order:
- In paged mode, bring back swapped requests if blocks are free (oldest first).
- Admit waiting requests in arrival order. A request that does not fit blocks the ones behind it; that is what first-come-first-served means. In paged mode nothing is admitted while a preempted request is still unfinished, which is the paper's rule.
- Give every running request one new token, taking a new block when its last block is full. If no block is free, the most recently arrived running request is swapped to CPU memory whole.
One rule here is my own addition, not something I read in the paper: a swapped request only returns when the free blocks cover its blocks plus one spare block per running request. Without it, my simulator swapped a request in and straight out again within the same cycle.
Paged mode with 0.3 GiB (24 blocks of 16 tokens), 21 cycles in. R3, the latest arrival among the running requests, was swapped to CPU at cycle 15; R4 onward are held back; each request's block table is on the right and the waste is 6.9% now, 6.4% averaged so far.
The timeline in the playground has one row per request and one column per cycle, so the first-come-first-served order and each swap are visible. The GPU-work meter uses the rough rule of 2 x 13e9 = 26 GFLOPs per token processed, which ignores the cost of attention itself, so it is a scale and not a measurement.
What the memory budget does
With the default requests (the fixed starting seed, 8 requests, block size 16), running to the end gives:
| Reserved KV memory | Paged: cycles to finish | Swap-outs | Paged waste, run average | Contiguous (2048-token slabs) |
|---|---|---|---|---|
| 2 GiB | 65 | 0 | 5.1% | 1 request at a time, 444 cycles, 93.4% waste |
| 0.5 GiB | 156 | 1 | 5.1% | does not fit: one slab needs 1.56 GiB |
| 0.3 GiB | 242 | 2 | 5.1% | does not fit |
At 4 GiB the contiguous mode fits two slabs and finishes in 227 cycles, still with 93.4% average waste.
Two comparisons with the paper, so these numbers are not read as more than they are. First, the playground's contiguous mode reserves the full maximum length for every request, which is what the paper's Orca (Max) baseline does: it always reserves space up to the model's maximum sequence length, 2048 tokens. Its other two baselines reserve less. Orca (Pow2) over-reserves the output space by at most 2x, and Orca (Oracle) is assumed to know the true output lengths, an upper bound the paper calls infeasible in practice. So the 20.4% to 38.2% in its Figure 2 is a range over three reservation policies. Mine is the same policy as the worst of them, Orca (Max), whose 20.4% is the "as low as 20.4%" the paper quotes; my 93% (the playground's average over the run, a number from my own workbench and not from the paper) is higher than its roughly 80% waste, and my explanation is that my example requests are shorter than the ones in the paper's workloads. I have not checked their lengths, so take that as my own reading. Second, the abstract claims near-zero waste, while my paged runs show about 5% at B = 16 (Figure 2 puts vLLM at 96.3% of KV cache memory holding token states, so about 3.7% not). That is because my requests are short: paged waste is at most B - 1 slots per request, 7.5 on average at B = 16, which is 5% of a 150-token request but only 1.5% of a 500-token one.
Contiguous mode with 2 GiB: one 2048-slot slab fits, so one request runs while the rest wait. R2 has used 123 of its 2048 reserved slots; the waste is 94.0% now and 93.4% averaged so far.
Two things to notice
- The paged waste stays near 5% whatever the memory budget. Tight memory costs time (more cycles and swap traffic, 400 MiB at 0.3 GiB), not space.
- A "cycle" is not a unit of time. A cycle with eight requests does more work than one with a single request, so 65 against 444 cycles overstates the speed-up. What it does show is that one reservation per request leaves almost no room for batching.
Paged mode with 2 GiB: all eight requests are admitted in the first cycle, no swapping, finished at cycle 65.
The block-size question
The worry with large blocks is that they bring the reservation problem back, and I wanted the performance characteristics. The playground covers the memory side. With all requests exactly 100 prompt + 50 generated tokens (variance 0) and the same seed rules, running to the end gives:
| Reserved memory | Block size | Blocks in pool | Paged waste, run average | Cycles | Swap-outs |
|---|---|---|---|---|---|
| 0.5 GiB | 4 | 163 | 1.2% | 144 | 2 |
| 0.5 GiB | 16 | 40 | 5.8% | 124 | 1 |
| 0.5 GiB | 64 | 10 | 19.6% | 124 | 2 |
| 2 GiB | 4 | 655 | 1.2% | 51 | 0 |
| 2 GiB | 16 | 163 | 5.7% | 51 | 0 |
| 2 GiB | 64 | 40 | 17.9% | 51 | 0 |
The block counts for 2 GiB (655, 163, 40) come from 2 GiB divided by the block size times 819,200 bytes, rounded down. Treat the swap-out column as noisy: it depends on exactly when requests arrive and finish, and it is not monotonic in block size. The waste column is the stable signal. Large blocks bring the reservation problem back in miniature, which is exactly the worry: with 64-token blocks, a 150-token request holds 192 slots, and on average about a fifth of what is allocated is empty.
The other side of the trade is the block table: more, smaller blocks mean more entries to walk. The playground only counts blocks; it does not measure time, so I cannot give a lookup cost in numbers. What the paper says (section 7.2) is that if the block size is too small, vLLM may not fully use the GPU's parallelism when reading the KV cache, and if it is too large, internal fragmentation grows and the chance of sharing drops. Its measurements found 16 to 128 best on one chat-style dataset (ShareGPT) and 16 or 32 best on another (Alpaca), and vLLM's default block size is 16. Its figure sweeps block sizes from 1 to 256.
So B = 16 is a compromise: 5.8% average waste in my runs against 1.2% for B = 4, and a block table four times shorter.
Two things to notice
- Going from 16 to 64 roughly triples the average waste (5.8% to 19.6% at 0.5 GiB).
- Going from 16 to 4 saves only about 4.6 percentage points of waste. The paper's argument for why smaller is not simply better is about GPU parallelism, which my model does not capture.
Parts of the paper the playground does not show
Sharing and copy-on-write. With parallel sampling or beam search, one prompt fans out into several continuations. With contiguous per-request caches, each continuation would store its own copy of the prompt's keys and values. With block tables, two sequences can point at the same physical blocks, and each physical block keeps a reference count. Per the paper, when a sequence writes into a block whose reference count is above 1, vLLM allocates a new block, copies the old block's contents, decrements the old block's count, and writes into the copy; this is at block granularity, so only one block is copied. When a count reaches 0 the block is freed. The paper reports memory savings from sharing (6.1% to 9.8% for parallel sampling and 37.6% to 55.2% for beam search on OPT-13B with the Alpaca dataset, and 16.2% to 30.5% and 44.3% to 66.3% with ShareGPT). The playground has no forking, so none of this is something I simulated.
The same four samples with paged blocks of 16 tokens. The 100-token prompt fills six blocks completely and the seventh with 4 tokens. Six blocks stay shared (reference count 4). On the first write into the seventh block, three samples copy it and the fourth keeps the original. That is 10 blocks (125 MiB) instead of 400 slots (312.5 MiB), a 60% saving: a little less than the 75% of one ideal shared copy, because the copy happens at block granularity. This is an illustration of the mechanism, not a simulation.
Prefix sharing across requests. Sharing is not only for several outputs of one request. Many requests start with the same text: a long task description, instructions and a few worked examples, often called a system prompt, followed by each user's own input. Per the paper (section 4.4), the service provider can store the KV cache of such a prefix in advance, by reserving a set of physical blocks for a set of predefined shared prefixes, "as how OS handles shared library across processes". A request that starts with that prefix maps its first logical blocks to the cached physical blocks, with the last block marked copy-on-write, and the prompt phase only has to run on the user's own input. The same block-table machinery as above does the work: no new mechanism, just more sequences pointing at the same blocks.
Eight requests that start with the same 341-token prefix. Their block tables point at the same 21 physical blocks (reference count 8) and each holds its own copy of the 22nd block, so the prefix costs 29 blocks (362.5 MiB) instead of 2,728 slots (2,131.3 MiB). Sizes use 819,200 bytes of KV per token, the OPT-13B shape used throughout; I did not check that the paper's model has the same KV size. An illustration of the mechanism with my arithmetic, not a simulation.
The paper measures this on LLaMA-13B with the WMT16 English-to-German dataset and two synthetic prefixes (section 6.4). With a one-shot prefix of 80 tokens, vLLM reaches 1.67x the throughput of Orca (Oracle); with a five-shot prefix of 341 tokens, 3.58x. The text names only that baseline for these two numbers, and I could not tell from it whether the experiment used pre-reserved prefix blocks or computed the prefix per request. My reading of the two results is that the longer the shared prefix is, the more there is to save, which fits the arithmetic in the picture above; that is my inference, not a claim from the paper.
A limit worth stating: the paper's chatbot experiment does not keep a conversation's KV cache between rounds. It rebuilds the prompt from the chat history each time, because, it says, storing the cache between rounds would occupy space that other requests need. So what the paper shows is sharing of predefined prefixes, not a general cache of everything a user said earlier. The playground does not simulate any of this.
Swapping and recomputation. The paper's eviction is all-or-nothing: because attention reads every block of a sequence, either all of a request's blocks leave or none do, and sequences from the same request are preempted together. Evicted blocks can go to CPU RAM through a CPU block allocator, and the swap space can never exceed the GPU block pool. New requests are not accepted until the preempted ones finish. The alternative is recomputation: drop the blocks and regenerate them later by treating the generated text as part of the prompt. In its measurements (section 7.3) recomputation is better at small block sizes, because swapping then needs many small CPU-GPU transfers; swapping is better at large block sizes, though recomputation's overhead is never higher than 20% of swapping's latency; and the two are comparable for block sizes 16 to 64. The playground implements swapping only, and its own spare-block rule is not from the paper.
How this connects to continuous batching
Continuous batching (I also call it "micro batching") works like this: instead of running a batch until its slowest request finishes, the scheduler re-forms the batch every decode step, so a finished request leaves and a new one joins immediately. (The paper calls this fine-grained batching and cites cellular batching and iteration-level scheduling as examples.) The playground's cycle is exactly this: admissions and completions happen between decode steps.
That scheduling style is the reason the memory problem is so sharp. When requests join and leave every step, the amount of KV memory in use changes every step, and lengths are unknown in advance. With contiguous slabs, a request that finishes frees one specific, huge hole. With blocks, it returns identical fixed-size blocks that any other request can use at once. I think of paging as what lets continuous batching actually keep the batch full. This is my reasoning from the mechanics, not a measurement of mine; the paper's evidence is the throughput comparison above.
Try it yourself
- Leave the mode on paged, set variance to 0, and press Run to end at 2 GiB, then 0.5 GiB, then 0.3 GiB. What changes: the waste, the cycle count, or the swap-outs?
- Switch to contiguous at 2 GiB and run it. Watch the timeline: how many requests are ever decoding at the same time? Then set 4 GiB and compare.
- In contiguous mode set the memory to 0.5 GiB. Why does nothing run? Lower the max length until a slab fits, and see how much memory a 150-token request really needed.
- In paged mode, step through the first few cycles with 0.3 GiB and find the first swap-out in the log. Is it the latest arrival? What does that request's row in the timeline look like afterwards?
- Compare block sizes 4, 16 and 64 at 0.5 GiB with variance 0. Which column is stable across runs, and which one is noisy?
- Click "New random requests" a few times at 0.3 GiB. Does the number of swap-outs change much? What does that say about reading too much into one run?
- Look at a request's block table in paged mode. Do its physical blocks ever appear out of order? Why does that not matter to attention?








Top comments (0)