PagedAttention 完全拆解：操作系统分页思想如何拯救 LLM 推理的内存利用率

背景：KV Cache 是什么，为什么它是推理系统的命脉#

自回归生成与两阶段推理#

大语言模型的推理是一个自回归（autoregressive）过程：模型一次只能生成一个 token，生成第 $t+1$ 个 token 时，要以”提示词 + 之前生成的 $t$ 个 token”作为输入。用概率的语言说，模型在计算一个条件概率的连乘积：

P(x) = P(x_1) \cdot P(x_2 \mid x_1) \cdots P(x_n \mid x_1, \dots, x_{n-1})

每一个条件概率都由 Transformer 的前向计算给出。而 Transformer 的核心是自注意力层：对输入序列中每个位置 $i$ 的隐藏状态 $x_i$ ，先做三个线性投影得到 query、key、value：

q_i = W_q x_i, \qquad k_i = W_k x_i, \qquad v_i = W_v x_i

然后，位置 $i$ 的注意力输出是所有”它能看到的位置”的 value 的加权平均，权重由 query 与 key 的点积经过 softmax 得到：

a_{ij} = \frac{\exp(q_i^{\top} k_j / \sqrt{d})}{\sum_{t=1}^{i} \exp(q_i^{\top} k_t / \sqrt{d})}, \qquad o_i = \sum_{j=1}^{i} a_{ij} v_j

其中 $d$ 是注意力头的维度，除以 $\sqrt{d}$ 是为了防止点积过大把 softmax 推向饱和区（这就是 softmax 缩放因子的由来）。

这里出现了一个关键结构：生成第 $t+1$ 个 token 时，新 query $q_{t+1}$ 需要和前面所有位置的 key 算点积，再和前面所有位置的 value 做加权求和。如果每个 step 都把前面所有 token 的 key、value 重新算一遍，计算量会随序列长度平方级增长——完全不可接受。所以推理系统把这些已经算过的 key、value 向量缓存在显存里，生成新 token 时直接复用。这个缓存就是 KV Cache。

于是，一次请求的推理被自然地分成两个阶段：

Prefill（预填充）阶段：一次性输入整个 prompt（比如 1024 个 token），并行计算所有位置的 key、value 并写入 KV Cache，同时算出第一个输出 token 的概率。这一阶段做的是大矩阵乘（matrix-matrix），GPU 的并行度被充分榨干，属于计算密集；
Decode（生成）阶段：逐个 token 生成。每一步只输入 1 个新 token，计算它的 query，再读取整段 KV Cache 做注意力。这一阶段做的是矩阵向量乘，GPU 算力利用率很低，瓶颈是把整段 KV Cache 从显存搬到计算单元的内存带宽——属于内存密集（memory-bound）。

decode 阶段是 memory-bound 这一点，是理解 PagedAttention 全部动机的钥匙。 它意味着：对 decode 阶段来说，最稀缺的资源不是算力（FLOPS），而是显存容量和显存带宽。谁能在有限显存里塞进更多的并发请求，谁的吞吐就更高。

KV Cache 有多大：先算一笔账#

用 PagedAttention 论文里的例子（OPT-13B 模型，FP16）：每个 token 的 KV Cache 大小是

2 \text{（K 和 V 两份）} \times 5120 \text{（隐藏维度）} \times 40 \text{（层数）} \times 2 \text{（FP16 每元素 2 字节）} = 800 \text{ KB/token}

模型支持最长 2048 token 的序列，那么一条请求的 KV Cache 最高可达 1.6 GB。一张 A100 40GB 的卡上，13B 模型的权重要占约 26 GB（65%），剩下的显存里很大一块都要用来装 KV Cache（约 30%）。

A100 上的显存分布：权重约 65%，KV Cache 约 30%，激活仅占小部分

A100 40GB 上服务 13B 模型的显存分布：灰色是常驻的模型权重（约 65%），红色是按请求动态分配/释放的 KV Cache（约 30%），黄色是临时的激活张量。右侧曲线对比 vLLM 与现有系统的 KV Cache 增长曲线。（来源：PagedAttention 论文 Figure 1）

这张图的右侧曲线值得单独解释：现有系统的 KV Cache 曲线是阶梯式跳变的——因为每个请求一进来就预分配了最大长度的连续内存，新请求到来时显存瞬间被占满；而 vLLM 的曲线是平滑增长的——KV Cache 按需分配，有多少 token 才占多少空间，同样的显存可以服务更多请求。

更麻烦的是，KV Cache 有两个”反常规”的特性：

大：如上所述，单序列就能吃掉 GB 级显存；
动态：它的大小取决于输出长度，而输出长度在生成完成前不可预知——同一个 prompt，可能生成 10 个 token 就停了，也可能生成 1000 个。

这两点让”给每个请求静态分配一块连续内存”的做法注定低效。下面进入正题：现有系统到底浪费了多少？

问题：连续内存预分配，60%-80% 的显存被白白浪费#

为什么大家都用”连续内存 + 预分配”#

几乎所有深度学习框架（PyTorch、TensorFlow）都要求张量存储在连续内存中——这是 GPU kernel 高效访存的前提（连续地址可以合并成一次大的内存事务，也就是 CUDA 里的 coalesced memory access）。因此 2023 年之前的主流推理系统（如 NVIDIA FasterTransformer、Orca）都把一条请求的 KV Cache 存成一个连续的张量。

问题是：输出长度未知。系统不可能等请求生成完了再分配内存（那就没法存了），只能”赌”一个上限——按模型支持的最大序列长度（比如 2048 token）为每个请求预分配一整块连续显存。这个看似无奈的选择，引入了三类内存浪费：

现有系统的 KV Cache 管理：请求 A 按最大长度 2048 token 预分配，请求 B 按 512 token 预分配。图中展示了三种内存浪费——预留槽位（reserved）、内部碎片（internal fragmentation）、外部碎片（external fragmentation）。每个格子代表一个 token 的 KV Cache。（来源：PagedAttention 论文 Figure 3）

