前缀缓存

共享的 system prompt、few-shot 示例和多轮对话意味着：大多数 prefill token 之前已经算过了。给 block 做哈希，然后复用。

块哈希
基数树
LRU 淘汰
引用计数
缓存命中率

为什么重要

问题

看看一个真实的对话服务收到的是什么：1500 token 的 system prompt，几千 token 的 few-shot 示例或检索文档，最后是四十个 token 的用户提问。下一个请求除了末尾那四十个 token 之外完全相同，再下一个也是。

多轮对话更糟，或者说更好，取决于你怎么看。第五轮会把第一到第四轮原封不动地重发一遍。这些 token 几秒钟前刚 prefill 过，引擎却把它们全部丢掉，重新算一遍。

prefill 受算力限制，所以这不是一笔小税。在带有大段 system prompt 的对话负载上，冗余 prefill 可能占到服务器全部 GPU 工作量的一大半。

核心思路

解法

S06 已经给了我们可共享的 block，缺的只是一个把两个请求指向同一块的理由。前缀缓存补上了这个理由：给每个 block 一个由其内容导出的身份，在计算任何东西之前先查一下这个身份。

这个身份必须包含位置，否则出现在不同偏移处的相同 token 块会被错误匹配。标准做法是链式哈希：一个 block 的哈希同时覆盖它自己的 token 和它父块的哈希。

基于哈希的前缀复用python

def match_prefix(self, token_ids, block_size):
    """Return the physical blocks we can reuse, and where prefill must start."""
    reused, parent_hash = [], None

    for start in range(0, len(token_ids) - block_size + 1, block_size):
        block = tuple(token_ids[start : start + block_size])
        h = hash((parent_hash, block))       # chained: position is baked in

        node = self.cache.get(h)
        if node is None:
            break                            # first miss ends the shared prefix
        node.last_used = self.clock
        node.ref_count += 1
        reused.append(node.physical_block)
        parent_hash = h

    return reused, len(reused) * block_size   # prefill starts here

只有填满的 block 才能被缓存

尾部那个未填满的 block 无法被哈希：请求马上还要往里追加 token，内容还会变。所以前缀缓存的命中总是落在 block 边界上，而更小的 block 以更高的开销换来更细的共享粒度。

工作原理

示意图链式哈希与基数树

共享前缀的请求会汇聚到同一批节点上。这棵树是「哪些 block table 恰好重叠」的一个视图，而不是一个独立的数据结构。

微妙之处在淘汰策略里

缓存是有限的，block 必须被淘汰。朴素的 LRU 在两个地方是错的。

绝不淘汰仍有已缓存子节点的节点。 子节点的哈希是从这个节点算出来的。丢掉父节点，子节点就变成了占着显存却无法到达的垃圾。只淘汰叶子。
绝不淘汰正在被运行中请求使用的 block。 引用计数解决这个问题：refcount > 0 的 block 被钉住，只有最后一个使用它的请求结束后才成为候选。

最终的行为像是在树的前沿上做 LRU，共享的 system prompt 因此顺带得到保护：它永远是一个有很多子节点的内部节点，永远不会成为候选。

基数树与 SGLang 的变体

vLLM 把它实现成一张从 block 哈希到 block 的扁平哈希表，树结构隐含在父指针里。SGLang 则用 RadixAttention 把它显式化：一棵以 token 序列为键的基数树，边上携带的是变长 token 串，而不是固定大小的 block。

显式的树按 token 粒度匹配，而不是 block 粒度。共享前缀较短时这一点很要紧，淘汰策略也变成了名副其实的树上叶子 LRU。代价是多了一个更复杂、还必须与分配器保持一致的结构。

动手观察

动手试试

六个共享同一段 system prompt 的请求循环往复，大致就是一个对话接口看到的流量。跑起来，注意第二轮：树停止生长，日志变绿。

模拟器带 LRU 淘汰的前缀缓存把流量跑两遍，然后缩小容量

block 大小4缓存容量（block 数）24

第 0 / 24 步

前缀命中率: 0%
复用的 token: 0
需 prefill 的 token: 0
淘汰次数: 0

基数树 · 已缓存 0/24 个 block

空 — 点击运行

每个节点是一个已缓存的 block。深度对应它在 prompt 中的位置，所以共享的 system prompt 只在根部出现一次，所有请求都挂在它下面。绿色节点是被复用过的。

请求日志

