Paged Attention: Core Concept
What you'll learn: How splitting KV cache into fixed-size blocks solves the memory fragmentation problem in LLM serving.
The Big Idea
Paged Attention borrows a concept from operating systems: instead of storing the entire KV cache for each sequence in one contiguous memory chunk, we break it into fixed-size blocks (called "pages"). These pages can live anywhere in physical GPU memory—they don't need to be next to each other.
Think of it like reading a book where chapters are stored on different shelves in a library. You don't need all chapters side-by-side on one shelf; you just need a table of contents (page table) that tells you where each chapter lives.
How It Works
In traditional LLM serving, each sequence's KV cache must occupy a continuous memory block. This creates two problems:
- External fragmentation: Large gaps appear between allocated blocks
- Over-reservation: You must allocate for the maximum possible sequence length upfront
Paged Attention solves this by:
- Dividing KV cache into pages (e.g., 16 or 64 tokens per page)
- Maintaining a page table that maps logical positions to physical memory locations
- Allocating pages on-demand as sequences grow
- Allowing pages to be scattered across GPU memory
The Attention Mechanism Adaptation
During attention computation, instead of reading from one contiguous tensor, the system:
- Consults the page table to find which physical pages contain the needed keys/values
- Gathers data from multiple non-contiguous locations
- Performs attention as normal
The slight overhead of indirect addressing is vastly outweighed by eliminating fragmentation and enabling much higher batch sizes.
Key Takeaway: Paged Attention treats KV cache like virtual memory—breaking it into fixed-size pages stored non-contiguously—dramatically improving memory utilization and reducing waste in LLM serving systems.