PagedAttention

一句话解释

PagedAttention 将请求的 KV Cache 组织为可映射的固定大小块，以减少连续分配带来的碎片与容量浪费。

问题从哪里来

每个请求的 KV Cache 随 token 逐步增长，而最终输出长度事先未知。如果系统先为最大长度预留连续显存，会产生大量未使用空间；如果要求增长时仍保持连续，又容易遇到外部碎片和搬移成本。KV 浪费会直接降低同一时刻可驻留的请求数，使 Continuous Batching 没有足够请求可排。

最小模型

PagedAttention 把一个请求看到的逻辑 token 序列切成固定大小的逻辑块，再用 block table 映射到任意可用的物理 KV block。

1
2
3
请求 A 的逻辑块：  [0] [1] [2]
block table：       0→7 1→2 2→9
物理 KV blocks：   [..][..][A1][..][..][..][..][A0][..][A2]

attention kernel 读取 block table，按逻辑 token 顺序访问可能不连续的物理块。请求增长时只需再分配一个块；结束后释放自己的块，不要求旁边空间连续。

它为什么有效

  • 外部碎片大幅降低，因为请求不再需要一整段连续 KV 空间。
  • 内部浪费被限制在最后一个未填满的块，而不是最大长度预留。
  • 多个序列可通过块引用共享共同前缀，在 copy-on-write 边界后再分叉。
  • 可用 KV 容量增加后，引擎能维持更大的有效 batch，从而间接提升吞吐。

因果链是：块化分配降低浪费 → 同显存驻留更多序列 → scheduler 有更多可批处理 token → 设备利用率上升。PagedAttention 本身不是“让 attention 数学变少”的算法。

与操作系统分页的类比边界

相同点是逻辑地址通过映射表访问非连续物理块，并以固定粒度分配/回收。不同点也很关键：这里管理的是设备上的 KV tensor，block table 要参与 attention kernel 寻址；它不是通用虚拟内存，不意味着发生磁盘换页，也不自动提供进程隔离、缺页处理或持久化。

代价与边界

  • block 太大会增加尾块内部浪费，太小会扩大元数据和寻址开销；粒度是实现权衡。
  • 块化解决分配问题，不消除 KV 随 batch、层数、head 维度和上下文长度线性增长的事实。
  • 更高容量不保证更低延迟；scheduler、kernel、内存带宽和请求分布仍可能成为瓶颈。
  • prefix sharing 只有在前缀真实重复且复用开销可控时才有收益。

与其他节点的关系

  • 向上：vLLM IMPLEMENTS PagedAttention 作为 KV 管理与 attention 执行路径的一部分。
  • 同层：PagedAttention ENABLES 更灵活的 prefix sharing，并 CONTRASTS-WITH 连续预留式 KV 分配。
  • 向下：它 MANAGES KV Cache 的物理布局，但仍 DEPENDS-ON 对应 attention kernel。
  • 系统效果：它与 Continuous Batching 配合；一个提高可驻留容量，一个决定每轮如何使用这些容量。

参考资料

block size 是容量与 kernel 的共同参数

block 太大，最后一个未填满 block 的内部浪费和请求之间的容量粗粒度会变明显；block 太小，block table、地址计算、cache miss 和 metadata 开销会上升。最佳粒度还依赖 Hkv × head_dim × dtype、batch 长度分布和 attention kernel 的向量化方式，因此不能从操作系统页大小直接类推。

可以用一个长度分布做容量估算：对每个请求计算 ceil(seq_len / block_size) 个 block，再将每层 KV 的字节数和 block table/临时 workspace 相加。把理论容量与实际可驻留序列、抢占次数和碎片率对照，才能知道分页是否解决了真实浪费，而不是只证明 allocator 能分配。

prefix sharing 的边界

共享前缀通常让多个请求引用同一批物理 block，分支写入时才 copy-on-write；但引用计数、租户隔离、TTL/淘汰和不同采样/位置配置会决定它是否安全。命中率高也可能没有收益：前缀太短、copy-on-write 很快发生，或 decode 已经受权重带宽限制时，省下的 prefill 不会改变 P99。生产监控应同时记录 prefix hit token 数、共享 block 数、copy-on-write 次数和真实 TTFT。

PagedAttention 解决的是 KV 的物理布局和分配，不负责 token 预算、公平性或跨节点 KV transfer；这些仍由 Continuous Batching 与 Prefill-Decode Disaggregation 的上层策略决定。