MiniPaged-Qwen：Paged KV Cache 与 KV Block Manager

2026-07-09 6002 words 12 minutes

大模型推理中，Attention 的计算优化只是问题的一部分。进入 Decode 阶段以后，另一个越来越重要的问题是：历史 Token 的 Key 和 Value 应该放在哪里，又应该怎样管理？

如果只考虑单个请求，这个问题似乎很简单：申请一块连续显存，把每个新 Token 的 K/V 依次写进去即可。但真实推理服务同时存在多个长度不同、结束时间不同的请求。某个请求可能生成 20 个 Token 就结束，另一个请求可能生成 2000 个 Token；如果按照最大长度提前预留连续空间，会浪费大量显存；如果每次空间不足再重新申请更大的连续区域，又会产生数据搬移和外部碎片。

Paged KV Cache 的出发点，就是把“一个 Sequence 的 KV Cache 必须在物理内存中连续”这个限制去掉。

本文先从 KV Cache 为什么存在讲起，然后分析连续 KV Cache 的问题，逐步推导 Paged KV Cache 的地址映射和 Block Manager，最后结合 MiniPaged-Qwen 的实现说明：

SequenceState 管理什么状态；
KVBlockManager 如何分配和释放物理 Block；
slot_mapping 如何把新 Token 写入正确位置；
PagedKVCache 的 Tensor 为什么这样组织；
Decode Attention 如何通过 block_tables 读取物理上离散的历史 KV。

1. 为什么需要 KV Cache

1.1 自回归生成中的重复计算

Decoder-only Transformer 的生成过程是自回归的。假设 Prompt 为：

今天上海的天气

Prefill 完成后，模型生成第一个新 Token。接下来为了生成第二个 Token，当前输入序列已经变成：

今天上海的天气 ...

如果每次 Decode 都重新计算整个历史序列的 K 和 V，那么前面已经计算过的 Token 会被反复计算。

对于第 $l$ 层 Attention，历史序列长度为 $L$ 时，可以写成：

$$ Q_l \in \mathbb{R}^{B\times H_q\times 1\times D} $$

$$ K_l,V_l \in \mathbb{R}^{B\times H_{kv}\times L\times D} $$

Decode 每一步只产生一个新的 Query：

$$ Q_{\mathrm{new}} $$

但 Attention 需要访问全部历史 Key 和 Value：

$$ O

\mathrm{Softmax} \left( \frac{Q_{\mathrm{new}}K_{\mathrm{history}}^T}{\sqrt D} \right) V_{\mathrm{history}} $$

因此最自然的方法是：把历史 Token 已经计算好的 K/V 保存下来。

假设当前已经缓存：

$$ K_{0:L-1},V_{0:L-1} $$

新 Token 到来后只计算：

$$ K_L,V_L $$

然后追加到 Cache：

$$ K_{0:L}

[K_{0:L-1};K_L] $$

$$ V_{0:L}

[V_{0:L-1};V_L] $$

这就是 KV Cache。

KV Cache 减少的是历史 Token 的重复计算，并没有消除 Decode 阶段读取历史 KV 的成本。随着上下文长度增加，每一步 Decode 仍然需要从显存读取越来越长的 K/V。

2. 连续 KV Cache 有什么问题

先考虑最直接的存储方式。对于一个 Sequence，在每一层预留：

$$ K,V \in \mathbb{R}^{H_{kv}\times L_{\max}\times D} $$

假设使用 FP16，每个元素占 2 Byte，一个 Sequence 的全部 KV Cache 大小近似为：

$$ M_{\mathrm{KV}}

2 \times N_{\mathrm{layer}} \times L \times H_{kv} \times D \times 2 $$

最前面的 $2$ 表示 K 和 V，最后的 $2$ 表示 FP16 的字节数。

因此 KV Cache 的显存开销会随着 Layer 数量、Sequence Length、KV Head 数量、Head Dimension 和并发请求数量线性增长。

