vToken: Turning Token-Level KV Eviction into Actually Reusable GPU Memory

Review date: 2026-08-16 Author: Zhongzhu Zhou Paper reviewed: vToken: Token-Level Virtualization for Reclaimable KV Caches Paper authors: Yuanhang Gao, Xiangrui Yang, Yuanfeng Chen, Hongjia Chen, Qianru Lv, Wenfei Wu, Dongsheng Li (National University of Defense Technology; Peking University) arXiv: 2608.13263 Venue/Status: arXiv preprint, August 2026

1. The setup: two good ideas that don’t compose

If you’ve spent any time reading LLM-serving systems papers, you’ve met both halves of this paper’s premise separately, and each one, on its own, sounds like a solved problem. Half one: PagedAttention (introduced by vLLM) manages the KV cache in fixed-size blocks instead of one contiguous per-request allocation, borrowing the idea of virtual-memory paging from operating systems, and this is now the default way essentially every serious LLM inference engine manages GPU memory. Half two: token-level KV eviction — H2O, StreamingLLM, Scissorhands, and a growing family of similar algorithms — observes that not every previously-generated token is equally useful for predicting the next one, and discards the unimportant ones to shrink the cache’s memory footprint, often by 50% or more with minimal quality loss.

Put those two ideas together in a real serving system, and something surprising happens: they don’t compose cleanly. The eviction algorithm makes decisions about individual tokens. The block manager only knows how to reclaim memory in units of whole blocks. If a 16-token block contains one token that H2O still wants to keep and fifteen tokens it has marked dead, that block cannot be returned to the free pool — it just sits there, allocated, mostly wasted. This paper’s core empirical finding is that this isn’t a minor edge case: across three eviction policies and two workloads, the resulting intra-block waste ratio reaches 40-60%, meaning a large fraction of the memory you thought your eviction policy freed up is actually still locked away, invisible to the allocator. vToken’s job is to fix exactly this — not by inventing a new eviction algorithm, but by inserting a virtualization layer that lets existing eviction decisions actually turn into usable physical memory.

This review works through why the mismatch exists structurally, unpacks vToken’s token-table design and its asynchronous reclamation backend step by step, walks through the deadlock-safety and correctness arguments the paper makes for touching live KV memory during decoding, and then digs into the six evaluation questions the paper asks, before turning a critical eye on what the paper leaves unaddressed.

Prerequisites: what you need to know before diving in

The KV cache and why it dominates serving memory. During autoregressive generation, a Transformer computes attention over every previously-generated token at each decoding step. To avoid recomputing the Key and Value projections for all prior tokens on every step, the serving system caches them — this is the KV cache. For a model with $L$ layers, $H$ attention heads, and head dimension $D$, storing the K and V tensors for one token costs $2 \times L \times H \times D \times \text{dtype\_size}$ bytes. Concretely, for a 13B-parameter LLaMA-style model (40 layers, 5120 hidden dimension, FP16), that’s roughly $2 \times 40 \times 5120 \times 2\,\text{B} \approx 0.8$ MB per token. At a 32K-token context, the KV cache alone exceeds 25 GB — larger than the model weights themselves for many serving configurations. Because GPU HBM is finite and every concurrently-served request needs its own KV cache, how efficiently you pack this memory directly determines how many requests you can serve at once (concurrency) and how long a context each request can afford (context length). This is why KV cache management, rather than raw compute, is usually the binding constraint on LLM serving throughput.

PagedAttention: block-based KV memory management. vLLM’s PagedAttention (2023) borrowed the classic operating-systems idea of paged virtual memory: instead of allocating one large contiguous buffer per request (which suffers from external fragmentation — the classic problem where memory is free in aggregate but not in one contiguous chunk large enough for a new request), PagedAttention divides GPU memory into fixed-size blocks (typically 16 tokens each) and maintains a block table per request that maps logical block positions in the sequence to physical block locations in GPU memory, which need not be contiguous. This is exactly analogous to how an OS page table maps virtual addresses to physical page frames. The benefits: blocks can be allocated on demand as a sequence grows, non-contiguous physical placement removes external fragmentation, and identical block contents (e.g., a shared system prompt prefix) can be referenced by multiple requests without duplication (“prefix caching”). PagedAttention’s guarantee, though, is at block granularity — it can allocate and free whole blocks efficiently, but it has no native concept of “this one token inside an otherwise-occupied block is now garbage.”

Token-level eviction algorithms. A separate line of work asks a different question: given a token’s position and its observed attention pattern, is it still useful to keep around at all? H2O (“Heavy-Hitter Oracle”) tracks a running cumulative attention score per token and retains only the highest-scoring “heavy hitters,” discarding the rest — reported to cut cache size by up to 50% with limited perplexity increase. StreamingLLM observes that a handful of initial tokens (“attention sinks”) receive disproportionate attention regardless of content, and keeps those plus a recent sliding window, discarding everything in between. Scissorhands and FastGen propose more refined criteria based on sparse attention patterns and per-head token roles. Random eviction, used in this paper as a stress-test baseline, discards tokens uniformly at random to hit a memory budget — useful precisely because it scatters retained tokens unpredictably across blocks, which is the worst case for block-granular reclamation. What every one of these policies has in common: the decision unit is a token, not a block.

Why “just shrink the block size” doesn’t work. The obvious first instinct on hearing “granularity mismatch” is: why not just make blocks smaller — say, 4 tokens instead of 16 — so less gets trapped per block? The paper’s answer, backed by prior systems experience, is that this trades one problem for a worse one. Smaller blocks mean more blocks per sequence, which means more metadata (each block needs a table entry), more address-translation overhead per attention step, and — critically for a GPU workload — more small, non-contiguous memory transfers whenever data needs to move (attention reads, KV copies, or offloading to CPU/disk). GPU memory subsystems are heavily optimized for large, coalesced accesses; shrinking granularity to fight fragmentation directly attacks the assumption that makes GPU memory access fast in the first place. At the other extreme, per-token allocation (no blocking at all) is impractical because GPU memory allocators have a minimum practical granularity and per-token bookkeeping would dwarf the data itself. vToken’s premise is that neither extreme is necessary: keep the block-based physical substrate exactly as-is, and add a thin logical layer on top that exposes token-granularity semantics without touching the physical allocation granularity.

