【Transformer 与注意力机制】49｜KV Cache：推理为什么是 O(n) 不是 O(n²)
内容提要
KV Cache 是自回归推理中缓存历史 token 的 Key 和 Value，避免重复计算前缀。它利用历史 K/V 不变性，将重复计算转为显存占用，成为长上下文推理的核心瓶颈。推理分 prefill 和 decode 两阶段，KV Cache 内存随层数、序列长度和 batch 线性增长。GQA、PagedAttention 和量化等技术用于优化 cache 管理，平衡性能与资源。
延伸解读
KV Cache 的本质：用显存换算力
KV Cache 的核心思想是将历史 token 的 Key 和 Value 缓存起来，避免在生成每个新 token 时重新计算整个前缀。这本质上是将重复计算转化为显存占用，从而显著降低推理时的计算量。但这也意味着显存成为新的瓶颈，尤其是长上下文场景下，KV Cache 的大小会随序列长度线性增长，对显存容量和带宽提出更高要求。
prefill 与 decode 的差异
推理过程分为 prefill 和 decode 两个阶段。prefill 阶段处理用户输入的 prompt，可以并行计算，类似训练时的 forward，容易吃满 GPU。decode 阶段则逐步生成 token，每一步都需要读取 KV Cache，计算粒度细，受内存读写和串行依赖限制。理解这两个阶段的差异，有助于针对性地优化推理性能，例如在 prefill 阶段使用 FlashAttention，在 decode 阶段优化 KV Cache 管理。
KV Cache 优化的多种路径
为了缓解 KV Cache 带来的显存压力，业界提出了多种优化方法。GQA/MQA 通过减少 KV head 数来降低 cache 大小；量化技术降低每个元素的字节数；PagedAttention 通过分页管理减少显存碎片；滑动窗口和缓存淘汰则限制历史范围。这些方法各有优劣，需要根据具体场景权衡质量、速度和资源消耗。
Q&A
KV Cache 是什么？它解决了什么问题？
KV Cache 是自回归推理中缓存历史 token 的 Key 和 Value 的技术。它利用历史 K/V 不变性，避免每生成一个新 token 就重新计算整个前缀，从而将重复计算转为显存占用，是长上下文推理的核心优化。
为什么推理时 KV Cache 能缓存 K 和 V，却不能缓存 Q？
历史 token 的隐藏状态在 decode 过程中已经确定，且 causal mask 禁止历史位置看未来，所以历史 K/V 不变，可以缓存。而新 token 的 Q 依赖于当前生成的 token，无法提前知道，因此不能缓存。
prefill 和 decode 阶段有什么区别？
prefill 阶段处理用户输入的 prompt，一次性计算所有 token 的表示并生成初始 KV Cache，计算形态类似训练 forward，可并行。decode 阶段逐步生成新 token，每步读取已有 cache 并追加新 K/V，计算粒度细，受内存带宽和串行依赖限制。
KV Cache 的内存大小如何计算？
粗略公式为 CacheBytes = 2 × L × B × S × H_kv × D_h × bytes，其中 2 表示 K 和 V 两份，L 是层数，B 是 batch size，S 是序列长度，H_kv 是 KV head 数，D_h 是每个 head 的维度，bytes 是每个元素字节数（如 FP16 为 2）。
GQA 和 MQA 如何减少 KV Cache？
MQA 让多个 query head 共享同一组 K/V，GQA 让一组 query heads 共享一个 K/V head，从而减少 KV head 数（H_kv），线性降低 cache 大小和读写成本。
PagedAttention 是如何管理 KV Cache 的？
PagedAttention 将 KV Cache 切成固定大小的 block，用类似虚拟内存分页的方式管理，请求看到连续逻辑序列，底层物理 block 可分散存放，从而减少显存碎片，支持动态 batching，提高吞吐和并发。
KV Cache 有哪些常见的误解？
常见误解包括：1）KV Cache 让 attention 不再依赖上下文长度（错，decode 每步仍要 attend 历史）；2）Q 也应该缓存（错，历史 Q 无复用价值）；3）训练也可用 KV Cache 省 O(n²)（错，训练数据流不同）；4）cache 越大越好（错，需权衡显存、并发和延迟）。
