arXiv’26 | vToken：KV Cache 淘汰后，为什么显存还是回收不回来？

原文：vToken: Token-Level Virtualization for Reclaimable KV Caches

1. 先说一个很容易被忽略的浪费

长上下文 LLM 推理里，KV Cache 的大小会随着上下文长度和并发请求一起涨。大家很自然会想到：既然历史 token 的重要性不一样，那就把不重要的 token 淘汰掉，只留下 attention 真正会用到的部分。

这个方向已经有不少工作了。H2O（Heavy-Hitter Oracle）保留累计 attention 分数高的 token，StreamingLLM 保留 attention sink 加最近窗口，Scissorhands 则根据 token 在多步 attention 中的稳定性做筛选。算法层面都在回答同一个问题：哪些 token 可以删？

但把它们接到 vLLM 之后，事情会变得有点离谱：token 确实删掉了，GPU 显存却不一定回来。

原因是 vLLM 的 PagedAttention 把 KV Cache 按固定大小的 block 管理，典型配置是一个 block 放 16 个 token。假设某个 block 里 16 个 token 有 6 个被淘汰、10 个还活着，这个 block 仍然不能释放。那 6 个 token 对模型已经没用了，但它们占的物理空间也不能给别的请求用。

逻辑上已经释放，物理上还被占着。这就是 vToken 要解决的核心矛盾。

2. 背景：PagedAttention 解决了哪种 fragmentation

2.1 KV Cache 为什么会撑爆显存

KV Cache 是每一层 attention 的 Key 和 Value。生成新 token 时，模型不需要重新计算历史 token 的 K/V，直接读取缓存即可，所以 attention 的历史部分从“反复重算”变成“读取已有状态”。代价是这些状态要为每个请求、每个历史 token 保存在 GPU 上。

一个 token 的 KV 大小近似是：

\[M_{token}=2\times L\times H\times D\times \text{dtype\_size}\]

其中 $L$ 是 layer 数，$H$ 是 KV head 数，$D$ 是 head dimension，乘 2 是 K 和 V 各一份。论文用一个 13B LLaMA 作为例子：40 层、hidden size 5120、FP16 下，一个 token 的 KV 约 0.8 MB；32K context 单请求就超过 25 GB。模型权重还没算，显存已经先被“记忆”吃掉了。

2.2 PagedAttention 的 block 视角

PagedAttention 借鉴操作系统虚拟内存：逻辑上的连续 token 序列不必放在连续物理显存里，而是通过 block table 映射到一组不连续的物理 block。这样做主要解决两件事：减少 allocator 层面的外部 fragmentation，并支持 prefix sharing。

但它的管理接口天然是 block-level 的：申请 block、释放 block、给 attention kernel 提供 slot，都以 block 为单位。它并不知道“一个 block 里面有几个 token 其实已经死了”。

而 token eviction 关注的是另一套语义：token 级别的保留和淘汰。两边各自都合理，接在一起却缺了中间层。

3. 真正的问题不是淘汰策略，而是粒度错位

设一个物理 block 能放 $S$ 个 token，第 $b$ 个 block 里还有 $n_b$ 个有效 token。它的利用率是：

\[u_b=\frac{n_b}{S}\]

如果总共分配了 $N$ 个 block，那么 block 内部的 waste ratio 可以写成：

\[F=1-\frac{\sum_{b=1}^{N}n_b}{N\times S}=1-\frac{1}{N}\sum_{b=1}^{N}u_b\]

这个 $F$ 不是 allocator 统计的“外部碎片”，而是 block 已经拿到手之后，里面有多少位置因为 token 被淘汰而空着，却仍然不能复用。

论文在 Llama-3.1-8B、16K context、batch size 16 上做了一个很直接的实验。对 H2O、Random 和 Scissorhands 三种 token-level policy，ShareGPT 上低于 50% 利用率的 block 占比是 56%、58%、56%；LongBench 上是 58%、67%、57%。其中最深的 0–25% 利用率区间占了相当大一部分。

Token 淘汰后的低利用率 block