2. Quantifying the mismatch before proposing a fix

Before presenting any design, the paper spends a full section establishing that this problem is real and large, which is the right instinct for a systems paper — a virtualization layer is only worth its added complexity if the mismatch it fixes is actually costing meaningful memory.

Formalizing “waste.” For a physical block $b$ with capacity $S$ tokens, let $n_b$ be the number of valid (non-evicted) tokens currently stored in it, and define block utilization as $u_b = n_b / S$. Given $N$ allocated blocks, the paper defines the intra-block waste ratio:

$$F = 1 - \frac{\sum_{i=1}^{N} n_i}{N \cdot S} = 1 - \frac{1}{N}\sum_{i=1}^{N} u_i \tag{1}$$

Reading Eq. (1): the numerator $\sum_i n_i$ is the total number of live tokens actually stored across all allocated blocks; the denominator $N \cdot S$ is the total capacity of those same blocks. Their ratio is the fraction of allocated capacity that is actually being used, and $F$ is one minus that — the fraction that’s wasted. When token-level eviction runs without a virtualization layer, a token being marked evicted reduces $n_b$ for whichever block held it, but the block itself remains fully allocated (the allocator has no way to know part of it is now free), so $F$ climbs directly with eviction aggressiveness.

Measuring it. The paper runs Llama-3.1-8B on a 16K-token subset of ShareGPT and LongBench with batch size 16, integrated with an H2O-inspired eviction policy on vLLM, and measures the fraction of allocated blocks sitting at $\leq 50\%$ utilization.

Figure 1 (paper Fig. 1): across all three eviction policies and both workloads, 56-67% of allocated blocks sit at or below 50% utilization. Random eviction is consistently the worst offender (58% on ShareGPT, 67% on LongBench) precisely because it scatters surviving tokens unpredictably, maximizing the chance that any given block has some live token blocking its release — this is the paper’s own stress test of the mismatch, and it behaves exactly as the granularity-mismatch theory predicts.

The takeaway the authors draw, and one worth sitting with: the loss here is not coming from the eviction policy being bad at deciding what to keep. The policies are doing their job — reducing the logical amount of KV data that needs to survive. The loss is a pure runtime-abstraction failure: there is no mechanism translating “this token is dead” into “this physical memory is free.” That reframing is what motivates treating the fix as an added virtualization layer rather than a smarter eviction algorithm.

The second cost: integration friction. Beyond wasted memory, the paper flags a second, more human cost. Without a virtualization layer, wiring a new eviction algorithm into vLLM requires the policy implementer to understand block-manager internals, translate token-level retention decisions into block-level actions, and manually keep attention slot mappings consistent with whichever tokens survive. The paper reports that a direct H2O integration into vLLM without vToken required modifying over 500 lines of code across multiple core modules, with nontrivial additional debugging to get memory-safety right — and every additional policy (StreamingLLM, Scissorhands, …) requires comparable fresh effort, because none of that plumbing is reusable across policies. This is the kind of cost that doesn’t show up in a benchmark chart but that determines whether a lab’s clever new eviction idea ever actually ships in a production serving stack.

3. vToken’s design: a virtualization boundary between policy and physical memory

3.1 Design goals, and why a full token-granular allocator isn’t the answer either

The paper frames the design space with two “obvious” fixes it deliberately rejects, both already touched on above: a fully token-granular allocator (breaks PagedAttention’s kernel and metadata assumptions) and smaller blocks (redistributes the fragmentation/bandwidth tradeoff without eliminating it). vToken’s actual move is architectural, not algorithmic: keep the block-managed KV runtime completely intact — same PagedAttention kernels, same CUDA Graph compatibility, same block allocator — and insert a thin virtualization boundary between the eviction policy and that runtime.

The contract this boundary defines is deliberately asymmetric. Above the boundary, an eviction policy operates purely on logical token identities: it says “token 47 in request 3 is no longer needed” and never has to know, or care, which physical block token 47 currently lives in, whether that block can be freed, or when reclamation will actually happen. Below the boundary, the runtime owns the logical-to-physical mapping, refreshes the slot mappings that attention kernels read from, and independently decides when it’s worth paying the cost of physically repacking blocks. The crucial decoupling this buys: deciding a token is dead and reclaiming its physical memory become two separate events that can be deferred and batched — the runtime doesn’t have to eagerly compact memory the instant a token dies, which would be expensive; it can wait until fragmentation is bad enough that compaction is clearly worth it.

Maintaining this contract while decoding is actively happening (i.e., while attention kernels are reading the very memory you might want to relocate) raises three concrete challenges the design has to solve simultaneously:

• (C1) Dual-view consistency. A token can die independently of its neighbors in the same block, but a block can only be released once every live token that was in it has been relocated elsewhere or discarded. The runtime needs metadata that tracks both facts — per-token liveness and per-block occupancy — at once.
• (C2) Safe reclamation during live decoding. If you physically move a token’s KV entry from one block to another, the attention kernel’s slot mapping (which tells it exactly which physical memory address to read for each token) must be updated before the next attention kernel launch reads from the new location — but you can’t afford to add a global synchronization point to every single decoding step just to be safe, because that would tax every request, including ones with no relocation happening at all.
• (C3) Policy-neutral, amortized cost. H2O, StreamingLLM, and Random all need to share the same scheduler, block-manager, and worker-layout code — the indirection overhead must be something you pay only when reclamation is actually worth doing, not a constant tax on every decoding step regardless of whether any fragmentation exists yet.

