Source: XGrammar
Dong et al. (2024, MLSys '25): a grammar engine that makes CFG-constrained decoding near-zero overhead by prechecking context-independent tokens.
Contents
- What: research paper (arXiv:2411.15100, MLSys 2025)
- Author/publisher: Yixin Dong, Charlie F. Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, Tianqi Chen
- Date: November 2024 (v3 May 2025)
- Original: arXiv:2411.15100
Summary
Context-free grammars (needed for JSON’s nesting) are expensive to check against every vocabulary token at every step because the parser carries stack state. XGrammar splits the vocabulary into context-independent tokens, whose validity can be precomputed per grammar position, and context-dependent tokens, which are checked at runtime with a persistent stack. It overlaps grammar work with GPU execution inside the serving engine.
Key claims
- Token partitioning moves most validity checks to preprocessing.
- Grammar transformations shrink the set of tokens that must be checked at runtime.
- A persistent stack speeds up the remaining runtime checks.
- Reported up to 100× speedup over prior solutions and near-zero end-to-end overhead in LLM serving.