KV 驱逐策略

为什么需要驱逐？

• KV Cache 显存有限，高并发 + 长上下文时必然超出容量

• 驱逐 = 从缓存中移除某些条目以腾出空间

• 好的驱逐策略：最小化重算开销 + 保证公平性 + 控制抖动

策略总览

策略	原理	优点	缺点
LRU	最久未访问者淘汰	简单、适合时间局部性	热点漂移时反应慢
LFU	访问次数最少者淘汰	保留稳定热点	新条目易被误杀
注意力感知	按注意力分数排序	语义相关性高	需要额外计算 attention score
H2O	Heavy-Hitter + Recent	只保留高注意力 + 最近 token	参数选择需调优
SnapKV	观察窗口选重要 token	压缩率高	需要额外 prefill 分析步
Fair/配额	按租户配额限制	多租户公平	全局命中率可能不是最优

LRU 实现要点

victim = argmin_{entry} entry.last_access_step

• 块级 LRU：以 block（而非 token）为驱逐粒度

• 实现：双向链表 + 哈希表 → O(1) 访问和驱逐

• 适合：前缀缓存场景（最近用过的前缀最可能被复用）

LFU 实现要点

victim = argmin_{entry} (entry.use_count, entry.last_access_step)

• tie-break 用 LRU（同频率时淘汰最旧的）

• 适合：热点稳定的场景（同一 system prompt 反复使用）

• 风险：新加入的条目 use_count=1 容易被立刻驱逐

注意力感知驱逐

• H2O：保留 heavy-hitter token（累积注意力分数 top-k）+ 最近 W 个 token

• 粒度更细（token 级而非序列级），但实现更复杂

多租户公平驱逐

• 每个租户有配额（按权重分配总块数）

• 驱逐时优先淘汰超配租户中最旧的条目

• 配额超出时退化为 LRU

• 公平性指标：Jain fairness index = (Σx)² / (n·Σx²)

驱逐抖动（Thrashing）

• 现象：频繁驱逐后立即又需要被驱逐的数据 → 反复重算

• 检测：短时间内同一 prefix 多次被驱逐

• 缓解：① 保留最小工作集不驱逐；② 增加容量；③ 冷却期

面试一句话

• "驱逐策略核心是在命中率、公平性和抖动之间做权衡。线上通常用 LRU 做 baseline，再叠加注意力感知或租户配额做增强。"