Paged Attention Fundamentals
What you'll learn: How Paged Attention organizes KV cache in fixed-size blocks to eliminate memory waste and enable efficient sharing across requests.
The Memory Fragmentation Problem
In traditional KV cache implementations, each sequence reserves a contiguous block of memory for its entire maximum length. If a sequence uses only 100 tokens but reserves space for 2048, the unused memory sits idle—this is memory fragmentation. Worse, when multiple sequences share a prompt prefix (like a system message), each wastefully stores duplicate KV states.
The Paging Solution
Paged Attention borrows an idea from operating systems: divide memory into fixed-size pages (or blocks), typically holding 16-64 tokens each. Instead of allocating one giant contiguous chunk, the KV cache grows incrementally as the sequence generates tokens, requesting new pages only when needed.
Think of it like a notebook: instead of reserving an entire 100-page notebook for a grocery list, you tear out pages as you need them, using exactly what's required.
How It Works
- Block tables map logical token positions to physical memory blocks
- Each sequence maintains a small pointer table, not the full cache
- When generating token 65 in a sequence with 64-token blocks, the system simply allocates a second block
- Prefix sharing: Multiple sequences with identical prompts point to the same physical blocks for shared tokens, using copy-on-write only when they diverge
This enables near-zero waste and dramatically increases batch size—critical for throughput optimization during inference.
Key Takeaway: Paged Attention treats KV cache like virtual memory, storing it in fixed-size blocks that eliminate fragmentation, reduce memory footprint by ~50%, and enable efficient sharing of prompt prefixes across multiple requests.