vLLM：PagedAttention 与前缀缓存 | Xiaojun 的技术笔记

大模型推理服务里，KV Cache 既是性能的关键，也是显存的主要消耗者。vLLM 用两项设计解决这个问题：PagedAttention 解决显存怎么存，前缀缓存（Prefix Caching）解决重复计算怎么省。本文梳理两者的原理与关系，并给出应用侧提高缓存命中率的做法。

两个痛点

自回归生成时，每个 token 的 Key/Value 向量都要保留，供后续 token 做 attention，这就是 KV Cache。它带来两个问题：

显存浪费：传统实现为每个请求预分配一段连续显存，按最大长度预留。实际生成长度事先未知，预留部分用不上，还会产生内部碎片和外部碎片。
重复计算：很多请求共享相同的开头（system prompt、工具定义、few-shot、多轮历史），每次都重新做 prefill，白白消耗算力。

PagedAttention

核心思想

借鉴操作系统的虚拟内存分页：

把 KV Cache 切成固定大小的 block（vLLM 默认 16 个 token 一块）。
每个请求维护一张 block table，记录“逻辑块 → 物理块”的映射。
物理块不要求连续，按需分配。

flowchart LR
    subgraph L["请求 A 的逻辑块"]
        L0["逻辑块 0"]
        L1["逻辑块 1"]
        L2["逻辑块 2"]
        L3["逻辑块 3"]
    end
    subgraph P["GPU 物理块"]
        P7["物理块 7"]
        P2["物理块 2"]
        P11["物理块 11"]
        P5["物理块 5"]
    end
    L0 --> P7
    L1 --> P2
    L2 --> P11
    L3 --> P5

带来的收益

问题	传统方式	PagedAttention
预留浪费	按最大长度预分配	用到才分配
内部碎片	每个请求尾部大量空闲	最多浪费最后一个 block
外部碎片	连续内存难以分配	不要求连续，无外部碎片
并发能力	受碎片限制	同样显存可容纳更大 batch

据 vLLM 论文报告，当时已有系统的 KV Cache 显存浪费可达 60%~80%，PagedAttention 可将其压到 4% 以下，吞吐因此显著提升。该数据来自论文的对比实验，不同模型与负载下会有差异。

块级共享

block table 是一层间接寻址，不同请求的表项可以指向同一个物理块。这是并行采样、beam search 共享前缀的基础，也是下面前缀缓存的基础。

前缀缓存

目标

新请求的开头与历史请求完全一致时，直接复用已算好的 KV block，跳过这部分 prefill，从而降低首 token 延迟（TTFT）并节省算力。它只优化 prefill，不影响 decode 阶段的速度。

链式哈希

每个已填满的 block 计算一个哈希：

hash(block_i) = H( hash(block_{i-1}), 本块 token ids, 额外键 )

哈希里包含前一块的哈希，所以它代表“从序列开头到本块”的整段前缀，而不只是本块内容。
额外键用于区分不同语义环境，如 LoRA 适配器、多模态输入、cache_salt 等。
第一块没有前驱，使用固定的初始值。

flowchart LR
    I["init"] --> H0["hash0<br/>tokens 0-15"]
    H0 --> H1["hash1<br/>tokens 16-31"]
    H1 --> H2["hash2<br/>tokens 32-47"]

只有从开头起逐 token 完全一致，对应位置的哈希才会一致。

查找与复用

维护全局的 哈希 → 物理块 映射表。
新请求到来，按顺序逐块计算哈希并查表。
命中的块直接挂到该请求的 block table 上，并增加引用计数。
遇到第一个未命中的块即停止，其后部分正常 prefill。

引用计数与 LRU

多个请求可同时引用同一个物理块，计数记录引用数。
请求结束后，计数降为 0 的块不立即清除，而是进入空闲队列，哈希映射仍然保留，等待被后续请求复用。
显存紧张时，按 LRU 从空闲队列淘汰：最近最少使用的块优先回收，分配给新请求。

边界条件

只缓存满块：尾部不足一个 block 的 token 不进入缓存。前缀共 100 个 token 时，最多缓存 96 个（6 个满块）。
前缀强一致：中间任何一个 token 不同，其后所有块的哈希都会改变，缓存全部失效。
块内变化整块失效：命中以 block 为粒度，块内一个 token 不同，该块整块重算。
部分命中：从开头起、第一个不一致的 block 之前都可复用，变化越靠后损失越小。

两者的关系

前缀缓存建立在 PagedAttention 之上，但不属于 PagedAttention 本身。

	PagedAttention	前缀缓存
解决的问题	显存碎片与浪费	重复前缀的重复计算
核心机制	分块 + block table	块哈希 + 引用计数 + LRU
角色	内存管理基础设施	构建在其上的复用策略
是否可选	始终生效	可开关（V1 引擎默认开启）
主要收益	更高的显存利用率与吞吐	更低的 TTFT 与算力开销

前缀缓存依赖 PagedAttention 的两点能力：固定大小的块（提供哈希与查表的粒度）和块表间接寻址（允许多个请求指向同一物理块）。如果 KV Cache 是每请求一段连续内存，就很难只共享其中一部分。

反过来，只用 PagedAttention 而不开前缀缓存完全可以工作，只是请求结束后块即释放，不会被后续请求复用。

提高命中率

核心原则只有一条：稳定的内容放前面，变化的内容放最后。

以 OpenAI 协议为例，推荐的上下文顺序为：

系统指令 → 工具定义 → 静态知识 / Few-shot → 历史对话 → 当前问题

对应到请求参数：

内容	位置
系统指令、静态知识	`messages[0]`，`role: system`
工具定义	顶层 `tools` 参数（由服务端 chat 模板渲染）
Few-shot、历史对话	其后的 `user` / `assistant` 交替消息
当前问题	`messages` 最后一条 `user`

注意事项：

顶层 key 顺序无关紧要：tools 写在 messages 前后均可，拼接顺序由服务端 chat 模板决定，真正重要的是数组元素顺序和文本内容。
工具定义在最终 prompt 中的位置取决于模板：有的模板把工具拼在 system 消息之后，有的拼在 system 内部。上线前用模型自带的 apply_chat_template 渲染一次，确认稳定内容确实排在前面。
tools 数组必须顺序确定、内容固定：工具顺序、description、properties 字段顺序、required 顺序，任何一处变化都会让后续缓存失效。动态注册的工具建议显式排序；在 Go 中尤其要避免直接遍历 map 生成数组，因为遍历顺序是随机的。
不要在前部混入易变信息，如时间戳、请求 ID、用户名，这类信息放到最后一条 user 消息中。
历史消息只追加，不改写、不中途裁剪。推理模型要留意：多轮对话里如果把上一轮的思考内容剥掉再回传，前缀就变了，缓存会从那里开始失效。
避免按问题动态筛选工具子集：不同组合会产生不同前缀。工具数量不大时，全量传入更利于命中。
vLLM 无需额外请求参数，前缀一致即自动命中。这与需要显式标记缓存断点的服务不同，迁移时注意区分。

小结

PagedAttention 通过分块与块表，让 KV Cache 的显存管理像操作系统分页一样高效，消除碎片，提升并发。
前缀缓存在分块的基础上，用链式哈希识别相同前缀，通过引用计数与 LRU 管理复用，直接省掉重复的 prefill。
两者是“基础设施”与“上层策略”的关系。应用侧只需遵循“稳定在前、变化在后”的原则构造 prompt，就能获得可观的 TTFT 收益。

参考

Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023
vLLM 官方文档：Automatic Prefix Caching