Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

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.

Large language models are often asked to produce outputs that must follow strict formats, such as JSON function calls or SQL queries. Current methods usually check only whether the next token is allowed. This can still lead to invalid outputs when the model runs out of tokens, and it can also change the model's intended distribution in undesirable ways. We introduce a decoding method that looks ahead to ensure that every chosen token can still lead to a valid complete output within the given token budget. We represent the constraints as finite automata and run them efficiently on GPUs. We also combine these constraints with a small probabilistic model that estimates which valid continuations are more likely. Experiments on function calling, keyword-based generation, and text-to-SQL show that our method produces valid outputs more reliably and needs fewer samples to approximate the desired constrained distribution. This makes constrained generation more accurate and efficient for structured language-model applications.