生成一段 JSON 时，模型其实有 95% 的时间都在做“确定的重复”：{、"、字段名、:、}。真正需要模型“想”的，可能只有每个字段的值。那能不能告诉解码器：这些位置不用采样，直接填？如果再把“猜下一步”交给一个更快的草稿模型，生成会不会快好几倍？

本文是围绕这个问题的技术分享，面向已经接触过 LLM 推理、想理解约束解码来龙去脉的读者。主线是：约束解码解决什么问题 → 方法如何一步步演进 → 关键证据支持哪些结论 → 实践中的经验与边界。

核心猜想：约束解码里大量内容是确定性重复（固定字段、括号、键名），能否把“确定的部分直接跳过采样、交给更快的前向”做成加速？这条主线贯穿全文，也是约束解码与投机解码（speculative decoding）能走到一起的原因。

问题与背景

约束解码要解决的核心问题：输出必须满足结构约束（正则、JSON Schema、CFG），且正确性要有保证，而不是“运气好碰对格式”。

约束解码与普通解码的差别在于，每一步都要回答“哪些 token 合法”。这个查询与 mask 本身有成本，于是出现两条演进方向：

  1. 约束怎么表达：从“必须包含指定词”（集合级约束），到“必须匹配某种语法”（FSM 可判定的约束）。
  2. 约束怎么不花钱：从逐 token 串行查表，到预计算、跳确定部分、与 GPU 前向重叠、最后与投机解码并行验证。

下文按“问题 → 方法 → 证据”展开，论文链接直接列在对应方法处。

一、早期约束解码：约束做进搜索过程

约束解码最早解决的问题是“输出必须包含某些指定内容”——不是格式合法，而是句子里必须出现某个词或短语。早期方法把约束做进 beam search 的搜索过程。

Grid Beam Search（Hokamp & Liu, ACL 2017）

方法

  • 约束定义为“输出必须包含一组指定的短语/词”。
  • 模型在 beam 上扩展时，额外维护一个“已覆盖约束”的状态，beam 排序优先覆盖更多约束的候选。
  • 约束是集合级的“必须包含”，不要求前缀匹配，可以出现在输出任意位置。

判断：这一代方法把约束做进搜索，正确，但只覆盖“必须包含词”这一种约束，且 beam 扩展成本随约束数量上升。它的意义是确立了“约束进解码过程”的范式，而不是进训练或后处理。

Outlines（Willard & Louf, 2023）

方法

  • 把正则、JSON Schema、CFG 编译成有限状态机（FSM），在词表上建立索引（vocabulary index）。
  • 每步只从“合法 token”集合里采样：给定当前 FSM 状态，查询词表索引得到该状态下所有合法 token，其余 token 的 logits 全部 mask 掉，从源头上保证输出满足结构。
  • 模型无关（model-agnostic），不改变模型参数。

实现细节（vLLM 的思路）

  • FSM 的每个状态预先知道“哪些 token 合法”，查询一次词表索引即可得到合法 token 集合，不需要每步扫描整个词表。
  • 每步只做“按状态查表 → 采样合法 token”两步，模型本身不需要改动，也不感知约束。

证据与判断：Outlines 成为社区主流 guided generation 实现（vLLM、SGLang 等均内置），原因是它把“约束”从搜索变成了可编译的 FSM，通用且几乎不增加生成开销。它留下的代价是逐 token 查询合法集——这个开销在后来与投机解码结合时成为核心问题。

Grammar-Constrained Decoding（Geng et al., EMNLP 2023）

方法

  • 提出 GCD 作为通用结构化 NLP 框架：把结构化任务（信息抽取、实体消歧、成分分析等）统一表达为“带语法的生成”。
  • 核心概念是 input-dependent grammar（输入依赖语法）。“随输入变化”要拆成两层看：
    • 固定的一层：语法骨架（模板）。输出结构对所有输入相同。以 cIE（封闭信息抽取）为例，输出是三元组序列，骨架固定为 List -> Triple | Triple List、Triple -> (Subject, Relation, Object)。这一层不随输入变。
    • 输入相关的一层：终结符集合。骨架里的每个槽位能填什么，由当前输入决定：Subject 和 Object 只能取“从当前句子中抽取出的实体”（候选来自输入，比如 Wikidata 实体集合约 270 万个），Relation 只能取预定义关系集合里的关系。不同输入句子抽出不同的实体 → 终结符集合不同 → 允许模型采样的 token 集合不同。
  • 解码时如何生效：grammar 状态决定当前在哪个槽位，槽位绑定的候选集合决定允许的 token；模型只在合法集合内采样。所以“随输入变化”不是模板变了，而是同一个模板装进了不同的候选集合。
  • 这样做的好处：新实体、新输入不需要重新训练模型，约束本身就把“输出必须是输入里出现的实体 + schema 里的关系”写死了。

证据与判断：GCD 用通用 LLM + 语法约束，在这些老任务上达到接近甚至超过专用微调模型的性能，说明“结构约束”能替代一部分训练时的先验注入。局限也在这：候选集合随输入动态变化且可能很大（百万级实体），无法像固定 grammar 那样预计算全词表位图，解码时的约束计算本身成为瓶颈——这正是下一节要解决的问题。

二、让“约束”本身的代价变小

上一节的遗留问题：每步都要查“哪些 token 合法”，查询和 mask 有成本。这一节的两篇工作分别用“跳过确定部分”和“预计算 + 重叠执行”处理。

SGLang（Zheng et al., NeurIPS 2024）

方法

  • compressed FSM：把 grammar 编译成更紧凑的转移结构，减少逐 token 状态维护开销。
  • jump-forward：当 grammar 在某段唯一确定 token 串时（例如 JSON 里的 {"key":），直接跳过模型前向，把固定文本一次性加入输出——相当于“100% 正确的投机”。

jump-forward 的问题

  • token 与字符的边界不确定：grammar 里的固定文本是按字符写的，但模型按 token 解码。跳过固定文本后，重新做分词得到的 token 可能和逐 token 解码时不一样（同一个字符串可能被分成不同的 token 序列），导致生成结果与正常解码不一致。
  • 可能破坏前缀缓存：跳过固定文本直接拼接，改变了“逐 token 生成”的输入序列；如果后续解码依赖完整的前缀 token 序列，前缀缓存可能失效或需要重新分词。

判断：jump-forward 方向对（确定的部分不该采样），但“直接跳过模型前向”这种形式不可取，原因是 token/字符边界不确定会破坏一致性，还可能影响前缀缓存。这为后面“把确定的部分做成预计算掩码，而不是跳过前向”埋下伏笔。

XGrammar（MLSys 2025）

方法

  • 核心洞察：词表分为 context-independent token（无论上下文都合法，如普通单词）和 context-dependent token（合法性依赖语法状态，如 JSON 键名、缩进 token）。前者可预计算合法 mask，后者才需要按状态查询。
  • 用**持久化栈（persistent stack）**维护语法状态，避免每次重新解析前缀。
  • 把这些计算放到 CPU 上执行，与 GPU 前向重叠执行（overlap with GPU execution）——mask 计算不再是 GPU 的串行依赖。

XGrammar 将 mask 生成和模型推理重叠

图：XGrammar 把 mask cache 构建与 prefill、mask 生成与 decoding 重叠。来自 XGrammar Figure 8，CC BY-SA 4.0。

关键不在于 mask 消失了，而在于它只依赖上一步 token、主要跑在 CPU；模型前向也只依赖上一步 token、主要跑在 GPU。因此两者可以并行，到 sampling 前才同步。只有 mask 计算没有超过 GPU 前向时间时，约束的端到端开销才会接近零。

证据与判断：论文报告约束计算最高约 100x 加速、接近零开销；它已成为 vLLM、SGLang 的默认结构化生成引擎之一，也是后文“约束 × 投机”实现的关键组件。数字为论文公开报告值，跨场景外推需自行复测。

三、约束解码 × 投机解码：DOMINO 怎么解决“错位”

投机解码（speculative decoding）是另一个独立主线：草稿模型快速生成候选，目标模型一次前向并行验证，不改变输出分布（Leviathan et al., ICML 2023，https://arxiv.org/abs/2211.17192）。DOMINO 是这两条线的交汇点。

DOMINO（Kang et al., ICML 2024）

它解决的问题

  1. 字符层 vs 子词层错位：约束（正则、JSON Schema）定义在字符层，但模型解码在子词（subword/BPE token）层。朴素做法是把 token 解码成字符再检查，慢且容易出错；DOMINO 做完全子词对齐（fully subword-aware），直接在 token 层构造合法集合。
  2. 逐 token mask 是串行开销：DOMINO 预计算合法 token 掩码（precomputed mask），把“查合法集”从每步串行工作变成可并行查表。
  3. 约束解码天然更慢：每步只有一小部分 token 合法，采样不确定性更高，实际吞吐比无约束解码更低。DOMINO 引入投机解码：草稿模型生成候选，目标模型一次前向验证多个 token，同时用约束掩码过滤非法 token。

三点逐一展开

  1. 第一篇文章（字符层检查）的问题：把 token 解码成字符再检查，实现上慢；且它和前面 jump-forward 一样，面临 token/字符边界不确定的问题——同一个字符序列可能对应不同的 token 切分，检查结果不稳定。DOMINO 的标准做法是对齐 token 而不是字符：合法集合直接定义在 token 层。
  2. 创新工作（可编辑查表预计算合法 token 掩码）：预先把“FSM 状态 → 合法 token 掩码”算好存成表，每步只做查表。具体说，就是用一个二维结构（状态 × 词表），mask[state] 直接给出该状态合法的 token 位图；每步取当前状态的掩码，与模型 logits 做一次位运算即可，不需要重新跑 FSM。这就是“把串行查询变成可并行查表”。
  3. 第三点（对应开头反事实）：约束解码的实际速度比无约束解码更低——这是反事实成立的前提。DOMINO 引入投机解码后，加速本质上来自投机解码（草稿模型猜 + 目标模型并行验证），不是来自约束本身；约束在这里的作用是在草稿上做约束引导的修正，把非法 draft 过滤掉。需要诚实说明：DOMINO 没有和“纯投机解码（无约束）”做对比——投机解码在无约束场景下本身就有 2.2～3 倍加速，DOMINO 约束+投机比这个要慢。换句话说，约束让投机解码的收益打折了，但它让“约束解码”从必然更慢变成了能吃到投机加速。

证据与判断：论文报告约束解码几乎零开销（near-zero overhead），部分场景比无约束解码还能近 2 倍加速。数字为论文报告值；但结论要定界：这个加速是“约束 + 投机”相对“无约束普通解码”的，不是相对“纯投机解码”的——后者的对比在论文里没有做，DOMINO 确实比纯投机慢。DOMINO 的核心贡献是把“约束”从每步串行查询变成了与投机验证并行的掩码。

DOMINO 中 speculative token 数与吞吐的关系

图：不同 speculative token 数下，带/不带 schema 的 JSON 生成吞吐。来自 DOMINO Figure 5，CC BY 4.0。

这张图补的是一个容易被口头叙述掩盖的事实：投机长度 k 不是固定越大越好，收益会随 grammar 和草稿可预测性改变。它支持“约束场景也能吃到投机加速”，但不构成约束组合优于纯投机解码的证据——论文没有做那组直接对照。

DOMINO 与前面工作的关系

问题早期做法DOMINO 的解法
约束在字符层、解码在子词层逐 token 解码成字符再检查完全子词对齐的合法 token 掩码
每步查合法集是串行开销FSM 逐 token 查询（Outlines 等）预计算掩码
约束解码吞吐比无约束低接受变慢投机解码并行验证 + 约束过滤

这张表说明：DOMINO 不是替代 FSM，而是把“查合法集”从 decode 关键路径上挪走，与投机验证并行。

合并点：约束过滤器 + 投机解码是互相帮助的关系

把两条线放在一起，真正的合并点在这里：

draft 模型快速生成候选 token
        ↓
约束过滤器（grammar mask）滤掉非法 draft —— 大部分乱猜的 token 在这一步就被挡掉
        ↓
剩下的合法 draft 才交给大模型（目标模型）并行验证
        ↓
验证通过的 token 才被接受
  • 约束帮了投机：没有约束过滤器时，draft 模型乱猜的 token 会全部进入目标模型验证，浪费大量前向。有了 grammar mask，大部分非法 draft 在进入验证前就被过滤掉，目标模型只需验证“本来就有可能是对的”那部分 token，验证次数大幅减少。
  • 投机帮了约束：约束解码本身每步只能采样少量合法 token，串行且慢；投机解码一次并行验证多个候选，把“每步只能走一步”变成“每步可以试多条路”，约束解码从必然更慢变成能吃到并行加速。

所以两者不是“约束拖慢投机”或“投机绕过约束”，而是互相帮助：约束负责告诉系统“什么不可能”，投机负责“一次多猜几条”，验证只发生在两者交汇处（合法候选上），浪费的前向最少。

但这是一个 tradeoff，不是免费午餐

“约束帮投机省验证”要定界：过滤本身也有成本。DOMINO 约束+投机比纯投机慢，本质是 tradeoff，而不是实现缺陷：

  • 省的和花的不是同一笔账：约束过滤能省的是目标模型的验证前向，但它自己做 mask 查询也要花钱。严格说，投机解码只是把约束解码原来“每步查表”的开销摊薄了（一次并行验证多条路径），并没有消除约束本身。过滤数量减少的是“进入验证的 token”，但过滤动作本身依然逐候选执行。
  • 收益取决于 draft 分布与合法集合的差距：
    • 差距小（约束松、draft 准）：大部分 draft 本来就合法，过滤成本低、验证收益高，接近纯投机；
    • 差距大（约束严、draft 乱猜）：大部分 draft 被过滤掉——验证次数确实省了，但过滤本身做了大量工作，被接受的候选很少，整体收益趋近于零，甚至过滤成本超过省下的验证。
  • 划算的场景是中间态：约束把 draft 收敛到合法区，但合法区又足够大，draft 不至于大部分被拒。约束越严、draft 与合法集合分布差越大，这个组合的收益越少。

四、相关工作：约束解码与投机解码的结合

DOMINO 之后，“约束 + 投机”成为结构化生成的主流方向。下面几条是代表性的演进线：

SketchGCD（ACL 2024）

方法：先让模型生成一个不含约束的草稿（sketch），再在草稿上做约束引导的修正，避免每步都查 FSM；扩展到黑盒 LLM 场景。

判断：这说明“约束不一定必须逐 token 生效”，先宽松生成再约束校验也是实用范式——与投机解码的“先 draft 再 verify”结构上同构。

JSONSchemaBench（2025）

方法：这是一个约束解码框架的系统评测，对比了 vLLM、SGLang、Outlines、XGrammar 等主流实现，在同一批 JSON Schema 任务上测三件事：正确率（是否严格满足 schema）、延迟、吞吐。

证据与判断：

  • 正确率维度：约束解码的“结构正确性”普遍有保障——只要约束生效，输出严格满足 schema。
  • 延迟/吞吐维度：不同框架差异显著，主要差距来自约束查询的实现方式（逐 token 串行 vs 预计算查表）以及能否与投机解码配合。
  • 结论：约束解码“能保证格式”，但“快不快”取决于实现；这解释了为什么实现细节（PR 层面的设计）值得单独讲。

XGrammar-2（2026-05）

它解决的问题：XGrammar 已经把单次约束计算的代价降到接近零，但投机解码场景下约束计算次数爆炸：投机解码会生成一棵候选树（多个草稿分支），每个候选节点都要查一次“该状态下哪些 token 合法”。树的宽度 × 深度次查询，即使单次很快，总量也可观；而且不同节点可能处于相同/相似的 FSM 状态，重复计算浪费明显。

方法：

  • Structural Tag：直接支持 JSON Schema / XML 等结构化标签，把常见结构化约束表达成框架内置的标签，而不是每次手动写 grammar。
  • 跨 grammar 缓存：不同请求共享同一 grammar 的预计算结果，避免每个请求重新编译。
  • 重复状态压缩：消除 FSM 中的重复状态，减少状态数，从而减少需要维护的掩码表大小。
  • 树遍历（TraverseDraftTree）：一次 DFS 遍历投机解码的候选树，为整棵树批量生成 grammar mask，而不是逐节点查询——这是“约束 × 投机”从论文走向工程的关键一步。

判断：XGrammar-2 解决的是“投机树让约束计算次数爆炸”的问题——单次约束计算已经很快，但次数多了总量可观；树遍历把“每节点一次”变成“每树一次”，跨 grammar 缓存把“每请求一次编译”变成“跨请求复用”。这是约束 × 投机工程化的最新状态：约束计算本身不再是瓶颈，瓶颈转移到“如何让约束掩码与投机树/缓存更好配合”。

五、功能实现：关键 PR 与实现细节

这一节看“约束解码怎么在框架里落地”。以 vLLM、SGLang、XGrammar 的公开实现为例，看约束查询怎么从“每步串行”变成“与投机并行”。

vLLM v0.4.0：guided_logits_processors.py 的逐 token mask

  • 文件：vllm/model_executor/guided_decoding/guided_logits_processors.py
  • 关键逻辑（BaseLogitsProcessor.__call__）：
    • 用 fsm_state = hash(input_ids) 维护 FSM 状态（基于当前前缀的哈希）；
    • 查 allowed_token_ids(state) 得到合法 token 集合；
    • mask = full(-inf)，再把 mask[allowed] = 0，最后 scores.add_(mask) 把非法 token 的 logits 压到 -inf。
  • 这一步每生成一个 token 都执行，且是纯 CPU 串行（FSM 查询在 CPU 上），所以它本身不会加速，只会增加延迟——这是早期“约束解码必然更慢”的根源之一。

缓解手段：guided_decoding.py 里用 ThreadPoolExecutor(max_workers=2) 异步编译 FSM，把编译开销藏到生成之外；但每步查询的开销仍在 decode 关键路径上，直到与投机解码结合才真正被绕开。

vLLM PR #14702：Structured Outputs + Speculative Decoding

做了什么：让 vLLM 支持结构化输出的投机解码——draft token 按 grammar 验证，非法 draft 直接丢弃，合法 draft 进入并行验证。

它解决的问题：之前 vLLM 里约束解码（guided decoding）和投机解码互斥——开了结构化输出就不能用投机加速。原因是草稿模型不知道语法约束，生成的 draft 大概率非法，直接验证会浪费目标模型的前向。

做了什么（补充）：让 draft token 按 grammar 验证，非法 draft 直接丢弃，合法 draft 才进入并行验证。约束在这里不是“额外负担”，而是天然的草稿过滤器——草稿模型乱猜的 token 大部分会被 grammar 挡住。

判断：PR 的关键是把“约束”从投机解码的障碍变成过滤器：合法 draft 进入验证，非法 draft 提前丢弃，结构化生成也能吃到投机加速。但要注意，这和 DOMINO 的结论一致——约束会挡住一部分合法草稿（草稿模型本来可能生成合法但被约束排除的内容），实际收益取决于草稿质量与约束严格度的权衡。

SGLang PR #13425：Spec V2 + XGrammar 同时启用

做了什么：让 SGLang 的投机解码（Spec V2）与 XGrammar 约束解码同时启用，此前二者互斥；实现上把 XGrammar 的 mask 计算从 decode 关键路径移出/重叠，与投机解码的草稿验证并行。

判断：这验证了 DOMINO 的路线在主流框架里可行——“约束几乎零开销 + 投机加速”两个目标可以同时成立。

XGrammar PR #490 / #613：投机解码树遍历的 mask 生成

做了什么：PR #490 提出 TraverseDraftTree，对投机解码的候选树做单次 DFS 遍历，一次性为整棵树生成 grammar mask，而不是对每个候选节点单独查询；PR #613 把它正式暴露为 GrammarMatcher API（XGrammar-2 的树遍历能力即源于此）。

它解决的问题：投机解码的候选树有多个分支，每个分支的 FSM 状态可能不同。如果每个节点单独查 mask，代价是树的规模（宽度 × 深度）次查询；且树里很多节点共享相同的前缀状态，重复计算明显。

判断：这是“约束 × 投机”从论文走向工程的最后一块拼图——约束计算从“每 token 一次”变成“每棵树一次”，开销进一步摊薄。树的规模越大，这个优化的收益越明显。

总结与适用边界

把这条线串起来看，约束解码的演进是**“约束怎么表达”到“约束怎么不花钱”**的过程：

  1. 早期（Grid Beam Search）把约束做进搜索：正确，但慢，且只覆盖“必须包含词”这一种约束。
  2. Outlines / GCD 把约束变成可编译的 FSM：通用、模型无关，但每步查合法集开始成为开销。
  3. SGLang / XGrammar 让约束本身变快：压缩 FSM、预计算、跳确定 token、与 GPU 重叠执行——“确定的部分直接跳过”第一次成为可行策略。
  4. DOMINO 把投机解码引入约束场景：解决字符层/子词层错位，用预计算掩码把约束查询变成查表，再通过投机解码让约束场景也能吃到并行验证的加速——但要明确，加速来自投机解码本身，且 DOMINO 比纯投机解码慢。
  5. 工程上（vLLM / SGLang / XGrammar 的 PR）把“约束 × 投机”做成默认能力：树遍历批量生成 mask、跨请求缓存，约束计算不再是瓶颈。

回到开头的猜想：“确定性的重复”确实可以做成加速——但关键不是只跳固定字符串，而是把“确定的部分”（固定字段、唯一合法 token）和“不确定的部分”（草稿模型猜、目标模型验）分开处理，让约束解码从“逐 token 串行查表”变成“批量掩码 + 并行验证”。

适用边界

  • 本文加速倍数（XGrammar 约 100x、DOMINO 近 2x）均为论文/官方公开报告值，具体场景请自行复测。
  • DOMINO 的“近 2 倍加速”是相对无约束普通解码的，不是相对纯投机解码；纯投机在无约束场景下本身有 2.2～3 倍加速，DOMINO 约束+投机比它慢（论文未做该对比）。
  • 约束解码保证的是“输出满足结构”，不保证“输出内容正确”——结构合法与语义正确是两件事。
  • 约束本身复杂时（超大 vocabulary、深层嵌套 schema），预计算与缓存的收益才明显；简单约束下逐 token FSM 的开销可能已经可接受。

写作说明：本文涉及的论文、框架与 PR 均来自公开资料（arXiv、ACL Anthology、GitHub、MLC Blog），截至 2026-08；加速倍数与性能数据均为论文/官方公开报告值，具体场景请自行复测。XGrammar-2 与部分 PR 属于较新资料，阅读时请注意版本迭代。