SwiftGram: Dynamic Lexical Forking for Precise and Efficient Grammar-Constrained Decoding

Abstract

Large Language Models (LLMs) must strictly adhere to grammatical constraints for reliable structured generation in agentic workflows, code synthesis, and domain-specific language (DSL) generation. Grammar-Constrained Decoding (GCD) enforces this by masking out tokens incompatible with the target grammar at each decoding step, and has been adopted as a core module in mainstream inference engines such as vLLM. However, existing GCD methods exhibit precision defects under grammars with overlapping terminal definitions. The misalignment between LLM tokens and grammar terminals induces terminal ambiguity, where a token admits multiple plausible terminal interpretations. Existing methods handle this imprecisely, causing both false acceptance and false rejection, while incurring high computational overhead. We propose SwiftGram, a GCD framework that incorporates dynamic lexical forking for precise token masking. By forking only at detected ambiguity boundaries, SwiftGram preserves all admissible terminal interpretations while suppressing spurious ones. It builds on Generalized LR (GLR) parsing with the Graph-Structured Stack (GSS) for compact multi-branch parsing, together with adjacency pruning and terminal tries to reduce online overhead. Experiments show that SwiftGram achieves near-zero grammar violations and no observed false rejection, whereas strong baselines remain prone to masking errors. SwiftGram improves effective throughput by up to 14.7% over the strongest baseline under rejection sampling, and achieves a 5.9× average speedup in per-step mask construction under mask-before-selection.