**SynCode: LLM Generation with Grammar Augmentation** This paper introduces SynCode, a novel framework for generating syntactically correct output using large language models (LLMs). SynCode addresses the challenge of ensuring that LLM outputs adhere to specific formats, such as JSON, YAML, or code in programming languages, by leveraging context-free grammars (CFGs). The framework ensures soundness and completeness with respect to the CFG, retaining valid tokens while filtering out invalid ones. SynCode uses an offline-constructed DFA mask store, derived from the DFA of the language's grammar, to efficiently generate syntactically correct output. The framework integrates seamlessly with any language defined by a CFG, as demonstrated through experiments with JSON, Python, and Go. Experiments show that SynCode eliminates all syntax errors in JSON generation and significantly reduces 96.07% of syntax errors in Python and Go code, showcasing its effectiveness in enhancing syntactical precision in LLM generation. **Contributions:** - A parsing-based technique for efficient and general syntactic decoding of LLMs. - Implementation of SynCode, a scalable and general framework that can work with any formal language defined by a CFG. - Extensive evaluation of SynCode's performance in generating syntactically correct output for JSON and Python/Go. **Background:** - Overview of LLMs and formal language grammar. - Notation and definitions for language models and formal language syntax. - Detailed description of the SynCode algorithm, including parsing partial output, computing accept sequences, and using the DFA mask store. **Key Insights:** - Token misalignment is a significant challenge in syntactic generation, which SynCode addresses by providing a provably sound and complete approach. - The DFA mask store allows for efficient computation of syntactically valid tokens during inference, leveraging parallelization on modern hardware. - SynCode's generality and efficiency are demonstrated through its integration with various decoding algorithms and its ability to handle large grammars.**SynCode: LLM Generation with Grammar Augmentation** This paper introduces SynCode, a novel framework for generating syntactically correct output using large language models (LLMs). SynCode addresses the challenge of ensuring that LLM outputs adhere to specific formats, such as JSON, YAML, or code in programming languages, by leveraging context-free grammars (CFGs). The framework ensures soundness and completeness with respect to the CFG, retaining valid tokens while filtering out invalid ones. SynCode uses an offline-constructed DFA mask store, derived from the DFA of the language's grammar, to efficiently generate syntactically correct output. The framework integrates seamlessly with any language defined by a CFG, as demonstrated through experiments with JSON, Python, and Go. Experiments show that SynCode eliminates all syntax errors in JSON generation and significantly reduces 96.07% of syntax errors in Python and Go code, showcasing its effectiveness in enhancing syntactical precision in LLM generation. **Contributions:** - A parsing-based technique for efficient and general syntactic decoding of LLMs. - Implementation of SynCode, a scalable and general framework that can work with any formal language defined by a CFG. - Extensive evaluation of SynCode's performance in generating syntactically correct output for JSON and Python/Go. **Background:** - Overview of LLMs and formal language grammar. - Notation and definitions for language models and formal language syntax. - Detailed description of the SynCode algorithm, including parsing partial output, computing accept sequences, and using the DFA mask store. **Key Insights:** - Token misalignment is a significant challenge in syntactic generation, which SynCode addresses by providing a provably sound and complete approach. - The DFA mask store allows for efficient computation of syntactically valid tokens during inference, leveraging parallelization on modern hardware. - SynCode's generality and efficiency are demonstrated through its integration with various decoding algorithms and its ability to handle large grammars.