Tutorials
Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
arXiv:2608.28229v1 Announce Type: cross Abstract: Grammar-constrained decoding helps large language models produce syntactically valid structured outputs, such as code, JSON, and SQL. For context-free
arXiv:2608.28229v1 Announce Type: cross 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.
Related
- Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms
- Interpretable Stylistic Variation in Human and LLM Writing Across Genres, Models, and Decoding Strategies
- Deep networks learn to parse uniform-depth context-free languages from local statistics
Source: arXiv cs.CL | 2026-08-31