PagedAttention

PagedAttention (Kwon et al., SOSP 2023) stores the KV cache in fixed-size blocks mapped by per-sequence block tables, like OS pages: waste falls below one block per sequence, samples share prompt blocks copy-on-write, and vLLM fits 2–4× more work.

7 min read794 wordsadvanced0 viewsupdated 2026-10-21

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

token i ↦ ( T[⌊i/b⌋], i mod b ),slots(n)=b⌈n/b⌉,waste=b⌈n/b⌉−n<b\text{token } i\ \mapsto\ \big(\,T[\lfloor i/b\rfloor],\ i \bmod b\,\big),\qquad \text{slots}(n)=b\left\lceil n/b\right\rceil,\qquad \text{waste}=b\left\lceil n/b\right\rceil-n<b
bb
block size in tokens (vLLM: 16 by default on GPUs)
TT
the sequence's block table: logical block → physical block id
nn
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 qiq_i of the newest token, it walks the block table and processes one block of keys and values at a time:

Aij=exp⁡ ⁣(qi⊤Kj/d)∑t=1⌈i/b⌉exp⁡ ⁣(qi⊤Kt1/d),oi=∑j=1⌈i/b⌉VjAij⊤A_{ij}=\frac{\exp\!\big(q_i^\top K_j/\sqrt d\big)}{\sum_{t=1}^{\lceil i/b\rceil}\exp\!\big(q_i^\top K_t\mathbf 1/\sqrt d\big)},\qquad o_i=\sum_{j=1}^{\lceil i/b\rceil}V_jA_{ij}^\top
Kj, VjK_j,\ V_j
the bb keys and values of logical block jj, fetched from physical block T[j]T[j]
AijA_{ij}
row vector of attention weights of qiq_i over the tokens of block jj
oio_i
attention output; the softmax denominator is accumulated across blocks with a running maximum, as in FlashAttention
prompt “The quick brown fox jumps over” · n = 2 samples · block size 4logical KV blocksblock tablephysical blocks (GPU pool)sample 1ThequickbrownfoxL00 → 7jumpsoverthelazyL11 → 3dogL22 → 5sample 2ThequickbrownfoxL00 → 7jumpsoverasleepingL11 → 1cattodayL22 → 2#0free#1jumpsoverasleepingref 1#2cattodayref 1#3jumpsoverthelazycopy#4free#5dogref 1#6free#7Thequickbrownfoxref 2copy-on-write: #1 held “jumps over” for both samples (ref 2). Sample 1 wrote “the”first, so the engine copied #1 to #3 for it and dropped #1 to ref 1; sample 2then writes into #1 in place. Block #7 is never written again and stays shared.memory: 19 token states in 5 blocks (20 slots); without sharing 6 blocks (24 slots)token i of a sequence lives at (table[⌊i/4⌋], i mod 4); only the last block is partly emptydecode step, sample 2: gather blocks 7, 1, 2 from the table; per block compute q·Kⱼᵀ/√d,merge with a running max and sum (online softmax), accumulate Σ softmax · Vⱼ
fig.Two samples of the prompt “The quick brown fox jumps over”, block size 4. Both block tables map logical block 0 to physical #7, which holds the first four prompt tokens once (ref count 2). Block #1 held “jumps over” for both; when sample 1 wrote “the”, the engine copied it to #3 and sample 2 kept writing into #1. Five physical blocks (20 slots) serve 19 token states; without sharing, six blocks would be needed.

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.

