The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding

• URL: http://arxiv.org/abs/2608.10137v1
• Date: Mon, 10 Aug 2026 18:52:43 GMT
• Title: The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding
• Abstract summary: 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.
• Score: 30.042720796822085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grammar Constrained Decoding (GCD) forces Language Models (LMs) to produce syntactically valid outputs by masking out non-conforming tokens at each step. However, rigid masking distorts the model's underlying probability distribution, often biasing generation toward valid but suboptimal outputs. While online sampling restores this distribution, it requires computationally expensive iterative resampling. As a result, existing methods force a compromise between output quality and inference latency. Our key insight is that the internal parser and lexer states inherently maintained during incremental parsing already encode future grammatical validity -- exactly the information required to restore the LM's true distribution. We propose a lightweight, offline-trained logit correction conditioned on this syntactic and lexical state together with candidate next tokens. Because these states are already computed as a necessary part of incremental parsing for masking, extracting them adds negligible overhead while leaving the base LM's weights completely untouched. Across several grammars, this correction substantially closes the gap between the masked distribution and the LM's true distribution, consistently outperforming both masking and online sampling. Even its lightest variant, which relies on the candidate next token alone, still matches or exceeds both baselines: the next token itself carries an implicit lookahead, much like how parsers commonly use a lookahead token to resolve ambiguous decisions. By restoring the probability mass that masking removes, it reconciles the LM's probabilistic integrity with grammar conformance.

Related papers

• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• NAVIRA: Decoupled Stochastic Remasking for Masked Diffusion Language Models [0.0]
  PRISM addresses this by learning token-level quality scores and remasking unreliable tokens.<n>We propose NAVIRA, an inference-time decoding policy that separates these two operations.<n>Temperature-controlled remasking reduces repeated correction of the same positions.
  arXiv  Detail & Related papers  (2026-06-04T11:24:47Z)
• SimSD: Simple Speculative Decoding in Diffusion Language Models [61.33773959352141]
  Diffusion large language models (dLLMs) offer faster inference through parallel or blockwise decoding.<n>Their masked language modeling formulation remains incompatible with standard token-level speculative decoding.<n>We propose a speculative decoding algorithm for dLLMs, named SimSD, that equips dLLMs with temporally valid token-level contexts.<n>Our method achieves up to 7.46x higher decoding throughput while maintaining and even improving average generation quality.
  arXiv  Detail & Related papers  (2026-06-01T17:46:46Z)
• Dependency-Guided Parallel Decoding in Discrete Diffusion Language Models [21.699371484195865]
  We propose DEMASK, a lightweight dependency predictor that attaches to the final hidden states of a dLLM.<n> Empirically, DEMASK achieves 1.7-2.2$times$ speedup on Dream-7B while matching or improving accuracy compared to confidence-based and KL-based baselines.
  arXiv  Detail & Related papers  (2026-04-02T22:21:24Z)
• From Early Encoding to Late Suppression: Interpreting LLMs on Character Counting Tasks [49.57538588967748]
  Large language models (LLMs) exhibit failures on elementary symbolic tasks such as character counting in a word, despite excelling on complex benchmarks.<n>We uncover a consistent phenomenon across modern architectures, including LLaMA, Qwen, and Gemma.<n>We show that symbolic reasoning failures in LLMs are not due to missing representations or insufficient scale, but arise from structured interference within the model's computation graph.
  arXiv  Detail & Related papers  (2026-04-01T11:40:12Z)
• Entropy-Aligned Decoding of LMs for Better Writing and Reasoning [21.971790771470324]
  Language models (LMs) are trained on billions of tokens in an attempt to recover the true language distribution.<n>Currently, vanilla random sampling from LMs yields low quality generations.<n>We introduce EPIC, a hyper- parameter-free decoding approach that incorporates the entropy of future trajectories into LM decoding.
  arXiv  Detail & Related papers  (2026-01-05T01:37:10Z)
• Blockwise SFT for Diffusion Language Models: Reconciling Bidirectional Attention and Autoregressive Decoding [60.06816407728172]
  Discrete diffusion language models have shown strong potential for text generation.<n>Standard supervised fine-tuning misaligns with semi-autoregressive inference.<n>We propose Blockwise SFT, which partitions responses into fixed-size blocks.
  arXiv  Detail & Related papers  (2025-08-27T02:49:33Z)
• 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)
• Not all tokens are created equal: Perplexity Attention Weighted Networks for AI generated text detection [49.15148871877941]
  Next-token distribution outputs offer a theoretically appealing approach for detection of large language models (LLMs)<n>We propose the Perplexity Attention Weighted Network (PAWN), which uses the last hidden states of the LLM and positions to weight the sum of a series of features based on metrics from the next-token distribution across the sequence length.<n>PAWN shows competitive and even better performance in-distribution than the strongest baselines with a fraction of their trainable parameters.
  arXiv  Detail & Related papers  (2025-01-07T17:00:49Z)
• Grammar-Aligned Decoding [30.972850034752884]
  Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches a given constraint. In this paper, we demonstrate that GCD techniques can distort the LLM's distribution, leading to outputs that are grammatical but appear with likelihoods that are not proportional to the ones given by the LLM.
  arXiv  Detail & Related papers  (2024-05-31T17:39:15Z)

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.