Zer0e's Blog

AI其八:什么是xgrammar?大模型结构化输出的守门员

字数统计: 5k阅读时长: 19 min
2026/10/24 Share

正文

凌晨两点,你的 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 下来翻了一遍。这篇文章就聊聊:

  1. 结构化输出为什么难做
  2. xgrammar 的核心算法:怎么把”每步检查 12 万个 token”变成”查一下缓存”
  3. 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
2
3
4
5
生成 "{" 后,词表检查:
token '"' → 合法(可以开始写 key) m = 1
token '}' → 合法(空对象) m = 1
token 'abc' → 非法(不是引号开头) m = 0 → logit 置 -∞
token '\n' → 合法(允许空白) m = 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
2
3
4
5
6
7
栈(从顶到底,即"待办事项清单"):
┌────────────────────────────┐
│ 期待: "," 或 "]" │ ← 栈顶
│ 期待: 一个 string │
│ 期待: 更多数组元素 │
│ 期待: 结束符 │
└────────────────────────────┘

问题来了:栈的内容组合是指数级的,你不可能像查字典一样把所有栈状态对应的合法 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
2
3
4
5
6
7
8
9
每一步生成时:
┌─────────────────────────────────────────────┐
│ 99% 的 token(上下文无关) │
│ → 拿栈顶节点当 key,查预计算缓存,直接得结果 │
├─────────────────────────────────────────────┤
│ <1% 的 token(上下文相关) │
│ → 带着完整栈,现场跑下推自动机 │
└─────────────────────────────────────────────┘
最后合并成这一步的最终 bitmask

这就是 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
2
3
4
5
6
7
8
9
10
11
12
13
14
把匹配过程中出现过的所有栈组织成一棵树:

root
│
"[" ← 第1步
│
'"a"' ← 第2步(所有分支共享这段历史)
╱ ╲
"," "]" ← 第3步的两种可能(分支)
│
'"b"' ← 沿着某分支继续

新状态 = 在树上新挂一个节点(O(1)),共享全部历史
回滚 = 把指针挪回祖先节点(O(1)),不用复制任何东西

关键特性:

  • 分支:遇到文法歧义(一个字符对应多条边)时,自动机分裂出多个并行栈,每个分支只是在树上多长一根枝
  • 回滚:把当前状态指针沿树回退即可,时间复杂度 O(1)
  • 省内存:所有历史状态共享公共前缀,只为新增部分付钱

这个设计在 vLLM 里被直接消费了——创建语法匹配器时传入 max_rollback_tokens,等于投机解码的深度:

1
2
3
4
5
6
# vllm/v1/structured_output/backend_xgrammar.py(节选)
matcher=xgr.GrammarMatcher(
ctx,
override_stop_tokens=list(stop_token_ids) if stop_token_ids else None,
max_rollback_tokens=self.num_speculative_tokens, # 为投机解码预留回滚深度
)

约束解码和投机解码,两个听起来不搭界的技术,在”持久化栈”这里接上了头。

vLLM 是怎么集成 xgrammar 的

理论讲完,看工程。把 vLLM 的源码(v1 引擎,2026 年 8 月 master)翻了一遍,xgrammar 的集成链路可以拆成五段。

第一步:后端自动选择——xgrammar 优先,搞不定再摇人

vLLM 的结构化输出支持多个后端(xgrammar、guidance、outlines、lm-format-enforcer),默认是 auto 模式,优先尝试 xgrammar:

1
2
3
4
5
6
7
8
9
10
# vllm/sampling_params.py(节选)
# auto 模式:先试 xgrammar,失败则按情况降级
try:
validate_xgrammar_grammar(self)
self.structured_outputs._backend = "xgrammar"
except VLLMValidationError:
# xgrammar 搞不定(比如 schema 用了它不支持的特性)
# 非 tekken 的 Mistral 分词器,或 guidance 也不支持的特性 → outlines
# 否则 → guidance
...

xgrammar 不是万能的:JSON schema 里的 uniqueItems、patternProperties、数字的 multipleOf 这些特性它不支持(见 has_xgrammar_unsupported_json_features),这时请求会无缝降级到 guidance。这就是为什么 vLLM 文档里说 xgrammar 是”默认但非唯一”的后端。

第二步:异步编译文法——请求先排队,别阻塞别人