真正困难的地方并不只是“KV Cache 很大”，而是每个请求的长度动态变化，而且提前无法准确知道最终生成长度。PagedAttention 的原始工作就是针对这种动态增长和收缩的 KV Cache 管理问题提出的：将每个请求的 KV Cache 切分成固定大小的 Block，通过 Block Table 将逻辑 Block 映射到非连续的物理 Block，从而按需分配显存并减少碎片。

2.1 最大长度预留

假设服务器支持：

$$ L_{\max}=4096 $$

请求 A 最终长度只有：

$$ L_A=300 $$

如果直接按照最大长度分配连续 Cache，那么利用率只有：

$$ \frac{300}{4096} \approx 7.3% $$

剩余空间虽然属于请求 A，但实际上永远不会使用。

2.2 动态扩容连续 Buffer

另一种思路是开始只分配较小 Buffer：

[0 ... 255]

长度超过 256 后扩大：

[0 ... 511]

问题是 GPU 上未必存在足够大的连续区域，因此可能需要：

allocate new buffer
        ↓
copy old KV
        ↓
free old buffer

对于不断增长的 Decode Cache，这种搬移成本无法接受。

2.3 多请求结束时间不同造成外部碎片

考虑物理内存：

A A A A | B B B | C C C C | D D

当 B 结束以后：

A A A A | _ _ _ | C C C C | D D

虽然中间有空闲空间，但如果新请求 E 需要更大的连续区域：

E E E E E

仍然无法直接放入。

这就是外部碎片问题。

Paged KV Cache 的核心思路是：不再要求一个 Sequence 的 KV Cache 在物理显存中连续。

3. Paged KV Cache 的核心思想

PagedAttention 的思想受到操作系统虚拟内存和分页机制启发。一个 Sequence 在逻辑上仍然拥有连续的 Token 位置：

token 0, 1, 2, 3, 4, 5, ...

但在物理存储中，它们可以位于不同的固定大小 Block：

logical block 0 → physical block 5
logical block 1 → physical block 2
logical block 2 → physical block 9

假设：

$$ block_size=4 $$

则逻辑位置：

token 0 1 2 3 | 4 5 6 7 | 8 9 10 11

被划分为：

logical block 0 | logical block 1 | logical block 2

地址转换分三步完成。

首先计算 Logical Block：

$$ logical_block

\left\lfloor \frac{token_pos}{block_size} \right\rfloor $$

然后计算 Block 内偏移：

$$ block_offset

token_pos \bmod block_size $$

通过 Block Table 找到 Physical Block：

$$ physical_block

block_table[sequence][logical_block] $$

最后得到线性 Slot：

$$ slot

physical_block \times block_size + block_offset $$

这四个公式就是整个 Paged KV Cache 地址映射的核心。

4. 一张图理解整个 Paged KV Cache

下面这张图把 Paged KV Cache 的地址映射、物理 Block Pool、多个 Sequence、生命周期、碎片和 Linux 虚拟内存类比放到了一起。

下面按照图中的编号逐步解释。

4.1 地址映射：Token Position 如何变成 Slot

图中第 1 部分从 token_pos 开始。

假设：

$$ block_size=4 $$

则：

token_pos:      0 1 2 3 | 4 5 6 7 | 8 9 10 11 | ...
logical_block:  0 0 0 0 | 1 1 1 1 | 2 2 2  2 | ...
block_offset:   0 1 2 3 | 0 1 2 3 | 0 1  2  3 | ...

假设当前 Sequence 的 Block Table 为：

logical block:   0  1  2  3
physical block:  5  2  9  1

现在查询：

$$ token_pos=6 $$

则：

$$ logical_block

\left\lfloor\frac{6}{4}\right\rfloor

1 $$

$$ block_offset

6\bmod4

2 $$

查询 Block Table：

$$ physical_block

block_table[1]

2 $$

所以：