vToken’s answer to all three, at a glance: a per-request token table provides the C1 metadata; a physical reclamation backend batches the relocation work in the background to satisfy C3 while driving the async copies needed for C2; and a small set of scheduler/worker hooks insert exactly the slot-mapping refresh and synchronization dependency C2 needs, without a global stall.

Figure 2 (paper Fig. 2): the overall system. Note the layering discipline in the diagram — “KV Eviction Policies” only ever talks to the “vToken Substrate” (Token Table + Reclamation Backend + Hooks), and the substrate is the only thing that talks to the unmodified “vLLM Block Runtime” (Block Manager + Scheduler + Physical KV Blocks) underneath. This is the architectural picture that makes vToken a reusable substrate: swapping H2O for Scissorhands only changes what calls the Policy API, not anything below it.

3.2 The token table: the central metadata structure

The token table, maintained per request, is what actually implements the C1 dual-view. For every logical token ID in a sequence, it records the token’s current physical location as a (block_id, offset) tuple, plus a liveness bit. Marking a token dead is purely a metadata write — no KV memory moves or gets freed at that instant. This is the key indirection: it separates deciding what to evict (the policy’s job) from maintaining the physical layout (the runtime’s job), and it’s what lets reclamation be deferred rather than happening synchronously on every eviction call.

Figure 3 (paper Fig. 3): a concrete worked example with two requests. Req 0’s logical sequence “Four score and seven” (4 tokens) maps, via its token table, to entries scattered across Block 5 (three of its four tokens: “Four”, “score”, “seven” — note token 2, “and”, has already been evicted, marked with a red ✗) and Block 0. Req 1’s sequence “Just have fun” similarly maps across Block 0 and Block 2. The diagram makes the mismatch visually obvious: Block 0 holds one live token from each of two different requests, and cannot be freed even though most of its capacity serves neither request fully.

The table exposes exactly three operations, two for policies and one internal to the reclamation backend:

• evict_token(req_id, token_id) — marks a token logically dead. Its KV entry may still physically exist, but attention slot mappings will no longer reference it, and the reclamation planner treats its space as dead.
• sync_new_tokens(req_id, block_ids, total_len) — registers newly generated tokens as the sequence grows; the scheduler passes the current block list and length, and the table assigns sequential logical IDs with their physical positions.
• apply_moves(req_id, moves) — called only by the reclamation backend after physical copies finish, atomically updating the affected token table entries to their new locations.

These three calls are deliberately block-agnostic from the policy’s perspective — a policy calling evict_token never learns which block held the token or whether that block became freeable as a result. This is what makes the substrate reusable: H2O, StreamingLLM, and Scissorhands all just call these same three functions with different token-selection logic behind them. The metadata cost is modest by design: $O(L)$ per sequence of length $L$ — one mapping entry and one liveness bit per token — independent of the number of layers, attention heads, or the actual size of the KV tensors those tokens correspond to. In the implementation, the canonical table lives on the CPU (simple, portable), with a GPU-resident lookup cache to keep the steady-state slot-translation path fast; the cache is appended-to on ordinary sequence growth and only fully rebuilt when a structural change (eviction, relocation) actually occurs.

3.3 The physical reclamation backend: turning logical holes into free blocks

The reclamation backend is where vToken actually earns its “reclaimable” name — it’s the component that converts the token table’s logical liveness bookkeeping into physically usable, freed blocks. Its concrete relocation mechanism in this implementation is lazy compaction: pack the surviving live tokens from several low-utilization blocks into fewer destination blocks, then return the now-empty source blocks to the allocator’s free pool. The backend runs this as four stages, shown end-to-end in Figure 4.

Figure 4 (paper Fig. 4, reproduced conceptually from Section 3.3): the backend (1) monitors fragmentation and plans which tokens should move where, (2) allocates a destination block and launches an asynchronous copy on a dedicated relocation CUDA stream while the move list is recorded, (3) once copies land, updates the token table so subsequent slot lookups reflect the new physical locations, and (4) refreshes slot mappings and frees the now-empty source blocks back to the allocator.

Stage 1 — reclamation eligibility. The backend maintains, per block, the count of currently-live tokens $n_b$ (updated incrementally whenever a token is evicted or a block is allocated/freed — no full-table scan needed), and derives the intra-block waste ratio $F$ from Eq. (1). A high $F$ signals that many blocks are underutilized system-wide. To avoid constantly re-checking, the planner amortizes these checks across multiple scheduling iterations rather than running on every single step.

Stage 2 — headroom-aware admission. Here’s a subtlety worth dwelling on: lazy compaction is out-of-place — you need a destination block available before you can start moving live tokens out of fragmented source blocks and freeing them. But if you wait until the free-block pool is completely empty before attempting reclamation, you’ve waited until exactly the moment reclamation is hardest to do safely. vToken’s fix is to reserve a small, bounded “evacuation headroom” of destination-block capacity within the same overall KV block budget used for request admission (it’s not extra memory on top — it’s carved out of the existing pool), and to attempt reclamation proactively once the global waste ratio $F$ exceeds a tunable threshold $\theta_F$ (the paper reports $\theta_F = 0.25$ as an empirically-tuned default) and the free-block count is nearing a low watermark. When headroom is tight, the scheduler applies admission backpressure — it prioritizes completing reclamation over admitting brand-new requests, rather than letting new admissions consume the last free blocks needed to make room for compaction.

Stage 3 — relocation planning. For each request under consideration, the backend selects eligible low-utilization source blocks (up to a configurable batch size $B$), computes how many live tokens $T_\text{live}$ they collectively contain, and only proceeds if the projected block count reduction is actually positive — i.e., if packing $T_\text{live}$ live tokens into $\lceil T_\text{live}/S \rceil$ destination blocks would free strictly more source blocks than it consumes as destinations. If the available headroom can’t supply enough destination blocks, the plan is deferred (or its candidate set shrunk) rather than forced through. The move list produced fills each destination block completely before moving to the next, preserving logical token order where possible (helping attention locality), and each move records a (token_id, src_block, src_offset, dst_block, dst_offset) tuple.

