A naive KV-cache implementation reserves one large contiguous memory block per request sized for the worst case, wasting huge amounts of GPU memory to fragmentation. PagedAttention (from the vLLM paper) borrows the operating-system idea of paging: the KV-cache is split into small fixed-size blocks allocated on demand and referenced indirectly, eliminating fragmentation and letting a GPU serve far more concurrent sequences from the same memory.
Worked example: PagedAttention stores the KV cache in fixed-size, non-contiguous blocks managed by a block table — like OS virtual-memory paging — so memory is allocated on demand, fragmentation vanishes, and requests sharing a prefix can share blocks. Gotcha: it dramatically raises how many requests fit in GPU memory; the lesson generalizes — LLM-serving bottlenecks are often memory-management problems solved by classic systems ideas.