vToken: Token-Level Virtualization for Reclaimable KV Caches in LLM Inference

Background: KV cache as the dominant memory bottleneck

For a 13B LLaMA model serving 32K-token contexts, KV cache alone reaches ~25 GB—about one-third of an 80 GB GPU. Existing solutions—PagedAttention in vLLM plus token-level eviction policies like H2O, StreamingLLM, and Scissorhands—address parts of the problem but leave a critical inefficiency unaddressed.

The problem: granularity mismatch

Eviction policies make decisions at token granularity, but vLLM manages memory at 16-token block granularity. When H2O marks 10 of 16 tokens in a block as evictable, the block cannot be freed because 6 live tokens remain. The 10 evicted slots become intra-block fragmentation—logical free space that physical memory cannot reclaim.

Measurements on vLLM at 16K context, batch size 16:

• Most allocated blocks show utilization below 50%.
• Intra-block waste rate F reaches 40%–60%.

Core insight: add a virtualization layer

vToken introduces a token-level virtualization boundary above the block-level runtime, directly analogous to OS virtual memory:

| OS Virtual Memory | vToken | |---|---| | Process virtual address space | Request's logical token sequence | | Physical page frames | PagedAttention physical KV blocks | | Page table | Token Table | | Page fault + reclamation | Physical reclamation backend |

Token Table: a "page table" for KV cache

For each request, vToken maintains a Token Table recording, per logical token ID:

• Physical location: (block ID, offset)
• Liveness bit: alive or dead

Eviction calls evict_token(req_id, token_id) and only updates the liveness bit—no KV data moves. Metadata overhead is ~256 KB for a 16K-token sequence (16 bytes per entry), under 0.1% of a 7B model's FP16 KV footprint (~2 GB).

Physical reclamation backend: async compaction

After marking dead tokens, the backend: 1. Scans block utilization to find low-efficiency blocks below a threshold. 2. Checks whether enough free blocks exist as destinations (margin-aware admission) and waits if not. 3. Plans greedy packing of live tokens into destination blocks. 4. Executes KV copies on an independent CUDA stream that does not block decoding.

The key design choice is async copying. The planner submits moves; decoding continues on the main stream; a CUDA event ensures copies finish before attention reads refresh the slot mapping. There is no global synchronization point.

Three design challenges and solutions

• C1 – Dual-view consistency: tokens die independently, but blocks free only when all KV entries are moved. Solution: the Token Table records both token liveness and block occupancy, kept consistent through one structure.
• C2 – Safe reclamation during decoding: mid-migration reads would mix old and new KV. Solution: slot mappings update atomically after copy completion; attention kernels read only through the slot map.
• C3 – Policy-agnostic amortized cost: H2O, StreamingLLM, Random, and others share the scheduler, block manager, and worker code. Solution: vToken exposes evict_token, sync_new_tokens, and apply_moves. Policies implement only the first two; the third is internal. Policy adapters drop from 500+ lines to under 50.

Results on H100 80GB (Mistral-7B, Llama-3.1-8B; ShareGPT, LongBench)

Memory efficiency

• Average memory utilization: +21.88% on Llama-3.1-8B; +21.67% on Mistral-7B.
• Retained blocks: -27.2% to -72.3%.
• Naive-Evict's main loss is the runtime's inability to translate token-level liveness into reclaimable physical capacity—not the eviction policy itself.

Throughput under tight latency SLAs (p95 ≤ 1.05× baseline)

• Mistral-7B: throughput +9.9% to +37.3%; p95 latency -9.9% to -27.5%.
• Llama-3.1-8B: average throughput +18.9%; p95 latency -14.7%.
• Strongest gains under Scissorhands: throughput +33.3% to +103.7%; p95 latency -21.8% to -33.0%.
• Random policy yields the largest gains because live tokens scatter across blocks and naive fragmentation worsens.

Capacity frontier

• At gpu_mem_util=0.35 (5,427 KV blocks): Native vLLM and Naive-Evict support C=5 concurrent requests; vToken supports C=8 (+60%).
• At gpu_mem_util=0.50 (11,519 blocks): native reaches C=11; vToken reaches C=22 (2×).
• vToken degrades gracefully: at C=8 it serves 180.3 tok/s, near its own C=5 peak of 203.2 tok/s.

Overhead

• Hook-only overhead (no eviction/reclamation enabled): throughput and p95 changes <1.0%.
• Main CPU cost comes from the planner's eligibility checks, not KV migration.
• Async copies complete across multiple decode steps; no explicit sync waits.

Engineering takeaways

1. Granularity matching matters. When two layers operate at different granularities, add a virtualization layer rather than forcing one side to match the other. 2. Change the layer, not the level. vToken does not shrink blocks; it adds a token-level abstraction above them—another instance of solving problems by shifting abstraction layers rather than optimizing within the original layer. 3. OS patterns transfer to AI systems. Token Table ≈ page table; async CUDA stream ≈ DMA; slot-map refresh ≈ TLB flush. Sixty years of OS design applies directly. 4. Lower integration cost accelerates research. Dropping policy adapters from 500+ lines to under 50 lowers the barrier to experimenting with new eviction strategies.

Limitations

• Single-node, single-GPU. Distributed scheduling and cross-device KV migration are out of scope.
• Shared prefix blocks are conservatively skipped to preserve prefix-cache correctness; copy-on-write is suggested but not implemented.
• Planner CPU overhead remains the dominant cost.
• vLLM-only instantiation. The abstraction is general, but no open-source code is available yet—adoption in TensorRT-LLM and SGLang requires per-engine implementation.

Paper

vToken: Token-Level Virtualization for Reclaimable KV Caches — Yuanhang Gao, Xiangrui Yang, Yuanfeng Chen, Hongjia Chen, Qianru Lv, Wenfei Wu, Dongsheng Li (NUDT, Peking University). Implemented on vLLM v0.18.0; no public repository at time of writing.

Personal note: virtualization as a recurring AI-systems pattern

PagedAttention resembles physical memory paging; vToken resembles virtual memory; KV eviction resembles page replacement; prefix cache resembles shared memory; chunked prefill resembles prefetching. Each classical OS problem is being re-solved in LLM inference. The likely next target: virtualizing attention computation itself—indirect mappings so that sparse attention, sliding window, and dynamic routing share one runtime instead of each requiring custom CUDA kernels. The general lesson: when two layers' granularities clash, do not optimize either in place—add a virtualization layer.