# 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.

Source: https://www.mlfoundry.in/learn/pagedattention  
Section: Generative AI › Serving Generative Models  
Level: advanced · 7 min read · updated 2026-10-21

**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

$$
\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
$$

- $b$: block size in tokens (vLLM: 16 by default on GPUs)
- $T$: the sequence's block table: logical block → physical block id
- $n$: 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 $q_i$ of the newest token, it walks the block table and processes one block of keys and values at a time:

$$
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
$$

- $K_j,\ V_j$: the $b$ keys and values of logical block $j$, fetched from physical block $T[j]$
- $A_{ij}$: row vector of attention weights of $q_i$ over the tokens of block $j$
- $o_i$: attention output; the softmax denominator is accumulated across blocks with a running maximum, as in FlashAttention

> Figure: 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.

$$
\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)
$$

- $p$: prompt tokens; its full blocks are stored once
- $g_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

> Figure: 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-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

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.

| 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 $\lceil 9/4\rceil=\lceil10/4\rceil=3$ blocks, 6 in all. With sharing, $\lfloor 6/4\rfloor=1$ prompt block is stored once, giving $1+(3-1)+(3-1)=5$ blocks.

```python
class BlockManager:
    """Paged KV-cache bookkeeping: a free list, per-sequence block tables, reference counts."""

    def __init__(self, num_blocks, block_size):
        self.bs = block_size
        self.free = list(range(num_blocks))[::-1]
        self.ref = [0] * num_blocks

    def _alloc(self):
        blk = self.free.pop()
        self.ref[blk] = 1
        return blk

    def new_seq(self, n_tokens):                 # prefill: ceil(n / bs) blocks
        return {"table": [self._alloc() for _ in range(-(-n_tokens // self.bs))], "len": n_tokens}

    def fork(self, seq):                         # parallel sample: share every block
        for blk in seq["table"]:
            self.ref[blk] += 1
        return {"table": list(seq["table"]), "len": seq["len"]}

    def append(self, seq):                       # make room for one new token
        t, i = seq["table"], seq["len"]
        seq["len"] += 1
        if i % self.bs == 0:                     # last block full: take a fresh one
            t.append(self._alloc())
        elif self.ref[t[-1]] > 1:                # partial block still shared: copy-on-write
            self.ref[t[-1]] -= 1
            src, t[-1] = t[-1], self._alloc()
            print(f"copy block {src} -> {t[-1]}")  # the engine copies this block's K and V

bm = BlockManager(num_blocks=8, block_size=4)
s1 = bm.new_seq(6)                               # "The quick brown fox jumps over"
s2 = bm.fork(s1)
for _ in range(3): bm.append(s1)                 # "the lazy dog"     -> copy block 1 -> 2
for _ in range(4): bm.append(s2)                 # "a sleeping cat today"
print(s1["table"], s2["table"])                  # [0, 2, 3] [0, 1, 4]
print("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)

> **Admission without reservation can thrash:** Admitting on current length lets far more sequences in, but if they all grow at once the pool runs out and sequences are preempted, swapped or recomputed, which costs time and adds latency spikes. vLLM keeps a small free-block watermark at admission. Setting `gpu_memory_utilization` close to 1 or `max_num_seqs` very high makes preemption more likely, and engines log it. See **Inference servers (vLLM, TGI)**.

> **Indirection is the real idea:** Once attention reads keys through a table, many features become bookkeeping. Sharing a prompt is a refcount, a fork is a table copy, prefix caching is a hash lookup, and moving a cache between GPUs ships blocks. The 2–4× throughput comes from packing, but the block table is what later features such as prefix reuse and disaggregated prefill are built on. vAttention (Prabhu et al., 2024) gets contiguous virtual addresses with paged physical memory from CUDA's virtual-memory API instead, so it can use unmodified attention kernels.

**Question:** With block size 16, what is the most memory a single sequence can waste to internal fragmentation?

- A. 0 slots
- B. 15 slots
- C. 16 slots per layer per head, times the sequence length
- D. Half its reserved maximum length

**Answer:** B. 15 slots — Only the last block can be partly empty, and a new block is taken only when the previous one is full, so the waste is $16\lceil n/16\rceil-n\le15$ slots (per layer, as every layer uses the same table layout).

**Question:** 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?

- A. 0
- B. 6
- C. 7
- D. 24

**Answer:** B. 6 — $\lfloor100/16\rfloor=6$ full blocks hold tokens 0–95 and are shared with ref count 4. Block 6 holds tokens 96–99 and is partly empty. The first time a sample writes into it, it gets its own copy (copy-on-write), so that block is not shared for long.

**Key points**

- KV cache in fixed blocks (16 tokens by default) anywhere in a GPU pool, found through per-sequence block tables.
- Waste is $b\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