逐类拆解（这张图值得逐格读）：

预留槽位（reserved）：预分配的大块内存里，只有一部分装下了真实 token 的 KV Cache，其余位置是”留给未来 token 的”。图里请求 A 右侧的空格就是预留空间。它最终会被使用（只要请求真的生成了那么多 token），但在整个请求生命周期内都被独占——别的短请求明明用不了那么多，也没法借用。
内部碎片（internal fragmentation）：由于输出长度不可预知，系统必须按最大长度预分配。大部分请求根本不会生成那么长——比如图里请求 A 实际只用了 2048 中的一小段，剩下的空间永远用不上，这就是内部碎片。内部碎片只有在请求结束后才被发现（生成完了才知道实际长度），所以完全无法回收利用。
外部碎片（external fragmentation）：每个请求预分配的大小不同（A 是 2048、B 是 512），内存分配器（比如 buddy allocator，伙伴分配器——把内存按 2 的幂切块分配）会把空闲空间切得七零八落，产生大量既不属于任何请求、又因为太小而装不下新请求的零散空洞。图里 B 的块旁边和上方的空洞就是外部碎片。

论文在 §6.2 的实验中实测了这些浪费的总量，结果触目惊心：

实验测得的不同系统中 KV Cache 内存浪费占比：灰色以外的部分都是浪费——预留槽位、内部碎片、外部碎片。真正被用来存 token 状态的有效内存只有 20.4%-38.2%。（来源：PagedAttention 论文 Figure 2）

也就是说，现有系统花了 5 倍的显存，只有约 1/5 到 1/3 真正装下了 KV Cache 数据。vLLM 官方博客给出的表述是：“现有系统因碎片化和过度预留浪费了 60%-80% 的内存”——和论文的 20.4%-38.2% 利用率是同一件事的两种说法。

浪费的后果：batch 上不去，吞吐上不去#

这套浪费直接卡住了推理服务的命脉——batch size。

推理系统提高吞吐的核心手段是批处理（batching）：多个请求共用同一份模型权重，权重从显存搬运的开销被多个请求摊薄，GPU 算力利用率显著提升。批得越多，摊得越薄，吞吐越高。而 batch 能做多大，取决于所有请求的 KV Cache 能不能同时装进显存——因为 KV Cache 恰恰占据了显存的大头。

于是逻辑链条很清晰：

连续预分配 → 60%-80% 浪费 → 有效 KV Cache 空间只有 20%-40% → 能同时批的请求数被卡死 → 吞吐上不去。

论文里有直接的数据佐证：在 OPT-13B、ShareGPT 流量下，vLLM 同一时刻处理的请求数是 Orca 的 2.2 倍（对比理想化的 Orca-Oracle），是 Orca-Max 的 4.3 倍——多出来的并发能力，全部来自内存利用率的提升，而不是调度技巧。

另外还有一个常被忽略的问题：内存共享机会被白白放弃。LLM 服务经常用高级解码算法，比如并行采样（一个 prompt 生成多个不同结果供用户挑选）和 beam search（保留 top-k 候选序列）。这些算法产生的多条序列共享同一个 prompt——它们的 prompt 部分 KV Cache 是完全相同的。但现有系统里每条序列的 KV Cache 都存在各自独立的连续内存中，相同的内容被重复存储了好几份。论文实验里，prompt 部分占并行采样场景总 KV Cache 的 12%，全是冗余。

为什么已有的调度优化救不了#

有人可能会问：Orca 不是已经提出过”迭代级调度”（iteration-level scheduling）吗？它允许每个迭代结束后就把完成的请求移出 batch、新请求移入 batch，避免请求级批处理的排队延迟和 padding 浪费。为什么它也不行？

答案是：Orca 优化的是”计算侧的浪费”，而 PagedAttention 要解决的是”内存侧的浪费”，两者正交。 迭代级调度确实让 GPU 算力利用率更高了，但算力利用率高不等于吞吐高——当显存只够装 20 个请求时，无论调度多精细，batch 都不可能超过 20。迭代级调度甚至让内存问题更尖锐：请求频繁进出，预分配/释放更频繁，碎片化更严重。论文里的 Orca 基线正是用 buddy allocator 预分配连续内存，才会浪费得那么厉害。

一句话：调度技巧管的是”哪些请求一起跑”，内存管理管的是”哪些请求装得下”。PagedAttention 解决的是后者。

核心思想：把 KV Cache 当成虚拟内存来管理#

PagedAttention 由 UC Berkeley 的 Woosuk Kwon、Zhuohan Li 等人提出，论文《Efficient Memory Management for Large Language Model Serving with PagedAttention》于 2023 年 9 月 12 日提交 arXiv，发表在 2023 年 10 月 23-26 日德国科布伦茨举行的 ACM SOSP（操作系统原理大会，ACM SIGOPS 第 29 届）上，同年 6 月开源的 vLLM 项目（GitHub 仓库）就是它的完整实现。这篇论文的灵感来源非常”操作系统”：把虚拟内存和分页技术从 OS 移植到 GPU 显存管理上。

虚拟内存是操作系统的经典设计（最早可以追溯到 1962 年 Kilburn 等人的 one-level storage）：进程看到的地址空间是连续的”虚拟地址”，但 OS 把它切成固定大小的页（page），通过页表（page table）把每个虚拟页映射到物理内存中任意位置（甚至不在内存里、而在磁盘上）。连续的逻辑页可以对应不连续的物理页，物理页按需分配，进程之间还能共享物理页。

PagedAttention 的映射关系是：

操作系统虚拟内存	PagedAttention
页（page）	KV 块（block）
字节（byte）	token
进程（process）	序列（sequence）
页表	块表（block table）

