Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Problem Statement and Limitations of Existing Methods

Current Large Language Models (LLMs) often fail to consistently enforce hard constraints, such as JSON schema or SQL syntax. Existing locally constrained decoding (LCD) approaches attempt to address this by masking out next tokens that immediately violate the constraint at each decoding step. However, this local strategy suffers from two major limitations:

1. Distortion of Distribution: LCD distorts the model’s distribution (plm(x t x<t)).

2. Lack of Global Guarantee: It does not guarantee constraint satisfaction within a finite token budget, as the model may continue generating locally valid prefixes indefinitely without ever reaching a satisfying completion.

Proposed Solutions: GCD and P-GCD

To overcome these issues, the authors propose two related methods:

1. Globally Constrained Decoding (GCD): This method addresses the lack of global guarantee. Given constraints encoded as finite automata, GCD masks tokens that cannot lead to a valid completion within a token budget (n. GCD guarantees constraint satisfaction at termination).

2. Probabilistic Globally Constrained Decoding (P-GCD): This addresses the sampling bias introduced by GCD’s binary masking. P-GCD augments the hard constraints with probabilistic information derived from the language model's distribution, creating a tractable proposal and potential function for Sequential Monte Carlo (SMC) sampling.

Technical Implementation: Tensorization and HMM Integration

The core of both methods relies on representing constraints as finite automata (FA).

• Tensorizing Finite Automata: A finite automaton is defined by a set of states S, a vocabulary V, a transition function delta, s 0, and an accepting set F. The FA is encoded using three binary matrices:

• T out in 0, 1 S times E (source incidence matrix).

• T in in 0, 1 E times S (destination incidence matrix).

• B f encodes the edge labels (emission matrix) in 0, 1 E times V.

• GCD Proposal (qgcd): GCD uses the tensorized FA to evaluate the indicator function 1x 1:t in X t,n, where X t,n is the set of prefixes that can be extended to a length- n sequence satisfying C. This allows for efficient evaluation of whether a candidate token is feasible within the remaining budget.

• P-GCD (The Product Distribution): P-GCD integrates an HMM (phmm) to approximate the LM's distribution (plm). The FA naturally induces an HMM whose hidden states correspond to FA edges. The resulting product distribution pprod proportional to phmm times pfa is defined by a product of parameters:

pi = pi h pi f

A = A h A f

