What memory problem PagedAttention solves

WHAT THIS TESTS The interviewer wants to know whether you understand the real bottleneck in LLM serving: KV-cache memory, not raw FLOPs. PagedAttention is fundamentally a memory-management idea borrowed from operating systems.

A GOOD ANSWER COVERS The problem: the KV cache for a request grows as it generates tokens, but you do not know the final length in advance. Naive serving pre-allocates a single contiguous block sized to the maximum possible sequence length for each request. This causes internal fragmentation, most of the reserved space sits unused because most requests are shorter than the maximum, and external fragmentation, contiguous free regions get carved up so new requests cannot find a large enough contiguous slot even when total free memory suffices. The result is poor memory utilization, which caps how many requests can be batched concurrently and throttles throughput. PagedAttention's solution: partition each sequence's KV cache into fixed-size blocks, akin to OS memory pages, and store them in non-contiguous physical GPU memory, with a block table mapping logical positions to physical blocks. Blocks are allocated on demand as the sequence grows, eliminating the need for one big contiguous reservation and reducing waste to at most one partially filled block per sequence. It also enables sharing identical prefix blocks across sequences, for example in beam search or shared system prompts, via copy-on-write.

COMMON WRONG ANSWERS Saying PagedAttention reduces attention computation or FLOPs, it is about memory layout, not math. Confusing it with FlashAttention, which optimizes the attention kernel's memory IO, not cache allocation. Ignoring the contiguous-allocation root cause.

LIKELY FOLLOW-UPS How does it enable prefix sharing, block tables plus copy-on-write. What is the analogy to virtual memory, pages and page tables. How does this raise throughput, more concurrent sequences per GPU.

ONE CONCRETE EXAMPLE Serving requests that might reach 4096 tokens but average 300, contiguous allocation wastes over 90 percent of each reservation. PagedAttention allocates 16-token blocks on demand, packing far more sequences into the same GPU and multiplying throughput.