换句话说，token eviction 已经把逻辑 KV 需求压下去了，但 block runtime 只能看到“这个 block 里还有一个活 token”，于是整块显存继续被占用。论文报告的 intra-block waste ratio 达到 40%–60%。这不是一个边角 case，而是 token 被分散在不同 block 时的必然结果。

3.1 为什么不能简单把 block 改小

有人可能会说：既然一个 block 里塞 16 个 token 会浪费，那改成 4 个甚至 1 个不就行了？

问题在于 block size 不是免费的。block 越小，metadata 越多，逻辑到物理的映射更复杂，KV copy 和 attention 需要处理更多不连续的小块，带宽效率也会下降。反过来，如果真的按 token 单独向 GPU allocator 申请，元数据和分配开销又会把系统拖回另一种极端。

所以需要的不是“把 block 改成 token”，而是保留 block 的物理效率，同时在上层暴露 token-level 的逻辑语义。

4. vToken：给 block runtime 加一层虚拟化

vToken 的核心不是提出一种新的 token importance score。它做的是在 eviction policy 和 PagedAttention 之间插入一个 token-level virtualization layer：

policy 只负责说哪些 logical token 不再需要；
vToken 维护 token 的逻辑地址和生存状态；
reclamation backend 再决定什么时候搬、搬到哪里、哪些物理 block 可以真正释放。

如下图，vToken substrate 上接各种 KV eviction policy，下接 vLLM 原来的 Block Manager 和 Scheduler。attention kernel 本身不需要改成 token allocator。

vToken 系统分层

这层边界解决了三个问题：

Dual-view consistency：同一个 token 同时有逻辑身份和物理位置，淘汰不会马上破坏物理布局。
Safe reclamation：token 搬家时，slot mapping 和 CUDA stream 依赖能保持一致。
Policy-neutral integration：H2O、Random、Scissorhands 复用同一套 runtime，不需要各自侵入 block manager。

5. Token table：逻辑 token 和物理 slot 之间的页表

vToken 的中心数据结构是 per-sequence token table。每个 logical token ID 记录：

token_id -> (physical block id, offset, live/dead)

它维护的是“这个 token 现在在哪”，而不是“这个 block 现在属于谁”。比如请求中的 token 0、1、3 原来在物理 block 5 的 offset 0、1、3；另一个请求的 token 1、2 可能在 block 0 和 block 2。逻辑序列仍然连续，物理存储可以完全不连续。

Token table 如何映射逻辑地址

上层 policy 只需要三个接口：

evict_token(req_id, token_id)：把 token 标记为逻辑 inactive，不立即搬数据；
sync_new_tokens(req_id, block_ids, total_len)：注册新生成 token 的物理位置；
apply_moves(req_id, moves)：后台搬迁完成后，原子更新 token 的新位置。

举个具体的 slot 计算例子。假设 block size $S=16$，token table 记录 token 42 在物理 block 12、offset 3，那么 attention 需要的 slot 是：

\[slot=12\times16+3=195\]

如果后台把它搬到 block 20、offset 1，逻辑 token ID 42 不变，但下一轮 input preparation 会根据新表计算出 $20\times16+1=321$。这个 indirection 在 attention kernel 之外完成，kernel 继续接收熟悉的 slot mapping。

因此，evict token 和 free block 被明确拆成两个时间点：先改变逻辑可见性，后在合适的时机重排物理布局。

6. 物理回收：不是 compact 一下就完事

6.1 什么时候值得搬

vToken 没有每一步都扫描整张 token table，而是增量维护每个 block 的 live-token 数量。当全局 waste ratio $F$ 超过阈值、free block 接近 low watermark，同时存在足够多低利用率 block 时，才触发 planner。

论文默认 fragmentation threshold 是 0.25。阈值太低，系统会频繁搬家；阈值太高，显存碎片积累得更严重。更重要的是，out-of-place relocation 需要先申请 destination block：如果等 free list 完全空了才开始回收，正好会陷入“没有空间搬，所以永远回收不了”的死结。

