Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
Artificial IntelligenceComputation and LanguageFormal Languages and Automata TheoryMachine Learning
Summary
The authors address the problem of generating correct structured text like code or queries with language models. They note that standard methods check each token locally to keep the ongoing output possibly valid, but this can still lead to dead ends. Their new method uses a lookahead technique based on pushdown automata to estimate if a partial output can eventually form a valid final result, improving pruning during decoding. This approach guarantees syntactically correct outputs and performs better on tasks involving JSON, SQL, and logical formulas. Experiments show that their method produces more valid and higher-quality completions than previous techniques.
Authors
Vincenzo Collura, Karim Tit, Eleonora Giunchiglia, Mike Papadakis, Maxime Cordy
Abstract
Grammar-constrained decoding helps large language models produce syntactically valid structured outputs, such as code, JSON, and SQL. For context-free grammars, many practical decoders enforce local prefix feasibility: each token must keep the current prefix extendable to some valid completion. Yet, under tokenizer-grammar mismatch and finite token budgets, feasible prefixes may still fail to reach acceptance. We propose a lookahead-guided decoding framework for context-free grammars based on pushdown automata. Offline, we compute bounded pushdown summaries with reachability labels and upper-bound distances to acceptance. Online, these estimates guide horizon-aware pruning and beam search. The resulting decoder is syntactically sound: every output is accepted by the target grammar. Experiments on JSON, SQL, and Linear Temporal Logic (LTL) show both consistent syntactic validity and improved completion quality over existing baselines.