Stage 4 — stage-aware asynchronous copy. This is the part with the most systems-engineering nuance, because naively overlapping the relocation copy with decoding can make things worse, not better. A decode step has three distinct phases with different resource profiles: attention forward (HBM-bandwidth-bound — it’s constantly streaming KV data), FFN forward (compute-bound), and post-forward bookkeeping (sampling, scheduling — mostly CPU-side, low GPU utilization). If you launch the relocation copy at an arbitrary point during the step, it competes with the attention phase for scarce HBM bandwidth, which is exactly the resource attention itself is starved for — so a naive overlap attempt can slow down the very decoding step it’s supposed to be running alongside.

vToken’s fix is to deliberately schedule the copy to launch after the current step’s forward pass has already returned, on its own dedicated relocation CUDA stream. Because that step’s slot mappings were already built from the pre-relocation token table (before the move was even planned), the in-flight attention/FFN computation for the current step can’t be corrupted by a relocation that starts after it. The copy then runs concurrently with sampling, scheduling, and next-step preprocessing — phases that don’t touch the KV cache and so don’t fight the copy for HBM bandwidth. Before the next step’s forward pass launches, the worker inserts a lightweight GPU-side wait_event dependency on the relocation stream — if the copy already finished during the post-forward window (the common case), this is a no-op; if not, the next step’s kernel simply waits on the GPU side rather than stalling the CPU host thread. This is meaningfully cheaper than a host-side (CPU) synchronization barrier, because the CPU never blocks waiting for the GPU event — only the next GPU kernel does, and only if the copy genuinely hasn’t finished yet.

3.4 Slot mapping and scheduler integration

In vanilla vLLM, attention kernels read the KV cache through slots — linear indices computed directly as $\text{slot} = \text{block\_id} \times \text{block\_size} + \text{offset}$, where block_id and offset come straight from the block table. This direct formula is only valid because, without vToken, a token’s physical location never changes once assigned. vToken breaks that assumption (tokens can move during relocation), so the slot-mapping function has to be rewritten to consult the token table instead:

$$\text{slot} = \text{token\_table}[\text{token\_id}].\text{block\_id} \times S + \text{token\_table}[\text{token\_id}].\text{offset} \tag{2}$$

This indirection is performed once per token during input preparation (building the batch’s slot-mapping tensor before the attention kernel launches), not inside the attention kernel itself — so the attention kernel’s actual code is untouched; only the slot-mapping tensor it’s handed looks up the current, possibly-relocated location.

Three scheduler/worker hooks wire this into vLLM’s execution loop:

• Scheduler-side reservation hook — maintains the bounded evacuation headroom (Stage 2 of §3.3) before admitting new KV allocations, so headroom is never silently consumed by ordinary request admission.
• Worker-side reclamation hook — during the worker’s execution path, evaluates reclamation opportunities, launches async KV-copy operations for selected requests, and rewrites the affected logical layout metadata.
• Pre-attention synchronization hook — before attention reads KV entries that might have been relocated, inserts the stream-level dependency on the relocation event (the GPU-side wait_event from §3.3’s Stage 4) so that moved data is guaranteed visible before it’s consumed.

CUDA Graph compatibility. This deserves a moment because it’s easy to assume relocating memory would force you to abandon CUDA Graphs (which capture and replay a fixed sequence of GPU operations for lower launch overhead — a big deal for latency-sensitive decoding). vToken avoids this: the KV cache tensors themselves and the graph’s captured input buffers never move or change shape; only the contents of the mutable slot-mapping buffer are updated before each replay, based on the token table. Relocation copies run entirely outside the captured graph, on their own stream, with the event-dependency inserted before any graph replay that might touch relocated entries. So vToken preserves CUDA Graph execution by treating slot-mapping as dynamic input data to a fixed graph, rather than by bypassing or re-capturing graphs — a design choice that matters a lot in practice, since re-capturing CUDA Graphs is expensive and would eat into exactly the latency savings the whole system is trying to deliver.

3.5 Correctness invariants — what “safe while decoding” actually means here

Touching live KV memory in the middle of active decoding is the scariest part of this design, so it’s worth taking the paper’s four correctness invariants seriously rather than skimming them. They’re the precise, checkable claims that “vToken doesn’t corrupt your generation” reduces to.

• I1 (Token conservation). For every request, the set of active logical token IDs and their K/V tensor contents are preserved across every relocation event. A relocation may change a token’s physical (block, offset), but never its logical identity and never its actual cached value.
• I2 (Unique mapping). Every active logical token maps to exactly one physical (block, offset), and every occupied physical slot is claimed by at most one logical token — no aliasing, no double-writes. apply_moves enforces this by atomically clearing the source slot and writing the destination slot together, so there’s never a window where both source and destination claim to hold the live copy.
• I3 (Pre-attention visibility). A relocated KV entry is only ever read by attention after its copy has completed — enforced via the CUDA event + wait_event mechanism from §3.3/3.4, which replaces what would otherwise need to be a full GPU-wide synchronization barrier with a narrowly-scoped, stream-level dependency.
• I4 (Layout-aware planning). A relocation plan is only committed from a consistent snapshot of the affected requests’ block-list and liveness state, is never allowed to overlap an in-flight plan on the same request, and is rejected outright if the projected block count doesn’t strictly decrease (i.e., vToken refuses to do “reclamation” that wouldn’t actually free anything). Shared-prefix blocks are conservatively excluded from any plan (more on this in §6 below).

