解码策略、采样方法与 KV Cache 管理

更新日期：2026-04-17

---

一、解码策略为什么重要

1.1 同一模型，不同解码 = 截然不同的输出

训练完成的 LLM 定义了一个条件概率分布 \(P(y_t | y_{<t}, x)\)，但如何从这个分布中选出下一个 token——即解码策略——直接决定最终文本的质量、多样性和风格。同一个 70B 模型：

• Greedy decoding → 重复、无聊的文本

• Beam search (B=5) → 流畅但泛化的翻译

• Top-p=0.95, T=0.9 → 创意写作

• Top-p=0.9, T=0.6 → 稳健的代码生成

1.2 训练与推理的断裂：Exposure Bias

Exposure bias 的后果：模型在训练中看到的都是"完美前缀"，推理时遇到自己的错误输出就会进入 out-of-distribution 区域。解码策略需要在"选最可能的 token"和"保持多样性避免错误累积"之间取得平衡。

1.3 解码策略的理论视角

从信息论角度，语言模型生成的文本应当满足一定的信息量特征。Meister et al. (2023) 提出 locally typical sampling：人类语言的每个 token 的信息量接近局部熵，即 \(-\log P(y_t | y_{<t}) \approx H(Y_t | y_{<t})\)。偏离这一特征的文本（太确定或太随机）都会显得不自然。

---

二、Greedy 与 Beam Search

2.1 Greedy Decoding

每步选概率最高的 token：

\(y_t = \arg\max_{v \in V} P(v | y_{<t})\)

def greedy_decode(model, prompt_ids, max_len):
    ids = prompt_ids.clone()
    for _ in range(max_len):
        logits = model(ids)[:, -1, :]
        next_id = logits.argmax(dim=-1, keepdim=True)
        ids = torch.cat([ids, next_id], dim=-1)
        if next_id.item() == eos_id:
            break
    return ids

局限：greedy 在每步做局部最优选择，但全局序列 \(\prod P(y_t|y_{<t})\) 不一定最优。经典反例：

\(P(\text{"the dog"}) = 0.5 \times 0.9 = 0.45\)

\(P(\text{"a cat"}) = 0.4 \times 0.95 = 0.38\)

Greedy 选 "the dog"，但如果后续上下文更适合 "a cat"，全局最优解被错过。

2.2 Beam Search

维护 \(B\) 个候选假设 (beam)，每步扩展所有候选并保留得分最高的 \(B\) 个：

\(\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log P(y_i | y_{<i})\)

def beam_search(model, prompt_ids, beam_width=5, max_len=100):
    beams = [(prompt_ids, 0.0)]  # (sequence, log_prob)

    for step in range(max_len):
        all_candidates = []
        for seq, score in beams:
            logits = model(seq.unsqueeze(0))[:, -1, :]
            log_probs = F.log_softmax(logits, dim=-1)
            topk_lp, topk_ids = log_probs.topk(beam_width)

            for i in range(beam_width):
                new_seq = torch.cat([seq, topk_ids[0, i:i+1]])
                new_score = score + topk_lp[0, i].item()
                all_candidates.append((new_seq, new_score))

        beams = sorted(all_candidates, key=lambda x: x[1], reverse=True)[:beam_width]

        if all(seq[-1].item() == eos_id for seq, _ in beams):
            break

    return beams[0][0]

2.3 Length Penalty

未经修正的 beam search 偏好短序列（log-prob 累加越多越负）。标准修正 (Wu et al., 2016)：

\(\text{score}(y_{1:t}) = \frac{\sum_{i=1}^{t} \log P(y_i | y_{<i})}{lp(t)}, \quad lp(t) = \frac{(5 + t)^{\alpha}}{(5 + 1)^{\alpha}}\)

2.4 Beam Search 的适用边界

"无聊文本"问题 (Holtzman et al., 2020)：beam search 最大化似然，而人类语言的高概率区域集中在安全、泛化的表达上。人类写作不是在做最大似然搜索——人的语言充满了次优但有趣的选择。

2.5 Diverse Beam Search