The P-GCD proposal (qpgcd) and potential (phi pgcd are defined as:

qpgcd(x t x<t) proportional to plm(x t x<t) times phmm(x t x<t, C) over 1-w

phi pgcd(x 1:t) proportional to plm(x 1:t) times phmm(C x 1:t)

SMC Sampling and Evaluation

Both GCD and P-GCD are evaluated within the Sequential Monte Carlo (SMC) framework. The performance of SMC depends on the quality of the proposal distribution.

• Key Finding: Compared to LCD proposals, (P-)GCD converges faster to the target distribution with significantly fewer particles.

• Benchmarks: The methods were tested on three tasks:

1. xLAM: Function-calling datasets constrained by JSON or Python-like syntax.

2. CommonGen: A keyword-based generation task requiring natural language sentences incorporating all given concepts (evaluated using BLEU).

3. Spider: A text-to-SQL task where outputs must follow strict SQL syntax constraints (evaluated using execution accuracy).

Results and Performance Analysis

• Constraint Satisfaction: GCD and P-GCD achieve 100% constraint satisfaction at moderate particle budgets (k=16), whereas LCD can fail to satisfy the constraint even at these budgets.

• Efficiency (Overhead): The overhead of the methods relative to unconstrained generation is minimal for GCD (about 1.08 times to 1.10 times). P-GCD is more computationally intensive due to additional HMM computations, ranging from 3.11 times to 10.2 times slowdown depending on the HMM size (H).

• Accuracy and Convergence: In all three benchmarks, both GCD and P-GCD demonstrate improved accuracy and faster convergence compared to LCD across a range of particle budgets. The advantage of P-GCD is particularly pronounced in low-particle regimes.

As a diligent AI researcher, my analysis of this paper indicates that the core weakness in current constrained generation systems is their myopic approach—a failure to reconcile local constraint satisfaction with global probabilistic likelihood. The proposed solutions, Globally Constrained Decoding (GCD) and Probabilistic Globally Constrained Decoding (P-GCD), provide a rigorous, tractable framework for replacing standard decoding methods with highly efficient, globally aware alternatives.

The following are the specific improvements I propose for implementing these findings into production AI systems:

• Action: Replace the standard locally masked token selection logic (e.g., in typical beam search or naive sampling) with a Globally Constrained Decoding (GCD) mechanism.

• Mechanism: The constraint C must be represented as a tensorized Finite Automaton (NFA/DFA), as described in Section 3. Instead of masking tokens that currently violate the constraint, the system calculates X t,n (the set of prefixes that can be extended to a length- n sequence satisfying C). Any token not belonging to this set is masked out.

• ** Technical Implementation:** The system must efficiently compute the indicator function 1x 1:t in X t,n using tensor operations (specifically matrix multiplications involving the incidence and emission matrices of the FA). This replaces simple bitwise checking with a high-throughput GPU-native logic.

• Action: Augment the GCD mechanism by distilling a Hidden Markov Model (HMM) approximation of the underlying Language Model (p lm). This creates Probabilistic Globally Constrained Decoding (P-GCD).

• Mechanism: The system calculates the joint distribution p prod(x 1:n) proportional to p lm(x 1:n) times 1x 1:n in X n. This is achieved by combining the FA's structure with the HMM’ forward (alpha t) and backward (beta t) messages.

• ** Technical Implementation:** The system must implement circuit multiplication (as detailed in Section 4.2) to define the Product HMM, p prod. This allows for efficient calculation of conditional probabilities p prod(x t x<t) without materializing massive Kronecker-product matrices.

• Action: Use P-GCD as a superior proposal distribution (q pgcd) and/or an **SMC potential function (phi pgcd ** within the SMC framework, replacing the biased LCD proposal.

• ** Mechanism:** q pgcd(x t x<t) proportional to p lm(x t x<t) times PHMM(x t x<t, C). This reweights the LM distribution based on the HMM's look-ahead estimate of constraint satisfaction.

• ** Technical Implementation:** The system implements on-the-fly normalization using the forward and backward messages to calculate these probabilities, ensuring that sampling from p prod is both efficient and unbiased.

By integrating these improvements, the new AI system will achieve several critical capabilities:

1. Guaranteed Constraint Satisfaction: Unlike existing systems (LCD) which may fail to satisfy complex constraints within a finite token budget, the GCD mechanism guarantees that every generated sequence adheres to C at termination.

2. Elimination of Sampling Bias: By using P-GCD as a proposal, the system avoids the myopic bias of LCD. It correctly weights tokens not just by local feasibility, but by their contribution to a globally valid and probable completion, ensuring the SMC process converges accurately to p lm(x 1:nC).

3. Handling Complex Constraints: The use of Nondeterministic Finite Automata (NFAs) allows the system to handle constraints (like complex JSON schemas or intricate SQL queries) that are exponentially larger when represented as Deterministic Finite Automata (DFAs), making real-world, large-scale structured generation feasible.

4. High Sampling Efficiency: The P-GCD approach enables SMC sampling to converge to the target distribution with significantly fewer particles compared to traditional LCD methods, drastically reducing computational overhead in complex decision-making tasks like function calling or SQL generation.

5. Multimodal Constraint Handling: The system can seamlessly handle diverse constraint types (e.g., JSON structure, keyword inclusion, SQL syntax) by mapping them all to their respective tensorized FA representations and applying the unified P-GCD framework across different datasets (xLAM, CommonGen, Spider).

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(times 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.