Prefix Caching：相同前缀，只算一次 prefill

先建立共同认知：KV 由前缀决定，重复计算本来可以避免；难的是在并发、分块和显存压力下安全地找到并留住可复用的块。

自回归模型在 prefill 阶段对 prompt 的每个 token 做一次前向，把每层的 K/V 写进 cache。 因果注意力决定了位置 i 的 K/V 只依赖 0..i 的 token，因此只要两条请求的开头是同一段 token， 这段前缀的 K/V 就是同一份数据；SGLang 论文 §3 把这一点写成「KV cache computation depends only on prefix tokens」。 重复计算这段前缀，不会改变结果，只会增加首 token 之前的计算量。

这种重复在真实负载里很常见。vLLM 文档列出两类典型场景： 用户拿同一份长文档（手册、年报）反复提问；或者多轮对话里每次都把完整聊天历史重新送进模型 （docs/features/automatic_prefix_caching.md:72-73）。前者共享文档正文，后者共享历史轮次。 前缀越长，重复 prefill 的绝对开销越大。

困难不在「知道可以复用」，而在「每次请求进来时，怎么知道哪一块可以复用、复用后怎么保证它不被提前释放」。 请求是交错到达的，块会被 eviction，共享同一块的多个请求随时可能有一个结束。 更麻烦的是粒度：KV 按块管理，前缀的末尾往往停在块中间，而块内只匹配一部分时，不能把整块 KV 当作已计算。

所以一个可用的实现至少要回答三个问题：内容如何映射到物理块；多个请求同时引用时如何计数；显存不够时按什么顺序淘汰。 后面的哈希、引用计数和空闲队列，都是围绕这三个问题展开的。

PagedAttention 把逻辑块映射到物理块，用引用计数和 CoW 管理共享；RadixAttention 把 token 序列放进 radix tree，用 LRU 叶子淘汰。vLLM V1 的 APC（Automatic Prefix Caching）是第三条：链式哈希 + 哈希表。

表 1 · 三种前缀共享实现的对照（页面整理；出处见各行）

三种实现都在做同一件事：把一段 token 前缀映射到可复用的 KV 单元。区别在索引结构——显式块表、radix tree、哈希表—— 以及淘汰时维护的元数据。页面不对三种方案做优劣排序；它们对负载、块大小和调度策略的假设不同。

记住三件事：哈希是链式的；只有满块有哈希；命中块靠引用计数活过本次请求，靠空闲队列的 LRU 顺序等待淘汰。

哈希的输入是三部分。父哈希 Hi−1 让相同内容出现在不同位置时得到不同键； 本块 token 元组降低碰撞概率；extrai 把 LoRA ID、多模态输入哈希、cache_salt 等 影响 KV 的因素并进键里（docs/design/prefix_caching.md:15-19）。 因此「哈希相同」不只表示 token 相同，还表示产生 KV 的条件相同。

BlockHash 是 bytes 类型（kv_cache_utils.py:51）。真正存进哈希表的键还会在末尾拼上 4 字节的 KV group id（make_block_hash_with_group_id，同文件 :64-73），这样同一段 token 在不同 KV cache group 里不会串键。 纯 full-attention 模型通常只有一个 group，可以把它理解成「块哈希 → 物理块」的一张表。

每个物理块由 KVCacheBlock 描述：不可变的 block_id、当前引用数 ref_cnt、 在块被缓存时赋值的 block_hash（本页主路径是满块），以及空闲队列用的前后指针 （kv_cache_utils.py:166-179；文档里的简化版在 docs/design/prefix_caching.md:106-119）。 请求侧则维护 block_hashes：前端会预计算 prompt 的哈希，Request 初始化时补上剩余部分， 后续输出 token 填满新块时继续追加（vllm/v1/request.py:238-243、:298-303）。

查找：从第一块开始，遇到第一个 miss 就停

调度器调用 get_computed_blocks()。命中长度先被限制在 prompt_length − 1： 即使所有 token 都缓存过，也要留最后一个 token 重算 logits（kv_cache_manager.py:318-324、 vllm/v1/request.py:354）。随后 find_longest_cache_hit() 按哈希顺序逐块查表； 某一块查不到就 break，因为父哈希链保证后面的块不可能单独命中 （single_type_kv_cache_manager.py:797-802）。纯 full-attention 路径上只有满块会进表，块内部分匹配不算命中 （docs/design/prefix_caching.md:22）。

共享与 PagedAttention 的关系

PagedAttention 提供的是地址转换：请求持有逻辑块表，表项指向物理块。APC 没有换掉这层转换， 它只是在物理块之上加了一张「内容哈希 → 块」的索引。命中时，请求的块表直接指向已经有 KV 的物理块， touch() 把 ref_cnt 加一（block_pool.py:774-790）；没有复制 KV。