The paper is explicit about how each invariant is validated: I1 and I2 are checked online, for every single relocation event, during the actual experiments (hash-and-compare, described further in §5.8 below). I3 is treated as structural — it follows necessarily from the CUDA-event topology already established, and is asserted via unit tests rather than measured empirically. I4 is enforced procedurally by the planner’s own admission gates. This is a sensible division of labor: the invariants that are cheap to check continuously (I1, I2 — comparing hashes) are checked continuously; the one that’s a structural guarantee by construction (I3) is tested rather than measured on every run; and the one that’s an admission-time policy (I4) is enforced by construction in the planner’s logic.

Algorithm 1: the vToken policy-adapter procedure (reconstructed from Figure 6 and §3.2-3.4)

To make the moving pieces concrete as an actual step-by-step procedure — this is the paper’s Figure 6 turned into pseudocode with the accompanying prose folded in:

Algorithm 1: vToken per-request decode step with reclamation
Input:  request r, newly generated tokens B_new, current
        sequence length L, eviction policy P
Output: decoded token(s) for r, with reclamation applied
        opportunistically in the background

1.  SyncNewTokens(r, B_new, L)
        # shared adapter: register new tokens' logical IDs
        # and physical positions in the token table

2.  V <- P.SelectVictims(r)
        # policy hook: H2O scores tokens and picks lowest-
        # score victims; StreamingLLM picks tokens outside
        # the sink+window; Scissorhands picks low-
        # persistence tokens; Random samples uniformly

3.  for each token t in V:
        EvictToken(r, t)
        # shared adapter: mark t logically dead in the
        # token table; no physical memory touched yet

4.  S <- BuildSlotMapping(r)
        # shared runtime: for every live token, compute
        # slot = token_table[t].block_id * block_size
        #             + token_table[t].offset   (Eq. 2)

5.  ReclaimAsync(r)
        # shared runtime: check eligibility (Stage 1),
        # admit under headroom (Stage 2), plan moves
        # (Stage 3), launch async copy on relocation
        # stream after this step's forward returns
        # (Stage 4) -- does NOT block steps 6 below

6.  Decode(r, S)
        # worker: run attention/FFN using slot mapping S;
        # if a prior relocation's copy hasn't completed,
        # a GPU-side wait_event blocks only the attention
        # kernel launch that needs it, not the CPU host

Reading this against Figure 6’s own accounting of who implements each line is illuminating: lines 1, 3, 4, 5 are shared runtime code that every policy reuses unmodified; only line 2 (SelectVictims) is policy-specific. This is exactly the “1-2 files, <50 LOC” integration footprint the paper reports for a new policy, versus “4-6 files, 500+ LOC” for a block-native (non-vToken) integration — the entire token-table/slot-mapping/reclamation machinery is written once and shared across every current and future eviction policy, and a new policy author only has to write step 2.

The paper’s own Figure 6 renders this same division as a numbered procedure table (reproduced above as Algorithm 1) alongside a two-row integration-footprint comparison table; because the original Figure 6 is itself text/tabular rather than a chart, we’ve folded its content directly into the pseudocode and prose above rather than reproducing it as an image.

4. Evaluation: does virtualization actually convert into usable capacity?

The evaluation is organized around six explicit questions, which is a clean structure worth following directly: (1) does token-level eviction really leave capacity trapped in partially-live blocks (§5.2 in the paper); (2) does vToken improve the paired eviction frontier under identical token-level decisions (§5.3); (3) does it extend the active-KV capacity frontier under memory pressure (§5.4); (4) where does overhead/overlap cost come from (§5.5); (5) how sensitive is it to runtime parameters (§5.6); (6) does it stay correct and compatible with production features like prefix caching (§5.7-5.8)?

Setup. All experiments run on a single NVIDIA H100 (80GB). The main comparison uses Mistral-7B and Llama-3.1-8B on ShareGPT and LongBench, with a Qwen2.5-14B capacity-frontier check added separately. Three eviction policies (H2O, Scissorhands, Random) are tested against three system variants: Native vLLM (unmodified, full-retention, no eviction at all — the baseline representing “don’t evict anything”), Naive-Evict (applies the same token-level eviction decisions as vToken, but with vToken’s physical-reclamation backend disabled, so partially-live blocks stay allocated — this is the crucial ablation baseline, because any difference between Naive-Evict and vToken isolates purely the value of physical reclamation, holding the eviction decisions themselves fixed), and vToken (both token-table indirection and physical reclamation enabled).

4.1 Memory efficiency: does reclamation actually recover the trapped memory?

Figure 7 (paper Fig. 7) is the paired comparison that most directly answers “does the mechanism work.” Panel (a) shows vToken increasing average memory utilization by 21.88% on Llama-3.1-8B and 21.67% on Mistral-7B relative to Naive-Evict, consistently across policies and workloads — this isn’t a fluke tied to one model or prompt distribution. Panel (b), arguably the more operationally meaningful metric, shows vToken reducing retained blocks per request by 27.2%-72.3% relative to Naive-Evict. Retained-block-count is what actually determines admission headroom: fewer blocks tied up per request under the same total budget means more requests can be resident simultaneously. The two panels tell the same underlying story from different angles — Naive-Evict retains a block as long as it holds any live token, so token-level holes never become reusable space without vToken’s active compaction.

4.2 SLA-constrained throughput: does reclaimed capacity translate to serving performance?

Isolating a memory-efficiency win is nice, but the systems question that matters is whether it shows up in serving throughput under a realistic latency constraint. The paper defines an SLA threshold as $1.05\times$ the Naive-Evict p95 latency at a reference concurrency $C_\text{ref}=8$ (giving both variants an identical latency budget, with 5% slack for run-to-run noise), then does a closed-loop concurrency sweep.