所以 scheduler 在同一个 KV block budget 内预留 bounded evacuation headroom。这不是额外显存，而是暂时留给搬迁目的地的工作空间。只有预计释放的 source block 数量严格大于 destination block 数量，计划才会被接受。

如果选中的 source blocks 一共有 $T_{live}$ 个活 token，每个 block 容量是 $S$，需要的目的 block 数量就是：

\[N_{dst}=\left\lceil\frac{T_{live}}{S}\right\rceil\]

例如 5 个碎片 block 里总共还活着 31 个 token，$S=16$，搬到 2 个新 block 后可以释放 3 个旧 block；这次 relocation 才是“赚的”。如果搬 3 个目的 block 只能释放 2 个 source block，planner 直接放弃。

6.2 三阶段搬迁流程

物理回收大致分三步：先扫描低利用率 source block 并生成 move list；再把活 token 按顺序搬到 packed destination block；最后提交 token table、刷新 slot mapping、归还空 source block。

物理回收的三阶段流程

注意这里维护的是 token 的逻辑顺序，而不是简单 memcpy 整个 block。move list 会记录每个 token 的 source (block, offset) 和 destination (block, offset)，这样搬迁之后 token table 仍然能逐项更新。

7. 关键工程细节：copy 不能和 attention 抢 HBM

最容易写成一句“异步 copy”的地方，恰恰是 vToken 最有工程味的地方。

一个 decode step 大致有三类阶段：attention forward 读 KV、FFN forward 更偏 compute-bound、post-forward 做 sampling 和 scheduler 逻辑。若把 KV copy 从 step 开始就和 attention 重叠，两者会同时争抢 HBM 带宽，结果是 attention 被 copy 拖慢。

vToken 的 stage-aware async copy 做法是：

当前 step 的 attention/FFN 先使用旧的 slot mapping 完成 forward；
forward 返回后，在独立 relocation stream 上启动 KV copy；
copy 与 sampling、调度和下一轮输入准备重叠，这些阶段不会读取 KV；
下一轮 attention 前，只在确实需要时通过 CUDA event wait_event 等待 copy 完成。

Stage-aware asynchronous copy

这里的关键不是“完全没有同步”，而是把 host blocking 换成 GPU stream dependency。CPU 不需要停下来等 copy，下一次 attention 只对相关 relocation 建立依赖。论文还保留了 CUDA Graph：graph 里的 KV tensor 和 input buffer 不变，只在 replay 前更新可变的 slot-mapping buffer。

8. 对 eviction policy 的接入有多轻

vToken 把 policy adapter 固定成一个很短的流程：注册新 token，调用 policy 选 victim，逐个 evict_token，构造 slot mapping，异步回收，然后 decode。

Policy adapter 和集成开销

论文给出的 integration footprint 很直观：传统 block-native 接入需要改 4–6 个 scheduler/worker 文件、500+ 行代码；vToken 只需 1–2 个 adapter 文件、少于 50 行 policy-specific code。H2O 只实现“选择最低分 token”，Scissorhands 只实现“选择低 persistence token”，Random 只负责随机采样可淘汰 token，token table、slot remapping 和 reclamation 都是共享逻辑。

这也是我觉得这篇工作比“又一个 eviction heuristic”更有价值的地方：它把 policy 研究和 runtime 工程解耦了。以后出现新的 token importance 方法，不必重复踩 vLLM block manager 的坑（希望不要再回忆了…）。

9. 实验结果：回收的是被困住的容量

9.1 实验设置

原型基于 vLLM v0.18.0 和 PyTorch 2.10.0，运行在单张 80GB H100 上，主要模型是 Mistral-7B 和 Llama-3.1-8B，工作负载包括 ShareGPT 和 LongBench，另外用 Qwen2.5-14B 做容量 frontier 检查。对比三种 token eviction policy：H2O、Scissorhands、Random。

