How does PagedAttention reduce KV allocation waste?

The bottleneck

Requests have different lengths and grow during generation. Reserving maximum contiguous buffers wastes memory, while resizing causes fragmentation. PagedAttention divides KV into fixed-size blocks and maps logical positions to noncontiguous physical blocks.

The mechanism

Requests acquire blocks as needed, and attention kernels follow the block table. Branching samples can share common prefix blocks with copy-on-write. This improves allocation and sharing rather than compressing each token’s mathematical KV payload; it complements representations such as GQA.

blocks = ceil(T / block_size)

Examples and evidence

Example: block size 16 and length 33 need 3 blocks with capacity 48, leaving 15 unused positions. Tail waste and metadata remain, but the maximum context need not be reserved. Real kernels and allocation policies affect results.

New constraints

Indirection, reference counting and kernels add complexity. Cross-request sharing requires correct cache keys and isolation. Paging can fit more requests without automatically meeting their latency targets.