Definition
PagedAttention is an attention algorithm and memory manager for LLM serving that splits each sequence's key-value cache into fixed-size blocks (default 16 tokens), stores them anywhere in a shared GPU pool, and finds them through a per-sequence block table, as an operating system maps virtual pages to physical frames. It was introduced with vLLM by Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang and Stoica in "Efficient Memory Management for Large Language Model Serving with PagedAttention" (SOSP 2023).
A server's throughput depends on how many sequences decode together, and the batch is limited by KV cache memory. That article covers what the cache holds and what it costs. Here the question is allocation. Before 2023, engines stored each request's cache in one contiguous tensor. Because the final length is unknown at admission, they reserved the maximum length. For OPT-13B, at 800 KiB per token, a 2,048-token reservation is 1.56 GiB, even if the answer ends after 300 tokens.
The paper names three kinds of waste: slots reserved for tokens not yet generated, slots inside a reservation that are never used (internal fragmentation), and gaps between reservations of different sizes (external fragmentation). In the systems it measured, only 20.4–38.2% of KV memory held actual token states.
Blocks, tables and the kernel
- block size in tokens (vLLM: 16 by default on GPUs)
- the sequence's block table: logical block → physical block id
- tokens currently in the sequence; a new block is taken only when the last one fills
The attention kernel no longer assumes adjacent keys. For the query of the newest token, it walks the block table and processes one block of keys and values at a time:
- the keys and values of logical block , fetched from physical block
- row vector of attention weights of over the tokens of block
- attention output; the softmax denominator is accumulated across blocks with a running maximum, as in FlashAttention
Sharing and copy-on-write
Each physical block has a reference count. Parallel sampling (n completions of one prompt) forks a sequence by copying its block table and incrementing the counts, without copying any data. Before a sequence writes into a block whose count is above 1, the engine allocates a new block, copies the contents and decrements the old count. Only the last, partly filled prompt block is ever copied. Beam search uses the same mechanism: beams that share a history share its blocks, and a block is freed when its count reaches 0.
- prompt tokens; its full blocks are stored once
- tokens generated so far by sample s
The same tables make prefix caching possible. A block can stay in the pool after its request ends, indexed by a hash of all tokens up to and including it, and a new request with the same system prompt maps those blocks instead of recomputing them (vLLM's automatic prefix caching; SGLang's RadixAttention keeps a radix tree of prefixes). The API-level view is in Prompt caching.
When the pool runs out
Paged allocation admits requests without reserving their future tokens, so running sequences can outgrow the pool. vLLM then preempts whole sequences (all samples of a request together), newest first under its first-come-first-served policy. It either swaps their blocks to CPU memory or frees them and later recomputes the cache from prompt plus generated tokens with one prefill pass. The paper found recomputation cheaper at small block sizes, where swapping moves many small blocks over PCIe.
From the paper and the vLLM launch
- Memory use
- 20.4–38.2% of KV memory held token states in the contiguous systems measured; waste under 4% with PagedAttention
- Throughput
- 2–4× FasterTransformer and Orca at the same latency, with larger gains for longer sequences, larger models and parallel sampling or beam search
- Kernel cost
- the paged attention kernel was 20–26% slower than FasterTransformer's contiguous one, because of table lookups and variable lengths; attention is a small part of end-to-end time, so the larger batch wins
- Sharing
- the June 2023 launch post reported up to 55% less memory for parallel sampling and beam search, and up to 2.2× throughput
- Block size
- 16 by default: large enough to use the GPU's memory transactions well, small enough to keep internal fragmentation low
The block size is a trade-off. Smaller blocks waste less (99.5% use at block 4 in the figure) but mean longer block tables and smaller, less efficient memory reads in the kernel. Larger blocks waste up to slots per sequence, and with prompt sharing they also share less, because only full prompt blocks are shared.
Worked example: one OPT-13B request
| Allocator | Slots held | Empty slots | Empty memory |
|---|---|---|---|
| Contiguous, reserve max length | 2,048 | 2,048 − 300 = 1,748 | 1,748 · 800 KiB = 1.33 GiB |
| Paged, b = 16 | ⌈300/16⌉ = 19 blocks = 304 | 304 − 300 = 4 | 4 · 800 KiB = 3.13 MiB |
The diagram's two samples work the same way. Each needs blocks, 6 in all. With sharing, prompt block is stored once, giving blocks.
1class BlockManager:2 """Paged KV-cache bookkeeping: a free list, per-sequence block tables, reference counts."""34 def __init__(self, num_blocks, block_size):5 self.bs = block_size6 self.free = list(range(num_blocks))[::-1]7 self.ref = [0] * num_blocks89 def _alloc(self):10 blk = self.free.pop()11 self.ref[blk] = 112 return blk1314 def new_seq(self, n_tokens): # prefill: ceil(n / bs) blocks15 return {"table": [self._alloc() for _ in range(-(-n_tokens // self.bs))], "len": n_tokens}1617 def fork(self, seq): # parallel sample: share every block18 for blk in seq["table"]:19 self.ref[blk] += 120 return {"table": list(seq["table"]), "len": seq["len"]}2122 def append(self, seq): # make room for one new token23 t, i = seq["table"], seq["len"]24 seq["len"] += 125 if i % self.bs == 0: # last block full: take a fresh one26 t.append(self._alloc())27 elif self.ref[t[-1]] > 1: # partial block still shared: copy-on-write28 self.ref[t[-1]] -= 129 src, t[-1] = t[-1], self._alloc()30 print(f"copy block {src} -> {t[-1]}") # the engine copies this block's K and V3132bm = BlockManager(num_blocks=8, block_size=4)33s1 = bm.new_seq(6) # "The quick brown fox jumps over"34s2 = bm.fork(s1)35for _ in range(3): bm.append(s1) # "the lazy dog" -> copy block 1 -> 236for _ in range(4): bm.append(s2) # "a sleeping cat today"37print(s1["table"], s2["table"]) # [0, 2, 3] [0, 1, 4]38print("refs", bm.ref[:5], "blocks used", 8 - len(bm.free)) # refs [2, 1, 1, 1, 1] blocks used 5Check yourself
With block size 16, what is the most memory a single sequence can waste to internal fragmentation?
Check yourself
Four samples are drawn from a 100-token prompt with block size 16. How many prompt blocks are stored once and shared by all four?
Remember
- ✓KV cache in fixed blocks (16 tokens by default) anywhere in a GPU pool, found through per-sequence block tables.
- ✓Waste is slots per sequence, against 20.4–38.2% of memory used in contiguous systems.
- ✓The kernel gathers blocks through the table and merges softmax across blocks; it was 20–26% slower than a contiguous kernel, but the larger batch more than pays for it.
- ✓Reference counts and copy-on-write let parallel samples and beams share prompt blocks; the same tables enable prefix caching.
- ✓Out of blocks: preempt whole sequences and swap to CPU or recompute later.