约束解码结构化输出:JSON Schema 与正则约束下 logit mask 和 FSM 推进的原理与延迟代价
更新时间:2026-09-30。让大模型输出「能直接被程序消费」的 JSON,是推理服务最常被点名的需求:函数调用、表单抽取、配置生成都要求输出严格符合某个 Schema。靠 prompt 里写「请只输出 JSON」只能保证 95% 的合规率,剩下 5% 的多一个逗号、少一个引号,就会让下游解析器崩盘。约束解码结构化输出(guided decoding / structured output)把这件事从「请求模型配合」变成「采样器强制保证」。它是 投机解码推理加速 的邻居技术——两者都在采样环节动手脚,但目标相反:一个为速度,一个为合法性。本篇只回答一个问题:约束是怎么从一份 JSON Schema 变成每一步 token 采样时的「合法集合」,以及这份保证要花多少延迟。
本文要回答的问题
- 约束解码为什么能保证输出 100% 符合 JSON Schema,而不是「大多数时候符合」?
- logit mask 是怎么从 Schema 一路推导到每个解码步的词表子集的?
- FSM(有限状态机)在约束推进里扮演什么角色,状态怎么随已生成 token 移动?
- 约束解码对首 token 延迟和每步解码延迟分别有多大影响,什么时候值得开?
一、从「求模型配合」到「采样器强制」
无约束的解码每一步都是从完整词表(比如 128K 个 token)上按 softmax 概率采样。模型大概率会输出合法 JSON,但「大概率」不等于「一定」——长输出里任何一步偏出语法,整个文档就废了。约束解码的思路非常直接:每一步采样前,先算出「当前位置允许出现哪些 token」,把不允许的 token 的 logit 置为 −∞,再 softmax、再采样。这样无论模型多想输出一个非法字符,采样器都物理上选不到它。
这个「置 −∞ 的向量」就是 logit mask。关键问题是:允许的 token 集合从哪来?答案是分两步:
- 编译期:把 JSON Schema(或正则表达式)编译成一个自动机——正则直接编译成 DFA(确定性有限自动机);JSON Schema 先展开成一个上下文无关文法,再针对「当前已经生成的部分输出」增量地求出下一个合法字符集。
- 运行期:每生成一个 token,自动机状态前进一步,重新计算下一步的合法 token 集合,生成新的 mask。
以 Outlines、XGrammar、vLLM 的 guided decoding 为代表的实现,都遵循这条流水线。下面这张图把整条链路画出来。
这张图里有两个循环值得注意。外循环是解码循环:LLM 前向 → mask → 采样 → 输出 token,这就是普通自回归解码,只是多了一个 mask 环节。内循环是自动机推进:采样出的 token 反馈回自动机,状态迁移,下一步的 mask 随之改变。约束的「强制性」就来自 mask 与采样器串联在数学上不可绕过——无论 prompt 注入、模型幻觉还是温度调高,非法 token 的概率都被乘成精确的 0。
二、FSM 推进:一个最小例子
用一个最简单的正则 "(yes|no)" 看状态机怎么工作。编译出来的 DFA 大概长这样:起始状态 S0,读到 " 进 S1,S1 读 y 进 yes 分支、读 n 进 no 分支,各自走到结尾的 " 进接受状态 Sf。
实际工程里麻烦的是 token 边界不跟字符对齐:tokenizer 可能把 "ye 切成一个 token,也可能把 " 单独成一个 token。所以 mask 生成器要做的查询是:「从当前状态出发,词表里哪些 token 的字符串能完整地沿自动机转移且不落入死路」。这一步需要对词表做索引——XGrammar 的做法是预先把词表里每个 token 按「能在哪些自动机状态下被接受」分类缓存,运行期只查表,把每步 mask 生成压到微秒级。
| 已生成前缀 | 自动机状态 | 合法 token 举例 | 非法 token 举例 |
|---|---|---|---|
| (空) | S0 | " | yes、{、1 |
" | S1 | ye、yes、n | x、数字 |
"ye | yes 分支 | s"、s | o、n" |
"yes" | Sf | (EOS 或后续分隔符) | 任何其他字符 |
对完整 JSON Schema,事情复杂在「当前位置」由文法栈决定:在 {"name": " 之后期望字符串字符,在 {"age": 之后期望数字,数组里还要匹配元素个数上下界。现代实现把 JSON 文法编译成下推自动机(PDA,带栈的 FSM),用栈跟踪括号嵌套深度,mask 查询时综合栈顶符号决定合法终结符集。
三、延迟代价:钱花在哪
约束不是免费的。开销分三块:
1. 编译开销(一次性)。Schema 编译成自动机通常几十到几百毫秒,复杂 Schema 更久。生产系统必须缓存编译结果——同一个 Schema 反复用,编译只付一次。这也是 连续批处理调度器 场景里要注意的:batch 里不同请求带不同 Schema,调度器按 Schema 哈希分桶能有效摊薄。
2. 每步 mask 开销(运行期,小)。词表索引命中后,mask 生成是一次位图查表加一次 128K 维向量加法,实测每步增加约 10~100 微秒——相对每步几十毫秒的前向计算可忽略。XGrammar 论文报告把每步开销压到 40 微秒以内,对吞吐影响 <5%。
3. 首 token 延迟(TTFT)的隐性收益。常被忽视的一点:约束解码往往减少总生成 token 数——模型不会再输出「好的,这是您要的 JSON:」这类废话,也不会在 JSON 外面包 Markdown 代码块。输出短了,端到端延迟反而可能下降。
还有一个交互效应:约束解码与 投机解码推理加速 同开时,draft 模型提议的 token 也要过 mask 校验,非法提议直接拒绝,接受率会略降,工程上通常让 draft 模型也在约束下采样以维持接受率。
四、什么时候开,什么时候不开
决策可以按输出消费者来分:
| 场景 | 建议 | 理由 |
|---|---|---|
| 函数调用 / API 参数生成 | 必开 | 下游是解析器,5% 失败率不可接受 |
| 表单抽取、ETL 入库 | 必开 | 还要枚举约束、数值范围约束 |
| 多 Agent 协议消息 | 建议开 | 格式错误会在系统内级联放大 |
| 给用户看的散文 | 不开 | 无 Schema 可言,纯增延迟 |
| 创意 JSON(字段不确定) | 谨慎 | 强 Schema 会限制模型表达,可考虑宽松 Schema |
工程接入时三个坑要提前想:其一,Schema 尽量扁平——深层嵌套和 anyOf 大 union 会让自动机状态爆炸,编译时间和内存都上去;其二,数值范围约束(minimum/maximum)在 token 级很难精确表达,现有实现多退化为「语法上合法的数字」,范围校验留给后处理;其三,流式输出时每个 chunk 都是部分 JSON,客户端解析要用增量解析器,不能等全文。推理框架侧的优化(比如把 mask 计算塞进 TensorRT 推理优化 的 CUDA kernel 里做融合)正在把每步开销进一步压向零。
这一篇在知识体系里的位置
- 横向:与 投机解码推理加速 同属「采样层改造」,一个改接受规则提速,一个改候选集合保合法性,可叠加使用。
- 上游:调度与吞吐侧见 连续批处理调度器,约束请求的 Schema 分桶是它的负载特征之一。
- 下游:kernel 层优化见 TensorRT 推理优化,mask 融合是其中一类自定义算子。
总结
约束解码结构化输出把 JSON Schema 或正则在编译期翻译成自动机,运行期每步按当前状态算出合法 token 集、用 logit mask 把非法 token 的概率置零,从而把输出合法性从「prompt 请求」升级为「采样器数学保证」;代价是一次性编译开销加每步几十微秒的查表,换来 100% 语法合规和更短的输出——凡输出要被程序解析的场景,都应该把约束打开。