English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

vToken: Adding Virtual Memory to LLM KV Caches to Eliminate Intra-Block Fragmentation

Forum topic · ✨步子哥 · 2026-08-16

Summary

vToken is a token-level virtualization layer for LLM KV cache management, developed by researchers at the National University of Defense Technology and Peking University and built on vLLM v0.18.0. The paper identifies a granularity mismatch: eviction policies (H2O, StreamingLLM, Scissorhands) evict tokens, while PagedAttention manages memory in 16-token blocks, leaving 40%-60% of logical free space trapped in partially-dead blocks that cannot be reused. vToken decouples logical token sequences from physical KV blocks, analogous to OS virtual memory: a Token Table (like a page table) records each token's physical location and alive/dead status, while an asynchronous reclamation backend compacts low-utilization blocks on a separate CUDA stream without global synchronization. On H100 80GB with Mistral-7B and Llama-3.1-8B (ShareGPT, LongBench), vToken improves average KV memory utilization by ~22%, reduces retained blocks by 27%-72%, and raises serving concurrency by 60% to 2x under equal latency SLAs, with under 1% overhead when idle. Policy adapter code shrank from 500+ lines to under 50. Limitations include single-GPU scope, skipped shared prefix blocks, and no public code release.

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%
  • 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:

  • Physical location: (block ID, offset)
  • Alive bit: alive or dead
  • 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

  • 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.
  • Results (H100 80GB, Mistral-7B / Llama-3.1-8B, ShareGPT + LongBench)

    Memory efficiency vs. Naive-Evict:

  • Average memory utilization: +21.88% (Llama-3.1-8B), +21.67% (Mistral-7B)
  • Retained blocks: -27.2% to -72.3%
  • Throughput (p95 latency capped at 1.05x baseline):

  • 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%
  • Random eviction benefits most — scattered live tokens maximize Naive-Evict fragmentation. The worse the fragmentation, the more vToken pays off.

    Capacity frontier:

  • 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
  • Overhead:

  • Pure indirection overhead (hook installed, eviction off): throughput and p95 changes <1.0%
  • Main cost is planner-side opportunity checks (CPU), not KV copying
  • 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

  • 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

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

Tags

#llm-inference#kv-cache#vllm#virtual-memory#paged-attention#memory-fragmentation#h2o#gpu-memory-optimization

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178633563