文法编译(JSON schema → EBNF → 下推自动机 + 掩码缓存)是有成本的,复杂 schema 可能要几十毫秒。vLLM 的处理方式是异步编译 + 专用等待状态:

  1. 请求进来后,StructuredOutputManager.grammar_init 把编译任务扔进线程池
  2. 请求进入 WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR 状态,暂时不参与调度
  3. 调度器每轮检查:编译好了(Future 完成)就升级为 WAITING,正常排队
1
2
3
4
5
6
# vllm/v1/core/sched/scheduler.py(节选)
if request.status == RequestStatus.WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR:
structured_output_req = request.structured_output_request
if not structured_output_req or structured_output_req.grammar is None:
return False # 还没编译完,继续等
request.status = RequestStatus.WAITING # 编译完成,放行

这就是论文里说的”掩码缓存构建与 prefill 重叠”:你的请求在等编译时,GPU 正在服务别的请求,编译耗时被藏在了调度间隙里。

后端初始化时还会建一个带 LRU 缓存的编译器,同一个 schema 来第二遍直接命中:

1
2
3
4
5
6
7
# vllm/v1/structured_output/backend_xgrammar.py(节选)
self.compiler = xgr.GrammarCompiler(
tokenizer_info,
max_threads=8, # 多线程并行编译
cache_enabled=True,
cache_limit_bytes=vllm.envs.VLLM_XGRAMMAR_CACHE_MB * 1024 * 1024,
)

VLLM_XGRAMMAR_CACHE_MB 默认 512,按注释说大约能装 1000 个 JSON schema。

第三步:每步生成批量填掩码——CPU 线程池并行

到了解码主循环,每一步调度器会为整个 batch 的结构化请求批量生成 bitmask。非投机解码场景下,大 batch(超过 128 个请求)时用线程池并行填:

1
2
3
4
5
# vllm/v1/structured_output/__init__.py(节选)
if len(structured_output_request_ids) > self.fill_bitmask_parallel_threshold:
# 每 16 个请求打一组,丢进线程池并行填掩码
if len(batch) == self.fill_bitmask_parallel_batch_size:
promises.append(self._async_submit_fill_bitmask(batch))

填掩码的底层调用就是 xgrammar 的 fill_next_token_bitmask——查缓存 + 跑那不到 1% 的上下文相关 token,实测单请求单步不到 40 微秒。

投机解码的配合尤其精巧。草稿模型提前猜了 K 个 token,vLLM 需要为每个草稿位置都算一张掩码(万一前几个草稿被拒,后面的位置还得接着约束)。做法是”吃一个、填一张、最后全退回去”:

1
2
3
4
5
6
7
8
9
10
# vllm/v1/structured_output/__init__.py(简化)
for i, token in enumerate(req_tokens): # 遍历草稿 token
self._fill_bitmasks(((grammar, cumulative_index, ...),)) # 先填当前位置的掩码
if advance_grammar and not grammar.is_terminated():
grammar.accept_tokens(req_id, [token]) # "吃掉"草稿 token,状态机前进
state_advancements += 1
cumulative_index += 1
...
if state_advancements > 0:
grammar.rollback(state_advancements) # 模拟完全部退回,深藏功与名

能看到持久化栈在这里发挥了作用:模拟多少步都能一次性全退回去,回滚代价几乎为零,这才敢对每个草稿位置都做一遍前向模拟。

第四步:GPU 上原位应用掩码——一个 Triton kernel 收尾

CPU 填好的 bitmask(int32 位压缩,一行 = 词表/32 个 int32)异步拷到 GPU,然后用一个 Triton kernel 把非法 token 的 logits 原地置为 $-\infty$。这个 kernel 就是从 xgrammar 官方实现改的:

1
2
3
4
5
6
7
8
9
# vllm/v1/worker/gpu/structured_outputs.py(节选,改编自
# xgrammar/python/xgrammar/kernels/apply_token_bitmask_inplace_triton.py)
@triton.jit
def _apply_grammar_bitmask_kernel(logits_ptr, logits_indices_ptr, bitmask_ptr, ...):
packed_bitmask = tl.load(bitmask_ptr + ...)
# 位解压:每个 int32 展开成 32 个 token 的合法性
bitmask = ((packed_bitmask[:, None] >> tl.arange(0, 32)[None, :]) & 1) == 0
# 非法位置写 -inf
tl.store(logits_ptr + ..., -float("inf"), mask=bitmask & ...)

