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.
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:
- 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]
- 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.
- 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:
- 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.
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
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:
- 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
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]:
- 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.
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:
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.
- 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\)
- function APPEND(\(s\), \(\mathbf{k}\), \(\mathbf{v}\)):
- \(j \leftarrow \lfloor n_s / \beta \rfloor\), \(o \leftarrow n_s \bmod \beta\) // formula (134.3)
- if \(j = |\text{BT}_s|\): // last block is full
- if \(F\) is empty: preempt a sequence (swap it out or drop it for recompute), then retry
- \(b \leftarrow F.\text{pop}()\); \(\text{ref}[b] \leftarrow 1\); append \(b\) to \(\text{BT}_s\)
- else if \(\text{ref}[\text{BT}_s[j]] \gt 1\): // block is shared: copy-on-write
- \(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\)
- write \(\mathbf{k}, \mathbf{v}\) into slot \(o\) of block \(\text{BT}_s[j]\) in every layer; \(n_s \leftarrow n_s + 1\)
- 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\)
- 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.
- APPEND(\(s\)): \(j \leftarrow \lfloor n_s/\beta \rfloor\), \(o \leftarrow n_s \bmod \beta\)
- if \(j = |\text{BT}_s|\): \(b \leftarrow F.\text{pop}()\); \(\text{ref}[b] \leftarrow 1\); append \(b\) to \(\text{BT}_s\)
- 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\)
- write \(\mathbf{k}, \mathbf{v}\) at slot \(\text{BT}_s[j]\,\beta + o\); \(n_s \leftarrow n_s + 1\)
- FORK(\(s\)): copy \(\text{BT}_s\); \(\text{ref}[b] \mathrel{+}= 1\) for each \(b\)
- FREE(\(s\)): \(\text{ref}[b] \mathrel{-}= 1\); if 0, push \(b\) to \(F\)
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:
Only the \(\lfloor P/\beta \rfloor\) full prompt blocks are stored once; everything after them belongs to one sample.
\(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:
- 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:
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]
- \(h \leftarrow \text{salt}\); \(m \leftarrow 0\); \(j \leftarrow 0\)
- while block \(j\) of \(p\) is full:
- \(h \leftarrow H(h, x_{j\beta}, \dots, x_{(j+1)\beta-1}, e)\) // (134.7)
- 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\)
- else: break // the first miss ends the match
- take \(\lceil (|p| - m)/\beta \rceil\) fresh blocks; prefill tokens \(m, \dots, |p|-1\)
- add the hashes of the new full blocks to the table
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.
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:
- 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]
- scheduler: pick the next request (first come, or longest MATCH)
- \((m, \text{path}) \leftarrow\) MATCH(\(p\)) // split an edge if the match ends inside it
- \(u.\text{ref} \mathrel{+}= 1\) for \(u\) in path // lock
- need \(\leftarrow |p| - m + |y|\)
- while size + need \(\gt C\): evict the unlocked leaf with the smallest \(t\)
- prefill \(p_m, \dots\), decode \(y\); insert the new tokens as a leaf
- \(u.t \leftarrow\) now on the path; \(u.\text{ref} \mathrel{-}= 1\) // unlock
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.
- 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}\)
- 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
- function SERVE(request with prompt \(p\)):
- \((m, \text{path}) \leftarrow\) MATCH(\(p\)); \(u.\text{ref} \mathrel{+}= 1\) for \(u\) in path // lock: these cannot be evicted now
- need \(\leftarrow |p| - m\) plus room for the output
- while free memory \(\lt\) need: evict the leaf with \(\text{ref} = 0\) and the smallest \(\text{t}\) // LRU on leaves
- prefill tokens \(p_{m}, \dots, p_{|p|-1}\) using the cached KV of \(p_0, \dots, p_{m-1}\); decode the output \(y\)
- 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
- \(u.\text{ref} \mathrel{-}= 1\) for \(u\) in path // unlock; the tokens stay cached
- 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
| Setting | What is shared or reused | Mechanism |
|---|---|---|
| Any LLM server under load | nothing shared; just no waste | Paged blocks; the default in vLLM, SGLang, TensorRT-LLM and others [Likely] |
| Chat products with a fixed system prompt | the system prompt across all users | Prefix caching (hash chain) or RadixAttention |
| Multi-turn chat and agents | earlier turns, tool descriptions, the whole history | Prefix 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\) samples | Fork with reference counts and copy-on-write |
| Beam search, tree search, speculative decoding trees | prompt plus common generated prefixes | Shared blocks; tree attention masks (SpecInfer) |
| RAG and long-document question answering | a popular document placed first in the prompt, asked about many times | Prefix caching, if the document comes before the question and its text is byte-identical [Likely] |
| Video question answering and Video-RAG | the visual tokens of one video (often thousands of tokens) across many questions about it | Prefix 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 instruction | the instruction and few-shot examples | RadixAttention with longest-prefix-first ordering |
| Hosted LLM APIs | long prompt prefixes sent repeatedly by one customer | Prompt 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
What is in a block table, and how does the kernel find token \(t\)?basic
How does copy-on-write work for parallel sampling?core
Why is the block size a trade-off? What would you pick?core
How does vLLM detect that a new prompt shares a prefix with cached data?core
Why does the hash of block \(j\) include the hash of block \(j-1\)? Isn’t hashing the block’s own tokens enough?core
What happens when a GPU runs out of free blocks in the middle of decoding?core
Prefix caching with block hashes vs RadixAttention: what is the difference?advanced
Why does longest-prefix-first scheduling raise the hit rate? What is the danger?advanced
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
Your prefix-cache hit rate is near zero although all requests use the same system prompt. What do you check?advanced
Exercises
- 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}}\)?
- With \(\beta = 16\) and a block table
[12, 3, 40, 7], where is token 50 stored (physical slot)? - Parallel sampling with \(P = 4{,}000\), \(G = 100\), \(n = 8\), \(\beta = 16\). Blocks with and without sharing? Saving in percent?
- 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\)?
- In Figure 5, set capacity 30. Read the final hit rate for both schedules. Why is first-come-first-served lower?
- 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
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
References for this session
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
- Miao et al. (2023). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
- Miao et al. (2023). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification
- vLLM project (docs). vLLM documentation
- Ye et al. (2025). FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- vLLM project (docs). vLLM design document: Automatic Prefix Caching