标准 beam search 的 \(B\) 个 beam 往往高度相似。Vijayakumar et al. (2018) 提出 diverse beam search：将 beam 分成 \(G\) 组，组间添加多样性惩罚：

\(\text{score}_g(y) = \log P(y | y_{<t}) - \lambda \sum_{g'<g} \Delta(y, \text{beam}_{g'})\)

其中 \(\Delta\) 是多样性度量（如 Hamming 距离）。在需要生成多个不同候选的场景（如对话系统候选回复、多样化摘要）中有价值。

---

三、采样方法

3.1 Temperature Sampling

Temperature \(T\) 控制 softmax 分布的尖锐程度：

\(P(y_i) = \frac{\exp(z_i / T)}{\sum_{j} \exp(z_j / T)}\)

其中 \(z_i\) 是 logit。 数学直觉：令 \(z_1 > z_2\) 为两个 logit。比值 \(P(y_1)/P(y_2) = \exp((z_1-z_2)/T)\)。\(T\) 越小，比值越大，分布越尖锐。

def temperature_sample(logits, temperature=0.8):
    scaled = logits / temperature
    probs = F.softmax(scaled, dim=-1)
    return torch.multinomial(probs, num_samples=1)

3.2 Top-k Sampling

Fan et al. (2018) 提出：只从概率最高的 \(k\) 个 token 中采样，其余置零后重新归一化。

def top_k_sample(logits, k=50, temperature=1.0):
    scaled = logits / temperature
    topk_vals, topk_ids = scaled.topk(k)
    probs = F.softmax(topk_vals, dim=-1)
    idx = torch.multinomial(probs, num_samples=1)
    return topk_ids.gather(-1, idx)

核心问题：\(k\) 是固定的。但模型的预测分布在不同 step 差异极大： 固定 k 无法适应这种动态分布变化，这直接催生了 top-p sampling。

3.3 Top-p / Nucleus Sampling

Holtzman et al. (2020) 提出：找到最小的 token 集合 \(V_p\)，使得累积概率 \(\geq p\)：

