文档教程人工智能大模型RLHF【免费下载链接】Awesome-ML-SYS-TutorialMy learning notes for ML SYS.项目地址https://gitcode.com/gh_mirrors/aw/Awesome-ML-SYS-Tutorial点击查看免费下载本文是 Awesome-ML-SYS-Tutorial 仓库中 constraint-decoding 学习笔记的扩展成文版围绕 SGLang 的结构化输出structured output能力系统梳理 constraint decoding 的概念、朴素实现流程及其面临的大词表性能瓶颈并以 SGLang 最新的 grammar backend X-Grammar 为线索逐项拆解其在表达力、算法与系统三个层面的优化手段。读完本文你将理解约束解码为什么是JSON decoding的超集、CFG 与 PDA 如何参与语法约束并能结合仓库中的调度器源码看清update_regex_vocab_mask等关键函数在真实推理流水线中的位置。概念constraint decoding 与 structured output 是一体两面在 LLM 推理服务中让模型输出符合特定结构的需求几乎无处不在调用 API 后需要按 schema 解析结果、让模型写 SQL 或 Cypher 查询、要求输出严格合法的 JSON 供下游程序消费。围绕这一需求业界先后出现过几种说法JSON decoding早期说法只聚焦于让输出符合 JSON 结构视野较窄structured output效果视角描述的是结果——模型输出符合特定格式constraint decoding方法视角描述的是手段——在模型的 decoding 阶段施加约束限制候选 token 空间。这两个词是同一枚硬币的两面结构化输出表达的是目标约束解码表达的是实现手段。而理论上任何CFGContext-Free Grammar上下文无关文法都可以被 constraint decoding 表达CFG 的表达能力远超 JSON——因此JSON decoding这个旧说法显得非常狭隘。在大量真实场景中我们希望模型输出特定结构以便后续 parsing实现这一目标的方法就是 constraint decoding。基本原理按语法规则掩码 Token 概率的六步流程最直观的实现方式是在 decoding 阶段直接约束 token 概率根据语法规则把不符合规则的 token 概率置零或接近 0再在过滤后的分布上采样。一个经典的流程如下定义约束规则这些规则可以是各类 CFG也可以是一些自定义的逻辑规则生成候选 tokenDecodingLLM 进行一轮 decoding得到候选 token 列表约束检查Mask Gen根据预定义的约束规则对候选 token 列表中的每个 token 进行检查判断其是否符合规则过滤Apply Mask将不符合规则的 token 的概率设置为 0或一个极小的值从而将它们从候选 token 列表中排除采样根据过滤后的概率分布从剩余的候选 token 中采样出一个 token作为生成的 token重复步骤 2-5直到生成完整的文本序列。这种 naive 实现的问题相当明显对于像 Llama-3 这样拥有 128,000 个 token 的大型词表如果每个生成步骤都对整个词表做完整的语法规则验证计算开销会非常大。一个直接的优化是按采样概率从高到低检测 token 是否符合规则命中即停止不必遍历完整个词表——但从期望复杂度来看代价依然很高。仓库佐证SGLang 中约束解码的真实调用链上述概率掩码的思想在 SGLang 中对应着一组真实的实现函数仓库中的 零开销批量调度器笔记 对此有详细描述SGLang 的约束解码保证模型输出一定符合给定的 grammar 格式在生成下一个 token 时模型的 logits未归一化的概率会与vocab_mask结合把无效 token 的 logits 设置为一个极小的值如-inf从而在采样阶段被排除。以grammarjson为例输出的 JSON 第一个 token 一定是{因此采样前需要调用apply_vocab_mask函数把其他 token 位置的 softmax 概率压低保证模型采样出的第一个 token 一定是{。mask 的更新逻辑集中在update_regex_vocab_mask函数中——因为它涉及语法解析逻辑是一个CPU 密集型操作而将 mask 应用到 logit 则只需在forward_batch_generation()的 sample 之前处理完即可。加上约束解码之后推理流程变成... - forward - constrained decoding(update_regex_vocab_mask) - sample - ...如果不对update_regex_vocab_mask做 overlap解码就会被这个 CPU 操作阻塞导致 GPU 卡在 sample 之前详见下文与 GPU 计算的流水线重叠。此外调度器中存在一个 ForwardMode 为DUMMY_FIRST的空 batch其作用是在真正第一个 batch 运行之前触发update_regex_vocab_mask的调用链路提前把 mask 算好。X-GrammarSGLang 结构化输出的新一代 grammar backend面对朴素实现的性能瓶颈SGLang 引入了最新的 grammar backendX-Grammar。它在规则表达和系统两个维度上进行了优化表达能力更强利用 CFG 更好地表达嵌套结构这是 JSON 很难做到的算法和系统优化通过并行和 overlap 策略降低约束解码带来的 overhead。先谈表达能力。CFG 是 JSON 的超集可以用 CFG 表达更复杂的结构例如 SQL 和 Cypher 这类具有嵌套、递归语法的查询语言。X-Grammar 主要通过EBNFExtended Backus–Naur Form来表达 CFG再通过PDAPushdown Automaton下推自动机在数据结构层面实现 CFG 的识别与约束。EBNF 提供了直观、可读的文法书写方式而 PDA 天然带有一个栈恰好能够承载 CFG 的嵌套与递归语义。算法优化一分离上下文无关的 token理解这一优化的关键是区分两类 token上下文无关 token其合法性只依赖当前 Grammar 节点的状态不依赖更深的栈状态或别的规则。例如 JSON 中布尔值只能是true或false若文法中有如下规则bool_value - true | false判断true/false是否合法只看当前是否位于bool_value节点即可与栈深无关。这类 token 可以在编译期就把该节点能接受的所有 tokentrue、false全部列举并缓存推理时直接取用免去运行时遍历。上下文相关 token其合法性依赖 PDA 栈的当前状态。考虑文法S - ( S ) S S - ε如果下一个 token 是)它是否合法取决于前文是否匹配过对应的(即需要检查 PDA 栈里是否有(可供匹配。若栈里没有更准确地说前序所有(都已匹配完则此时)不合法。因此对于)这个 token必须根据栈状态才能判定是否接受。所幸大部分 token 都是上下文无关的。基于此X-Grammar 在预处理阶段对语法规则进行编译给每个节点或状态缓存其特定的上下文无关 token这些提前编译好的内容称为Adaptive Token Mask Cache。推理时对于大部分上下文无关的 token可以直接从缓存取出掩码避免逐 token 遍历验证的开销。算法优化二持久化执行栈Persistent Execution Stack在语义分析树上进行回溯或分支时传统做法需要复制多份栈拷贝开销较大。X-Grammar 改用树形结构来管理栈的快照通过复用已有节点、在树的分支上增量扩展减少对栈的重复拷贝从而节省内存与计算开销。这一设计对 speculative decoding 这类需要频繁回滚rollback的场景尤其关键——回滚时只需在栈树上退回到对应节点而不是恢复一整份拷贝。算法优化三PDA 结构内联并扩展上下文X-Grammar 通过编译期的两类手段简化 PDA 内部状态数减少执行时的遍历次数内联inlining把一些只做一次简单跳转的非终结符内联到上层规则里减少不必要的调用层级。例如规则A - B; B - token可内联为A - token等价状态合并将 PDA 中行为等价的状态合并缩减状态空间上下文推断context inference与内联类似在编译时尽可能推断更多上下文信息将更多 token 从看似依赖栈状态转化为上下文无关。有些 token 看似依赖栈但通过上下文前向/后向分析可能在编译期就能判定其合法性——例如规则S - ( S ) S | ε中一个没有前置未匹配(的)在编译期即可被判定为不合法无需运行时查栈。系统优化一并行编译Parallel Grammar CompilationGrammar 编译包括构造 PDA 和缓存上下文无关 token发生在预处理阶段传统实现是单线程串行。X-Grammar 把编译过程拆分给多核 CPU 并行运行显著缩短编译时间。对于大型 Grammar——如完整 JSON Grammar、SQL、JSON Schema 扩展等——在多核 CPU 上并行编译可明显加速预处理让上线前的一次性编译成本尽量不再成为瓶颈。系统优化二与 GPU 计算的流水线重叠Overlapping with GPU Computation约束解码的语法解析是 CPU 密集操作如果串行执行CPU 算 mask 时 GPU 只能空闲等待。X-Grammar 通过对接推理 runtime把 CPU 侧的 grammar 处理与 GPU 后续的运算重叠起来降低 overhead。仓库中 零开销批量调度器 给出了 SGLang 对这一思想的工程实现假设有 batch1 和 batch2可以在 batch2 sample 之前、batch1 的process_batch_result中提前把 batch2 的regex_vocab_mask更新出来从而把 CPU 密集操作 overlap 在 GPU 计算之后。关键代码如下# in process_batch_result_prefill and process_batch_result_decode if batch.next_batch_sampling_info: # 注意这里是 next_batch batch.next_batch_sampling_info.update_regex_vocab_mask() self.current_stream.synchronize() batch.next_batch_sampling_info.sampling_info_done.set()而对于第一个 batch需要在它运行之前就把regex_vocab_mask计算好所以调度器会先构造一个dummy_batch来触发update_regex_vocab_mask的调用链路——这个 dummy batch 并不真正在 GPU 上跑只是用于提前预热 mask 更新流程。模型采样前通过等待sampling_info_done这个 event保证 mask 一定已经更新完毕。这一前一个 batch 的后处理阶段顺带算好下一个 batch 的约束掩码的流水线设计正是 X-Grammar 所倡导的 CPU/GPU 重叠思想在真实推理引擎中的落地。系统优化三支持 Speculative Decoding 场景推理引擎常常采用 speculative decoding 或 jumpahead decoding 等手段加速推理。以仓库中 speculative-decoding 笔记为例draft model 一次性预测多个 tokentarget model 再逐一验证存在全部接受 / 部分接受 / 全部拒绝三种情况其中部分接受时被拒绝 token 的 KV cache 需要驱逐——这天然要求解码状态具备可回滚能力。X-Grammar 为此提供了相应 API当预测分支被判定不合法时能迅速回溯rollback到上一个合法状态在 jumpahead 场景下也能直接步进jump-forward。配合持久化执行栈的树形快照设计回滚与跳跃的开销被进一步降低使约束解码在加速解码场景下不至于成为瓶颈。小结与延伸阅读回顾全文constraint decoding 的演进路径清晰可循从JSON decoding的窄口径到以 CFG 为理论边界的结构化输出从每个 step 全词表遍历验证的朴素掩码到 X-Grammar 通过 Adaptive Token Mask Cache、持久化执行栈、PDA 内联与上下文扩展、并行编译、CPU/GPU 流水线重叠以及 speculative 场景回滚/步进 API 的一整套优化体系。理解这条脉络既能帮助你在使用 SGLang 结构化输出时做出正确的配置决策也能为阅读推理引擎源码提供切入点——例如顺着 zero-overhead-batch-scheduler 中的update_regex_vocab_mask、apply_vocab_mask与dummy_batch一路追踪即可看到约束解码在真实调度流水线中的完整生命周期。本文英文版Constraint Decoding: Concepts, Methods, and Optimization约束解码 CPU/GPU 重叠的工程细节Zero-Overhead Batch Scheduler加速解码相关背景Speculative DecodingSGLang 整体推理流水线SGLang Code Walk Through赞分享文档教程人工智能大模型RLHF【免费下载链接】Awesome-ML-SYS-TutorialMy learning notes for ML SYS.项目地址https://gitcode.com/gh_mirrors/aw/Awesome-ML-SYS-Tutorial点击查看免费下载相关推荐Awesome-ML-SYS-Tutorial深入解析Constraint Decoding技术原理与优化Awesome ML SYS Tutorial深入解析Constraint Decoding技术原理与优化 引言 在现代大型语言模型应用中结构化输出生成是一文档教程人工智能大模型RLHFLeetCode 139 Word Break 深度剖析从朴素递归到 Trie 动态规划的六种解法LeetCode 139 Word Break 深度剖析从朴素递归到 Trie 动态规划的六种解法 本篇文章以 LeetCode 139「单词拆分」Word示例工程教程swift-algorithm-club 洗牌算法详解从朴素实现到 Fisher-Yates / Knuth Shuffleswift algorithm club 洗牌算法详解从朴素实现到 Fisher Yates / Knuth Shuffle 洗牌Shuffle是把数组元示例工程教程上一篇KOReader OTA 更新指南从版本匹配到升级回滚下一篇英雄联盟智能工具革命用数据驱动你的游戏体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考