mlsanityData to 14 Oct 2026

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

arXiv 2608.28229 ↗First posted 28 Aug 2026cs.AI cs.CL cs.FLcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

14 of 28 references.

References · 14

  1. 2018Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Taskcited by 1,139
  2. 2024Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generationcited by 101
  3. 2024SynCode: LLM Generation with Grammar Augmentationcited by 69
  4. 2023Tractable Control for Autoregressive Language Generationcited by 65
  5. 2025Flexible and Efficient Grammar-Constrained Decodingcited by 43
  6. 2023Data-Efficient Learning of Natural Language to Linear Temporal Logic Translators for Robot Task Specificationcited by 38
  7. 2025Type-Constrained Code Generation with Language Modelscited by 35
  8. 2025Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Samplingcited by 21
  9. 2025Constrained Decoding of Diffusion LLMs with Context-Free Grammarscited by 14
  10. 2025Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generationcited by 11
  11. 2025Correctness-Guaranteed Code Generation via Constrained Decodingcited by 7
  12. 2025ABS: Enforcing Constraint Satisfaction On Generated Sequences Via Automata-Guided Beam Searchcited by 3
2 more
  1. 2026Hidden Biases in Conditioning Autoregressive Modelscited by 1
  2. 2026TruncProof: A Guardrail for LLM-based JSON Generation under Token-Length Constraintscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Structural Automata for Neural Semantic Parsingcited by 0