KV Cache & Inference Optimizations: 解释投机解码（speculative decoding）的无损性。

Core Concept: 用廉价草稿模型提议 k 个 token，目标模型一次并行验证；按接受/拒绝规则采样可证明输出分布与目标模型一致。

数学机理：<strong>动机</strong>——decode 阶段每步只算 1 个 token，GPU 利用率低（memory-bound + 并行度低）；若能'一次验证多个 token'，就能提升算术强度。<strong>投机解码（Leviathan 等 2023；Chen 等 2023）</strong> 用<strong>两个模型</strong>：(a) <strong>草稿模型（draft）</strong>——小、快，自回归地生成 k 个候选 token；(b) <strong>目标模型（target）</strong>——大、慢，但可<strong>一次并行</strong>计算这 k 个位置的输出分布（因为输入已知）。然后按规则逐个<strong>验证</strong>候选：对第 t 个候选 x_t，计算接受概率 min(1, p(x_t)/q(x_t))（p 为目标模型概率、q 为草稿模型概率），以该概率接受；若拒绝，则从<strong>修正分布</strong> norm(max(0, p−q)) 重新采样该位置的 token 并停止后续验证。<strong>无损性的证明要点</strong>——这套'接受/拒绝 + 修正重采样'是标准的<strong>拒绝采样（rejection sampling）</strong> 技巧：可以证明，按此规则生成的 token 的<strong>边缘分布恰好等于目标模型 p 的分布</strong>（而非近似）。直觉：当草稿模型高估某 token（q>p）时，接受概率 <1 以抵消；当草稿模型低估（q<p）时接受概率为 1，但拒绝后的修正分布补足了被低估的部分。<strong>加速来源</strong>——若草稿模型与目标模型分布接近（接受率高），则一次前向可推进多个 token，吞吐提升（论文报告 2~3 倍，无质量损失）。

深度剖析与工程权衡：① <strong>加速比的公式化</strong>——若平均接受长度为 α（每轮接受 α 个 token）、草稿开销为 c（相对目标模型的比例），则加速比约 α/(1+c)。故<strong>关键</strong>是 (a) 草稿模型与目标模型分布接近（提高 α）、(b) 草稿模型足够快（降低 c）。② <strong>草稿模型的获取</strong>——(a) 用同系列的小模型（如 LLaMA-7B 给 70B 做草稿）；(b) <strong>自投机（self-speculation）</strong>——用目标模型本身的不同层/不同精度做草稿（如早退层、量化版本）；(c) 训练专门的草稿模型（distillation）。③ <strong>与 batch 的交互</strong>——投机解码在<strong>小 batch、低负载</strong>时收益最大（此时 GPU 利用率低、有冗余算力做验证）；大 batch 时 GPU 已饱和，收益下降甚至为负（因草稿模型占用算力）。故它是'改善单请求延迟'的技术，而非'提升峰值吞吐'的技术。④ <strong>与连续批处理的配合</strong>——不同请求的接受长度不同，故需<strong>变长验证</strong>与动态调度（vLLM 的实现需处理这一点）。⑤ <strong>与 Medusa/EAGLE/MTP 的关系</strong>——这些是'不用独立草稿模型'的变体（见后续题）。⑥ <strong>面试要点</strong>——被问'投机解码为什么无损'，应给出'<strong>接受概率 min(1,p/q) + 拒绝时从 max(0,p−q) 重采样 = 拒绝采样</strong>'，并说明'边缘分布等于目标分布'；能给出加速比公式 α/(1+c) 与'小 batch 收益最大'的工程结论是明显加分。