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

Emmanuel Anaya Gonzalez (University of California San Diego) · Sairam Vaidya (University of California, San Diego) · Kanghee Park (University of California, San Diego) · Ruyi Ji (Peking University) · Taylor Berg-Kirkpatrick (UC San Diego) · Loris D'Antoni (University of California San Diego)

constrained decodingconstrained sampling frameworkconstraint satisfyingefficient explorationhard constraints language modelslikelihoodmarkov chain monte carlomcmcmetropolis-hastings acceptance criterionmodel distributionmonotonically convergingprogram fuzzingproposal distributionreal-world tasks synthetic benchmarks

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.