# Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance

arXiv: https://arxiv.org/abs/2608.28229 · HTML: https://mlsanity.com/paper/2608.28229/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 28 references that are in the map.
- First posted on arXiv 28 Aug 2026.

## Builds on (most cited first, 14 of 14)

- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [Data-Efficient Learning of Natural Language to Linear Temporal Logic Translators for Robot Task Specification](https://mlsanity.com/paper/2303.08006/) (2023)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [Constrained Decoding of Diffusion LLMs with Context-Free Grammars](https://mlsanity.com/paper/2508.10111/) (2025)
- [Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation](https://mlsanity.com/paper/2506.03887/) (2025)
- [Correctness-Guaranteed Code Generation via Constrained Decoding](https://mlsanity.com/paper/2508.15866/) (2025)
- [ABS: Enforcing Constraint Satisfaction On Generated Sequences Via Automata-Guided Beam Search](https://mlsanity.com/paper/2506.09701/) (2025)
- [Hidden Biases in Conditioning Autoregressive Models](https://mlsanity.com/paper/2604.07855/) (2026)
- [TruncProof: A Guardrail for LLM-based JSON Generation under Token-Length Constraints](https://mlsanity.com/paper/2605.13076/) (2026)

## Built on by (most cited first, 1 of 1)

- [Structural Automata for Neural Semantic Parsing](https://mlsanity.com/paper/2610.13896/) (2026)

## Abstract (arXiv)

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.