还没有请求

绿色是你不必再做的 prefill。第二轮流量走完后，system prompt 对每个请求都是免费的。这直接砍掉的是首 token 时间，不只是 GPU 成本。

这对 TTFT 意味着什么

无前缀缓存

有前缀缓存

prefill 受算力限制，所以跳过它带来的延迟收益接近线性。带有大段共享 system prompt 的生产对话流量，命中率通常在 60–90%。vLLM 和 SGLang 都默认开启这项功能。

现在把容量拖到 8 个 block。淘汰开始，命中率下降。KV 缓存容量和前缀缓存容量本就是同一份预算：每一个用来为可能到来的未来请求保存历史的 block，都是正在运行的请求拿不到的 block。

亲手实现

实现

code/s07_prefix_caching.py（节选）python

def evict(self, n_needed: int):
    """LRU over evictable leaves only."""
    has_cached_child = {node.parent_hash for node in self.cache.values()}

    candidates = [
        node
        for h, node in self.cache.items()
        if node.ref_count == 0            # not pinned by a running request
        and h not in has_cached_child     # not a prefix of something cached
    ]
    candidates.sort(key=lambda n: n.last_used)

    for node in candidates[:n_needed]:
        self.free_blocks.append(node.physical_block)
        del self.cache[node.hash]

哈希碰撞是正确性 bug，不是性能 bug

如果两个不同的 token 序列哈希到同一个值，一个请求就会无声地读到另一个请求的 KV 缓存。输出流畅且错误，而且没有任何地方会记录一条错误。生产引擎会用 64 位或更宽的哈希，在偏执一点的配置里还会把 token id 与哈希一起存下来、命中时做比对。如果你是认真要上线，就把 token 存下来并比对。

前缀缓存会跨请求泄漏信息

缓存命中比未命中快，而这个时间差是可观测的。能对请求计时的攻击者可以推断某个特定前缀是否已被缓存；在多租户服务器上，这就暴露了其他用户发送过什么。在意这一点的引擎会按租户或按 API key 隔离缓存。如果你用一个实例服务多个客户，这不是可选项。

在本地运行

在 S06 的块管理器之上构建一个链式哈希前缀缓存，回放一份带共享 system prompt 和多轮对话的合成负载，并报告命中率、节省的 prefill token 数，以及容量收缩时的淘汰行为。

$ python code/s07_prefix_caching.py

预期输出：对话负载上约 80% 的块命中率、约 78% 的 prefill token 被复用，以及一次容量扫描，展示只淘汰叶子的 LRU 如何保护共享前缀。

只需要 NumPy — 查看环境准备.

生产实践

在生产环境中

vLLM —— enable_prefix_caching，在 v1 中默认开启。在与 PagedAttention 相同的 block 池上使用链式 block 哈希。
SGLang —— RadixAttention；缓存就是分配器，且支持 token 粒度匹配。
Anthropic 与 OpenAI 的 API —— 把它以 prompt 缓存的形式暴露出来：Anthropic 让你显式放置 cache_control 断点，OpenAI 则对 1024 token 及以上的 prompt 自动缓存；两家都给缓存 token 打折计价。API 层的这个功能，就是这套机制配上一张价目表。
quant.cpp —— 把压缩后的 KV 缓存序列化到一个 .kv 文件，让会话恢复时零重算。这是同一想法的单用户版本。

练习

1
在缓存命中时加上 token id 比对，并刻意构造一次碰撞，证明你的检查确实能抓住它。
2
实现两级缓存：GPU block 后面挂一层主机内存。测量 PCIe 传输是否比重算 prefill 更便宜。答案取决于 prompt 长度，找到那个交叉点才是重点。
3
实现缓存感知路由：在两个引擎副本之间，把每个请求送到最可能已经持有其前缀的那个副本。测量相对轮询的命中率提升。

继续学习

接下来

我们已经让缓存变小、可共享、可复用。最后一个显存杠杆，是让缓存里的每一个数字本身更小。S08 讲量化：INT8 与 INT4 权重、分组 scale、GGUF K-quant，以及那种能让消费级硬件跑长上下文的 KV 缓存压缩。

自测

习题

先作答，再看解析。答错比答对更有价值，因为解析会指出你该回头重读哪一部分。

自测第 1 题 / 共 6

为什么一个 block 的哈希要包含其父块的哈希，而不只是它自己的 token？

得分 0/6