How PagedAttention Powers vLLM's KV Cache

Here is a result that surprises people the first time they hit it. You load a 13B model onto a GPU with plenty of spare memory and point some traffic at it. Long before the math says you should be out of room, the server starts refusing requests or slows to a crawl. The weights fit. The activations fit. What ran out is the KV cache, the per-request store of attention state that grows with every token. More often than not, the memory it needed was there all along, just chopped into pieces too awkward to use.

This post is for engineers who serve open models on their own GPUs, with engines like vLLM or Hugging Face’s Text Generation Inference (TGI), and who want to know what the engine actually does with that memory. It covers three things:

• why the obvious way to store the KV cache wastes most of it,
• how PagedAttention borrows paging from operating systems to get almost all of it back,
• where the approach still bites.

If you’ve read the KV cache post, this unpacks the paragraph that mentioned PagedAttention in passing.

Quick recap: the KV cache is per token, and it grows

During generation, the model keeps a key vector and a value vector for every token it has already seen, at every layer. Keeping them means it doesn’t have to recompute attention over the whole prefix for each new token. That store is the KV cache.

The cache grows linearly with sequence length and with batch size (the number of requests processed together). On a busy server it is usually the largest memory cost. The weights are a fixed cost, but the cache scales with how many requests you serve and how long each one runs. I did the per-token arithmetic in the earlier post. The one fact to carry forward: the cache is large, live, and a different size for every request.

That last part is the whole problem.

Why contiguous storage wastes most of your memory

The straightforward implementation stores each sequence’s cache in one contiguous slab of GPU memory. The trouble is that you don’t know how long a request will run when it arrives: a user might want three tokens or three thousand. To be safe, the server reserves a slab sized to the maximum context length. A request that stops after 40 tokens still holds a reservation sized for 2,048 and leaves the rest empty until it finishes.

Three kinds of waste pile up. They are the same three you’d see in any naive memory allocator:

• Internal fragmentation: the reserved but unused tail of each request’s slab. This is the dominant cost, because most requests are far shorter than the maximum.
• External fragmentation: free gaps between slabs that are each too small to hold a new request’s reservation, so nobody can use them.
• Over-reservation: memory a request will use eventually but hasn’t yet. In the meantime it sits out of reach of everyone else.

The vLLM team measured production serving systems and found they used as little as 20 to 40% of the memory allocated to the KV cache. The rest was lost to exactly these three kinds of waste (Kwon et al., “Efficient Memory Management for LLM Serving with PagedAttention,” SOSP 2023).

That waste has a direct cost. Every gigabyte tied up in an unused reservation is a gigabyte that can’t hold another request’s cache. That caps how many sequences you can batch together, and batch size caps throughput. Here, memory efficiency and throughput are the same lever.

PagedAttention: paging, borrowed from the operating system

Operating systems solved this exact problem decades ago, and PagedAttention is a fairly direct port of their solution. An OS doesn’t give each process one contiguous chunk of physical memory. Instead it splits memory into fixed-size pages and lets a process’s address space scatter across whatever pages are free. A page table translates the addresses the process sees, which look contiguous, into physical locations (Arpaci-Dusseau, Operating Systems: Three Easy Pieces, paging chapter). Fragmentation drops to at most one partly used page per process, because only the tail is ever over-allocated.

PagedAttention maps that idea onto the KV cache almost term for term:

• A block is a page: a fixed-size slot holding the keys and values for a small, fixed number of tokens. vLLM’s default is 16 tokens per block.
• A sequence is a process. Its cache is a list of logical blocks that look contiguous to the attention code.
• A block table is a page table. Each sequence has one, and it maps each logical block to the physical block that actually holds it, anywhere in GPU memory.

Here is how a sequence’s cache grows and shrinks. When the sequence needs room for more tokens, the engine takes a free physical block from a shared pool and appends an entry to the sequence’s block table. When the sequence finishes, its blocks go straight back to the pool for the next request. Nothing is reserved up front. The only waste left is the last, partly filled block of each active sequence, which is where the paper’s “under 4%” figure comes from (Kwon et al., 2023).

The attention kernel has to read scattered blocks

This is more than a bookkeeping change. Attention needs every key and value in the sequence, and those now live in blocks scattered across memory rather than in one run you can stride through. So the attention kernel (the GPU function that computes attention) has to change too. It walks the block table and gathers keys and values block by block. vLLM ships a custom CUDA kernel to do exactly that (vLLM launch post).

That is why PagedAttention is a serving-engine feature and not something you can bolt onto a stock model.generate(). The memory layout and the kernel that reads it are designed together.

The bonus contiguous storage can’t give you: sharing

Once the cache lives in blocks behind a translation table, two sequences can point their block tables at the same physical block. That turns out to be worth as much as the fragmentation win.

