💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

This paper proposes a generic approach to mitigate bias in locally constrained decoding by constructing tractable, globally constrained proposals via tensorized finite automata and circuit multiplication, enabling efficient Sequential Monte Carlo sampling that converges faster to the target distribution with fewer particles across tasks like function calling and SQL generation.

Original authors: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very creative but slightly chaotic storyteller (a Large Language Model) to write a story that follows a very strict rulebook, like a JSON code format or a specific SQL database query.

The problem is that the storyteller loves to wander. If you just say, "Don't break the rules," they might start a sentence that looks okay at first but becomes impossible to finish correctly by the end.

Here is how the paper solves this problem, using simple analogies:

1. The Old Way: The "Myopic" Guide (LCD)

Imagine the storyteller is walking through a maze. The old method (called Locally Constrained Decoding or LCD) acts like a guide who only looks at the very next step.

How it works: If the next step looks like it might hit a wall, the guide blocks it.
The Flaw: The guide is "myopic" (short-sighted). They might let the storyteller take a path that looks safe for the next step but leads to a dead end three steps later. The storyteller keeps walking, thinking they are fine, only to realize at the very end that they can't finish the story within the word limit. They have to start over or produce a broken story.

2. The New Way: The "Global Map" (GCD)

The authors propose a new method called Globally Constrained Decoding (GCD).

The Analogy: Instead of just looking at the next step, this guide has a complete map of the entire maze and knows exactly how many steps are left to reach the exit.
How it works: Before the storyteller takes a step, the guide checks: "If you go this way, can you actually reach the exit within the remaining steps?"
The Result: If the answer is "No," the guide blocks that path immediately. This guarantees that no matter what the storyteller chooses, they will always reach a valid ending. It's like having a GPS that only shows you routes that are guaranteed to get you to your destination on time.

3. The "Smart" Map: Adding Probability (P-GCD)

The "Global Map" (GCD) is great at avoiding dead ends, but it treats all valid paths as equal. It doesn't know which path the storyteller prefers or which one is more likely to be a good story.

