WGRAMMAR: Leverage Prior Knowledge to Accelerate Structured Decoding
WGRAMMAR precompiles static structures and uses FSMs, achieving 250× speedup in constrained decoding.
Key Findings
Methodology
WGRAMMAR employs a constraint decomposition strategy, precompiling static output structures offline and instantiating dynamic parameters at runtime via grammar snippets. It replaces pushdown automata with a compositional set of operators based on finite state machines (FSMs), leveraging domain knowledge to simplify grammar design. The system integrates offline template construction, online request-specific instantiation, and global mask caching, optimizing GPU mask creation and state transitions. This approach reduces latency significantly, enabling real-time structured decoding for large language models. The core components include grammar templates, operator composition, and cache mechanisms, which collectively streamline the decoding pipeline.
Key Results
- In multiple real-world tasks, WGRAMMAR reduces the time to first token (TTFT) by up to 250× compared to XGrammar (e.g., from 120,234ms to 10.93ms in outline tasks). It also improves per-token decoding time (TPOT) by 2.33×. Across benchmarks, the system maintains high accuracy while drastically lowering latency, enabling near-instantaneous output generation.
- Experimental evaluations on datasets like Outlines, Reference Lookup, and JSON schema adherence demonstrate consistent speedups. For instance, in JSON schema tasks, TTFT drops from over 6 seconds to under 2 seconds, with a corresponding TPOT reduction from 20ms to under 1ms.
- Ablation studies confirm that offline template precompilation and FSM-based state tracking are critical for performance gains. The system scales well with complex templates and large vocabularies, outperforming prior art substantially.
Significance
This work addresses the longstanding bottleneck in constrained decoding—balancing expressive power with efficiency. By leveraging prior knowledge and constraint decomposition, WGRAMMAR offers a scalable, fast, and flexible solution suitable for industrial applications requiring structured outputs. Its innovations pave the way for deploying large language models in real-time, domain-specific scenarios such as automated content creation, semantic parsing, and code synthesis, where latency is critical. The approach also opens avenues for further research into adaptive templates and multi-modal structured decoding.
Technical Contribution
The main technical contributions include the constraint decomposition framework, which separates static and dynamic parts, and the replacement of pushdown automata with FSMs, reducing transition latency. The system's offline template precompilation minimizes runtime overhead, while global mask caching accelerates GPU computations. Operator composition techniques translate regex patterns into structured control flows, enabling efficient, flexible decoding. These innovations collectively push the performance boundary of CFG-based constrained decoding, offering both theoretical guarantees and practical speedups.
Novelty
This is the first work to combine offline static structure precompilation with FSM-based runtime instantiation for constrained decoding. Unlike traditional CFG or PDA approaches, WGRAMMAR’s use of domain knowledge and grammar snippets achieves unprecedented speed, especially in large-scale, real-time scenarios. Its operator-based composition and cache mechanisms represent a new paradigm in structured decoding, bridging the gap between expressiveness and efficiency.
Limitations
- The approach relies heavily on predefined templates and prior knowledge, limiting flexibility in highly dynamic or unpredictable output formats. Frequent template updates can incur overhead.
- FSMs may struggle with deeply nested or highly recursive structures, potentially affecting generalization in complex tasks.
- The system’s efficiency gains depend on the quality of offline templates; poorly designed templates may reduce performance benefits.
Future Work
未来将探索自适应模板更新机制，支持动态结构定义；结合深度学习优化Operator组合策略，增强复杂任务的适应性；扩展多模态场景支持，推动跨领域结构化生成技术的发展。
AI Executive Summary
Structured decoding is essential for ensuring large language models produce outputs in precise formats such as JSON or HTML, especially in downstream applications like code generation or semantic parsing.传统方法依赖推导自动机（PDA）和动态掩码，导致状态切换频繁，GPU端掩码生成耗时长，限制了实时应用的性能。WGRAMMAR提出一种创新方案，通过将输出约束分解为静态和动态两部分，利用离线预编译模板和运行时实例化的语法片段，有效降低了状态转移和掩码生成的延迟。核心技术包括用有限状态机（FSM）替代推导自动机，结合域知识简化语法设计，以及全局掩码缓存技术，极大提升了结构化解码的速度。在多个真实场景和公开基准测试中，WGRAMMAR实现了最高250倍的速度提升，显著缩短了首次生成时间（TTFT）和每词生成时间（TPOT），满足工业级实时需求。这一突破不仅推动了结构化解码的性能极限，也为未来定制化、领域特定的生成任务提供了新思路。未来将关注模板自适应更新、多模态支持及复杂结构的泛化能力，期待在内容生成、智能问答、代码自动化等领域引发深远变革。
Deep Analysis
Background
近年来，随着大模型在自然语言处理中的快速发展，结构化解码成为确保输出符合特定格式的关键技术。早期方法如CFG和PDA支持有限的表达能力，难以应对复杂场景中的高性能需求。XGrammar等系统引入状态机优化，但在大规模模板和复杂结构下仍存在延迟瓶颈。随着应用场景不断扩展，研究逐渐转向结合域知识的定制化方案，以提升效率和适应性。当前，CFG支持的解码技术在工业界得到广泛应用，但在复杂嵌套和高吞吐量场景中仍面临性能挑战。
Core Problem
现有结构化解码系统主要依赖推导自动机（PDA）和GPU端掩码，导致状态切换频繁，GPU掩码生成耗时长，整体延迟高。尤其在大规模模板和复杂结构中，解码速度难以满足实时应用需求。如何在保证表达能力的同时，降低状态转移和掩码计算成本，成为亟需解决的核心难题。传统方法在处理复杂结构时，状态机的复杂度指数级增长，严重制约了模型的实际部署。
Innovation
WGRAMMAR的创新点在于：1）将静态结构预编译离线，动态参数在运行时实例化，减少实时计算；2）采用有限状态机（FSM）替代推导自动机，降低状态切换延迟；3）引入域知识和语法片段重用，提升模板复用率；4）利用全局掩码缓存，减少GPU端掩码生成时间。这些创新结合，极大提升了结构化解码的速度和效率，突破了传统CFG方法的性能瓶颈。系统设计兼顾通用性与效率，支持多样化任务需求，为工业应用提供了可扩展的解决方案。
Methodology
- �� 离线模板构建：用户定义结构模板，利用EBNF语法预编译成结构工厂，存储常用结构和参数映射。• 结构实例化：请求到达时，结合模板和参数动态生成具体结构，构建对应的状态机。• Operator组合：将正则表达式转化为Wait/Write操作，支持条件判断和循环控制，确保结构符合预定义规则。• 状态追踪：通过FSM实时更新状态，限制下一步可能的输出，避免无效路径。• GPU掩码生成：利用全局缓存快速生成GPU端掩码，减少重复计算。• 性能优化：减少状态切换，缓存重复计算结果，提升整体解码速度。
Experiments
在多个任务（如HTML摘要、JSON引用匹配）和公开基准（Outlines、XGrammar）上，评估TTFT和TPOT性能。采用NVIDIA A100硬件，比较不同方法的速度提升。消融实验验证离线模板和FSM的关键作用，结果显示WGRAMMAR在TTFT上比XGrammar快250倍，TPOT提升2.33倍。不同结构复杂度和模板变化的测试也验证了其鲁棒性。实验还包括多任务、多场景的性能表现，确保系统的广泛适用性。
Results
WGRAMMAR在所有测试中均表现出极大优势，TTFT从120秒降至10毫秒，TPOT从11毫秒降至0.5毫秒。与传统CFG方法相比，速度提升超过200倍，满足实时应用需求。消融分析显示，离线预编译和FSM的结合是性能提升的核心。多任务、多场景验证了其稳定性和适应性，特别在复杂结构和大规模模板下表现优异。
Applications
该技术适用于内容自动生成、智能问答、代码自动化等多种场景，尤其在对输出格式要求严格、实时性高的工业应用中具有广泛潜力。未来可结合多模态信息，支持更复杂的结构化输出，推动自动内容创作的智能化发展。
Limitations & Outlook
目前方法依赖预定义模板，难以应对高度动态或未预料的结构变化。模板频繁更新会带来维护成本。FSM在极端复杂或深层嵌套结构中可能表现不足，影响泛化能力。未来需探索自适应模板和更强表达能力的模型，以应对多变场景。
Plain Language Accessible to non-experts
想象你在厨房做饭。每次做菜都需要按照食谱，提前准备好所有食材和步骤。WGRAMMAR就像提前把常用的菜谱整理成模板，遇到新菜时，只需根据食材参数快速组合出完整的做法，而不用每次都从零开始设计。这样，做菜的速度就快多了，也更容易保证菜的味道一致。它还用一种特殊的记忆工具，记住了每个步骤和食材的关系，避免重复计算。这样一来，无论是做简单的快餐，还是复杂的宴席，都能快速完成，效率大大提升。
ELI14 Explained like you're 14
想象你在玩拼图游戏。每次拼图都要找合适的块，放到正确的位置。有些拼图有固定的图案，比如一只猫或一辆车，你只要知道这个图案的基本形状，就可以提前准备好拼图块。WGRAMMAR就像这样，把常见的拼图块提前整理好，遇到类似的拼图时，只需要快速组合，不用每次都从零拼起。它还用一种聪明的记忆方法，记住哪些块可以放在哪些位置，避免重复试错。这样，无论拼多复杂的图案，都能更快完成，节省时间。
Abstract
Structured decoding enables large language models (LLMs) to generate outputs in formats required by downstream systems, such as HTML or JSON. However, existing methods suffer from efficiency bottlenecks due to grammar compilation, state tracking, and mask creation. We observe that many real-world tasks embed strong prior knowledge about output structure. Leveraging this, we propose a decomposition of constraints into static and dynamic components -- precompiling static structures offline and instantiating dynamic arguments at runtime using grammar snippets. Instead of relying on pushdown automata, we employ a compositional set of operators to model regular formats, achieving lower transition latency. We introduce wgrammar, a lightweight decoding engine that integrates domain-aware simplification, constraint decomposition, and mask caching, achieving up to 250x speedup over existing systems. wgrammar's source code is publicly available at https://github.com/wrran/wgrammar.