$$ slot

2\times4+2

10 $$

于是逻辑 Token 6 的 K/V 最终写入物理 Slot 10。

注意：Block Table 只完成 Logical Block 到 Physical Block 的映射，Slot Mapping 才是 Token 到最终写入位置的结果。

4.2 物理 Block Pool 和 Free List

图中第 2 部分表示固定大小的 Physical Block Pool。

例如：

physical block 0
physical block 1
physical block 2
...
physical block N-1

每个 Block 包含固定数量的 Slot：

$$ slots_per_block=block_size $$

如果：

$$ block_size=4 $$

那么一个 Physical Block 可以存放连续 4 个 Token 的 KV。

Block Manager 维护：

free_blocks = [0, 3, 4, 6, 8, ...]

新 Sequence 需要 Block 时，从 Free List 取出一个：

allocate_block()

Sequence 结束时，把它拥有的 Block 全部返回：

release_sequence()

这里释放的粒度是整个 Block，而不是单独 Slot。

4.3 多个 Sequence 拥有不同 Block Table

图中第 3 部分强调：Block Table 是 Sequence 私有的地址映射状态。

例如：

seq A: [5, 2]
seq B: [1, 7, 9]
seq C: [2]

它们的物理 Block 不要求连续。

如果 Sequence A 长度为 $7$，Block Size 为 $4$，需要：

$$ \left\lceil\frac{7}{4}\right\rceil

2 $$

个 Block。

更一般地：

$$ num_logical_blocks

\left\lceil \frac{sequence_length}{block_size} \right\rceil $$

随着 Decode 继续生成，Block Table 按需增长。

5. Block Manager 的生命周期

Paged KV Cache 并不是只有一个地址转换公式，还需要一个管理器维护动态生命周期。

一个 Sequence 从创建到释放，大致经历：

create_sequence
        ↓
append_token
        ↓
append_token
        ↓
跨 Block 边界
        ↓
allocate_block
        ↓
继续 append_token
        ↓
sequence finish
        ↓
release_sequence
        ↓
blocks 回到 free list

5.1 创建 Sequence

Sequence 初始状态：

SequenceState(
    sequence_id=sid,
    sequence_length=0,
    block_table=[],
)

此时不一定需要立即分配 Block。

这样做的好处是：Sequence 元数据创建和物理存储分配解耦。

5.2 Append Token

当前长度为：

$$ L $$

新 Token 的位置就是：

$$ token_pos=L $$

计算：

$$ logical_block

\left\lfloor \frac{L}{block_size} \right\rfloor $$

$$ block_offset

L\bmod block_size $$

如果：

$$ logical_block

len(block_table) $$

说明当前 Token 正好进入一个新的 Logical Block，需要分配新的 Physical Block：

state.block_table.append(
    self.allocate_block()
)

否则直接复用当前最后一个 Block。

5.3 Sequence 结束

Sequence 结束以后，不需要移动其他请求的数据，只需要遍历 state.block_table，把物理 Block 放回 free_blocks。

这就是分页方案减少外部碎片的关键：空闲块可以直接被其他请求复用，而不要求相邻空闲区域合并成一个大的连续 Buffer。

6. Paged KV Cache 解决了哪些碎片问题

图中第 6 部分区分了外部碎片和内部碎片。

6.1 外部碎片

分页之后，请求拥有的是多个独立 Block：

Sequence A → [5, 2, 9]

物理上不需要：

5, 6, 7

连续。

请求释放 Block 2 后，新的 Sequence 可以立即使用 Block 2，不需要等待旁边的 Block 同时释放。

因此固定大小 Block Pool 能显著减少外部碎片。

6.2 内部碎片

分页不能完全消除内部碎片。

假设：

$$ block_size=4 $$

Sequence 长度为：

$$ L=10 $$

则需要 3 个 Block：

Block 0: 4 / 4 used
Block 1: 4 / 4 used
Block 2: 2 / 4 used

