Efficient Attention & FlashAttention: 解释 PagedAttention 如何解决 KV Cache 碎片。

Core Concept: 把 KV cache 分成固定大小的块（page），用块表间接映射，实现非连续存储、按需分配与共享，消除碎片。

数学机理：<strong>问题</strong>——传统推理引擎为每个请求<strong>预分配</strong>一段连续的 KV cache 空间（大小 = max_seq_len × 层数 × KV 头 × d_h）。但实际输出长度<strong>不可预知</strong>（可能远小于最大长度），故 (a) <strong>内部碎片</strong>——分配了但没用到的空间浪费（实测可达 60%~80%）；(b) <strong>外部碎片</strong>——不同请求的连续空间大小不一，导致显存难以利用；(c) <strong>无法共享</strong>——相同前缀（如系统提示、few-shot 示例）在每个请求中重复存储。<strong>PagedAttention（Kwon 等 2023，vLLM 的核心）</strong> 借用操作系统<strong>虚拟内存分页</strong>的思想：把 KV cache 切成固定大小的<strong>块（block/page，如 16 个 token）</strong>；每个序列维护一个<strong>逻辑块 → 物理块</strong>的映射表（block table）；物理块<strong>无需连续</strong>，按需分配。<strong>收益</strong>：(a) <strong>消除碎片</strong>——浪费最多一个块（≤16 token 的空间），显存利用率接近 100%；(b) <strong>按需增长</strong>——序列变长时动态分配新块；(c) <strong>共享前缀</strong>——相同前缀的请求可<strong>指向同一物理块</strong>（引用计数），显存与计算都省（配合 prefix caching）；(d) <strong>灵活调度</strong>——块级管理使连续批处理（continuous batching）与抢占（preemption）更易实现。<strong>效果</strong>——vLLM 报告吞吐提升 2~4 倍（同等延迟下），主要来自显存利用率与批大小的提升。

深度剖析与工程权衡：① <strong>与操作系统的类比</strong>——PagedAttention 完全对应 OS 的'分页 + 页表 + 写时复制（CoW）'：前缀共享对应 CoW（多个序列共享只读块，写入时复制）；这使'LLM 推理的内存管理'成为一个成熟的系统工程问题。② <strong>块大小的权衡</strong>——块太小则映射表开销大、kernel 效率低；块太大则碎片增加、共享粒度粗。实践中常用 16（vLLM 默认）。③ <strong>与连续批处理的协同</strong>——PagedAttention 使'新请求可随时插入正在运行的批'（因为块可动态分配），这是连续批处理能实现的前提；两者共同构成现代推理引擎的基础。④ <strong>与 prefix caching 的关系</strong>——PagedAttention 的块级共享是 prefix caching 的实现基础（用哈希索引相同前缀的块）；对'多请求共享同一长系统提示'的场景收益巨大。⑤ <strong>与 Flash Attention 的分工</strong>——Flash 优化'计算'（不物化 L×L），PagedAttention 优化'存储'（KV cache 的内存管理）；推理引擎通常两者都用（Flash 做 prefill 计算、Paged 做 KV 管理）。⑥ <strong>面试要点</strong>——被问'PagedAttention 解决什么'，应给出'<strong>预分配导致碎片（最多浪费 60-80%）→ 分页按需分配 + 块表间接映射 + 前缀共享</strong>'，并量化收益（显存利用率近 100%、吞吐 2~4 倍）；能类比 OS 虚拟内存是深度理解的标志。