2.3 Prefix Cache 与 RadixAttention：复用共享前缀的 KV

1. 重复的前缀有多浪费#

先看几个再常见不过的场景：

• 共享 System Prompt：一个客服机器人，每个请求前面都挂着 800 Token 的角色设定和规则说明，只有用户那句话不同。
• Few-shot 提示：分类任务里每个请求都带着相同的 10 个示例，几千 Token 的示例对所有请求都一样。
• 多轮对话：第 5 轮对话的输入 = 前 4 轮的全部历史 + 新问题，前 4 轮的内容和第 4 轮请求高度重合。

这些场景的共同点是：大量 Token 在不同请求间完全相同，且位置也相同（都在序列开头）。而上一章讲过，Prefill 是 Compute Bound 的重活。把同一段 800 Token 的前缀对每个请求都重新 Prefill 一遍，等于反复做同样的昂贵计算。

📌 关键点：Attention 的因果性决定了——一个 Token 的 Key/Value 只取决于它自己和它前面的 Token。所以两个请求只要前缀完全一致，这段前缀每个 Token 算出来的 KV 就一模一样，完全可以只算一次、大家共用。

用类比来说：这就像一份标准合同，前面几页的通用条款对所有客户都一样，没必要给每个客户重新起草——存一份模板，签约时只补上后面的个性化条款即可。

2. 复用的物理基础：块级 KV 共享#

前缀能复用的前提，是显存管理支持”多个请求指向同一份 KV”。这正是上一节 PagedAttention 打下的地基：

• KV Cache 以固定大小的块存储，请求通过块表间接引用物理块。
• 只要两个请求的某些前缀块内容相同，就让它们的块表指向同一个物理块，配合引用计数记录有几个请求在用。
• 新生成的内容写在各请求自己的新块里，共享块只读。vLLM V1 只共享已写满的块，因此跨请求复用不会出现”往共享块里写”的情况，也就不需要 Copy-on-Write。

所以 Prefix Cache 本质上是把”共享前缀块”这件事从’同时并存的请求之间’扩展到’先后到达的请求之间’：前一个请求算完的前缀块，先不急着扔，留在缓存里；后来的请求如果前缀匹配，直接复用这些块，跳过对应的 Prefill 计算。

🔑 核心概念：Prefix Cache = 跨请求、跨时间地复用前缀 KV 块。 PagedAttention 的块共享是空间维度（并存请求共享），Prefix Cache 把它延伸到时间维度（先后请求复用）。

3. vLLM 的 Automatic Prefix Caching#

vLLM 的方案叫 Automatic Prefix Caching（APC，自动前缀缓存）。“Automatic”是它的一大亮点——你不需要手动声明哪段是共享前缀，引擎自动检测并复用。它靠的是对 KV 块做哈希。

3.1 块哈希：如何判断”前缀相同”#

关键问题是：怎么快速判断一个新请求的某个前缀块，和缓存里的某个块”内容相同”？vLLM 的做法是给每个填满的块算一个哈希值，这个哈希由三部分组成：

• 父块的哈希（也就是它前面所有前缀块的哈希）
• 本块内 Token 的序列
• 额外标识（如 LoRA ID、多模态输入的哈希、cache salt 等）

$$\text{block\_hash} = \text{Hash}(\text{parent\_hash},\ \text{block\_tokens},\ \text{extra})$$

把”父块哈希”纳入计算是精髓所在：它保证了只有从序列开头到当前块的整条前缀都完全一致，哈希才会相同。这样就精确刻画了”前缀相同”这件事——第 3 个块的哈希相同，意味着前 3 个块的全部 Token 都相同。把块内 Token 也纳入哈希，则是为了降低哈希碰撞的概率。

下图用 block_size = 4 演示两个请求的哈希链。蓝色块是 A、B 相同的系统提示，黄色是请求 A 的问题，绿色是请求 B 的问题。A 逐块算出的哈希登记进中间黄底的缓存表；B 下方的蓝字标出命中复用的块，红字标出从第 3 块开始与 A 内容不同、哈希分叉后需要新算的块；斜线格是尾块里还没写的槽位，未写满的尾块不参与哈希。

💡 提示：vLLM 自 v0.11 起默认使用 sha256 作为哈希算法，也可通过 --prefix-caching-hash-algo 切换为 sha256_cbor（跨语言可复现）、xxhash、xxhash_cbor 等。非加密算法（如 xxhash）更快，但碰撞风险略高。

3.2 匹配与复用流程#

