The KV Cache · 4. Blocks and shared prefixes
One table, real rows, and the resources behind each policyI follow real keys and values through scattered blocks and shared prefixes.
Open video ↗Read the walkthrough
Reservation. Four requests have lengths 179, 402, 155 and 293, with a maximum of 512. At 327,680 bytes per token, reserved memory is 671,088,640 bytes, used memory 337,182,720, and wasted memory 333,905,920. The PagedAttention paper measured only 20.4 to 38.2 percent useful cache memory in the systems it compared, and reports under four percent waste and two to four times throughput at the same latency. Those are its benchmark results, not guarantees for this example.
The block table. The storage exercise holds all ten input tokens, including the full stop, in logical blocks 0, 1, 2 and physical blocks 6, 1, 9. This differs deliberately from the pilot generation, which emits the stop without processing it. Every numeric row is from the unchanged Transformer toy. A real physical block has corresponding storage in each layer; the drawing shows one toy layer and head.
The read. The actual Breaking decode pass reads eight rows. Token position 5 is logical block 1, offset 1, so table[1] sends the read to physical block 1. Scores [1.5, 0, 2, 0, 0, 1, 0, 2] give attention output [0.382, 1.310, -0.092, 0.382]. The displayed decimals are rounded; the sum uses full precision. The grids explain the logical read, not a claim that an optimized kernel materializes all these intermediate matrices.
Sharing and copy-on-write. The generic fork shares blocks 6 and 1 with reference counts of two. Before divergent writes to the partial tail, B copies physical 1 to 4. A has [6, 1], B has [6, 4], and references are 2, 1, 1 for physical blocks 6, 1, 4. Breaking and the are illustrative alternative continuations; the latter is not the greedy toy answer. Current vLLM V1 automatic prefix caching reuses full blocks, so this partial-tail fork is a general PagedAttention mechanism, not its APC implementation.
Reuse. Twenty requests sharing a 4,096-token prefix avoid nineteen copies: 25,501,368,320 bytes, or 25.50 GB, before private suffixes. vLLM hashes tokens and preceding prefix, with prefix caching enabled by default in V1. SGLang uses a radix tree, evicts LRU leaves, and uses cache-aware scheduling. Its paper reports 52.4 and 74.1 percent cache hit rates on two production traces, average 1.7 times lower time to first token, and up to 6.4 times benchmark throughput against the systems it evaluated. Exact reuse requires matching model state, positions and relevant input context.
Waste bound. A 16-token block of the real model is 5,242,880 bytes, or 5 MiB. At most fifteen unused token slots cost 4.6875 MiB per sequence in this simple fixed-block layout. A 432 GB node-wide cache budget holds 82,397 such blocks before metadata. Paging allocates physical blocks on demand within a pool that the engine may preallocate. It removes the requirement for a contiguous per-request slab; blocks themselves are contiguous storage units.