三个系统变体要分清：Native vLLM 是 full-retention baseline；Naive-Evict 使用同样的 token eviction 决策，但没有物理回收，所以碎片 block 继续占着；vToken 在相同 policy 和 memory budget 上打开 token table 与 physical reclamation。这个 paired comparison 很重要，否则很容易把 policy 的收益误算成 vToken 的收益。

9.2 memory utilization 和 retained blocks

vToken 在 Llama-3.1-8B 上平均提升 21.88% 的 memory utilization，在 Mistral-7B 上提升 21.67%。这里的 utilization 不是“GPU 显存用了多少”，而是已经分配的 KV block 里，有多少位置确实存着 retained token。

Token-level eviction 的内存利用率

右侧 retained blocks per request 更直接：Naive-Evict 由于 live token 分散在 partially live blocks 中，物理 block 数量仍然偏高；vToken 把这些 live token 重新 packed 后，空出来的 block 才能回到 allocator。

9.3 SLA frontier：吞吐不是盲目把 concurrency 拉高

论文没有只报一个峰值 throughput，而是给每个设置加了 p95 latency 约束。SLA 阈值设为 Naive-Evict 在参考并发 $C_{ref}=8$ 时 p95 的 1.05 倍，$C_{sel}$ 是满足 SLA 的最大吞吐点。

SLA 约束下的吞吐 frontier

在 Mistral-7B 上，vToken 在不同 workload-policy 组合下把 selected feasible throughput 提升 9.9%–37.3%，同时 p95 latency 降低 9.9%–27.5%。Llama-3.1-8B 上平均吞吐提升 18.9%，p95 降低 14.7%。Random 的收益通常更大，因为随机淘汰会把 live token 撒得更散；Scissorhands 的收益也很明显，在两个模型和 workload 上达到 33.3%–103.7% 的 throughput 提升。

这点要说清楚：vToken 不是让 attention kernel 突然快了一倍，而是把原本已经“逻辑上省出来”的容量真正变成 admission headroom，于是系统能在同一个 SLA 下接更多请求。

9.4 capacity frontier：同一块显存能塞下多少活请求

在 Llama-3.1-8B、gpu_mem_util=0.35 下，H100 有 5,427 个可用 KV blocks。Native vLLM 和 Naive-Evict 的可行并发边界是 $C=5$，vToken 把它推到 $C=8$，提升 60%。在 gpu_mem_util=0.50 下，边界从 $C=11$ 推到 $C=22$，直接翻倍。

Active-KV capacity frontier

为什么会出现这么大的差距？以 16-token block 为例，6 个完整保留的请求需要 6,120 blocks，超过 5,427 的池子；H2O 淘汰后理想 packed footprint 只需要 512 blocks，但 Naive-Evict 因为活 token 分散，实际需求仍然接近 full retention。vToken 做的就是把“512 blocks 的逻辑需求”逼近物理布局。

在 Qwen2.5-14B 的额外检查里，3,261 个 usable blocks 下，Native/Naive 的边界是 $C=3$，vToken 能到 $C=6$。这说明收益不只属于某个 8B 模型。

KV block demand 与容量预算

10. 开销、稳定性和边界

10.1 异步回收不是零成本

indirection-only ablation 显示，只安装 vToken hooks、不开 eviction 和 reclamation 时，吞吐和 p95 相对 Native vLLM 的变化小于 1%。真正的成本来自 pressure-activated planner 和 relocation backend，而不是每次 attention 都多查一次表。

论文把开销拆开后发现，CPU 侧主要是 planner 的 opportunity checks；KV copy 本身很短，但会和 decode 共享 GPU 资源。force-sync ablation 则会暴露每次 relocation 的 CPU blocking，异步路径通过 CUDA event 避免了显式同步等待。

Physical reclamation 的开销与重叠

所以 vToken 的“async”不是魔法：它消除的是同步 stall，不保证 copy 和 attention 没有 bandwidth contention。在更高压力下，copy/decode 争抢资源仍然可能出现。

10.2 正确性和 prefix cache

论文在线检查四个 invariant：token 不丢不重复、每个 live token 唯一映射、attention 只在 copy 完成后读取、规划基于一致的 block/liveness snapshot。所有 relocation event 都通过了 token/KV hash 校验。