具体做法：把一条序列的 KV Cache 切成若干个固定大小的 KV 块，每个块容纳固定数量 token 的 key 和 value（默认每块 16 个 token）。这些块不需要在物理显存中连续，通过块表记录”逻辑块 → 物理块”的映射。新 token 生成时按需分配新块，序列结束时释放所有块，物理块立刻可以被其他请求复用。

PagedAttention 示意图：KV Cache 分散在三个不连续的物理块中

PagedAttention 算法示意：这条序列的 KV Cache 分散存储在物理地址不连续的三个块里。计算时，当前 query token（图中 “forth”）先与块 0 的 key 向量（“Four score and seven” 的 key）算注意力分数，再与后续各块依次计算，最后把各块分数拼起来做 softmax，再与各块的 value 加权求和。（来源：PagedAttention 论文 Figure 5）

这张图是全文的灵魂，逐格读：

图中块 0 存了 “Four score and seven”（4 个 token，假设块大小 4 便于图示）的 key/value，块 1 存 “years ago” 的，块 2 存 “our fathers” 的——三个块在物理内存中是散开的（块 0 和块 2 相邻、块 1 隔着一段，说明它们来自不同的物理地址，中间的空洞可能属于别的序列）；
当前要生成的是 “forth” 这个 query token（这是美国《葛底斯堡演说》文本的后续词），它的 query 向量 $q_i$ 依次和各块内的 key 做矩阵乘得到部分注意力分数；
各块的分数在 token 维度拼成完整的分数向量，softmax 归一化后，再分别和对应块的 value 做加权求和，得到最终输出 $o_i$ 。

PagedAttention 改变了什么、没改变什么，要划清界限：它没有改变注意力公式本身（数学上和标准 softmax 注意力完全等价，没有任何近似），改变的是 KV Cache 的存储布局——从”一整块连续内存”变成”若干可寻址、可独立分配/释放/共享的块”。所有性能收益都来自这个布局变化带来的内存管理自由度。

对比之前的问题清单，这个设计逐一击破：

内部碎片：只发生在每个序列的最后一个块（装不满 16 个 token 的尾部空位）。块小（16 个 token 的 KV），浪费被限制在一小块以内，实测浪费不足 4%；
外部碎片：所有块大小相同、由统一的内存池分配，分配器不存在”不同大小的空洞”——彻底消除；
内存共享：共享粒度从”整条序列”细化为”一个块”。多条序列（同一请求的多个采样，甚至不同请求）可以把逻辑块映射到同一个物理块，配合引用计数和写时复制（Copy-on-Write）机制安全共享；
按需分配：不再需要预分配最大长度，序列的 KV Cache 随生成过程动态生长，物理块用完即释放、立即复用。

原理详解（一）：块、块表与解码流程走查#

KV 块的物理形态#

先明确一个实现细节：一个”块”里到底装了什么？Transformer 的每个 token 在每一层、每一头都有一份 key 和 value。vLLM 的实现选择是：每层、每头分别有独立的块表和块空间——即”第 0 层第 0 头的 K 块”是一块，“第 0 层第 0 头的 V 块”是另一块。论文脚注说明这个选择纯粹为了方便实现，和”所有层所有头共用一个块”性能上没有差别。实际中 vLLM 还把 K 和 V 合并存放（每个 token 的 [k, v] 连续存放），以便一次内存事务读取。

每个物理块能容纳的 token 数叫块大小（block size）B，vLLM 默认 $B = 16$ 。这个数字的权衡在论文 §7.2 有专门消融，后面”设计参数”一节细讲。先记住结论：16 足够让 GPU 并行度吃饱，又足够小让碎片可忽略。

块表：逻辑块到物理块的翻译#

vLLM 的 KV Cache 管理器（KV Cache Manager）维护每个序列的块表。块表的每个条目记录两样东西：

该逻辑块对应的物理块编号（指向统一内存池中的一块）；
该块中已填充的位置数（因为最后一个块往往装不满 16 个 token）。

vLLM 中的块表翻译。上图：一条 7-token prompt 的 KV Cache 占用 2 个逻辑块（每块 4 个 token，便于图示），映射到物理块 7 和 1；块表记录物理块编号和已填充位置数。下图：两步解码后，第二个逻辑块写满，新 token 的 KV 存入新分配的物理块 3。（来源：PagedAttention 论文 Figure 6）

论文用这个例子走查了完整的解码流程（图 6 上下两部分），我按论文的编号展开：

① 预填充阶段：prompt 有 7 个 token，块大小假设为 4（图示简化），那么需要 $\lceil 7/4 \rceil = 2$ 个逻辑块。vLLM 不为”未来可能生成的 2048 个 token”预留任何内存，只为 prompt 的实际 KV Cache 分配 2 个物理块（图中物理块 7 和 1）。prefill 阶段用常规的（连续内存版）FlashAttention 之类 kernel 计算，然后把前 4 个 token 的 KV 写入逻辑块 0（物理块 7），后 3 个 token 写入逻辑块 1（物理块 1）——逻辑块 1 还剩 1 个空位，块表的 #filled 记录为 3；
② 第一次 decode：生成第一个新 token，用 PagedAttention kernel 在物理块 7 和 1 上完成注意力计算。新 token 的 KV 正好填进逻辑块 1 剩下的空位，块表的 #filled 从 3 更新为 4——没有分配任何新内存；
③ 第二次 decode：逻辑块 1 已经写满，新 token 的 KV 需要新块。vLLM 从内存池分配物理块 3，在块表中登记”逻辑块 2 → 物理块 3”的映射，然后把 KV 写进去。

整个过程没有一次”大块预分配”。每次迭代，vLLM 的调度器先选出这一轮要批处理的序列集合，为需要新块的序列分配物理块，然后把所有输入 token 拼成一个 batch 喂给模型，模型内部用 PagedAttention kernel 按块表读写 KV Cache。

