The idea
Early servers reserved one contiguous block of GPU memory per request for its KV cache, sized for the maximum possible length. Most requests are much shorter, so most of that memory sat empty, which capped how many requests could run at once.
PagedAttention, introduced with vLLM, splits the KV cache into fixed-size blocks allocated on demand and tracked by a block table, just like virtual memory pages. Little memory is wasted, and identical prefixes can share blocks.
More free memory means bigger batches, which means higher throughput on the same GPU.
It is a key reason self-hosted serving became cost-competitive, and a classic example of systems ideas applied to AI.
Picture it
Words to know
- Block tableMaps a sequence’s logical KV positions to physical memory blocks.
- FragmentationMemory that is reserved but unusable.
Try it without code
Do the waste maths
- Assume max length 4,096 tokens and average request 600 tokens.
- With contiguous pre-allocation, what share of KV memory is wasted?
- With 16-token pages, how much at most per request?
Use it in code
Compare reserved memory for contiguous vs paged allocation.
import math, random
random.seed(1)
MAX_LEN, PAGE = 4096, 16
lengths = [random.randint(100, 1500) for _ in range(64)]
contiguous = MAX_LEN * len(lengths)
paged = sum(math.ceil(n / PAGE) * PAGE for n in lengths)
used = sum(lengths)
print(f"contiguous waste {1 - used / contiguous:.0%}, paged waste {1 - used / paged:.1%}")Explain PagedAttention in 5 sentences as you would in a system design interview, including why it raises throughput.
Common mistakes
- Thinking it changes model outputs; it only changes memory management.