核心发现
方法论
XGrammar把上下文无关文法编成字节级PDA，并将词表分成可预检的“上下文无关token”和需运行时解释的“上下文相关token”。它先用自适应token mask cache预计算前者，再用上下文扩展（context expansion）缩小后者；运行时通过持久执行栈（persistent execution stack）快速分叉、回滚和合并多条匹配栈，最后与LLM推理引擎重叠执行以隐藏CPU侧开销。
关键结果
- 在Llama-3.1与JSON语法、128k词表设置下，context-dependent tokens只有1134个，且经context expansion后降到120个，减少90%。
- 自适应存储将JSON语法的mask内存从160 MB压到0.46 MB，仅为0.2%；预处理阶段需检查的字符数降到整个词表的30%。
- 端到端评测显示：相对现有方案，CFG逐token延迟最高提升100x；与LLM serving引擎结合后，在H100上对Llama-3.1结构化输出的端到端吞吐最高提升80x。
研究意义
这项工作把“结构正确”从推理后的校验问题，推进为推理时几乎无感的系统能力。对研究界，它证明CFG并不必然意味着高代价，关键在于把词表检查、栈管理和GPU执行做系统级协同；对工业界，它直接降低函数调用、JSON输出、SQL生成、机器人指令等场景的服务成本，使结构化输出更接近普通自由生成的速度。
技术贡献
技术上，XGrammar的贡献不是单点优化，而是一套可组合的执行体系：1）自适应token mask cache把绝大多数token的合法性前移到离线；2）context expansion利用父子规则上下文，提前剪掉大量必错token；3）persistent execution stack用树形共享结构支持O(1)回滚和廉价分叉；4）与LLM引擎的计算重叠把grammar开销隐藏在GPU计算之下。相比传统逐token、逐栈暴力枚举，它显著减少运行时状态空间。
新颖性
其新颖性在于首次将CFG执行显式拆成“上下文无关token+上下文相关token”两类，并围绕这一划分设计缓存、扩展与栈结构。与只做语法约束或简单缓存的方法不同，XGrammar把语法分析、数据结构和推理调度统一起来，形成可落地的高性能结构化生成引擎。
局限性
- 论文主要展示了JSON语法与Llama-3.1上的结果，说明方法很强，但不同DSL、深层递归或高度歧义文法下的收益分布仍需更广泛验证。
- 上下文扩展和缓存预处理会增加离线构建复杂度；对于频繁变化的动态语法或用户自定义grammar，预处理成本与工程集成难度可能上升。
- 文中强调了CPU/GPU重叠与持久栈，但在极端小batch或超低延迟单请求场景下，隐藏开销的空间可能有限。
未来方向
未来可把XGrammar扩展到更多语法族和动态生成任务，例如可编辑DSL、工具链自动补全与多轮Agent规划；还可进一步研究歧义文法的并行消歧、跨请求缓存复用，以及在更大词表和更多模态指令下的通用调度策略。作者也提到希望将其集成到主流开源LLM框架中。
AI 总览摘要
大模型正在从“会聊天”走向“会办事”：函数调用、代码生成、SQL、JSON和机器人指令都要求输出不仅通顺，还必须严格符合结构。但越是通用的结构化约束，越容易让推理变慢。传统约束解码通常要在每个解码步扫描整个词表，再结合上下文无关文法逐项判断合法性；当词表达到Llama-3.1的128k规模时，这种做法会把结构化生成变成明显的系统瓶颈。
XGrammar给出的答案是把“语法检查”工程化拆解。它先把CFG转成字节级PDA，再把token分成两类：大多数只需看栈顶就能判断的上下文无关token，以及少数必须查看完整栈状态的上下文相关token。前者被离线写入自适应token mask cache；后者交给运行时的持久执行栈处理。随后，context expansion进一步利用父级上下文提前排除大量注定失败的token，把需要慢查的部分压到更小。
这套设计的关键不只是快，而是“快得有系统感”。持久栈把不同时间步和分支路径共享成一棵树，支持O(1)回滚与廉价分叉；缓存又采用按节点自适应存储，遇到accept-heavy或reject-heavy场景只存小集合。最后，XGrammar把语法计算与GPU推理重叠起来，让结构约束尽量躲进模型前向传播的空隙里。对JSON这类常见语法，它把context-dependent tokens从1134个降到120个，内存从160 MB压到0.46 MB。
实验结果显示，这些微观优化汇聚成了宏观提升：在CFG逐token延迟上，XGrammar相较现有方案最高快100x；与LLM serving引擎联用后，在H100上对Llama-3.1结构化输出的端到端服务最高快80x。更重要的是，它并没有牺牲CFG的灵活性，仍可支持递归结构、嵌套格式和复杂DSL，这使其比只适合正则表达式的方案更通用。
从更大的视角看，XGrammar把结构化生成从“额外负担”变成“基础能力”。这意味着未来的Agent系统可以更自然地输出可解析、可执行、可回滚的结果，而不必在速度和可靠性之间做痛苦取舍。它也提示一个趋势：下一代LLM系统的竞争，越来越不只在模型参数和算力，还在语法、缓存、栈和GPU调度的协同设计上。
当然，XGrammar也不是终点。它的收益在复杂度、语法类型和请求模式之间如何变化，仍需要更广泛的跨场景验证；动态语法、强歧义语言和超低延迟场景也会提出新的约束。但作为一个把理论、数据结构和系统协同统一起来的方案，XGrammar已经把结构化生成推向了接近“零额外成本”的现实路径。
深度分析
研究背景
LLM应用正从纯文本对话扩展到函数调用、代码生成、调试、SQL构造和机器人控制等场景，结构化输出因此成为核心基础设施。传统约束解码依赖正则表达式或简单规则，表达力有限；CFG则能描述递归嵌套的JSON、SQL和DSL。与之相配套的PDA能够通过栈处理递归，但直接把CFG用于解码会在每一步遍历整个词表、维护多条栈路径，并处理token跨字符边界的问题，因此系统开销很高。
核心问题
核心问题是：如何在保留CFG灵活表达力的同时，把运行时token合法性判定做得足够快。难点来自三方面：词表大（如128k）；栈状态组合无限，难以全缓存；token本身可能跨越语法边界，导致需要在当前规则和父规则间回退检查。若每步都暴力判断，结构化生成会显著拖慢LLM推理。
核心创新
XGrammar的创新可概括为四点。其一是token分解：把合法性只依赖栈顶的token视为上下文无关，提前缓存；其二是context expansion：对每个规则提取“扩展后缀”FSA，用父级上下文过滤更多必错token；其三是persistent execution stack：把多条栈与历史时间步组织成共享树，实现快速分叉和回滚；其四是系统共设计：让grammar计算与GPU前向重叠，减少端到端可见开销。
方法详解
- �� CFG到PDA：将语法规则转成字节级pushdown automata，字符边可跨多个byte，兼容不规则token边界与子UTF-8片段。
- �� 自适应token mask cache：按PDA节点预计算上下文无关token的合法性；运行时只需查缓存并对少量上下文相关token做全栈解释。
- �� 自适应存储：对每个节点在accept-heavy、reject-heavy、近似均衡三种格式中选最省空间者；前两种只存小集合，后者才用bitset。
- �� Algorithm 1：合并多条并行栈的mask时，用集合交并操作在小子集上完成，避免对全词表做重复运算。
- �� Context expansion：Algorithm 2先抽取规则R在父规则中的“可继续匹配后缀”，再构建FSA；若token剩余部分连这些后缀都不可能匹配，就直接剪枝。
- �� Persistent execution stack：把当前步与历史步的多条栈合并为树，栈顶只是树节点指针；回滚只需切换指针，分叉只复制受影响分支。
- �� 计算重叠：将grammar检查与LLM推理并行调度，尽量把mask生成隐藏在GPU计算期间。
实验设计
论文主要在Llama-3.1与JSON grammar上评测，并强调128k词表规模下的运行时压力。指标包括：每token延迟、mask生成时间、context-dependent token数量、预处理字符检查比例、缓存内存占用，以及与LLM serving结合后的端到端吞吐/延迟。文中还展示了并行栈合并和回滚对预处理的作用，并用JSON等递归结构验证CFG场景。
结果分析
最突出的结果是速度与内存同时大幅改善：CFG逐token延迟最高100x加速，端到端结构化服务在H100上最高80x加速。对JSON语法，context-dependent tokens从1134/128k降到120，说明context expansion非常有效；预处理时需检查的字符量降到30%，说明persistent stack显著减少了重复前缀工作。内存方面，从160 MB降到0.46 MB，仅占0.2%。
应用场景
最直接的应用是函数调用与工具调用：模型输出必须精确符合schema，XGrammar可在几乎不拖慢推理的前提下保证格式正确。第二类是代码、SQL与JSON生成：递归结构和嵌套字段正是CFG擅长描述的对象。它还适合机器人控制指令、Agent规划输出、可回滚树搜索和跳转式解码等需要结构正确性的系统。
局限与展望
方法的主要前提是语法可被有效编译为CFG/PDA，且缓存预处理值得投入；如果语法频繁变化或完全在线生成，离线优化收益会受限。对极其歧义、深递归或大量跨规则回跳的语言，context expansion可能仍留下较多上下文相关token。未来需要更系统地评测不同词表、不同batch与不同模型规模下的稳定收益。
通俗解读 非专业人士也能看懂
可以把这篇工作想成“给机器人装了一个既快又严格的质检员”。以前，机器人每说一个词，质检员都要把整本说明书翻一遍，看看这句话会不会违规；说明书越厚，机器人说话就越慢。XGrammar的方法是先把说明书拆成两类：一类是“看一眼门牌号就知道能不能进”的简单规则，提前贴好标签；另一类才是真正麻烦、要进屋仔细检查的规则。这样，大部分情况都不用重新检查。
它还给质检员配了一本“活页笔记本”。当机器人试着说不同的词时，很多词开头都一样，比如 read、ready、reader。以前每次都要从头检查；现在只要检查到相同前缀，就能直接从上次的位置接着看，省去大量重复劳动。再加上它会先根据上下文把明显不合适的词删掉，最后真正需要细查的词就很少了。
更聪明的是，质检工作还能和机器人思考同时进行：机器人在电脑里算答案时，质检员也在旁边快速整理规则。结果就是，既不容易出错，又不会明显变慢。
简单解释 像给14岁少年讲一样
想象你在玩一个超严格的游戏，游戏规则是：你每说一句话，都必须符合某个格式，比如先写名字，再写年龄，再写地点。以前的“检查员”太笨了，每说一个字都要把全部规则从头到尾扫一遍，像老师每次都从第一页翻到最后一页找答案，当然会很慢！
XGrammar做的事，就像给检查员发了一套超聪明的便利贴。哪些内容一眼就能判断对错，先贴好；哪些内容真的需要认真看，再留到最后。这样，绝大多数词根本不用临时现查。遇到像“read、ready、reader”这种前面都一样的词，检查员也不用每次重来，而是从共同部分继续检查，省很多时间。
它还把检查员的记忆做成了“分叉树笔记本”：如果一句话有多个可能走向，就分开记，但大家共用大部分内容，不会重复抄写。这样不光省内存，还能随时回到上一步，特别适合做撤回、改写、树状搜索这类任务。
所以你可以把XGrammar理解成：让大模型既能“说得像样”，又能“按规矩来”，而且还不拖慢速度。对聊天机器人、写代码、发指令、做工具调用，这都很重要——因为现实世界里，光会说还不够，得说得能直接用！
术语表
Context-Free Grammar (上下文无关文法)
一种用规则定义字符串结构的方法，规则可以递归地引用其他规则，所以能描述嵌套格式。技术上，它比正则表达式更适合JSON、SQL和DSL这类复杂结构。
论文用CFG作为结构化生成的核心约束形式。
Pushdown Automaton, PDA (下推自动机)
一种带栈的自动机，专门用来识别CFG生成的语言。栈负责记录嵌套和递归展开过程。
XGrammar把CFG编译成字节级PDA来执行约束解码。
Token Mask (token掩码)
在每个解码步标记哪些token允许生成、哪些必须屏蔽的集合。屏蔽的token logits会被置为-∞。
论文的核心目标是高效生成token mask。
Adaptive Token Mask Cache (自适应token掩码缓存)
按PDA节点预先存储可判定token的合法性，只保留小集合而不是整表。它根据accept-heavy/reject-heavy自动选存储格式。
§3.1是主要加速机制。
Context Expansion (上下文扩展)
利用父规则与可继续匹配的后缀，提前剪掉更多必错token的预处理方法。它减少运行时需要检查的上下文相关token。
§3.2用于把1134个上下文相关token降到120个。
Persistent Execution Stack (持久执行栈)
把多条栈与历史状态组织成共享树的数据结构，支持快速分叉与回滚。它减少重复存储，也让重算公共前缀变得便宜。
§3.3用于加速运行时和预处理阶段的PDA执行。
开放问题 这项研究留下的未解疑问
- 1 不同类型语法的收益边界仍不清楚：例如高度歧义、深递归、动态生成的grammar是否同样能获得接近JSON场景的90%剪枝率与100x加速，需要更系统的跨任务实验。
- 2 当前方法依赖离线构建缓存与上下文扩展；在频繁热更新语法、超低batch或多租户服务中，如何平衡预处理成本、缓存复用与时延稳定性，仍是开放问题。
应用场景
近期应用
Function calling / JSON schema serving
面向工具调用、API参数、结构化问答服务，系统可在生成时直接约束输出格式，减少解析失败和重试。只需提前提供grammar或schema，即可把结构正确性变成推理内生能力。
SQL、代码与DSL生成
适用于需要严格语法的代码补全、SQL拼接和领域专用语言生成。开发者可将语法编译为CFG，让模型输出可直接执行或进一步编译的文本。
远期愿景
Near-zero-overhead structured agents
长期愿景是让Agent在规划、调用工具、回滚与分支搜索时都默认带结构约束，几乎不再为格式检查付出额外代价。若与主流推理框架深度集成，结构化生成可像普通采样一样自然。
原文摘要
The applications of LLM Agents are becoming increasingly complex and diverse, leading to a high demand for structured outputs that can be parsed into code, structured function calls, and embodied agent commands. These developments bring significant demands for structured generation in LLM inference. Context-free grammar is a flexible approach to enable structured generation via constrained decoding. However, executing context-free grammar requires going through several stack states over all tokens in vocabulary during runtime, bringing non-negligible overhead for structured generation. In this paper, we propose XGrammar, a flexible and efficient structure generation engine for large language models. XGrammar accelerates context-free grammar execution by dividing the vocabulary into context-independent tokens that can be prechecked and context-dependent tokens that need to be interpreted during runtime. We further build transformations to expand the grammar context and reduce the number of context-independent tokens. Additionally, we build an efficient persistent stack to accelerate the context-dependent token checks. Finally, we co-design the grammar engine with LLM inference engine to overlap grammar computation with GPU executions. Evaluation results show that XGrammar can achieve up to 100x speedup over existing solutions. Combined with an LLM inference engine, it can generate near-zero overhead structure generation in end-to-end low-LLM serving.