\(V_p = \arg\min_{V' \subseteq V} |V'| \quad \text{s.t.} \quad \sum_{y \in V'} P(y | y_{<t}) \geq p\)

然后在 \(V_p\) 中重新归一化并采样。

def top_p_sample(logits, p=0.9, temperature=1.0):
    scaled = logits / temperature
    probs = F.softmax(scaled, dim=-1)
    sorted_probs, sorted_ids = probs.sort(descending=True)
    cumsum = sorted_probs.cumsum(dim=-1)

    mask = cumsum - sorted_probs >= p  # 第一个超过 p 的位置之后全部 mask
    sorted_probs[mask] = 0.0
    sorted_probs /= sorted_probs.sum()

    idx = torch.multinomial(sorted_probs, num_samples=1)
    return sorted_ids.gather(-1, idx)

典型值：p=0.9（通用）, p=0.95（高多样性）, p=0.8（低多样性）。

3.4 Min-p Sampling

Nguyen et al. (2024) 提出更直觉的截断方式：只保留概率 \(> p_{\text{base}} \times P(y_{\text{top}})\) 的 token，其中 \(P(y_{\text{top}})\) 是当前 step 概率最大的 token。

\(V_{\text{min-p}} = \{y \in V : P(y | y_{<t}) > p_{\text{base}} \times \max_v P(v | y_{<t})\}\)

def min_p_sample(logits, min_p=0.1, temperature=1.0):
    scaled = logits / temperature
    probs = F.softmax(scaled, dim=-1)

    top_prob = probs.max()
    threshold = min_p * top_prob
    mask = probs < threshold
    probs[mask] = 0.0
    probs /= probs.sum()

    return torch.multinomial(probs, num_samples=1)

3.5 Combined Strategies（实际系统的采样流水线）

现代推理引擎（vLLM, SGLang, llama.cpp）的采样流水线：

def combined_sampling(logits, config):
    # Step 1: Temperature scaling
    logits = logits / config.temperature

    # Step 2: Repetition / frequency / presence penalty
    for token_id, count in generated_counts.items():
        logits[token_id] -= config.repetition_penalty * count
        logits[token_id] -= config.frequency_penalty * count
        logits[token_id] -= config.presence_penalty * (1 if count > 0 else 0)

    # Step 3: Top-k filtering
    if config.top_k > 0:
        topk_vals, _ = logits.topk(config.top_k)
        logits[logits < topk_vals[:, -1:]] = -float('inf')

    # Step 4: Top-p filtering
    if config.top_p < 1.0:
        sorted_logits, sorted_ids = logits.sort(descending=True)
        cumprobs = F.softmax(sorted_logits, dim=-1).cumsum(dim=-1)
        mask = cumprobs - F.softmax(sorted_logits, dim=-1) >= config.top_p
        sorted_logits[mask] = -float('inf')
        logits = sorted_logits.scatter(-1, sorted_ids, sorted_logits)

    # Step 5: Min-p filtering
    if config.min_p > 0:
        probs = F.softmax(logits, dim=-1)
        top_prob = probs.max()
        logits[probs < config.min_p * top_prob] = -float('inf')

    # Step 6: Sample
    probs = F.softmax(logits, dim=-1)
    return torch.multinomial(probs, num_samples=1)

重复惩罚机制

采样策略综合对比

---

四、KV Cache 深度解析

4.1 为什么需要 KV Cache

Transformer 解码时，每生成一个新 token 都需要与所有历史 token 做 attention。如果不缓存，每步都要重新计算所有位置的 \(K, V\)：

无 KV Cache：生成第 \(t\) 个 token 时，需对 \(t\) 个位置执行投影 \(K = XW_K, V = XW_V\)。生成整个长度 \(n\) 的序列总计算量：

\(\sum_{t=1}^{n} O(t \cdot d) = O(n^2 \cdot d) \quad \text{per token 平均 } O(n \cdot d)\)

有 KV Cache：将已计算的 \(K_{1:t-1}, V_{1:t-1}\) 缓存，第 \(t\) 步只计算新 token 的 \(k_t, v_t\)：

\(K_{1:t} = [K_{\text{cache}}; k_t], \quad V_{1:t} = [V_{\text{cache}}; v_t]\)

每步计算量降至 \(O(d)\) 的投影 + \(O(t \cdot d)\) 的 attention，省去了 \(O(t \cdot d)\) 的重复投影。

4.2 KV Cache 内存公式

\(\text{KV Cache (bytes)} = 2 \times L \times n_{\text{kv}} \times d_h \times s \times b \times \text{dtype\_bytes}\)

其中：

• \(2\)：K 和 V 各一份

• \(L\)：层数

• \(n_{\text{kv}}\)：KV head 数（GQA 下小于 query head 数）

• \(d_h\)：head 维度

• \(s\)：序列长度

• \(b\)：batch size

• \(\text{dtype\_bytes}\)：数据类型字节数（BF16=2, FP8=1）

4.3 KV Cache 压缩技术

H2O: Heavy Hitter Oracle

Zhang et al. (2024) 观察到 attention 权重的分布高度不均匀：少数 token（heavy hitters）持续获得高 attention，大量 token 几乎不被关注。

class H2OKVCache:
    def __init__(self, budget, n_sink=4, n_recent=64):
        self.budget = budget
        self.n_sink = n_sink
        self.n_recent = n_recent
        self.n_heavy = budget - n_sink - n_recent
        self.attn_scores = None  # 累积 attention 分数

    def update(self, new_k, new_v, attn_weights):
        self.k_cache = torch.cat([self.k_cache, new_k], dim=-2)
        self.v_cache = torch.cat([self.v_cache, new_v], dim=-2)

        self.attn_scores = self._accumulate(attn_weights)

        if self.k_cache.shape[-2] > self.budget:
            self._evict()

    def _evict(self):
        seq_len = self.k_cache.shape[-2]
        sink_ids = list(range(self.n_sink))
        recent_ids = list(range(seq_len - self.n_recent, seq_len))

        middle_ids = list(range(self.n_sink, seq_len - self.n_recent))
        middle_scores = self.attn_scores[middle_ids]
        heavy_ids = [middle_ids[i] for i in middle_scores.topk(self.n_heavy).indices]

        keep_ids = sorted(sink_ids + heavy_ids + recent_ids)
        self.k_cache = self.k_cache[:, :, keep_ids, :]
        self.v_cache = self.v_cache[:, :, keep_ids, :]

KIVI: 超低精度 KV Cache 量化

KIVI (Liu et al., 2024) 的核心发现：Key 和 Value 的数值分布特征不同，需要不同的量化策略。

4.4 Attention Sink 现象

Xiao et al. (2023) 发现：无论输入内容如何，序列开头的 token（通常是 BOS 或前 2-4 个 token）总是获得异常高的 attention 权重。

这不是因为这些 token 语义重要——即使把 BOS 换成任意 token，该现象依然存在。原因：

1. Softmax 的归一化需求：attention 权重必须 \(\sum = 1\)。当模型"不需要关注任何特定 token"时，需要一个"垃圾桶"来倾倒多余的 attention 质量

2. 位置偏差：初始 token 在所有 attention 计算中都存在（causal mask 不会遮挡它们），因此模型学会了将它们作为默认的 attention 接收器

3. 训练动态：梯度会强化这种模式——一旦某个位置开始充当 sink，后续训练会进一步加强这种行为

实践影响：

---

五、Speculative Decoding 概览

5.1 核心思想

自回归解码是 memory-bandwidth bound：每生成一个 token 需要读取整个模型权重，但 GPU 的 FLOPS 远未饱和。Speculative decoding 利用这一 gap：

1. 用小 draft 模型快速生成 \(K\) 个候选 token

2. 用大 target 模型一次前向传播并行验证所有 \(K\) 个 token

3. 数学保证输出分布与直接用 target 模型完全一致

\(P(\text{accept } y_i) = \min\left(1, \frac{P_{\text{target}}(y_i)}{P_{\text{draft}}(y_i)}\right)\)

5.2 变体速览

---

六、Structured Decoding

6.1 为什么需要结构化解码

LLM 在 agent 和工具调用场景中需要生成符合特定格式的输出（JSON、SQL、API 调用）。自由采样生成的文本可能违反格式约束，导致：

• JSON parse 失败

• API 参数类型错误

• SQL 语法不合法

6.2 Grammar-Guided Decoding

核心思路：在每步采样时，根据目标语法（如 JSON schema、正则表达式、CFG）mask 掉不合法的 token，只从合法 token 中采样。

class GrammarConstrainedSampler:
    def __init__(self, grammar, tokenizer):
        self.fsm = grammar.compile_to_fsm()
        self.tokenizer = tokenizer
        self.state = self.fsm.initial_state

    def sample(self, logits):
        valid_token_ids = self.fsm.get_valid_tokens(self.state, self.tokenizer)

        mask = torch.full_like(logits, -float('inf'))
        mask[valid_token_ids] = 0.0
        constrained_logits = logits + mask

        probs = F.softmax(constrained_logits, dim=-1)
        token_id = torch.multinomial(probs, num_samples=1)

        self.state = self.fsm.transition(self.state, token_id)
        return token_id

6.3 主要框架

6.4 性能影响

Grammar-guided decoding 的关键问题是 mask 计算开销：

---

七、选型指南

使用场景	推荐策略	Temperature	Top-p	其他	为什么
机器翻译	Beam search (B=4-5) + length penalty	-	-	\(\alpha=0.6\)	目标输出高度确定，搜索比采样更好；beam 捕获全局最优翻译
代码生成 (pass@1)	Temperature sampling	0.6-0.8	0.9	-	代码需要正确性但有多种实现；中等 T 平衡正确率和多样性
代码生成 (pass@k, k>1)	Temperature sampling	0.8-1.0	0.95	生成 k 个不同方案	高 T 增加多样性，多次采样取最好；Chen et al., 2021 的 Codex 论文验证此策略
创意写作	Top-p + temperature	0.9-1.2	0.95	presence penalty=0.6	需要意外性和丰富词汇；高 T + presence penalty 鼓励新词新表达
事实性问答	Greedy 或低 T	0.0-0.3	-	-	答案唯一或近唯一，不需要多样性；高 T 引入的随机性只会降低准确率
JSON/结构化输出	Grammar-guided + 低 T	0.2-0.5	-	JSON Schema 约束	格式必须合法，grammar constraint 保证结构正确；低 T 减少字段值的随机性
对话 (chatbot)	Top-p + temperature	0.7-0.9	0.9	rep. penalty=1.1	平衡自然度与一致性；rep. penalty 避免机械重复
文本摘要	Beam search 或低 T sampling	0.3-0.5	0.9	length penalty	需要忠实于原文（高确定性）但避免逐字抄写（适度多样性）

使用场景	推荐策略	Temperature	Top-p	其他	为什么
Agent 工具调用	Greedy + structured decoding	0.0	-	function schema 约束	工具调用参数必须精确；任何随机性都可能导致无效调用

---

八、追问延伸

1. Best-of-N sampling vs beam search：生成 \(N\) 个独立样本，用 reward model 选最优。为什么这种"采样+排序"范式在 RLHF 后的模型上优于 beam search？

2. Speculative decoding 的理论最优 draft 长度：给定 draft 模型接受率 \(\gamma\)，最优 \(K = ?\)。\(K\) 太大浪费 draft 计算，\(K\) 太小无法充分利用 target 的并行验证能力。

3. Adaptive temperature：能否让模型自适应调整 temperature？Entropy-Guided Temperature (2024) 根据预测分布的熵动态调整 \(T\)——高熵时降 \(T\)（模型不确定时保守），低熵时升 \(T\)（模型自信时可以冒险）。

4. 解码策略与 alignment 的交互：RLHF/DPO 训练后的模型分布已经被"重塑"，此时 temperature 和 top-p 的最优值是否需要重新调整？

---

参考文献

1. Wu, Y., et al. (2016). "Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation." arXiv:1609.08144

2. Fan, A., Lewis, M., & Dauphin, Y. (2018). "Hierarchical Neural Story Generation." arXiv:1805.04833

3. Vijayakumar, A.K., et al. (2018). "Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models." arXiv:1610.02424

4. Keskar, N.S., et al. (2019). "CTRL: A Conditional Transformer Language Model with Controllable Generation." arXiv:1909.05858

5. Holtzman, A., et al. (2020). "The Curious Case of Neural Text Degeneration." arXiv:1904.09751

6. Chen, M., et al. (2021). "Evaluating Large Language Models Trained on Code." arXiv:2107.03374

7. Leviathan, Y., Kalman, M., & Matias, Y. (2022). "Fast Inference from Transformers via Speculative Decoding." arXiv:2211.17192

8. Meister, C., et al. (2023). "Locally Typical Sampling." arXiv:2210.07185

9. Ainslie, J., et al. (2023). "GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints." arXiv:2305.13245

10. Kwon, W., et al. (2023). "Efficient Memory Management for Large Language Model Serving with PagedAttention." arXiv:2309.06180

11. Xiao, G., et al. (2023). "Efficient Streaming Language Models with Attention Sinks." arXiv:2309.17453

12. Jiang, A.Q., et al. (2023). "Mistral 7B." arXiv:2310.06825

13. Zheng, L., et al. (2023). "SGLang: Efficient Execution of Structured Language Model Programs." arXiv:2312.07104

14. Cai, T., et al. (2024). "Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads." arXiv:2401.10774

15. Li, Y., et al. (2024). "EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty." arXiv:2401.15077

16. Fu, Y., et al. (2024). "Break the Sequential Dependency of LLM Inference Using Lookahead Decoding." arXiv:2402.02057

17. Liu, Z., et al. (2024). "KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache." arXiv:2402.02750

18. Zhang, Z., et al. (2024). "H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models." arXiv:2306.14048

19. DeepSeek-AI. (2024). "DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model." arXiv:2405.04434

20. Nguyen, M., et al. (2024). "Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs." arXiv:2407.01082

21. Dong, H., et al. (2024). "XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models." arXiv:2411.15100

---

↑ 上级 · G. 推理与部署