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

This paper studies constrained sampling for language models from an MCMC perspective. The goal is to generate outputs that satisfy hard constraints while preserving the language model’s conditional distribution, instead of only forcing validity through local token masks.

The work frames constrained generation as a sampling problem over valid outputs. It constructs proposal distributions that stay inside the constrained space and uses a Metropolis-Hastings acceptance rule based on the language model likelihood. This gives a principled way to explore valid outputs while converging toward the desired conditional distribution.

The paper evaluates the approach on synthetic benchmarks and program fuzzing tasks, where both validity and diversity matter. It appeared at NeurIPS 2025.