与论文里的 CoW 路径相比，V1 的满块命中是只读共享。可写条件是「ref_cnt == 1 且块还没有哈希」 （block_pool.py:794-796）：一旦块变满并写入缓存，它就不再被修改。 因此 APC 的共享满块不需要 CoW；生成阶段要写入的是请求自己的尾块或新块。 论文 §4.4 给 shared prefix 的最后一块标记 CoW，是因为那里共享的块还可能被继续写； V1 只缓存满块，最后一块本来就不在共享范围里。

引用计数与 LRU：缓存块平时就住在空闲队列里

这是 vLLM V1 最容易看漏的一点：一个块被缓存后，即使当前没有请求使用它，它也不会被单独放进另一个「缓存池」。 它继续留在 block pool 里，ref_cnt 为 0 时挂在空闲队列上，同时哈希表仍然指向它。 主路径上，只有分配器从队头把它取走时，才会清掉哈希、完成驱逐（block_pool.py:681-715、:751-772）。

• 命中：touch() 在 ref_cnt == 0 时先把块移出空闲队列，再执行 ref_cnt += 1（block_pool.py:786-790）。计数大于 0 的块不在队列里，不会被分配。
• 释放：请求结束时 ref_cnt 递减；只有减到 0 的块才回到队列。带哈希的块进队尾，无哈希的块进队头（block_pool.py:824-837）。
• 淘汰：分配从队头取块；队头带哈希就先清哈希。队头是最近最少使用的缓存块，所以这是块级 LRU（docs/design/prefix_caching.md:204-208）。
• 顺序：请求释放时按逆序归还块，最后一个块（哈希覆盖 token 最多、后续最不可能被复用）最先进入队尾方向，因而更早被淘汰（docs/design/prefix_caching.md:198）。

工程上它很便宜：每满块一次哈希、每命中块一次字典探测。贵的是缓存占住的显存，以及块内无法复用的尾部。

块大小是这套机制的粒度税。V1 的代码默认块大小是 64 个 token （vllm/config/cache.py:185）。前缀尾部不足一个块的 token 不会进缓存，所以最坏情况下有 63 个 token 的共享前缀无法复用（64 − 1）。 块越大，哈希和查找次数越少，但尾部浪费越大；块越小，命中越细，但每块元数据和查找次数上升。 论文 §7.2 也指出：块太大增加内部碎片、降低共享概率，块太小则不利于 GPU 并行读取和处理 KV。

还有一笔固定开销：即使 prompt 全部命中，也要留最后一个 token 重算 logits（vllm/v1/request.py:354）。 由于 num_computed_tokens 要按块大小对齐，实际可能重算一整个块，而不是只重算一个 token （vllm/v1/core/kv_cache_manager.py:318-323）。这意味着「全部命中」也不等于零重算。

哈希算法本身也有取舍。默认是 sha256（vllm/config/cache.py:262），文档说明它用 Python pickle 序列化， 跨 Python / vLLM 版本不一定可复现；需要跨语言可复现时可选 sha256_cbor。 xxhash 更快，但不是加密哈希，理论上增加碰撞风险，多租户场景需要自行评估 （docs/design/prefix_caching.md:24-31）。

把调度器、块池和请求三者的动作按时间排开；注意引用计数是在查表之后、分配阶段更新的，查表本身不改状态。

1. 请求进入：前端预计算 prompt 的块哈希，Request 初始化时调用 update_block_hashes()；后续输出 token 填满新块时继续追加（request.py:238-243、:298-303）。
2. 查表：调度器调用 get_computed_blocks()；命中上限是 prompt_length − 1，再交给 find_longest_cache_hit()（kv_cache_manager.py:318-329）。
3. 首 miss 停止：按块哈希顺序查 cached_block_hash_to_block，第一块缺失就 break；链式哈希保证后面的块不可能单独命中（single_type_kv_cache_manager.py:797-802）。
4. 分配：allocate_slots() 先 touch 命中块（ref_cnt 0→1，移出空闲队列），再从队头取新块；队头若带哈希，先清掉哈希完成驱逐（block_pool.py:774-790、:681-715）。
5. 前向与回填：模型只 prefill 未命中的 token；请求推进到满块时，cache_full_blocks() 把哈希键插入表（block_pool.py:203-276）。
6. 释放：请求结束时 ref_cnt 递减；减到 0 的块回到空闲队列。带哈希的块进队尾（晚驱逐），无哈希的块进队头（先复用）（block_pool.py:824-837）。

文档示例说明块内部分匹配的损失；论文实验说明前缀越长，吞吐收益越大。两组数字的口径不同，不能混在一起。

