人工智能:理论、算法与系统 · 第 31 课
PagedAttention、Prefix Caching 与 KV Cache 分配/驱逐
2026 年 11 月 19 日|第 5 周第 3 课|讲授约 18 分钟
上一课讨论 Continuous Batching 如何在每轮动态插入、退出请求。但它依赖一个隐藏前提:请求的 KV Cache 能随时增加、释放、复用,而且不把 GPU 显存切成难以利用的小洞。 今天从操作系统的分页思想讲起,再深入前缀共享与缓存驱逐。
本课四个目标:①推导固定大小 KV Block 的内存和碎片;②解释逻辑块表、链式前缀 Hash;③设计引用计数和安全驱逐;④区分命中率、节省 Prefill FLOPs、TTFT、Decode 性能。
一、为什么连续分配容易浪费 HBM?
推理时单个请求的历史长度会从 Prompt 的 S 增长到 S+G,输出长度 G 在请求到达时通常未知。若提前为最长输出分配一块连续 KV 内存,未使用空间会浪费;若经常扩容、缩容,又可能需要复制大块数据或遇到外部碎片。
例如可用区合计有 10 MiB,分散成 4 MiB、3 MiB、3 MiB 三个空洞;一次需要连续 6 MiB 的分配仍可能失败,虽然总空闲容量足够。这是外部碎片;不是 KV 数学公式的问题。
PagedAttention 借鉴虚拟内存:把一个请求的连续逻辑 Token 位置分成固定大小的逻辑块,再把每个逻辑块映射到任意空闲的物理 KV Block。Attention Kernel 按 Block Table 寻址历史 KV,而不要求物理块在 HBM 连续。
flowchart LR
A["请求 A:逻辑块 0 / 1 / 2"] --> T["Block Table A"]
B["请求 B:逻辑块 0 / 1 / 2"] --> U["Block Table B"]
T --> P["物理块 7:共享前缀 0"]
T --> Q["物理块 2:共享前缀 1"]
T --> R["物理块 11:A 的末尾"]
U --> P
U --> Q
U --> S["物理块 5:B 的末尾"]
图中逻辑块 0、1 在 A/B 之间共享,但物理 ID 为 7 和 2:逻辑有序不等于物理连续。
这项技术减少连续分配造成的浪费,同时引入页表查询、物理块元数据及块内未用槽位。它不消除每个新 Query 对历史 K/V 的必要访问,也不把密集 Attention 的线性单步历史读取变成 O(1)。
二、从张量形状算出“一页”有多大
设模型具有 L 层、每层 Hkv 个 KV Head、每头维数 dh,KV 元素占 b 字节;一个物理块容纳 g 个 Token。忽略不同设备上的层/头分片,此块跨所有层存储的容量为:
[ \boxed{s_{\rm block}=2L\,g\,H_{\rm kv}\,d_h\,b\quad\text{bytes}} ]
系数 2 来自 K 和 V。实际引擎也可能按层分别管理池,公式应对应其内存布局。
数值示例(只计 KV 本体): L=24、Hkv=8、dh=128、b=2(BF16)、g=16。
[ s_{\rm block}=2\times24\times16\times8\times128\times2 =1{,}572{,}864\ {\rm bytes}=1.5\ {\rm MiB}. ]
如果模型在该布局下有 80 个可用物理块,KV 本体池就是 120 MiB;这并非 GPU 总显存,也不包含模型权重、工作区与块表。
长度为 T 的独占序列使用:
[ \boxed{n(T)=\lceil T/g\rceil} ]
个块,末块未用槽位为:
[ \boxed{w(T)=g\lceil T/g\rceil-T,\quad 0\le w<g}. ]
例如 g=16、T=35 时占 3 块、剩下 13 个槽位。这是内部碎片:物理块已分配,里面却有空位。
对没有共享的 B 条请求,物理占用粗估为 (\sum_i\lceil T_i/g\rceil s_{\rm block})。启用共享后,应该数唯一的物理 Block ID,不能再把不同请求的逻辑块简单相加。
三、Prefix Caching 为何必须匹配“前面所有 Token”?
常规自回归 Transformer 第 j 个位置的 K/V 是该位置经过多层网络后的结果。即使当前字词相同,其隐藏状态也可能因之前的上下文不同而不同:
[ K_j=f_K(x_{\le j},\ \text{模型、位置等上下文}),\quad V_j=f_V(x_{\le j},\ \cdots). ]
因此“两个请求包含相同的四个 Token 子串”不等于它们在该位置的 K/V 可以复用。要安全命中,需确保相关因果前缀与计算上下文一致。
vLLM 的一种哈希式自动前缀缓存思路是对完整块建立链式标识:
[ \boxed{h_j=H(h_{j-1},\ {\rm tokenIDs}[jg:(j+1)g],\ {\rm context})}. ]
parent hash 让块 j 的身份依赖此前所有块;context 需要体现实际影响计算的模型版本、位置方案、LoRA/适配器、多模态输入等,隔离场景下还可加入租户 salt。哈希相等还需满足实现的碰撞安全要求。不同 vLLM 版本的算法与默认值会变化;目前文档介绍 SHA-256 等选项及缓存隔离措施。
| 示例: g=4。请求 A 为 [a b c d | e f g h | i j];请求 B 为 [a b c d | e f g h | x]。前两块是相同完整前缀,可以把它们的 KV 映射到同两块物理页;尾块不满,分别使用私有页。若另一个请求为 [z b c d | e f g h | x],即使第二段字符相同,其 parent hash 不同,不能直接拿 A 的第二块 KV 来用。 |
vLLM 文档中的哈希前缀缓存只复用完整的可识别块;与之不同,Beam Search 或某些分支执行会有自己的共享/COW 管理方式。不要混淆“在页表中共享一个物理块”与“任意可写块都能原地共同修改”。
flowchart TD
A["新请求:Token IDs + 模型上下文"] --> B["按 g 分块并计算链式 Hash"]
B --> C{"完整块的前缀 Hash 命中?"}
C -->|是| D["复用物理 KV 块;增加 ref_cnt"]
C -->|否| E["申请新物理块并执行剩余 Prefill"]
E --> F["块完整后登记 Hash"]
D --> G["后续新 Token 用私有可写块"]
F --> G
G --> H["请求完成:减少引用数"]
H --> I["零引用缓存进入可回收集合"]
前缀命中通常节省重复的 Prefill 计算,不意味着 Decode 可以跳过读取历史 K/V。 即便输入 Prompt 完全命中,实现仍可能需要为首个输出 Logit 做少量必要计算。
四、ref_cnt=0 为什么不必马上擦除 KV?
为每个物理块维护:block_id、内容 Hash(若完整可缓存)、ref_cnt 和空闲队列状态。引用计数可理解为当前有多少活跃请求持有这一块。
- 新请求命中块:把块从可回收队列取出,ref_cnt 加一;不能在此时被驱逐。
- 请求正常结束或取消:释放其持有的块,ref_cnt 减一。
- ref_cnt 下降到 0:不再被活跃请求使用,但其完整 KV 内容可保留在闲置缓存中,供下一条相同前缀请求复用。
- 当需要新块但没有彻底空白块:从零引用缓存中按 LRU 等策略选择牺牲块,删除旧 Hash 映射,再重新分配。
要避免两个危险错误:第一,引用数大于零时覆盖物理块,会破坏正在运行请求的上下文;第二,在共享的可写尾块上原地追加,会污染其他请求。可选择只共享不可变完整块,或使用正确的 Copy-on-Write(写时复制)流程。
# 教学伪代码:省略锁、并发、重复 Hash 和分片边界
def acquire(full_block_hash):
blk = hash_table.get(full_block_hash)
if blk is not None:
free_lru.remove_if_present(blk)
blk.ref_cnt += 1
return blk
blk = take_blank_or_evict_unref_block()
blk.ref_cnt = 1
return blk
def release(blk):
assert blk.ref_cnt > 0
blk.ref_cnt -= 1
if blk.ref_cnt == 0:
free_lru.append(blk) # 可保留旧 Hash 直到真正被驱逐
def evict():
blk = free_lru.pop_lru() # 只允许 ref_cnt == 0
remove_hash_mapping_if_matches(blk)
blk.block_hash = None
return blk
这只是接口示意。真实 vLLM 有预分配 Block Pool、空闲队列、请求页表以及重复 Hash 的具体处理规则;其最新设计文档还说明部分版本采用 append-only 的页表和重复块的延迟消除,不能把上述伪代码当成逐行实现说明。
五、块大小越小就越好吗?
块大小 g 减小,典型末块内部浪费的 Token 槽位下降,也可能以更细粒度命中共享前缀。但块数增长,会增加页表、Hash/引用计数、分配管理和潜在 Kernel 寻址开销。
粗略地,若序列长度 T 且块表每项需要 c 字节:
[ M_{\rm metadata}\approx c\lceil T/g\rceil. ]
如果末块剩余位置在 0 到 g−1 之间近似均匀,平均浪费大约 ((g-1)/2) 个 Token 槽位。这是额外分布假设,不是对所有工作负载的定理。
还要注意“命中率”有多种口径:请求命中比例、命中完整 Block 数、复用的 Token 数、实际节省的 Prefill FLOPs 并不等价。相同 50% Token 命中率下,长前缀和短前缀的计算节省可能截然不同。
六、Eviction:LRU 与“保留有价值的前缀”
LRU 保留最近访问过的闲置块;实现简单,但它并不知道将来哪些前缀更可能再次出现,也不直接考虑重新计算某段前缀的代价。
可以提出一个研究化的启发式评分:
[ \boxed{ v_i \approx \frac{\Pr(\text{未来在窗口内命中 }i)\cdot C_{\rm avoided}(i)} {s_i} } ]
其中 (C_{\rm avoided}) 是若复用该内容可以避免的计算或时间成本,(s_i) 是占用字节。低价值零引用块可优先被驱逐。但这个公式并非 vLLM 默认实现:前缀块有依赖关系,某个尾块要命中通常必须有其全部前缀;(\Pr) 难以预测,而且维护估计器本身有开销。它也不能凌驾于 ref_cnt>0 不可驱逐的安全规则之上。
另一个边界是跨节点缓存迁移:如果 GPU 本地没有块,可以重新 Prefill,也可能从 CPU/远端加载。应该比较重算延迟、网络/PCIe 传输、缓存校验与其他请求的资源干扰,不能只说“命中一定最快”。
七、如何测量真正的收益?
在完全相同的模型、Tokenizer、权重、精度、硬件和请求到达流下,比较:①连续/非共享 KV 基线(若可运行);②Paged KV 但不启用自动前缀复用;③Paged KV + Prefix Caching。最好另扫 g、缓存池容量、负载强度。
构造两类数据:冷启动随机独立 Prompt(几乎不共享);相同 system prompt 加上不同用户后缀、反复访问长文档(存在共享前缀)。再控制 0%、25%、50%、75% 等可共享 Token 比例,避免把前缀相似度与请求量同时改变。
记录:正确性(固定输入下的 Logits/生成一致性)、Prefix Reuse Token 数、Full-Block Hit Rate、TTFT p50/p95、TPOT p95、满足双 SLO 的 Goodput、GPU 物理 KV 块峰值、内部浪费、驱逐/重算量、CPU/远端传输开销和队列时间。延迟变化应按真实请求跟踪,而不只看命中率。
对于公开多租户服务,不要在公开基准、日志或仓库里存储私密 Prompt 原文;应验证盐隔离、Cache 身份和访问控制,防止通过命中延迟推断别的租户处理过什么内容。
八、常见反例与研究边界
| 错误直觉 | 正确结论 |
|---|---|
| PagedAttention 会把单步稠密 Attention 变成 O(1) | 分页改变寻址/分配,不消除读取历史 Key/Value |
| Hash 只看当前块的 Token 就够 | 因果 KV 依赖整个此前前缀以及计算上下文 |
| ref_cnt=0 代表缓存已清零 | 可暂留在空闲缓存,需求上来时再驱逐 |
| 可以直接修改多人共享的 KV 末块 | 共享可写状态须避免竞态,用私有页或 COW |
| 小块总能同时省显存和提速 | 内部碎片降低,但元数据与索引成本增加 |
| 前缀命中率高,Decode 计算必然同比例下降 | 主要减少重复 Prefill,不取消 Decode 的历史访问 |
| LRU 或预测式驱逐一定最优 | 取决于未来请求分布、前缀链和真实重算代价 |
经典部分:虚拟内存分页、引用计数、LRU、因果 Attention 的历史依赖,以及上述内存公式。具体研究/工程:Kwon 等在 SOSP 2023 提出 PagedAttention/vLLM;vLLM 的哈希式 Prefix Caching、空闲队列和缓存盐属于具体设计,版本与实现细节可能更新,任何固定吞吐收益需复现实验确认。
参考资料: PagedAttention / vLLM(SOSP 2023);vLLM Automatic Prefix Caching 设计文档(文档页面注明 2026-06-23 更新)。
九、四级递进自测(总分 100)
首版不展示答案。 Lv1/2/3 为客观题,Lv4 按推导与实验方案评分。80 分及以上继续;60–79 分针对性补练;低于 60 分复习再练。
Lv1|分页 KV、引用计数和自动前缀缓存的职责(15 分)
考点: 分页 KV、引用计数和自动前缀缓存的职责|预计用时: 2 分钟|题型: 单选
某标准因果 Transformer 服务同时开启 Paged KV 与哈希式 Automatic Prefix Caching。以下哪项理解最准确?
A. PagedAttention 将稠密注意力计算从 O(T) 降为 O(1),所以不用读历史 K/V。
B. 只要两个请求包含相同的一段子字符串,不论前文和位置是否相同,都能直接安全共享这一段 KV。
C. 分页把逻辑 Token 块映射到不连续的物理块;前缀缓存还须验证完整的因果前缀和模型上下文一致,并保护仍被活跃请求引用的块。
D. 某块的引用数为零,就证明它的缓存内容已经被清零,不可能被后续请求命中。
提示:把“放在哪里”、 “能否重用计算结果”和“仍有人使用时能否驱逐”分成三个问题。
Lv2|物理块数量与前缀共享手算(20 分)
考点: 物理块数量与前缀共享手算|预计用时: 4 分钟|题型: 数值
设每个 KV 物理块容纳 4 个 Token。三个同时运行的请求 A、B、C 分别需要缓存 10、9、6 个 Token;A 与 B 前 8 个 Token 完全相同,C 与它们前 4 个 Token 完全相同,其余所有位置均不存在可共享的完整 4-Token 前缀块。模型和位置等其他缓存上下文一致,只有完整块可以跨请求共享,部分末尾块各自占一个物理块。若分配器允许共享已完成的前缀块,最少需要多少个独立物理 KV 块?
答题格式: 填写一个数值,单位为块。
提示:先计算各请求的逻辑块数,再按完整共同前缀逐块去重;未填满的最后一块仍占一个物理块。
Lv3|内碎片、哈希身份、驱逐与系统收益边界(25 分)
考点: 内碎片、哈希身份、驱逐与系统收益边界|预计用时: 6 分钟|题型: 多选
在每块 g 个 Token 的 Paged KV 和仅复用完整前缀块的哈希缓存系统中,哪些陈述成立?(多选)
A. 一条独占、未共享的长度 T 序列需要 ceil(T/g) 个块,末块空位小于 g;分页能减少连续大段预留的外部碎片,但有页表和内部碎片。
B. 只要最后一个块的 Token ID 一样,即使它之前的所有 Token 不同,也可以直接共享该块的 KV,而不会改变模型输出。
C. 引用计数为正的物理块不能被当作普通空闲缓存块驱逐;引用计数降到零的完整缓存块可以保留供后续命中,在需要空间时再回收。
D. 提高前缀缓存命中率必然按相同比例降低每个 Decode Token 的 Attention 算术量,因为历史 K/V 已不必访问。
E. 缓存标识应考虑完整前缀、相关模型/适配器和多模态输入等上下文;共享环境还须考虑哈希碰撞、租户隔离和潜在时序侧信道。
F. 块越小总是越好,因为减小了内部碎片并且必然不会增加查表元数据、哈希和管理开销。
提示:分别区分页内空位、前缀依赖、活动引用、Prefill 节省与 Decode 读缓存;留意“必然”断言。
Lv4|KV 管理器设计、公式推导、回收策略和系统实验(40 分)
考点: KV 管理器设计、公式推导、回收策略和系统实验|预计用时: 15 分钟|题型: 开放
为一个单节点、单 KV Pool 的 Decoder-only GQA 推理服务设计 Paged KV + Prefix Cache 管理器。设层数 L、KV 头数 Hkv、头维 dh、每元素 b 字节、每块 g Token、GPU 可供 KV 使用的物理块数 M。 A(12 分):从 K/V 的张量形状推导每个物理块字节数,写出不共享时长度为 Ti 的请求块数、最后一块空位范围,以及逻辑块表与非连续物理页的例子。 B(10 分):给出可安全复用的前缀块哈希身份定义,解释为何只匹配相同子串不够、何时不能跨租户/模型/LoRA/多模态输入直接共享,并区分完整块与部分块。 C(10 分):定义 ref_cnt、空闲缓存队列、命中与驱逐流程,说明共享块保护、写时复制或只共享不可修改块的规则;提出一个综合命中价值与重算成本的候选驱逐策略,并说明它不一定比 LRU 更好。 D(8 分):设计可复现的 A/B 对照:无缓存、分页无前缀复用、分页+前缀复用;覆盖共享率、Prompt 长度、块大小、并发、冷/热缓存与多租户安全;报告正确性、TTFT、TPOT、Goodput、峰值 HBM、重算量、命中率和驱逐数。
提示:从每层 K+V 两份张量出发;对哈希块记录 parent hash 与本块 Token;为活动引用设置不可驱逐条件;性能比较要固定模型、输入与到达流。
十、下一课预告
第 32 课|2026 年 11 月 20 日|第 5 周第 4 课:KV Cache 量化与 Eviction/Offloading 的精度—带宽权衡。
我们将从 INT8/INT4 的 Scale 与误差传播出发,推导压缩 KV 后的 HBM 占用及访存收益,再比较 GPU HBM、CPU RAM 与跨节点迁移的重算/传输决策。
GitHub 文件: microcourses/lessons/ai-031.md 与 microcourses/quizzes/ai-031.json。首版讲义不含标准答案;独立 JSON 保存答案、解析及开放题评分细则。