Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon · 2026

Read Mitigating Bias in Locally Constrained Decoding via Tractable Proposals by Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01926.txt.

Introduction

Dang and co-authors fix a bias in how chat models follow format rules. Models often fail to match required output shapes. JSON schema is a common case of such rules. Local constrained decoding masks forbidden tokens step by step. That myopic masking skews the sampling and hurts quality.

Recent Monte Carlo methods ease the bias in part. Their weak point is crafting good proposal distributions. The team build proposals from the constraints themselves. Constraints written as finite automata are tensorized for GPUs. That yields globally constrained decoding proposals. Circuit tricks borrowed from hidden Markov models help too. Potentials for the sampling come from the same structure.

Catalog record

CREATORMeihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01926

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon 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 lm ( ⋅ ∣ constraint ) 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. 1 Introduction Many applications require LLM outputs to satisfy strict logical or structural constraints. Examples include generating function calls conforming to a JSON schema ( Patil et al. 2024 ; Patil et al. 2025 ) , producing syntactically valid SQL queries ( Lei et al. 2025 ) , and avoiding toxic content ( Gehman et al. 2020 ) . Despite substantial advances in instruction fine-tuning ( Wei et al. 2022 ; Chung et al. 2024 ) and preference optimization ( Ouyang et al. 2022 ; Rafailov et al. 2023 ) , current LLMs remain unreliable at consistently enforcing such hard constraints ( Lu et al. 2023 ) . Given a constraint \mathcal{C} , the simplest unbiased way to sample from the constrained distribution p_{\mathrm{lm}}(x_{1:n}\!\mid\!\mathcal{C}) is rejection sampling : repeatedly draw from the unconstrained LM and reject those violating the constraint. However, it becomes impractical for complex constraints due to vanishingly low acceptance rates. A standard alternative is locally constrained decoding (LCD) , which masks out next tokens that immediately violate the constraint at each decoding step ( Scholak et al. 2021 ; Dong et al. 2025 ) . However, this local strategy (i) distorts the model’s distribution ( Park et al. 2024 ) and (ii) does not guarantee constraint satisfaction within a finite token budget , since the model may continue generating locally valid prefixes indefinitely without ever reaching a satisfying completion ( Li et al. 2025 ) . To address the two limitations of LCD, we propose: 1. Globally constrained decoding (GCD) . Given constraints encoded as finite automata, we compile them into tensorized representations for efficient execution on GPUs. We use them to efficiently mask tokens that cannot lead to a valid completion within a token budget. This guarantees constraint satisfaction at termination. 2. Probabilistic GCD (P-GCD) . We first distill hidden Markov models to approximate the LM’s distributions, following Zhang et al. 2023 . Then we efficiently multiply them with the finite automata, leveraging circuit multiplication and tensor-network operations ( Loconte et al. 2025 ) . The multiplied distributions capture both hard constraint satisfaction and probabilistic information about future valid completions. We compare (P-)GCD against LCD within the sequential Monte Carlo (SMC) sampling framework. Prior work applies SMC with LCD as the proposal distribution, mitigating its bias by re-weighting and re-sampling a batch of sequences ( particles ) ( Loula et al. 2025 ; Lipkin et al. 2025 ) . SMC is guaranteed to converge to the target distribution as the number of particles increases, but the convergence rate is bottlenecked by the quality of the proposal. We evaluate (P-)GCD on three constrained generation benchmarks: xLAM, a function-calling dataset with outputs constrained to follow JSON or Python-like syntax; CommonGen, a keyword-based generation task; and Spider, a text-to-SQL task where outputs must follow SQL syntax. When used as the proposal or potential distribution within the SMC framework, (P-)GCD outperforms LCD-based proposals in both generation quality and sampling efficiency, converging to the target distribution with significantly fewer particles. 1 1 1 Code available at https://github.com/MhDang/gelatwo . 2 Problem Setup Notation. We denote a sequence of n tokens as x_{1:n} , with x_{t} the token at position t and x_{<t} the prefix x_{1},\dots,x_{t-1} , and assume all sequences generated by language models are padded to length n . We use p to denote a distribution defined by a model (e.g., p_{\mathrm{lm}} ), q to denote any modified distribution used for sampling, and \mathcal{C} to denote any constraint. Constrained Generation. The goal of this work is to sample sequences from an LLM that strictly satisfy a given logical constraint \mathcal{C} . Let p_{\mathrm{lm}}(x_{1:n})=\prod_{t=1}^{n}p_{\mathrm{lm}}(x_{t}\!\mid\!x_{<t}) denote the LLM distribution over token sequences of length n . The target distribution is then \displaystyle p_{\mathrm{lm}}(x_{1:n}\mid\mathcal{C})\propto p_{\mathrm{lm}}(x_{1:n})\cdot\mathbf{1}\{x_{1:n}\in\mathcal{X}_{n}\}, where \mathbf{1}\{\cdot\} denotes the indicator function and \mathcal{X}_{n}:=\{\,x_{1:n}:x_{1:n}\text{ satisfying }\mathcal{C}\,\} . Rejection Sampling. The simplest and unbiased approach to sample from the target distribution p_{\mathrm{lm}}(x_{1:n}\!\mid\!\mathcal{C}) is rejection sampling: repeatedly drawing x_{1:n}\!\sim\!p_{\mathrm{lm}} until x_{1:n}\!\in\!\mathcal{X}_{n} . However, this is impractical for non-trivial constraints, where acceptance rates can be vanishingly low. Locally Constrained Decoding. During autoregressive generation, one can often detect whether a candidate next token would immediately violate the constraint. For example, a valid JSON object must begin with an opening brace “{” or bracket “[”; sampling anything else at the first step immediately violates the constraint. Locally constrained decoding (LCD) exploits this by masking out invalid tokens at each sampling step and renormalizing distribution over the tokens that still permit a valid completion from the current prefix. That is, it defines the proposal distribution: \displaystyle q_{\mathrm{lcd}}(x_{t}\mid x_{<t})\propto p_{\mathrm{lm}}(x_{t}\mid x_{<t})\cdot\mathbf{1}\{x_{1:t}\in\mathcal{X}_{t,*}\}, (1) where \mathcal{X}_{t,m}=\{\,x_{1:t}:\exists\,x_{t+1:m},\;x_{1:m}\text{ satisfying }\mathcal{C}\,\} is the set of prefixes that can be extended to a length- m sequence satisfying \mathcal{C} , and \mathcal{X}_{t,*}=\bigcup_{m\geq t}\mathcal{X}_{t,m} allows extension to satisfying sequences of any length. In other words, LCD rejects x_{t} only when no valid sequence of any length begins with the prefix x_{1:t} ( Lipkin et al. 2025 ) . However, this is a “loose” masking criterion: locally valid prefixes may only admit a valid completion beyond length n , so the final length- n sequence may still violate the constraint \mathcal{C} . For example, when generating a JSON object, the decoder may repeatedly emit unmatched opening braces “{”. Each step remains locally valid, but if generation stops at length n before the braces are closed, the final sequence is invalid. There are a variety of open-source constrained decoding frameworks, such as Outlines ( Willard & Louf 2023 ) and XGrammar ( Dong et al. 2025 ) , and constrained decoding is widely deployed in production for proprietary models, such as the OpenAI API ( Geng et al. 2025 ) . To the best of our knowledge, all of the aforementioned systems perform LCD and do not guarantee constraint satisfaction within a given token budget . Our approach eliminates such failure cases (Section 3 ). Moreover, the greedy and myopic enforcement of LCD deviates from the target

Read the complete text