Vol. XXIII · Serving Plate 3 of 9paged attention, vLLM, fragmentation, memory allocation, KV cache, concurrency, blocksCE

Running Out of Cache.

Reserve for the longest possible answer and most of the memory sits empty. Allocate as tokens arrive instead.

A server does not know how long an answer will be when a request arrives. Early systems reserved a contiguous region of cache for the maximum length — the prompt plus the largest permitted output — so that a sequence could grow in place. Most answers are far shorter, and the reserved remainder can be used by nobody: fragmentation. Kwon and colleagues measured that most of the KV memory reserved by existing systems held no token states at all.

Their fix, PagedAttention in the vLLM server, borrows from operating systems: the cache is divided into fixed blocks of a few tokens, a sequence’s blocks need not be adjacent, and a block table maps positions to blocks, exactly as page tables map virtual to physical memory. A sequence takes a new block only when it fills its last one, so waste is under one block per sequence. The workshop serves Llama 3 8B on one H100 with requests of 1 000 prompt and 250 output tokens on average, a maximum length of 8 192, and either allocation.

Below: left, how many requests fit at once under each allocation; right, the median time to first token as the request rate rises. Readouts give the share of reserved cache that holds real tokens.

What you will learn
Workshop
Simulated: Llama 3 8B in BF16 on one H100 (about 56 GB of cache after weights), Poisson arrivals, prompt and output lengths exponential with means 1 024 and 256, continuous batching. Contiguous: each request reserves 8 192 tokens. Paged: 16-token blocks allocated as needed. Times are roofline estimates from the H100’s published specifications (989 TFLOP/s dense BF16, 3.35 TB/s), assuming 60% of peak compute and 80% of peak bandwidth are reached plus 0.2 ms per pass — not measurements.

Fragmentation is lost users

Reserving 8 192 tokens per request fits 52 requests in the cache, of which only 15% holds real tokens; paging fits 333 — 6.4 times as many — with 99% in use. At 18 requests a second the difference shows up as waiting: requests that cannot be admitted queue for a slot, and the median time to the first token is 6.01 s with contiguous reservation against 0.054 s with paging. The GPU’s arithmetic is the same in both; only the bookkeeping changed.

In the systems Kwon and colleagues profiled, only 20.4% to 38.2% of the KV memory held token states. Paging has a second benefit the workshop does not model: blocks can be shared. Several samples from one prompt, or many requests with the same system prompt (plate XXIII.6), can point at the same physical blocks and copy only on write. Kwon and colleagues reported throughput 2–4 times that of earlier systems at the same latency. Paged KV memory is now the default in open-source servers, and when even paging runs out, servers pre-empt a request — evicting its cache to recompute or swap it in later.

The block size is a trade-off: smaller blocks waste less of the last block, larger ones make the attention kernel’s memory accesses more efficient. 16 tokens is a common default.

Terms

Fragmentation
Reserved memory that holds nothing and can be used by nobody.
Paged attention
Allocating the KV cache in fixed blocks mapped by a table.
Block table
The map from a sequence’s positions to physical cache blocks.
Pre-emption
Evicting a running request’s cache when memory runs out.
Contiguous reservation wastes most of the cache; paging allocates as tokens arrive and serves several times the requests on the same GPU.

Sources

  1. Kwon et al., “Efficient Memory Management for Large Language Model Serving with PagedAttention”, SOSP 2023.
  2. Kilburn et al., “One-Level Storage System”, IRE Transactions on Electronic Computers, 1962 (paging).