vLLM 将操作系统虚拟内存分页机制引入 LLM KV cache 管理：固定大小 block 替代连续预分配，消除碎片与冗余复制，结合 copy-on-write 实现跨请求共享，使吞吐提升 2–4×。
现有 LLM 推理系统将 KV cache 存储为连续张量，按最大序列长度预分配空间。实际测量表明仅 20.4%–38.2% 的 KV cache 内存被有效利用（§1 / Fig. 2），浪费来自三个来源：
此外，parallel sampling 和 beam search 等解码算法共享部分 KV cache，但连续存储使跨请求内存共享不可能。
PagedAttention：将 KV cache 划分为固定大小的 KV block（默认 block size $B = 16$ tokens），block 可存储在非连续物理内存中。引入 logical block → physical block 的映射表（block table），类似 OS 页表。
核心注意力计算改写为按 block 索引：
$$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})},\quad o_i = \sum_{j=1}^{\lceil i/B \rceil} V_j A_{ij}^\top$$
其中 $K_j, V_j$ 为第 $j$ 个 KV block 中连续 $B$ 个 token 的 key/value 向量。
KV Cache Manager：block engine 在 GPU DRAM 上预划分连续物理 block 池；每个请求按需分配 logical block 并映射到空闲 physical block；新 block 仅在前一 block 填满后分配，使浪费限制在每请求至多一个 block。
Copy-on-Write：parallel sampling / beam search 中多序列共享 prompt 的 physical block（引用计数 > 1），写入时才复制，显著减少内存。
Preemptive Scheduling：FCFS + 全量换出（all-or-nothing eviction），支持 swap-to-CPU 和 recomputation 两种恢复策略。
核心技术壁垒：将 OS 分页思想映射到注意力内核级别——在保持 exact attention 的同时实现非连续 KV 内存访问，并将 block 粒度的内存管理与 GPU warp 级并行性匹配（block size 16 对齐 GPU warp size），使间接寻址开销仅 20–26%。
系统组件：
Scheduling & Preemption：
| 策略 | 机制 | 适用场景 |
|---|---|---|
| Swap | KV blocks 整体换出到 CPU RAM | block size 较大时 PCIe 带宽利用率高 |
| Recompute | 重新 prefill 生成 KV cache | block size 较小时（避免大量小 PCIe 传输） |
| 选择 | 对 block size 16–64 二者相当 | 默认 recompute（开销 < swap 的 20%） |
Memory Management：
| 操作 | 触发条件 | 粒度 |
|---|---|---|
| Allocate | 前一 logical block 填满 | 单 physical block |
| Free | 序列完成或被 preempt | 整个请求的所有 blocks |
| Copy-on-Write | 写入 refcount > 1 的 block | 单 block 复制 |
| 符号 | 含义 |
|---|---|
| $q_i$ | 位置 $i$ 的 query 向量 |
| $K_j, V_j$ | 第 $j$ 个 KV block（$B$ 个 token 的 key/value 矩阵） |
| $B$ | Block size（tokens per block） |
| $A_{ij}$ | 位置 $i$ 对 block $j$ 的 attention score 行向量 |
| $o_i$ | 位置 $i$ 的 attention 输出 |
| $d$ | 隐藏维度 |
PagedAttention 的核心公式将标准 attention 重写为按 block 索引的等价形式：逐 block 取出 $K_j$ 计算 score，逐 block 取出 $V_j$ 加权求和，与标准 attention 数学等价（因为 softmax 分母遍历所有 block）。
论文无独立的 throughput/latency 性能模型。吞吐提升完全通过实验证明，核心论点是：减少内存浪费 → 更大 batch size → 更高 GPU 利用率 → 更高吞吐。
| 模型 | GPU 配置 | KV cache 容量 | Max KV slots |
|---|---|---|---|
| OPT-13B | 1×A100-40GB | 12 GB | 15.7K |
| OPT-66B | 4×A100-40GB | 21 GB | 9.7K |
| OPT-175B | 8×A100-80GB | 264 GB | 60.1K |
工作负载：ShareGPT（真实 ChatGPT 对话，高方差长序列）和 Alpaca（短序列）。请求到达服从 Poisson 分布。
基础 sampling 吞吐（§6.2）：
| 模型 / 数据集 | vLLM vs Orca (Oracle) | vLLM vs Orca (Max) | vLLM vs FasterTransformer |
|---|---|---|---|
| OPT-13B / ShareGPT | 2.2× 更多并发请求 | 4.3× | 高达 22× |
| OPT-175B / Alpaca | 优势较小（compute-bound 场景） | — | — |
Beam search / Parallel sampling 内存节省（§6.3 / Fig. 15）：
| 解码方式 / 数据集 | Alpaca 内存节省 | ShareGPT 内存节省 |
|---|---|---|
| Parallel sampling | 6.1%–9.8% | 16.2%–30.5% |
| Beam search | 37.6%–55.2% | 44.3%–66.3% |
Block size 消融（§7.2）：block size 16 在 ShareGPT 和 Alpaca 上均最优，兼顾 GPU 并行性和低碎片。
Kernel 开销（§7.1）：PagedAttention kernel 比 FasterTransformer 高度优化的 attention kernel 慢 20–26%，但仅影响 attention 层，不影响 FFN 等其他层。
| 步骤 | 论点 | 证据 |
|---|---|---|
| 1 | LLM serving 中 KV cache 占 GPU 内存 ~30%，且动态增长、长度不可预知 | §1 Fig. 1（A100-40GB 内存分布）；§3 OPT-13B 单 token KV = 800 KB |
| 2 | 现有连续分配方案有效利用率仅 20.4%–38.2%，来自 reserved slots / internal / external fragmentation | §1 Fig. 2（profiling）；§3.1 Fig. 3（三种浪费示意） |
| 3 | OS 分页思想可消除碎片：固定大小 block + 非连续映射 + 按需分配 | §4.1 PagedAttention 算法等价性证明；§4.2 block table 机制 |
| 4 | Copy-on-Write 实现跨序列 KV cache 共享，beam search 共享率高达 55%+ | §4.4 Fig. 8–10（parallel sampling / beam search / shared prefix 的 block 共享） |
| 5 | 减少内存浪费 → 更大 batch size → 更高吞吐 | §6.2–6.5 全实验（2–4× 吞吐提升）；§7.2 block size 消融 |
| 6 | Kernel 开销可控且仅影响 attention 层 | §7.1 Fig. 18a（20–26% overhead）；§8 讨论 kernel fusion 缓解 |
代码仓库：vLLM