先看文档里的最小例子。块大小取 4，请求 1 有 14 个 prompt token， 前 10 个与请求 0 相同。前两块各 4/4 命中； 第三块只对上 2/4；所以只命中 8 个 token， 剩余 6 个需要重算（docs/design/prefix_caching.md:222）。 这不是实现漏掉了 2 个 token， 而是「只有满块能缓存」的直接结果：第三块没有满，不能把它的 KV 当作完整前缀交给下一个请求。

下面的交互把这段例子缩成可调参数的模拟。拖动共享前缀长度，或者切换块大小，看命中长度怎样被块边界截断； 默认参数就是上面这组数字。

默认参数对应 docs/design/prefix_caching.md:222 的 14-token 示例；块大小 4 是文档示例值，V1 代码默认是 64（vllm/config/cache.py:185）。 这个模拟是简化模拟，不是源码还原。

共享前缀越长，吞吐收益越大

PagedAttention 论文的 §6.4 做了一个共享前缀的翻译实验：模型是 LLaMA-13B，数据是 WMT16 EN–DE， 基线是 Orca (Oracle)。前缀从 1 个示例（80 token）增加到 5 个示例 （341 token）， vLLM 的端到端吞吐分别是基线的 1.67× 和 3.58×。

表 2 · 共享前缀长度的吞吐对照（PagedAttention 论文 §6.4；LLaMA-13B / WMT16 EN-DE）

条件必须和数字一起读：这是论文 §6.4 的共享前缀实验，vLLM 当时通过服务方预留物理块来共享， 不是 V1 的自动哈希查找。3.58× 是 5-shot / 341 token 条件下的端到端吞吐比， 不能直接外推到所有 APC 负载，也不能拆成单独的 prefill 收益。能直接归因的是论文 §4.4 的描述： 共享前缀后，prompt 阶段只需要计算用户的任务输入，重复的前缀 prefill 被省掉。

同一论文 §6.3 的块共享实验口径不同：它统计「共享省下的块数 ÷ 不共享时的总块数」，场景是同一请求内的并行采样与 beam search。 Alpaca 上并行采样节省 6.1%–9.8% 显存、beam search 节省 37.6%–55.2%；ShareGPT 上分别是 16.2%–30.5% 与 44.3%–66.3%（§6.3）。 这些数字说明块共享的显存收益，不是 APC 的命中率或 TTFT 数字。

收益边界与 prefill 占比有关。文档明确写：APC 只减少 prefill 时间，不减少 decode 的逐 token 生成； 当答案很长、或者新请求与已有请求没有相同前缀时，收益消失（docs/features/automatic_prefix_caching.md:77）。 命中率对 TTFT 的影响也沿着同一条线：命中减少的是首 token 之前的 prefill token 数； 如果请求在队列里等待，TTFT 还包含排队时间，缓存命中只作用于真正开始 prefill 之后的那段计算。

把适用边界写清楚：只缓存满块、只省 prefill、只认精确前缀，缓存本身还要占显存。

• 只缓存满块：块内部分匹配不算命中。默认 64-token 块下，前缀尾部最多有 63 个 token 无法复用（64 − 1）。 共享前缀如果总停在块中间，命中长度按块下取整；影响有多大，取决于前缀长度的分布。
• 最后一个 token 必重算：即使全部命中，也要留 token 产生 logits；块对齐可能让重算扩大到一整块 （vllm/v1/request.py:354、kv_cache_manager.py:318-323）。
• 只省 prefill：decode 的逐 token 生成不变；长输出、无共享前缀的负载没有收益 （docs/features/automatic_prefix_caching.md:77）。
• 只认精确前缀：改一个 token，该块及其后所有块的哈希都会变；不是语义相似匹配，也不做编辑距离。 共享必须从第一个 token 起连续相同，中间缺一块就停。
• 缓存要占显存：缓存块留在 block pool 里，哪怕当前没有请求使用；它们仍计入 free blocks 的容量， 块池紧张时按空闲队列 LRU 淘汰，命中率会随并发和负载波动。
• 多租户要隔离：cache_salt 会进入首块哈希，只有相同 salt 的请求才能共享 （docs/design/prefix_caching.md:87）；默认哈希是 sha256， 换成 xxhash 属于非加密哈希，碰撞风险需要自行评估（vllm/config/cache.py:262、docs/design/prefix_caching.md:24-31）。
• 混合模型与重复块：Mamba / sliding window 的细粒度部分命中、EAGLE 丢块、KV connector 不在本页范围；V1 的 block table 是 append-only，可能暂时缓存同一哈希的重复块，直到请求释放 （docs/design/prefix_caching.md:194）。