PagedAttention：让 KV cache 按需生长
token 要按顺序读，显存不必连成一整片。
按 → 推进 · 动画可播放、拖动和倒回
2026-10-20 · 图中的容量、时长与 token 均为教学示意
答案有多长，开始时并不知道
生成一个 token，就要把它的 K、V 留下来，供后续 token 读取。
如果每个请求一开始都预留最大长度，短答案也会占着一大片空地。
这里两条请求实际只用了 8 个位置，却预留了 24 个。空位挡住了其他请求。
每个方格代表一个 token 在各层的 KV；图中容量仅用于演示。
先数清楚：一个 token 要留下多少数据
普通 GQA 的 K、V 各有一个四维张量。这里只算 KV，不把权重、临时 workspace 混进来。
| 符号 | 含义 | 教学模型 |
|---|---|---|
| L | Transformer 层数 | 32 |
| Hkv / d | 每层 KV 头数 / 每头宽度 | 8 / 128 |
| b | 每个元素的存储字节数 | BF16：2 B |
若做张量并行，用每张卡实际存储的 KV 头数代入；复制的 KV 不能按卡数再除一次。
128 KiB：每新增一个位置的账单
前面的 2 是 K 和 V。代入：2 × 32 × 8 × 128 × 2 = 131,072 B = 128 KiB。
逻辑块装 B 个 token 的 KV。所有层通常共用 token→物理块编号，底层各层有自己的 KV 存储。
计量统一用 KiB / MiB / GiB：分别是 2¹⁰ / 2²⁰ / 2³⁰ B。不要把 GB 的十进制单位混入容量题。
24 GiB 的 KV 池，能同时容纳多少请求？
延续上页模型，块大小 16，池内共有 24 × 1024 / 2 = 12,288 个物理块。
47 条占 12,079 块，还剩 209 块。第 48 条需要 257 块，差 48 块；“总 token 数看着还够”不足以证明能放下。
这里每条长度固定、不共享块；真实服务还要留增长余量，pool 容量应来自运行时完成权重和 workspace 预留之后的测量。
顺序留在表里，数据放进空闲块
先把序列切成小块：每块放 4 个 token 的 KV。最后一块可以暂时没装满。
block table 记录“逻辑第几块，对应物理哪一块”：这里是 [P5, P1, P7]。
物理块可以散落在显存里。请求看到的 token 顺序仍然是 0、1、2……
教学块大小 B = 4；实际引擎按模型与 kernel 选择块大小。
读 token 6，先查表，再找偏移
attention 仍然按逻辑序列读历史。分页改变的是地址计算。
token 6 落在逻辑块 1。查表得到 P1，再取 P1 里偏移为 2 的 K、V。
PagedAttention kernel 一边按表定位，一边计算 attention。无需先把整个历史复制成连续数组。
token 编号从 0 开始，token 6 是第 7 个；图中只画一层、一个 KV head 的寻址。
把 token 6 变成真正的内存地址
教学布局：K 和 V 分开，每个 K 池按 [物理块, 块内位置, KV 头, 头内维度] 连续存放。
先做整除和取余，再查 block table；最后按 stride 展开。实际 kernel 可重排维度，但映射必须等价。
分页以后，attention 仍然按完整历史归一化
for logical_block in range(ceil(length / B)):
physical = block_table[logical_block]
K_tile, V_tile = load_kv(physical)
valid = logical_block * B + arange(B) < length
scores = (q @ K_tile.T) * scale
online_softmax_update(scores, V_tile, mask=valid)尾块里的未写位置必须 mask。每块独立 softmax 再把结果相加，会丢失块之间的归一化权重。
block table 是整数元数据，通常远小于 KV。性能更依赖合并访存、向量化和跨块归约。
写满一块，再拿下一块
P5 已装满 4 个 token。下一次 decode 会为 token 4 生成新的 K、V。
从空闲池取出 P2，把新 token 的 KV 写进去。原来的 P5 不需要搬家。
block table 追加一项。以后继续填 P2，直到它也装满。
一般只有尾块会留下未用槽位；不同模型的分层存储细节由引擎处理。
请求结束，块就能交给下一位
一个请求结束后，它独占的 KV 不再需要。这里先看不保留 prefix cache 的情况。
移除 A 的 block table，P5、P2 回到空闲池。无需把其他请求挪到一起。
B 可以立刻拿走空闲块。分页让“结束、释放、再使用”变成小块之间的交接。
启用 prefix caching 时，引用计数归零的满块可以先保留内容，等有新需求再驱逐。
只读时共用，要写入时再分开
同一提示词生成两种续写时，两条分支可共享已算好的 KV。这里共享的尾块还剩一个空位。
A、B 要写入不同 token，不能同时改同一尾块。给 B 分配 P8，复制已有的 a、b、c。
A 在 P3 写 X，B 在 P8 写 Y。更早的完整只读块仍可继续共享，这就是写时复制。
这是分支采样的写时复制示意；满块 prefix cache 命中通常直接共享，不必复制。
引用计数管理“谁还在读”，长度管理“哪里能写”
每个请求
block_table：逻辑块到物理块
length：已写 KV 的 token 数
状态：运行 / 等待 / 完成
每个物理块
refcount：活跃请求引用数
valid length：尾块有效范围
free queue：可再分配块
没有 prefix cache 时，refcount 变成 0 可以直接归还。启用 prefix cache 时，还可能留下有效 hash 和内容，直到被驱逐。
引用计数不是 token 数；同一块被两个请求读取，哪怕只写了三个 token，refcount 仍然是 2。
一次写入，为什么会先少掉一个空闲块？
B = 4，两个请求共享未满的尾块 P2。A 要继续写：先分配并复制 P3，再把 A 的映射切过去，最后写 1001。
如果尾块已经满，下一 token 直接申请新块；不用复制已经写满的前缀。
先确保分配成功，再改变可见状态
if tail_is_full:
new = allocate_or_fail()
table.append(new)
elif refcount[tail] > 1:
new = allocate_or_fail() # 失败时旧映射完全不动
copy_valid_kv(tail, new)
wait_until_copy_is_visible()
refcount[tail] -= 1
table[-1] = new
write_token(table[-1], token)GPU stream / event 要保证 copy 和 write 的顺序。请求取消、异常返回也要走释放路径；只靠正常完成释放会慢慢漏掉整个池。
三个空闲块，四个请求同时跨边界
池里只剩 3 块。A、B、C、D 本轮各需要一个新块，token 预算却足够安排四人。
可行的调度
本轮只运行其中 3 条，另一条等待；或者先抢占一个可释放足够块的请求，再分配。
必须避免
先给四条都追加映射，再在 GPU kernel 中发现地址无效。容量检查要在发布这轮 block table 前完成。
不能回收仍被其他请求引用的共享块；“抢占了一个请求”不等于“释放了它表里的所有块”。
腾出显存以后，还要付一次恢复成本
教学估算：某条请求已处理 4,000 个 token；保留 token ID，释放 KV，之后以 20,000 token/s 重新 prefill。
若改为搬运 500 MiB KV，链路有效带宽 25 GiB/s，单向理想搬运时间是 500 / 25 / 1024 s ≈ 19.5 ms。
换出再换回合计至少 39.1 ms，还需 CPU 内存、同步和调度。选择重算还是搬运，要测实际开销，并看这段时间会阻塞谁。
把浪费限制在尾块里
长度 10，块大小 4
分配 3 块，共 12 个位置。前两块装满，尾块空 2 个。
每条序列的尾部空位 < 1 块
固定大小块可以互换使用，避免为了连续地址留下大段碎片。
这里计算的是 KV 的 token 槽位，不含 block table、模型权重和临时工作区；共享还会进一步减少实际块数。
把“尾块浪费”算成可观测的数
| 长度 T | B = 16 的块数 | 分配位置 | 尾部空位 |
|---|---|---|---|
| 17 | 2 | 32 | 15 |
| 32 | 2 | 32 | 0 |
| 63 | 4 | 64 | 1 |
| 合计 112 | 8 | 128 | 16 |
每请求最多浪费 B−1 个位置。若长度对 B 的余数均匀，平均浪费 (B−1)/2；真实长度常集中在模板附近，应从 trace 统计。
块越小，省下的是空位，多出来的是管理
| 同一组长度 17 / 32 / 63 | B = 4 | B = 16 | B = 64 |
|---|---|---|---|
| 总块数 | 29 | 8 | 3 |
| 分配位置 | 116 | 128 | 192 |
| 空位 | 4 | 16 | 80 |
| 128 KiB/token 的空位容量 | 0.5 MiB | 2 MiB | 10 MiB |
小块减少尾部浪费，让共享边界更细；大块减少表项、哈希和分配操作，也可能更适合某个 kernel 的访存布局。
选择引擎与 kernel 支持的块大小，再用相同请求轨迹测延迟、吞吐和块占用。不要只最小化浪费率。
容量优化不会抹掉读取历史的成本
教学模型：32 条请求，每条历史长度 4,096，每个历史位置占 128 KiB KV。一次 decode 读取全部历史：
这是按每份 KV 恰读一次的带宽下界，未含权重、通信和 kernel 开销。分页解决放置和共享，attention kernel 才决定读得多有效率。
若跨请求复用了同一物理前缀，缓存层次可能改变实际 HBM 流量；不能直接把逻辑读取量当实测带宽。
占用率只有 70%，为什么请求还是进不来？
| 教学日志 | 读法 |
|---|---|
| 物理块 1,000；活跃 700；闲置缓存 300 | 闲置缓存可驱逐，不等于不可用 |
| 新请求需 350 块；剩余可用 300 | 差 50 块，入场条件不成立 |
| 取消 100 条请求后 refcount 没变 | 引用释放缺失，是泄漏线索 |
先分清 allocated / active / cached / free 的定义，再看拒绝入场的原因。空闲率平均值掩盖了长请求一次所需的大额分配。
核对守恒：活跃唯一块 + 可驱逐缓存块 + 未缓存空闲块 = 物理池容量。
一次有效的块大小实验，固定四件事
输入固定
相同到达时间、输入/输出长度、共享前缀比例、随机种子。先保存 trace，再重放。
预算固定
同一 KV 池字节数、同一调度 token 预算、相同并发限制、相同精度。
输出同时记录：尾部空位 MiB、块表长度、抢占次数、P50/P99 TTFT 与 ITL、完成请求/s。
若把块变小后还提高了 KV 总容量，就无法判断改善来自粒度还是额外显存。
调度决定谁上场，分页决定住哪里
分页让长度不同的请求更容易共存；调度器才能不断让新请求填进空位。
继续看：Continuous batching：每一轮重新组队
Prefix caching：相同的开头，只算一次 · 显存预算
8 GiB 池能容纳多少条 1,025-token 请求？
展开参考解答
① 每 token：2 × 24 × 4 × 128 × 2 = 49,152 B = 48 KiB。
② 每块：16 × 48 = 768 KiB；池有 floor(8 × 2²⁰ / 768) = 10,922 块。
③ 每请求 ceil(1,025 / 16) = 65 块。
④ floor(10,922 / 65) = 168 条，剩 2 块；池还有不足一块的 512 KiB 未分配。
共享尾块之后，谁该释放哪一块？
展开参考解答
① A 写前 COW：申请 P3；P2=1、P3=1，空闲 4。
② A 完成：P3 从 1→0，归还，空闲 5；P2 保持 1。
③ B 完成：P2 从 1→0，归还，空闲 6。
最后比最初多一块，因为最初已有 P2 被占用。直接清空 P2 会破坏 B。
逻辑顺序没错，为什么 attention 输出还是错？
展开参考解答
① 第二块仅位置 4、5 有效；把逻辑位置 ≥ 6 的 score 设为 −∞，不读未初始化值参与计算。
② 各块的归一化分母不同，不能等权平均；使用全局 softmax 或可合并的在线 softmax 状态 (m, l, o)。
验证时随机打乱物理块编号，与连续 KV 的 dense attention 比较；包含长度 0/1/B/B+1 等边界。
用一个小内存池，亲手触发 COW 和 OOM
下载代码后，在保存代码的目录运行：
python3 lab.py --block-size 16 python3 lab.py --block-size 4
B=16：blocks=8，slots=128，useful=112，tail_waste=16。B=4：blocks=29，tail_waste=4；两次均输出 PASS。
先预测块数，再修改 lengths。代码还验证共享后写入互不污染、最后一个引用归还、COW 分配失败不破坏旧映射。把 refs 检查删掉再故意漏一次 release，观察池怎样耗尽。
下载 lab.py · Python 3 标准库从内存池走到推理引擎
- Kwon et al. — Efficient Memory Management for Large Language Model Serving with PagedAttention（SOSP 2023）：分页、块共享与写时复制。
- vLLM：Paged Attention：attention kernel 如何根据 block table 访问 KV。
- vLLM：Automatic Prefix Caching：缓存块的引用、释放与驱逐。