最后一个 Block 浪费：

$$ 4-2=2 $$

个 Slot。

对于任意非空 Sequence，最后一个 Block 的浪费为：

$$ waste

\begin{cases} 0, & L\bmod B_s=0\ B_s-(L\bmod B_s), & \text{otherwise} \end{cases} $$

其中 $B_s$ 为 Block Size。

因此存在一个经典权衡：

Block Size 大：Metadata 少、Block Table 短，但最后一个 Block 的内部碎片可能更大；
Block Size 小：内部碎片更少，但 Block Table 更长，Metadata 和地址查询开销增加。

这也是图中底部箭头想表达的含义。

7. 为什么它像 Linux 虚拟内存，但又不完全一样

PagedAttention 的核心设计确实借鉴了操作系统分页思想，但不能把两者完全等同。

7.1 相似点

逻辑地址不直接等于物理地址。

Linux 中：

$$ virtual_page \rightarrow page_table \rightarrow physical_frame $$

Paged KV Cache 中：

$$ logical_block \rightarrow block_table \rightarrow physical_block $$

两者都通过 Mapping Table 隔离逻辑视图和物理存储位置，因此逻辑上连续的数据可以位于物理上不连续的存储区域。

7.2 不同点

MiniPaged-Qwen 中的 Block Manager 更简单：

没有硬件 TLB；
没有 Page Fault；
没有 Swap；
没有 R/W/X 权限保护；
不进行通用虚拟地址翻译；
Physical Block 来自预先创建的固定大小 KV Pool。

因此更准确的理解是：

Paged KV Cache 借鉴了分页系统的“逻辑地址与物理地址解耦”思想，但它是针对 LLM KV Cache 访问模式专门设计的软件管理机制。

8. MiniPaged-Qwen 中的 Block Manager

下面进入项目实现。

MiniPaged-Qwen 将 Paged KV Cache 分成两层：

CPU Metadata Plane
    └── KVBlockManager
          ├── SequenceState
          ├── free_blocks
          ├── block_table
          └── sequence_length

GPU Data Plane
    └── PagedKVCache
          ├── key_cache
          └── value_cache

这是一个非常重要的设计：

CPU 管元数据和生命周期，GPU 保存真正的 K/V 数据并执行 Attention。

8.1 `SequenceState`

项目中每个 Sequence 的状态为：

@dataclass
class SequenceState:
    sequence_id: int
    sequence_length: int = 0
    block_table: List[int] = field(default_factory=list)

三个成员分别表示：

`sequence_id`

请求的标识：

sequence_id

用于：

self.sequences[sequence_id]

查找状态。

`sequence_length`

已经写入的 Token 数：

sequence_length

同时也是下一次 Append 的逻辑位置。

例如：

sequence_length = 13

下一个 Token 的：

$$ token_pos=13 $$

`block_table`

当前 Sequence 的逻辑 Block 到物理 Block 的映射：

block_table = [5, 2, 9, 1]

表示：

logical block 0 → physical block 5
logical block 1 → physical block 2
logical block 2 → physical block 9
logical block 3 → physical block 1

8.2 `KVBlockManager`

构造函数：

class KVBlockManager:
    def __init__(
        self,
        num_physical_blocks: int,
        block_size: int,
    ):
        self.num_physical_blocks = num_physical_blocks
        self.block_size = block_size
        self.free_blocks = list(
            range(num_physical_blocks)
        )
        self.sequences = {}

这里管理两个核心集合：

free_blocks

和：

sequences

其中：

$$ free_blocks \subseteq {0,1,\dots,N_{blocks}-1} $$

sequences 中保存所有 Live Sequence 的 SequenceState。

9. `append_token()`：整个 Block Manager 的核心

项目核心逻辑可以概括为：

