理解采样背后的优化逻辑
在 Artificial Analysis 的 Kimi 服务商对比中,各家 inference 团队都在竞争更高的 tokens per second(TPS)。一个自然的问题是:同一个模型,如果大家使用相同型号的 GPU,并发都是 1,测试的 prompt 也相同,速度差距还会来自哪里?这篇文章会先从Sampler讲起,然后衍生到一个针对开源 sglang 的 decode 性能优化。本系列后续文章也会沿用 SGLang 作为代码参考。
投机采样先由draft模型提出一串 draft token,再由 target model 一次验证,输出接受的tokens。具体细节会由之后的文章来论述,本文先介绍high level的框架。如下伪代码所示:
Input: context, draft_state, draft_policy, target_policy, rng, D (draft length)
Output: accepted_tokens, next_token
for j ← 0 to D-1:
draft_logits[j], draft_state ← DraftForward(context, d[:j], draft_state)
d[j], draft_info[j] ← DraftSample(draft_logits[j], draft_policy, rng[j])
target_logits ← TargetForward(context, d)
target_info ← TargetDistribution(target_logits, target_policy)
L, next_token ← VerifyAndSample(d, draft_info, target_info, rng)
accepted_tokens ← d[:L]
DraftForward 与 TargetForward 负责产生 logits,Draft/Target模型架构不影响细节。在文本可以先假设我们讨论Chain的投机采样,先不讨论Tree Draft,毕竟我们关注的重点是 DraftSample、TargetDistribution 和 VerifyAndSample:如何抽 token,需要保留哪些概率信息,以及这些信息如何计算。
draft_info 包括了 Draft 分布 $q$;target_info 包括了 target 分布 $p$; draft_policy 和 target_policy 则代表了Sampling策略,主要包括:
top_k=-1 表示禁用 top-k。top_p=1 表示不截断。temperature=0或者top_k=1代表Greedy,参考SGLang SamplingParams。另外,draft 的 sampling policy 不必与 target 相同,但通常来说 draft_info 需要保留概率分布(原因见下面reject sampling章节)。本文检查的 SGLang 链式 proposal 路径不做请求的 top-k/top-p 截断;TRT-LLM 的 advanced draft sampler 则可以复用请求的 top-k/top-p。后者参考 commit 8e20795612 的 _draft_sampler_advanced,不能把一种路径的选择推广到所有 draft 实现。
Note:Top-p sampling 也称为 nucleus sampling,HuggingFace 文档使用 nucleus filtering 这个名称。本文称为 top-p 筛选。
这一章分场景讨论能省掉哪些工作:只要 token 时,尝试省去 softmax;需要概率时,减少归一化的扫描与通信;需要 top-p 时,减少确定保留集合的工作。后文重点讨论 top-p,top-k 只在需要说明组合顺序时涉及。2.1 和 2.2 都假设只应用 temperature;启用 top-k 时,必须先完成全局选择并 mask,归一化摘要不能替代这一步。
这里的优化是用 Gumbel-max 直接从 logits 抽 token,省去先生成完整 softmax 概率的步骤。前提是只应用 temperature,没有 top-k、top-p 等过滤,后续也不需要查询概率;greedy 则直接取 argmax。
具体做法是给每个 token 的 logit 加上独立的 Gumbel 噪声,再取 argmax。每个 token 都有机会靠噪声成为最大值,最终被选中的概率恰好等于 softmax 定义的概率。公式如下,证明见 Appendix A:
\[U_i\sim\mathrm{Uniform}(0,1),\qquad G_i=-\log(-\log U_i),\qquad \mathrm{token}=\arg\max_i(z_i/T+G_i).\]$\log$ 是自然对数,$U_i$ 对每个token都彼此独立;$G_i$ 服从标准 Gumbel 分布。Gumbel-max 是用它完成抽样的方法。后文的 GumbelMax(scores, rng) 返回选中的 token;需要跨 rank merge 时,则显式保留加噪声后的 score 与 token ID。
这里的优化是用一次小摘要交换替代完整 logits 聚合,并把局部最大值与指数和放进同一次扫描。因为后续需要查询概率,不能省去归一化;但求本地 token 的概率,并不需要拿到其他 rank 的所有 logits。这里同样假设没有 top-k/top-p 等过滤。下面先给出 baseline,再展开摘要如何同时支持抽样与概率计算,令 $x_i=z_i/T$。
在 TP 词表分片的情况下,一个直接的实现是先聚合完整 logits,再计算 softmax 和抽样。每个 rank 都得到完整概率数组:
Input: x_local (scaled logits [V/TP]), rng
Output: p (probabilities [V]), token, p_token
x ← AllGather(x_local)
p ← Softmax(x)
token ← GumbelMax(x, rng)
return p, token, p[token]
Stable Softmax的数学公式如下: \(p_i=\frac{e^{x_i-M}}{S},\qquad M=\max_i x_i,\quad S=\sum_i e^{x_i-M}.\)
Online softmax则不要求完整的数据,每个rank 得到局部信息 $(m_r,s_r)$,其中 $s_r=\sum_{i\in r}e^{x_i-m_r}$。最后通过交换这些信息即可:
\[p_i=e^{x_i-\mathrm{LSE}}, \qquad M=\max_r m_r,\qquad S=\sum_r s_r e^{m_r-M},\qquad \mathrm{LSE}=M+\log S.\]LSE 在数学上等于 $\log\sum_i e^{x_i}$,证明见 Appendix B。工程上保留 $(M,S)$ 更稳妥,按 $p_i=e^{x_i-M}/S$ 求概率;若把带有很大公共偏移的 logits 压成单个 FP32 LSE,可能丢失归一化信息。后文用 OnlineSoftmaxStats 得到局部 $(m_r,s_r)$,MergeSoftmaxStats 返回全局 $(M,S)$。
这里有两个独立优化:交换 $(m_r,s_r)$ 减少通信,online 更新减少本地计算统计量时的遍历。普通 local max 再求 sum 也能产生相同的摘要。两个数只是归一化摘要;抽样还需要 winner 的 score、token ID 和 scaled logit。每个 rank 发出的摘要大小不随词表长度增长,AllGather 收到的总量仍随 TP 大小增长。
计算Gumbel-Max的逻辑也可以通过类似的方式实现,每个 rank 对 local logits 加 Gumbel 噪声,选出local winner,再通过all-gather选择最终winner。可以将all-gather合并,避免了增加额外通信次数。
Input: x_local (scaled logits [V/TP]), global_ids, rng
Output: p_local (probabilities [V/TP]), token, p_token
key_local ← x_local + Gumbel(rng, global_ids)
winner ← ArgMax(key_local)
m_local, s_local ← OnlineSoftmaxStats(x_local)
record ← (key_local[winner], global_ids[winner],
x_local[winner], m_local, s_local)
records ← AllGather(record)
best ← ArgMax(records.key)
token ← records[best].token_id
M, S ← MergeSoftmaxStats(records.m, records.s)
p_local ← Exp(x_local - M) / S
p_token ← Exp(records[best].x - M) / S
return p_local, token, p_token
两版都返回概率、token 和该 token 的概率。区别是 baseline 的 p 在每个 rank 上包含完整词表,新版本的 p_local 只包含 local token的概率。若要求完整的 p,则还需 AllGather(p_local)。
这里要减少确定 top-p 集合的工作。假设已经通过 AllGather(logits) 和 softmax 得到完整概率,接下来不一定需要排序整个词表:概率集中时可以只排序少量候选;否则可以通过分桶逐步定位边界。先用完整排序作为baseline,再介绍这两种改进。
下面用 $p_i$ 表示概率,$P$ 表示 top-p 阈值。本文统一保留 cutoff 上的全部并列项:例如 $p=(0.4,0.3,0.3)$、$P=0.5$,三个 token 都保留,而不是按 token ID 只取最短前缀。Sort、Candidate、Bucket 和 Dual Pivot 都采用这个规则;对照框架时也必须检查它的 ties 语义。
Sort + PrefixSum + LowerBound
SortTopP(p, P) 表示它。LowerBound 是“找第一个不小于目标的位置”;GPU 也可以并行比较后取最小索引,不必逐步二分。Candidate Selection
SortTopP。后文统一称为 CandidateTopP;如果条件不满足,Fallback到其他实现。top_p=0.95 的边界;若buffer里token的总概率只有 0.80,则不够,fallback。Bucket Selection
当候选快速路径不能直接确定结果时,可以通过分桶避免完整排序,因为 top-p 只需要边界,不需要所有 token 的完整次序。每个桶累计概率和,从高桶向低桶做前缀和,用 LowerBound 找到达到剩余目标质量的桶。更高的桶全部保留,更低的桶全部排除,只继续处理边界桶。例如更高的桶已经累计 0.80,目标是 0.95,下一轮就在边界桶内寻找剩余的 0.15。关键是如何分桶。
按数值区间分桶:对 $[a,b)$ 设定桶宽 $\Delta$,桶编号为 floor((value-a)/Δ),下一轮再细分边界区间。后文称为 HistogramSelect。
按浮点编码分桶:对非负 FP32 概率,把原始 32 位编码按无符号整数读取,得到保持数值顺序的 key。不是浮点转整数取整,也不是随机分配 key。
| 概率 | FP32 key |
|---|---|
| 0.125 | 0x3E000000 |
| 0.25 | 0x3E800000 |
| 0.5 | 0x3F000000 |
每轮读取 key 的一组位作为桶编号,例如 (key >> 24) & 255,先处理高位,再处理边界桶的低位。这就是 radix selection,后文称为 RadixSelect。浮点编码产生的桶并不按数值等宽。AIR Top-P 使用这类算法。读完所有位后,同一 key 的项无法再拆分,按本文规则全部保留为 cutoff ties。
Bucket Selection 本身通常不需要 fallback:只要搜索范围覆盖全部有效数值,并持续细分边界桶,就能确定结果。但部分实现为了加速,会限制最后取出并排序的边界桶最多包含多少个 token(例如 2048 个),或先跳过数量可能很多的小概率 token。如果实现不再继续细分,而边界桶仍超过容量,或未跳过的 token 的累计概率不足以达到 top-p,就需要 fallback 到不受这些限制的完整筛选,不能直接丢弃这些 token 来返回结果。
这里的优化是直接抽出符合 top-p 分布的 token,省去先构建完整保留集合的步骤。因为调用方只需要一个 token,不需要筛选后的概率,所以可以一边抽候选,一边检查候选是否属于 top-p 集合。
候选 $j$ 合格的条件是 $\sum_{i:p_i>p_j}p_i<P$,也就是排在它前面的概率还没有达到阈值。若不合格,它以及所有概率更小的 token 都可以排除,再从剩余项中按权重抽样。
Dual Pivot Rejection Sampling 额外维护一个阈值上界。候选不合格时,再测试候选概率与上界之间的中点,收紧下一轮搜索范围。high 是边界搜索的上界,不是抽样集合的上界。
Input: p (probabilities [V]), P, rng
Output: token
low ← 0
high ← Max(p)
loop:
j ← WeightedSample(p[{i : p[i] > low}], rng)
a ← p[j]
if Sum(p[i] for i where p[i] > a) < P:
return j
b ← (a + high) / 2
if Sum(p[i] for i where p[i] > b) < P:
low ← a
high ← b
else:
low ← b
WeightedSample 按给定权重抽样,可以用累计概率和均匀随机数实现。FlashInfer 实现了这个算法。这里的关键在于,候选是按概率随机抽出来的,不是搜索过程任意找到的。算法保证最终返回的 token 服从 top-p 筛选并归一化后的分布,证明放在 Appendix D。
投机采样让较便宜的 draft 提议 token,减少 target 串行生成的次数;但不能直接提交 draft 的结果。Rejection sampling 的作用是利用这些提议,同时保持 target 的输出分布。它也解释了为什么前面的“只要 token”优化不能直接覆盖投机验证。
记 $p$ 为 target policy 处理后的分布,$q$ 为实际生成 draft token 的分布。以三个token A, B, C 为例,可能p = [0.5, 0.4, 0.1], q = [0.8, 0.1, 0.1]。这里在draft分布里,token A被选择的概率是被过分的高估了,因此在verify的时候,虽然A依然是概率最大的,但我们不能直接接受它,因为这样会导致B被选择的概率大幅度降低。这就引入了 rejection sampling,验证候选 $d$ 时,以 $\min(1,p(d)/q(d))$ 的概率接受;拒绝后,按 $\max(p-q,0)$ 的权重抽出 replacement。这上面这个例子里,被拒绝之后应该按 [0, 0.3, 0] 的权重抽样,这里B就一定会被选择。数学证明与原始论文见 Appendix C。
接受判断只需要两个标量 $p(d)$ 和 $q(d)$;补偿抽样则需要所有 token 的 $p(i)$ 和 $q(i)$。这就是最开始是 draft_info 和 target_info 必须保留概率信息的原因。保留 logits 与归一化摘要也能恢复概率,不必物化完整概率数组。
先用 SGLang 的数据流确定需要完成哪些工作,再从这些工作推导一个优化方案:把 sampling 纳入 CUDA Graph,以设备上的参数统一处理 greedy 与 sampled,然后减少 draft 通信与 target 筛选的开销,并保持 draft 分布分片,在各 rank 完成补偿抽样,最后只交换 winner。后面的设计以采样语义不变为前提,可以用于检查一个现有实现还有哪些可优化的地方。
这里参考 SGLang commit 12004043b8:普通非投机采样在 model forward 返回 logits 后执行 sampler,greedy 取 argmax,随机请求则应用采样参数并抽出 token。
下面重点看启用 rejection sampling 的链式投机路径。SGLang 也有 tree target-only 等验证方式,不能把它们与使用真实 draft 分布 $q$ 的链式验证混为一谈。这里省略 logprob、grammar 与其他 logit 调整,按一个请求、$D$ 个 draft token 展示。
Draft:抽 token,并保留验证所需的分布信息
随机 draft 使用温度调整后的完整分布,不执行请求的 top-k/top-p 截断。EAGLE 的 sample_draft_proposal 计算并返回 $q$、$q(d)$ 和 $d$;DSpark 则可以保留实际用于抽样的 logits,在验证前重建 $q$。两者都必须保留足够信息,不能只把抽到的 token 传给 verify。
Input: context, draft_state, T, rng, D
Output: d (draft tokens [D]), q (draft probabilities [D, V])
for j ← 0 to D-1:
z_local, draft_state ← DraftForward(context, d[:j], draft_state)
z ← AllGather(z_local)
q[j] ← Softmax(z / T)
d[j] ← CategoricalSample(q[j], rng[j])
return d, q
这里把词表聚合显式写出来,表示普通 TP 下 sampler 消费完整词表的 logits;实际聚合位于 logits 处理路径,并不是每个 sampler 自己调用。CategoricalSample 表示按给定概率抽样,具体可以使用前面介绍的 Gumbel-max 等价形式。代码见 draft 概率与抽样 和 DSpark draft。
Target:一次 forward 得到各位置分布,再验证整条链
Target 输入 anchor 和 draft token,一次 forward 得到 $D+1$ 行 logits。第 $j$ 行用于判断 $d_j$;最后一行用于全部接受后的 bonus。每一行都应用 target policy,得到真正用于验证的 $p_j$。
Input: context, d (D draft tokens), q, target_policy, rng
Output: accepted_tokens, next_token
z_local ← TargetForward(context, d)
z ← AllGather(z_local)
if target_policy.greedy:
best ← ArgMax(z, axis=vocab)
L ← LeadingTrueCount(d == best[:D])
next_token ← best[L]
else:
p ← Softmax(z / target_policy.T)
if target_policy.top_k_enabled:
p ← TopKRenormalize(p, target_policy.top_k)
if target_policy.top_p < 1:
p ← TopPRenormalize(p, target_policy.top_p)
L ← D
for j ← 0 to D-1:
if Uniform(rng.accept, j) × q[j][d[j]] ≥ p[j][d[j]]:
L ← j
break
weights ← Max(p[L] - q[L], 0) if L < D else p[D]
next_token ← CategoricalSample(Normalize(weights), rng.final)
L, next_token ← BroadcastFromRank0(L, next_token)
return d[:L], next_token
这是源码的逻辑展开,不表示循环里的每一步都是一个独立 kernel。实际 rejection kernel 完成接受判断和最终抽样,并写出 token、接受索引与接受数量;随机验证路径随后广播这些结果,避免各 rank 因浮点计算或抽样差异而提交不同 token。伪代码将广播结果简写为 L 和 next_token。调用见 eagle_utils.py。
这里的 TopPRenormalize 调用 FlashInfer 的 top_p_renorm_probs,本文单独核查的 FlashInfer commit 0caca03ce6 对常见 LLM 词表使用 AIR Top-P,即前面介绍的 radix selection。
上述 FlashInfer 版本并不代表该 SGLang commit 实际安装的依赖版本。
这一流程中,draft 与 target 都处理完整词表分布,verify 还需要保存或重建 draft 概率。下一节先讨论把 sampler 和 acceptance 纳入 CUDA Graph,再讨论减少完整词表通信与中间概率读写;不能只优化最后的 categorical sampling 就覆盖整个开销。
本文引用版本的 EAGLE draft graph 已 capture draft_forward,其中包含 sample_draft_proposal,并为 rejection sampling 准备 greedy/sample variants。进一步的优化是统一设备上的 policy,减少 variants,并把尚在 graph 外的 verify 工作纳入 capture,以减少重复的 host 调度。
下面展示目标组织方式,仍使用第一章的接口:
Input: context, draft_state, draft_policy, target_policy, rng, D
Output: accepted_tokens, next_token
within DraftGraph:
for j ← 0 to D-1:
z_draft[j], draft_state ← DraftForward(context, d[:j], draft_state)
d[j], draft_info[j] ← DraftSample(z_draft[j], draft_policy, rng[j])
within VerifyGraph:
z_target ← TargetForward(context, d)
target_info ← TargetDistribution(z_target, target_policy)
L, next_token ← VerifyAndSample(d, draft_info, target_info, rng)
accepted_tokens ← d[:L]
接下来需要处理 greedy 和 sampled 的差异。Graph 固定了 kernel 及其依赖关系,但请求可能改变 temperature、top-p,甚至从随机采样变为 greedy。我们希望同一组 shape 下复用 graph,因此把 policy 放在地址固定的 GPU buffers 中,每次 replay 前更新其值,由 kernel 内部分支决定执行哪些计算:
Before replay:
policy_buffer ← (greedy, temperature, top_k, top_p)
rng_buffer ← (seed, step)
Inside sampling kernels:
if policy_buffer.greedy:
token ← ArgMax(logits)
else:
distribution_info ← Distribution(logits, policy_buffer)
token ← Sample(distribution_info, rng_buffer)
Inside verification kernels:
if policy_buffer.greedy:
L ← LeadingTrueCount(d == target_argmax[:D])
next_token ← target_argmax[L]
else:
L, next_token ← RejectionSample(d, draft_info, target_info, rng_buffer)
这里的分支表示 kernel 内的设备端判断,不是 replay 时由 Python 重新选择 kernel。Greedy 只执行 argmax 和 token 比较,sampled 才计算概率、筛选和随机抽样。一个请求可能经过多个 kernel;只服务于 sampled 的 kernel 在 greedy 情况下提前退出。Top-p 的 fallback 也应提前 capture,通过设备上的标记决定是否执行其中的工作。
这样,改变采样参数不需要重新 capture,也不需要为 greedy 和 sampled 各维护一套 graph。不过,共用 graph 仍会保留提前退出的 kernel 节点开销;纳入 graph 也不会自动减少词表读写、通信或把多个 kernel 融合。下面继续优化这些实际工作。
4.3 与 4.5 的伪代码展开 draft 和 target 均为随机采样的路径;target greedy 沿用 4.2 的 argmax 验证。
这里要省去每轮 draft 对完整词表 logits 的聚合,改为一次小摘要交换。这个优化成立的前提是 draft 只应用 temperature、不做 top-k/top-p:它不需要全局候选筛选,只需要一个 token 和计算其分布所需的信息。
做法是在同一次局部扫描中计算 Gumbel-max 的 winner 与 online softmax 的 $(m,s)$,一起交换,再 merge 出全局 token 和归一化摘要。保留本地 logits 与摘要,就能在拒绝时恢复其他 token 的 draft 概率。
Input: z_local (draft logits [V/TP]), global_ids, T, rng
Output: token, draft_info
x_local ← z_local / T
key ← x_local + Gumbel(rng, global_ids)
w ← ArgMax(key)
stats_local ← OnlineSoftmaxStats(x_local)
records ← AllGather(key[w], global_ids[w], x_local[w], stats_local)
best ← ArgMax(records.key)
token ← records[best].token_id
M, S ← MergeSoftmaxStats(records.stats)
log_q_token ← (records[best].x - M) - Log(S)
draft_info ← (x_local, M, S, log_q_token)
return token, draft_info
伪代码分别表示 winner 和统计量,实现时可以在同一次扫描中计算。Greedy 只需普通 argmax,不计算归一化摘要。
Target 需要支持完整的请求 policy,因此这里保留 logits AllGather,在每个 rank 上完成 top-k/top-p 筛选。本地 softmax 使用 online 更新不会增加通信;只有改成跨 rank 筛选协议,才需要重新考虑通信次数与延迟。下面显式写出概率数组以说明逻辑,实现可以保留 logits、筛选结果及对应的归一化常数,按需计算最终分布的概率。
我们主要优化的 top-p 筛选:首先根据概率会集中在部分token上的假设来执行CandidateTopP,假设不满足时再执行 radix selection。
Input: z_local (target logits), policy
Output: target_info
z ← AllGather(z_local)
if policy.greedy:
return (greedy=True, argmax=ArgMax(z))
p ← Softmax(z / policy.T)
if policy.top_k_enabled:
p ← TopKRenormalize(p, policy.top_k)
if policy.top_p < 1:
selection ← CandidateTopP(p, policy.top_p)
if not selection.valid:
selection ← RadixSelect(p, policy.top_p)
p ← Normalize(Mask(p, selection))
return p
这里的优化是,既然 draft 已经不再聚合完整分布,verify 也在各 rank 就地计算 residual,最后只交换 winner:
L。各 rank 使用一致的接受概率和随机数,保证得到相同的结果。max(p_target_local − p_draft_local, 0),用 Gumbel-max 选出本地 winner。最后通过一次 AllGather 交换各 rank 的 (score, token_id),再 merge 得到全局 winner,无需聚合完整 draft 分布。全部接受时,同样的方法直接用于 target 的 bonus 分布。这里的一次 AllGather 指最终抽样阶段,不包括前面 target logits 的聚合。
global_ids 是本 rank 持有的全局 token ID;本地 draft 数组按相同顺序存储。接受判断所需的 $q_j(d_j)$ 直接由 4.3 保存的 log_q_token 恢复,$p$ 则是 4.4 得到的 target 分布。
Input: d (draft tokens [D]), draft_info, p, global_ids, rng, tp_group
Output: accepted_tokens, next_token
parallel for each TP rank:
q_token[j] ← Exp(draft_info[j].log_q_token)
accept[j] ← Uniform(rng.accept, j) × q_token[j] < p[j][d[j]]
L ← LeadingTrueCount(accept)
weights_local ← p[L][global_ids]
if L < D:
q_local ← Exp(draft_info[L].x_local - draft_info[L].M) / draft_info[L].S
weights_local ← Max(weights_local - q_local, 0)
scores_local ← Log(weights_local) + Gumbel(rng.final, L, global_ids)
winner_local ← (Max(scores_local), global_ids[ArgMax(scores_local)])
winners ← AllGather(winner_local, tp_group)
next_token ← MergeArgMax(winners).token_id
return d[:L], next_token
要证明的结论是:对有限的 logits $z_i$ 和 $T>0$,给每个 $x_i=z_i/T$ 加独立的标准 Gumbel 噪声后,最大值对应的 token 满足
\[\Pr(X=i)=\frac{e^{x_i}}{\sum_j e^{x_j}}.\]这说明它能替代“计算 softmax,再按概率抽样”这段流程;它本身输出的是 token,不是 softmax 的所有概率。
第一步:把加噪声取最大值改写成取最小值。 取独立的 $U_i\sim\mathrm{Uniform}(0,1)$,令 $E_i=-\log U_i$。对 $t\ge0$,
\[\Pr(E_i>t)=\Pr(U_i<e^{-t})=e^{-t}.\]因此 $E_i$ 服从参数为 1 的指数分布,而 Gumbel 噪声是 $G_i=-\log E_i$。令 $w_i=e^{x_i}>0$,则
\[X=\arg\max_i(x_i-\log E_i) =\arg\min_i\frac{E_i}{w_i}.\]第二步:计算第 $i$ 项成为最小值的概率。记 $Y_i=E_i/w_i$。对 $t\ge0$,
\[\Pr(Y_i>t)=\Pr(E_i>w_it)=e^{-w_it}.\]先求分布函数,也就是“不超过 $t$ 的概率”,再对它求导,就得到概率密度:
\[F_i(t)=\Pr(Y_i\le t)=1-e^{-w_it},\qquad f_i(t)=\frac{dF_i(t)}{dt}=w_i e^{-w_it}.\]密度 $f_i(t)$ 不是“恰好取到 $t$”的概率;连续随机变量取到某一个指定值的概率为零。它描述一个很短的区间中有多少概率:
\[\Pr(t\le Y_i<t+\Delta t) =F_i(t+\Delta t)-F_i(t) \approx f_i(t)\Delta t.\]要让 $Y_i$ 成为最小值,需要其他所有 $Y_j$ 都大于它。若先固定 $Y_i$ 的值为 $t$,由于各项独立,其他项都大于 $t$ 的条件概率是
\[\Pr(Y_j>t\ \text{for all }j\ne i\mid Y_i=t) =\prod_{j\ne i}\Pr(Y_j>t) =\prod_{j\ne i}e^{-w_jt}.\]这里是对给定 $Y_i$ 取值的条件分布进行计算,不是把 $\Pr(Y_i=t)$ 当成非零概率。最后用 $Y_i$ 的密度对所有可能的 $t$ 加权积分:相当于把各个小区间中“$Y_i$ 落在这里且其他项都比它大”的概率相加。由连续形式的全概率公式,
\[\begin{aligned} \Pr(X=i) &=\int_0^\infty w_i e^{-w_it}\prod_{j\ne i}e^{-w_jt}\,dt\\ &=\int_0^\infty w_i e^{-t\sum_jw_j}\,dt\\ &=\frac{w_i}{\sum_jw_j} =\frac{e^{x_i}}{\sum_je^{x_j}}. \end{aligned}\]连续随机变量出现并列最小值的概率为零,因此不影响上述结论。证明按精确实数运算成立;实际实现还需处理有限精度、随机数端点与并列值。
已有概率时为什么能用 argmax(probs / E)? 令 $p_i=w_i/Z$、$Z=\sum_jw_j$,则
公共分母 $Z$ 不改变最大值的位置。这也说明只要权重非负、总和大于零,就不必先把它们归一化;零权重的 token 不参与竞争。
记 $x_i=z_i/T$。Stable softmax 减去整行最大值 $m$,避免指数溢出:
\[p_i=\frac{e^{x_i-m}}{\sum_j e^{x_j-m}},\qquad m=\max_j x_j.\]问题是扫描到一半时,还不知道最终的 $m$。参考 Zihao Ye 的 From Online Softmax to FlashAttention,我们改为维护当前前缀的最大值与指数和:
\[m_n=\max_{i\le n}x_i,\qquad s_n=\sum_{i\le n}e^{x_i-m_n}.\]新值 $x$ 到来后,令 $m’=\max(m_n,x)$。旧和换到新基准,再加上新值:
\[\boxed{s'=s_n e^{m_n-m'}+e^{x-m'}}.\]这是因为 $e^{x_i-m’}=e^{x_i-m_n}e^{m_n-m’}$。扫描结束时,running max 就是全局最大值,$s$ 也恰好成为最终分母。比如 [2,1,3]:先得到 $(2,1+e^{-1})$,读到 3 后变为 $(3,(1+e^{-1})e^{-1}+1)$。
同样的规则可以合并两个 tile,也可以合并两个 GPU 上的分片:
\[\boxed{\begin{aligned} m&=\max(m_A,m_B),\\ s&=s_Ae^{m_A-m}+s_Be^{m_B-m}. \end{aligned}}\]因此,rank $t$ 只需计算局部 $(m_t,s_t)$,再交换、合并这些统计量:
\[m=\max_t m_t,\qquad s=\sum_t s_t e^{m_t-m},\qquad \mathrm{LSE}=m+\log s,\qquad p_i=e^{x_i-\mathrm{LSE}}.\]LSE 在数学上给出全局归一化常数,不要求 logits 先聚合到同一张卡。工程上建议保留 $(m,s)$,按 $p_i=e^{x_i-m}/s$、$\log p_i=(x_i-m)-\log s$ 计算:例如 FP32 的 $x=(10^8,10^8)$,单值 $m+\log 2$ 可能舍入回 $m$,再相减会错误地得到概率 1,而不是 $1/2$。 不能直接相加各 rank 的 $s_t$,必须先用 $e^{m_t-m}$ 统一基准。空或全被 mask 的分片贡献零指数和;整行无合法 token 则需显式处理。
Online softmax 将最大值与分母的计算合成一次扫描。若还要输出所有概率,通常仍需再读 logits;若只要少量候选的概率,就只需保留候选 logits。正文的候选聚合方案利用的就是这一性质。
合并公式的证明。 对任意非空分片 $A$,定义 $m_A=\max_{i\in A}x_i$、$s_A=\sum_{i\in A}e^{x_i-m_A}$。合并不相交的分片 $A,B$,令 $m=\max(m_A,m_B)$,则
\[\begin{aligned} \sum_{i\in A\cup B}e^{x_i-m} &=\sum_{i\in A}e^{x_i-m_A}e^{m_A-m} +\sum_{i\in B}e^{x_i-m_B}e^{m_B-m}\\ &=s_Ae^{m_A-m}+s_Be^{m_B-m}. \end{aligned}\]合并后的 $(m,s)$ 与直接扫描并集得到的定义完全相同。因此在精确运算下,可以逐元素、逐 tile 或逐 rank 合并;浮点运算中不同合并顺序可能有舍入差异。取 $B$ 为单个新元素,就得到上面的 online 更新式。最终 $\mathrm{LSE}=m+\log s=\log\sum_i e^{x_i}$,所以 $p_i=e^{x_i-\mathrm{LSE}}$。
这里证明的是投机采样中的“接受提议,否则从补偿分布抽样”规则。参考 Leviathan、Kalman 和 Matias 的 Fast Inference from Transformers via Speculative Decoding,第 2.3 节与 Appendix A.1。它与拒绝后不断重新提议的经典 rejection sampling 有所区别,原论文 Appendix A.2 专门讨论了这一点。
固定一个生成前缀,令 $p_i$ 为应用 temperature、top-k、top-p 等规则后的 target 概率,$q_i$ 为 draft 实际使用的提议概率,满足 $\sum_i p_i=\sum_i q_i=1$。以下使用精确实数运算,并假设接受判断和补偿抽样使用独立的随机数。
接受分支。 先抽 $d\sim q$,再以 $a(d)=\min(1,p_d/q_d)$ 的概率接受。记 $A$ 为接受事件,则通过这条分支输出 token $i$ 的概率为
\[\Pr(d=i,A)=q_i a(i)=\min(p_i,q_i).\]当 $q_i=0$ 时,该 token 不会被提议,这一项为零,不需要计算 $p_i/q_i$。因此总接受概率和总拒绝概率分别是
\[\alpha=\sum_i\min(p_i,q_i)=1-\frac12\sum_i\lvert p_i-q_i\rvert,\qquad R=1-\alpha.\]这里使用 $\min(p_i,q_i)=(p_i+q_i-\lvert p_i-q_i\rvert)/2$ 并对词表求和。忽略 EOS 等提前截断时,一轮输出 $L+1$ 个 token,因此性能应比较平均每轮延迟除以 $\mathbb{E}[L]+1$,不能只比较 sampling kernel 的耗时。
拒绝分支。 接受分支已经为 token $i$ 提供了 $\min(p_i,q_i)$ 的输出概率。要达到 $p_i$,还差
\[w_i=p_i-\min(p_i,q_i)=\max(p_i-q_i,0).\]这些缺少的概率之和恰好等于拒绝概率:
\[\sum_i w_i=\sum_i p_i-\sum_i\min(p_i,q_i)=1-\alpha=R.\]当 $R>0$ 时,拒绝后的条件抽样分布应为 $r_i=w_i/R$。注意 $r_i$ 是“已经拒绝”的条件下输出 $i$ 的概率,所以它对最终输出的贡献还要乘以 $R$。
合并两条分支。 记最终输出为 $X$,由全概率公式,
\[\begin{aligned} \Pr(X=i) &=\Pr(d=i,A)+\Pr(A^c)\Pr(X=i\mid A^c)\\ &=\min(p_i,q_i)+R\frac{\max(p_i-q_i,0)}{R}\\ &=p_i. \end{aligned}\]当 $R=0$ 时,$p=q$,所有提议都被接受,不执行补偿抽样。因此两种情况都保持 target 分布。即使某个 token 的 $q_i=0<p_i$,它也可以通过补偿分支输出。
从单个 token 到整条序列。 在每个相同的已生成前缀下重复上述规则,下一 token 都服从对应的 target 条件分布。第一次拒绝后,后续 draft 候选必须丢弃,因为它们依赖的是被拒绝的前缀。全部接受时,直接从最终前缀对应的 target 分布抽 bonus。由条件概率的链式法则,整条输出序列的分布与 target 自回归采样一致。
这个证明要求 $q$ 与实际提议过程一致,保证的是分布一致,不是相同 seed 下 token 序列相同;浮点舍入和有限精度实现仍需单独检查。
设 top-p 的保留集合为 $S$,概率之和为 $Z=\sum_{i\in S}p_i$。假设 $0<P<1$,使用精确运算,并按正文规则保留 cutoff ties。令 $H(a)=\sum_{i:p_i>a}p_i$,则 $S={j:H(p_j)<P}$;同概率的 token 要么全部属于 $S$,要么全部不属于。每一轮的抽样集合 $C$ 都包含 $S$:被拒绝候选及更低概率的项都在 $S$ 外,第二个 pivot 也只有在其上方的概率之和仍达到 $P$ 时才提高排除阈值。
固定一轮之前的历史,令 $W=\sum_{i\in C}p_i$。这一轮抽中 $i\in S$ 的概率为 $p_i/W$,成功返回的概率为 $Z/W$,所以
\[\Pr(X=i\mid\text{这一轮成功,历史}) =\frac{p_i/W}{Z/W}=\frac{p_i}{Z}.\]不同历史、不同成功轮次下都是同一分布,混合后仍为 $p_i/Z$。每次失败至少排除一个集合外概率值,有限词表下最终会成功。参考 FlashInfer 的算法与正确性讨论。浮点实现的停止条件需另外处理。