KV Cache 与 PagedAttention：推理的内存战争

是什么：KV Cache 的定义

Step 1：没有 KV Cache 的灾难

Transformer 的自注意力机制，每个 token 要对所有之前的 token 算 Attention：

生成第 1 个 token 时：计算 [t₁] 的 QKV
生成第 2 个 token 时：计算 [t₁, t₂] 的 QKV（t₁ 的 KV 重新算了一遍！）
生成第 3 个 token 时：计算 [t₁, t₂, t₃] 的 QKV（t₁, t₂ 的 KV 又重算一遍！）
...
生成第 N 个 token 时：计算 [t₁, t₂, ..., tₙ] 的 QKV（前 N-1 个全重算！）

计算量：O(n²)，而且随着序列增长，每生成一个新 token 都要重新计算所有历史 token 的 K 和 V。这是纯浪费。

Step 2：KV Cache 来了

KV Cache 的原理极其朴素：算过的 K 和 V 存起来，下次直接用。

第 1 步：算 [t₁] 的 K₁, V₁ → 存入 Cache
第 2 步：只算 t₂ 的 K₂, V₂ + 从 Cache 读 K₁, V₁ → Attention
第 3 步：只算 t₃ 的 K₃, V₃ + 从 Cache 读 K₁⁻₂, V₁⁻₂ → Attention
...

每个新 token 只算自己的 KV，历史的从 Cache 读。计算量从 O(n²) 降为 O(n)。

广告系统类比

这和你的正排索引逻辑一模一样：

KV Cache：已计算的历史 K,V → 存起来复用
正排索引：已构建的广告字段（标题/描述/质量分）→ 索引存储，请求时直接读

没有 KV Cache = 每次请求都重新解析广告文本、重新算质量分 → 和没有正排索引一样蠢

为什么 KV Cache 是内存杀手？

KV Cache 的大小公式：

KV Cache 大小 = 2 × 层数 × hidden_dim × 序列长度 × 精度(bytes)

以 Llama-2 70B 为例：
= 2 × 80层 × 8192维 × 4096 tokens × 2 bytes(FP16)
= 2 × 80 × 8192 × 4096 × 2
≈ 10.7 GB

一个请求的 KV Cache 就要 10.7 GB！ 如果你要并发处理 10 个请求，光 KV Cache 就吃掉 107 GB 显存——A100 整张卡才 80GB。

而且还有个更糟的问题：序列长度是不确定的。

请求 A：最终生成 500 tokens
请求 B：最终生成 4000 tokens

如果你给每条都预分配 4096 token 的空间 → A 浪费了 87% 的空间
如果你给每条按实际分配 → B 扩展到 4000 时可能周围已经被别的请求占满了

这个问题的本质和你的广告系统里 “不知道该给每个 query 分配多少候选数” 完全一样——预分配多了浪费，分配少了不够，动态扩展又会碎片化。

是什么：PagedAttention

PagedAttention 是 vLLM 提出的一种 KV Cache 管理方法。核心思想：把 KV Cache 按固定大小的 Block 分页，像 OS 管理虚拟内存一样管理显存。

Step 1：Block 化 KV Cache

传统方式（连续分配）：
请求A: [K₁ K₂ K₃ K₄ K₅ K₆ K₇ K₈ ...]  一整块连续显存

PagedAttention（分页）：
请求A: [Block 0: K₁⁻⁴] → [Block 3: K₅⁻⁸] → [Block 7: K₉⁻¹²]
       不一定连续，通过 Block Table 映射

Step 2：Block Table 映射

请求 A 的 Block Table:  [0, 3, 7, ...]
请求 B 的 Block Table:  [1, 4, 8, ...]
请求 C 的 Block Table:  [2, 5, ...]

空闲 Block Pool:        [6, 9, 10, 11, ...]

当请求需要更多 KV Cache 时，从空闲池里分配一个 Block，追加到它的 Block Table。不需要时释放回池子。

广告系统类比

PagedAttention 的 Block Table  →  倒排索引的跳表 (Skip List)
PagedAttention 的 Block Pool   →  共享内存池
PagedAttention 的按需分配      →  正排字段的 L2 按需加载

你的索引系统里，每条广告的 KV 数据不是连成一片存的——跳表指针让数据可以分散存储。
PagedAttention 的 Block Table 完全一样：逻辑连续，物理分散。

去掉 PagedAttention 的代价

回到传统连续分配的三个致命问题：

1. 碎片化

显存布局（传统方式）：
[请求A 4096] [请求B 2048] [请求C 4096] [空闲 2048]

