Paged Attention — KV Cache 的虚拟内存

attention-mechanisms · lesson 04 视觉辅助 · 操作:1–4 切 Tab,← → 翻步

问题:为什么不能简单地连续分配?

传统做法给每个请求预留一整段连续显存,长度按 max_seq_len 算(怕生成到最长)。但实际生成长度天差地别 → 大量预留显存空着,谁也用不了。拖动滑块看浪费。

实际用到的 token 预留但空着(浪费)
–
实际占用 token
–
预留浪费 token
–
显存利用率
为什么这么算:连续分配下,每个请求都按最坏情况 max_seq_len 占一段地址,哪怕它只生成几个 token。利用率 = 实际 token ÷ 预留 token。短请求一多,利用率可以跌到 20–40%——这就是内部碎片 + 预留浪费。还没算另一种问题:不同请求的预留段大小不一,回收后留下塞不进新请求的空洞(外部碎片)。

解法:把 KV Cache 切成定长「块」,逻辑连续、物理分散

借鉴操作系统虚拟内存:每个序列的 KV 在逻辑上是连续的块 0,1,2…;物理上这些块从一个空闲块池里随便抓,地址不连续。一张 Block Table(≈页表)记录逻辑块 → 物理块的映射。块大小 block_size = 4 token。

0 / 0
序列的逻辑视图(连续的块)
Block Table(逻辑块 → 物理块)
GPU 物理块池(地址分散)
分给本序列 空闲 块内未用槽

共享 + Copy-on-Write:多个采样共用一份 prompt

并行采样 / beam search 里,多条输出共享同一段 prompt。分页让它们的 Block Table 指向同一批物理块(引用计数 ref=2),prompt 只存一份。等到某条要往一个共享且没填满的块里写新 token 时,触发 Copy-on-Write:先复制该块,改自己的映射,再写——互不污染。

Prompt = 7 token,block_size = 4 ⟹ 逻辑块 L0 满(4),L1 半满(3,剩 1 个空槽)。A、B 共享 L0、L1。

序列 A 的 Block Table
序列 B 的 Block Table
物理块池(含引用计数 ref)
共享 ref≥2 A 独占 B 独占
事件日志
为什么这么算:第一次往共享半满块写 token 的那条序列会触发复制(ref>1 不能就地改);复制后原块 ref 减 1。等另一条再写时,那个块 ref 已经是 1,不必再复制,直接就地写。结果:prompt 的满块(L0)永远共享一份,只有真正分叉的那半满块被复制——节省的显存随采样数线性放大。

回报:同样的显存能同时塞下多少请求?

固定显存预算 = 96 个 token 槽,block_size = 4,max_seq_len = 24。每个请求实际只生成 8 个 token。拖动滑块看两种方案各能并发多少请求。

连续分配(按 max_seq_len 预留)
4
个并发请求
Paged Attention(按需分块)
12
个并发请求
3.0×
并发提升倍数
≤3
分页每请求最大浪费(token)
为什么这么算:连续方案无论实际多短都按 max_seq_len=24 预留 → 固定塞 ⌊96/24⌋=4 个。分页方案每请求只占 ⌈len/4⌉ 个块 = ⌈len/4⌉×4 个槽,浪费只有最后一块的零头(至多 block_size−1 = 3 个 token,与序列长短无关)。请求越短,倍数越夸张——这正是 vLLM 把吞吐做上去的根本原因:消灭碎片 = 把省下的显存换成更大的 batch。
注:真实系统里块还会因 prefix 共享(Tab 3)进一步省,这里只算单请求独占的下界。