Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912417245560832 |
|---|---|
| author | Gonzalez, Emmanuel Anaya Vaidya, Sairam Park, Kanghee Ji, Ruyi Berg-Kirkpatrick, Taylor D'Antoni, Loris |
| author_facet | Gonzalez, Emmanuel Anaya Vaidya, Sairam Park, Kanghee Ji, Ruyi Berg-Kirkpatrick, Taylor D'Antoni, Loris |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05754 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective Gonzalez, Emmanuel Anaya Vaidya, Sairam Park, Kanghee Ji, Ruyi Berg-Kirkpatrick, Taylor D'Antoni, Loris Artificial Intelligence Computation and Language Machine Learning 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. |
| title | Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective |
| topic | Artificial Intelligence Computation and Language Machine Learning |
| url | https://arxiv.org/abs/2506.05754 |