---
tags: [nanochat, inference, kv-cache]
阶段: 09-推理Engine与工具
难度: ★★★
created: 2026-10-22
related: "[[自注意力机制]], [[自回归解码与prefill-decode]], [[部署与成本]], [[KV缓存]]"
---

# KV Cache 原理

## 定义

KV Cache（键值缓存）是自回归解码时保存每一层、每个历史位置的键向量 $\mathbf{k}_i$ 与值向量 $\mathbf{v}_i$，使第 $t$ 步只计算当前 token 的查询 $\mathbf{q}_t$ 与新的 $\mathbf{k}_t,\mathbf{v}_t$，历史部分直接读取缓存、不再重算的推理优化。

符号约定：层数 $L$，查询头数 $H$，KV 头数 $H_{kv}$，单头维度 $D$，上下文长度 $T$，批大小 $B$，缓存元素字节数 $s$（bf16 为 2）。$\mathbf{W}_Q\in\mathbb{R}^{d\times HD}$、$\mathbf{W}_K,\mathbf{W}_V\in\mathbb{R}^{d\times H_{kv}D}$ 为投影矩阵，$d$ 为模型宽度。

## 为什么重要

解码阶段每生成一个 token 都要做一次前向。若不做缓存，第 $t$ 步会把长度 $t$ 的完整前缀重新送入模型：投影、注意力、MLP 全部重算。注意力部分对第 $t$ 步的复杂度是 $O(t^2d)$，全部 $T$ 步累计 $O(T^3d)$；而真正新增的信息只有第 $t$ 个 token 的 $\mathbf{q}_t,\mathbf{k}_t,\mathbf{v}_t$。

KV Cache 把「历史 token 的键值」这一与查询无关的量物化下来，使第 $t$ 步的注意力计算降为「一次查询对 $t$ 个键的打分」，复杂度 $O(td)$，累计 $O(T^2d)$。代价是显存：缓存大小随 $B\cdot T\cdot L\cdot H_{kv}\cdot D$ 线性增长。

nanochat 的 speedrun 模型 d24、上下文 2048、bf16 下，KV Cache 每个 token 占用 $24\times 2\times 12\times 128\times 2=147{,}456$ 字节，约 144 KiB；单条 2048 序列约 288 MiB。这个数字直接决定推理能开多大 batch、能支持多长上下文，也是 [[部署与成本]] 中显存预算的第一项。

## 原理与推导

### 1. 单步生成中哪些计算是冗余的

设第 $l$ 层输入为 $\mathbf{X}^{(l)}\in\mathbb{R}^{T\times d}$，注意力子层计算

$$
\mathbf{Q}=\mathbf{X}\mathbf{W}_Q,\qquad
\mathbf{K}=\mathbf{X}\mathbf{W}_K,\qquad
\mathbf{V}=\mathbf{X}\mathbf{W}_V,
$$

$$
\mathbf{O}=\operatorname{softmax}\!\left(\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{D}}+\mathbf{M}\right)\mathbf{V},
$$

其中 $\mathbf{M}$ 为因果掩码，$M_{ij}=0$（$j\le i$）或 $-\infty$（$j>i$）。生成第 $t$ 个 token 时，只有最后一行 $\mathbf{q}_t$ 是新的；$\mathbf{K}_{1:t},\mathbf{V}_{1:t}$ 的第 $i$ 行 $\mathbf{k}_i,\mathbf{v}_i$ 只由第 $i$ 个 token 及其之前的信息决定，与后续查询无关。

因此第 $t$ 步只需要

$$
\mathbf{o}_t=\sum_{i=1}^{t}\alpha_{ti}\mathbf{v}_i,\qquad
\alpha_{ti}=\frac{\exp(\mathbf{q}_t^{\top}\mathbf{k}_i/\sqrt{D})}{\sum_{j=1}^{t}\exp(\mathbf{q}_t^{\top}\mathbf{k}_j/\sqrt{D})}.
$$

第 $t$ 步的输出只依赖 $\mathbf{q}_t$ 与 $\{(\mathbf{k}_i,\mathbf{v}_i)\}_{i\le t}$。把后者存起来，就是 KV Cache。

### 2. 复杂度对比

| 方案 | 单步注意力计算 | $T$ 步累计 | 单步显存访问 |
|---|---|---|---|
| 无缓存 | $O(t^2d)$ | $O(T^3d)$ | 重算全部中间激活 |
| KV Cache | $O(td)$ | $O(T^2d)$ | 读取 $O(td)$ 缓存 |

