Paged Attention:KV Cache 的虚拟内存
上一篇停在一个尴尬的局面:显存明明还有空,新请求却放不下。Paged Attention 的办法来自操作系统:别再要求一段连续空间,把 KV Cache 切成固定大小的块,用一张表记住每块在哪。
本课颜色约定Query 钴蓝Key 镉橙Value 绿块表 / 查表 品红prompt token生成的 token
## 问题回顾:连续分配为什么会碎
[03 课](03.html)的图 5 里,碎片有两种来源:
- **预留了没用上**:不知道对话会多长,只能按上限预留一整段,实际只用掉一截。
- **释放后留下空洞**:请求有长有短、先后结束,空闲空间被切成大小不一的几段,新请求要的那段连续空间凑不出来。
两种浪费的根子是同一个要求:**每个序列的 KV Cache 必须放在一段连续的显存里。**
## 借操作系统的思路:分页
操作系统早就遇到过一模一样的问题:每个进程都想要一大段连续内存,物理内存却被切得七零八落。它的解法是**虚拟内存分页**:进程看到的地址是连续的,但背后被切成固定大小的页,每一页可以放在物理内存的任何位置,由一张**页表**记录映射关系。
vLLM(Kwon 等,2023)把这套思路搬到了 KV Cache 上:
- 显存预先切成很多**物理块**(physical block),每块能放固定数量 token 的 K 和 V(vLLM 默认 16 个)。
- 每个序列的 KV Cache 在逻辑上是连续的**逻辑块** 0、1、2……
- 每个序列有一张**块表**(block table),记录「第几个逻辑块放在哪个物理块」。
- 序列长到当前块装满时,才从空闲列表里**再要一块**,要到哪块都行。
图 1 逻辑上连续,物理上分散,中间隔一张块表(示意:一块 4 个 token)
这样一来,「需要一段连续空间」这个要求就消失了:只要空闲块的**总数**够,新请求就能放下,块在哪里无所谓。浪费也只剩下每个序列**最后一块里还没填满的那几格**,最多不到一块。
## 同一个场景,换成分页
把 03 课图 5 的四个请求原样搬过来,这次按块分配:
图 2 分页后:没有预留,也没有凑不出的连续空间(示意:一块 2 格,和 03 课图 5 同样 24 格显存)
vLLM 论文报告,用这种方式管理后,KV Cache 的显存浪费从此前系统的 60–80% 降到 **4% 以下**。省出来的显存可以同时容纳更多请求,同样延迟下吞吐量是 FasterTransformer、Orca 等系统的 2–4 倍。
## Attention 怎么读分散的块
K、V 不再连续了,attention 怎么算?Paged Attention 的 kernel 一块一块地读:每处理一个逻辑块,先查块表拿到物理块号,再去那里取出这一块的 K 和 V,算完这一块再取下一块。块内是连续的,块之间靠查表跳转。
图 3 新 token 的 Query 沿着块表,一块一块地读 K、V
一块一块地算、最后合成整行的结果,正是 [02 课](02.html)的分块 + online softmax 那一套,所以结果和连续存放时**完全一样**,不是近似。代价是多了一次查表的间接寻址,实际测下来开销很小。
## 共享:同一段 prompt 只存一份
分页还带来一个意外的好处:**块可以被多个序列共享**。
比如让模型对同一个 prompt 生成多个候选回答(parallel sampling)。这些序列的 prompt 部分一模一样,K、V 也一模一样,没必要各存一份:让它们的块表指向同一批物理块,每个物理块记一个**引用计数**(有几个序列在用它)。
麻烦出在 prompt 的最后一块往往没填满,各个序列生成的新 token 要往里写,而它们写的内容不同。这时用操作系统的另一个老办法:**写时复制**(copy-on-write)。某个序列要往一块里写之前,先看引用计数:
- **大于 1**:还有别人在用,先把这块复制一份给自己,改自己的块表指向副本,原块引用计数减 1,再写。
- **等于 1**:只剩自己在用,直接写,不用复制。
图 4 两个候选回答共享 prompt 的块,写的时候才复制(示意:一块 4 个 token)
装满的块永远不会再被写,所以可以一直共享下去;需要复制的只有「没填满、又要被写」的那一块。beam search 里多个候选共享前缀、以及多个请求共用同一段 system prompt,用的都是这套机制。
## 块大小怎么选
块大小是一个取舍:
- **块太小**:最后一块的浪费很少,但块表变长,kernel 每读一小块都要查一次表、做一次跳转,GPU 读得零碎,效率下降。
- **块太大**:查表少、每次读得多,但最后一块平均空着的格子变多,短请求尤其吃亏,又回到了预留浪费的老路。
图 5 同样三条序列,换三种块大小
vLLM 默认的 16 是一个折中:浪费已经很小,块又大到足够让 GPU 一次读一整段。
到这里,推理系统这一侧的基础打完了。下一篇转向架构:2025–26 年的主流模型已经不再每一层都用标准 attention,有的层只看附近的窗口,有的层换成固定大小的状态,有的层只挑一部分 token 看。我们先画一张地图。(「不同请求共享前缀」的 Radix Attention 放在第 11 课。)