datawhale社区Datawhale-学用 AI,从此开始llm-algo-leetcode教程地址GitHub - datawhalechina/llm-algo-leetcode: LLM algorithm practice lab with theory, solutions, and test cases.《大模型算法与系统教程》面向大模型入门到进阶的算法实战教程覆盖原理讲解、答案解析、测试用例与 CUDA/Triton 实战。 · GitHubTop-p中恢复顺序解决的问题索引对齐。模型输出的 logits 不是随便一串数字它的位置是有含义的logits[5] 4.0 → 意思是词表中第 5 号词的得分是 4.0logits[6] 3.1 → 第 6 号词的得分是 3.1后续所有操作softmax、torch.multinomial采样都默认采样返回的下标就是 token ID可以直接拿去 embedding 表查词、拼到序列里继续生成。排序之后下标的含义变了torch.sort之后sorted_logits [4.0, 3.1, 2.3, 1.2, 1.1, 0.4, 0.1, 0.0, -0.5, -1.0]sorted_indices [ 5, 6, 1, 3, 8, 2, 0, 7, 4, 9 ]现在sorted_logits[0] 4.0但它的下标 0不再代表词表第 0 号词它实际对应的是原来的第 5 号词。排序只是为了方便从大到小累加概率找截断点是一个临时的计算视角。如果不恢复顺序会发生什么假设直接拿sorted_logits去做torch.multinomial采样返回下标1你以为采样到了词表第 1 号词实际上那对应排序后数组里的 3.1真正该输出的是第 6 号词。也就是说确实找到了概率大的那批词、也砍掉了尾部但采样出来的 token ID 是错位的生成结果就全乱了。投机编码中以 p/q 的概率接受是怎么执行的它就是一次掷硬币。假设 p(x)0.4q(x)0.5那么 p/q0.8。执行方式是生成一个 [0,1) 区间上的均匀随机数 r相当于掷一枚概率硬币如果 r0.8接受否则拒绝。因为 r 在 [0,1) 上均匀分布所以 r0.8 这件事发生的概率恰好就是 80%。以 0.8 的概率接受不是接受 0.8 个 token而是每次验证时掷一次硬币有 80% 的几率通过。举个生活化的类比小模型过于自信觉得某个词有 50% 概率该出现q0.5但大模型认为只有 40%p0.4。小模型超额推荐了这个词所以不能全信它只能按比例打折扣——它的推荐只按 0.4/0.580% 的可信度采纳。为什么偏偏是 p/q当 p(x)≥q(x) 时大模型认为 x 至少和小模型说的一样可能出现小模型没有夸大所以 100% 接受当 p(x)q(x) 时小模型夸大了 x 的出现频率它采样出 x 的次数太多了。要把它在最终输出中的占比从 q 压回到 p就需要按 p/q 的比例抽样保留——从 q 份样本里均匀抽走 p 份正好把频率从 q 校正到 p。若 p≥qq(x)×1q(x)而这个 token 本来就处于大模型概率更高的区间多出来的部分 p(x)−q(x) 由拒绝后的修正采样从调整后的分布 norm(max⁡(0,p−q)) 中重新采样补回来。两者相加恰好等于 p(x)若 pqq(x)×p(x)q(x)p(x)q 恰好被约掉直接等于大模型的概率。大模型既然都算出 K 个位置的概率了直接每个位置采样一个不就行了不能直接这么做因为大模型那 K 个位置的概率是在草稿前缀下算出来的前缀一旦错了后面的概率就全部作废。投机解码的加速本质是用一次并行前向换掉 K 次串行前向正常自回归大模型要走 K 次前向每次只前进 1 个 token投机解码小模型先便宜地猜出 K 个 token把这 K 个候选 token一次性喂给大模型。由于注意力是因果的每个位置只能看到前面的内容大模型在一次前向里就能同时给出这 K 个位置的预测。而推理阶段的大模型前向主要是访存瓶颈每步都要把几十 GB 的权重从显存搬一遍所以一次前向算 1 个 token 和算 K1 个 token 的耗时差距很小。这就是一次验证换 K 次调用的账。那为什么不能直接拿大模型这 K 个位置的结果用关键陷阱在于大模型第 i 个位置的概率分布是以草稿的前 i-1 个 token为条件算出来的。举个具体例子。小模型草拟了 3 个 token草稿: 我 → 爱 → 猫大模型一次前向给出:位置0: P(下一个 | 上文) ← 无条件依赖草稿位置1: P(下一个 | 上文 我) ← 依赖草稿第0个位置2: P(下一个 | 上文 我 爱) ← 依赖草稿第0、1个现在假设验证时发现位置 1 的爱被拒绝了大模型其实想说喜欢。那么位置 2 的那个分布P(下一个 | 上文 我 爱)是在错误的前缀下算的——大模型心里想的是我爱后面接什么而真实序列要走的是我喜欢。这个分布直接作废位置 2 的采样结果不能代表大模型的真实意图。所以如果图省事直接每个位置采一个得到的序列分布就和纯大模型自回归不一样了——这就是有损的文本质量会退化投机解码无损加速的核心卖点也就没了。比较环节到底在干什么?比较接受-拒绝循环实际上是在回答一个问题草稿前缀到哪一步为止还是可信的从头逐个检查被连续接受的前缀部分大模型对应位置的概率分布才是基于正确前缀算的可以放心使用一旦某步被拒绝从这个位置开始大模型已经算好的后面那些概率全部作废只能等下一轮前向重新算。而且这个比较本身几乎零成本——只是对 K 个标量做大小比较和掷硬币相比一次大模型前向可以忽略不计。真正的开销结构是方案大模型前向次数产出 token 数纯大模型自回归K 个 tokenK 次K投机解码1 次 廉价的验证循环接受的个数最好 K14.投机解码是多 token 解码的一种实现吗可以这么理解但更准确的说法是投机解码是多 token 解码这个大类里最经典的一种实现。多 token 解码是一个目标导向的伞状概念——让一次解码步尽量推进多个 token凡是服务于此目标的方案都算方法提议proposal从哪来Speculative Decoding投机解码用一个独立的小草稿模型连续采样Medusa在大模型上加几个额外的多头同时预测未来几个位置Lookahead / Jacobi 解码不需要草稿模型用 n-gram 缓存或并行迭代猜后续 tokenEAGLE在大模型特征层上做自回归草稿它们的共同点正是本章强调的三件事接受率、验证成本、回退策略。所以教材导读里说两者都在减少 token-level 往返——投机解码侧重谁提议、谁验证的分工多 token 解码侧重一步推进多少个的形态前者是后者的一个具体形态。一个重要差异第 23 章投机解码用的是严格的接受-拒绝采样min⁡(1,p/q) 掷硬币保证输出分布无损本章的接受规则target_prob draft_prob * min_accept_ratio只是一个简化的启发式阈值教学上用来说明控制流并不保证分布无损。教材在 Step 3 里也明确说了这一点真实系统会使用更严格的分布校正或采样验证规则。5.为什么一个请求要分成 prefill 和 decode 两步这两个阶段都要算注意力、都要跑完整的前向真正的区别在于一次前向处理多少个 token以及由此带来的完全不同的硬件特性。Prefill预填充一次性读完用户的 prompt用户发来一段 prompt比如 500 个 token模型需要把这段输入消化掉。Prefill 做的事把这 500 个 token一次性并行喂进模型跑一次前向计算过程中每一层为这 500 个 token 生成的 Key 和 Value 被存下来形成 KV Cache顺带产出下一个 token的概率分布也就是第一个生成 token。所以 prefill 的产物不是注意力分数而是KV Cache 第一个输出 token。这一步是大规模矩阵乘矩阵的运算GPU 算力吃满属于计算密集型compute-bound。Decode解码一次只生成一个 token反复循环进入 decode 后每一步只做一件事拿最新的 1 个 token跑一次前向注意力计算时这个新 token 去查询之前 prefill以及之前所有 decode 步存下的 KV Cache——旧的 K/V 不用重算直接查缓存采样出下一个 token同时把这一步新产生的 K/V 追加进 cache。如此循环直到生成结束。每步只算 1 个 token但每步都要把几十 GB 的模型权重和 KV Cache 从显存搬一遍GPU 算力大量闲置属于访存密集型memory-bound。那为什么要分成两步看待不是人为要分而是它们的物理特性天然不同必须区别对待PrefillDecode处理 token 数整段 prompt几百~几千每步 1 个瓶颈算力compute-bound显存带宽memory-bound执行方式一次并行前向反复串行循环耗时特征一次性、较重单次轻、但次数极多这正是调度要处理的核心矛盾一个长 prompt 的 prefill 会霸占 GPU 很久让正在 decode 的请求憋住吐不出下一个字延迟抖动反过来如果只顾 decode新请求的首 token 延迟TTFT又会爆炸。教材里_schedule_key把phase放在排序键第一位就是在处理这一步该推进 prefill 还是 decode的取舍。你后面会读到的第 38 章 PD 分离更极端——干脆把两个阶段放到不同的 GPU 集群上跑。