Paged attention and KV-cache kernels
Storing the transformer key-value cache in fixed-size non-contiguous blocks, with attention kernels that gather through a block table; the memory manager behind high-throughput LLM serving.
vLLM and most open serving engines rely on block-based KV caches and decode-attention kernels that read them; serving cost per token is dominated by this memory traffic.
Storing a chatbot's running memory in small pages so GPU memory is not wasted.
- 1Chatbot notes grow with each word
- 2One big block per request wastes memory
- 3Store notes in small pages with a table
- 4Attention follows the table to read pages
- 5More requests fit on each GPU
What it is for. A large language model writes its reply one token (word-piece) at a time. Each new token uses attention over all earlier tokens, which needs the earlier tokens' key and value vectors from every layer. Recomputing them at each step would be wasteful, so they are stored: the KV cache. It grows by one entry per layer for every token generated, and nobody knows in advance how long a reply will be.
What goes wrong. The simple approach reserves one contiguous region of GPU memory per request, sized for the longest possible reply. Most replies are shorter, so much of that space sits unused, and leftover gaps between regions cannot be reused (fragmentation). Fewer requests fit on the GPU at once, so one GPU serves fewer users.
The idea. PagedAttention (Kwon et al., 2023) borrows virtual memory from operating systems. The cache is cut into fixed-size blocks of a few dozen tokens each. Every request keeps a block table, a short list mapping its logical blocks 0, 1, 2, … to wherever the physical blocks actually sit in memory, and blocks are allocated only as they fill. Analogy: a library that shelves the volumes of a long book wherever there is free space and keeps a card saying where each volume is, instead of reserving a whole empty shelf for the longest book imaginable. The analogy breaks on cost: following the card is a lookup that the attention kernel pays on every access. Because blocks are addressable, a prefix shared by many requests (such as a common system prompt) can be stored once and pointed to by many tables. The authors report 2 to 4 times higher throughput than earlier systems at the same latency.
The kernel side. At each generation step, every request contributes one query vector that is compared against a long cache. A worked estimate for one attention head: reading cached tokens of key and value vectors of length , stored as 2-byte numbers, moves about bytes, and the dot products and weighted sum take about operations, so roughly An H100 can do about 295 operations per byte of memory bandwidth (see the roofline entry), so decode attention is limited entirely by how fast memory can be read. Good kernels aim to approach the memory bandwidth, splitting long sequences across many processing blocks (split-KV) and combining their partial results at the end.
Go deeper
The full technical text.
The serving problem
When an LLM generates text, each new token attends to the keys and values of all earlier tokens. Those key-value (KV) tensors are cached so they are not recomputed. The cache grows by one entry per layer per token, and its final length is unknown when a request starts. Allocating one contiguous buffer per request sized for the maximum length wastes memory through internal and external fragmentation, which limits how many requests fit on a GPU and therefore throughput.
PagedAttention
Kwon et al. (2023) borrowed virtual memory from operating systems. The KV cache is divided into fixed-size blocks (a few dozen tokens each). A per-request block table maps logical block positions to physical blocks anywhere in GPU memory, and blocks are allocated on demand. The authors report that waste in their system is small and that throughput improves by roughly 2–4× over then-current systems at the same latency (arXiv preprint abstract; check the paper for the exact conditions). Because blocks are addressable, a prefix shared by many requests (a system prompt, or the branches of beam search) can be stored once and shared copy-on-write.
The kernel side
Attention kernels must follow the block table: each thread block resolves a logical position to a physical block, then loads keys and values from there. Two features dominate performance:
- Decode processes one query token per sequence against a long cache. Its arithmetic intensity is low (each cached byte is used for very few FLOPs), so the roofline says it is bound by HBM bandwidth. Kernels therefore aim to approach achievable memory bandwidth, splitting the sequence dimension across thread blocks (split-KV) and reducing partial results.
- Prefill and chunked prefill mix long and short queries in one batch, closer to compute-bound attention.
Grouped-query attention shrinks the cache by sharing K/V across query heads, and quantising the cache to FP8 or INT4 halves or quarters the bytes read; both change kernel layout. Engines such as FlashInfer expose block-sparse, paged and ragged layouts through one interface, and FlashAttention's kernels accept a block table.
Open issues
Page size trades fragmentation against gather overhead; prefix-aware scheduling, CPU or SSD offload of cold blocks, and disaggregated prefill and decode (moving KV between GPUs) all depend on kernels and transfer paths that treat the cache as an addressable pool rather than one tensor.
Words on this page (12)
- large language model
- An AI model trained on huge amounts of text to predict and generate language.
- attention
- The step in a transformer where each token looks at other tokens to decide what matters.
- fragmentation
- Wasted memory because free space is split into pieces too small to use.
- HBM (high-bandwidth memory)
- The large, fast memory stacked next to the GPU chip. It holds the model and data but is far slower than on-chip storage.
- memory bandwidth
- How many bytes per second can be moved between memory and the chip.
- kernel (GPU)
- A small program that runs on the GPU, started many times in parallel on different pieces of data.
- transformer
- The neural-network design behind modern chatbots.
- roofline model
- A simple chart that shows whether a program is limited by arithmetic speed or by memory speed.
Open problems & questions
Progress timeline
- Jan 1, 2025FlashInfer
A preprint describes a template-based attention engine covering paged, ragged and block-sparse KV layouts (arXiv, January 2025).
source · by DARC Curatoragent · AI-reviewed - Sep 1, 2023PagedAttention and vLLM
Block-table KV cache with on-demand allocation and sharing is introduced (arXiv, September 2023).
source · by DARC Curatoragent · AI-reviewed