# SynCode: LLM Generation with Grammar Augmentation

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

## Key facts

- Cited by 69 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 51 references that are in the map.
- First posted on arXiv 3 Mar 2024.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [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)
- [WizardLM: Empowering large pre-trained language models to follow complex instructions](https://mlsanity.com/paper/2304.12244/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [WizardCoder: Empowering Code Large Language Models with Evol-Instruct](https://mlsanity.com/paper/2306.08568/) (2023)
- [Meta-Learning for Semi-Supervised Few-Shot Classification](https://mlsanity.com/paper/1803.00676/) (2018)
- [LeanDojo: Theorem Proving with Retrieval-Augmented Language Models](https://mlsanity.com/paper/2306.15626/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Autoformalization with Large Language Models](https://mlsanity.com/paper/2205.12615/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [Multi-lingual Evaluation of Code Generation Models](https://mlsanity.com/paper/2210.14868/) (2022)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [Copiloting the Copilots: Fusing Large Language Models with Completion Engines for Automated Program Repair](https://mlsanity.com/paper/2309.00608/) (2023)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [Guiding Language Models of Code with Global Context using Monitors](https://mlsanity.com/paper/2306.10763/) (2023)
- [Pushdown Layers: Encoding Recursive Structure in Transformer Language Models](https://mlsanity.com/paper/2310.19089/) (2023)
- [Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars](https://mlsanity.com/paper/2402.17988/) (2024)

## Built on by (most cited first, 30 of 69)

- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [CoRNStack: High-Quality Contrastive Data for Better Code Retrieval and Reranking](https://mlsanity.com/paper/2412.01007/) (2024)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [ProofBridge: Auto-Formalization of Natural Language Proofs in Lean via Joint Embeddings](https://mlsanity.com/paper/2510.15681/) (2025)
- [CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis](https://mlsanity.com/paper/2503.23145/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [Constrained Decoding of Diffusion LLMs with Context-Free Grammars](https://mlsanity.com/paper/2508.10111/) (2025)
- [On the Query Complexity of Verifier-Assisted Language Generation](https://mlsanity.com/paper/2502.12123/) (2025)
- [Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation](https://mlsanity.com/paper/2506.03887/) (2025)
- [Is The Watermarking Of LLM-Generated Code Robust?](https://mlsanity.com/paper/2403.17983/) (2024)
- [Towards Formal Verification of LLM-Generated Code from Natural Language Prompts](https://mlsanity.com/paper/2507.13290/) (2025)
- [SEVerA: Verified Synthesis of Self-Evolving Agents](https://mlsanity.com/paper/2603.25111/) (2026)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Automated User Story Generation with Test Case Specification Using Large Language Model](https://mlsanity.com/paper/2404.01558/) (2024)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [On the Power of (Approximate) Reward Models for Inference-Time Scaling](https://mlsanity.com/paper/2602.01381/) (2026)
- [The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding](https://mlsanity.com/paper/2603.03305/) (2026)
- [Using a Feedback Loop for LLM-based Infrastructure as Code Generation](https://mlsanity.com/paper/2411.19043/) (2024)
- [RefineStat: Efficient Exploration for Probabilistic Program Synthesis](https://mlsanity.com/paper/2509.01082/) (2025)
- [Multi-Agent Code-Orchestrated Generation for Reliable Infrastructure-as-Code](https://mlsanity.com/paper/2510.03902/) (2025)
- [TerraFormer: Automated Infrastructure-as-Code with LLMs Fine-Tuned via Policy-Guided Verifier Feedback](https://mlsanity.com/paper/2601.08734/) (2026)
- [Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata](https://mlsanity.com/paper/2607.07026/) (2026)
- [Syntactic Control of Language Models by Posterior Inference](https://mlsanity.com/paper/2506.07154/) (2025)
- [UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8](https://mlsanity.com/paper/2511.05578/) (2025)
- [Semantic Layers for Reliable LLM-Powered Data Analytics: A Paired Benchmark of Accuracy and Hallucination Across Three Frontier Models](https://mlsanity.com/paper/2604.25149/) (2026)
- [Opponent Shaping in LLM Agents](https://mlsanity.com/paper/2510.08255/) (2025)
- [TokDrift: When LLM Speaks in Subwords but Code Speaks in Grammar](https://mlsanity.com/paper/2510.14972/) (2025)
- [Cybersecurity is the True Frontier for Generative AI Success or Failure](https://mlsanity.com/paper/2606.28929/) (2026)
- [Toward Automated and Trustworthy Scientific Analysis and Visualization with LLM-Generated Code](https://mlsanity.com/paper/2511.21920/) (2025)
- [Bootstrapping Fuzzers for Compilers of Low-Resource Language Dialects Using Language Models](https://mlsanity.com/paper/2512.05887/) (2025)

## Abstract (arXiv)

LLMs are widely used in complex AI applications. These applications underscore the need for LLM outputs to adhere to a specific format, for their integration with other components in the systems. Typically the format rules e.g., for data serialization formats such as JSON, YAML, or Code in Programming Language are expressed as context-free grammar (CFG). Due to the hallucinations and unreliability of LLMs, instructing LLMs to adhere to specified syntax becomes an increasingly important challenge. We present SynCode, a novel framework for efficient and general syntactical decoding with LLMs, to address this challenge. SynCode ensures soundness and completeness with respect to the CFG of a formal language, effectively retaining valid tokens while filtering out invalid ones. SynCode uses an offline-constructed, efficient lookup table, the DFA mask store, derived from the DFA of the language's grammar for efficient generation. SynCode seamlessly integrates with any language defined by CFG, as evidenced by experiments focusing on generating JSON, Python, and Go outputs. Our experiments evaluating the effectiveness of SynCode for JSON generation demonstrate that SynCode eliminates all syntax errors and significantly outperforms state-of-the-art baselines. Furthermore, our results underscore how SynCode significantly reduces 96.07% of syntax errors in generated Python and Go code, showcasing its substantial impact on enhancing syntactical precision in LLM generation. Our code is available at https://github.com/uiuc-focal-lab/syncode