What problem does paged attention solve in LLM serving?

It fixes KV cache waste caused by reserving large contiguous regions for requests that may finish early. Instead of allocating up to a declared maximum length, the server allocates fixed-size physical blocks as the sequence grows. That keeps batching capacity tied to actual generated tokens, not pessimistic reservations.

How does a block table work in paged attention?

Each live sequence has a table mapping its logical block positions to physical KV blocks in GPU memory. The attention kernel treats the sequence as logically continuous, but follows the table to gather keys and values from wherever those blocks currently live. This is similar to virtual memory paging.

Is paged attention the same as FlashAttention?

No. FlashAttention improves how attention computation moves data through the kernel, especially around SRAM and HBM traffic. Paged attention manages the KV cache address space across requests. They are complementary: one optimises the kernel’s internal data movement, the other makes server-side KV memory allocation practical.

The KV Cache

03.07 · Walkthrough

Paged Attention

Design paged attention: map logical KV blocks to physical ones via a block table, eliminate fragmentation, and explain why this is the 2026 floor, not an optimisation. Trace vLLM's block-level memory management from allocation through eviction.

Paged attention stores each request’s KV cache as logical token blocks mapped to reusable physical blocks, so attention can read a continuous sequence without requiring continuous memory. Allocation happens as tokens arrive, finished blocks return to a pool, and fragmentation is bounded to tail waste rather than maximum requested length.

What this lesson answers

how does paged attention manage KV cache memory
why does vLLM use block tables for attention
how does paged attention reduce KV fragmentation

Notes

PagedAttention is the KV-cache layout from the vLLM paper “Efficient Memory Management for Large Language Model Serving with PagedAttention” (Kwon et al., SOSP 2023): split each sequence’s logical KV cache into fixed-size token blocks and translate logical block ids to physical block ids through a per-sequence block table, exactly like virtual memory paging. For a model with $L$ layers, $H_{k v}$ KV heads, head dimension $d$ , element size $b$ bytes, and block size $B$ tokens, one physical KV block costs $M_{b l oc k} = 2 L B H_{k v} d b$ , where the factor $2$ is K and V.

References

Common questions

What problem does paged attention solve in LLM serving?: It fixes KV cache waste caused by reserving large contiguous regions for requests that may finish early. Instead of allocating up to a declared maximum length, the server allocates fixed-size physical blocks as the sequence grows. That keeps batching capacity tied to actual generated tokens, not pessimistic reservations.
How does a block table work in paged attention?: Each live sequence has a table mapping its logical block positions to physical KV blocks in GPU memory. The attention kernel treats the sequence as logically continuous, but follows the table to gather keys and values from wherever those blocks currently live. This is similar to virtual memory paging.
Is paged attention the same as FlashAttention?: No. FlashAttention improves how attention computation moves data through the kernel, especially around SRAM and HBM traffic. Paged attention manages the KV cache address space across requests. They are complementary: one optimises the kernel’s internal data movement, the other makes server-side KV memory allocation practical.

Short definition: what is Paged Attention?

03.06 · The KV CacheFragmentation 03.08 · The KV CachePrefix Caching