Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

• URL: http://arxiv.org/abs/2606.01926v1
• Date: Mon, 01 Jun 2026 08:58:18 GMT
• Title: Mitigating Bias in Locally Constrained Decoding via Tractable Proposals
• Abstract summary: Existing locally constrained decoding approaches enforce constraints by myopically masking out next tokens.<n>Recent work uses sequential Monte Carlo methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge.<n>We propose a generic approach to construct proposals and potentials for SMC sampling from $p_mathrmlm( cdot mid mathrmconstraint)$.
• Score: 73.78736135699953
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Generations from large language models often fail to conform to desired constraints such as JSON schema. Existing locally constrained decoding (LCD) approaches enforce constraints by myopically masking out next tokens, resulting in biased sampling and degradation in performance. Recent work uses sequential Monte Carlo (SMC) methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge. In this work, we propose a generic approach to construct proposals and potentials for SMC sampling from $p_{\mathrm{lm}}( \cdot \mid \mathrm{constraint})$. First, we show that constraints specified as finite automata can be tensorized for efficient execution on GPUs, which we use to construct globally constrained decoding (GCD) proposals. In addition, leveraging the fact that tensorized finite automata share the same circuit structure as hidden Markov models, we circuit-multiply them to obtain the probabilistic GCD (P-GCD) proposals encoding both logical and probabilistic information about the target distributions. We evaluate (P-)GCD on the tasks of function calling, keyword-based generation, and SQL generation. Experiments show that under the same SMC sampling setup, compared to LCD proposals, (P-)GCD converges faster to the target distribution with significantly fewer particles.

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)
• The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models [49.67598869075125]
  In autoregressive language modeling, Probabilistic Circuits (PCs) lag behind Transformer-based large language models (LLMs)<n>We show that structured-decomposable PCs can match Transformer separation rank on vtree-aligned partitions, but that this capacity is limited to partitions aligned with the fixed routing structure.<n>We further prove that decomposable PCs are strictly more expressive than structured-decomposable ones, though effectively optimizing them remains an open challenge.
  arXiv  Detail & Related papers  (2026-05-13T03:22:10Z)
• Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse [0.0]
  We introduce language tries (PLTs), a unified representation that makes explicit the prefix structure implicitly defined by any generative probabilistic model over sequences.<n>We also introduce a hybrid compression architecture decomposing any dataset into a covered majority and a sparse residual store, connecting arithmetic coding with Kolmogorov-style program representations and rate-distortion theory.
  arXiv  Detail & Related papers  (2026-03-29T21:24:26Z)
• Top-b: Entropic Regulation of Relative Probability Bands in Autoregressive Language Processes [16.569049230416123]
  Top-b is a decoding strategy that regulates the candidate set via a dynamic bandwidth coefficient.<n>We show that Top-b significantly reduces generation entropy and inter-decoding variance while maintaining competitive reasoning accuracy.
  arXiv  Detail & Related papers  (2026-03-15T19:39:51Z)
• SimGR: Escaping the Pitfalls of Generative Decoding in LLM-based Recommendation [68.00727783181289]
  A core objective in recommender systems is to accurately model the distribution of user preferences over items to enable personalized recommendations.<n>We observe that existing methods inevitably introduce systematic bias when estimating item-level preference distributions.<n>We propose textbfSimply textbfGenerative textbfRecommendation (textbfSimGR), a framework that directly models item-level preference distributions in a shared latent space.
  arXiv  Detail & Related papers  (2026-02-08T07:26:52Z)
• Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective [31.37618506317961]
  Constrained decoding enables Language Models to produce samples that provably satisfy hard constraints.<n>Existing constrained-decoding approaches distort the underlying model distribution.<n>We propose a new constrained sampling framework based on Markov Chain Monte Carlo.
  arXiv  Detail & Related papers  (2025-06-06T05:28:20Z)
• Reviving Any-Subset Autoregressive Models with Principled Parallel Sampling and Speculative Decoding [55.2480439325792]
  In arbitrary-order language models, it is an open question how to sample tokens in parallel from the correct joint distribution.<n>We find that a different class of models, any-subset autoregressive models (AS-ARMs), holds the solution.<n>We show that AS-ARMs achieve state-of-the-art performance among sub-200M parameter models on infilling benchmark tasks, and nearly match the performance of models 50X larger on code generation.
  arXiv  Detail & Related papers  (2025-04-29T06:33:13Z)
• 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)
• Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors [1.8130068086063333]
  Stragglers and other failures can severely impact the overall completion time. Recent works in coded computing provide a novel strategy to mitigate stragglers with coded tasks. We show that this strict definition does not directly optimize the probability of failure.
  arXiv  Detail & Related papers  (2022-02-07T19:20:00Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)

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.