Flexible and Efficient Grammar-Constrained Decoding

2025/02/07 by Kanghee Park, Park, Kanghee, Timothy Zhou +3 · 14 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #Algorithms and Data Compression #Natural Language Processing Techniques

paper · pdf · doi:10.48550/arxiv.2502.05111

Abstract

Large Language Models (LLMs) are often asked to generate structured outputs that obey precise syntactic rules, such as code snippets or formatted data. Grammar-constrained decoding (GCD) can guarantee that LLM outputs matches such rules by masking out tokens that will provably lead to outputs that do not belong to a specified context-free grammar (CFG). To guarantee soundness, GCD algorithms have to compute how a given LLM subword tokenizer can align with the tokens used by a given context-free grammar and compute token masks based on this information. Doing so efficiently is challenging and existing GCD algorithms require tens of minutes to preprocess common grammars. We present a new GCD algorithm together with an implementation that offers 17.71x faster offline preprocessing than existing approaches while preserving state-of-the-art efficiency in online mask computation.

Cited by

• Imprompt: A Language Framework for Prompt Programming
• Bootstrapping Fuzzers for Compilers of Low-Resource Language Dialects Using Language Models
• Orthographic Constraint Satisfaction and Human Difficulty Alignment in Large Language Models
• Grounded Misunderstandings in Asymmetric Dialogue: A Perspectivist Annotation Scheme for MapTask
• Position: Vibe Coding Needs Vibe Reasoning: Improving Vibe Coding with Formal Verification
• AdapTrack: Constrained Decoding without Distorting LLM's Output Intent
• ToolPRM: Fine-Grained Inference Scaling of Structured Outputs for Function Calling
• Constrained Adaptive Rejection Sampling
• Play by the Type Rules: Inferring Constraints for LLM Functions in Declarative Programs
• Specification-Guided Synthesis of Deadlock-Free Communication Protocol Refinements with Large Language Models
• XML Prompting as Grammar-Constrained Interaction: Fixed-Point Semantics, Convergence Guarantees, and Human-AI Protocols
• ChopChop: a Programmable Framework for Semantically Constraining the Output of Language Models
• A DbC Inspired Neurosymbolic Layer for Trustworthy Agent Design
• Continuous Diffusion Models Can Obey Formal Syntax

Related

• Grammar-Aligned Decoding
• Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning
• Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation
• Using Grammar Masking to Ensure Syntactic Validity in LLM-based Modeling Tasks
• WGRAMMAR: Leverage Prior Knowledge to Accelerate Structured Decoding