用马尔可夫链蒙特卡洛方法，让语言模型高效生成满足约束的多样化输出。
Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective
- 基于MCMC构造有效输出的提议分布，通过似然接受准则探索约束空间。
- 在合成数据和程序模糊测试任务中均优于现有方法，生成质量高且收敛快。
- 适合需要严格约束与多样性并重的应用，如自动化测试、代码生成。
约束解码使语言模型生成的样本能严格满足硬性约束。然而，现有方法常扭曲原始模型分布，尤其在程序模糊测试等场景中，需生成多样且合法的程序输入时问题更突出。本文提出一种基于马尔可夫链蒙特卡洛（MCMC）的新采样框架，同时满足三大核心要求：约束满足（每个样本均满足约束）、单调收敛（采样过程收敛到真实条件分布）和高效性（高质量样本在少数步骤内出现）。该方法构建有效输出上的提议分布，并基于语言模型的似然应用梅特罗波利斯-哈斯廷斯接受准则，实现对约束空间的合理且高效的探索。实验表明，该采样器在合成基准和真实程序模糊测试任务中均显著优于现有方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。