Paged Attention

PagedAttention 是一种面向 LLM 服务的 KV Cache 管理与 Attention 访问机制。它借鉴操作系统分页：把每个请求的逻辑 KV 序列拆成固定大小的块，通过 Block Table 映射到不连续的物理显存块，从而按需分配、快速回收，并减少显存碎片。

连续 KV Cache 的问题

自回归生成时，KV Cache 会随序列逐 Token 增长。对于标准 MHA/GQA，单个 Token 的 KV 大小近似为：

$$M_{\text{token}}=2N_{\text{layer}}{H}_{kv}{d}_{head}b$$

其中 $2$ 表示 Key 和 Value，$N_{\text{layer}}$ 是层数，$H_{kv}$ 是 KV Head 数，$d_{head}$ 是 Head 维度，$b$ 是每个元素的字节数。

如果为每个请求预留一块连续的最大长度空间，会产生大量未使用容量；如果只按当前长度分配，序列增长时又可能需要重新分配和复制。请求长度与结束时间不同还会造成外部碎片，降低可用于批处理的 KV 容量。

核心原理

PagedAttention 将逻辑 Token 序列按每块 $B$ 个 Token 划分。请求 $r$ 的 Block Table 记为 $P_r$，逻辑位置 $t$ 对应：

$$i=\lfloor \frac{t}{B}\rfloor ,o=tmodB,\text{slot}(r,t)=(P_r[i],o)$$

$i$ 是逻辑块号，$o$ 是块内偏移，$P_r[i]$ 给出物理块号，物理块不必连续。

Attention Kernel 根据 Block Table 按逻辑顺序读取 Key 和 Value，所以数学上仍然计算相同的 Attention；分页只改变 KV 的物理布局和寻址方式，不会截断上下文或近似注意力。

分配与访问流程

1. 按需分配：请求到达时只分配容纳当前 Token 所需的物理块。
2. 增量写入：Decode 产生新 KV 时写入最后一块；块满后再申请新块。
3. 分页读取：Kernel 通过 Block Table 定位各逻辑块，直接在分页 KV 上完成 Attention。
4. 及时回收：请求完成或被抢占后，释放其不再共享的物理块，供其他请求复用。

只有最后一个块可能未填满，因此内部碎片上限与块大小相关。共享前缀或并行采样还可以让多个逻辑序列引用同一组物理块；若要修改共享块，则需要 Copy-on-Write 或等价的所有权管理。

优势与代价

方面	影响
显存利用率	减少连续预留和外部碎片
动态批处理	请求可以独立增长和结束，页面可快速复用
KV 共享	支持前缀、Beam 或并行采样之间共享物理块
寻址开销	需要维护并传递 Block Table 或 Slot Mapping
Kernel	Attention 必须支持分页 KV 的间接访问
块大小	块太大会增加尾块浪费，块太小会增加元数据和寻址开销

PagedAttention 让 KV 容量更接近实际 Token 数，但不是“完全没有浪费”：最后一块仍有内部碎片，Block Table、本地工作区和对齐也会占用空间。

SGLang 中的实现

SGLang 使用 ReqToTokenPool 保存“请求逻辑位置 → KV 槽位”的映射。page_size > 1 时，PagedTokenToKVPoolAllocator 按页分配 Prefill 和 Decode 的 KV 槽位，并在释放时把槽位还原为页号；Attention Backend 再根据这些索引准备分页 Kernel 所需的元数据。

相关入口：

• ReqToTokenPool
• PagedTokenToKVPoolAllocator
• Paged Allocator 初始化

参考

1. Efficient Memory Management for Large Language Model Serving with PagedAttention
2. vLLM Block Table Source
3. SGLang Paged KV Allocator Source