在 144 条匹配生成上，vToken 相对 Naive-Evict 的 ROUGE-L F1 平均差是 -0.0016，93.1% 的样本差异不超过 0.01；输出长度比值中位数是 0.99，没有观察到系统性变长。

prefix cache 目前采取保守策略：shared-prefix block 不搬，只回收 private suffix。共享度为 2、4、8 时，shared blocks 全部跳过，retained block 减少 33.0%、32.3%、42.2%，吞吐分别提升 76.1%、97.2%、146.5%。注意这不是 prefix hit rate 的功劳，两边都启用了 prefix cache，收益来自 private suffix 的物理回收。

Prefix cache 兼容性

10.3 这篇工作的边界

第一，vToken 不是 eviction policy。H2O 如果淘汰错了 token，vToken 只会忠实地把错误的逻辑状态压紧，它不会替你恢复模型质量。eviction ratio 和 accuracy-preserving budget 仍然要由 policy 自己负责。

第二，当前原型聚焦 single-node、single-GPU decode fast path，一个 KV cache group，并且保守跳过 shared-prefix block。多 GPU、多个 KV group、跨设备搬运需要额外处理，但这与 vToken 解决的 granularity mismatch 是正交问题。

第三，回收需要 headroom。显存完全耗尽时，系统没有 destination block 可以搬，vToken 也救不了。因此它是一个 pressure-activated runtime extension，不是“显存满了再凭空变出空间”。Native vLLM 在没有内存压力时仍然是更简单的路径。

11. 我的 take：这是一层 runtime abstraction，不是又一个 cache trick

KV Cache 优化大致有三条轴：

表示层：quantization、compression，减少每个 KV 元素的字节数；
访问层：sparse attention、token eviction，减少要看的历史 token；
管理层：allocation、mapping、reclamation，决定省下来的空间能否被下一个请求使用。

很多工作把前两层做得很漂亮，但最后一层仍然用 block-level runtime，于是优化结果卡在“逻辑上省了，物理上没释放”。vToken 的贡献就是把管理层补上：token-level liveness 必须成为 serving runtime 的一等公民。

这和刚刚解读的 OasisKV 是两条不同路线。OasisKV 解决的是“KV 已经在远端，怎么预测并预取”；vToken 解决的是“KV 已经淘汰，为什么 block 还不能释放”。一个优化时间/空间层次之间的数据搬运，一个修复逻辑生命周期和物理布局之间的接口。以后真正的 serving system 很可能需要把两者组合起来：先用 token-level policy 控制保留集合，再用 vToken 把碎片回收，最后用分层存储和 prefetch 把剩下的 KV 搬到合适的位置。

12. 总结

如果只记住一句话：vToken 没有发明新的 token eviction，而是给 token eviction 补上了 block runtime 缺失的虚拟化层。

policy 负责回答“哪些 token 死了”，token table 负责记录“活 token 现在在哪”，reclamation backend 负责“什么时候把它们重新打包”，CUDA event 则负责“搬家时下一次 attention 不能读到半成品”。

这套设计把低利用率 block 中被困住的显存变成了真正可复用的 KV capacity，在相同 SLA 和 allocator budget 下提高并发和吞吐，同时把新 eviction policy 的接入成本从 500+ 行降到 50 行以内。说到底，KV Cache 优化的终点不是少存几个 token，而是让省下来的每一个 token 真正回到系统的 free list。

顺带一提，我们把 AutoML、NAS 和 LLM 压缩的相关积累整理成了《动手学 AutoML：从 NAS 到大语言模型优化实战》。这篇 vToken 讲的是 serving runtime 的内存管理，书里更偏模型和搜索层：第 8 章讨论 LLM 剪枝、量化和模型融合，第 11 章有 LLM 后训练剪枝实战。一个是在 runtime 里回收被浪费的空间，一个是在模型侧减少不必要的计算和参数，角度不同，但目标都是把有限资源用在真正影响结果的地方。