投机采样 · 为什么它能无损加速
A small model guesses ahead, a big model checks the work — and the answer is provably identical to the big model alone. Here is why, built from playable timelines. 小模型抢跑猜答案,大模型只负责验收 —— 而最终输出和"只用大模型"分毫不差。这篇用可以玩的"时间线"讲清楚它为什么无损。
Both produce the same text. Speculative decoding just gets there in fewer expensive steps. 两者输出完全相同,投机解码只是用更少的"昂贵步骤"到达终点。
Generating text from an LLM is autoregressive: to produce the next token, the model must read every weight in from GPU memory — then it emits one token and does it all again. Decoding is memory-bandwidth bound, so the GPU's math units sit mostly idle. 大模型生成文本是自回归的:每吐一个字,都要把所有权重从显存里搬一遍,然后只产出一个 token,再重来。解码是受显存带宽限制的,GPU 的算力大部分时间在空转。
Key observation: checking k tokens in a single forward pass costs almost the same wall-clock time as generating one, because the expensive weight-loading happens only once. That spare compute is a free lunch — if only we had candidate tokens to check. 关键观察:在一次前向里同时校验 k 个 token,和只生成一个的耗时几乎一样 —— 因为昂贵的"搬权重"只发生一次。这些闲置算力就是免费的午餐 —— 只要我们手上有候选 token 可以校验。
So: let a cheap draft model (SLM) propose a burst of tokens, then let the expensive target model (LLM) verify them all at once. Accept the good ones, fix the first bad one, repeat. The whole trick lives in how you accept and fix — do it right and the output distribution is exactly the target's. 于是:让便宜的草稿模型(SLM)一口气提议一串 token,再让昂贵的目标模型(LLM)一次性校验。接受对的、修正第一个错的、然后重复。全部玄机都在如何接受与修正 —— 做对了,输出分布就和目标模型完全一致。
Two probability distributions over the same vocabulary. p is what the target LLM wants. q is what the draft SLM proposes. Our only job: turn samples from q into samples that look like they came from p — without ever fully trusting q. 同一个词表上的两个概率分布。p 是目标大模型想要的,q 是草稿小模型提议的。我们唯一要做的:把从 q 采样得到的 token,变成看起来像从 p 采样出来的 —— 且永远不完全相信 q。
To make it concrete, we shrink the vocabulary to two words, straight from the original article: 为了具体,我们把词表缩到只有两个词(直接沿用原文的设定): 💗 love / 爱 🖤 hate / 恨.
Imagine sampling the next token 5 times from each model — five parallel timelines. The target LLM's five draws land as 💗💗💗🖤🖤 (3 love, 2 hate). The draft SLM's five draws land as 💗🖤🖤🖤🖤 (1 love, 4 hate). 想象从每个模型各采样 5 次 —— 五条平行时间线。目标 LLM 的五次结果是 💗💗💗🖤🖤(3 爱 2 恨),草稿 SLM 的五次结果是 💗🖤🖤🖤🖤(1 爱 4 恨)。
The SLM over-produced hate and under-produced love. To make the SLM's timelines look like the LLM's, some timelines must be erased and re-sampled ("rejected"), while the rest are kept ("accepted"). Play with it: SLM 多生产了"恨",少生产了"爱"。要让 SLM 的时间线看起来像 LLM 的,就得把一些时间线抹掉重采样(拒绝),其余的保留(接受)。动手玩一下:
We track one quantity: P(X = a token), the probability the final emitted token equals some value. We want to show it equals the target p. Reveal the steps one at a time. 我们只盯住一个量:P(X = 某个token),即最终吐出的 token 等于某个值的概率。我们要证明它等于目标 p。逐步揭示:
Two rules did all the work. Let's earn each one with its own playground. 两条规则完成了全部工作。下面各用一个小玩具把它们"挣"回来。
The draft handed you token a, which it drew with prob q(a). The target only wanted it with prob p(a). So keep it with probability min(1, p(a)/q(a)): if the draft under-sampled it (q<p) always keep it; if it over-sampled it (q>p) keep only the fair fraction. 草稿递给你 token a,它以概率 q(a) 采到它;而目标只以概率 p(a) 想要它。于是以 min(1, p(a)/q(a)) 的概率保留:草稿少采了(q<p)就全保留,多采了(q>p)就只保留公平的那一比例。
When a draft token is rejected, we can't just resample from p — that would double-count the mass we already accepted. We resample from the residual (p−q)+ = max(0, p−q), normalized. It's exactly the probability that "leaked" past the accept step. Binary vocab hides this (the residual is only 0 or 1), so here we add a third token 🤍 meh / 无. 当草稿 token 被拒绝时,不能直接从 p 重采样 —— 那会把已经接受的部分重复计。我们从残差 (p−q)+ = max(0, p−q)(归一化后)重采样,它正是"漏过"接受步骤的那部分概率。二元词表看不出这点(残差只有 0 或 1),所以这里加入第三个 token 🤍 无。
The bars are the empirical output distribution; the gold ticks are the target p. As samples grow, the bars snap to the gold — the sampler emits exactly p, whatever the draft q was. That is losslessness, demonstrated. 柱子是输出的经验分布,金色刻度是目标 p。样本越多,柱子越贴近金线 —— 无论草稿 q 是什么,采样器都精确输出 p。这就是被演示出来的"无损"。
Zoom out from one token to a sentence. The draft proposes a run of 4 tokens; the target verifies them in a single forward pass, accepting the longest correct prefix, then either fixing the first mismatch from the residual or adding one free bonus token. Step through a run: 从"一个 token"放大到"一句话"。草稿一次提议 4 个 token;目标在一次前向里全部校验,接受最长的正确前缀,然后要么用残差修正第一个不匹配处,要么白送一个 bonus token。逐步走一遍:
■ accepted draft · ■ rejected · ■ target's fix / bonus. A vanilla decoder would need one pass per token. ■ 接受的草稿 · ■ 被拒绝 · ■ 目标的修正/bonus。普通解码器每个 token 都要一次前向。
If each drafted token is accepted with probability α, a block of γ draft tokens yields on average (1 − αγ+1) / (1 − α) tokens per target pass. Higher α (better-aligned draft) or bigger γ both help — until draft cost eats the gains. 若每个草稿 token 以概率 α 被接受,一块 γ 个草稿 token 平均每次目标前向产出 (1 − αγ+1) / (1 − α) 个 token。α 越高(草稿越对齐)或 γ 越大都有帮助 —— 直到草稿本身的成本吃掉收益。
speedup vs. α (dashed = your γ) 加速比随 α 变化(虚线 = 当前 γ)
Speculative sampling was proposed almost simultaneously by Leviathan, Kalman & Matias (Google, 2022→ICML 2023) and Chen et al. (DeepMind, 2023), generalising the draft-then-verify idea of Blockwise Parallel Decoding (Stern et al., 2018). Both report a 2–3× lossless latency win. Since then a whole family has grown: 投机采样几乎同时由 Leviathan、Kalman、Matias(Google, 2022→ICML 2023)与 Chen 等(DeepMind, 2023)提出,推广了 Blockwise Parallel Decoding(Stern 等, 2018)的"草稿-验收"思想。两者都报告了 2–3× 的无损加速。此后衍生出一整个家族: