LLM & VLM courseBlog
134Track 5: LLM inference and serving · session 57 of 65

Memory management: PagedAttention, prefix caching, RadixAttention

The KV cache is the memory that decides how many users a GPU can serve. This session shows why reserving one contiguous slab per request wastes most of it, how PagedAttention cuts the cache into fixed-size blocks found through a block table, how blocks are shared with reference counts and copy-on-write, and how prefix caching and RadixAttention reuse the cache of repeated system prompts, documents and chat turns.

Time: 2.5 to 3.5 hours (reading 2 hours, exercises 1 hour)Level: IntermediateBefore this: Sessions 80 (the KV cache), 125 (decode attention) and 133 (the serving stack)

What you will learn

  • The three kinds of waste in naive KV allocation: reserved-but-unused slots, internal fragmentation and external fragmentation
  • How paging works: fixed-size blocks, a block table per sequence, address translation, and the block-size trade-off
  • How the attention kernel reads K and V through the block table, and what that costs
  • How reference counts and copy-on-write let parallel samples and beams share blocks, with the memory saved
  • How hash-based prefix caching finds reusable full blocks with a chain of block hashes, and why one changed token breaks all later blocks
  • How RadixAttention stores every cached sequence in a radix tree, evicts least-recently-used leaves, and why longest-prefix-first scheduling raises the hit rate
  • How to size the cache in tokens and requests for a real model on a real GPU

Why this matters

On a serving GPU, the model weights are fixed, but the KV cache grows with every user and every token. The number of requests that can run at the same time, and so the throughput, is decided by how well that cache memory is managed.

In session 80 we computed how big the cache is: for Llama 3 8B, 128 KiB per token. In session 133 we followed one request from the API to the GPU. This session is about the part of the engine that hands out cache memory to those requests. Three problems must be solved:

  1. Waste. We do not know how long an answer will be. If each request gets one contiguous slab of memory for its maximum length, most of the slab is never used. The vLLM paper measured that in the systems it studied only 20.4% to 38.2% of KV cache memory held real token states. [Certain]
  2. Sharing. When you ask for 4 samples of one prompt, or run beam search, all candidates have the same prompt. Storing its cache 4 times is wasteful.
  3. Reuse across requests. Thousands of requests start with the same system prompt, the same few-shot examples, the same document, or the earlier turns of the same chat. Their KV cache is identical. Computing it again for each request wastes both memory and prefill compute.

PagedAttention (vLLM) solves the first two with an idea from operating systems: virtual memory with pages. Prefix caching (vLLM) and RadixAttention (SGLang) solve the third by keeping finished caches and matching new prompts against them. The vLLM paper reports 2–4× higher throughput than the systems it compared, at the same latency [Certain that the paper reports this], and SGLang reports up to 6.4× higher throughput for programs with a lot of shared structure. [Certain that the paper reports this]

The problem: fragmentation with naive KV allocation

A request arrives with a prompt of \(P\) tokens and a limit max_tokens on the answer. Early serving systems stored each request’s cache as one contiguous tensor, because attention kernels expected K and V for one sequence in one piece. Since the answer length is unknown, the system must reserve space for the worst case when the request starts:

\[ R_i = P_i + G^{\max}_i, \qquad \eta_{\text{contig}} = \frac{\sum_i T_i}{\sum_i R_i} \tag{134.1} \]
Read the symbols
\(R_i\)
tokens reserved for request \(i\): its prompt length \(P_i\) plus its maximum answer length \(G^{\max}_i\)
\(T_i\)
tokens that request \(i\) really holds right now (prompt plus tokens generated so far)
\(\eta\)
memory utilization: the fraction of the allocated cache memory that holds real token states

The vLLM paper names three kinds of waste [Certain]:

  • Reserved slots. Space for tokens that will be generated later. It is used one day, but for now it blocks other requests.
  • Internal fragmentation. Space inside a reservation that is never used, because the answer stopped before max_tokens. Most answers are much shorter than the limit.
  • External fragmentation. Free gaps between reservations. When requests finish at different times, free memory is cut into holes. A new request may need 320 tokens of contiguous space, and the GPU may have 448 free tokens, but in two holes of 192 and 256. The request must wait.

Step through Figure 1. The same requests run in both memories. The top memory reserves contiguous slabs; the bottom one uses blocks, which we explain in the next section.

token states in usereserved but emptyfree
Figure 1. One KV memory of 1,024 token slots (64 cells of 16 tokens), used two ways. Top: each request reserves prompt plus max_tokens in one contiguous range (first fit). Bottom: each request gets 16-token blocks only when it needs them, anywhere in memory. Requests A to D arrive first; B and D finish; then E, F and G arrive.
How to read Figure 1

Each cell is 16 tokens. Dark fill is real token data, light fill is reserved space that holds nothing yet. At step 4, the contiguous memory has 28 free cells, but the largest hole is 16 cells and E needs 20, so E must wait: this is external fragmentation. The paged memory never has this problem, because any free block can be used. At the last step compare the utilization numbers: about a quarter for the contiguous scheme and above 90% for the paged one, with more than twice as many requests running.

Paging: fixed-size blocks and a block table

Operating systems solved the same problem decades ago. A program sees one long, contiguous virtual address space, but the memory behind it is cut into fixed-size pages that can sit anywhere in physical RAM. A page table maps virtual pages to physical pages. Memory is given out one page at a time, when it is touched.

PagedAttention does exactly this for the KV cache [Certain]:

  • At startup, the engine measures free GPU memory and cuts it into a pool of physical blocks. Each block holds the keys and values of \(\beta\) tokens (vLLM’s default is \(\beta = 16\) [Certain]).
  • Each sequence has a block table: a short list that maps its logical blocks 0, 1, 2, … to physical block numbers. The paper also keeps the number of filled slots per entry. [Certain]
  • Blocks are filled from left to right. A new physical block is taken from the free list only when the last block of the sequence is full.
  • When a request finishes, its blocks go back to the free list. Any free block can serve any request, so there is no external fragmentation.

So a sequence of \(T_i\) tokens uses