新请求进来时，vLLM 逐块计算前缀哈希，拿去缓存表（hash → block ID 的映射）里查：

• 命中：对应的物理块还在缓存里，直接把请求的块表指向它、增加引用计数，跳过这部分 Prefill。
• 未命中：正常 Prefill 计算，算完后把新块的哈希登记进缓存，供后续请求复用。

下图中蓝底卡片是命中分支，红底卡片是未命中分支；命中后回到下一块继续查，第一次未命中后就转入正常 Prefill。

📌 关键点：命中前缀缓存能直接砍掉那部分 Prefill 的计算，最直接的收益是大幅降低 TTFT（首 Token 更快出来），同时省下的算力还能服务更多请求。共享前缀越长、命中率越高，收益越大。

4. 缓存的淘汰：LRU 与引用计数#

缓存空间有限，物理块用完了就得淘汰旧的。vLLM 的策略结合了引用计数和 LRU（最近最少使用）：

• 正在被使用的块不能淘汰：引用计数 > 0 的块（还有请求在用）受保护。
• 空闲块按 LRU 淘汰：请求结束后，它的块引用计数归零、进入空闲队列，但内容和哈希先保留着——万一马上有匹配的新请求来，还能命中复用。当显存吃紧需要腾地方时，才真正回收最久没被用到的空闲块。

一个有意思的细节：vLLM 释放块时，是把请求的块按逆序放进空闲队列尾部。因为一个请求的最后一个块哈希了最多的 Token（前缀最长），最不容易被别的请求命中复用，所以让它优先被淘汰；而靠前的块（短前缀，如共享 System Prompt 的开头）更可能被复用，就让它们更晚淘汰。

💡 提示：这个”逆序入队”的小设计体现了一个朴素直觉——越靠近序列开头的前缀，越通用、越值得留；越靠后的前缀越个性化，留着也难命中。

5. SGLang 的 RadixAttention#

vLLM 的 Hash 方案高效，但它有个隐含限制：匹配是”块对齐”且”线性前缀”的——按块边界比对一条从头开始的前缀。而多轮对话、树状采样等场景里，请求的共享关系是树状的：一个共同前缀分叉出多个不同的后续。

SGLang 提出的 RadixAttention 用一棵 Radix Tree（基数树/压缩前缀树） 来管理 KV Cache 的复用：

• 树的每条边代表一段 Token 序列，从根到某节点的路径就是一段前缀，对应缓存的 KV。
• 新请求到来时，沿树做最长前缀匹配，匹配到的路径部分直接复用 KV，只对分叉之后的新内容做计算。
• 分叉天然对应”共同前缀 + 不同后续”，非常契合多轮对话（同一段历史派生多轮）和并行采样（同一 Prompt 采样多个回答）。
• 每个节点带一个引用计数，记录有几个运行中的请求正在用它；只有引用计数为 0 的节点才可淘汰。淘汰按 LRU 进行，并且先淘汰叶子，这样祖先节点上的公共前缀能留得更久。
• 调度时优先处理与缓存共享前缀最长的请求（论文称为 cache-aware scheduling），在同样的缓存容量下提高命中率。

下图是一棵缓存树的快照。蓝色实心节点正被运行中的请求引用（ref > 0），不可淘汰；绿色粗线是新请求沿”系统提示 S → Q1 + A1”匹配到的路径，它只需为绿色斜线的新分支 Q3 做 Prefill；灰色虚线框的叶子 Y 已无人引用（ref = 0），是 LRU 最先淘汰的对象。

🔑 核心概念：两者目标一致——复用共享前缀的 KV、跳过重复 Prefill；区别在数据结构。Hash 表简单高效、适合线性前缀；Radix Tree 更擅长表达和利用树状的前缀共享关系。

⚠️ 注意：不要把它们对立起来看。vLLM 的方案在绝大多数场景已经很够用，且随 V1 做到了近乎零开销；RadixAttention 是在高度树状复用的负载下（如复杂 Agent、大量并行采样）展现出额外优势。SGLang 论文在这类结构化 LLM 程序负载上报告了最高 6.4 倍的吞吐提升，这个数字来自 RadixAttention 与其他优化的组合。选型时看你的负载形态，而非简单认为”树一定比哈希好”。

6. 源码走读：vLLM APC 的哈希与匹配#

前面讲了原理，这一节钻进 vLLM V1 源码，看自动前缀缓存的哈希链和块复用具体怎么落地。相关逻辑主要在 vllm/v1/core/kv_cache_utils.py（哈希）和 block_pool.py / kv_cache_manager.py（复用与淘汰）。下面基于 main 分支的官方设计文档梳理，代码持续演进，以你所用版本为准。

