Even The Oracle Wastes

The PagedAttention paper profiles how much of a server's KV cache memory actually holds live token states. Three configurations pre-allocate a contiguous chunk per request and differ only in how they pick the chunk size:

configuration	live token states	reserved for future tokens	internal frag.	external frag. and other
pre-allocate the model's max length	20.4%	13.3%	57.3%	8.9%
round the max length up to a power of two	26.8%	17.9%	13.6%	41.6%
oracle: exact output length known in advance	38.2%	25.2%	0%	36.6%
vLLM (paged blocks)	96.3%	-	-	3.7%

The oracle row is the interesting one. It sizes every chunk perfectly, with zero internal fragmentation, and still puts only 38.2 percent of the cache into live tokens. Why does perfect knowledge of the output length not solve the problem?

Model parameters take 65 percent of the card, so only 35 percent is available to the KV cache in the first place.

Its unwritten tail is reserved for the request's whole lifetime and unusable by anyone else, and chunks of many different sizes leave holes between them.

The oracle still has to round each chunk up to the allocator's block granularity, and that rounding is what the 36.6 percent measures.

Attention kernels require the KV tensor to be padded to a power of two, so the oracle cannot actually use its exact size.