注意「累计」仍是二次的：因果注意力本身需要每个位置与全部历史交互。KV Cache 消除的是重复计算，不是注意力固有的二次项。这也是 [[FlashAttention与高效注意力]] 与 sliding window 仍然重要的原因。

### 3. 显存公式

每层缓存 $\mathbf{K},\mathbf{V}$ 各一个 $B\times T\times H_{kv}\times D$ 张量，元素字节 $s$：

$$
\mathrm{bytes}=2\cdot L\cdot B\cdot T\cdot H_{kv}\cdot D\cdot s.
$$

nanochat 的 `GPT.kv_bytes_per_token` 实现的就是去掉 $B\cdot T$ 的版本：

```python
def kv_bytes_per_token(self):
    head_dim = self.config.n_embd // self.config.n_head
    kv_dtype_bytes = COMPUTE_DTYPE.itemsize  # KV 缓存使用计算精度（通常 bf16）
    return self.config.n_layer * 2 * self.config.n_kv_head * head_dim * kv_dtype_bytes
```

d24 代入：$2\times24\times12\times128\times2=147{,}456$ 字节/token。单条 2048 上下文为 $147{,}456\times2048\approx302$ MB，约 288 MiB。batch 8 则约 2.25 GiB。

### 4. prefill 与 decode 是两种不同的负载

**prefill**：一次处理长度 $T_p$ 的提示，矩阵乘规模为 $T_p\times d$，GPU 算力利用率高，属于 compute-bound。其注意力 FLOPs 为

$$
4\cdot H\cdot D\cdot\left[\frac{W(W+1)}{2}+(T_p-W)W\right]
$$

每层，其中 $W=\min(T_p,\text{window})$。nanochat 的 `estimate_prefill_flops` 逐层累加这一项。

**decode**：每步只处理 1 个 token（每行），矩阵乘退化为矩阵-向量乘，算力远未饱和，时间由读取权重与 KV 缓存决定，属于 memory-bound。若权重字节为 $P_s$、缓存读取字节为 $K_s$、显存带宽为 $\mathrm{BW}$，单步下界约

$$
t_{\text{decode}}\gtrsim\frac{P_s+B\cdot K_s}{\mathrm{BW}}.
$$

nanochat 的 `GPT.kv_read_bytes(context_len)` 只统计缓存读取，并考虑 sliding window：短窗口层只读最近 $W$ 个位置。对 `SSSL` 的 d24，18 层短窗口（代码实算 512，源码注释误写 768）、6 层全窗口 2048，单行单步读约

$$
18\cdot6144\cdot512+6\cdot6144\cdot2048\approx132\ \text{MB},
$$

其中 $6144=2H_{kv}Ds$ 是每层每个位置的 K/V 字节数。权重读取通常更大，因此 decode 的吞吐首先由权重带宽决定；batch 增大时权重只读一次，缓存读取随 $B$ 线性增长，二者在某一点相交，这就是 [[部署与成本]] 中 batch 扫描曲线的来源。

### 5. GQA 与 sliding window 对缓存的影响

GQA 让 $H_{kv}<H$ 个 KV 头服务 $H$ 个查询头，缓存缩小为原来的 $H_{kv}/H$。nanochat 的 d24/d20 配置里 `n_kv_head == n_head`，GQA 不带来节省，但 `CausalSelfAttention` 与 `KVCache` 都按通用 GQA 实现，改配置即可获得收益。通用原理见 [[分组查询注意力GQA]]。

sliding window 只减少「读取」而不减少「存储」：nanochat 按 `len(tokens) + max_tokens` 分配缓存（`max_tokens` 缺省时才用 `sequence_len`），不随窗口缩减；FA3 在打分时把窗口外的位置屏蔽，因此 `kv_read_bytes` 随窗口截断，而 `kv_bytes_per_token` 不截断。若要在存储上也节省，需要环形缓冲或按层分配窗口大小，nanochat 当前没有这样做。

### 6. 在 nanochat 中的落地

**缓存结构**（`nanochat/engine.py` 的 `KVCache`）：形状为 `(n_layers, B, T, H, D)`，K 与 V 各一份；`cache_seqlens` 是长度为 $B$ 的 int32 张量，FA3 用它定位每个 batch 元素的写入位置；`prev_embedding` 保存上一步归一化后的 embedding，供 `smear` 在单 token 解码时使用。

