KV缓存与PagedAttention — 练习

练习 1：块分配模拟

配置：block_size=16，总共 8 个物理块。

请求序列：

请模拟每步的块分配状态（物理块使用情况、空闲块数、引用计数）。

参考答案

初始：8 个空闲块 [0-7]

请求 A（40 tokens）：需要 3 个块（ceil(40/16)=3）。分配块 [0,1,2]。空闲：5
- Block 0: hash(A[0:16]), ref=1
- Block 1: hash(A[16:32]), ref=1
- Block 2: hash(A[32:40]), ref=1（部分填充）
请求 B（24 tokens，前 16 与 A 相同）：需要 2 个块。
- Block 0: hash 匹配，复用，ref=2
- Block 3: 新分配（B[16:24]），ref=1
- 空闲：4
请求 A decode 10 tokens：现有 40+10=50 tokens，需要 ceil(50/16)=4 个块。
- Block 2 原来只填到 40，现在填到 48（8 个新 token）
- 需要 Block 4（第 49-50 token），新分配，ref=1
- 空闲：3
请求 C（48 tokens，前 16 与 A 相同）：需要 3 个块。
- Block 0: hash 匹配，复用，ref=3
- Block 5, 6: 新分配（C[16:48]），ref=1
- 空闲：1

假设 system prompt 为 512 tokens，有 10 个并发请求共享此 system prompt。

计算有无前缀缓存时的 KV 缓存块数（block_size=16）：

参考答案

System prompt 块数：ceil(512/16) = 32 块

无前缀缓存：每个请求独立存储 system prompt。
- 10 × 32 = 320 块用于 system prompt
- 总共至少 320 + 10 × (user query blocks)
有前缀缓存：所有请求共享一份 system prompt。
- 32 块用于 system prompt（ref=10）
- 总共 32 + 10 × (user query blocks)
- 节省：320 - 32 = 288 块（90% 节省）

分析以下场景中应该使用哪种卸载策略：

参考答案