The Problem: KV Caches Are the Memory Bottleneck
Serving a 13B LLaMA model, the weights take ~26 GB — but at a 32K context, the KV cache alone consumes ~25 GB (about 0.8 MB per token). On an 80 GB GPU, a single long-context request eats a third of the memory.
The community's answer was PagedAttention (the core of vLLM), which manages KV caches in fixed-size blocks (usually 16 tokens/block), like OS paging. Then came token-level eviction algorithms: H2O keeps high-attention "heavy hitter" tokens, StreamingLLM keeps attention sinks plus a recent window, Scissorhands keeps persistent attention patterns.
Problem solved? No.
The Overlooked "Granularity Mismatch"
The vToken paper (August 2026, arXiv:2608.13263) formally defines a problem everyone has hit:
> Eviction policies make decisions at token granularity, but the runtime manages memory at block granularity. These granularities don't match.
If H2O evicts 10 tokens inside a 16-token block, the block can't be freed because 6 tokens remain alive — the 10 evicted slots become intra-block fragmentation. Measured on vLLM with H2O at 16K context, batch size 16:
- Most allocated blocks are less than 50% utilized
- Intra-block waste rate F reaches 40%-60%
- Physical location: (block ID, offset)
- Alive bit: alive or dead
- C1 — Dual-view consistency: token-level alive status and block-level occupancy are maintained in the same table.
- C2 — Safe reclamation mid-decode: slot mappings update atomically after migration completes; attention kernels read only the slot mapping; CUDA events order copy completion before mapping refresh.
- C3 — Policy-agnostic amortized cost: three interfaces —
evict_token,sync_new_tokens,apply_moves(internal). Policy adapters shrank from 500+ lines to under 50. - Average memory utilization: +21.88% (Llama-3.1-8B), +21.67% (Mistral-7B)
- Retained blocks: -27.2% to -72.3%
- Mistral-7B: throughput +9.9% to +37.3%, p95 latency -9.9% to -27.5%
- Llama-3.1-8B: throughput +18.9% average, p95 -14.7%
- Best under Scissorhands: throughput +33.3% to +103.7%
- At
gpu_mem_util=0.35: concurrency C=5 (baseline) → C=8 with vToken (+60%) - At
gpu_mem_util=0.50: C=11 → C=22 (2x) - At C=8, throughput is 180.3 tokens/s vs. its own C=5 peak of 203.2 — graceful degradation, not collapse
- Pure indirection overhead (hook installed, eviction off): throughput and p95 changes <1.0%
- Main cost is planner-side opportunity checks (CPU), not KV copying
- Single-node, single-GPU: distributed scheduling and cross-device KV migration are out of scope
- Shared prefix blocks conservatively skipped (copy-on-write proposed but not implemented)
- Planner overhead is the main CPU cost — an engineering optimization target
- vLLM-only implementation: TensorRT-LLM, SGLang, etc. would need their own hooks. No public code release, limiting immediate community adoption
The evicted "unimportant" tokens save logical space, but 40-60% of it is trapped in half-dead physical blocks, unreusable by other requests.
vToken's Core Insight: Add a Virtualization Layer
> Add a token-level virtualization boundary on top of the block-level runtime.
This is virtual memory, applied to KV caches:
| 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 | | Process unaware of physical layout | Eviction policy unaware of block layout |
Token Table: A Page Table for KV Caches
Each request gets a Token Table recording, per logical token ID:
When a policy calls evict_token(req_id, token_id), only the alive bit flips — no KV data moves. Metadata cost is tiny: a 16K-token sequence needs 256 KB (16 bytes/entry), under 0.1% of a 7B model's FP16 KV footprint (~2 GB).
Physical Reclamation Backend: Async "Defragmentation"
1. Reclamation eligibility check: scan for blocks below a utilization threshold 2. Slack-aware admission: verify enough free destination blocks exist (don't create new fragmentation) 3. Migration planning: greedily pack live tokens into destination blocks 4. Asynchronous copy: KV copies run on a dedicated CUDA stream, non-blocking for decoding; CUDA events guarantee completion before the next attention computation refreshes slot mappings — no global sync point.
Three Design Challenges
Results (H100 80GB, Mistral-7B / Llama-3.1-8B, ShareGPT + LongBench)
Memory efficiency vs. Naive-Evict:
Throughput (p95 latency capped at 1.05x baseline):
Random eviction benefits most — scattered live tokens maximize Naive-Evict fragmentation. The worse the fragmentation, the more vToken pays off.
Capacity frontier:
Overhead:
Engineering Takeaways
1. Granularity alignment: eviction is token-granular, PagedAttention is block-granular; mismatch causes 40-60% fragmentation. Aligning granularity via a virtualization layer eliminates it — the eviction algorithm isn't bad; the runtime's granularity doesn't match it.
2. Solve at a different layer: vToken doesn't shrink blocks — it adds a layer above, following the same pattern as other cross-layer solutions.
3. OS design patterns transfer: Token Table = page table, evict_token = marking a page invalid, reclamation backend = page-reclaim daemon, async CUDA stream = DMA, slot mapping refresh = TLB flush. Sixty years of virtual memory design maps cleanly onto KV cache management.
4. Cheaper experimentation: policies now only implement SelectVictims; new eviction strategies no longer require deep vLLM block-manager knowledge.
Unresolved Issues
Closing Thought
AI systems are re-walking the road of computer systems: PagedAttention = paging, vToken = virtual memory, KV eviction = page replacement, prefix cache = shared memory, chunked prefill = prefetch. vToken's real value is proving that the 60-year-old virtualization abstraction still works in the LLM serving era. When two layers' granularities mismatch, don't grind at either one — add a layer of virtualization.
---
Paper: vToken: Token-Level Virtualization for Reclaimable KV Caches Authors: Yuanhang Gao, Xiangrui Yang, Yuanfeng Chen, Hongjia Chen, Qianru Lv, Wenfei Wu, Dongsheng Li Institutions: National University of Defense Technology, Peking University Implemented on vLLM v0.18.0; no public repository at time of writing