xavier-ramirez.com
STAGE 0 · SERVING · 3 NODES

Managing the KV cache

You already know the KV cache — every token a model generates stores its keys and values so the next one is cheap. But that cache is enormous and grows unpredictably. This is how a serving engine manages it the way an operating system manages memory: fixed pages to stop waste, and shared prefixes to reuse work across requests.

THE 3 IDEAS
01The fragmentation problem02PagedAttention03RadixAttention
NODE 01 / 03

Why the cache wastes most of its memory

A request's cache grows one token at a time, and you can't know in advance how long it will get. The naive fix — reserve the maximum up front — leaves most of the memory empty and unusable.

  • The KV cache is per-request and variable-length. A reply might be 20 tokens or 2,000, and you don't know which when it starts.
  • Naive serving reserves one contiguous slab sized to the maximum length. A short answer leaves most of its slab empty — that reserved-but-unused space is internal fragmentation.
  • Finished requests leave holes. The free space is real, but scattered into gaps too small for the next request — external fragmentation.
  • The result: often under 40% of the cache holds real tokens. The rest is reserved-empty or stranded in gaps.
GPU KV-CACHE · 32 BLOCKS

Raise the reserved length and watch utilisation collapse — then free R2 to strand its blocks in a gap.

Each request reserves its maximum length up front. The taller the reservation, the more sits empty — real tokens fill only a fraction.

CACHE_UTILISATION
IN USE12 / 32 · 38%
RESERVED · EMPTY12 blk
LARGEST GAP8 / 8 free
How full the cache really is: blocks holding tokens, blocks reserved but empty, and the biggest single free run a new request could use.
NODE 02 / 03

PagedAttention — cache in fixed pages

Operating systems beat fragmentation decades ago with virtual memory: chop memory into fixed pages and let a page table scatter them anywhere. PagedAttention does exactly this to the KV cache.

  • Split the cache into fixed-size pages — a handful of tokens each. A request grows one page at a time, only when it needs it. No giant reservation.
  • A block table maps a request's tokens to physical pages, which can sit anywhere in memory instead of one contiguous run. That's the page table from virtual memory.
  • Waste drops to at most one partial page per request — a few percent, versus more than half.
  • Any free page fits any request, so external fragmentation disappears — the requests the naive strip rejected now all fit.
OS ANALOGY · VIRTUAL MEMORY
A page table for the KV cache
In an OS, your program sees one smooth address space while the page table quietly maps it to scattered physical pages. PagedAttention gives each request that same illusion — logically contiguous tokens, physically scattered pages — which is where the name (and the vLLM engine that introduced it) comes from.
CONTIGUOUS vs PAGED · SAME REQUESTS

Add requests — the contiguous strip fills up and starts rejecting; the paged strip keeps packing them in.

Each request reserves 6 blocks contiguously in the naive strip, but only needs a page or two. Paging hands out just the pages it actually uses.

PACKING
CONTIGUOUS67% full
PAGED89% full
NAIVE REJECTS0
Real utilisation each way — tokens held divided by blocks locked up — and how many active requests the naive strip had to reject.
NODE 03 / 03

RadixAttention — reuse a shared prefix

Many requests start with the same tokens — a long system prompt, a few-shot example, a chat history everyone shares. Caching that prefix once, for all of them, is RadixAttention.

  • A shared prefix has identical keys and values for every request — so its cache blocks are identical too. Storing them per-request is pure duplication.
  • Keep every cached prefix in a radix tree — a prefix tree where a shared beginning is a single branch. A new request that matches it reuses those blocks instead of recomputing them.
  • Only the unique suffix costs new memory — and new compute. The shared trunk is a cache hit: nothing recomputed, nothing extra stored.
  • Turn sharing off and every request re-stores the whole prefix — the grey blocks repeat once per request, down the page.
SHARED PREFIX · ONE COPY OR MANY

Turn prefix sharing on — the repeated grey prefixes collapse into a single shared trunk.

Sharing off — every request stores its own copy of the shared prefix. The grey blocks repeat once per request.

PREFIX_CACHE
BLOCKS STORED36 blk
vs NO SHARING36 blk
SAVED0%
Cache blocks stored with sharing versus storing each request's prefix separately, and the memory that saves.
EXPLAIN IT BACK
PagedAttention and RadixAttention both borrow an idea from operating systems. What does each one solve, and how do they differ?
NEXT: QUANTIZATION

Paging and prefix-sharing squeeze more requests into the cache — but every number in it still takes real bytes. Next, quantization: shrinking the weights and the cache from 16 bits down to 8 or 4, and what that costs in accuracy.

← Back: verifiable rewardsContinue to quantization →
Language: English