生成第 N 个 token 时:
需要计算 token 1, 2, ..., N 的 Q, K, V
其中 token 1 到 N-1 的 KV 在前 N-1 步已经算过
如果不缓存：每步重新计算所有历史 token 的 KV
复杂度：O(N^2) 每步，总复杂度 O(output_len^3)

如果缓存:
每步只计算新 token 的 KV (O(1))，Attention 用缓存
总复杂度：O(output_len^2)

加速比: O(output_len) 倍。当 output_len = 1000，就是 1000 倍加速。

---
O(output_len^3) 推导:
生成第 1 个 token: Attention 计算 1×1 矩阵 = O(1^2)
生成第 2 个 token: Attention 计算 2×2 矩阵 = O(2^2)
...
生成第 N 个 token: Attention 计算 N×N 矩阵 = O(N^2)

总计算量 = 1^2 + 2^2 + ... + N^2 = N(N+1)(2N+1)/6 ≈ O(N^3)

使用 KV Cache 后:
每步 Attention 只需 O(N)（Q 是 1×d，K_cache 是 N×d）
总计算量 = 1 + 2 + ... + N = O(N^2)

所以 KV Cache 将总计算量从 O(N^3) 降到 O(N^2)。

KV_Cache_Size = 2 × num_layers × batch_size × seq_len × num_kv_heads × head_dim × bytes_per_element

各变量含义:
2 → K 和 V 各一份
num_layers → Transformer 的层数（如 Llama 3 70B 有 80 层）
batch_size → 并发处理的请求数
seq_len → 当前序列长度（prompt + 已生成的 token）
num_kv_heads → KV 头数（MHA = num_heads, GQA = num_heads/G, MQA = 1）
head_dim → 每个头的维度（通常 64 或 128）
bytes_per_element → 数据类型大小: FP32=4, FP16/BF16=2, FP8/INT8=1

单位换算: 结果以 bytes 计，除以 1024^3 得到 GB

时间线示例 (总显存 80GB):

T0: Batch 0 请求, seq=2000 → 分配 3 GB
T1: Batch 1 请求, seq=1500 → 分配 2.3 GB
T2: Batch 2 请求, seq=3000 → 分配 4.5 GB

T3: Batch 1 完成 → 释放 2.3 GB (中间留下空洞)
T4: 新请求, seq=5000 → 需要 7.5 GB
但最大连续空闲块只有 4 GB → OOM!
实际空闲: 2.3 + (80 - 3 - 2.3 - 4.5) = 2.3 + 70.2 = 72.5 GB

空闲 72.5 GB 但因为无法找到 7.5 GB 的连续块而 OOM。
这就是碎片化问题。

FP16 → INT8: 减少 50%，精度损失 < 0.5%
FP16 → FP8: 减少 50%，精度损失 < 0.3%
FP16 → INT4: 减少 75%，精度损失 1-2%

部署建议:
INT8 量化 KV Cache 是最安全的优化
FP8 需要 Hopper 架构 GPU 支持
INT4 适合对质量不敏感的场景

策略:
- 保留最近 N 个 token 的 KV
- 保留 attention score 最高的 token（关键 token）
- 丢弃中间低 attention score 的 token

效果:
seq_len 从 32K 压缩到 4K，KV Cache 减少 87.5%
质量损失: 取决于任务，长文档 QA 损失较大，对话损失较小

代表工作: H2O, SnapKV, TOVA

vLLM 中的 KV Cache 分配策略:

1. 启动时预分配最大可用显存给 KV Cache
gpu_memory_utilization=0.9 → 90% 显存给 KV Cache

2. 计算最大可容纳的 token slots:
max_num_tokens = KV_Cache_GPU_Memory / per_token_KV_size

3. Continuous Batching:
- 每个请求用完立即释放其 block
- 新请求可以插入任何有空闲 block 的位置
- 不像传统 batching 需要等所有请求完成

4. Prefix Caching:
- 相同 system prompt 的请求共享前缀 KV
- 多轮对话场景可节省 50-90% KV Cache
- 使用 LRU 策略管理缓存前缀

KV = 2 × 80 × 16 × 16384 × 8 × 128 × 2 bytes
= 2 × 80 × 16 × 16384 × 8 × 128 × 2
= 4,294,967,296 × 16
= 68,719,476,736 bytes
≈ 64 GB