How does PagedAttention enable prefix sharing across requests and what data structure makes it cheap?

PagedAttention stores the **KV cache** in fixed-size blocks instead of one contiguous slab per request, like an operating system splits memory into pages. Each request carries a block table: a small array mapping its logical token positions to the physical block where that token's keys and values live. This indirection is the whole trick. Because a request never addresses physical memory directly, two requests can have block tables that point to the same physical block. When many requests begin with an identical prefix, such as a long shared system prompt, their prefix tokens land in identical blocks, so they all point at one copy. Nothing is duplicated. The prefix occupies one set of blocks referenced by every request that uses it. A reference count on each block records how many requests point at it, so a block is freed only once the last user is gone. When one request diverges, meaning it writes into a shared block, copy-on-write triggers. A fresh block is allocated, the new token is written there, and only that request's table is repointed. The others keep sharing the original. Detecting a shared prefix at admission is cheap because block contents are hashed and looked up.

**PagedAttention** breaks the KV cache into fixed-size physical blocks and gives each request a block table mapping logical token positions to those blocks. That indirection is what makes sharing possible. When requests share an identical prompt prefix, their block tables simply point at the same physical blocks. No bytes are copied. The prefix lives once and is referenced many times. A reference count per block tracks how many requests use it, so memory is freed only when the last user leaves. Divergence is handled by copy-on-write. The moment a request writes a token into a shared block, the engine allocates a fresh block. It writes the new token there and repoints only that one entry in the request's table. The rest of the prefix stays shared. Detection is cheap because blocks are content addressed. Each block gets a hash over its tokens chained with its parent block's hash. The engine keeps a hash table from block hash to physical block. On admission it hashes the incoming prefix block by block and looks each up. A hit reuses the cached block, so the prefill for that span is skipped. The payoff is large for shared system prompts and few-shot contexts.