Figure 8 (paper Fig. 8) shows vToken (red) sitting consistently above Naive-Evict (blue) in every throughput panel, and consistently below it in every p95-latency panel — the star ($C_\text{sel}$) marks the highest-throughput point that still satisfies the SLA. On Mistral-7B, vToken improves selected feasible throughput by 9.9%-37.3% and cuts p95 latency by 9.9%-27.5%; the same pattern holds on Llama-3.1-8B (18.9% average throughput gain, 14.7% average latency reduction), with the biggest gains concentrated under Random eviction — 33.3%-103.7% throughput improvement for Scissorhands and up to 37% for Random on Llama. The mechanistic explanation the paper gives is worth internalizing: Random and Scissorhands scatter surviving live tokens more unpredictably across physical blocks than H2O does (whose retained “heavy hitters” tend to cluster more structurally), so the fraction of memory Naive-Evict traps unreclaimed is worse for those policies — and correspondingly, vToken has more slack to recover. The gain is a frontier shift, not just “run at higher batch size”: $C_\text{sel}$ is not always the largest concurrency tested, confirming the improvement is really about reclaiming capacity that already existed logically after eviction, not about pushing more aggressive batching.

4.3 Capacity frontier under memory pressure: the headline result

This experiment asks the sharpest version of the systems question: under a fixed KV block budget, how many requests can actually stay resident simultaneously? Using Llama-3.1-8B, LongBench, H2O, and a 12K-token output length, the H100 exposes 5,427 usable KV blocks at gpu_mem_util=0.35 and 11,519 at 0.50. A fully-retained request in this setup needs 1,020 blocks, while the ideal packed footprint after H2O eviction is only 512 blocks — so there’s a roughly 2x gap between what full retention needs and what an ideally-compacted eviction result would need, and the whole question is how much of that gap each system variant actually captures.

Figure 9 (paper Fig. 9): both Native vLLM and Naive-Evict become infeasible (marked ×) beyond concurrency $C=5$ — Naive-Evict barely helps here because its retained tokens stay scattered across blocks that remain mostly allocated regardless. vToken, in contrast, remains feasible through $C=8$, a 60% increase in maximum feasible concurrency under the identical block budget, and its throughput at the new boundary ($C=8$) is close to its own peak at $C=5$ — i.e., it degrades gracefully rather than collapsing as it approaches its new limit.

Figure 10 (paper Fig. 10) explains the mechanism behind Figure 9’s frontier shift directly: it plots normalized KV-block demand against active concurrency for both gpu_mem_util settings. At 0.35, Native vLLM and Naive-Evict both hit the 100% budget line by $C=5$; vToken’s demand curve grows much more slowly, only crossing the line at $C=8$. At the larger 0.50 budget, the same relationship doubles the verified feasible concurrency from $C=11$ to $C=22$. A separate check on Qwen2.5-14B (a different model and scale entirely) shows the same qualitative 2x frontier extension (native/Naive-Evict fail at $C=4$; vToken remains feasible through $C=6$, failing only at $C=8$), which is the paper’s evidence that this isn’t an artifact specific to Llama-3.1-8B’s particular head/layer configuration.

4.4 Overhead and overlap: is the async design actually paying for itself?

The paper’s Figure 11 (a three-panel overhead/overlap breakdown) is reported here in prose rather than reproduced as an image, since our figure budget is concentrated on the architecture, mechanism, and headline capacity-frontier results above; the key numbers are unpacked below. Two results here matter for judging whether this design is production-viable rather than just algorithmically clever. First, an indirection-only ablation — installing vToken’s hooks but disabling actual eviction/reclamation, so the only cost measured is the steady-state slot-table lookup path — shows throughput and p95 latency changing by less than 1.0% relative to unmodified Native vLLM at both $C=16$ and $C=48$. This is an important negative result: it means the overhead vToken does incur comes entirely from the pressure-activated reclamation machinery, not from a constant tax paid by every request regardless of whether reclamation ever triggers. Second, a force-synchronization ablation (removing the async design and forcing an explicit CPU-side wait for every relocation copy) confirms the value of the async design directly: the normal async path shows relocation copies with no explicit synchronization stall (the copy stays pending across multiple decode steps, overlapping cheaply with other work), while the force-sync ablation exposes real CPU blocking per relocation event. Under this stress test, async reclamation improves both throughput and decode p95 over Naive-Evict at both tested concurrencies, while staying close to (though not quite matching) the theoretical force-sync-without-explicit-waits baseline — the paper is careful to frame this as a stress test of the overlap mechanism, not the steady-state cost at typical operating points, since reclamation triggers far less often once a system is near its capacity frontier than in this deliberately-stressed measurement.

4.5 Sensitivity to runtime parameters

A one-factor-at-a-time sweep over block size, eviction ratio, and the fragmentation threshold $\theta_F$ under H2O shows: block size — vToken’s default of 16 (the minimum vLLM’s allocator supports) achieves the best throughput/latency tradeoff, with larger sizes (32, 48) trading away reclaimable capacity for worse performance, confirming that simply enlarging blocks is not a substitute for token-level reclamation; eviction ratio — as the ratio sweeps from 0.3 to 0.7, retained KV capacity drops substantially while throughput improves and latency drops, showing vToken can convert more aggressive eviction directly into reclaimed capacity (though the paper is careful to note that choosing an accuracy-preserving eviction ratio remains the eviction policy’s responsibility, not vToken’s); fragmentation threshold $\theta_F$ — this is the least impactful of the three, with the tested range showing only mild effects on capacity and latency, meaning vToken doesn’t require delicate trigger-threshold tuning to work reasonably well.

4.6 Prefix-cache compatibility and generation-quality validation

