vToken recovers up to 72% of wasted vLLM KV cache

vToken recovers 27.2% to 72.3% of the KV cache blocks vLLM wastes during eviction, per a paper posted August 16. That waste caps how many requests a server can hold in memory. Recovering it lifts SLA-constrained throughput as much as 1.37x and, under a tight active-KV budget, doubles the concurrency a server can handle.

The mismatch is architectural. Eviction algorithms like H2O and Scissorhands drop individual tokens, but PagedAttention only frees memory in fixed-size blocks. Evict a token from the middle of a block, and the hole sits unusable until the whole block empties.

vToken's fix is a token-table indirection layer that tracks which tokens in a block are still live. Asynchronous repacking then moves those tokens together to free whole blocks, without changing PagedAttention's kernels or breaking CUDA Graph compatibility.

The paper also reports that adding a new eviction policy now takes under 50 lines of code, down from more than 500. It calls vToken a working vLLM patch, not a simulation.