这里有一个值得体会的工程哲学：“逻辑块填满才分配新物理块”这个规则，把所有内存浪费限制在一个块以内。序列的 KV Cache 在逻辑上仍然是从左到右连续增长的（像虚拟内存的连续地址空间），但物理上每个块都是独立分配的——这就是”用一层间接寻址，换来内存管理的全部自由”。

两个序列共存：统一内存池#

同一时刻两条序列的 KV Cache：左侧是序列 A 的逻辑块（映射到物理块 1、3），右侧是序列 B 的逻辑块（映射到物理块 2、4）。两条序列的逻辑块可以交错存放在同一片物理内存池中，互不干扰，也没有空洞。（来源：PagedAttention 论文 Figure 7）

这张图展示了”外部碎片消除”的直观效果：序列 A 的逻辑块 0、1 分别落在物理块 1、3（中间隔着序列 B 的物理块 2），序列 B 的逻辑块 0、1 落在物理块 2、4。所有物理块都被占满，池子里没有一处浪费。序列 A 结束后，它的物理块 1、3 立即释放，可以被新序列复用——不需要搬动任何数据（对比：连续内存系统里要”压缩”内存才能填补空洞，而论文明确说在性能敏感的推理系统里做压缩不现实，因为 KV Cache 体量太大）。

原理详解（二）：块式注意力的数学#

PagedAttention 的注意力计算可以写成块式的。设第 $j$ 个 key 块为 $K_j = (k_{(j-1)B+1}, \dots, k_{jB})$ ，第 $j$ 个 value 块为 $V_j = (v_{(j-1)B+1}, \dots, v_{jB})$ （每个都是 $B \times d$ 的矩阵， $d$ 是头维度）。论文把标准注意力公式改写成：

A_{ij} = \frac{\exp(q_i^{\top} K_j / \sqrt{d})}{\sum_{t=1}^{\lceil i/B \rceil} \exp(q_i^{\top} K_t \mathbf{1} / \sqrt{d})}, \qquad o_i = \sum_{j=1}^{\lceil i/B \rceil} V_j A_{ij}^{\top}

逐个符号解释：

