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

Emmanuel Anaya Gonzalez, Sairam Vaidya, Kanghee Park, Ruyi Ji, Taylor Berg-Kirkpatrick, Loris D’Antoni · 2025

Read Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective by Emmanuel Anaya Gonzalez, Sairam Vaidya, Kanghee Park, Ruyi Ji, Taylor Berg-Kirkpatrick, Loris D’Antoni (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-05754.txt.

Introduction

Emmanuel Anaya Gonzalez and co-authors sample from language models under hard rules with a Markov chain method, in work from twenty twenty-five. Constrained decoding forces outputs to obey strict validity rules. Past methods warp the model's own distribution while enforcing rules. That warp hurts tasks like fuzzing, which need diverse valid inputs. Three goals are set: validity, true convergence, and speed.

A proposal over valid outputs is built, then filtered by an acceptance rule. The rule weighs model likelihood, in classic Metropolis-Hastings style. Samples thus converge to the true conditional distribution over time. Synthetic benchmarks and real fuzzing tasks test the sampler. It beats existing methods on both fronts in the report. Valid, diverse, and faithful sampling can coexist in one method.

Catalog record

CREATOREmmanuel Anaya Gonzalez, Sairam Vaidya, Kanghee Park, Ruyi Ji, Taylor Berg-Kirkpatrick, Loris D’Antoni
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-05754

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective Emmanuel Anaya Gonzalez, Sairam Vaidya, Kanghee Park, Ruyi Ji, Taylor Berg-Kirkpatrick, Loris D’Antoni Abstract 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. 1 Introduction Language Models (LMs) have revolutionized a wide range of domains, from code generation [ 9 ] to automated reasoning [ 48 ] . Yet, ensuring that their outputs satisfy hard structural constraints—such as syntactic validity in domain-specific languages—remains an significant challenge [ 14 ] . While constrained decoding methods [ 6 , 10 , 15 , 36 , 40 , 41 , 42 , 44 , 35 , 2 , 29 , 46 ] can enforce these constraints, they often distort the underlying generative distribution learned by the model, degrading performance in downstream tasks [ 43 , 34 ] . This tradeoff is particularly detrimental in applications that rely not on a single high-quality sample, but on diverse samples from the constrained distribution. A compelling example is program fuzzing , a technique for discovering software bugs by automatically generating test inputs that explore different execution paths in a program. Modern fuzzers bootstrap this process using a small set of seed inputs, and the effectiveness of these seeds hinges on both their correctness—the seeds should be syntactically valid inputs that the program will not reject—and their distributional diversity—the seeds should exercise different execution paths. LMs offer a powerful mechanism to generate such seeds—but only if we can sample efficiently and faithfully from the constrained distribution. Can we design constrained sampling algorithms that when executed for a given amount of time t are (i) Constraint satisfying: produce a sample within t time and that sample satisfies the constraint; (ii) Monotonically Converging: converge to the true conditional distribution when t goes to infinity; and (iii) Efficient: produce good estimates of the constrained distribution for low values of t ? We answer this question in the affirmative. Focusing on constraints expressed as context-free grammars , we introduce a family of sampling algorithms rooted in Markov Chain Monte Carlo (MCMC) techniques. Our key insight is to construct proposal distributions that generate only constraint-satisfying samples and use a Metropolis-Hastings criterion guided by the LM’s likelihood function to accept/reject candidates. Unlike rejection sampling, every candidate in our method is valid by construction—ensuring constraint satisfaction . Our use of likelihood-aware MCMC transitions ensures monotonic convergence , and crucially, our empirical results reveal that the resulting chains converge efficiently to the desired conditional distribution. We make the following contributions. First, we formalize the desiderata for constrained sampling—constraint satisfying, monotonically converging, and efficient—and show that existing methods fail to satisfy all three ( Section 2 ). Second, we introduce an effective MCMC-based framework for constrained sampling that satisfies all three desiderata and instantiate it with three concrete proposal distributions ( Section 3 ). Third, we validate our approach on both synthetic distributions and real-world fuzzing targets such as libxml2 and sqlite. The samples produced from our approach exhibit better KL divergence from the target distribution than competing approaches. Most importantly, program fuzzers (i.e., automated random testers) seeded with our samples consistently achieve higher code coverage on real-world tasks compared to fuzzers seeded using existing approaches ( Section 4 ). 2 The Ideal Properties of Constrained Sampling In this section, we formalize the problem of sampling from a language model (LM) conditioned on a constraint (i.e., constrained sampling), define our key desiderata of a good constrained sampling algorithm, and describe how existing constrained sampling algorithms do not meet such desiderata. We follow the definitions proposed by Park et al. 2024 . Language Models. An (autoregressive) language model defines a probability distribution P over sequences of tokens (i.e., sentences) w\in\mathcal{V}^{\ast} , where \mathcal{V} denotes the vocabulary. The probability of a sequence is computed as the product of conditional probabilities for each token in the sequence: P(w_{1}\ldots w_{n})=\Pi^{n}_{i=1}P(w_{i}\mid w_{1:i-1}) Constraints and Grammars. Given a LM P and a constraint \varphi , the goal of constrained sampling is to sample sequences that satisfy the constraint. Constraints are typically specified as a language, which could be a regular language, context-free grammar (CFG), or other types of logical conditions that sequences must fulfill. In this work, we focus on constraints that can be defined by a context-free grammar, an expressive and formal way to define sets of valid sequences. For example, context-free grammars can express what programs in a given programming language are syntactically valid and what format a JSON object should abide to when being used to transfer data. While we focus on grammars, the techniques we propose can be applied to other types of constraints. Formally, a context-free grammar \mathcal{G}=(\Sigma,\mathcal{N},S,\mathcal{R}) consists of a set of terminal symbols \Sigma , a set of non-terminal symbols \mathcal{N} , a start nonterminal symbol S\in\mathcal{N} , and a set of production rules \mathcal{R} . A sequence w is a valid sentence belonging to the language \mathcal{L}(\mathcal{G}) if it is derivable from the start symbol S by applying a sequence of rules from \mathcal{R} . Each step in this derivation transforms a string \alpha A\gamma into \alpha\beta\gamma using a rule A\to\beta\in\mathcal{R} , and denoted by \alpha A\gamma\Rightarrow\alpha\beta\gamma . Question 1: Generate a complete and complex sqlite .test file using different Tcl commands. Do not reuse previous solutions. Ensure you write a single .test file without any comments that ends with a "finish_test". Solution 1: set testdir [file dirname $argv0] source $testdir/tester.tcl ... ifcapable journalMode { catchsql {PRAGMA journal_mode=WAL} } {0 {}} finish_test Question 2: Generate a complete and complex sqlite .test file using different Tcl commands. Do not reuse previous solutions. Ensure you write a single .test file without any comments that ends with a "finish_test". Solution 2: (a) Prompt root ::= header test_block_list finish header ::= "set testdir [file dirname $argv0]" "source $testdir/tester.tcl" "set testprefix" identifier "set ::timeout 60000" ( variable_definition ) * ... test_block_list ::= ( test_block ) + test_block ::= do_test | do_execsql_test | ifcapable_block | procedure_definition | conditional_block | tcl_statement do_execsql_test ::= "do_execsql_test" test_name "" sql_statements "" expected_result ... sql_statements ::= sql_statement ( ";" sql_statement ) * ";" ? finish ::= "finish_test" (b) Grammar Figure 1 : (a) Prompt to generate seed test cases for fuzzing the SQLite engine. (b) Simplified version of the SQLite test-script grammar written in EBNF notation. The goal of the problem is to generate multiple diverse seeds that trigger different code paths in the library being tested. Example 0 (SQLite Test-Script Grammar) . Figure 1

Read the complete text