def append_token(self, sequence_id):
    state = self.sequences[sequence_id]

    logical_block = (
        state.sequence_length
        // self.block_size
    )

    block_offset = (
        state.sequence_length
        % self.block_size
    )

    if logical_block == len(state.block_table):
        state.block_table.append(
            self.allocate_block()
        )

    physical_block = state.block_table[
        logical_block
    ]

    state.sequence_length += 1

    return (
        physical_block * self.block_size
        + block_offset
    )

这段代码做了三件事。

9.1 判断是否跨 Block 边界

假设：

$$ block_size=4 $$

当前：

$$ sequence_length=7 $$

则：

$$ logical_block

\left\lfloor\frac{7}{4}\right\rfloor

1 $$

$$ block_offset

3 $$

下一个位置仍然在 Logical Block 1。

当：

$$ sequence_length=8 $$

则：

$$ logical_block=2 $$

此时需要新 Physical Block。

9.2 必要时分配 Physical Block

if logical_block == len(state.block_table):
    state.block_table.append(
        self.allocate_block()
    )

假设原来：

block_table = [5, 2]

新分配 Physical Block 9：

block_table = [5, 2, 9]

9.3 返回 Slot Mapping

假设：

$$ physical_block=9 $$

$$ block_offset=0 $$

则：

$$ slot=9\times4+0=36 $$

这个返回值会交给 Cache Write Kernel。

10. `slot_mapping` 为什么重要

Block Manager 管理的是逻辑状态，但 CUDA Kernel 最终需要知道：

当前新 Token 的 K/V 应该写到 GPU Cache Tensor 的哪个位置？

因此项目使用：

slot_mapping

连接 CPU Block Manager 和 GPU KV Cache。

流程如下：

append token
      ↓
KVBlockManager
      ↓
slot_mapping
      ↓
Cache Write Kernel
      ↓
PagedKVCache

对于 Batch 中多个 Sequence，可以得到：

slot_mapping = [
    slot_seq_0,
    slot_seq_1,
    slot_seq_2,
]

这样每个 Sequence 的新 K/V 可以写入不同 Physical Block。

11. `PagedKVCache` 的数据布局

MiniPaged-Qwen 中：

self.key_cache = torch.zeros(
    num_blocks,
    num_kv_heads,
    block_size,
    head_dim,
)

self.value_cache = torch.zeros_like(
    self.key_cache
)

所以：

$$ KCache,VCache \in \mathbb{R}^{ N_{blocks} \times H_{kv} \times B_s \times D } $$

四个维度分别表示：

num_blocks
    ↓
物理 Block 编号

num_kv_heads
    ↓
KV Head

block_size
    ↓
Block 内 Token Offset

head_dim
    ↓
每个 Head 的向量维度

因此 Token 的物理访问形式是：

$$ KCache[ physical_block, kvh, block_offset, : ] $$

$$ VCache[ physical_block, kvh, block_offset, : ] $$

注意：

slot_mapping 是一个压平后的线性表示，实际访问 Cache 时仍然会重新分解成 physical_block 和 block_offset。

即：

$$ physical_block

\left\lfloor \frac{slot}{block_size} \right\rfloor $$

$$ block_offset

slot\bmod block_size $$

12. Cache Write：从新 K/V 到物理 Slot

对于 Decode 的一个新 Token，Attention Layer 产生：

$$ K_{\mathrm{new}} \in \mathbb{R}^{B\times H_{kv}\times D} $$

$$ V_{\mathrm{new}} \in \mathbb{R}^{B\times H_{kv}\times D} $$

Block Manager 产生：

$$ slot_mapping \in \mathbb{Z}^{B} $$

Cache Write 根据每个 Batch Item 的 Slot：

slot
 ↓
physical_block
 ↓
block_offset
 ↓
key_cache[pb, :, off, :]
value_cache[pb, :, off, :]

项目同时保留 CPU fallback 和 CUDA cache write 两条路径，方便正确性验证和 GPU 集成。

13. Decode Attention 如何读取分页 KV