bitmask 的复制走独立的 CUDA stream 异步进行,与主计算流重叠——又是”藏延迟”的老手艺。之后采样器面对的就是一个”非法 token 概率为零”的分布,怎么采都合法。

第五步:接受新 token,状态机前进

采样出结果后,调度器调 accept_tokens 把新 token 喂给匹配器,状态机前进一步;如果状态机拒绝(理论上不可能发生,除非有 bug),会记一条 “Please file an issue” 的错误日志。

整条链路串起来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
请求到达
│ (JSON schema / regex / EBNF / structural tag)
▼
后端选择: auto 优先 xgrammar,失败降级 guidance / outlines
│
▼
异步编译文法 ──► 请求挂起在 WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR
│ (不阻塞其他请求,编译与 GPU 计算重叠)
▼
每步解码:
┌─────────────────────────────────────────────┐
│ CPU: 为整个 batch 填 bitmask │
│ (线程池并行 / 投机解码逐位模拟+回滚) │
│ │ 异步拷贝 │
│ ▼ │
│ GPU: 模型前向 → logits │
│ │ │
│ ▼ │
│ Triton kernel: 非法 logits → -∞ │
│ │ │
│ ▼ │
│ 采样 → accept_token 推进状态机 │
└─────────────────── 循环 ─────────────────────┘
│
▼
输出 100% 符合结构的结果

另外值得一提的是对思考模式(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from openai import OpenAI

client = OpenAI(base_url="http://localhost:8000/v1", api_key="EMPTY")

resp = client.chat.completions.create(
model="Qwen/Qwen2.5-7B-Instruct",
messages=[{"role": "user", "content": "提取:张三,28岁,杭州,电话138xxxx"}],
extra_body={
"structured_outputs": {
"json": {
"type": "object",
"properties": {
"name": {"type": "string"},
"age": {"type": "integer"},
"city": {"type": "string"},
},
"required": ["name", "age", "city"],
}
}
},
)
print(resp.choices[0].message.content)
# {"name": "张三", "age": 28, "city": "杭州"} ← 保证合法,直接 json.loads

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import xgrammar as xgr

# 1. 准备:分词器信息 + 编译器(全局一份,带缓存)
tokenizer_info = xgr.TokenizerInfo.from_huggingface(tokenizer, vocab_size=128256)
compiler = xgr.GrammarCompiler(tokenizer_info, max_threads=8)

# 2. 编译 schema 成自动机(每个请求一次)
ctx = compiler.compile_json_schema('{"type": "object", ...}')
matcher = xgr.GrammarMatcher(ctx)

# 3. 每步解码
bitmask = xgr.allocate_token_bitmask(1, tokenizer_info.vocab_size)
matcher.fill_next_token_bitmask(bitmask) # 生成掩码,<40μs
xgr.apply_token_bitmask_inplace(logits, bitmask) # 应用到 logits
token_id = sample(logits) # 你自己的采样逻辑
matcher.accept_token(token_id) # 状态机前进

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 就是它的全部使命:让大模型说出的每一句”机话”,都符合语法。

参考资料

CATALOG
  1. 1. 正文
    1. 1.1. 约束解码:在采样环节掐断错误
    2. 1.2. 三座大山:约束解码为什么难
      1. 1.2.1. 第一座山:词表太大
      2. 1.2.2. 第二座山:语法状态是”栈”,没法穷举缓存
      3. 1.2.3. 第三座山:token 边界和语法边界对不齐
    3. 1.3. xgrammar 的核心洞察:把词表”三分天下”
    4. 1.4. 自适应存储:160MB 怎么压成 0.46MB
      1. 1.4.1. 再砍一刀:上下文展开(Context Expansion)
    5. 1.5. 持久化执行栈:投机解码的”后悔药”
    6. 1.6. vLLM 是怎么集成 xgrammar 的
      1. 1.6.1. 第一步:后端自动选择——xgrammar 优先,搞不定再摇人
      2. 1.6.2. 第二步:异步编译文法——请求先排队,别阻塞别人
      3. 1.6.3. 第三步:每步生成批量填掩码——CPU 线程池并行
      4. 1.6.4. 第四步:GPU 上原位应用掩码——一个 Triton kernel 收尾
      5. 1.6.5. 第五步:接受新 token,状态机前进
    7. 1.7. 性能数据:到底省了多少
    8. 1.8. 怎么用
    9. 1.9. 尾声:从守门员到动态守门员
    10. 1.10. 参考资料