Two final checks matter for anyone actually considering deploying this. Prefix caching: vToken’s current implementation conservatively excludes shared-prefix blocks from relocation (to avoid corrupting data multiple requests depend on) while keeping private per-request suffix blocks eligible. Tested with an 8K-token shared prefix + 8K private suffix at sharing degrees 1, 2, 4, 8: for degrees $\geq 2$, all shared-prefix candidates are correctly skipped and all consistency checks pass, and relative to Naive-Evict-with-prefix-caching, vToken still reduces retained blocks by 28.6%-42.2%, with gains coming entirely from private-suffix reclamation (both variants get the same prefix-caching hit rate). Correctness and generation stability: the paper hashes the ordered set of retained token IDs plus their K/V tensor contents before and after every relocation event across all evaluated workloads/policies, and reports these checks holding for every single event (validating invariants I1/I2 empirically, not just by construction). Separately, on a paired 144-generation comparison (Llama-3.1-8B, ShareGPT, deterministic decoding), mean ROUGE-L F1 difference between vToken and Naive-Evict is only $-0.0016$, with 93.1% of pairs differing by at most 0.01, and median output-length ratio of 0.99 — indicating vToken’s indirection and relocation introduce no measurable quality drift beyond whatever the underlying eviction policy already contributes.

5. Design-choice discussion: alternatives, tradeoffs, and where they break

Why lazy compaction instead of, say, immediate eager compaction on every eviction? The obvious alternative to “batch and defer” reclamation would be to compact a block the instant it drops below some utilization threshold. This would keep fragmentation permanently lower but at the cost of constant background copy traffic — every eviction call could potentially trigger a compaction, competing for HBM bandwidth continuously rather than only when the global waste ratio $F$ crosses $\theta_F$. vToken’s threshold-gated, batched approach trades a bounded amount of “stale” fragmentation (memory that’s technically reclaimable but hasn’t been compacted yet) for dramatically lower background copy traffic. The boundary condition: if a workload’s eviction rate is bursty (long stretches of no eviction, then sudden heavy eviction), the threshold-based trigger could lag behind a sudden fragmentation spike, briefly under-reclaiming exactly when memory pressure is highest — the paper’s $\theta_F=0.25$ default is empirically tuned for the tested workloads, and there’s no adaptive mechanism described for detecting and reacting faster to a fragmentation spike.

Why a CPU-resident canonical token table rather than keeping everything GPU-resident? Keeping the canonical table on the CPU is simpler to implement correctly (host-side data structures are easier to reason about and debug than GPU-resident ones) and keeps compatibility with existing vLLM scheduler code, which already runs primarily on the CPU. The tradeoff is that every steady-state slot-mapping computation needs to consult a GPU-resident cache of the CPU table rather than the canonical table directly, adding a synchronization surface between the two copies that must be kept consistent (refreshed on structural changes). An alternative fully-GPU-resident table would avoid this cache-consistency concern but would complicate every host-side scheduling decision that currently reasons about token liveness — the paper’s choice optimizes for keeping the scheduler simple at the cost of a small cache-refresh mechanism on the worker side.

Why exclude shared-prefix blocks from relocation entirely, rather than using copy-on-write? The conservative choice — never relocate a block that’s shared across multiple requests via prefix caching — sacrifices some potential reclamation (private-suffix-only reclamation captures less benefit than being able to compact shared blocks too, especially at high sharing degrees where most of a request’s KV footprint could be the shared prefix). The paper explicitly names copy-on-write as the natural extension: relocate a shared block only when the expected reclamation benefit clearly justifies the extra copy cost of duplicating it first. The current design accepts a real, quantifiable ceiling on reclaimable capacity in exchange for a much simpler correctness argument — no risk of one request’s compaction silently corrupting another request’s view of a block it still depends on.

6. The deadlock-safety argument this design implicitly assumes (paper’s discussion, made explicit)

This paper is primarily about the token table and reclamation backend, but reading between the lines of §3.3-3.4, the async copy design also implicitly assumes something about GPU scheduling that’s worth spelling out because it’s the kind of assumption that silently breaks in adjacent deployment scenarios. The wait_event-based dependency in Stage 4 assumes the relocation stream’s copy operation and the next attention kernel are both scheduled promptly by the GPU driver — if the relocation copy were somehow queued behind a large backlog of other unrelated kernel work on the same device (a realistic scenario in a multi-tenant serving node running several models or request streams concurrently on shared SMs), the wait_event could stall longer than the paper’s steady-state overhead numbers suggest, since those numbers were measured on an otherwise-idle H100 dedicated to this single evaluation. This isn’t described as a correctness risk (the design remains deadlock-free regardless of scheduling delay, because nothing here uses busy-wait spinning across independently-scheduled blocks the way some competing designs do — vToken’s dependency is a proper CUDA-event wait, not a spin loop), but it is a latency-predictability risk worth flagging for anyone deploying this alongside other GPU workloads rather than in an isolated benchmark environment.

7. Limitations, as the paper itself acknowledges

The paper is candid about several scope boundaries. The prototype targets the single-node, single-GPU decoding fast path specifically, deliberately isolating the token/block granularity mismatch from distributed scheduling or cross-device KV movement — tensor-parallel deployments, where each TP shard has its own independent KV block pool, would need token-table indirection and reclamation to operate per-shard, with cross-shard coordination remaining the responsibility of the existing scheduler (an extension direction the paper names but doesn’t implement or evaluate). Shared-prefix blocks are handled conservatively (excluded from relocation, as discussed above) rather than via copy-on-write. The evaluation covers MHA-style attention implicitly through the tested models but the paper argues (without a dedicated MoE-serving-scale experiment) that GQA and MQA variants only change the physical KV tensor shape, not token identity or slot-remapping semantics — a reasonable claim architecturally, but one the paper doesn’t empirically stress-test at the scale where head-count/shard-size ratios might interact with the reclamation planner’s assumptions differently. The vLLM version underlying the prototype requires a minimum block size of 16, which is why the block-size sensitivity sweep (§4.5 above) is restricted to $\geq 16$-token blocks — smaller-block configurations that might interact differently with the reclamation design are untested.

8. Critical analysis