The Analogy: Imagine the storyteller has a favorite way of walking. The basic map just says, "This path is valid." The new Probabilistic GCD (P-GCD) says, "This path is valid, and it's also the path the storyteller is most likely to enjoy."
How it works: The authors combine the "Global Map" (the rules) with a "Memory Model" (a simplified version of the storyteller's brain). They multiply these two together.
The Result: The guide now doesn't just block bad paths; it gently nudges the storyteller toward the paths that are both valid and high-quality. This makes the storytelling process much more efficient.

4. The "Particle" Race (SMC)

To test these methods, the researchers use a technique called Sequential Monte Carlo (SMC).

The Analogy: Imagine you are trying to find the best route through a foggy forest. Instead of sending one person, you send out a swarm of 100 "particles" (explorers).
The Old Way: With the short-sighted guide, you need to send out thousands of explorers because many of them will get lost or hit dead ends before they finish.
The New Way: With the "Global Map" and "Smart Map," the explorers stay on the right track. You need far fewer explorers to find the perfect path because the guide is so much better at filtering out bad options early on.

5. The "Shape-Shifting" Trick (Tensorization)

One of the paper's technical breakthroughs is how they handle the "Map."

The Problem: Complex rules (like JSON schemas) can create maps with millions of paths. Usually, computers get overwhelmed trying to draw these maps on a standard processor.
The Solution: The authors turned these complex maps into mathematical blocks (tensors) that fit perfectly onto modern graphics cards (GPUs).
The Analogy: It's like taking a giant, messy pile of paper maps and folding them into a compact, high-speed digital chip that a supercomputer can read instantly. This allows the "Global Map" to be calculated in the blink of an eye, even for very complex rules.

Summary of Results

The paper tested this on three real-world tasks:

Function Calling: Making sure AI calls computer functions with the right format (like JSON).
Keyword Generation: Making sure a story includes specific words.
SQL Generation: Writing database queries that are syntactically correct.

The Verdict:

Reliability: The new method guarantees the story ends correctly within the word limit, whereas the old method often failed at the finish line.
Efficiency: To get the same quality of results, the new method needed significantly fewer "explorers" (particles) than the old method.
Speed: While the "Smart Map" (P-GCD) takes a bit more computing power, it is still fast enough to be practical, and the "Global Map" (GCD) is almost as fast as the old method.

In short, the paper gives AI a "Global Map" and a "Smart Nudge" so it can follow strict rules without getting lost, wasting time, or producing broken code.

Technical Summary: Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Problem Statement

Large Language Models (LLMs) often fail to generate outputs that strictly adhere to logical or structural constraints, such as JSON schemas, valid SQL queries, or specific function-calling formats. While instruction tuning and preference optimization have improved general alignment, they remain unreliable for enforcing "hard" constraints.

Existing approaches face two primary limitations:

Rejection Sampling: While unbiased, it is computationally impractical for complex constraints due to vanishingly low acceptance rates.
Locally Constrained Decoding (LCD): This standard approach masks tokens that immediately violate a constraint at each step. However, it suffers from two critical flaws:
- Bias: It distorts the model's underlying distribution by myopically masking tokens without considering future validity, leading to sampling bias.
- No Termination Guarantee: LCD only ensures local validity. A sequence may remain locally valid indefinitely (e.g., an unclosed brace in JSON) but fail to satisfy the constraint within a fixed token budget $n$ .

To address these issues, the Sequential Monte Carlo (SMC) framework has been proposed, using LCD as a proposal distribution and re-weighting particles to converge to the target distribution. However, the convergence rate of SMC is bottlenecked by the quality of the proposal; LCD is a weak proposal because it lacks probabilistic information about future valid completions and does not guarantee constraint satisfaction within a finite budget.

Methodology

The authors propose a generic approach to construct tractable proposals and potential functions for SMC sampling from the constrained distribution $p_{lm}(\cdot \mid C)$ . The core innovation involves representing constraints as finite automata and leveraging tensor operations for efficient GPU execution.

1. Globally Constrained Decoding (GCD)

GCD improves upon LCD by ensuring that every generated token can lead to a valid completion within the remaining token budget $n$ .

Tensorized Finite Automata: Constraints encoded as Finite Automata (FA), specifically Non-deterministic Finite Automata (NFAs) and Deterministic Finite Automata (DFAs), are compiled into tensorized representations (transition matrices $T_{out}, T_{in}$ and emission matrix $B_f$ ). This allows for efficient execution on GPUs.
Forward-Backward Inference:
- Forward Process: Computes the set of FA states reachable after observing the prefix $x_{1:t-1}$ .
- Backward Process: Computes whether a state can reach an accepting state in exactly $n-t$ steps.
Global Masking: A token is permitted only if it leads to a state that admits a valid continuation within the remaining budget. This guarantees that any sequence of length $n$ generated under GCD satisfies the constraint $C$ .

2. Probabilistic Globally Constrained Decoding (P-GCD)

While GCD guarantees constraint satisfaction, its mask is binary (valid/invalid) and ignores the likelihood of valid completions under the LLM. P-GCD addresses this by integrating probabilistic information.

HMM Distillation: The LLM's distribution is approximated by a Hidden Markov Model (HMM), following prior work (Zhang et al., 2023).
Circuit Multiplication: The tensorized FA (viewed as an unnormalized HMM over edges) is multiplied with the distilled HMM using circuit multiplication algorithms. This leverages the shared algebraic structure of FAs and HMMs.
Product Distribution: The resulting product distribution $p_{prod}$ captures both the hard logical constraints of the FA and the probabilistic preferences of the LLM.
Proposal and Potential:
- Proposal ( $q_{pgcd}$ ): Reweights the LM distribution at each step using the constrained next-token probability derived from $p_{prod}$ .
- Potential ( $\phi_{pgcd}$ ): Weights particles in SMC by the product of the LM's prefix probability and the HMM's look-ahead estimate of constraint satisfaction.

3. Efficient Implementation

The authors utilize tensor-network operations (specifically the Kronecker-vec identity) to avoid explicitly materializing large Kronecker-product matrices. This reduces the computational cost of transition steps from $O((HE)^2)$ to $O(H^2E + HE^2)$ , where $H$ is the HMM hidden size and $E$ is the FA edge count, enabling efficient autoregressive generation.

Key Contributions

GCD and P-GCD Frameworks: The introduction of Globally Constrained Decoding and Probabilistic GCD, which provide tractable proposals and potentials for SMC that guarantee constraint satisfaction within a token budget.
Tensorized Automata on GPUs: The first proposal to tensorize finite automata (including NFAs) for efficient GPU-native inference, overcoming the CPU-bound limitations of existing frameworks like Outlines and XGrammar.
NFA Support: Demonstrating that NFAs can be exponentially more succinct than DFAs for complex constraints (e.g., function calling with variable parameters), making the approach scalable to real-world agentic applications where DFA construction may cause memory overflow.
Integration with SMC: Showing that (P-)GCD significantly accelerates SMC convergence compared to LCD-based proposals, requiring far fewer particles to reach the target distribution.

Experimental Results

The authors evaluated (P-)GCD on three benchmarks: xLAM (function calling), CommonGen (keyword-based generation), and Spider (text-to-SQL).

Function Calling (xLAM):
- (P-)GCD achieved substantially higher accuracy than LCD at the same number of particles.
- P-GCD converged to the ground-truth distribution (rejection sampling) faster than GCD, highlighting the benefit of probabilistic information.
- Constraint Satisfaction: GCD and P-GCD achieved 100% constraint satisfaction rates across all particle budgets, whereas LCD failed to satisfy constraints even at moderate budgets (e.g., ~95% for JSON).
- Efficiency: LCD and GCD incurred modest overhead (1.08× and 1.10× slowdown). P-GCD was slower (3.11× to 10.2×) due to HMM computations but remained feasible.
Keyword Generation (CommonGen): Using P-GCD as both proposal and potential improved BLEU scores and convergence speed significantly over LCD.
Text-to-SQL (Spider): GCD and P-GCD improved execution accuracy over LCD across various particle budgets, particularly at moderate values.
NFA vs. DFA: Experiments confirmed that for complex schemas (e.g., variable-length function parameters), NFAs grow linearly in size while DFAs grow exponentially. For the Spider SQL grammar, DFA construction resulted in Out-of-Memory (OOM) errors at the token level, whereas the NFA remained tractable (~32k states).

Significance and Claims

The paper claims that locally constrained decoding introduces substantial sampling bias and fails to guarantee constraint satisfaction within finite token budgets. By proposing (P-)GCD, the authors offer a solution that:

Guarantees Validity: Ensures that any generated sequence of length $n$ satisfies the constraint, eliminating the failure cases of LCD.
Reduces Bias: By incorporating probabilistic information (via P-GCD) and global lookahead, the proposals better approximate the target conditional distribution.
Improves Efficiency: In the SMC framework, (P-)GCD converges to the target distribution with significantly fewer particles than LCD-based approaches, reducing the computational cost of high-quality constrained generation.

The work positions itself as a foundational step toward reliable, constraint-satisfying generation for LLMs in applications requiring strict structural adherence, such as function calling and code generation, by unifying logical constraints (via automata) and probabilistic modeling (via HMMs) in a GPU-efficient manner.