$A_{ij}$ 是一个行向量（ $1 \times B$ ），元素是 query token $i$ 对第 $j$ 块内每个 key 的注意力分数 $a_{ij'}$ ；
$q_i^{\top} K_j$ ：query 向量与块内全部 $B$ 个 key 向量的一次矩阵乘，一次性算出 $B$ 个未归一化分数；
$\mathbf{1}$ 是长度 $B$ 的全 1 列向量， $\exp(q_i^{\top} K_t \mathbf{1} / \sqrt{d})$ 表示”块内所有分数的和”——分子（该块的分数向量）与分母（该块分数之和）用同一个 $\exp$ 操作算出来，数值上比先算指数再分别求和更稳定；
$\lceil i/B \rceil$ ：因果注意力下，query $i$ 最多能看到第 $\lceil i/B \rceil$ 块（块大小 $B$ ，第 $i$ 个 token 属于第 $\lceil i/B \rceil$ 块，之后的内容被掩码掉）；
最后 $o_i = \sum_j V_j A_{ij}^{\top}$ ：把各块的 value 矩阵乘以对应的分数行向量（的转置），逐块累加出最终输出。

为什么可以这样分块？关键在于 softmax 的归一化是对所有已见位置求和的全局操作，但求和满足结合律——先算每块的”部分和”，最后把各块的部分和加起来，与直接对全部位置求和数学上完全等价。 $o_i$ 的累加同样是线性的，块之间顺序无关。所以：分块只是改变了计算的组织方式，结果是逐位精确的，没有任何近似。

工程上，PagedAttention kernel 的处理方式是把公式拆成”逐块”执行：对每个物理块，先算分数（query 乘 key 块）、记录块内和，处理完所有块后再统一归一化、逐块累加输出。这与 FlashAttention 的在线 softmax（一边流式读块一边维护运行统计量，不必等所有块读齐）思路互补——vLLM 的 prefill 阶段用的就是 FlashAttention 类 kernel（那时 KV 是连续布局），decode 阶段才用 PagedAttention kernel（KV 是分页布局）。

一个关键的实现细节：块表查找的代价#

有了块表，注意力 kernel 就不能像连续内存那样”按顺序直接读”，而是每读一个块都要做一次”逻辑块 → 物理块”的翻译。这个间接寻址是 PagedAttention 引入的新开销，论文毫不避讳：在 §7.1 的 kernel 微基准里，PagedAttention 的注意力 kernel 延迟比高度优化的 FasterTransformer 版本高 20%-26%（多出来的部分来自块表访问、额外分支和变长序列处理）。

那为什么这个代价值得？两层原因：

这个 20%-26% 只作用于注意力 kernel，而注意力只是模型中众多算子之一（Linear、LayerNorm 等都和内存布局无关，零开销）；
这点 kernel 开销换来的是 2-4 倍的端到端吞吐提升——因为内存利用率提升后 batch 可以大好几倍，GPU 算力被喂得更饱，单次 kernel 慢一点完全被”同时跑的请求多几倍”淹没。

论文的结论是：“尽管有这个开销，PagedAttention 让 vLLM 在端到端性能上大幅超过 FasterTransformer。” 这是”局部变慢、全局变快”的典型例子，值得记住——做系统优化时，不要因为某个局部指标恶化就否定整体收益，要先量化两个层面各自的影响。

原理详解（三）：kernel 实现#

vLLM 的引擎由 8.5K 行 Python（调度器、块管理器等控制面）+ 2K 行 C++/CUDA（PagedAttention 等 kernel）组成。论文 §5.1 描述了三个为分页 KV Cache 定制的 kernel 优化：

1. 融合 reshape 与块写入（fused reshape and block write）。每个 Transformer 层算完新 token 的 key/value 后，需要按块表把结果写到散落在物理内存各处的块里——写入前还要把数据 reshape 成利于块读取的内存布局（比如把”token 维度”和”头维度”的排布互换，使后续读取时每个 warp 连续读一个块）。这两个操作（reshape + 按块表写入）被融合成一个 kernel，避免多次 kernel 启动的开销。

2. 融合块读取与注意力（fusing block read and attention）。这是 PagedAttention 的核心 kernel：按块表读取 KV 块并就地完成注意力计算。为了合并访存（coalesced memory access）——即让同一 warp 的 32 个线程访问连续的地址，CPU/GPU 才能把 32 次小访问合并成几次大的内存事务——kernel 分配一个 warp（32 线程）读一个块。同时这个 kernel 支持 batch 内变长序列（每条序列块数不同、最后一块填充数不同）。

3. 融合块复制（fused block copy）。写时复制（下节讲）需要把某些物理块的内容复制一份。被复制的块物理地址不连续，如果用 cudaMemcpyAsync 逐块复制会产生大量小规模内存搬运调用。vLLM 写了一个 kernel 把一批块的复制操作合并成一次 kernel 启动，显著降低复制开销。

这三个 kernel 体现的共同原则是：分页引入的间接寻址必须由 kernel 原生消化，而不是在 kernel 外做数据搬运——任何”先把分页数据整理成连续数据再计算”的做法都会把内存收益吐回去。

内存共享：并行采样、Beam Search 与共享前缀#

引用计数：块级共享的安全基础#

分页带来的第二个大杀器是块级内存共享。前面说过，并行采样和 beam search 会产生多条共享 prompt 的序列。在分页体系里，多条序列的同一个逻辑块可以映射到同一个物理块——物理块只存一份，逻辑块表各记各的。

但这引出一个安全问题：物理块是共享的，如果一条序列要往共享块里写数据（decode 会不断写新 KV），就会污染其他序列的数据。vLLM 的解法是操作系统的经典答案：引用计数 + 写时复制（Copy-on-Write）。每个物理块记录一个引用计数（有几个逻辑块指向它）：

需要读共享块：随便读，无冲突；
需要写共享块：先检查引用计数。若计数 > 1，则新分配一个物理块，把原块内容复制过去（只复制这一块），引用计数减 1，然后在新块上写；若计数 = 1，直接写。

并行采样示例：样本 A1、A2 共享同一个 prompt（逻辑块 0、1 都映射到物理块 7、1，引用计数均为 2）。进入生成阶段后，两个样本的输出 token 不同，需要各自独立的内存——vLLM 为第一个要写入的样本（A1）分配新物理块 3 并复制物理块 1 的内容（写时复制），之后 A2 的写入直接落在已减到 1 的物理块 1 上。（来源：PagedAttention 论文 Figure 8）

走查一遍论文的这个例子（图 8）：

并行采样产生样本 A1、A2，两者 prompt 完全相同。vLLM 只为 prompt 分配一份物理块（块 7 和 1），两条序列的块表都指向它们，物理块 7、1 的引用计数都是 2；
生成阶段，A1、A2 采样出不同的 token。A1 先要写它的最后一个逻辑块（逻辑块 1，物理块 1）：vLLM 检查到物理块 1 的引用计数为 2 > 1，于是分配新物理块 3，把物理块 1 的内容复制过去，物理块 1 引用计数减为 1，A1 的块表把逻辑块 1 改指向物理块 3，然后写入；
轮到 A2 写：物理块 1 的引用计数已经是 1，A2 直接写入——它恰好得到了”内容正确”的物理块 1（因为复制发生在 A1 写入之前，A1 写的是新块 3，物理块 1 还是原来的内容）。

注意一个精妙的细节：复制发生在”需要写的人”身上，而不是”共享的所有人”身上——A1 触发复制时，复制的是它要修改的那一块的旧内容；A2 完全不感知复制发生，继续用原块。这保证了写时复制的正确性：谁先写，谁拿走旧块；剩下的人继续共享。

共享的边界也值得说清楚：prompt 部分（前面所有逻辑块）可以完全共享；但每条序列最后那个”正在写的”逻辑块，写时复制会让它们很快分开（如上面 A1、A2 各自独享最后一个块）。随着生成推进，每条序列的”最后一个块”不断刷新——所以并行采样场景的共享收益主要集中在 prompt 部分（论文实验里占 12% 的 KV Cache，加上短生成序列共享比例有限）。

Beam Search：动态变化的共享树#

Beam search（束搜索）比并行采样更复杂：每一步都要从 $k \times |V|$ 个候选中保留 top-k（ $|V|$ 是词表大小），候选序列会”合并同类项”——不同候选可能源自同一个父序列，也可能一起被淘汰。这意味着共享关系随解码推进动态变化，像 OS 里 fork 出的进程树。

Beam search 示例（束宽 4）：所有候选共享第一个逻辑块（prompt），候选 3 从第二个块开始与大家分歧，候选 0-2 共享前三个块、在第四块分歧。虚线标记的迭代后，top-4 候选全部源自候选 1、2——候选 0、3 被淘汰，其物理块（2、4、5、8）引用计数归零被释放，新分配的物理块 9-12 供新候选使用。此时所有候选共享块 0、1、3，候选 0、1 共享块 6，候选 2、3 共享块 7。（来源：PagedAttention 论文 Figure 9）

这张图信息量大，拆开读：

虚线之前：4 个候选各用了 4 个逻辑块。块 0 全共享（prompt 部分）；候选 3 从块 1 起就和别人分歧（它采样了一条独立的路）；候选 0-2 共享块 1、2，在块 3 分歧；
虚线处：这一步结束时，top-4 候选全部来自候选 1 和 2（候选 0、3 得分不够被淘汰）。淘汰者的物理块引用计数清零——块 2、4、5、8 被立即释放，回到内存池；
新一步：为 4 个新候选分配物理块 9-12。现在所有候选共享块 0、1、3；候选 0、1 共享块 6；候选 2、3 共享块 7。

对比现有系统：beam search 里候选序列被淘汰后，它的 KV Cache 内存要等整条序列结束才能释放（或者频繁整段复制 KV）。论文特别指出：现有系统频繁执行跨候选的 KV Cache 复制——比如上图虚线之后，候选 3 要复制候选 2 的大段 KV 才能继续生成。而 vLLM 里大部分块天然共享，复制只发生在写时复制那一刻的一个块。

共享前缀与系统提示词#

第三种共享场景是共享前缀（shared prefix）。LLM 服务常常给所有请求拼一个很长的系统提示词（system prompt：任务描述 + 示例输入输出），比如机器翻译服务把”你是一个翻译引擎，以下是几个英译德示例”拼在每个翻译请求前面。这类请求的前缀部分 KV Cache 完全重复。

vLLM 的做法和 OS 的共享库如出一辙：服务端预先为一组已知的共享前缀分配好物理块、算好 KV Cache（注意，“前缀内容要预先算好”在论文的语境里是服务提供者的实现细节——vLLM 后来的版本用”前缀缓存/哈希”机制自动完成，见”局限与未解决的问题”一节的第 6 点）；用户请求只要把它的逻辑块映射到这些缓存物理块即可，prefill 只算用户自己那部分输入。共享前缀块的最后一个块同样标记为写时复制。

论文在翻译工作负载（WMT16 英译德，LLaMA-13B）上验证：共享 1 个示例（80 token）的前缀时，vLLM 比 Orca（Oracle）吞吐高 1.67 倍；共享 5 个示例（341 token）时，高 3.58 倍——前缀越长、共享越多，收益越大。

三种原语：fork、append、free#

vLLM 用三个极简原语统一实现所有解码算法（论文 §5.2）：

fork：从已有序列派生新序列（并行采样、beam search 的分支都用它——fork 时新序列的块表复制旧序列的映射，物理块引用计数 +1）；
append：给序列追加一个 token（写入 KV Cache，必要时分配新块/触发写时复制）；
free：删除序列（物理块引用计数 -1，归零则释放）。

任何未来出现的解码算法，只要能拆成这三个操作，就能直接跑在 vLLM 上。这种”用少量原语抽象复杂语义”的设计，让系统的内存管理器完全不需要理解 beam search 或并行采样的细节——它只维护引用计数和块表，复杂逻辑全部下沉到这三个原语。

共享收益的数据#

论文 §6.3 实测了块共享节省的内存比例（节省块数 / 不共享时的总块数）：

场景	Alpaca 流量	ShareGPT 流量
并行采样（2-8 个样本）	6.1% - 9.8%	16.2% - 30.5%
Beam search（束宽 2-6）	37.6% - 55.2%	44.3% - 66.3%

vLLM 官方博客给出的口径是：共享让并行采样和 beam search 这类复杂采样算法的内存占用最高降低 55%，折算成吞吐最高提升 2.2 倍——共享让”复杂解码算法”从奢侈选项变成了人人可用。

vLLM 系统设计：调度、抢占与分布式#

整体架构#

vLLM 系统总览：集中式调度器（Scheduler）持有 KV Cache 管理器（KV Cache Manager），管理 GPU worker 上的物理 KV 块；GPU worker 各自维护一块物理内存池（GPU Block Allocator），另有 CPU 块分配器（CPU Block Allocator）用于抢占时的换出。每个迭代，调度器把输入 token 和块表广播给各 worker，worker 执行模型后用 NCCL 同步中间结果。（来源：PagedAttention 论文 Figure 4）

vLLM 的整体架构是集中式调度 + 分布式执行：

调度器（Scheduler）：唯一的决策中枢，运行在 CPU 上，持有全局的 KV Cache 管理器。每个迭代它决定：batch 里有哪些序列、每条序列需要哪些新块、要不要抢占；
GPU worker：每张卡一个，负责执行模型。worker 内有一个块引擎（block engine），从 GPU 显存中划出一块连续的区域切成等大的物理块（这就是”统一内存池”的物理实现）。此外每个 worker 还有一个 CPU 块分配器，管理换出到 CPU 内存的块（抢占用，见下）；
KV Cache 管理器：不直接碰显存，而是通过指令让 GPU worker 的块引擎干活——分配块、释放块、复制块。这样调度器的 Python 代码和 kernel 的执行完全解耦。

调度与抢占：内存不够时怎么办#

请求流量超过系统容量时，vLLM 必须决定谁先谁后。论文的调度策略很简单：FCFS（先来先服务）——保证公平、避免饿死；需要抢占时，最先到达的请求最后被抢占，最新到达的先被抢占。

关键问题来了：显存耗尽时抢占谁？被抢占的 KV Cache 怎么恢复？

选谁抢占：论文采用”全有或全无（all-or-nothing）“策略——一条序列要么全部块都在 GPU 上，要么全部换出。原因很直接：处理一个请求需要它的全部 token 状态都在显存里（注意力要读整段 KV），驱逐一半毫无意义。此外，同一请求内的多条序列（比如 beam search 的候选）组成一个序列组（sequence group），组内共享物理块，必须整体调度（一起抢占、一起恢复），否则引用计数会被拆散。

怎么恢复：两种经典技术，论文都实现并对比了：

换出（Swapping）：把被抢占序列的 KV 块复制到 CPU 内存（类比 OS 的磁盘 swap）。等显存有空位了再换回来。换出空间有个优雅的天然上界：换到 CPU 的块数永远不会超过 GPU 上的总块数——因为同一时刻 GPU 上至少有一批块在服务其他请求，且每块被换出时 GPU 就少一块，所以 CPU swap 空间最坏也就等于 GPU KV 池大小；
重算（Recomputation）：把被抢占序列生成的 token 拼回 prompt，当作一个”新的长 prompt”重新跑一遍 prefill——所有位置的 KV 可以在一次 prefill 迭代里并行算出（这就是 decode 阶段生成过的 token 可以”打包重算”的原因：KV Cache 的每层计算可以并行，重算的总耗时远小于原始逐 token 生成耗时）。重算不占额外内存，但占算力。

微基准：不同块大小下，重算（recomputation）与换出（swapping）两种恢复机制的开销。换出在小块时开销陡增（大量小块传输让 PCIe 带宽吃不满），重算开销与块大小无关且始终较低；中等块大小（16-64）下两者端到端性能接近。（来源：PagedAttention 论文 Figure 19a）

怎么选？论文 §7.3 的结论很清晰：

换出对块大小敏感：块越小，被抢占序列的块数越多，CPU-GPU 之间的小数据传输越多，PCIe 带宽利用率越低，开销越大；
重算与块大小无关：它根本不碰 KV 块，开销只取决于被抢占序列的长度和 GPU 算力；
综合结论：块小的时候重算更优；块大的时候换出更优；但重算的开销从不高于换出的 20%——在论文的实验配置（A100、PCIe 传输）下，重算几乎总是更好的选择。vLLM 后续版本也以重算为默认抢占模式，把换出作为可选开关保留。

分布式执行：一张块表管多卡#

大模型（如 OPT-175B 需要 8 张 A100-80GB）要跨卡切分。vLLM 支持 Megatron-LM 风格的张量并行：线性层按列切分、注意力按头切分、每次前向通过 all-reduce 同步中间结果。

这里有个非常漂亮的观察（论文 §4.6）：张量并行下，每张卡处理的输入 token 完全相同，只是各自算不同的头——所以每张卡需要的 KV Cache 是同一批位置。于是 vLLM 只维护一份 KV Cache 管理器（放在调度器里），所有 GPU worker 共享同一套逻辑块到物理块的映射。每张卡只存属于自己那部分注意力头的 KV（物理块编号相同，但各自只存自己负责的头的 K/V 切片）。

每次迭代的流程：调度器准备”输入 token + 各序列的块表”的控制消息并广播给所有 worker → worker 执行模型，注意力层按块表读各自负责的 KV 切片 → 中间结果通过 NCCL all-reduce 同步 → 把采样结果送回调度器。worker 之间不需要在内存管理上同步——所有内存决策都发生在调度器这一处，这大大简化了分布式实现。

设计参数：块大小为什么是 16#

块大小是 PagedAttention 最重要的旋钮，论文 §7.2 专门做了消融：

块太小（如 4）：GPU 并行度吃不饱。每个 warp 读一个块，块越小，每次读的数据越少，warp 间的并行和内存带宽利用都不够，kernel 延迟上升；
块太大（如 128、256）：内部碎片和共享粒度变差。短序列（比块还短）的请求浪费增大；共享发生在”块”粒度，块越大，序列间能共享的公共部分越难以恰好对齐到块的边界，共享收益下降。Alpaca 流量（短输入短输出）下，块大小 32 以上性能显著劣化，就是因为”序列比块还短”的比例太高；
论文的实测：ShareGPT 流量下块大小 16-128 都表现良好；Alpaca 流量下只有 16、32 表现好。最终选择 $B = 16$ 作为默认值——“足够大以高效利用 GPU，足够小以避免显著内部碎片”。

这个权衡也解释了为什么块大小不能照搬 OS 的页大小：OS 页面是 4KB 对齐的固定值，而 LLM 推理的”页”要同时服务 GPU 并行度和内存碎片率两个互相拉扯的指标，只能在两者之间取平衡。后续引擎（如 FlashMLA 用 64、TensorRT-LLM 用 128 等）各有各的取舍，但思路一脉相承。

性能评估：2-4 倍吞吐从哪来#

论文的实验设置：OPT-13B/66B/175B 与 LLaMA-13B，跑在 Google Cloud A2（A100）实例上；流量用真实数据集 ShareGPT（ChatGPT 对话，平均输入/输出都比 Alpaca 长 8.4 倍/5.8 倍）和 Alpaca（指令微调数据，短）按泊松到达过程合成；指标是归一化延迟（每个请求的端到端延迟 ÷ 输出长度，衡量”在多少请求率下延迟还能保持平稳”）和可持续的请求率。基线：FasterTransformer（配了动态批处理调度）和自研的 Orca 三种变体——Orca (Oracle)（先知输出长度，理论上限）、Orca (Pow2)（预留最多 2 倍输出长度）、Orca (Max)（按最大序列长度 2048 预留）。

基本采样#

对比对象	vLLM 可维持的请求率优势
Orca (Oracle)	1.7x - 2.7x
Orca (Max)	2.7x - 8x
FasterTransformer	最高 22x

（数据来源：PagedAttention 论文 §6.2）

论文摘要里的”2-4x”是对 Orca 全系对比的保守口径。为什么对 FasterTransformer 能到 22 倍？因为 FasterTransformer 没有细粒度调度机制，内存管理还停留在”最大长度预分配”（等价于 Orca-Max 的水平），叠加没有迭代级调度，并发能力被双重压制。

一个反例值得注意：Alpaca 流量 + OPT-175B（640GB 显存，KV Cache 池巨大）时，vLLM 对 Orca (Oracle) 的优势明显收窄（图 12f）——因为这个配置下系统变成了 compute-bound 而不是 memory-bound：显存绰绰有余，大家都能批很多请求，内存优化不再重要。这反向印证了 PagedAttention 的价值前提：显存紧张时它才发挥威力，而 LLM 服务的常态恰恰是显存紧张。

并行采样与 Beam Search#

并行采样（样本数越多收益越大）：对 Orca (Oracle) 的优势从基本采样的 1.3x 提升到 2.3x（beam width 6）；
序列越长、束宽越大，vLLM 优势越明显——因为共享块的比例随序列变长而变高。

共享前缀与聊天场景#

机器翻译共享前缀：1 个示例 → 1.67x；5 个示例 → 3.58x（对比 Orca (Oracle)）；
聊天场景（ShareGPT 流量，1024 token 长 prompt）：vLLM 可维持的请求率是三种 Orca 基线的 2 倍——聊天请求几乎人人 1024 token 的 prompt，Orca 的 buddy 分配器给每条请求预留整段空间，碎片和预留双重浪费最严重，PagedAttention 的按需分配优势最大。

vLLM 博客的实战数据#

论文之外，vLLM 官方博客给出了更面向社区的对比（LLaMA-7B/A10G 与 LLaMA-13B/A100，ShareGPT 流量）：

单输出：比 HuggingFace Transformers 吞吐高 14x-24x，比 HuggingFace TGI 高 2.2x-2.5x；
三路并行输出：比 HF 高 8.5x-15x，比 TGI 高 3.3x-3.5x（并行输出越多，内存共享的收益越明显，这与论文的结论一致）；
LMSYS 的 Chatbot Arena 在 2023 年 4 月起用 vLLM 作为推理后端：日均 3 万请求、峰值 6 万，GPU 数量砍掉一半（这组数字出自 vLLM 博客的 LMSYS 一节）。

局限与未解决的问题#

讲透一项技术，也要讲清楚它的边界：

1. 注意力 kernel 有 20%-26% 的固有开销。 块表间接寻址、变长序列分支都是纯开销。论文诚实承认这一点，也解释了为什么值得：开销只在注意力算子，且换来了数倍的端到端吞吐。但对”延迟敏感、batch 很小”的场景（单请求在线聊天、流式输出），这部分开销是实打实的——这也是后来 vLLM 陆续接入 FlashAttention、FlashInfer 等更优 kernel 后，PagedAttention kernel 逐渐退居二线的原因（现在的 vLLM 默认用 FA 系列的 PagedAttention 变体，但分页内存管理本身保留至今）。

2. 块大小是永远存在的折中。 16 是”多数场景最优”，但长序列（希望块更大省块表开销）和短序列（希望块更小省碎片）的最佳点不同。论文没有提出自适应块大小方案——后来的系统（如 SGLang 的 RadixAttention、FlashMLA 的 64、DeepSeek 系列）各自选择了不同块大小，但没有统一答案。

3. 换出/重算的取舍依赖硬件。 论文结论”重算开销不超过换出的 20%“是在 A100 + PCIe 上测的。如果换成 HBM 更大的卡、PCIe 5.0/6.0（带宽翻倍）、或 NVLink 直连的 CPU-GPU（如 Grace-Hopper 的 C2C 互联），换出的相对成本会显著下降，结论可能反转。vLLM 至今保留两种机制供用户选择，就是这个原因。

4. 它只解决”内存管理”，不解决”内存不够”本身。 PagedAttention 把浪费从 60%-80% 压到 4% 以下，但 KV Cache 的体积（每 token 每层若干 KB）没有变小一字节。上下文变长、并发变大，最终还是装不下——所以才需要后续的 KV 压缩（MLA、KV 量化）、KV 驱逐（QEvict）等手段在”内容”层面再压缩。PagedAttention 是这些技术的地基：它让”KV Cache 是一块块可独立管理的小内存”这件事成为可能，后续所有”哪块该保留、哪块该驱逐、哪块该压缩”的精细操作都是在这块地基上盖楼。

5. 对非 LLM 负载没有普适性。 论文 §8 自己划清了边界：分页思想适合”内存需求动态不可预知 + 性能受显存容量限制”的负载。DNN 训练张量形状静态，内存分配可以在编译期优化；非 LLM 的推理服务往往 compute-bound，提高内存效率转化不成吞吐。对这些场景引入分页的间接寻址反而是负优化。

6. 后续演进（简要）：vLLM 在 PagedAttention 之后又发展出前缀缓存（Prefix Caching，用哈希自动识别共享前缀、按块缓存）、Chunked Prefill（把长 prefill 切成块与 decode 混合调度）、FP8 KV Cache 量化、以及接入 FlashAttention-3 等更快的注意力后端——这些都是在”分页 KV Cache”这一层之上叠加的优化。今天主流推理引擎（vLLM、SGLang、TensorRT-LLM、llama.cpp 等）无一例外采用分页式 KV Cache 管理，PagedAttention 已经是整个 LLM 推理生态的公共基础设施。

小结#

把 PagedAttention 的全部机制收进一张表：

机制	解决的问题	手段	代价
分块存储	连续预分配的浪费	KV Cache 切成 16-token 块，非连续存放	块表间接寻址
块表	逻辑连续 ↔ 物理任意	逻辑块→物理块映射 + 填充计数	每读一块查一次表
按需分配	预分配最大长度	块写满才分配新块	无（仅尾部块内浪费 <4%）
引用计数 + 写时复制	序列间共享的安全写	共享只读块，写时复制一块	偶尔一次块复制
统一内存池	外部碎片	所有序列共享等大块的池	无
全有或全无抢占 + 重算/换出	显存耗尽时的公平调度	整体驱逐序列，重算或换到 CPU	重算占算力/换出占 PCIe
fork/append/free	任意解码算法	三个原语组合	无

PagedAttention 给我们的最大启示是一个视角的转换：KV Cache 不是”一个张量”，而是”一批可寻址的内存单元”。一旦接受这个视角，操作系统的整套内存管理工具箱（分页、页表、写时复制、换页、共享库）就都可以为推理服务所用——这正是这篇 SOSP 2023 论文的含金量所在：把五十年前操作系统解决”内存碎片与共享”的成熟思路，平移到一个崭新的、吃内存吃到吐的工作负载上。今天再看，PagedAttention 的”分页”早已成了推理引擎的默认设定，就像虚拟内存之于现代 OS 一样理所当然——但回看 2023 年，这个”把页表搬进显存”的灵感，是整个 LLM 推理优化时代的起点。

音乐

音乐