blocks(n samples)=⌊pb⌋+∑s=1n(⌈p+gsb⌉−⌊pb⌋)\text{blocks}(n\text{ samples})=\left\lfloor\tfrac{p}{b}\right\rfloor+\sum_{s=1}^{n}\left(\left\lceil\tfrac{p+g_s}{b}\right\rceil-\left\lfloor\tfrac{p}{b}\right\rfloor\right)
pp
prompt tokens; its full blocks are stored once
gsg_s
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
paged: blocks taken on demand from a free list, anywhere in the poolpool 4,096 slots (32 rows × 128) · 10 queued requests × 2 samples · block = 16 tokens0102420483072admitted (FCFS)7 of 10 requests · 14 sequencestoken states served3,662slots allocated3,776 of 4,096slots holding data3,662 (97.0%)allocated but empty114requests admitted at this b, ncontiguous4paged7paged + sharing10request 0 (prompt 224 tokens) block tables, logical → physicalsample 0: [47, 133, 244, 140, 99, 178, 8, …] 16 blockssample 1: [62, 51, 117, 45, 36, 169, 205, …] 20 blocksno sharing: every sample has its own copy of the prompt
allocator
fig.Ten queued requests (prompts of 30–299 tokens, each sample has generated 10–199 tokens) in a pool of 4,096 KV slots, admitted first come, first served. Defaults (block 16, n = 2): contiguous 512-slot reservations admit 4 requests (8 sequences), and only 51.3% of the pool holds data. Paging admits 7 (14 sequences); 3,776 slots are allocated and 97.0% hold data. With prompt sharing all 10 fit: 5,492 token states in 4,048 slots. At block 64 paging falls to 6 requests and 88.7% use. At n = 4, admissions are 2, 3 and 6.

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 b−1b-1 slots per sequence, and with prompt sharing they also share less, because only full prompt blocks are shared.

Worked example: one OPT-13B request

AllocatorSlots heldEmpty slotsEmpty memory
Contiguous, reserve max length2,0482,048 − 300 = 1,7481,748 · 800 KiB = 1.33 GiB
Paged, b = 16⌈300/16⌉ = 19 blocks = 304304 − 300 = 44 · 800 KiB = 3.13 MiB
OPT-13B (40 layers, d = 5,120, fp16): 2 · 40 · 5,120 · 2 bytes = 800 KiB per token. One request ends at n = 300 tokens; maximum length 2,048.

The diagram's two samples work the same way. Each needs ⌈9/4⌉=⌈10/4⌉=3\lceil 9/4\rceil=\lceil10/4\rceil=3 blocks, 6 in all. With sharing, ⌊6/4⌋=1\lfloor 6/4\rfloor=1 prompt block is stored once, giving 1+(3−1)+(3−1)=51+(3-1)+(3-1)=5 blocks.

python
1class BlockManager:
2 """Paged KV-cache bookkeeping: a free list, per-sequence block tables, reference counts."""
3
4 def __init__(self, num_blocks, block_size):
5 self.bs = block_size
6 self.free = list(range(num_blocks))[::-1]
7 self.ref = [0] * num_blocks
8
9 def _alloc(self):
10 blk = self.free.pop()
11 self.ref[blk] = 1
12 return blk
13
14 def new_seq(self, n_tokens): # prefill: ceil(n / bs) blocks
15 return {"table": [self._alloc() for _ in range(-(-n_tokens // self.bs))], "len": n_tokens}
16
17 def fork(self, seq): # parallel sample: share every block
18 for blk in seq["table"]:
19 self.ref[blk] += 1
20 return {"table": list(seq["table"]), "len": seq["len"]}
21
22 def append(self, seq): # make room for one new token
23 t, i = seq["table"], seq["len"]
24 seq["len"] += 1
25 if i % self.bs == 0: # last block full: take a fresh one
26 t.append(self._alloc())
27 elif self.ref[t[-1]] > 1: # partial block still shared: copy-on-write
28 self.ref[t[-1]] -= 1
29 src, t[-1] = t[-1], self._alloc()
30 print(f"copy block {src} -> {t[-1]}") # the engine copies this block's K and V
31
32bm = 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 -> 2
36for _ 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 5
Block-table bookkeeping with reference counts and copy-on-write, replaying the diagram (runs as is; prints the copy and the final tables)

Check 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 b⌈n/b⌉−n<bb\lceil n/b\rceil-n<b 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.
← back to Generative AI roadmap