Explain how PagedAttention works and why it matters.

PagedAttention solves the issue of inefficient KV cache allocation by partitioning the KV cache into fixed-size blocks. By using a block table to map logical tokens to these physical blocks, the system avoids the need for contiguous memory allocation. This approach significantly reduces memory waste; while pre-PagedAttention systems often lose 20-40% of their KV cache to fragmentation, PagedAttention limits internal fragmentation to at most 15 tokens per sequence with a block size of 16. Furthermore, it supports efficient memory sharing across sequences through copy-on-write, which is particularly beneficial for parallel sampling and beam search.