LLM DiveDeep(1): Sampling

理解采样背后的优化逻辑

Introduction

在 Artificial Analysis 的 Kimi 服务商对比中,各家 inference 团队都在竞争更高的 tokens per second(TPS)。一个自然的问题是:同一个模型,如果大家使用相同型号的 GPU,并发都是 1,测试的 prompt 也相同,速度差距还会来自哪里?这篇文章会先从Sampler讲起,然后衍生到一个针对开源 sglang 的 decode 性能优化。本系列后续文章也会沿用 SGLang 作为代码参考。

1. Problem Statement

投机采样先由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策略,主要包括:

另外,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 筛选。

2. Sampling Algo

这一章分场景讨论能省掉哪些工作:只要 token 时,尝试省去 softmax;需要概率时,减少归一化的扫描与通信;需要 top-p 时,减少确定保留集合的工作。后文重点讨论 top-p,top-k 只在需要说明组合顺序时涉及。2.1 和 2.2 都假设只应用 temperature;启用 top-k 时,必须先完成全局选择并 mask,归一化摘要不能替代这一步。

2.1 no prob, no top-p:Gumbel-max

这里的优化是用 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。

2.2 need prob, no top-p: online softmax

这里的优化是用一次小摘要交换替代完整 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)。

2.3 need prob, with top-p

这里要减少确定 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 语义。

  1. Sort + PrefixSum + LowerBound

    • 将概率从大到小排序,计算前缀和,再用二分搜索找到第一个累计值不小于 $P$ 的位置,取该位置的概率为 cutoff,保留所有不小于 cutoff 的项。这就是完整排序方案。经典leetcode题,可以算coding面试题的那种。
    • 后文用 SortTopP(p, P) 表示它。LowerBound 是“找第一个不小于目标的位置”;GPU 也可以并行比较后取最小索引,不必逐步二分。
  2. Candidate Selection

    • 优化目标是只排序少量候选,而不是整个词表。这里的Assumption是大部分请求的概率集中在少量 token 上。
    • 具体实现如下:设置一个较小的 buffer,扫描并记录所有 $p_i \ge \tau$ 的 token。若 Buffer 没有溢出,而且 buffer 里token的概率之和大于等于 $P$,就只需在这些候选中用原分布的概率做 SortTopP。后文统一称为 CandidateTopP;如果条件不满足,Fallback到其他实现。
    • 例如容量为 64、$\tau=0.001$。只出现 20 个候选且总概率为 0.97 时,可以在这 20 个候选中找到 top_p=0.95 的边界;若buffer里token的总概率只有 0.80,则不够,fallback。
  3. 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 来返回结果。

2.4 top-p token only:Dual Pivot Rejection Sampling

这里的优化是直接抽出符合 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。

3. Rejection sampling

投机采样让较便宜的 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 与归一化摘要也能恢复概率,不必物化完整概率数组。

4. SGLang Optimization

先用 SGLang 的数据流确定需要完成哪些工作,再从这些工作推导一个优化方案:把 sampling 纳入 CUDA Graph,以设备上的参数统一处理 greedy 与 sampled,然后减少 draft 通信与 target 筛选的开销,并保持 draft 分布分片,在各 rank 完成补偿抽样,最后只交换 winner。后面的设计以采样语义不变为前提,可以用于检查一个现有实现还有哪些可优化的地方。

4.1 baseline implementation

这里参考 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 就覆盖整个开销。

4.2 sampling within CUDA Graph

本文引用版本的 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 DraftSample:use online softmax

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,不计算归一化摘要。

4.4 TargetDistribution: Optimize top-p selection

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

4.5 VerifyAndSample

这里的优化是,既然 draft 已经不再聚合完整分布,verify 也在各 rank 就地计算 residual,最后只交换 winner:

这里的一次 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

Appendix

A. Gumbel-Max

要证明的结论是:对有限的 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$,则

\[\arg\max_i\frac{p_i}{E_i} =\arg\max_i\frac{w_i}{ZE_i} =\arg\max_i\frac{w_i}{E_i}.\]

公共分母 $Z$ 不改变最大值的位置。这也说明只要权重非负、总和大于零,就不必先把它们归一化;零权重的 token 不参与竞争。

B. Online Softmax

记 $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}}$。

C. Rejection sampling

这里证明的是投机采样中的“接受提议,否则从补偿分布抽样”规则。参考 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 序列相同;浮点舍入和有限精度实现仍需单独检查。

D. Dual Pivot Rejection Sampling

设 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 的算法与正确性讨论。浮点实现的停止条件需另外处理。

参考资料