写入完成以后，Attention Kernel 面临另一个问题：

历史 KV 不连续，如何按照 Token 顺序读取？

输入元数据是：

block_tables
seq_lens

对于 Batch 中第 $b$ 个 Sequence 和历史位置 $pos$：

$$ logical_block

\left\lfloor \frac{pos}{block_size} \right\rfloor $$

查询：

$$ pb

block_tables[ b, logical_block ] $$

再计算：

$$ off

pos\bmod block_size $$

读取：

$$ K

key_cache[ pb, kvh, off, : ] $$

$$ V

value_cache[ pb, kvh, off, : ] $$

因此 Attention 的数学模型没有改变：

$$ O

\mathrm{Softmax} \left( \frac{QK^T}{\sqrt D} \right)V $$

改变的是 K/V 的地址获取方式。

连续 KV：

base + pos

Paged KV：

pos
 ↓
logical block
 ↓
block table lookup
 ↓
physical block
 ↓
offset
 ↓
K/V address

14. GQA 下的 KV Head 映射

Qwen3 使用 GQA。Query Head 数量和 KV Head 数量可以不同。

设：

$$ H_q=16 $$

$$ H_{kv}=8 $$

则：

$$ group_size

\frac{H_q}{H_{kv}}

2 $$

第 $qh$ 个 Query Head 对应：

$$ kvh

\left\lfloor \frac{qh}{group_size} \right\rfloor $$

例如：

qh 0, 1   → kvh 0
qh 2, 3   → kvh 1
qh 4, 5   → kvh 2
...

因此 Paged Attention 的地址计算不仅要知道 Physical Block 和 Block Offset，还要根据 Query Head 得到 KV Head。

最终读取：

$$ K[pb,kvh,off,:] $$

和：

$$ V[pb,kvh,off,:] $$

15. MiniPaged-Qwen 的 Block Manager 不变量

内存管理器不能只“能跑”，还必须保证任何操作之后不会出现：

一个 Physical Block 被两个独立 Sequence 重复分配；
同一个 Block 同时存在于 Allocated Set 和 Free Set；
Block 丢失；
Block 被重复释放。

项目定义：

$$ allocated_blocks

\bigcup_s block_table_s $$

要求：

$$ allocated_blocks \cap free_blocks

\varnothing $$

并且：

$$ |allocated_blocks| + |free_blocks|

num_physical_blocks $$

代码中的：

invariants_ok()

就是在验证这些条件。

同时还检查：

len(allocated)
==
len(set(allocated))

用于保证同一个 Physical Block 不会被重复分配。

这部分对 Runtime 很重要，因为 Block Manager 的错误往往不会立刻产生 Python Exception，而可能表现为：

两个 Sequence 写入同一 KV Block
        ↓
Cache 被静默覆盖
        ↓
Attention 数值错误
        ↓
最终生成结果异常

16. MiniPaged-Qwen 中各数据结构分别负责什么

最后把项目结构统一整理一下。

16.1 `SequenceState`

负责单个 Sequence 的逻辑状态：

sequence_id
sequence_length
block_table

解决的问题：

这个请求已经有多少 Token？
拥有多少 Logical Block？
每个 Logical Block 映射到哪个 Physical Block？

16.2 `KVBlockManager`

负责 CPU 侧 Physical Block 生命周期：

create_sequence
allocate_block
append_token
slot_mapping_for_append
release_sequence
get_block_table_tensor
get_seq_lens_tensor
invariants_ok
internal_fragmentation_tokens

解决的问题：

什么时候分配新 Block？
从哪里取 Block？
Token 应写到哪个 Slot？
请求结束如何回收？
如何把 CPU Metadata 转成 CUDA Kernel 输入？

16.3 `PagedKVCache`

负责真正的 GPU K/V 数据：

$$ [num_blocks, num_kv_heads, block_size, head_dim] $$

每层拥有独立的 K/V Tensor。

