# Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

arXiv: https://arxiv.org/abs/2606.01926 · HTML: https://mlsanity.com/paper/2606.01926/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 42 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Builds on (most cited first, 30 of 34)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Models](https://mlsanity.com/paper/2009.11462/) (2020)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [GeDi: Generative Discriminator Guided Sequence Generation](https://mlsanity.com/paper/2009.06367/) (2020)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Spider 2.0: Evaluating Language Models on Real-World Enterprise Text-to-SQL Workflows](https://mlsanity.com/paper/2411.07763/) (2024)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [APIGen: Automated Pipeline for Generating Verifiable and Diverse Function-Calling Datasets](https://mlsanity.com/paper/2406.18518/) (2024)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [Controllable Text Generation with Neurally-Decomposed Oracle](https://mlsanity.com/paper/2205.14219/) (2022)
- [Bounding the Capabilities of Large Language Models in Open Text Generation with Prompt Constraints](https://mlsanity.com/paper/2302.09185/) (2023)
- [Adaptable Logical Control for Large Language Models](https://mlsanity.com/paper/2406.13892/) (2024)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)

## Built on by (most cited first, 8 of 8)

- [Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata](https://mlsanity.com/paper/2607.07026/) (2026)
- [Repair, Not Improvement: Decomposing Constrained Decoding in Tool-Call Abstention](https://mlsanity.com/paper/2608.13959/) (2026)
- [Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments](https://mlsanity.com/paper/2607.18357/) (2026)
- [The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding](https://mlsanity.com/paper/2608.10137/) (2026)
- [Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models](https://mlsanity.com/paper/2609.32900/) (2026)
- [Twist, Don't Tilt: Trajectory-Exact Constrained Decoding for Masked Diffusion Models](https://mlsanity.com/paper/2609.35609/) (2026)
- [GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning](https://mlsanity.com/paper/2609.39869/) (2026)
- [Provably Tractable NFA-Constrained Language Generation via HMMs](https://mlsanity.com/paper/2609.40185/) (2026)

## Abstract (arXiv)

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 plm( · mid 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.