08. PagedAttention：把 KV Cache 分页管理
第 4 篇结尾留下了一个问题：账面上一张卡能装下 40 万个 token 的 KV，早期的推理系统却只能用上其中一小部分。这一篇先看浪费是怎样产生的，再看 vLLM 怎样借用操作系统管理内存的思路，把 KV Cache 切成固定大小的“页”来分配。读完你应该能解释块表、物理块和逻辑块的关系，知道 PagedAttention 省下了哪部分显存、付出了什么代价，以及为什么它是后面前缀缓存和抢占的基础。
浪费从哪里来
一个请求进来时，推理系统并不知道它会生成多长：可能 20 个 token 就结束，也可能写满 2000 个。早期系统的做法是按最大可能长度，为每个请求预留一整块连续的显存。
像餐厅不管来几位客人，都先摆好一张最大的桌子。浪费有三种：
- 预留浪费：请求最终只生成了 100 个 token，却按 2048 预留，后面的座位一直空着，直到请求结束才释放。
- 内部碎片：即使知道最终长度，按固定粒度分配也会在末尾留下用不满的空间。
- 外部碎片：不同请求的预留块大小不一，释放以后在显存里留下零碎的空隙。空隙加起来不少，却拼不成一整块，新请求放不进去。
vLLM 的论文统计了当时的推理系统，KV Cache 显存里真正存放有效 token 状态的比例只有约 20% 到 38%。剩下的六七成，都浪费在上面三种情况里。
借用操作系统的办法：分页
操作系统早就遇到过同样的问题：每个程序都想要一大片连续内存，物理内存却是零碎的。它的解决办法是分页：把内存切成固定大小的页，程序看到的是连续的“虚拟地址”，实际数据分散在物理内存的各个页里，由一张页表记录对应关系。
PagedAttention 把这个办法用在 KV Cache 上：
- 把 KV Cache 的显存切成固定大小的物理块（block），每块存固定数量 token 的 KV，比如 16 个。
- 每个请求的 KV 在逻辑上是连续的：第 0—15 个 token 在逻辑块 0，第 16—31 个在逻辑块 1，以此类推。
- 每个请求有一张块表（block table），记录“逻辑块 i 存在哪个物理块里”。物理块可以分散在显存的任何位置。
块是按需分配的：请求开始时只分配 Prefill 需要的块；Decode 过程中，当前块写满了，再从空闲块里拿一个新的。请求结束后，它的块全部归还给空闲列表，任何新请求都能用。
浪费降到了多少
分页以后，每个请求最多只浪费最后一块里没填满的部分，也就是不到一个块的 token 数。块大小为 16 时，平均每个请求只浪费约 8 个 token 的空间。
代入我们的例子算一下。Llama-3.1-8B 每个 token 的 KV 是 128 KiB，一个 16 token 的块存全部 32 层，就是：
text
16 × 128 KiB = 2 MiB / 块
50 GiB 的 KV 空间 ÷ 2 MiB ≈ 25,600 个块一个生成了 1000 个 token 的请求需要 63 个块，最后一块只用了 8 个位置，浪费 8 × 128 KiB = 1 MiB，占它总占用的不到 1%。外部碎片则完全消失：所有块大小相同，任何一个空闲块都能分给任何请求。
论文报告，vLLM 的 KV Cache 中约 96% 的空间存放着有效的 token 状态，浪费接近于零。省下来的显存可以同时容纳更多请求，批变大了，吞吐也跟着上去：在相同延迟水平下，vLLM 的吞吐是当时主流系统的 2 到 4 倍。
为什么叫 PagedAttention
分页带来一个新问题：一个请求的 KV 不再连续存放，而普通的注意力计算假设 K、V 是一整块连续的数组。
所以 vLLM 重写了注意力的 GPU 内核：计算时按块表找到每个逻辑块对应的物理块，从分散的位置读出 K、V，再做注意力。这就是 PagedAttention 这个名字的由来，它首先是一个能读分页 KV 的注意力算子，其次才是一套显存管理方案。
写入时也要按块表定位。新 token 的 K、V 算出来后，要写到“它所在的物理块的第几个位置”。nano-vllm（第 13 篇）里这一步只有一行公式，每个 token 对应一个槽位（slot）：
python
slot = block_table[逻辑块号] * block_size + 块内偏移然后用一个小的 GPU 内核，把每个 token 的 K、V 写到对应槽位。
分页的代价是读取时多了一次查表、数据不再连续。现代的注意力内核（FlashAttention、FlashInfer 等）都原生支持分页的 KV，这部分开销已经很小。
块多大合适
块大小是一个权衡：
| 块大小 | 好处 | 代价 |
|---|---|---|
| 小（如 16） | 末尾浪费少，前缀共享的粒度细 | 块表更长，内核读取更零碎 |
| 大（如 256） | 块表短，内核读取效率高 | 末尾浪费多，只有完整块才能共享 |
vLLM 在 NVIDIA GPU 上常见的块大小是 16，具体由注意力后端决定，比如 DeepSeek 的 MLA 后端用 64；nano-vllm 默认用 256，换来实现上的简单。一般用引擎的默认值即可。
分页还顺带解决了什么
块表让“共享”变得很自然：两个请求的块表可以指向同一个物理块，只要给物理块记一个引用计数，记录有几个请求在用它。
- 并行采样：同一个问题要生成 3 个候选回答（请求参数
n=3），三份回答共享同一段输入，输入部分的块只存一份，引用计数为 3，各自生成的内容再分配各自的新块。PagedAttention 论文里还设计了写时复制（copy-on-write）：共享块需要被其中一个请求修改时，先复制一份再改，用来支持束搜索这类在块中间分叉的场景。当前 vLLM 的 V1 引擎做了简化，只共享写满的块，n>1的请求拆成几个独立的子请求，靠前缀缓存共享输入部分，不再需要写时复制。 - 前缀共享：不同用户发来的请求开头相同（比如同样的系统提示），它们的前几个块可以指向同一份物理块。这是第 10 篇的主题。
- 抢占：显存不够时，可以把某个请求的块全部释放，以后重新计算；或者把块的内容换到 CPU 内存，以后再换回来。块是统一大小的，换进换出都很方便。这是下一篇的内容之一。
它没有解决什么
分页提高了显存的利用率，没有增加显存的总量。50 GiB 的 KV 空间仍然只能装 40 万个 token；请求太多、太长时，空闲块照样会用完。那时调度器必须决定：让新请求等着，还是把正在运行的某个请求暂停。
PagedAttention 也不改变注意力的计算量。Decode 每一步仍要读全部历史 KV，分页只是改变了它们存放的位置。
早期系统按最大长度为每个请求预留连续显存，造成大量预留浪费和碎片；PagedAttention 把 KV 切成固定大小的块，用块表把逻辑上连续的 KV 映射到分散的物理块，按需分配，把浪费压到每个请求最后一块的空余。块表和引用计数又让共享、写时复制和抢占变得容易。
显存利用率提上来以后，下一个问题是怎样把这些空间用好：多个请求怎样一起算，有人结束后空位怎样立刻补上，显存不够时让谁让路。下一篇讲连续批处理与调度。