在完整 MiniPaged-Qwen Runtime 中，可以理解为：

                Shared Sequence Metadata
                       │
                 KVBlockManager
                       │
                   Block Table
                       │
       ┌───────────────┼───────────────┐
       │               │               │
       ▼               ▼               ▼
Layer 0 KV Cache  Layer 1 KV Cache ... Layer N KV Cache

Block Table 是 Sequence 的地址映射状态，可以跨层复用；但不同 Layer 的 K/V 数值不同，所以每层必须拥有独立 Cache Tensor。

16.4 `slot_mapping`

负责连接 Block Manager 和 Cache Write。

它回答：

这个新 Token 的 K/V 最终应该写到哪个物理 Slot？

16.5 `block_tables`

负责连接 Block Manager 和 Paged Attention Read。

它回答：

历史第 $pos$ 个 Token 位于哪个 Physical Block？

16.6 `seq_lens`

告诉 Attention Kernel 每个 Sequence 当前有效历史长度，防止 Kernel 读取最后一个 Block 中尚未使用的 Slot 或 Block Table Padding。

17. MiniPaged-Qwen 已经实现了哪些功能

当前项目已经完成了一个最小但完整的 Paged KV Cache 学习实现。

17.1 CPU Block Manager

实现：

固定大小 Physical Block Pool
Free List
Sequence 创建
Token Append
按需 Block 分配
Sequence 释放
Block Table 生成
Sequence Length Tensor
Slot Mapping
Block Manager 不变量检查
内部碎片统计

KVBlockManager 的 append_token() 根据 sequence_length 计算 Logical Block 和 Offset，在跨 Block 边界时申请新 Physical Block，并返回压平后的 Slot；release_sequence() 将 Sequence 持有的所有 Block 归还 Free List；invariants_ok() 检查已分配集合与空闲集合互斥且覆盖完整 Block Pool。

17.2 GPU Paged KV Cache

实现：

Per-layer Key Cache
Per-layer Value Cache
固定 Block Layout
CPU fallback cache write
CUDA cache write

Cache Tensor 采用：

$$ [num_blocks, num_kv_heads, block_size, head_dim] $$

布局，Cache Write 通过 Slot Mapping 恢复 Physical Block 和 Block Offset。

17.3 Decode Paged Attention

实现：

Block Table 间接寻址
Sequence Length 边界控制
GQA Head Mapping
Online Softmax
CPU Reference
CUDA Paged Attention Kernel

CPU Reference 按 pos // block_size 查询 Block Table，通过 pos % block_size 得到 Block Offset，并在遍历历史 KV 时维护 Online Softmax 状态。CUDA 路径调用自定义 paged_attention_online Kernel。

17.4 Qwen3 集成验证

实现：

Qwen3 Q/K/V Projection
QK Norm
RoPE
Paged KV Cache 写入
Paged Attention
O Projection
与 Hugging Face Eager Attention 对齐

集成脚本会先把 Qwen3 Attention Layer 产生的 K/V 写入 Paged KV Cache，再使用最后一个 Query 调用 Paged Attention，并与 Hugging Face Eager Attention 的对应输出比较数值误差。

18. 总结

KV Cache 解决的是：

不要重复计算历史 Token 的 K/V。

Paged KV Cache 进一步解决的是：

历史 KV 在不断增长、请求长度不确定、多个请求动态加入和结束时，如何高效管理显存。

它的核心不是改变 Attention 数学公式，而是加入一层地址映射：

$$ token_pos \rightarrow logical_block \rightarrow block_table \rightarrow physical_block \rightarrow block_offset \rightarrow KV\ address $$

MiniPaged-Qwen 将这个过程拆成了几个清晰的组件：

SequenceState
    ↓
保存 sequence_length 和 block_table

KVBlockManager
    ↓
管理 physical block pool 和生命周期

slot_mapping
    ↓
指导新 K/V 写入