**训练路径**：`kv_cache is None`，`CausalSelfAttention.forward` 调用 `flash_attn_func(q,k,v,causal=True,window_size=...)`，不写缓存。

**推理路径**：`kv_cache` 非空时调用 `flash_attn_with_kvcache(q,k_cache,v_cache,k=k,v=v,cache_seqlens=...,causal=True,window_size=...)`。FA3 在原地把当前步的 $\mathbf{k},\mathbf{v}$ 写入缓存，按 `cache_seqlens` 决定位置；`GPT.forward` 用 `T0 = kv_cache.get_pos()` 截取对应的 RoPE 片段 `cos[:, T0:T0+T]`，保证旋转位置与绝对位置一致。缓存的推进只由最后一层执行一次（`if self.layer_idx == kv_cache.n_layers - 1: kv_cache.advance(T)`），否则每层都会重复推进 $T$。

**批量采样**（`Engine.generate`）：先用 `batch_size=1` 对提示做一次 prefill，得到最后位置的 logits；再分配 `batch_size=num_samples` 的解码缓存，调用 `kv_cache_decode.prefill(kv_cache_prefill)` 把提示的 K/V 复制到每一行，同时把 `prev_embedding` 从单行扩展为 `num_samples` 行。这样只需一次提示前向就能并行采样多条回复，是 pass@k 与 GRPO rollout 的成本前提。

**停止与工具**：生成循环每步对每行采样一个 token，遇到 `<|assistant_end|>` 或 `<|bos|>` 标记该行完成；遇到 `<|python_start|>` 进入工具状态，收集表达式直到 `<|python_end|>`，用 `use_calculator` 求值，再把 `<|output_start|>结果<|output_end|>` 作为强制 token 注入。强制 token 的 mask 记为 0，不参与 RL 的损失。

## 关键直觉

> [!tip] 机制性直觉
> 解码的第 $t$ 步中，历史位置的键和值与当前查询无关，可以物化复用；缓存把「每步重算前缀」变成「每步只算新 token 并读取历史」。其收益上限由注意力的二次项决定，其成本由缓存字节数决定，因此优化方向总是「减少缓存读写」而不是「减少缓存计算」。

这一直觉与严格推导的关系：它成立的前提是因果掩码与固定位置编码（RoPE 只依赖绝对位置，缓存中存旋转后的 $\mathbf{k}$ 仍然正确）。若位置编码依赖完整前缀或注意力非因果，缓存的复用条件会被破坏。

## 例子与代码

### 例 1：NumPy 验证缓存与全量重算等价

```python
import numpy as np
rng = np.random.default_rng(0)

T, D = 6, 4
X = rng.normal(size=(T, D))
Wq, Wk, Wv = (rng.normal(size=(D, D)) for _ in range(3))
q, k, v = X @ Wq, X @ Wk, X @ Wv          # (T, D)

def attend(q_t, K, V):
    scores = K @ q_t / np.sqrt(D)          # (t,)
    w = np.exp(scores - scores.max())
    w /= w.sum()
    return w @ V                            # (D,)

# 全量：第 t 步把前缀重新投影并计算
full = []
for t in range(T):
    k_full = X[:t + 1] @ Wk
    v_full = X[:t + 1] @ Wv
    full.append(attend(q[t], k_full, v_full))

# 缓存：只追加当前步的 k_t, v_t
cache_k, cache_v, cached = [], [], []
for t in range(T):
    cache_k.append(k[t])
    cache_v.append(v[t])
    cached.append(attend(q[t], np.stack(cache_k), np.stack(cache_v)))

print(np.allclose(full, cached))            # True
```

这段代码的关键在第 22–24 行：缓存只追加当前 token 的 $\mathbf{k}_t,\mathbf{v}_t$，查询只取 $\mathbf{q}_t$。如果把 `q[t]` 换成完整 `q`，得到的是训练时的并行注意力，形状为 `(T, D)`，两者在最后一行上一致。

### 例 2：估算 d24 的缓存预算

```python
def kv_bytes_per_token(n_layer, n_kv_head, head_dim, dtype_bytes=2):
    return n_layer * 2 * n_kv_head * head_dim * dtype_bytes

per_tok = kv_bytes_per_token(24, 12, 128)
print(per_tok)                       # 147456
for ctx in (512, 1024, 2048):
    for batch in (1, 8, 32):
        gib = per_tok * ctx * batch / 1024**3
        print(ctx, batch, f"{gib:.2f} GiB")
```