Weaknesses and flaws specific to this paper. First, every quantitative result in the evaluation comes from a single hardware configuration — one NVIDIA H100 — and the paper reports no measurements at all on other GPU generations, on multi-GPU tensor-parallel setups, or under any form of resource contention from co-located workloads; given that the deadlock-safety and overlap arguments both implicitly rely on assumptions about how promptly the GPU scheduler dispatches the relocation stream (discussed in §6 above), the absence of any contended or multi-tenant measurement is a real gap for a systems paper whose central pitch is production deployability. Second, the paper reports no variance or confidence intervals across repeated runs for any of its headline percentage improvements (21.88% memory utilization gain, 27.2%-72.3% block reduction, 9.9%-103.7% throughput range) — for numbers spanning as wide a range as “9.9% to 103.7%,” and derived from GPU benchmarks that are known to have meaningful run-to-run variance from thermal state and scheduling jitter, the absence of error bars or repeated-trial statistics makes it hard to judge how much of the wide range reflects genuine policy-dependent behavior versus measurement noise. Third, the fragmentation-threshold sensitivity analysis (§4.5) tests $\theta_F \in \{0.20, 0.25, 0.35\}$ — a fairly narrow band around the chosen default of 0.25 — and doesn’t explore what happens at the extremes (a near-zero threshold that reclaims almost continuously, or a near-1.0 threshold that essentially never triggers), which would more clearly bound the actual sensitivity of the design to this parameter rather than just confirming it’s not overly sensitive within a narrow, already-reasonable range.

Limitations the authors understate or omit. The paper’s headline capacity-frontier numbers (§4.3) are measured using a single, fixed eviction ratio implied by the H2O configuration used — but real deployments would need to choose an eviction ratio that trades off generation quality against memory savings, and the paper doesn’t discuss how sensitive the capacity-frontier gains are to that choice, beyond the separate (and narrower) eviction-ratio sweep in §4.5 which measures throughput/latency, not the capacity-frontier metric specifically. The paper is also notably silent on the CPU-side cost of maintaining the token table itself at scale — while the per-sequence $O(L)$ metadata footprint is quantified as negligible in raw bytes, the paper doesn’t report the CPU-side compute cost of the scheduler-side bookkeeping (updating per-block liveness counts, running eligibility checks, planning relocations) as concurrency scales into the dozens-to-hundreds of simultaneously-tracked requests that a production multi-tenant serving cluster would actually run, as opposed to the tested concurrencies (peaking around $C=48$ in the overhead experiments, $C=22$-32 elsewhere) that remain modest by production standards. Finally, the persistent risk that other concurrent GPU work could delay the relocation stream’s completion (discussed in §6) is not measured anywhere in the paper’s evaluation, even though it’s directly relevant to whether the reported <1% steady-state overhead and the overlap-mechanism stress test generalize to a real multi-tenant serving node rather than a dedicated benchmark GPU.

Concrete, specific improvement suggestions. (1) Report variance/confidence intervals (e.g., across at least 3-5 repeated runs) for the headline throughput, latency, and memory-utilization numbers, particularly given how wide some of the reported ranges already are. (2) Extend the sensitivity analysis on $\theta_F$ to a wider range (e.g., 0.05 to 0.90) to properly characterize the tuning surface rather than only probing near the chosen default. (3) Add at least one experiment measuring vToken’s behavior under GPU resource contention — for instance, co-locating an unrelated CUDA workload on the same device to see whether the relocation stream’s completion latency (and therefore the wait_event stall risk) degrades meaningfully, since this is the most direct threat to the paper’s near-zero steady-state overhead claim generalizing beyond a dedicated benchmark environment. (4) Report CPU-side scheduler overhead (not just GPU-side kernel overhead) as a function of concurrently-tracked request count, scaling well beyond the tested $C\leq 48$, since production multi-tenant deployments commonly track hundreds of concurrent sequences and the token-table bookkeeping cost per scheduling iteration could plausibly become non-negligible at that scale even if it’s clearly negligible at the tested scale.

9. Reproducibility notes

The paper specifies its prototype stack precisely enough to reproduce in spirit: vLLM v0.18.0 with PyTorch v2.10.0, evaluated on a single NVIDIA H100 (80GB). The three added components — TokenTable, ReclamationManager, and CUDACopyEngine — are named explicitly, which gives a concrete target for anyone attempting an independent re-implementation, though the paper (as is common for a systems paper of this length) doesn’t include a public code release link in the text reviewed here. The evaluated models (Mistral-7B, Llama-3.1-8B, and the additional Qwen2.5-14B capacity check) are all openly available checkpoints, and the workloads (ShareGPT, LongBench) are standard, publicly available datasets, so the experimental setup itself is fully reconstructable even without the exact prototype code. What is not fully specified is the precise CUDA/driver version pinning, the specific occupancy/threshold parameters used per experiment beyond the headline $\theta_F=0.25$ default, and the exact profiling harness used to produce the overhead breakdown in §4.4 — a reader wanting to exactly reproduce the reported percentage improvements would need to reconstruct these from the vLLM integration described, or reach out to the authors directly.

10. What this means if you’re building or operating a PagedAttention-based serving stack

If you’re already running token-level KV eviction (H2O, StreamingLLM, or a custom policy) on a PagedAttention-based serving system, the paper’s §2 characterization is worth checking against your own deployment independent of whether you adopt vToken specifically: measure what fraction of your allocated KV blocks sit below 50% utilization after eviction runs. If that number is anywhere near the 56-67% this paper measures, you are very likely leaving a large, currently-invisible chunk of GPU memory on the table — memory your eviction policy has already logically freed but that your block manager has no way to know about. vToken’s core idea generalizes beyond this specific implementation: any block-granular memory manager sitting underneath a token- (or more generally, sub-block-)granular liveness decision is a candidate for the same virtualization-boundary treatment — decouple “deciding something is dead” from “reclaiming its physical memory,” defer the latter, and batch it opportunistically behind independent computation. That’s a pattern worth keeping in your back pocket well beyond RMSNorm-adjacent normalization tricks or this specific KV-cache use case.