输出长度事先未知，旧系统按最大长度预留一整段连续显存；论文实测只有 20.4%–38.2% 的 KV 内存真正存了 token 状态。 PagedAttention 把每个序列的 KV Cache 切成固定大小的块，逻辑块经 block table 映射到任意物理块，从而按需分配、跨序列共享。 代价是 attention kernel 多一层间接寻址（延迟高 20–26%），以及每个序列最后一块的内部碎片。
旧系统的浪费不止一种：按最大长度预留未来槽位、实际长度小于预留长度造成的内部碎片、以及 buddy allocator 产生的外部碎片。论文 Fig. 2 的 profiling 里，有效 KV 内存最低只有 20.4%。
PagedAttention 的关键不是把 KV Cache 搬走，而是取消「必须连续」这个约束：逻辑块按 token 顺序生长，block table 把每个逻辑块映射到任意物理块；attention kernel 按块分别读取，因此物理块可以不连续。
共享是 block table 的自然结果：多个逻辑块可以指向同一个物理块，用 ref count 记录引用；写入共享尾块时做 block 级 copy-on-write。parallel sampling、beam search、shared prefix 都建立在这一个机制上。
读这篇要分清两个时代：论文的默认块大小是 16，抢占可选 swap 或 recompute；当前 V1（commit e740bad）的 CacheConfig 默认是 64，block table 在 worker 侧，抢占路径是释放块后重算。算法思想没变，工程实现已经分叉。
读完这节你应该知道：KV Cache 为什么随请求线性膨胀，以及三种浪费各自发生在哪。
以 OPT-13B 为例，单个 token 的 KV Cache 约 800 KB：22（key/value 两组）× 5120（hidden size）× 40（层）× 2（FP16 字节）。序列长到 2048 个 token，一个请求就要 1.6 GB（§3）。A100 的显存是几十 GB 量级；即使全部拿来放 KV，也只能同时容纳几十个请求。serving 的吞吐因此是 memory-bound，不是 compute-bound。
更麻烦的是输出长度不可预知。旧系统只能按请求的最大可能长度预分配一段连续显存，于是出现三种浪费（Fig. 3）：
给未来生成的 token 留的位置。它最终会被用到，但在请求的整个生命周期里一直占着，别的请求用不了。
请求实际长度小于预分配的最大长度，尾部槽位永远空着。只有请求结束后才能确认，是纯浪费。
不同请求的 chunk 大小不一，buddy allocator 留下的空洞无法被后续请求利用。这些空洞永远不会用来存生成的 token。
论文的 profiling 把这三类浪费加在一起：在 §6.2 的实验里，旧系统只有 20.4%–38.2% 的 KV 内存真正存了 token 状态（§3.1 / Fig. 2）。最差情况下浪费 79.6%（100 − 20.4）。压缩（compaction）可以消除外部碎片，但 KV Cache 太大，在性能敏感的 serving 系统里搬运不现实；而且它仍然解决不了跨序列共享（§3.1）。
只要分配单位从「整个请求的最大长度」变成「固定大小的块」，系统就不需要在请求开始时知道它会生成多少 token；块可以随生成逐个追加，也可以在请求之间共享。
读完这节你应该知道：连续分配与分页的分界线，以及 OS 的虚拟内存为什么可以搬过来。
当时的 serving 系统（Orca、FasterTransformer）把每个请求的 KV Cache 存成一个连续的 tensor，因为大多数深度学习算子要求 tensor 在内存里连续。输出长度又不可知，所以只能按最大序列长度静态预留。于是分配器看到的是一个个大小不一的连续 chunk，而不是可以任意拼接的页。
kernel 可以直接按基址 + 偏移寻址，实现简单；代价是请求开始时就得决定 chunk 多大。
卡点：预留、内部碎片、外部碎片三者叠加；不同序列的 KV 存在各自连续空间里，无法共享。
固定大小的块可以散落在物理显存任意位置；逻辑块按 token 顺序编号，block table 负责翻译。
代价：每次 attention 读 KV 都要先查 block table；kernel 要处理非连续块和可变序列长度。
这正是 OS 虚拟内存的做法：进程看到连续的逻辑页，物理页可以任意映射；页表负责翻译，物理页按需分配。论文把三个对象一一对应起来——块 = 页，token = 字节，请求 = 进程（§4.2）。区别在于，OS 的页表由硬件 MMU 走，vLLM 的 block table 由 attention kernel 自己查。
所以 PagedAttention 不是「把 KV Cache 变成连续」，而是反过来：让 attention 能直接读非连续块。只有 kernel 支持了，分页内存管理才有意义；否则 block table 只是摆设。
读完这节你应该知道：PagedAttention 的块级注意力怎么算、block table 存什么，以及共享与 COW 如何工作。
论文把每个序列的 KV Cache 切成固定大小的 KV block，每块装 B 个 token 的 key/value 向量。第 j 个 key block 记为 Kj，value block 记为 Vj。注意力不再一次读完整条序列，而是按块累加：
每个请求维护一张 block table：第 i 个逻辑块指向哪个物理块，以及这个逻辑块已经填了多少个位置（§4.2）。逻辑块从 0 开始，随着新 token 从左到右填充；最后一个逻辑块可能只填了一部分，剩余槽位留给后续生成。物理块由 GPU 上的 block engine 统一划分成固定大小，因此可以按需分配，不需要为整个请求预留最大长度。
prompt 有 7 个 token，块大小 B=4：逻辑块 0 装满 4 个，逻辑块 1 装 3 个、留 1 个空槽。vLLM 把它映射到物理块 7 和 1；第一次 decode 直接用逻辑块 1 的空槽；第二次 decode 时逻辑块 1 满了，才分配新的物理块 3。整个过程没有按 2048 预留。
共享也来自这张表。多个逻辑块可以映射到同一个物理块，物理块上记一个 ref count。写入共享块时不能原地改，否则会污染其他序列；vLLM 做 block 级 copy-on-write：复制出一个新物理块，把 ref count 减一，再往新块里写。Fig. 8 的 parallel sampling 就是两个 sample 共享 prompt 的逻辑块 0、1，物理块 7、1 的 ref count 都是 2；A1 写尾块时复制出物理块 3，A2 再写时 ref 已经降到 1，直接原地写。
下面的模拟器把 Figure 8 的两个 sample 换写成两个请求 A/B——两者共享同一段 7-token 前缀，用同一套 block table 语义走一遍分配、共享、COW 和释放；块号仍沿用 7/1/3。
prompt 7 个 token 切成 2 个逻辑块。A/B 的逻辑块 0、1 都映射到物理块 7、1，ref=2；尾块只填了 3/4，标记为 COW。
占用物理块 2 · 共享块 2 · 相对无共享节省 50.0%
模拟器取 B=4、prompt 7 token、8 个物理块；把 Figure 8 的两个 sample 改写成请求 A/B，物理块 7/1/3 沿用 Figure 8 的编号。第 ④ 步的 4/5 是页面为展示「各自新增块」补的，不在 Figure 8 里。
口径：块节省 =（逻辑映射数 − 唯一物理块数）/ 逻辑映射数 × 100%，不是按字节算。逻辑映射数 = A、B 当前持有的逻辑块总数；唯一物理块数 = 两个请求实际占用的不同物理块数。
组 1：A、B 各生成 1 个 token。共享期有 2×2 = 4 个逻辑映射，唯一物理块 2 个（7、1），节省 4−2 = 2 块，2/4 = 50.0%。A 触发 COW 后：A 持有 7、3，B 持有 7、1；唯一物理块 3 个（7、3、1），逻辑映射仍是 4 个，节省 4−3 = 1 块，1/4 = 25.0%。
组 2：A、B 各生成 2 个 token。尾块写满后各自新增一块：A 持有 7、3、4，B 持有 7、1、5；逻辑映射 3×2 = 6 个，唯一物理块 5 个（7、3、4、1、5），节省 6−5 = 1 块，1/6 = 16.7%。与 JS 在第 ④ 步的读数一致。
COW 只复制一个块（Figure 8 中复制物理块 1 的内容到物理块 3），不是复制整条 prompt；这也是论文强调「block 级 copy-on-write」的原因（§4.4）。
读完这节你应该知道：attention kernel 为分页付出什么代价、block size 如何权衡，以及论文与 V1 在哪些实现上分叉。
分页不是免费的。PagedAttention kernel 要读 block table、按块跳转、处理变长序列，比连续内存的 attention 多出分支和间接寻址。论文的 microbenchmark 显示，attention kernel 的延迟比高度优化的 FasterTransformer 高 20–26%（§7.1 / Fig. 18a）。这个开销只落在 attention 算子，不落在 Linear 等算子上；端到端仍然被显存节省带来的更大 batch 抵消。
block size 是一个双向权衡（§7.2 / Fig. 18b）：太小，GPU 读 KV 的并行度不够；太大，内部碎片增加，能共享的边界也变粗。论文的结论是 16 在大多数负载上足够大、又足够小；ShareGPT trace 上 16–128 都能工作，Alpaca 上 16/32 表现好，更大的块会显著退化，因为序列比块还短。论文因此把 vLLM 的默认块大小设为 16。
docs.vllm.ai/en/latest/design/paged_attention.html 开头明确写着 «This is a historical document based on the original paper for vLLM. It no longer describes the code used in vLLM today.» 所以下面涉及当前行为的部分，一律以 commit e740bad 的源码为准，不拿 2023 年的文档当现状。
V1 的实现可以概括成一条链：
KVCacheManager.allocate_slots 计算这次要新增多少 token、需要多少块，再从 BlockPool 取块（vllm/v1/core/kv_cache_manager.py:401；vllm/v1/core/block_pool.py:681）。KVCacheBlock 带 ref_cnt 和 block_hash（vllm/v1/core/kv_cache_utils.py:166）。前缀命中时 touch 增加引用（block_pool.py:774）；请求结束或抢占时 free_blocks 减引用（block_pool.py:798）。cache_full_blocks 把满块的哈希写进缓存（block_pool.py:203）；后续请求用同样的 token 前缀就能命中同一物理块。new_block_ids（vllm/v1/core/sched/output.py:146-156）；worker 的 BlockTable 把物理块号追加成一行 dense tensor（vllm/v1/worker/block_table.py:49），再用 compute_slot_mapping 根据 token position 算出每个 token 的 (block, offset)（block_table.py:153；vllm/v1/worker/gpu_model_runner.py:2250）。_preempt_request 释放请求的块，把 num_computed_tokens 置 0，然后把请求放回 waiting queue（vllm/v1/core/sched/scheduler.py:1876,1899）。
V1 的 CacheConfig.DEFAULT_BLOCK_SIZE 是 64（vllm/config/cache.py:185），不是论文的 16。后端还会约束可用块大小：FlashAttention 后端声明接受 MultipleOf(16) 的块大小（vllm/v1/attention/backends/flash_attn.py:357,367）。因此读论文的 16-token 实验时，不要把它和今天 V1 的默认值混在一起。
把论文语义与 V1 当前实现并列，差异集中在五处：
| 维度 | 论文 / 原始 vLLM | V1（commit e740bad） |
|---|---|---|
| 默认块大小 | 16 token（§7.2） | 64 token（vllm/config/cache.py:185） |
| 逻辑 → 物理映射 | 每请求一张 block table，条目含物理块号 + 已填位置数（§4.2） | 调度器每步下发 new_block_ids；worker 的 BlockTable 只存物理块号，槽位由 position 算（sched/output.py:146-156；worker/block_table.py:49,153） |
| 共享 | ref count + block 级 COW；shared prefix 可预留物理块（§4.4 / Fig. 8, 10） | block hash 前缀缓存 + ref_cnt；本 commit 还有部分块 COW 路径（block_pool.py:203；single_type_kv_cache_manager.py:460） |
| 抢占 | swap 到 CPU，或重算（§4.5） | 释放块 + num_computed_tokens=0 + 重算（sched/scheduler.py:1876-1899） |
| block table 位置 | KV manager 维护映射，workers 共享（§4.6） | 调度器不持久化 dense table；worker 侧张量（worker/block_table.py:49） |
有一处容易误读：V1 目录里存在独立的 vllm/v1/kv_offload/ 子系统，也有 swap_blocks 相关的 Triton kernel；但这不是论文 §4.5 的抢占式 swapping——论文的 swapping 是「抢占序列 → 把它的块换到 CPU → 需要时换回」，而 V1 调度器的 _preempt_request 走的是释放块后重算。两条路径不能互相代替。
分页消除了「按最大长度预留」造成的巨额内部碎片，但没有消除每个序列最后一块的空槽：序列长度为 L 时，块内碎片是 ceil(L/B)×B − L 个槽位，最多 B−1 个。块越大，单序列尾部的浪费上限越大，能共享的粒度也越粗（§7.2）。下面用 Figure 16 的两个前缀长度 80 和 341 做示例计算——注意论文没有报告这两个百分比，这是页面按 ceil 规则算的演示。
分配 8 块 · 512 槽 · 空 91 槽 · 碎片率 17.8%
口径：每个序列按 ceil(L/B) 分配块，分配槽位 = 块数 × B，空槽 = 分配槽位 − 80 − 341；总碎片率 = 空槽 / 分配槽位 × 100%。这是页面示例，不是论文测得的碎片率。
组 1：B=16。80 token → 5 块、80 槽、0 空槽；341 token → 21 个满块 + 1 个尾块 = 22 块、352 槽、11 空槽。合计 27 块、432 槽、11 空槽，11/432 = 2.5%。
组 2：B=64。80 token → 1 个满块 + 1 个尾块 = 2 块、128 槽、48 空槽；341 token → 5 个满块 + 1 个尾块 = 6 块、384 槽、43 空槽。合计 8 块、512 槽、91 空槽，91/512 = 17.8%。
JS 的滑块在这两组参数下分别输出 2.5% 和 17.8%，与上面的手算逐位一致。B=32 和 B=128 的读数见 LEDGER。
读完这节你应该知道：逻辑块、block table、物理块在一次请求里如何串起来，以及 worker 实际读的是什么。
allocate_slots 把 token 数换算成块数，先看前缀缓存能不能命中，再决定从空闲池取多少块（kv_cache_manager.py:401）。new_block_ids 放进 SchedulerOutput（sched/output.py:146-156）。worker 的 BlockTable 把 ID 追加到请求对应的行。compute_slot_mapping 用 token position 和 block size 算出每个 token 的物理槽位（block_table.py:153）。这样 block table 不需要额外存「已填几个」，位置由序列长度直接决定。free_blocks 把引用减一；ref 归零的未缓存块放回空闲队列前端（LIFO，利于 GPU 局部性），有哈希的缓存块放回后端等待 LRU 淘汰（block_pool.py:798）。这张图也解释了为什么「逻辑块连续」不等于「物理块连续」：逻辑块 0、1、2 是请求视角的顺序，物理块 7、3、4 可以散落在显存任意位置；真正把两者连起来的是中间那张表。请求 B 只需要在它自己的 block table 里把 L0 指向 7，就能和 A 共享同一份 prompt KV。
读完这节你应该知道：论文的节省区间、吞吐数字，以及为什么有些场景收益会消失。
先看共享带来的内存节省。论文在 OPT-13B 上对比了 Alpaca 和 ShareGPT 两条 trace：parallel sampling 只共享 prompt，beam search 还能共享生成中的分支，所以后者的节省明显更大（§6.3 / Fig. 15）。
| 工作负载 | parallel sampling | beam search |
|---|---|---|
| Alpaca | 6.1%–9.8% | 37.6%–55.2% |
| ShareGPT | 16.2%–30.5% | 44.3%–66.3% |
吞吐方面，论文报告的是「在保持相近 normalized latency 的前提下，能承受更高的 request rate」。ShareGPT 基本采样下，vLLM 相对 Orca (Oracle) 高 1.7–2.7×，相对 Orca (Max) 高 2.7–8×，相对 FasterTransformer 最高 22×（§6.2）。beam search 的共享更多，OPT-13B + Alpaca 上相对 Orca (Oracle) 从基本采样的 1.3× 提升到 width=6 的 2.3×（§6.3）。shared prefix 更长时收益更明显：LLaMA-13B + WMT16 英德翻译，80-token one-shot 前缀是 1.67×，341-token few-shot 前缀是 3.58×（§6.4 / Fig. 16）。
| 场景 | 对比对象 | 结果 |
|---|---|---|
| ShareGPT，基本采样 | Orca (Oracle) / Orca (Max) | 1.7–2.7× / 2.7–8× |
| ShareGPT，基本采样 | FasterTransformer | 最高 22× |
| OPT-13B + Alpaca，beam width 6 | Orca (Oracle) | 1.3× → 2.3× |
| LLaMA-13B + WMT16，前缀 80 / 341 token | Orca (Oracle) | 1.67× / 3.58× |
两个反直觉的发现。第一，parallel sampling 的节省只有 6.1%–9.8%（Alpaca），远低于 beam search 的 37.6%–55.2%：前者只共享 prompt，decode 阶段每个 sample 仍要独立块；后者 beam 之间还能共享生成中的块（§6.3 / Fig. 15）。第二，OPT-175B + Alpaca 上 vLLM 相对 Orca 的优势变弱：这个配置显存足够大、序列又短，Orca 也能 batch 很多请求，系统从 memory-bound 变成 compute-bound（§6.2）。分页管理的收益，取决于「显存是不是瓶颈」。
读完这节你应该知道：PagedAttention 解决不了什么，以及什么时候不该把它当成万能药。
B−1 个槽位；块越大，单序列尾部的浪费上限越大，共享粒度也越粗（§7.2）。论文的 16 是在「GPU 并行度」和「碎片」之间的折中；V1 今天默认 64（cache.py:185），与论文的 16 不同。block_pool.py:203），本 commit 还出现了部分块 COW 的路径（single_type_kv_cache_manager.py:460），但都不是语义相似检索。前缀不同，就无法共享。_preempt_request 释放块并把 num_computed_tokens 置 0（scheduler.py:1876,1899）；论文 §4.5 的 swap-out/swap-in 在这个调度器路径里没有对应实现。V1 另有独立的 kv_offload/ 子系统，但不要把它和抢占式 swapping 混为一谈。值得：输出长度方差大、并发请求多、有共享 prompt 或并行采样/beam search，而且系统是 memory-bound。
要谨慎：序列普遍短于块大小、没有可共享前缀、工作负载 compute-bound，或者对 attention 延迟极其敏感。此时先调小 block size，再评估分页的间接寻址是否值得。
最后回到版本问题：论文的 16-token 默认值、swap/recompute 双路径、每请求 block table，是 2023 年 SOSP 版本的语义；今天 V1 的 64-token 默认值、worker 侧 block table、抢占重算，是 e740bad 的实现。两者共享同一个核心思想——逻辑块与物理块解耦——但读数字和读代码时，不能把两个时代的细节混在一起。