正文
凌晨两点,你的 LLM 应用又挂了。
错误日志很熟悉:json.decoder.JSONDecodeError: Expecting ',' delimiter。又是那个老问题——你让模型以 JSON 格式返回一个函数调用参数,模型”非常配合”地返回了 99% 正确的 JSON,然后在最后一个大括号前少写了一个逗号。
对程序来说,99% 正确就是 100% 错误。
这就是结构化输出的困境:你可以在 prompt 里跪求模型”请务必返回合法 JSON”,也可以在解析失败后自动重试,但前者不可靠,后者烧钱。真正的解法是约束解码(Constrained Decoding)——在采样环节直接掐断非法 token,让模型从原理上”不可能”输出错误格式。
而今天的主角 xgrammar,就是约束解码引擎里的卷王:由陈天奇团队(CMU mlc-ai)于 2024 年 11 月开源,论文发表于 MLSys 2025。如今它是 vLLM、SGLang、TensorRT-LLM、MLC-LLM 的默认结构化输出后端,DeepSeek、xAI、Meta、Databricks 都是它的使用者。
为了搞清楚它到底怎么工作的,我把 vLLM 和 xgrammar 的源码 clone 下来翻了一遍。这篇文章就聊聊:
- 结构化输出为什么难做
- xgrammar 的核心算法:怎么把”每步检查 12 万个 token”变成”查一下缓存”
- vLLM 是怎么把它嵌进推理主循环的(真实代码路径)
约束解码:在采样环节掐断错误
先说清楚约束解码的基本原理。
大模型生成文本是自回归的:每一步对词表里的所有 token 算出一个 logits 向量 $z$,经过 softmax 变成概率分布,再采样出下一个 token:
$$
P(t_i) = \frac{e^{z_i}}{\sum_j e^{z_j}}
$$
约束解码的思路简单粗暴:**每一步生成前,检查词表里哪些 token 会导致输出违反目标结构,把它们的 logits 直接置为 $-\infty$**。softmax 之后这些非法 token 的概率就是 0,物理上不可能被采样到:
$$
P’(t_i) = \frac{e^{z_i} \cdot m_i}{\sum_j e^{z_j} \cdot m_j}, \quad m_i \in {0, 1}
$$
其中 $m_i$ 是 token $i$ 的合法性掩码(bitmask),1 表示合法,0 表示非法。
1 | 生成 "{" 后,词表检查: |
这样一路”安检”下去,模型生成的每一个 token 都在合法集合内,最终输出100% 符合结构。这个性质是 prompt 工程和重试永远给不了的——数学上可证明的正确。
但魔鬼在细节里。想高效地实现”每一步检查整个词表”,要翻过三座大山。
三座大山:约束解码为什么难
第一座山:词表太大
主流模型的词表动辄 12 万起步(Llama 3.1 是 128256)。每生成一个 token,就得把全部 12 万个 token 挨个跑一遍语法检查。如果每次检查要 1 微秒,一步就是 128 毫秒——而 GPU 上一步解码本身可能只要 6 毫秒。语法检查直接成了瓶颈,还是 20 倍的那种。
第二座山:语法状态是”栈”,没法穷举缓存
JSON、SQL 这类结构的规范写法是上下文无关文法(Context-Free Grammar, CFG),因为它支持递归嵌套——数组里套对象、对象里再套数组,正则表达式根本表达不了。
判断一段文本是否符合 CFG,经典方法是下推自动机(Pushdown Automata):维护一个栈,栈里记录”目前匹配到哪、接下来还期待什么”。比如匹配 ["a 这个前缀时,栈大致是这样:
1 | 栈(从顶到底,即"待办事项清单"): |
问题来了:栈的内容组合是指数级的,你不可能像查字典一样把所有栈状态对应的合法 token 预先算好。每一步的合法性判断都依赖当前这个”独一无二”的栈,这就是为什么朴素实现快不起来。
第三座山:token 边界和语法边界对不齐
LLM 的 token 不是字符,是 BPE 切出来的任意字符串。一个 token 可能横跨多个语法元素,比如 token ": tr 同时跨过了字符串结尾、冒号、空白和布尔值开头;反过来,一个语法元素也可能被切成好几个 token。
这意味着”检查一个 token 是否合法”可能要连续触发多次栈的 push/advance/pop,中途任何一步失败,这个 token 就是非法的。边界错位的处理逻辑,朴素实现里全是特判。
xgrammar 的核心洞察:把词表”三分天下”
xgrammar 论文的关键洞察是:虽然每一步的栈都独一无二,但词表里绝大多数 token 的合法性,其实只跟”栈顶节点”有关,跟栈的其余部分无关。
下推自动机匹配一个 token 时,栈的变化只有三种情况:
| 类型 | 行为 | 例子 |
|---|---|---|
| push | 展开进入子规则,压新元素入栈 | 遇到 [,进入数组规则 |
| advance | 在当前规则内前进,更新栈顶位置 | 在字符串里继续读字符 |
| pop | 当前规则结束,弹栈回到父规则 | 遇到 ],数组闭合 |
绝大多数 token 属于前两类——只碰栈顶,不弹栈。这类 token 叫上下文无关 token(context-independent):给定栈顶节点,它的合法性就确定了,和栈底下压着什么没关系。
只有极少数 token 会触发 pop,而且 pop 之后还要看新的栈顶才能定生死——这类叫上下文相关 token(context-dependent),必须带着完整栈现场跑一遍自动机。
有多悬殊?论文实测:Llama 3.1(128256 词表)配 JSON 文法,上下文相关 token 只有1134个占比不到1%。
于是 xgrammar 的策略一目了然:
1 | 每一步生成时: |
这就是 adaptive token mask cache(自适应 token 掩码缓存):预处理阶段为每个栈顶节点预计算好上下文无关 token 的合法性并存起来,运行时查一下就行。每步的开销从”12 万次语法检查”骤降到”一次查表 + 1134 次现场计算”。
自适应存储:160MB 怎么压成 0.46MB
缓存听起来很美,但有个坑:一个栈顶节点对应一张全词表的掩码(128256 位 ≈ 16KB),JSON 文法展开后的栈顶节点数以万计。如果老老实实每个节点存一张全量 bitset,缓存直接膨胀到 160MB。
xgrammar 的解法是自适应存储格式——观察每个节点掩码的稀疏特性,挑最省的方式存:
| 场景 | 特点 | 存什么 |
|---|---|---|
| accept-heavy | 大部分 token 合法 | 只存少数”被拒绝”的 token 列表 |
| reject-heavy | 大部分 token 非法 | 只存少数”被接受”的 token 列表 |
| 极端均衡 | 两者数量接近(罕见) | 老老实实压成词表大小的 bitset |
直觉上就像”记名单”:99 个人都到场,你只需要记谁没来;99 个人都缺席,你只需要记谁来了。
效果:Llama 3.1 + JSON 文法的缓存从 160MB 压到 0.46MB,只剩原来的 **0.2%**。缓存小到能塞进任何设备的内存,这也是 xgrammar 能跑在浏览器、手机上的前提之一。
再砍一刀:上下文展开(Context Expansion)
连那不到 1% 的上下文相关 token,xgrammar 还想再削减。
思路是:预处理时提取每个规则的展开后缀自动机——“完成当前规则之后,紧接着必须匹配哪些字符”。如果某个上下文相关 token 的内容跟所有可能的后续都接不上,那它在预处理阶段就可以被判死刑,不用等到运行时。
这相当于提前剧透:”这个出口出去只能往左走,想往右的现在就可以劝退了。”
持久化执行栈:投机解码的”后悔药”
约束解码还有个隐藏需求:回滚(rollback)。
最典型的场景是投机解码(本系列其六聊过):草稿模型一次猜 K 个 token,目标模型验证时可能只接受前 3 个。如果语法状态机跟着草稿一路推进了 5 步,发现第 4 个就错了,状态机就得退回到第 3 步的位置重新来。
传统栈结构做回滚很痛苦:要么每步都深拷贝一份栈(内存爆炸),要么从头重放(时间爆炸)。xgrammar 用了一个经典数据结构技巧——持久化栈(persistent stack):
1 | 把匹配过程中出现过的所有栈组织成一棵树: |
关键特性:
- 分支:遇到文法歧义(一个字符对应多条边)时,自动机分裂出多个并行栈,每个分支只是在树上多长一根枝
- 回滚:把当前状态指针沿树回退即可,时间复杂度 O(1)
- 省内存:所有历史状态共享公共前缀,只为新增部分付钱
这个设计在 vLLM 里被直接消费了——创建语法匹配器时传入 max_rollback_tokens,等于投机解码的深度:
1 | # vllm/v1/structured_output/backend_xgrammar.py(节选) |
约束解码和投机解码,两个听起来不搭界的技术,在”持久化栈”这里接上了头。
vLLM 是怎么集成 xgrammar 的
理论讲完,看工程。把 vLLM 的源码(v1 引擎,2026 年 8 月 master)翻了一遍,xgrammar 的集成链路可以拆成五段。
第一步:后端自动选择——xgrammar 优先,搞不定再摇人
vLLM 的结构化输出支持多个后端(xgrammar、guidance、outlines、lm-format-enforcer),默认是 auto 模式,优先尝试 xgrammar:
1 | # vllm/sampling_params.py(节选) |
xgrammar 不是万能的:JSON schema 里的 uniqueItems、patternProperties、数字的 multipleOf 这些特性它不支持(见 has_xgrammar_unsupported_json_features),这时请求会无缝降级到 guidance。这就是为什么 vLLM 文档里说 xgrammar 是”默认但非唯一”的后端。
第二步:异步编译文法——请求先排队,别阻塞别人
文法编译(JSON schema → EBNF → 下推自动机 + 掩码缓存)是有成本的,复杂 schema 可能要几十毫秒。vLLM 的处理方式是异步编译 + 专用等待状态:
- 请求进来后,
StructuredOutputManager.grammar_init把编译任务扔进线程池 - 请求进入
WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR状态,暂时不参与调度 - 调度器每轮检查:编译好了(
Future完成)就升级为WAITING,正常排队
1 | # vllm/v1/core/sched/scheduler.py(节选) |
这就是论文里说的”掩码缓存构建与 prefill 重叠”:你的请求在等编译时,GPU 正在服务别的请求,编译耗时被藏在了调度间隙里。
后端初始化时还会建一个带 LRU 缓存的编译器,同一个 schema 来第二遍直接命中:
1 | # vllm/v1/structured_output/backend_xgrammar.py(节选) |
VLLM_XGRAMMAR_CACHE_MB 默认 512,按注释说大约能装 1000 个 JSON schema。
第三步:每步生成批量填掩码——CPU 线程池并行
到了解码主循环,每一步调度器会为整个 batch 的结构化请求批量生成 bitmask。非投机解码场景下,大 batch(超过 128 个请求)时用线程池并行填:
1 | # vllm/v1/structured_output/__init__.py(节选) |
填掩码的底层调用就是 xgrammar 的 fill_next_token_bitmask——查缓存 + 跑那不到 1% 的上下文相关 token,实测单请求单步不到 40 微秒。
投机解码的配合尤其精巧。草稿模型提前猜了 K 个 token,vLLM 需要为每个草稿位置都算一张掩码(万一前几个草稿被拒,后面的位置还得接着约束)。做法是”吃一个、填一张、最后全退回去”:
1 | # vllm/v1/structured_output/__init__.py(简化) |
能看到持久化栈在这里发挥了作用:模拟多少步都能一次性全退回去,回滚代价几乎为零,这才敢对每个草稿位置都做一遍前向模拟。
第四步:GPU 上原位应用掩码——一个 Triton kernel 收尾
CPU 填好的 bitmask(int32 位压缩,一行 = 词表/32 个 int32)异步拷到 GPU,然后用一个 Triton kernel 把非法 token 的 logits 原地置为 $-\infty$。这个 kernel 就是从 xgrammar 官方实现改的:
1 | # vllm/v1/worker/gpu/structured_outputs.py(节选,改编自 |
bitmask 的复制走独立的 CUDA stream 异步进行,与主计算流重叠——又是”藏延迟”的老手艺。之后采样器面对的就是一个”非法 token 概率为零”的分布,怎么采都合法。
第五步:接受新 token,状态机前进
采样出结果后,调度器调 accept_tokens 把新 token 喂给匹配器,状态机前进一步;如果状态机拒绝(理论上不可能发生,除非有 bug),会记一条 “Please file an issue” 的错误日志。
整条链路串起来:
1 | 请求到达 |
另外值得一提的是对思考模式(reasoning)的支持:配置了 reasoning_parser 的请求,在推理内容结束前不施加结构约束(思考部分随便写),检测到推理结束标记后才开始填掩码。这个开关就是 should_fill_bitmask 里那段判断。
性能数据:到底省了多少
论文(Llama-3.1-8B-Instruct,RTX 4090 / H100)的关键数字:
| 指标 | 结果 |
|---|---|
| 单步掩码生成延迟 | < 40 μs(CPU) |
| JSON CFG 场景加速 | 相比 SOTA(Outlines/llama.cpp)最高 100 倍 |
| JSON Schema 场景加速 | 最高 3 倍 |
| 端到端服务吞吐(H100) | 相比旧版 vLLM+Outlines 最高 80 倍 |
| 结构化带来的额外开销 | 近乎为零 |
| 掩码缓存内存 | 160 MB → 0.46 MB(0.2%) |
| 上下文相关 token 占比 | 1134 / 128256 ≈ 0.9% |
“开销近乎为零”有实测背书:开与不开结构约束,TPOT(每 token 耗时)几乎无差别——
| 任务 | Batch | 无约束 | 有约束 |
|---|---|---|---|
| JSON Schema | 1 | 6.2 ms | 6.3 ms |
| JSON Schema | 16 | 9.0 ms | 9.2 ms |
| CFG (JSON) | 1 | 6.3 ms | 6.3 ms |
| CFG (JSON) | 16 | 9.0 ms | 9.1 ms |
(单位毫秒,摘自论文 Table 1)
换句话说:在 vLLM 里开结构化输出,你得到 100% 的格式保证,付出的代价约等于零。旧时代”结构化输出慢几倍”的印象,已经是老黄历了。
怎么用
如果你在用 vLLM 部署,什么都不用配——只要请求里带上结构化参数,xgrammar 自动上岗。OpenAI 兼容接口:
1 | from openai import OpenAI |
structured_outputs 里除了 json,还支持 regex(正则)、grammar(自定义 EBNF 文法)、choice(限定选项)和 structural_tag(结构化标签)。老教程里常见的 guided_json、guided_regex 等参数在 vLLM v0.12.0 已移除,注意迁移。想强制指定后端,启动服务时加 --structured-outputs-config.backend=xgrammar 即可。
如果你想在自己的推理循环里直接用 xgrammar(不经过 vLLM),核心 API 也就几行:
1 | import xgrammar as xgr |
xgrammar 本体只有 1.2 万行核心 C++ 代码,通过 Emscripten 编译成 WebAssembly 后还能跑在浏览器里(WebLLM 就是这么干的),手机上跑 Qwen-2.5-0.5B 配结构化输出也近乎零开销。
尾声:从守门员到动态守门员
回到开头那个凌晨两点的报错。
xgrammar 解决的本质问题是:如何在每一步 12 万个候选的检查里,找到那 99% 可以”抄答案”的部分。它的答案是把词表按”是否依赖栈的深处”一刀切开,用自适应缓存把空间压到 0.2%,用持久化栈把回滚变成 O(1),再用与 GPU 计算的重叠把最后的延迟藏起来。
这套组合拳打下来,约束解码从”昂贵的保险”变成了”免费的保险”——这也是它能在一年内成为所有主流推理引擎默认后端的原因。
故事还有个后续:2026 年 5 月,团队发布了 XGrammar-2,核心从下推自动机换成了 Earley 解析器,主打 Agent 场景下的动态结构——比如 JSON schema 本身依赖模型前面生成的内容这种”越生成越变化”的约束。如果你关注 agentic 场景下的工具调用和函数编排,值得留意。
至于 xgrammar 这个名字——“x” 大概是这个团队(MLC)一如既往的致敬习惯(MLC-LLM、TVM…),而 grammar 就是它的全部使命:让大模型说出的每一句”机话”,都符合语法。
参考资料
- XGrammar 论文:XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models(MLSys 2025)
- XGrammar-2 论文:XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs
- 代码仓库:mlc-ai/xgrammar、vllm-project/vllm
- 本文 vLLM 代码路径基于 2026 年 8 月 master 分支:
vllm/v1/structured_output/backend_xgrammar.py、vllm/v1/structured_output/__init__.py、vllm/v1/worker/gpu/structured_outputs.py、vllm/v1/core/sched/scheduler.py - vLLM 结构化输出文档:Structured Outputs