# Accelerating Constrained Decoding with Token Space Compression

arXiv: https://arxiv.org/abs/2605.29986 · HTML: https://mlsanity.com/paper/2605.29986/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 13 of 13)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Benchmarking on HumanEval-X](https://mlsanity.com/paper/2303.17568/) (2023)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [StructEval: Benchmarking LLMs' Capabilities to Generate Structural Outputs](https://mlsanity.com/paper/2505.20139/) (2025)
- [Procedural Environment Generation for Tool-Use Agents](https://mlsanity.com/paper/2506.11045/) (2025)
- [Leveraging Code to Improve In-context Learning for Semantic Parsing](https://mlsanity.com/paper/2311.09519/) (2023)
- [XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs](https://mlsanity.com/paper/2601.04426/) (2026)

## Abstract (arXiv)

To guarantee that an LLM's outputs conform to a specified structure, context-free grammar (CFG) decoding engines force the selection of next tokens to produce strings that conform to a given CFG. Current CFG-constrained decoding engines are highly optimized, but still suffer from the inherent costs arising from their massive per-step search space---i.e. the entire token vocabulary. This results in intractably high overhead for more complex CFGs, which is precisely the situation where CFG engines are most useful. In this paper, we introduce CFGzip, an offline technique for compressing the token search space, which massively reduces CFG engine overhead. In experiments, we report latency reduction of up to 75x during batched inference, cutting overhead down to ~1.2-2x on the hardest grammars: with CFGzip, constrained decoding is now possible at scale for complex CFGs