预期：2048 上下文、batch 1 约 0.28 GiB，batch 32 约 9.0 GiB。这还未计入权重与激活，因此 24 GB 显卡在 2048 上下文下很难同时容纳 d24 权重与较大 batch。

### 例 3：nanochat 的 prefill 复制

```python
# Engine.generate：单行 prefill，然后复制到 num_samples 行
kv_cache_prefill = KVCache(batch_size=1, seq_len=len(tokens), ...)
logits = self.model.forward(ids, kv_cache=kv_cache_prefill)   # 写入提示的 K/V
kv_cache_decode = KVCache(batch_size=num_samples, seq_len=kv_length_hint, ...)
kv_cache_decode.prefill(kv_cache_prefill)                     # 复制 K/V 与 prev_embedding
```

`KVCache.prefill` 断言目标缓存为空，用一次切片赋值把 `other.k_cache[:, :, :other_pos]` 复制到所有层，并把 `cache_seqlens` 填为 `other_pos`；`prev_embedding` 用 `expand` 复制后 `clone`，避免多行共享同一块内存。

## 易错点

> [!warning] 常见错误
> 1. 把缓存的推进放在每一层：`advance(T)` 必须只在最后一层调用一次，否则位置偏移会变成 $L$ 倍。
> 2. 忘记给 RoPE 加偏移：缓存非空时 `cos_sin` 必须从 `T0 = kv_cache.get_pos()` 开始截取，不能用 `cos[:, :T]`，否则第 2 个 token 会被当成位置 0。
> 3. 缓存 dtype 与计算 dtype 不一致：nanochat 用 `COMPUTE_DTYPE` 分配缓存，bf16 下 `itemsize=2`；用 fp32 估显存会高估一倍。
> 4. 以为 sliding window 会缩小缓存：它只减少读取，nanochat 仍按 `sequence_len` 预分配完整缓存。
> 5. 在 prefill 复制时漏掉 `prev_embedding`：`smear` 在解码第一步需要上一 token 的 embedding，漏复制会得到与训练不一致的结果。
> 6. 把 `q` 也缓存：查询只与当前 token 有关，缓存查询既浪费显存又会让后续步骤读到过期值。

## 关联笔记

- 前置：[[自注意力机制]] —— 缓存复用的前提是因果掩码与 $\mathbf{k},\mathbf{v}$ 的定义。
- 前置：[[多头注意力]] —— GQA 的 KV 头数与 `head_dim` 决定缓存形状。
- 后续：[[自回归解码与prefill-decode]] —— 本篇只讲缓存结构，那篇讲两阶段的调度与采样。
- 后续：[[部署与成本]] —— 缓存字节数进入显存预算与 batch 上限。
- 跨库：[[KV缓存]] —— 通用推导与不同框架的实现对比，本库不重复。

## 达标检测

- [ ] 能不看书写出第 $t$ 步注意力的输出公式，并指出其中哪些量可以缓存。
- [ ] 能推导无缓存与有缓存的累计复杂度差异，说明为什么缓存不能消除二次项。
- [ ] 能写出 KV Cache 显存公式，并计算 d24、2048 上下文、batch 8 的缓存大小。
- [ ] 能解释 `Engine.generate` 为什么先做 batch=1 prefill 再复制缓存，而不是直接 batch=num_samples prefill。
- [ ] 能指出 nanochat 中 `advance`、RoPE 偏移、`prev_embedding` 三处实现细节，并说明各自出错时的现象。
- [ ] 能解释 `kv_bytes_per_token` 与 `kv_read_bytes` 的差异，以及 sliding window 在哪一侧生效。
- [ ] 能用 NumPy 写出一个可验证「缓存与全量重算等价」的最小实验。

## 参考来源

- Vaswani et al., *Attention Is All You Need*, arXiv:1706.03762 —— 缩放点积注意力与因果掩码的定义。
- Dao et al., *FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision*, arXiv:2407.08608 —— `flash_attn_with_kvcache` 的原地缓存机制与窗口参数。
- Ainslie et al., *GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints*, arXiv:2305.13245 —— KV 头共享对缓存大小的影响。
- *nanochat* 仓库（commit 92d63d4），`nanochat/engine.py` 与 `nanochat/gpt.py` 的 `kv_bytes_per_token`、`kv_read_bytes`、`estimate_prefill_flops` —— 本篇所有实现细节的事实来源。
- *nanochat* 仓库 `dev/LOG.md`（2026-01-11 sliding window、2026-07 inference benchmarking 条目）—— 窗口模式与推理基准的设计背景。