The clearest case is a shared prefix. Suppose ten requests all begin with the same long system prompt. Under contiguous allocation, you store that prompt’s cache ten times. With blocks, the engine computes the prompt’s blocks once and shares them, and each shared block carries a reference count (how many sequences point at it).

When one sequence needs to write past the shared region (because it sampled different tokens, say), the engine copies that block first, so the divergent part stays private. This is copy-on-write, the same mechanism behind fork() in a Unix process. vLLM builds automatic prefix caching on top of it (vLLM launch post).

The same trick makes parallel sampling and beam search cheap. Both produce several candidate outputs that branch from one prompt. With shared blocks, the candidates reuse the prefix instead of each paying for a full copy.

Using it

vLLM caught on because none of the above leaks into your code. You get the memory behaviour just by using the engine. The snippet below generates text for two prompts; block tables, the shared pool and reclamation all happen inside the LLM object:

from vllm import LLM, SamplingParams

llm = LLM(model="mistralai/Mistral-7B-Instruct-v0.2")
params = SamplingParams(temperature=0.7, max_tokens=256)

prompts = ["Summarize this incident report: ...", "Draft a shift handover note: ..."]
for out in llm.generate(prompts, params):
    print(out.outputs[0].text)

Block size, how much GPU memory the cache pool may claim, and prefix caching are all knobs on the engine. You don’t manage them per request. The one worth knowing early is gpu_memory_utilization (default 0.9). It sets the fraction of the card vLLM reserves for the weights plus the KV cache pool, and it’s the dial you reach for when tuning how many sequences you can batch.

Where it bites

Paging doesn’t create memory. It only stops you from wasting it, so a busy enough server still fills the pool. What happens then is the interesting part.

Preemption isn’t free. When the pool is exhausted and a running sequence needs another block, vLLM has to evict something. It preempts (pauses) one or more sequences and either swaps their blocks out to CPU memory or recomputes them from scratch later. These are the two eviction strategies the paper describes for a full pool (Kwon et al., 2023). Either way, the preempted request stalls, and under sustained overload you’ll see latency spikes and falling throughput. Paging pushes the cliff much further out, but it doesn’t remove it. Watch for preemption in the engine’s metrics: it’s an early sign you’re over capacity, not a bug.

Block size is a real tradeoff. Bigger blocks mean fewer block-table entries and less per-block overhead. They also mean more waste in the last partial block of each sequence, so internal fragmentation creeps back in. Smaller blocks cut that waste but add bookkeeping, and they can leave the attention kernel doing more, smaller reads. 16 is a sensible default for a reason. Change it only after you’ve measured.

Non-contiguous reads have a cost. Gathering keys and values through a block table is genuinely more work than striding one contiguous array, so each attention operation is slower on paper. It wins anyway, because the freed memory lets you run a much larger batch, and the batch-size gain dwarfs the per-operation cost. That trade only holds while you’re memory-bound and batching hard. Real servers do live in that regime, but it’s worth naming rather than assuming.

It’s independent of the other levers. PagedAttention manages where the cache lives. It doesn’t change how big each token’s cache is. Grouped-query attention (several query heads sharing one set of keys and values), a quantized cache, and shorter contexts all shrink the per-token cost, and they stack on top. Paging plus a smaller per-token footprint gives you a bigger batch than either alone.

Tradeoffs, and what I’d reach for

If you serve an open model to more than a trivial amount of traffic, use an engine that pages the cache. On a self-hosted setup it’s usually the single biggest throughput win available, and vLLM makes it the default path rather than a flag you have to find (Kwon et al., 2023). The paper reports between 2x and 4x the throughput of the previous generation of serving systems. That gain comes from exactly this chain: reclaimed memory becomes a bigger batch, and a bigger batch means more tokens per second on the same card.

Where I’d stop short: batch-size-one on a laptop GPU, or a single-user internal tool that never sees concurrency. There, the paging machinery solves a problem you don’t have, and a simpler runtime is less to reason about. The design earns its complexity when sequences of unpredictable length compete for one pool, which is exactly the shape of any real serving workload.

That competition is the environment I spend my time in. The tooling I worked on around the CMS experiment at CERN runs jobs on shared GPU and HPC (high-performance computing) capacity, where the scarce resource is memory and the workloads never line up neatly. PagedAttention encodes a simple instinct: hand out small pieces on demand, share what’s identical, and reclaim the moment you’re done. The same instinct keeps Archi, the retrieval copilot I built for CMS operations, answering more than one operator at a time without a GPU per person. Good memory management rarely shows up in a demo. It shows up as the request that gets served instead of dropped.

Diagrams by M. Hassan Ahmed, released under CC0. No external image was used for this post; the figures are original work by the author.