# Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 68 references that are in the map.
- First posted on arXiv 20 Jul 2026.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence](https://mlsanity.com/paper/2606.19348/) (2026)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [KernelBench: Can LLMs Write Efficient GPU Kernels?](https://mlsanity.com/paper/2502.10517/) (2025)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Is Self-Repair a Silver Bullet for Code Generation?](https://mlsanity.com/paper/2306.09896/) (2023)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [We Have a Package for You! A Comprehensive Analysis of Package Hallucinations by Code Generating LLMs](https://mlsanity.com/paper/2406.10279/) (2024)
- [When Language Model Meets Private Library](https://mlsanity.com/paper/2210.17236/) (2022)
- [Knowledge Transfer from High-Resource to Low-Resource Programming Languages for Code LLMs](https://mlsanity.com/paper/2308.09895/) (2023)
- [TileLang: A Composable Tiled Programming Model for AI Systems](https://mlsanity.com/paper/2504.17577/) (2025)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [CodeHalu: Investigating Code Hallucinations in LLMs via Execution-based Verification](https://mlsanity.com/paper/2405.00253/) (2024)
- [IterGen: Iterative Semantic-aware Structured LLM Generation with Backtracking](https://mlsanity.com/paper/2410.07295/) (2024)
- [babble: Learning Better Abstractions with E-Graphs and Anti-Unification](https://mlsanity.com/paper/2212.04596/) (2022)
- [Programming Protocol-Independent Packet Processors](https://mlsanity.com/paper/1312.1719/) (2013)
- [ChopChop: a Programmable Framework for Semantically Constraining the Output of Language Models](https://mlsanity.com/paper/2509.00360/) (2025)
- [Hazelnut: A Bidirectionally Typed Structure Editor Calculus](https://mlsanity.com/paper/1607.04180/) (2016)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Correctness-Guaranteed Code Generation via Constrained Decoding](https://mlsanity.com/paper/2508.15866/) (2025)
- [Learning Highly Recursive Input Grammars](https://mlsanity.com/paper/2108.13340/) (2021)

## Abstract (arXiv)

Large language models now write a growing share of the world's code, increasingly inside agents and serving systems that compile, execute, or dispatch generated code without line-by-line review. This works well for mainstream languages but remains brittle for low-resource programming surfaces such as domain-specific languages, custom library APIs, and command-line tools. Even under grammar-constrained decoding, a model can still produce references invalid in the current environment: a buffer never declared, a column absent from the schema, a function the library does not provide, or an unsupported CLI option. This paper introduces decode-time grammars: grammar fragments instantiated during generation from a runtime environment Gamma. A region-specific policy selects a fragment for each hole, and a tightening operator replaces open reference positions with Gamma-typed slots whose candidates are exactly the names, fields, APIs, or options available at that point. Newly generated declarations enter Gamma before later regions are decoded, so the constraining grammar can depend on the prefix already generated. This ensures not only grammatical correctness but also semantic correctness, by preventing references to undefined symbols. We formalize grammar fragments as environment-indexed grammars ordered by refinement, prove No-Ghost soundness for Gamma-slotted fragments, show that refinement preserves this support-set guarantee, and characterize the boundary of mask-enforceable properties. We implement the approach in gproj with offline grammar induction and online policy resolution. Across TileLang, SQL, and P4, with models from 0.6B to 236B parameters, gproj eliminates ghost references by construction at moderate overhead over standard constrained decoding.