\[ n_i = \left\lceil \frac{T_i}{\beta} \right\rceil \text{ blocks}, \qquad \text{waste}_i = \beta\, n_i - T_i \le \beta - 1, \qquad \eta_{\text{paged}} = \frac{\sum_i T_i}{\beta \sum_i n_i} \tag{134.2} \]

All waste sits in the last, partly filled block of each sequence: less than one block per sequence, about \(\beta/2\) tokens on average. With \(\beta = 16\) and sequences of a few hundred tokens, utilization is above 95%.

To read token \(t\) of a sequence (counting from 0), the kernel does the same address translation as a CPU:

\[ j = \left\lfloor \frac{t}{\beta} \right\rfloor, \qquad o = t \bmod \beta, \qquad \text{slot}(t) = \text{BT}[j] \cdot \beta + o \tag{134.3} \]
Read the symbols
\(j\)
the logical block that holds token \(t\)
\(o\)
the offset of the token inside that block, from 0 to \(\beta - 1\)
\(\text{BT}[j]\)
entry \(j\) of the block table: the physical block number
\(\text{slot}(t)\)
the token’s position in the big physical pool, counted in token slots
Figure 2. Address translation with a block table. Top: the sequence in logical order, cut into blocks of \(\beta\) tokens. Middle: the block table. Bottom: the physical pool of 128 token slots, shared with other requests (gray). The chosen token is followed through formula (134.3).
How to read Figure 2

Move \(t\) and watch the arrow jump from the logical block to a physical block that can be anywhere in the pool. Change \(\beta\): small blocks give a longer block table and less waste in the last block; large blocks give a short table and more waste. The readout shows the waste of this sequence from formula (134.2).

Choosing the block size

The block size is a trade-off. Small blocks waste less memory, but each block is a separate small memory read for the attention kernel, and the block tables get longer. Large blocks read memory efficiently but waste more in the last block, and they share less (only full blocks can be shared, as we will see). The vLLM paper found that block sizes from 16 to 128 worked best on ShareGPT traces, while large blocks hurt on the Alpaca trace, where many sequences are shorter than one block. [Certain] SGLang goes to the other extreme: its RadixAttention uses a page size of one token. [Certain]

Attention that reads through the block table

The attention kernel no longer gets one K tensor and one V tensor per sequence. It gets the pool, the block table and the sequence length. For the query \(\mathbf{q}\) of the newest token, the paper writes attention block by block [Certain]:

\[ \mathbf{a}_j = \frac{\exp\!\left(\mathbf{q}^\top K_j / \sqrt{d}\right)}{\sum_{m=0}^{n-1} \exp\!\left(\mathbf{q}^\top K_m / \sqrt{d}\right) \mathbf{1}}, \qquad \mathbf{o} = \sum_{j=0}^{n-1} V_j^\top \mathbf{a}_j^\top \tag{134.4} \]
Read the symbols
\(K_j, V_j\)
the \(\beta \times d\) keys and values stored in physical block \(\text{BT}[j]\); the kernel fetches them through the table
\(\mathbf{a}_j\)
the \(1 \times \beta\) row of attention weights for the tokens of block \(j\)
\(\mathbf{1}\)
a column of ones: it sums the \(\beta\) scores of block \(m\)
\(n\)
the number of blocks of the sequence; slots after the last real token are masked

This is the same math as ordinary attention: the sum over all tokens is just grouped by block. The cost is the indirection. The paper measured the PagedAttention kernel at 20–26% higher attention latency than the contiguous FasterTransformer kernel, which it calls acceptable because attention is only part of the step and the larger batch more than pays for it. [Certain] Modern kernels (FlashAttention, FlashInfer, the split-KV kernels of session 125) read paged caches directly.

Worked example: how many requests fit on one GPU?

Llama 3 8B stores \(2 \times 32 \text{ layers} \times 8 \text{ KV heads} \times 128 \times 2 \text{ bytes} = 131{,}072\) bytes = 128 KiB per token. Suppose that after weights and activations, 60 GiB is left for the cache:

\[ N_{\text{tok}} = \left\lfloor \frac{M_{\text{kv}}}{s} \right\rfloor = \frac{60 \times 2^{30}}{131{,}072} = 491{,}520 \text{ tokens} \tag{134.5} \]

Contiguous, with a reservation of 8,192 tokens per request (1 GiB each): \(491{,}520 / 8{,}192 = 60\) requests.

Paged, if a request really holds 600 tokens on average: \(\lceil 600/16 \rceil = 38\) blocks = 608 slots, so \(\lfloor 491{,}520 / 608 \rfloor = 808\) requests, 13.5× more. Utilization goes from \(600/8{,}192 = 7.3\%\) to \(600/608 = 98.7\%\).

The real gain is smaller than 13.5×, because a request that grows must still find free blocks, and the batch is also limited by compute. But this is the reason paging raised throughput by 2–4× in the paper.

