Era 6 · Generative models and systems · 2023

49 vLLM / PagedAttention

Efficient Memory Management for LLM Serving with PagedAttention · Kwon, Li, Zhuang et al. · UC Berkeley · SOSP
🟧 read selectively~1.5–2 horiginal ↗
The gist in 20 seconds. Manage the KV cache the way an OS manages virtual memory: cut the cache into block-sized "pages" that need not be contiguous. Fragmentation disappears → more requests fit in a batch → LLM serving throughput ×2–4. This is the vLLM engine.

Context

In LLM SERVING most of the memory goes to the KV cache — the stored keys and values for each request's context; it grows with every new token, and requests have different lengths.

The idea and the mechanism

Naive storage (a contiguous buffer sized for the maximum length, per request) produces enormous fragmentation and over-reservation → few requests fit, throughput is low. The fix, by analogy with an OS's virtual memory: cut the KV cache into fixed-size blocks ("pages") that need not be contiguous; a "page table" maps logical token positions onto physical blocks.

systems Paging for the KV cache: where the ×2–4 comes from

The KV cache for one request is 2 · L · nheads · dhead · ntokens (K and V for every layer and token) — and it grows as generation proceeds. The trouble with the naive approach is two kinds of fragmentation:

  • Internal: you reserve a buffer for the maximum length, but the request is shorter → the slots sit idle.
  • External: requests of different lengths leave "holes" that nothing fits into.

In practice only about 20–40% of the memory was doing useful work. PagedAttention: the cache is a set of fixed-size blocks, and a block table ties logical token positions to arbitrary physical blocks. Memory is allocated as the context grows, there are almost no holes → utilization near 100% → many times more requests fit in the same memory → bigger batches → throughput ×2–4 at the same latency.

Python The block table (the paging idea) 
# logical token positions → arbitrary physical blocks
block_size = 16
block_table = {}                    # request_id → [phys_block, ...]

def append_token(req, kv, pool):
    blocks = block_table.setdefault(req, [])
    if len(blocks) * block_size <= req.len:   # need a new block?
        blocks.append(pool.alloc())           # allocate as it grows
    write(blocks[-1], kv)                       # no contiguity, no over-reservation
naive (contiguous): reserved space sits idle → paged (blocks): blocks anywhere, no holes
A contiguous buffer over-reserves and fragments; a paged cache allocates a little at a time and packs it tightly.
Analogy. The same story as memory in an operating system. Handing every program a contiguous chunk of RAM "with room to spare" is wasteful and leaves holes. The OS cuts memory into pages, hands them out in any order and keeps a table of where things went. PagedAttention carries that OS trick over to the KV cache of an LLM, quite literally — hence the name.

Why it matters

One of the most widely used open-source inference engines; it showed that systems ideas from OS design move LLM serving efficiency directly (cost and latency in production). A bonus: blocks can be SHARED across requests (a common system prompt or prefix) via copy-on-write.

Connections

← uses48. FlashAttention

vLLM computes the attention itself with FlashAttention kernels, while PagedAttention manages the memory across requests. Two levels of inference optimization: inside attention (Flash) and around it (Paged).

← serves32. Transformer

The KV cache exists precisely because of the Transformer's autoregressive attention: K and V are cached so that the past need not be recomputed at every step. vLLM makes that cache cheap to manage — a direct consequence of the architecture in #32.

→ for open models50. LLaMA

Open models like LLaMA have to be run somewhere efficiently — vLLM became the standard serving engine for them. Open weights + efficient inference = practical self-hosted LLMs.

Questions worth asking

Why did a "systems" idea, rather than a new model, give such a jump?

Because the serving bottleneck was not model quality but memory utilization: at 20–40% useful use, two thirds of expensive VRAM sat idle. By removing fragmentation, vLLM improved no model at all — it let many times more requests fit in the same memory. The lesson: part of the progress in ML is classical systems engineering, not new architectures.

What does prefix sharing buy you, and where is it genuinely useful?

If many requests share a long system prompt (or few-shot examples), its KV blocks can be stored once and referenced from every request (copy-on-write, like shared pages in an OS). That saves memory and the time to prefill it again. It is especially useful in production, where thousands of requests share one large system prompt.

Does paging have a price, or is it free?

Almost free, but not quite: you pay overhead for the block table and the indirection, and the attention kernel has to cope with non-contiguous memory (a special PagedAttention kernel). That makes the implementation more complicated than a contiguous buffer. But the gain in memory utilization outweighs those costs many times over — the classic systems trade of "slightly more complex code for a much better use of the resource".

What to read in the original

Read the essentials — the paging analogy, KV-cache fragmentation, prefix sharing.