01 · Attention算完，还没有选出下一个token
模型输出词表logits后，生成引擎仍要按约定处理分数、应用限制、选择token、更新请求状态，再准备下一轮。词表很大时，排序、临时概率表和小kernel启动可能明显；若把整行logits拷给CPU再选，传输与同步也可能成为生成间隔的一部分。
这篇优化的是选token的实现。降低temperature、缩小top-k或把随机采样改成贪心，会改变生成策略，不能算保持同一分布的执行提速。
02 · top-k和top-p究竟保留哪些候选
自设四个token A/B/C/D，原概率为[0.4,0.3,0.2,0.1]。top-k=2保留A/B，再归一化得到[4/7,3/7]。top-p=0.8按概率从大到小，取累计质量达到阈值的最短前缀，本例保留A/B/C，归一化为[4/9,3/9,2/9]。
参考约定：
先处理temperature与业务分数规则
再应用合法token mask
按top-k限制候选并归一化
再按top-p选择累计概率最短前缀
对剩余候选重新归一化并采样
# 这是本篇演示的顺序；实际引擎需明确自己的合同。temperature τ>0时可以用logits/τ再Softmax。贪心通常是单独的argmax路径，不能直接除以0。惩罚、mask和过滤的顺序、阈值边界与并列分数规则也会影响结果。
四个候选，过滤后按什么概率抽？
本例先合法性mask，再top-k并归一化，再top-p，最后按token编号的CDF抽样；u不是改成贪心。原概率固定，temperature=1；不模拟GPU无排序算法。03 · 为什么顺序属于正确性，而不是小细节
仍用原概率，top-k=2且top-p=0.5：先top-k后，A概率4/7超过0.5，只保留A。若先在完整分布做top-p，则A的0.4不够，还需B；与top-k取交集后仍有A/B。两种规则都可定义，但不是相同采样分布。
如果约束只允许C/D，先mask再归一化得到[2/3,1/3]；若先top-k=2选A/B，再与约束相交，候选变空。不能把空候选偷偷改成一个语法不允许的token。应按明确合同报错、结束或采取允许的回退策略。
不同并列处理规则也可能留下不同候选数量。验收时需要比较概率、候选集合和边界，不只是检查生成文字“看起来正常”。
04 · 少排序与融合：省的是执行组织
| 基线开销 | 优化方向 | 不能省掉的条件 |
|---|---|---|
| 完整词表排序 | top-k用选择/阈值，采样可使用适配的无完整排序算法 | 仍需符合原top-k/top-p定义和并列处理。 |
| 多个概率/过滤临时表 | 融合Softmax、过滤与采样，减少物化和启动 | 数值稳定、分布与随机状态正确。 |
| 整行logits回CPU | 设备侧选token，仅在必要时返回小结果 | 约束状态和后续任务依赖仍要满足。 |
| 逐请求小操作 | 按兼容请求批量处理，可支持每请求参数 | batch重排后参数和随机流不能错配。 |
FlashInfer提供不显式完整排序的GPU采样实现，是阅读算法与内核融合的入口。它仍需扫描或归约候选并可能进行多轮拒绝采样；没有排序不等于无需读取词表，也不能用O(V)标签直接预测某负载更快。
同一分布不保证同seed得到逐token相同结果：不同内核的随机数消耗和浮点归约顺序可能不同。验证可分为分布一致、统计误差和特定实现的可复现性。
依据：FlashInfer · 无完整排序采样作者讲解 ↗ · FlashInfer 0.7.1 · top-k/top-p顺序与随机状态 ↗
05 · 约束解码：约束的是token拼接后的字符串
语法约束通常维护当前已生成前缀的解析状态。合法token是追加其解码片段后，仍有机会完成合法输出的候选；不要求每个token本身是一段完整JSON或单字符。一个token可能跨过多个符号，检查不能只看首字符。
自设只允许完整输出yes或no。起始可接受片段y、ye、yes、n、no；片段yes!不合法。已得到y时，下步e或es可延续；得到yes后，按本例规则只允许EOS结束。这个有限字符串例子帮助理解状态，不能当通用JSON解析器。
初始化当前请求的语法状态
由状态生成合法token bitmask
按约定将不合法logit设为-inf
采样合法token
把实际token的完整解码片段提交给状态机
下一步使用新状态；EOS仅在允许结束时接受语法/schema和tokenizer相关的编译结果可以复用；每个请求的运行中状态仍独立。XGrammar原作者实现提供预处理与缓存等入口，支持范围和接入接口要按版本确认。语法成立不保证答案内容真实或符合业务含义。
06 · 把CPU解析和设备计算组织起来
在依赖允许时，CPU可准备其他请求的mask，设备同时计算已就绪任务；固定模式或兼容状态的mask可缓存。bitmask减少传输字节，但实际展开、读取和更新也有成本。只缓存schema编译结果，不能代替当前前缀的合法性检查。
同一请求的状态更新依赖实际采样token，不能在未知结果时直接提交下一状态。投机解码回滚时，语法状态和随机状态也要按合同处理；batch槽位复用时需保留请求身份，避免旧异步mask写进新请求。
图重放若始终使用相同seed和offset内容，可能重复同一随机样本。FlashInfer接口支持显式随机状态参数，调用方应按实际消耗推进；不能只因为图已捕获，就把随机状态冻结。
依据：XGrammar · 原作者结构化生成实现 ↗ · FlashInfer 0.7.1 · top-k/top-p顺序与随机状态 ↗
07 · 小脚本先检查概率和约束
下载脚本比较排序参考与top-k局部选择路径，核对过滤顺序、稳定Softmax、mask空集和并列规则；用CDF区间检查采样概率，另运行yes/no有限语言状态机及回滚。它没有实现GPU多轮拒绝采样，不报告硬件加速比。
记录采样合同：temperature、过滤顺序、并列与EOS
用小词表列出每个候选的预期概率
比较候选内核的分布与极端输入
核对请求/参数/随机流映射与语法状态
测LM head→mask→采样→下一步输入的完整间隔
# 分布相同与同seed逐次相同是两项不同检查。实际还要覆盖NaN、全−∞、极端logits和停词。不同后端对异常输入的返回约定不同，应显式处理，不用一个默认token掩盖异常。
08 · 如何定位采样链路收益
- 语义：每请求参数、mask、过滤顺序、EOS/停止规则，完整候选分布。
- 内核：排序/选择、Softmax、过滤、采样总耗时及临时表。
- 系统：CPU状态更新时间、bitmask传输、同步等待和batch排队。
- 服务：生成间隔、尾延迟及吞吐；约束输出有效率单独统计。
FlashInfer的CUDA采样入口不是所有GPU/NPU通用开关。平台对照应比较同一采样合同的完整路径，确认设备侧算子和CPU语法运行时如何衔接。
依据：vLLM Ascend · 支持功能矩阵（main） ↗
- top-k=2、top-p=0.5，为什么不同顺序会留下不同集合？
- 把logits留在设备上，是否意味着同请求下一步可以不等采样结果？
- 重复使用schema编译缓存与复用请求解析状态有什么区别？
流程位置与关联方法
这个方法可能出现在多个位置；计算线包含模型计算与算子实现，执行线包含运行时、内存和通信。
资料与核查范围
原理依据以原始论文和官方文档为主；算例与时间线是教学推导。文档核查日期：2026-10-10。引用 main / latest 文档时，实际接口以安装版本为准。
- FlashInfer 0.7.1 · 设备采样算子 ↗
- FlashInfer · 无完整排序采样作者讲解 ↗
- FlashInfer 0.7.1 · top-k/top-p顺序与随机状态 ↗
- XGrammar · 原作者结构化生成实现 ↗
- vLLM Ascend · 支持功能矩阵（main） ↗
代码为接入片段或教学伪代码；本页没有声称完成 NVIDIA / 昇腾硬件实测。