PagedKVCache
    ↓
保存真正的 GPU K/V 数据

block_tables + seq_lens
    ↓
指导 Decode Attention 读取历史 KV

从操作系统视角来看，这个设计最值得理解的地方是：

通过增加少量 Metadata 和一次 Block Table 间接寻址，换取物理存储位置的灵活性。

从 LLM Runtime 视角来看，它为后续的：

Variable-length Batching
Continuous Batching
Request Scheduler
Prefix Cache
Beam Search KV Sharing
KV Cache Eviction

提供了一个统一的 Block 级内存管理基础。

参考资料

Woosuk Kwon, et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023 / arXiv:2309.06180.
vLLM Documentation. Paged Attention.
MiniPaged-Qwen source code: block_manager.py, paged_attention.py, Qwen3 Paged Attention integration scripts.

Contents

MiniPaged-Qwen：Paged KV Cache 与 KV Block Manager

1. 为什么需要 KV Cache

1.1 自回归生成中的重复计算

$$ O

$$ K_{0:L}

$$ V_{0:L}

2. 连续 KV Cache 有什么问题

$$ M_{\mathrm{KV}}

2.1 最大长度预留

2.2 动态扩容连续 Buffer

2.3 多请求结束时间不同造成外部碎片

3. Paged KV Cache 的核心思想

$$ logical_block

$$ block_offset

$$ physical_block

$$ slot

4. 一张图理解整个 Paged KV Cache

4.1 地址映射：Token Position 如何变成 Slot

$$ logical_block

\left\lfloor\frac{6}{4}\right\rfloor

$$ block_offset

6\bmod4

$$ physical_block

block_table[1]

$$ slot

2\times4+2

4.2 物理 Block Pool 和 Free List

4.3 多个 Sequence 拥有不同 Block Table

$$ \left\lceil\frac{7}{4}\right\rceil

$$ num_logical_blocks

5. Block Manager 的生命周期

5.1 创建 Sequence

5.2 Append Token

$$ logical_block

$$ block_offset

$$ logical_block

5.3 Sequence 结束

6. Paged KV Cache 解决了哪些碎片问题

6.1 外部碎片

6.2 内部碎片

$$ waste

7. 为什么它像 Linux 虚拟内存，但又不完全一样

7.1 相似点

7.2 不同点

8. MiniPaged-Qwen 中的 Block Manager

8.1 SequenceState

sequence_id

sequence_length

block_table

8.2 KVBlockManager

9. append_token()：整个 Block Manager 的核心

9.1 判断是否跨 Block 边界

$$ logical_block

\left\lfloor\frac{7}{4}\right\rfloor

$$ block_offset

9.2 必要时分配 Physical Block

9.3 返回 Slot Mapping

10. slot_mapping 为什么重要

11. PagedKVCache 的数据布局

$$ physical_block

$$ block_offset

12. Cache Write：从新 K/V 到物理 Slot

13. Decode Attention 如何读取分页 KV

$$ logical_block

$$ pb

$$ off

$$ K

$$ V

$$ O

14. GQA 下的 KV Head 映射

$$ group_size

\frac{H_q}{H_{kv}}

$$ kvh

15. MiniPaged-Qwen 的 Block Manager 不变量

$$ allocated_blocks

$$ allocated_blocks \cap free_blocks

$$ |allocated_blocks| + |free_blocks|

16. MiniPaged-Qwen 中各数据结构分别负责什么

16.1 SequenceState

8.1 `SequenceState`

`sequence_id`

`sequence_length`

`block_table`

8.2 `KVBlockManager`

9. `append_token()`：整个 Block Manager 的核心

10. `slot_mapping` 为什么重要

11. `PagedKVCache` 的数据布局

16.1 `SequenceState`

16.2 `KVBlockManager`

16.3 `PagedKVCache`

16.4 `slot_mapping`

16.5 `block_tables`

16.6 `seq_lens`