Back to AI Research

AI Research

vToken: Token-Level Virtualization for Reclaimable... | AI Research

Key Takeaways

  • vToken: Token-Level Virtualization for Reclaimable KV Caches introduces a virtualization layer designed to solve the memory fragmentation bottleneck in large...
  • Large language model serving faces a critical memory bottleneck: the KV cache grows with sequence length and batch size.
  • PagedAttention uses fixed-size memory blocks to reduce allocator-level fragmentation, but recent KV eviction algorithms operate at a token granularity finer than block-level management.
  • This mismatch causes intra-block fragmentation, leaving a large fraction of allocated KV memory unreclaimable.
  • We present vToken, a lightweight token-level virtualization layer that decouples logical token liveness from physical block placement.
Paper AbstractExpand

Large language model serving faces a critical memory bottleneck: the KV cache grows with sequence length and batch size. PagedAttention uses fixed-size memory blocks to reduce allocator-level fragmentation, but recent KV eviction algorithms operate at a token granularity finer than block-level management. This mismatch causes intra-block fragmentation, leaving a large fraction of allocated KV memory unreclaimable. We present vToken, a lightweight token-level virtualization layer that decouples logical token liveness from physical block placement. vToken maintains a stable logical token view through token-table indirection and realizes physical reclamation by repacking live tokens asynchronously. The design preserves PagedAttention kernels and CUDA Graph compatibility. We implement vToken in vLLM and evaluate it with H2O, Random, and Scissorhands across models. Compared with a paired Naive-Evict baseline, vToken reduces retained KV blocks per request by 27.2\%--72.3\% and improves SLA-constrained throughput by up to 1.37$\times$. Under a constrained active-KV budget, it extends the maximum feasible concurrency by up to 2$\times$, while reducing the per-policy integration footprint from 500+ lines to under 50.

vToken: Token-Level Virtualization for Reclaimable KV Caches introduces a virtualization layer designed to solve the memory fragmentation bottleneck in large language model (LLM) serving. By decoupling logical token liveness from physical block storage, the system allows inference engines to reclaim memory from underutilized blocks without requiring changes to existing attention kernels or memory allocators.

The Granularity Mismatch

Modern LLM serving systems like vLLM use PagedAttention to manage KV cache memory in fixed-size blocks. While this reduces allocator-level fragmentation, it creates a conflict with token-level eviction algorithms (such as H2O or Scissorhands). These algorithms decide which specific tokens to keep or discard, but because the runtime manages memory at the block level, a block cannot be freed until every token inside it is evicted. This leads to "intra-block fragmentation," where partially empty blocks remain trapped in memory, preventing the system from reusing that space for new requests. The authors report that this mismatch can result in intra-block waste exceeding 40% when using a 16K context window.

How vToken Works

vToken acts as a lightweight virtualization layer that sits between eviction policies and the underlying PagedAttention substrate. It uses three primary mechanisms to manage memory:

  • Token Table Indirection: A per-request token table tracks the logical identity of each token and its physical location. When an eviction policy marks a token as dead, the system updates this table rather than immediately modifying physical memory.

  • Asynchronous Repacking: The system uses a reclamation backend to perform "lazy compaction." When fragmentation reaches a certain threshold, the backend identifies low-utilization blocks, moves the remaining live tokens into new, tightly packed blocks, and then releases the original blocks back to the free pool.

  • Stage-Aware Copying: To avoid slowing down the model's inference speed, vToken performs these memory moves on a dedicated stream after the attention forward pass is complete. This ensures that the KV cache copy process does not compete with the model's primary compute tasks for GPU memory bandwidth.

Performance and Integration

The authors implemented vToken within the vLLM framework and evaluated it using H2O, Random, and Scissorhands eviction policies. The results show that vToken reduces the number of retained KV blocks per request by 27.2% to 72.3% compared to a naive eviction baseline. Under memory-constrained conditions, the system improved SLA-constrained throughput by up to 1.37× and increased maximum feasible concurrency by up to 2×. Furthermore, the abstraction layer simplifies development; integrating a new eviction policy requires fewer than 50 lines of code, compared to over 500 lines for a direct implementation.

Considerations

vToken is designed as a pressure-activated extension rather than a replacement for standard serving. The authors note that the native, non-virtualized path remains more efficient when KV memory is not the primary bottleneck. Additionally, the system relies on a tunable threshold for reclamation; setting this threshold involves a trade-off between memory efficiency and the overhead associated with frequent relocation planning. The design intentionally keeps the physical block allocator and attention kernels untouched to maintain compatibility with existing infrastructure.

Comments (0)

No comments yet

Be the first to share your thoughts!