1
# 伪代码：还原 vLLM 块哈希的链式计算（非逐字源码）
2
# 设置了 PYTHONHASHSEED 时由它派生；否则 sha256 系列用固定种子，xxhash 系列用随机种子
3
NONE_HASH = <进程启动时确定的常量>
4

5
def hash_request_tokens(token_ids, block_size, extra):
6
    block_hashes = []
7
    parent_hash = NONE_HASH                       # 第一个块没有父块
8
    for blk_tokens in chunk(token_ids, block_size):
9
        if len(blk_tokens) < block_size:
10
            break                                 # 只对"填满的块"算哈希
11
        # 关键：把父块哈希一起塞进去 → 天然编码了"从头到此的整条前缀"
12
        curr_hash = hash((parent_hash, tuple(blk_tokens), extra))
13
        block_hashes.append(curr_hash)
14
        parent_hash = curr_hash                   # 链式推进
15
    return block_hashes

7. 适用场景与注意事项#

✅ 前缀缓存收益大的场景：

• 长 System Prompt / 长 Few-shot 且被大量请求共享
• 多轮对话（历史不断累积复用）
• 同一 Prompt 并行采样多个输出（n > 1）
• RAG 中固定的指令模板 + 变化的检索内容（固定部分放前面才能命中）

❌ 收益有限甚至无收益的场景：

• 每个请求前缀都不同（如无模板的自由问答）
• 共享部分放在了 Prompt中间或末尾——前缀缓存只能复用从头开始连续相同的部分，共享内容一旦不在开头就无法命中

📌 关键点：想吃到前缀缓存的红利，Prompt 工程上要有意识地”把公共内容前置”——固定不变的指令、示例、上下文放最前面，变化的用户输入放最后。这是一条几乎零成本却常被忽视的优化。

⚠️ 注意：前缀缓存不改变模型输出（复用的是数学上完全等价的 KV），可以放心开启。但要留意多租户环境下的隔离——vLLM 提供 cache_salt 等机制，避免不同租户/权限的请求意外命中彼此的缓存造成信息泄露。

📝 总结#

• Prefix Cache 复用共享前缀的 KV，跳过重复 Prefill，核心收益是降低 TTFT + 提升吞吐。
• 它的物理基础是 PagedAttention 的块级只读共享 + 引用计数，把块共享从”并存请求”延伸到”先后请求”。
• vLLM 的 Automatic Prefix Caching 用含父块哈希的块哈希自动检测相同前缀；V1 做到近乎零开销、默认开启；用 LRU + 引用计数淘汰，并按逆序入队优先淘汰个性化的尾块。
• SGLang 的 RadixAttention 用 Radix Tree 做最长前缀匹配，配合引用计数和”先淘汰叶子”的 LRU，更擅长多轮对话、树状采样等树状复用场景。
• 源码上，vLLM 用 NONE_HASH 起始的链式块哈希把前缀匹配压成 $O(1)$ 查表，配合”块池 + 空闲链表 + 哈希表 + 请求表”四结构完成复用与 LRU 淘汰。
• 实践中要把公共内容前置才能命中，并注意多租户下的缓存隔离。

🎯 自我检验清单#

• 能解释为什么”前缀相同”的请求可以复用同一份 KV（Attention 因果性）
• 能说清 Prefix Cache 与 PagedAttention 块共享在时间维度上的联系
• 能描述 vLLM 块哈希为什么要包含”父块哈希”，以及它如何刻画”前缀相同”
• 能说清链式块哈希如何把前缀匹配变成 $O(1)$ 查表，以及为何只缓存填满的块
• 能说明前缀缓存命中主要优化的是哪个指标（TTFT）及原因
• 能解释 vLLM 释放块时”逆序入队”背后的直觉
• 能对比 Hash 方案与 RadixAttention 的数据结构与擅长场景
• 能指出哪些 Prompt 组织方式能/不能命中前缀缓存

📚 参考资料#

• vLLM Design — Automatic Prefix Caching
• vLLM V1 Alpha Release（零开销前缀缓存）
• vLLM V1 源码 — kv_cache_utils.py（块哈希实现）
• vLLM V1 源码 — block_pool.py（空闲队列与 LRU 淘汰）
• SGLang: Efficient Execution of Structured Language Model Programs（RadixAttention）
• vLLM — Engine Arguments（—prefix-caching-hash-algo）