请求 A 结束了 → 释放 4096
[空闲 4096] [请求B 2048] [请求C 4096] [空闲 2048]

新请求 D 需要 8192 → 分配失败！
因为最大的连续块只有 4096，虽然总空闲是 4096+2048=6144，但不连续

这就是 OS 内存管理里经典的“外部碎片”问题。PagedAttention 直接复用操作系统 50 年前就解决的方案：分页 + 不要求连续。

2. 预分配浪费

每个请求的最终长度很难提前知道。传统方式要么预分配太大（浪费），要么预先不够（扩不了）。

PagedAttention：按需分配 Block，不够再加。一个 Block 是固定 16 或 32 个 token。浪费上限 = 最后一个 Block 的空间（最多 15-31 个 token 的空间）。

3. 无法共享

很多场景下不同请求共享同一个 prompt（如 few-shot learning 的系统提示）。传统 KV Cache 每个请求都要各自存一份相同的 prompt KV。

PagedAttention 可以让多个请求的 Block Table 指向同一批物理 Block（引用计数），去重显存。

覆盖多少场景？

场景 KV Cache 压力 PagedAttention 收益
短对话（<500 tokens） 低 小，但无副作用
长文档（>4000 tokens） 极高 最大，避免碎片化和预分配浪费
高并发（>50 个请求同时） 极高 关键，碎片化问题是并发杀手
多轮对话（累积上下文） 随轮次线性增长 大，按需扩展避免早期预分配
共享前缀（如 system prompt） 可去重 额外收益，Block 共享节省大量显存

判断标准：当你的平均请求长度 > 2000 tokens 或并发数 > 20 时，PagedAttention 是必选项。

不变的本质

KV Cache 和 PagedAttention 背后三条不变原理：

1. 缓存 = 用空间换时间

KV Cache 不是免费的——它以显存为代价，换取避免重复计算。和你的正排索引用内存换检索速度一模一样。

2. 碎片化是动态分配的天敌

任何动态分配系统（OS 内存、数据库 Buffer Pool、广告正排缓存）都面临碎片化。解决方案永远是分页 + 非连续 + 空闲池。PagedAttention 不是发明新东西，是把 OS 50 年前就发明的方案搬到了显存管理。

3. 去重是批处理的天然红利

当多个请求有共享部分时，缓存共享 = 免费的性能提升。这个原理在你的广告系统里也一样——多个广告共享相同的行业特征，该去重的就去重。

元结构映射

广告系统                          LLM 推理 KV Cache
────────                        ──────────
正排索引（已构建数据）    →      KV Cache（已计算的 K,V）
L1 热数据（频繁访问）     →      最近几个 token 的 KV（高频 Attention）
L2 温数据（按需加载）     →      中间 token 的 KV
L3 冷数据（长期存储）     →      极长序列的早期 KV（可能需要 offload）
字段级去重               →      Block 共享（前缀缓存）
mmap 按需映射            →      Block Table 非连续映射
外部碎片问题             →      连续分配 vs 分页分配
正排分层节省 65% 内存    →      PagedAttention 节省 ~55% KV Cache 显存

关联我的经验

我在广告系统的索引压缩和正排分层项目中学到的，直接映射到 KV Cache 管理：

  1. 正排 L1/L2/L3 = KV Cache 的热温冷分层 正排：质量分/出价放 L1（热）、标题描述放 L2（温）、完整素材放 L3（冷）。 KV Cache：最近 100 个 token 高频访问（热）、早期 token 低频访问（冷）。 理论上可以设计多级 KV Cache——热数据放 SRAM，冷数据放 HBM 甚至 SSD。

  2. 字段去重 = Prefix Cache 共享 正排去重让 15% 的内存被复用。多个请求共享 system prompt 的 KV Cache，本质上就是字段去重。

  3. $正排分层节省了 65% 内存 = PagedAttention 的碎片消除 你做正排分层之前，所有字段全放内存。分层后按需加载，节省了大量空间。 PagedAttention 从预分配连续块 → 按需分页，同样的逻辑节省了 ~55% KV Cache 显存。

  4. 客户沟通语言：“你的卡原来只能跑 5 个并发请求，上 PagedAttention 后可以跑 12 个——等效于每张卡的吞吐翻倍，成本减半。”

一句话总结本质

KV Cache = 正排索引，PagedAttention = 正排分层按需加载 + 碎片消除。推理系统的内存管理，和广告系统的索引管理，在底层是完全同构的两个问题。