Algorithm 1: the block manager (append one token, with copy-on-write)
  1. state: free list \(F\) of physical blocks, reference count \(\text{ref}[b]\) per block, block table \(\text{BT}_s\) and length \(n_s\) per sequence \(s\)
  2. function APPEND(\(s\), \(\mathbf{k}\), \(\mathbf{v}\)):
  3.   \(j \leftarrow \lfloor n_s / \beta \rfloor\), \(o \leftarrow n_s \bmod \beta\) // formula (134.3)
  4.   if \(j = |\text{BT}_s|\): // last block is full
  5.     if \(F\) is empty: preempt a sequence (swap it out or drop it for recompute), then retry
  6.     \(b \leftarrow F.\text{pop}()\); \(\text{ref}[b] \leftarrow 1\); append \(b\) to \(\text{BT}_s\)
  7.   else if \(\text{ref}[\text{BT}_s[j]] \gt 1\): // block is shared: copy-on-write
  8.     \(b \leftarrow F.\text{pop}()\); copy block \(\text{BT}_s[j]\) into \(b\); \(\text{ref}[\text{BT}_s[j]] \mathrel{-}= 1\); \(\text{ref}[b] \leftarrow 1\); \(\text{BT}_s[j] \leftarrow b\)
  9.   write \(\mathbf{k}, \mathbf{v}\) into slot \(o\) of block \(\text{BT}_s[j]\) in every layer; \(n_s \leftarrow n_s + 1\)
  10. function FORK(\(s\)): new sequence \(s'\) with \(\text{BT}_{s'} \leftarrow \text{copy of } \text{BT}_s\), \(n_{s'} \leftarrow n_s\); \(\text{ref}[b] \mathrel{+}= 1\) for every \(b\) in \(\text{BT}_s\)
  11. function FREE(\(s\)): for every \(b\) in \(\text{BT}_s\): \(\text{ref}[b] \mathrel{-}= 1\); if \(\text{ref}[b] = 0\), push \(b\) to \(F\)

Sharing blocks: reference counts and copy-on-write

Paging gives a second gift: two block tables can point to the same physical block. This is how operating systems share memory between processes after fork(). Each physical block keeps a reference count: how many block tables point to it. [Certain]

Parallel sampling (the API parameter n, used for best-of-n and for RL rollouts that need many answers per prompt): the prompt is prefilled once. Then the sequence is forked into \(n\) samples. All of them point to the same prompt blocks, with reference count \(n\).

A full shared block is never written again, so it can stay shared forever. The problem is the last, partly filled prompt block: every sample wants to write its own next token there. The rule is copy-on-write [Certain]: before writing into a block with reference count above 1, copy it to a fresh block, point this sample’s table to the copy, and decrease the old block’s count. The last sample to write finds a count of 1 and writes in place, without a copy.

prompt tokensample 1sample 2sample 3sample 4reference count above 1 (shared)
Block manager (Algorithm 1, short form)
  1. APPEND(\(s\)): \(j \leftarrow \lfloor n_s/\beta \rfloor\), \(o \leftarrow n_s \bmod \beta\)
  2.   if \(j = |\text{BT}_s|\): \(b \leftarrow F.\text{pop}()\); \(\text{ref}[b] \leftarrow 1\); append \(b\) to \(\text{BT}_s\)
  3.   elif \(\text{ref}[\text{BT}_s[j]] \gt 1\): copy into \(b \leftarrow F.\text{pop}()\); old ref \(-1\); \(\text{BT}_s[j] \leftarrow b\)
  4.   write \(\mathbf{k}, \mathbf{v}\) at slot \(\text{BT}_s[j]\,\beta + o\); \(n_s \leftarrow n_s + 1\)
  5. FORK(\(s\)): copy \(\text{BT}_s\); \(\text{ref}[b] \mathrel{+}= 1\) for each \(b\)
  6. FREE(\(s\)): \(\text{ref}[b] \mathrel{-}= 1\); if 0, push \(b\) to \(F\)
Figure 3. The block manager of Algorithm 1, run in your browser one APPEND at a time. A prompt of \(P\) tokens is prefilled, the sequence is forked into \(n\) samples, each sample generates \(G\) tokens (round robin), and finally sample 2 finishes. Top: the block table of each sequence. Bottom: a pool of 24 physical blocks; the small squares are the \(\beta\) token slots of a block, colored by who wrote them, and the circle is the reference count. The algorithm line that runs is highlighted; the panel shows formula (134.3) and the copy-on-write test with the live values. With the default settings it runs the same steps as the PyTorch code later in this session.
How to read Figure 3

Press Play. During prefill, one block is taken from the free list each time the last block is full. At the FORK step, nothing is copied: all block tables point to P0, P1, P2 and their counts become 3 (the circles turn to the track color). Then watch P2, the partly filled prompt block. Sample 1 wants to write its token 10 there, but the count is 3, so line 3 runs: P2 is copied into P3 (the blue prompt slots are copied too) and only then the orange token is written. Sample 2 gets a copy in P4. Sample 3 finds count 1 and writes in place. When the third blocks are full, each sample takes a fresh block. The panel then checks formula (134.6): 8 blocks in use, against 12 without sharing. In the last step sample 2 finishes: its private blocks P4 and P6 return to the free list, and P0 and P1 drop to count 2. Change \(\beta\), \(n\), \(P\) and \(G\): the count at the end of decoding always equals (134.6). With \(P\) a multiple of \(\beta\) there is no partly filled block, so no copy happens at all.

How much does sharing save? For a prompt of \(P\) tokens and \(n\) samples of \(G\) tokens each:

\[ \text{blocks}_{\text{no share}} = n \left\lceil \frac{P + G}{\beta} \right\rceil, \qquad \text{blocks}_{\text{share}} = \left\lfloor \frac{P}{\beta} \right\rfloor + n \left( \left\lceil \frac{P + G}{\beta} \right\rceil - \left\lfloor \frac{P}{\beta} \right\rfloor \right) \tag{134.6} \]

Only the \(\lfloor P/\beta \rfloor\) full prompt blocks are stored once; everything after them belongs to one sample.

Worked example: sharing in parallel sampling

\(P = 100\), \(G = 200\), \(n = 4\), \(\beta = 16\). Without sharing: \(4 \times \lceil 300/16 \rceil = 4 \times 19 = 76\) blocks. With sharing: \(\lfloor 100/16 \rfloor = 6\) shared blocks, plus \(4 \times (19 - 6) = 52\), so 58 blocks. Sharing saves \(18/76 = 23.7\%\). With a longer prompt and short answers (for example a RAG prompt of 4,000 tokens), the saving approaches \((n-1)/n = 75\%\).

Beam search shares even more. Beams share the prompt and also long stretches of generated text, and when a beam is dropped its blocks lose a reference and may return to the free list. With reference counts, this bookkeeping is the same code as for sampling. On OPT-13B the paper measured memory savings of 6.1–9.8% for parallel sampling and 37.6–55.2% for beam search on the Alpaca trace, and 16.2–30.5% and 44.3–66.3% on ShareGPT. [Certain]

Token trees. The same idea appears in speculative decoding. SpecInfer verifies a whole tree of draft tokens in one forward pass: candidates that share a prefix share its KV entries, and a tree-shaped attention mask makes each candidate attend only to its own ancestors. [Certain] See session 129.

When memory runs out: preemption

Paging lets the engine admit requests optimistically: it does not reserve their future tokens. So at some step there may be no free block for the next token. vLLM then preempts a request, with an all-or-nothing rule: all blocks of that request are evicted, because a sequence needs all of its tokens to continue. [Certain] Two ways to bring it back [Certain]:

  • Swapping: copy its blocks to CPU memory, and copy them back later. Costs PCIe bandwidth.
  • Recomputation: drop the blocks, and later run prefill again on prompt plus generated tokens. Costs GPU compute, but prefill is fast and parallel, so this is often cheaper for short sequences.

The paper schedules with first-come-first-served and preempts the latest arrivals first. [Certain] Scheduling policies are the topic of session 136.

Prefix caching: reuse the cache of repeated prompts

So far, sharing happened inside one request. But many different requests start with the same tokens:

  • a system prompt of hundreds or thousands of tokens, the same for every user of a product;
  • few-shot examples placed before every question;
  • a long document, a code file or a video transcript that users ask several questions about;
  • multi-turn chat, where turn 3 resends turns 1 and 2;
  • agents, which resend the tool descriptions and the whole history at every step.

The KV entries of a token depend only on the token and on everything before it. So if two prompts agree on their first \(\ell\) tokens, the K and V of those \(\ell\) tokens are identical in both, and the second request can skip their prefill. Prefix caching keeps blocks of finished requests in memory and lets new requests point their block tables at them.

How vLLM finds a matching prefix: a chain of block hashes

Comparing a new prompt token by token against every cached prompt would be slow. vLLM gives every full block a hash and keeps a dictionary from hash to physical block. [Certain] The hash of block \(j\) covers its own tokens and the hash of the block before it:

\[ h_j = H\big(h_{j-1},\; x_{j\beta}, \dots, x_{(j+1)\beta - 1},\; e\big), \qquad h_{-1} = \text{salt} \tag{134.7} \]
Read the symbols
\(H\)
a hash function (the vLLM default is SHA-256 [Certain])
\(x_{j\beta}, \dots\)
the \(\beta\) token ids inside block \(j\)
\(h_{j-1}\)
the parent hash. Because it is included, \(h_j\) identifies the whole prefix up to the end of block \(j\), not only the block’s own tokens
\(e\)
extra keys that change the KV values: the LoRA adapter id, hashes of images in the block, and so on
salt
an optional per-tenant value, so that different users cannot share (or probe) each other’s cached blocks

For a new prompt, the scheduler computes \(h_0, h_1, \dots\) and looks them up one by one until the first miss. Every hit is a block it can reuse: increase its reference count and put it in the block table. Only the tokens after the last hit go through prefill. With a shared prefix of \(\ell\) tokens:

\[ r = \beta \left\lfloor \frac{\ell}{\beta} \right\rfloor \text{ tokens reused}, \qquad \text{prefill FLOPs saved} \approx 2 N r \tag{134.8} \]

Here \(N\) is the number of model parameters (the \(2N\) FLOPs per token rule of session 78). The attention part of prefill, which grows with \(\ell^2\), is saved too. If every token of the prompt hits, the engine still recomputes the last token, because it needs that token’s logits to sample the first output token. [Likely]

hit: reused blockfirst missnew block, prefilled
Prefix-cache lookup for a new prompt \(p\)
  1. \(h \leftarrow \text{salt}\); \(m \leftarrow 0\); \(j \leftarrow 0\)
  2. while block \(j\) of \(p\) is full:
  3.   \(h \leftarrow H(h, x_{j\beta}, \dots, x_{(j+1)\beta-1}, e)\) // (134.7)
  4.   if \(h\) in table: \(b \leftarrow \text{table}[h]\); \(\text{ref}[b] \mathrel{+}= 1\); \(\text{BT}[j] \leftarrow b\); \(m \mathrel{+}= \beta\); \(j \mathrel{+}= 1\)
  5.   else: break // the first miss ends the match
  6. take \(\lceil (|p| - m)/\beta \rceil\) fresh blocks; prefill tokens \(m, \dots, |p|-1\)
  7. add the hashes of the new full blocks to the table
Figure 4. Prompt A (48 tokens) is already in the cache: it has finished, and its blocks wait in the free queue with reference count 0, still holding their data and hashes. Prompt B (52 tokens) is A with one token changed at position \(\ell\), plus 4 new tokens at the end. The animation runs the lookup for B: it computes the chained hash (134.7) of one block at a time (first 4 hex digits shown) and looks it up. Under each block of A is its physical block; under B is B’s block table as it is filled.
How to read Figure 4

Press Play. Each step hashes one block of B with its parent hash and looks it up. A hit draws an arrow to the cached block of A and copies its physical block number into B’s block table (green). The first block that contains the changed token (red outline) misses, and the loop stops. Then B takes fresh blocks for everything after the match (blue) and prefills only those tokens. Notice that the blocks after the miss are never looked up: even if their own tokens are identical to A’s, their keys and values depend on the changed token through attention, so their chained hashes are different anyway. The last step shows them: blue, new hashes. Move \(\ell\) to 48 (no token changed): B reuses all 48 tokens of A and prefills only its 4 new tokens. Larger blocks lose more of the shared prefix to rounding.

Worked example: a shared system prompt

A product sends a 1,000-token system prompt before a 50-token user message. With \(\beta = 16\), the first \(\lfloor 1000/16 \rfloor = 62\) blocks are full and identical across users: \(r = 992\) tokens are reused, and only \(8 + 50 = 58\) tokens are prefilled. That removes 94.5% of the prefill tokens. For Llama 3 8B (8.03B parameters), formula (134.8) gives \(2 \times 8.03 \times 10^9 \times 992 = 1.59 \times 10^{13}\) FLOPs saved per request, and the 62 blocks are stored once for all users.

Eviction: an LRU list of unused blocks

A cached block that no running request uses has reference count 0. vLLM does not free it right away. It goes to the tail of a free queue, still holding its data and its hash. [Certain] When the engine needs a new block, it pops the head of the queue: the least recently used block. If that block still has a hash, the hash is removed from the dictionary first (the cached prefix is evicted). If a new request hits a block that sits in the free queue, the block is taken out of the queue and reused. [Certain] So the cache uses all memory that running requests do not need, at no cost.

One detail: when a request finishes, its blocks enter the queue in reverse order, so the last block of the request is evicted first. The last block covers the longest prefix and is the least likely to be shared. [Certain]

RadixAttention: a tree of every cached sequence

SGLang takes the same goal further. It treats the KV cache of all requests, running and finished, as one data structure: a radix tree. [Certain]

  • A radix tree (also called a compressed trie) stores many sequences by their shared prefixes. Each edge is labeled with a run of tokens, not one token. Two sequences share the path for their common prefix and split into two branches where they first differ.
  • Each node points to the KV cache of the tokens on its edge. Pages are one token, so a split can happen anywhere. [Certain]
  • Each node has a reference counter: how many running requests use it. A node with counter 0 can be evicted. [Certain]
  • Eviction is LRU on leaves: when memory is needed, remove the least recently used leaf, and repeat. Removing a leaf may make its parent a leaf. [Certain] There is no separate, fixed-size cache pool: all memory not used by running requests is cache. [Certain]

For a new request, SGLang walks down the tree as far as the prompt matches, reuses all those tokens, prefills the rest, and inserts the new tokens as a new branch. When the request ends, its generated tokens stay in the tree too. That is what makes multi-turn chat cheap: turn 2 finds turn 1’s prompt and answer in the tree.

The difference from block hashes: the hash chain can only match whole blocks and only along one chain per prompt, while the tree matches to the exact token and naturally stores many branches (a few-shot header, then several documents, then many questions per document). vLLM’s hash table and SGLang’s tree are two ways to answer the same query, “what is the longest cached prefix of this prompt?”.

Cache-aware scheduling: longest prefix first

With a small cache, the order of requests matters. If requests that share a prefix are spread out in time, the prefix is evicted between them and must be computed again. SGLang sorts waiting requests by the length of their matched prefix and runs the longest match first. [Certain] The paper proves that, for a batch of requests known in advance and a cache at least as large as the longest request, visiting the tree in depth-first order gives the best possible hit rate, and that longest-shared-prefix-first is equivalent to depth-first order. [Certain] The paper also warns that this greedy order can starve requests with no shared prefix, which a real server must guard against. [Certain]

We measure the result with the cache hit rate:

\[ \text{hit rate} = \frac{\sum_i m_i}{\sum_i P_i} \tag{134.9} \]
Read the symbols
\(m_i\)
prompt tokens of request \(i\) found in the cache (the length of the matched path)
\(P_i\)
prompt tokens of request \(i\)

On its benchmarks, SGLang reports hit rates from 50% to 99%, and its cache-aware scheduler reaching 96% of the optimal hit rate on average. When there is nothing to reuse, managing the tree cost less than 0.3% of the run time. [Certain]

matched and locked by this requestnew tokens inserted by this requestLRU leaf being evictedcached, not used now
RadixAttention, one request (Algorithm 2, short form)
  1. scheduler: pick the next request (first come, or longest MATCH)
  2. \((m, \text{path}) \leftarrow\) MATCH(\(p\)) // split an edge if the match ends inside it
  3. \(u.\text{ref} \mathrel{+}= 1\) for \(u\) in path // lock
  4. need \(\leftarrow |p| - m + |y|\)
  5. while size + need \(\gt C\): evict the unlocked leaf with the smallest \(t\)
  6. prefill \(p_m, \dots\), decode \(y\); insert the new tokens as a leaf
  7. \(u.t \leftarrow\) now on the path; \(u.\text{ref} \mathrel{-}= 1\) // unlock
Figure 5. RadixAttention on 8 requests for a video assistant: a 6-token system prompt (SYS…), two 4-token video clips (clipA, clipB), several questions per clip, and one second chat turn (request 6 continues request 1 with its answer). Each node shows its first tokens, its length and \(t\), the step when it was last used. Every request runs in phases: MATCH and lock, one frame per eviction (the victim leaf turns red before it is removed), then prefill and insert. After each request, its prompt and answer stay in the tree.
How to read Figure 5

Step through the first requests at capacity 24 with first-come-first-served. Request 1 fills the empty tree (15 tokens with its answer). Request 2 matches the 6 system-prompt tokens: the edge is split there, and the panel shows need \(= 12 - 6 + 1 = 7\) and the size test \(15 + 7 \le 24\). At request 3 the tree holds 22 tokens and needs 5 more (\(22 + 5 = 27 \gt 24\)), so the least recently used unlocked leaf (\(t = 1\)) is evicted: the question and answer of request 1, 5 tokens. But the clipA path that request 3 has just matched is locked and stays. Then play through both schedules at capacity 24. With first-come-first-served, clipA and clipB requests alternate, so each clip’s branch is evicted before it is needed again: the final hit rate is 54 of 101 prompt tokens (53.5%). With longest-prefix-first, the requests on clipA run together, then those on clipB: 69 of 101 (68.3%), the best possible here. Raise the capacity to 44 and both orders reach 69, because nothing is evicted. Lower it to 19 (the longest request) and first-come-first-served falls to 46 while longest-prefix-first still gets 69.

Algorithm 2: RadixAttention, one request
  1. state: radix tree with root \(\rho\); each node \(u\) has a token run \(u.\text{tok}\), KV indices, a reference counter \(u.\text{ref}\) and a last-access time \(u.\text{t}\)
  2. function MATCH(prompt \(p\)): walk from \(\rho\), following the child whose run starts with the next token; compare token by token; if the match ends inside an edge, split that node in two; return matched length \(m\) and the path
  3. function SERVE(request with prompt \(p\)):
  4.   \((m, \text{path}) \leftarrow\) MATCH(\(p\)); \(u.\text{ref} \mathrel{+}= 1\) for \(u\) in path // lock: these cannot be evicted now
  5.   need \(\leftarrow |p| - m\) plus room for the output
  6.   while free memory \(\lt\) need: evict the leaf with \(\text{ref} = 0\) and the smallest \(\text{t}\) // LRU on leaves
  7.   prefill tokens \(p_{m}, \dots, p_{|p|-1}\) using the cached KV of \(p_0, \dots, p_{m-1}\); decode the output \(y\)
  8.   insert \(p \Vert y\) into the tree (a new leaf under the last matched node); set \(u.\text{t} \leftarrow\) now on the whole path
  9.   \(u.\text{ref} \mathrel{-}= 1\) for \(u\) in path // unlock; the tokens stay cached
  10. scheduler: among waiting requests, pick the one with the longest MATCH first (cache-aware), with a guard against starvation

A complete example in PyTorch

The code builds a tiny paged KV cache: a pool of blocks, a free list, reference counts, block tables, APPEND with copy-on-write and FORK from Algorithm 1. It reproduces Figure 3, checks that attention read through the block tables equals ordinary attention on contiguous tensors, and computes chained block hashes as in Figure 4. It runs on a CPU in under a second.

import hashlib, math, torch
torch.manual_seed(0)

H, D, BLOCK, NUM_BLOCKS = 2, 8, 4, 32            # kv heads, head dim, tokens per block, pool size
k_pool = torch.zeros(NUM_BLOCKS, BLOCK, H, D)    # physical KV memory, shared by all sequences
v_pool = torch.zeros(NUM_BLOCKS, BLOCK, H, D)
free = list(range(NUM_BLOCKS - 1, -1, -1))       # free block ids (pop from the end)
ref = [0] * NUM_BLOCKS                           # reference count per physical block

class Seq:
    def __init__(self): self.table, self.n = [], 0   # block table and number of tokens

def alloc():
    b = free.pop(); ref[b] = 1; return b

def release(b):
    ref[b] -= 1
    if ref[b] == 0: free.append(b)

def append(seq, k, v):                           # write the KV of one new token
    j, o = divmod(seq.n, BLOCK)                  # logical block, offset (formula 134.3)
    if j == len(seq.table):                      # last block full: get a new one
        seq.table.append(alloc())
    elif ref[seq.table[j]] > 1:                  # shared block: copy-on-write
        old, new = seq.table[j], alloc()
        k_pool[new], v_pool[new] = k_pool[old], v_pool[old]
        release(old); seq.table[j] = new
    b = seq.table[j]
    k_pool[b, o], v_pool[b, o] = k, v
    seq.n += 1

def fork(seq):                                   # parallel sampling: share every block
    child = Seq(); child.table, child.n = list(seq.table), seq.n
    for b in seq.table: ref[b] += 1
    return child

def paged_attention(q, seq):                     # q: (H, D); reads K and V through the block table
    idx = torch.tensor(seq.table)
    K = k_pool[idx].reshape(-1, H, D)[: seq.n]   # gather blocks, drop the empty tail
    V = v_pool[idx].reshape(-1, H, D)[: seq.n]
    w = torch.softmax(torch.einsum("hd,thd->ht", q, K) / math.sqrt(D), dim=-1)
    return torch.einsum("ht,thd->hd", w, V)

# 1) a 10-token prompt, then 3 samples that share it
ks, vs = torch.randn(13, 3, H, D), torch.randn(13, 3, H, D)
parent = Seq()
for t in range(10): append(parent, ks[t, 0], vs[t, 0])
samples = [parent, fork(parent), fork(parent)]
print("after fork  :", [s.table for s in samples], "refs", ref[:3])
for t in range(10, 13):
    for i, s in enumerate(samples): append(s, ks[t, i], vs[t, i])
print("after 3 more:", [s.table for s in samples])
print("blocks in use:", NUM_BLOCKS - len(free), "without sharing:", 3 * math.ceil(13 / BLOCK))

# 2) paged attention equals ordinary attention on a contiguous copy
q = torch.randn(H, D)
for i, s in enumerate(samples):
    Kc = torch.cat([ks[:10, 0], ks[10:, i]]); Vc = torch.cat([vs[:10, 0], vs[10:, i]])
    ref_out = torch.einsum("ht,thd->hd", torch.softmax(torch.einsum("hd,thd->ht", q, Kc) / math.sqrt(D), -1), Vc)
    print("sample", i, "max diff:", (paged_attention(q, s) - ref_out).abs().max().item())

# 3) prefix caching: chained hashes of full blocks (formula 134.7)
def block_hashes(tokens, extra=""):
    h, out = extra, []
    for j in range(len(tokens) // BLOCK):        # only full blocks get a hash
        h = hashlib.sha256((h + str(tokens[j*BLOCK:(j+1)*BLOCK])).encode()).hexdigest()[:8]
        out.append(h)
    return out
a = list(range(100, 118))                        # 18 tokens
b = a[:9] + [999] + a[10:]                       # one token changed at position 9
ha, hb = block_hashes(a), block_hashes(b)
print(ha); print(hb)
hit = 0
while hit < min(len(ha), len(hb)) and ha[hit] == hb[hit]: hit += 1
print("reusable blocks:", hit, "-> reuse", hit * BLOCK, "tokens, recompute", len(b) - hit * BLOCK)

Output (PyTorch 2.x, CPU):

after fork  : [[0, 1, 2], [0, 1, 2], [0, 1, 2]] refs [3, 3, 3]
after 3 more: [[0, 1, 3, 5], [0, 1, 4, 6], [0, 1, 2, 7]]
blocks in use: 8 without sharing: 12
sample 0 max diff: 0.0
sample 1 max diff: 0.0
sample 2 max diff: 0.0
['947bbe4f', 'a4bb0caf', '2915ba54', 'b9328771']
['947bbe4f', 'a4bb0caf', 'bcc4e3b1', '36b6f47b']
reusable blocks: 2 -> reuse 8 tokens, recompute 10

Read the output. Sample 0 writes first into shared block 2 and gets a copy (block 3); sample 1 gets block 4; sample 2 is the last user and writes into block 2 in place. Blocks 0 and 1 stay shared. In part 3, blocks 2 and 3 of b have new hashes, although block 3 has exactly the same tokens as in a: the chain carries the change forward. A real engine does the gather inside the attention kernel instead of building K and V in memory.

Where this is used

SettingWhat is shared or reusedMechanism
Any LLM server under loadnothing shared; just no wastePaged blocks; the default in vLLM, SGLang, TensorRT-LLM and others [Likely]
Chat products with a fixed system promptthe system prompt across all usersPrefix caching (hash chain) or RadixAttention
Multi-turn chat and agentsearlier turns, tool descriptions, the whole historyPrefix caching; RadixAttention also keeps generated answers in the tree
Best-of-n, self-consistency, RL rollouts (GRPO needs many answers per prompt)the prompt across \(n\) samplesFork with reference counts and copy-on-write
Beam search, tree search, speculative decoding treesprompt plus common generated prefixesShared blocks; tree attention masks (SpecInfer)
RAG and long-document question answeringa popular document placed first in the prompt, asked about many timesPrefix caching, if the document comes before the question and its text is byte-identical [Likely]
Video question answering and Video-RAGthe visual tokens of one video (often thousands of tokens) across many questions about itPrefix caching keyed by the video’s hash as an extra key \(e\) in (134.7) (session 210)
Batch jobs: classify or tag thousands of clips or documents with one long instructionthe instruction and few-shot examplesRadixAttention with longest-prefix-first ordering
Hosted LLM APIslong prompt prefixes sent repeatedly by one customerPrompt caching, often billed at a lower price for cached input tokens [Likely]

Common mistakes

  • Putting the changing part first. A timestamp, a user name or a request id at the top of the system prompt changes block 0, so the hash chain misses everything after it. Put fixed content first, variable content last.
  • Assuming “same text” means “same tokens”. A different chat template, an extra space, or a different tokenizer version gives different token ids, and nothing is shared. Prefix caching works on token ids, not on strings.
  • Expecting a prefix of 15 tokens to be cached with \(\beta = 16\). Hash-based prefix caching shares only full blocks (formula 134.8). Short prefixes give nothing.
  • Forgetting that the cache depends on more than tokens. A different LoRA adapter, different images, or a different model version produce different K and V for the same tokens. They must be part of the key (the \(e\) in formula 134.7).
  • Sharing across tenants without thinking about privacy. A cache hit makes the first token come back faster, and that timing can reveal that someone else sent the same prefix. Use a per-tenant salt where this matters.
  • Writing into a shared block. Any custom kernel or cache update must respect reference counts; writing in place into a block with count above 1 silently corrupts another sequence.
  • Counting cache memory by tokens of one layer. One block covers \(\beta\) tokens in every layer, so its size is \(\beta \cdot s\), with \(s\) the bytes per token for the whole model (128 KiB for Llama 3 8B, so 2 MiB per 16-token block).
  • Ignoring starvation with longest-prefix-first. Requests with no shared prefix can wait forever behind a stream of cache hits. Real schedulers mix in a fairness rule.

Interview questions

What problem does PagedAttention solve, and how?basic
Contiguous per-request KV allocation must reserve the maximum length up front, which wastes memory three ways: reserved slots for future tokens, internal fragmentation (answers end early), and external fragmentation (holes between reservations). The vLLM paper measured only 20.4–38.2% useful memory in earlier systems. PagedAttention cuts the cache into fixed-size blocks (16 tokens by default), allocates them on demand, and keeps a block table per sequence that maps logical blocks to physical blocks anywhere in memory. Waste falls to less than one block per sequence, so many more requests fit in a batch, which gave 2–4× higher throughput.
What is in a block table, and how does the kernel find token \(t\)?basic
One entry per logical block: the physical block number (and, in the paper, the number of filled slots). For token \(t\): logical block \(j = \lfloor t/\beta \rfloor\), offset \(o = t \bmod \beta\), physical slot \(\text{BT}[j]\cdot\beta + o\). The kernel receives the block table and the sequence length, loads each block’s keys and values through this mapping, and masks the unused slots of the last block.
How does copy-on-write work for parallel sampling?core
The prompt is prefilled once; FORK creates \(n\) block tables that point to the same blocks and raises each block’s reference count to \(n\). Full blocks are never written again, so they stay shared. When a sample wants to write into a block whose count is above 1 (the partly filled last prompt block), the engine copies the block, points that sample’s table at the copy, and decrements the original’s count. The last sample finds count 1 and writes in place. Only the full prompt blocks, \(\lfloor P/\beta \rfloor\), are stored once, formula (134.6).
Why is the block size a trade-off? What would you pick?core
Small blocks: less waste in the last block, finer sharing (more of a prefix is in full blocks), but more table entries and smaller, less efficient memory reads in the kernel. Large blocks: efficient reads, short tables, but more waste and coarser prefix sharing. The vLLM paper found 16 to 128 best on ShareGPT traces and saw large blocks hurt on short Alpaca sequences; 16 is the common default. SGLang uses one-token pages in its radix tree, so matching is exact.
How does vLLM detect that a new prompt shares a prefix with cached data?core
Every full block gets a hash of (parent block hash, the block’s token ids, extra keys such as the LoRA id and image hashes). Because the parent hash is included, a block hash identifies the entire prefix up to that block. A dictionary maps hashes to physical blocks. For a new prompt the scheduler computes the hash chain and looks up blocks in order until the first miss; all hits are reused by raising their reference counts. Only full blocks are cached, so the reusable length is \(\beta\lfloor \ell/\beta\rfloor\).
Why does the hash of block \(j\) include the hash of block \(j-1\)? Isn’t hashing the block’s own tokens enough?core
No. The keys and values of a token depend on all earlier tokens (through attention in every layer below the top). Two blocks with identical tokens but different histories have different K and V. Including the parent hash makes the key represent the full prefix, so a hit guarantees that the cached KV is exactly what the model would compute. One changed token therefore invalidates every block after it.
What happens when a GPU runs out of free blocks in the middle of decoding?core
The engine preempts one or more running sequences, all-or-nothing, since a sequence needs all of its tokens to continue. It either swaps their blocks to CPU memory (costs PCIe transfers) or drops them and recomputes later by prefilling prompt plus generated tokens (costs compute, often cheaper for short sequences). vLLM schedules first-come-first-served and preempts the most recent requests first. Before that, it evicts cached blocks with reference count 0 from the free queue.
Prefix caching with block hashes vs RadixAttention: what is the difference?advanced
Both answer “what is the longest cached prefix of this prompt?” and both evict least-recently-used unused data. vLLM uses a flat hash table over full blocks plus an LRU free queue; it matches at block granularity and only along one chain. SGLang keeps one radix tree over all running and finished sequences with one-token pages: it matches to the exact token, splits nodes where sequences diverge, stores generated answers in the tree (multi-turn reuse), counts references per node, evicts LRU leaves, and lets the scheduler use the tree to run requests with long matches first. The tree also helps the frontend place forks of a program correctly.
Why does longest-prefix-first scheduling raise the hit rate? What is the danger?advanced
With a limited cache, a shared prefix may be evicted between two requests that need it. Running requests with the longest matches first groups requests on the same branch, which is a depth-first walk of the radix tree; for an offline batch and a cache at least as large as the longest request, the SGLang paper proves that depth-first order maximizes the hit rate. In Figure 5 at capacity 24 it raises the hit rate from 53.5% to 68.3%. The danger is starvation and unfairness: requests with no match can wait indefinitely, so production schedulers add priorities, aging or limits.
Size it: Llama 3 8B, 60 GiB free for the cache, average 600 tokens per request, \(\beta = 16\). How many requests fit, paged vs contiguous with 8k reservations?core
Per token: \(2 \cdot 32 \cdot 8 \cdot 128 \cdot 2 = 131{,}072\) bytes. Tokens: \(60 \cdot 2^{30} / 131{,}072 = 491{,}520\). Contiguous with 8,192-token reservations: 60 requests. Paged: 38 blocks = 608 slots per request, 808 requests (13.5×). In practice compute limits and growth headroom reduce the gain, but memory is no longer the first limit.
Your prefix-cache hit rate is near zero although all requests use the same system prompt. What do you check?advanced
(1) Is something variable placed before or inside the system prompt (date, user id, request id, shuffled tool list)? It changes an early block and breaks the chain. (2) Are the token ids really identical (same chat template, same whitespace, same tokenizer version)? (3) Is the shared part at least one full block? (4) Different LoRA adapters, cache salts or images change the extra keys. (5) Is prefix caching enabled, and is the cache large enough, or are blocks evicted between requests by memory pressure? (6) With many replicas, does the router send requests with the same prefix to the same replica? Each GPU has its own cache, so prefix-aware routing matters.

Exercises

  1. Four requests hold 37, 100, 260 and 513 tokens. With \(\beta = 16\), how many blocks does each use, and what is \(\eta_{\text{paged}}\)? With contiguous reservations of 1,024 tokens each, what is \(\eta_{\text{contig}}\)?
  2. With \(\beta = 16\) and a block table [12, 3, 40, 7], where is token 50 stored (physical slot)?
  3. Parallel sampling with \(P = 4{,}000\), \(G = 100\), \(n = 8\), \(\beta = 16\). Blocks with and without sharing? Saving in percent?
  4. A system prompt has 1,500 tokens, and the user message 80. How many tokens are prefilled with prefix caching at \(\beta = 16\)? At \(\beta = 128\)?
  5. In Figure 5, set capacity 30. Read the final hit rate for both schedules. Why is first-come-first-served lower?
  6. Llama 3 70B has 80 layers, 8 KV heads and head dimension 128. What is the size of one 16-token block in BF16?
Answerscheck
1. Blocks: 3, 7, 17, 33 = 60 blocks = 960 slots for 910 tokens, so \(\eta_{\text{paged}} = 94.8\%\). Contiguous: \(910 / 4{,}096 = 22.2\%\). 2. \(j = \lfloor 50/16 \rfloor = 3\), \(o = 2\), so physical block 7, slot \(7 \times 16 + 2 = 114\). 3. Without: \(8 \times \lceil 4100/16 \rceil = 8 \times 257 = 2{,}056\). With: \(\lfloor 4000/16 \rfloor = 250\) shared, plus \(8 \times (257 - 250) = 56\), total 306. Saving \(1 - 306/2056 = 85.1\%\). 4. At 16: \(\lfloor 1500/16 \rfloor = 93\) blocks = 1,488 tokens reused, so \(12 + 80 = 92\) prefilled. At 128: \(11\) blocks = 1,408 reused, so \(92 + 80 = 172\) prefilled. 5. First-come-first-served 62/101 = 61.4%, longest-prefix-first 69/101 = 68.3%. In arrival order, clipA and clipB requests alternate and the system prompt subtree is shared, so the less recently used clip branch is evicted just before it is needed. 6. \(2 \times 80 \times 8 \times 128 \times 2 = 327{,}680\) bytes = 320 KiB per token, so 5 MiB per block.

Key takeaways

  • Contiguous KV reservations waste memory three ways (reserved slots, internal and external fragmentation); earlier systems used only 20–38% of it for real tokens (134.1).
  • PagedAttention cuts the cache into blocks of \(\beta\) tokens (16 by default) with a block table per sequence; waste is less than one block per sequence (134.2), and kernels translate addresses with (134.3) and attend block by block (134.4).
  • Reference counts let many block tables share blocks; copy-on-write copies a shared block only when someone writes into it. Parallel sampling stores the full prompt blocks once (134.6); beam search saves even more.
  • Prefix caching hashes each full block together with its parent hash (134.7), so a hit means the whole prefix matches; only full blocks are reused (134.8), and unused cached blocks live in an LRU free queue.
  • RadixAttention keeps all cached sequences, including answers, in a radix tree with one-token pages, reference counters and LRU leaf eviction; longest-prefix-first scheduling raises the hit rate (134.9).
  • Design prompts for caching: fixed content first, variable content last, identical tokens, same adapter.

Key formulas

\[ n_i = \left\lceil \tfrac{T_i}{\beta} \right\rceil, \quad \text{slot}(t) = \text{BT}\!\left[\lfloor t/\beta \rfloor\right]\beta + (t \bmod \beta), \quad h_j = H(h_{j-1}, x_{j\beta:(j+1)\beta}, e), \quad r = \beta \left\lfloor \tfrac{\ell}{\beta} \right\rfloor \]

References for this session

  1. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  2. Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
  3. Miao et al. (2023). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification
  4. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  5. Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
  6. Miao et al. (2023). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification
  7. vLLM project (docs). vLLM documentation
  8. Ye et al. (2025). FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving
  9. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  10. vLLM project (docs). vLLM design document: Automatic Prefix Caching