Research map / Probabilistic and scientific modeling / Variational and generative sampling
Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an MCMC (Metropolis-Hastings) framework that turns grammar-constrained decoding into a grammar-aligned sampler converging to the true constrained LM distribution, and shows better KL and fuzzing branch coverage than GCD and ASAp with Llama-3.1-8B.
Problem
Constrained decoding for LMs with context-free grammar constraints distorts the model's conditional distribution, and asymptotically correct alternatives such as ASAp converge too slowly; this hurts diverse valid sample generation such as seed generation for program fuzzing.
Approach
Use Metropolis-Hastings over grammar-valid sequences, with proposals that keep a random prefix and resample the suffix via GCD; the LM-likelihood acceptance ratio cancels the intractable normalizer, giving constraint satisfaction, monotone TV convergence, and efficiency at few steps.
Key results
- On SQL fuzzing, MCMC-Priority (k=10) reaches 33.70% branch coverage vs 28.26% for GCD and 29.91% for ASAp (about 1.2x over GCD).
- On XML fuzzing, MCMC-Priority (k=10) reaches 12.81% branch coverage vs 10.67% for GCD (about 1.15x).
- KL reductions for MCMC at 10 steps: geomean 2.11x (Uniform), 2.42x (Priority), 5.07x (Restart) vs GCD; 3.99x-8.70x vs ASAp.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MCMC-Priority (k=10) instead of GCD | Grammar-aligned sampling with Llama-3.1-8B-Instruct · SQL | branch coverage: 28.26(0.68) -> 33.70(0.44) | Helped |
| Use MCMC-Priority (k=10) instead of ASAP | Grammar-aligned sampling with Llama-3.1-8B-Instruct · SQL | branch coverage: 28.71(0.48) -> 33.70(0.44) | Helped |
| Use MCMC-Priority (k=10) instead of GCD | Grammar-aligned sampling with Llama-3.1-8B-Instruct · XML | branch coverage: 10.67(0.05) -> 12.81(0.05) | Helped |
| Use MCMC-Priority (k=10) instead of ASAP | Grammar-aligned sampling with Llama-3.1-8B-Instruct · XML | branch coverage: 10.66(0.09) -> 12.81(0.05) | Helped |
| Increase MCMC steps from k=2 to k=10 (ablation) | MCMC-Prefix · SQL | branch coverage: 29.47(0.75) -> 32.93(0.83) | Helped |
| Increase MCMC steps from k=2 to k=10 (ablation) | MCMC-Priority · SQL | branch coverage: 29.99(1.40) -> 33.70(0.44) | Helped |
| Increase MCMC steps from k=2 to k=10 (ablation) | MCMC-Restart · SQL | branch coverage: 29.45(0.32) -> 32.36(0.74) | Helped |
| Increase MCMC steps from k=2 to k=10 (ablation) | MCMC-Prefix · XML | branch coverage: 11.77(0.18) -> 12.16(0.05) | Helped |
| Increase MCMC steps from k=2 to k=10 (ablation) | MCMC-Priority · XML | branch coverage: 12.10(0.20) -> 12.81(0.05) | Helped |
| Increase MCMC steps from k=2 to k=10 (ablation) | MCMC-Restart · XML | branch coverage: 11.37(0.16) -> 12.00(0.06) | Helped |
| Use Priority proposal instead of Prefix or Restart (ablation) | MCMC (k=10) · SQL and XML | branch coverage: SQL: 32.93(0.83), 32.36(0.74) -> 33.70(0.44); XML: 12.16(0.05), 12.00(0.06) -> 12.81(0.05) | Helped |
| Run MCMC for 10 steps instead of 5 (ablation) | MCMC proposal families · SQL and XML | branch coverage: k=5 already captures ≥95% of the gain realised by k=10 | Helped |
Surprising findings
- MCMC-Restart converges faster in KL than Uniform and Priority despite not accumulating information across the chain.
- Coverage ranking of MCMC variants is inversely mirrored by their KL divergence to the true constrained distribution, suggesting that closer approximation to the target is not what drives coverage.
Limitations
- Results only for one model (Llama-3.1-8B-Instruct) due to compute limits.
- Fuzzing evaluated on only two projects (libxml2, SQLite) with a single prompt and 1-hour trials.
- Only three proposal distributions studied.
Experimental setup
Datasets: SyGuS benchmarks (SLIA, BV4, CP) libxml2 XML grammar SQLite test-script grammar
Benchmarks: SyGuS SLIA SyGuS BV4 constituency parsing (CP) libxml2 fuzzing SQLite fuzzing
Metrics: KL divergence (empirical, on samples) branch coverage function coverage line coverage acceptance rate
Baselines: GCD ASAp Grammarinator rejection sampling
Builds on: grammar-constrained decoding ASAp Metropolis-Hastings AFL++ Transformers-GAD
Closest papers by meaning
- Grammar-Aligned Decoding (NeurIPS 2024 · similarity 0.88)
- Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo (ICLR 2025 · similarity 0.88)
- Controllable Generation via Locally Constrained Resampling (ICLR 2025 · similarity 0.87)
- A Probabilistic Perspective on Unlearning and Alignment for Large Language Models (ICLR 2025 · similarity 0.87)
- Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata (NeurIPS 2026 · similarity 0.87)
- XTC: Head-Aware Sampling by Excluding Top Choices (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.