# Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 6 Jun 2025.

## Builds on (most cited first, 25 of 25)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Diffusion-LM Improves Controllable Text Generation](https://mlsanity.com/paper/2205.14217/) (2022)
- [LeanDojo: Theorem Proving with Retrieval-Augmented Language Models](https://mlsanity.com/paper/2306.15626/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Efficient Training of Language Models to Fill in the Middle](https://mlsanity.com/paper/2207.14255/) (2022)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [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)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models](https://mlsanity.com/paper/2408.02442/) (2024)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Gradient-Based Constrained Sampling from Language Models](https://mlsanity.com/paper/2205.12558/) (2022)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [Evaluating Fuzz Testing](https://mlsanity.com/paper/1808.09700/) (2018)
- [Adaptable Logical Control for Large Language Models](https://mlsanity.com/paper/2406.13892/) (2024)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [Zero and Few-shot Semantic Parsing with Ambiguous Inputs](https://mlsanity.com/paper/2306.00824/) (2023)
- [Controllable Generation via Locally Constrained Resampling](https://mlsanity.com/paper/2410.13111/) (2024)
- [CodePAD: Sequence-based Code Generation with Pushdown Automaton](https://mlsanity.com/paper/2211.00818/) (2022)

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

- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation](https://mlsanity.com/paper/2511.22277/) (2025)
- [Constrained Adaptive Rejection Sampling](https://mlsanity.com/paper/2510.01902/) (2025)
- [The Format Tax](https://mlsanity.com/paper/2604.03616/) (2026)
- [Bootstrapping Fuzzers for Compilers of Low-Resource Language Dialects Using Language Models](https://mlsanity.com/paper/2512.05887/) (2025)
- [LatticeBridge: Rare-Event Sequential Inference for Faithful Structured Sequence Synthesis](https://mlsanity.com/paper/2606.11203/) (2026)
- [The Alignment Problem in Constrained Code Generation](https://mlsanity.com/paper/2606.21619/) (2026)
- [DecompressionLM: Deterministic, Diagnostic, and Zero-Shot Concept Graph Extraction from Language Models](https://mlsanity.com/paper/2602.00377/) (2026)
- [Continuous Diffusion Models Can Obey Formal Syntax](https://mlsanity.com/paper/2602.12468/) (2026)
- [Length Value Model: Scalable Value Pretraining for Token-Level Length Modeling](https://mlsanity.com/paper/2604.27039/) (2026)
- [Generative Compilation: On-the-Fly Compiler Feedback as AI Generates Code](https://mlsanity.com/paper/2607.13921/) (2026)
- [The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding](https://mlsanity.com/paper/2608.10137/) (2026)
- [Explore Broadly, Reason Sharply: Push Small Models toward the Frontier via Sampling](https://mlsanity.com/paper/2609.38104/) (2026)
- [Provably Tractable NFA-Constrained Language Generation via HMMs](https://mlsanity.com/paper/2609.40185/) (2026)

## Abstract (arXiv)

Constrained decoding enables Language Models (LMs) to produce samples that provably satisfy hard constraints. However, existing constrained-decoding approaches often distort the underlying model distribution, a limitation that is especially problematic in applications like program fuzzing, where one wants to generate diverse and valid program inputs for testing purposes. We propose a new constrained sampling framework based on Markov Chain Monte Carlo (MCMC) that simultaneously satisfies three core desiderata: constraint satisfying (every sample satisfies the constraint), monotonically converging (the sampling process converges to the true conditional distribution), and efficient (high-quality samples emerge in few steps). Our method constructs a proposal distribution over valid outputs and applies a Metropolis-Hastings acceptance criterion based on the LM's likelihood, ensuring principled and efficient exploration of the constrained space. Empirically, our sampler outperforms existing methods on both synthetic benchmarks and real-world program fuzzing tasks.