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

• URL: http://arxiv.org/abs/2608.28229v1
• Date: Fri, 28 Aug 2026 11:44:53 GMT
• Title: Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
• Abstract summary: We propose a lookahead-guided decoding framework for context-free grammars based on pushdown automata.<n>The resulting decoder is syntactically sound: every output is accepted by the target grammar.
• Score: 18.38520405734125
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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 papers

• Efficient Grammar-Constrained Decoding via Parser Stack Classification [27.415578917916054]
  Grammar-constrained decoding (GCD) can guarantee the syntactic validity of the generated output, by masking out tokens that violate rules specified by a context-free grammar.<n>We propose PSC, a novel grammar-constrained decoding method.<n> PSC can compute the complete mask by checking the stack exactly once per decoding step, with time independent of the vocabulary size.
  arXiv  Detail & Related papers  (2026-08-04T03:26:54Z)
• Weave of Formal Thought [51.56484100374058]
  We introduce Weave of Formal Thought (WoFT), a paradigm uniting rigorous syntactic validation with learned structural representations.<n>We present a latent-variable fine-tuning method training the language model to interleave non-terminal grammar symbols directly into generation.<n>For Python, fine-tuning StarCoder2-3B with our RWS objective reduces per-token cross-entropy by 14.3% relative to a text-only SFT baseline.
  arXiv  Detail & Related papers  (2026-06-24T15:58:11Z)
• Prefix Parsing is Just Parsing [53.010152712125766]
  Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar.<n>We introduce the prefix grammar transformation, an efficient reduction of prefix parsing to ordinary parsing.<n>We also present a strategy-based on algorithmic differentiation-for computing the next-token weight vector.
  arXiv  Detail & Related papers  (2026-04-23T01:20:40Z)
• Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding [0.2864713389096699]
  We study grammar-constrained decoding (GCD) as a coupling between an autoregressive next-token distribution and a reachability over a pushdown system compiled from a context-free grammar (CFG)<n>We define decoding-cost equivalence classes of grammars and prove existence of minimal-SAC representatives within bounded rewrite families.
  arXiv  Detail & Related papers  (2026-03-04T11:49:55Z)
• Token-Oriented Object Notation vs JSON: A Benchmark of Plain and Constrained Decoding Generation [0.0]
  Token-Oriented Object Notation (TOON) aims to replace as a serialization format for passing structured data to LLMs with significantly reduced token usage.<n>To test this, we conducted a benchmark creating several test cases with regard to structural complexity, a validation and comparing plain generation vs structured output.
  arXiv  Detail & Related papers  (2026-02-08T11:58:03Z)
• Are you going to finish that? A Practical Study of the Partial Token Problem [85.49816027251013]
  Language models (LMs) are trained over sequences of tokens, whereas users interact with LMs via text.<n>This mismatch gives rise to the partial token problem, which occurs when a user ends their prompt in the middle of the expected next-token.<n>In this work, we identify three domains where token and "word" boundaries often do not line up.
  arXiv  Detail & Related papers  (2026-01-30T17:47:16Z)
• Correctness-Guaranteed Code Generation via Constrained Decoding [11.531496728670746]
  We present a constrained runtime decoding algorithm for generating semantically correct programs.<n>We show that our method can generate semantically correct programs conforming to any prescribed scripting API.<n>We further show that, with careful design, our semantic guarantees extend to correctness, as validated in the application of generating game mechanics for a roguelike video game.
  arXiv  Detail & Related papers  (2025-08-20T20:48:18Z)
• $\texttt{SEM-CTRL}$: Semantically Controlled Decoding [53.86639808659575]
  $texttSEM-CTRL$ is a unified approach that enforces rich context-sensitive constraints and task- and instance-specific semantics directly on an LLM decoder.<n>texttSEM-CTRL$ allows small pre-trained LLMs to efficiently outperform larger variants and state-of-the-art reasoning models.
  arXiv  Detail & Related papers  (2025-03-03T18:33:46Z)
• Tokenization as Finite-State Transduction [24.19959327497118]
  We introduce a finite-state framework which can efficiently encode all possible tokenizations of a regular language. We show that Byte-Pair. Match (BPE) and MaxPiece (WordPiece) fit within this framework. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern.
  arXiv  Detail & Related papers  (2024-10-21T07:10:07Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
  arXiv  Detail & Related papers  (2023-05-24T11:47:35Z)
• Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
  grammar-constrained decoding (GCD) can be used to control the generation of large language models (LMs) GCD can serve as a unified framework for structured NLP tasks in general. We show that grammar-constrained LMs substantially outperform unconstrained LMs or even beat task-specific finetuned models.
  arXiv  Detail & Related papers  (2023-05-23T11:54:37Z)
• On Parsing as Tagging [66.31276017088477]
  We show how to reduce tetratagging, a state-of-the-art constituency tagger, to shift--reduce parsing. We empirically evaluate our taxonomy of tagging pipelines with different choices of linearizers, learners, and decoders.
  arXiv  Detail & Related papers  (2022-11-14T13:37:07Z)
• Lexically-constrained Text Generation through Commonsense Knowledge Extraction and Injection [62.071938098215085]
  We focus on the Commongen benchmark, wherein the aim is to generate a plausible sentence for a given set of input concepts. We propose strategies for enhancing the semantic correctness of the generated text.
  arXiv  Detail & Related papers  (2020-12-19T23:23:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.