Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding

• URL: http://arxiv.org/abs/2603.05540v1
• Date: Wed, 04 Mar 2026 11:49:55 GMT
• Title: Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding
• Abstract summary: 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.
• Score: 0.2864713389096699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study grammar-constrained decoding (GCD) as a coupling between an autoregressive next-token distribution and a reachability oracle over a pushdown system compiled from a context-free grammar (CFG). We prove an oracle invariance theorem: language-equivalent grammars induce identical admissible next-token sets for every prefix, hence identical logit masks, yet can yield provably different compiled state spaces and online ambiguity costs. We give exact control-state blowup counts for the canonical $a^n b^n$ language under redundant nonterminal delegation, and introduce a left-to-right structural ambiguity cost (SAC) measuring incremental packed-parse-forest growth per token. For two equivalent grammars over all finite strings, SAC is $O(1)$ per token under right-recursion but $Θ(t^2)$ per token and $Θ(n^3)$ cumulatively under concatenation. We establish engine-independent lower bounds: any sound, retrieval-efficient, parse-preserving online masking engine must incur $Ω(t^2)$ work per token on a specific constant-size CFG family, unconditionally within this model. We define decoding-cost equivalence classes of grammars and prove existence of minimal-SAC representatives within bounded rewrite families. Finally, we characterize the true conditional sampler via a Doob $h$-transform and derive sharp one-step KL and total-variation distortion bounds for hard-masked decoding in terms of survival-probability spread among admissible next tokens. We integrate these results with Transformer and Mixture-of-Experts architectures, derive latency envelopes in terms of vocabulary size, active state sets, and beam width, and connect SAC to instrumentation-based predictive performance models and automated grammar optimization.

Related papers

• The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding [30.042720796822085]
  Grammar Constrained Decoding (GCD) forces Language Models (LMs) to produce syntactically valid outputs by masking out non-conforming tokens at each step.<n>Online sampling restores this distribution, but it requires computationally expensive iterative resampling.<n>We propose a lightweight, offline-trained logit correction conditioned on this syntactic and lexical state together with candidate next tokens.
  arXiv  Detail & Related papers  (2026-08-10T18:52:43Z)
• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
  arXiv  Detail & Related papers  (2026-08-05T17:51:25Z)
• GRID: Grammar-Railed Decoding for Enterprise SQL Generation [0.0]
  We present GRID (Grammar-Railed Decoding), a grammar-constrained decoding engine.<n>It uses advanced LALR(1) itself as a viable oracle.<n>Four guarantees (soundness, completeness, termination, and near-constant per-token cost) are stated with explicit preconditions.
  arXiv  Detail & Related papers  (2026-07-11T19:25:23Z)
• 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)
• Adaptation to Intrinsic Dependence in Diffusion Language Models [5.185131234265025]
  Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive (AR) approaches.<n>We introduce a distribution-agnostic unmasking schedule for DLMs that adapts to the (unknown) dependence structure of the target data distribution.<n>Our results significantly improve upon prior convergence theories and yield substantial sampling acceleration for low-complexity distributions.
  arXiv  Detail & Related papers  (2026-02-23T18:41:34Z)
• Dynamic Large Concept Models: Latent Reasoning in an Adaptive Semantic Space [56.37266873329401]
  Large Language Models (LLMs) apply uniform computation to all tokens, despite language exhibiting highly non-uniform information density.<n>We propose $textbfDynamic Large Concept Models (DLCM)$, a hierarchical language modeling framework that learns semantic boundaries from latent representations and shifts from tokens to a compressed concept space where reasoning is more efficient.
  arXiv  Detail & Related papers  (2025-12-31T04:19:33Z)
• Low-Complexity Semantic Packet Aggregation for Token Communication via Lookahead Search [32.63323958382152]
  This paper focuses on token packetization to maximize the average token similarity (ATS) between the original and received token channels.<n>To address this, we propose a novel framework of semantic aggregation with lookahead search (SemPA-Look)<n>SemPA-Look applies a lookahead search-inspired algorithm that samples intra-packet token candidates without replacement.
  arXiv  Detail & Related papers  (2025-06-24T09:25:44Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30: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)
• A Partition Cover Approach to Tokenization [24.595558878756787]
  Tokenization is a process of encoding strings into tokens of a fixed vocabulary size.<n>Byte-Pair corpora (BPE) formulates the tokenization problem as a compression problem and tackles it by performing sequences of merges.<n>We show that GreedTok outperforms BPE and Unigram on compression and achieves a covering score comparable to GreedWMC.
  arXiv  Detail & Related papers  (2025-01-08T17:07:07Z)
• 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)
• Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles [23.134664392314264]
  Tokenization is associated with many poorly understood shortcomings in language models (LMs)<n>This work studies how tokenization impacts model performance by analyzing and comparing models with their byte-level counterparts.<n>We introduce the Byte-Token Representation Lemma, a framework that establishes a mapping between the learned token distribution and its equivalent byte-level distribution.
  arXiv  Detail & Related papers  (2024-10-11T23:30:42Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)

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.