KV cache and PagedAttention

Lesson 4.3 · 4 min read · by Vinay C

We'll cover the following

An LLM writes one token at a time. To pick token 101 it must attend to tokens 1 to 100, and each earlier token contributes a Key (K) and a Value (V) vector at every layer. Those never change once computed, so the server stores them in GPU memory instead of recomputing them for every new token. That store is the KV cache. It trades memory for compute.

Two phases

PhaseWhat happensBottleneck
PrefillProcess the whole prompt at once and fill the cacheCompute
DecodeGenerate one token at a time, reading the cacheMemory bandwidth

Why long contexts are expensive

The cache grows with every token, for every layer and every request: roughly 2 (K and V) x layers x kv_heads x head_dim x bytes per token. For a 70B-class model that is a few hundred KB per token, so one 8K-token request can hold about 3 GB. Twenty concurrent users can fill a whole GPU on top of the weights. So concurrency is usually limited by cache memory, not compute.

PagedAttention (vLLM)

Old servers reserved one contiguous block per request, sized for the maximum length. Most requests use far less, so 60 to 80% of cache memory was wasted on unused tails and unusable gaps (fragmentation). PagedAttention borrows from OS virtual memory:

  • Split the cache into small fixed-size blocks (for example 16 tokens).
  • Each request has a block table mapping its token positions to blocks anywhere in GPU memory.
  • Allocate a block only when needed, so waste drops to under about 4% and you batch many more requests (often 2 to 4x throughput).
  • Blocks can be shared: requests with the same system prompt point to the same blocks, and a block is copied only when one request writes to it (copy-on-write).

That sharing is what prompt caching really is: a hit means reusing the K/V blocks already computed for an identical prefix. This is why the static part of the prompt must come first and match exactly.

Check yourselfWhy does doubling the context length roughly halve the number of users one GPU can serve?

The cache per request doubles, and cache memory is what limits concurrency, not compute.

Summary: say it in the interview

  • "Decode speed and concurrency are limited by KV-cache memory. PagedAttention manages it like virtual memory, with small blocks allocated on demand, so fragmentation almost disappears and I can batch far more requests. The same block sharing makes prefix caching cheap."