Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective
Authors: Emmanuel Anaya Gonzalez
Sairam Vaidya
Kanghee Park
Ruyi Ji
Taylor Berg-Kirkpatrick
Loris D'Antoni
Venue: NeurIPS 2025 poster ()
Keywords: Language Models
Context-Free Grammars
Markov Chain Monte Carlo
Primary area: probabilistic_methods
TL;DR: This paper presents a lightweight MCMC-based approach for constrained decoding in LLMs

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.

Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective
Emmanuel Anaya Gonzalez! Sairam Vaidya'
Kanghee Park Ruyi Ji²
Taylor Berg-Kirkpatinn
Loris D' Antonii
UCSD
Peking University
(fanayagonzalez, sta.raaaaay..aaaaaaaaaaaaaaaaaya kap022, tberg, jiruy19109877149pkku edu. cn
Iddatt,dattomnii lnl.ntooinn...m Jucsdd edu
Abstract
Constrained decoding enables Language Models (LMs) to produce samples that provably satisfy hard constraints. However, existing constrained-decoding ap- proaches often distort the underlying model distribution, limitation that pecially problematic generate diverse and valid program inputs for testing purposes. We propose 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 the true conditional distribution), and efficient (high-quality sam- ples emerge in few steps). Our method constructs a proposal distribution over Hatropolis-Hasttnge 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
applications like program fuzzing, where one wants to
valid outputs and applies
Introduction
Language Models (LMs) have revolutionized a wide range of domains, from code generation [12 to automated reasoning (59]. Yet, ensuring that their outputs satisfy hard structural constraints such as syntactic validity in domain-specific languages remains a significant challenge [18]. While constrained decoding methods [9]
13
19
45
50
52
53
55
44 2 36 57] can enforce these
constraints, they often distort the underlying generative distribution learned by the model, degrading
performance in downstream tasks (44 43
This tradcoff is particularly detrimental in applications that rely not on a single high-quality sample, but diverse samples from the constrained distribution. A compelling example is program frogramfuczing, technique for discovering software bugs by automatically generating test inputs that explore different execution paths in program. Modern fuzzers bootstrap this process using small set of seed inputs, and the effectiveness of these seeds hinges on both their correctness- seeds should be syntactically valid inputs that the program will not reject-and and their distributional diversity the seeds should exercise different execution paths. LMs offer powerful mechanism to generate such seeds-but only if we 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 sample within t time and that sample satisfies the constraint; (ii)
"Equal contribution.
Code available
http:/itwwb..c///aggggeoeereoeee models/cam casa
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Monotonically Converging: converge to the true conditional distribution when 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 Sestropolis-Hasttine 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 ensures monotonic convergence, and crucially, our empirical results reveal that the resulting chains converge efficiently to the desired conditional distribution.
MCMC transitions
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 ( Second, we introduce an effective MCMC-hased framework for constrained sampling that satisfies all three desiderata and instantiate 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 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. [3
Language Models. An (autoregressive) language model defines probability distribution P over sequences of tokens (i.e., sentences) w V*, where V denotes the vocabulary. The probability of sequence is computed as the product of conditional probabilities for each token in the sequence:
P(w1... ... w.) = II P(w; w1=-1)
Constraints and Grammars. Given LM P and a constraint y, the goal of constrained sampling is to sample sequences that satisfy the constraint. Constraints are typically specified as 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 constraints that can be defined by context- free grammar, an expressive and formal way to define sets of valid sequences. For example, context-fiee grammars express what programs in 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 other types of constraints.
set of terminal symbols Σ, a set of non-terminal symbols N, start nonterminal symbol S E N, and set of production rules R. A sequence w is valid sentence belonging to the language L(g) if is derivable from the start symbol S by applying sequence of rules from R. Each step in this derivation transforms string aAy into aBy using a rule A + 3 e R, and denoted by aAy + aBy
Formally, a context-free grammar 9 = (E,N, S, R) consists
Example 1 (SQLite Test- Sestiptript Grammar). Figure 7 Iillustrates a typical use-case: we ask a language model to generate SQLite regression test files (. test) that drives the SQLite engine down as many distinct execution paths as possible (Figure Tap. To exercise a specific component of the database, each file must satisfy the syntactic and semantic restrictions encoded in the SQLite test-script grammar shown in Figure e.g. the file should include a mandatory timeout directive set ::timouut 60000 in the header and well-formed do execsql_test blocks that wrap one or more SQL statements in braces and specify an expected result.
A complete derivation therefore starts from the non-terminal root, transforms (i.e., using =) into header test, block_looliieeeocccll finish, and continues recursively until only quoted terminals remain. (See Appendix E.2 for a condensed parse tree.)
2

---

Question Generate complete complex sglite test file using different Tel comnanda. Do not reuse previous aolutions. Enaure you write single teat file without any commenta that ends with "fimish_test",
::- headar teat_block, list finish
"set testdir [file dirnane $argvō]*
"aource #teatdir/teste:: tel"
Solution
"set testprefix' identifier
set testdir [file dirname Sargv0]
"set :itineout 60000" variable_defiimttion))
source $testdir/tester..e
ifcapable JournalMode
bast_blockklist (test_bbocck-
catchaql (PRAGMA puurnal_made-iAli } [o (3} finieh_teat
test_block ::= do_test do_execaql_
ifeapable_ block deiittureddefiiitionn
conditionsl_ besenallblocc tcl_etatenent
do ex.eexcolltsst ::-
Question Gemerate complete complex sqlite test file using different Tel comnanda. Do not reuse previous solutione, Ensure you krite single .test file without any
"to_arecaql_test"
aql_statenente expected_reault
that enda with "Finish_test"
atatenentt ::2
sql_etateeent (";" "ql_"sllaaae sql_statement) ";"?
Solution
finish "finich_test"
(a) Prompt
(b) Grammar
Figure I: (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.
Grammar-Alligned Sampling. Grammar- sampling aims to sample sequences from P that belong to the language L()), while preserving the model's underlying distribution. This can be viewed as sampling from the constrained distribution pe, which is proportional to the original model distribution but restricted to sequences that satisfy the constraint. Mathematically, for a given grammar G and model P, we want to sample from
1[ E C(G) P(w)
(w) ENe [w' L(9)) P(w")
2.1 Limitations of Existing Approaches
Rejection Sampling. A common method for obtaining constrained samples from a language model is rejection sampling, which repeatedly draws outputs from the model and discards ones that do not satisfy the constraint. While samples accepted via this process correctly follow the language model's distribution conditioned on the constraint, there is guarantee how many samples one needs to reject before getting a sample satisfying the constraint. This inefficiency becomes especially pronounced when the constraint describes pattern that is infrequent not naturally favored by the model's 's learned distribution, often requiring many rejections before valid sample is drawn. For example, for the problem in Figure [1 out of 500 samples produced by Llama-3. 1-80--8BB-- Instruct, only 2 (0.4%) satisfied the constraint imposed by the grammar.
Constrained Decoding. The inefficiency of rejection sampling has led to constrained decoding algorithms (50 9 19 that at each decoding step evaluate the LM next tokens against the specified constraints. Invalid tokens that cause the generated sequence not satisfy the given constraint are masked from the probability distribution, forcing the model to select tokens that will lead to constraint-ssatifsiing sequences. In particular, when the constraint is context-free grammar, the technique is known as Grammar-Constrained Decoding (GCD) 19
As shown by Park et al. 43), constrained decoding does not preserve the underlying distribution of the model. we define the prefix language Cpreax = (w e E' we E L(G) of a grammar & the set containing all possible prefixes of sentences in the grammar's language, the distribution captured by GCD is the following incorrect conditional distribution:
P(w; W 1) 1 1w Lprefix (9)
@e w1:-1) Σn::
P( w1x-1) [W1s-1, w/ E (gre
For example, for the problem in Figure 1 regardless of how many samples one generates using GCD with Ll 3. 1.ma--.1-880 1-.1--8-Tia Instruct the empirical KI. divergence from the sample distribution to Pg does not decrease.

---

If we assume that the LM is good at sampling good seeds for fuzzer, this unfaithfulness to the target distribution results in worse samples that cover fewer code paths (as shown in Section 4.2
Adaptive Sampling with Approximate Expected Futures (ASAp). Park et al. [43] showed how to correct next-token conditional distribution for grammar-aligned sampling using the notion of Expected Future Grammaticality (EFG), defined as c(W1:) = Bp( [) [w [(])]-ii.e. the probability that sampling a continuation of the prefix wi: will lead to a valid sequence in the grammar. The conditional probability required by Hammaar-aligned sampling can be then written as:
P(w; wis- c(wr::)
p9 (w: W Ew: P(uy w1=-1) -- c(wis-1,, w()
Park et al. 43 proposed Adaptive Sampling with Approximate expected futures (ASAp) to approxi- mate grammar- -aligneddddddddddd-- sampling. ASAp iteratively overapproximates expected future grammaticality by removing probability mass associated with invalid prefixes identified from previous samples. While in the limit this approach reaches the desired distribution, it does not do so monotonically-iia it can produce intermediate EFG approximations that are very skewed. Park al. 43 empirically showed that it can take thousands of samples for ASAp to start converging, making the algorithm practically not efficient. For example, for the problem Figure 100 samples generated using ASAp with Llama-3. Instructt exhibited worse empirical KL divergence from p9 than even GCD!
2.2 Desired Properties of a Grammar-Alignan Sampler
We formulate properties we claim good constrained-samplinn algorithm should satisfy. Because convergence in the limit is impractical, we assume that an algorithm S' is given a finite amount of time to produce a sample, and we want the algorithm to satisfy three properties:
Constraint Satisfying: produces a sample within time and that sample satisfies the constraint;
Monotonically Converging: the total variance distance between the output distribution of S and the target distribution pe monotonically decreases and converges to 0 as t approaches infinity; Efficient: S produces good estimates of the constrained distribution for low values of t.
By focusing on these properties, we aim to provide a sampling approach that balances efficiency, reliability, and correctness, addressing the shorteomings of existing methods, which fail achieve all three goals simultaneously. In Section 3 we present our MCMC-based approach for constrained decoding, which provably guarantees the first two properties and is in practice efficient (Section { During the development of this work, concurrent research [38] 377 has introduced sequential Monte Carlo algorithms that also align with our desiderata. We empirically evaluate their performance in Section 4 and discuss how they relate to our approach in Section 5
3 Grammar-Aligned MCMC Sampling
We propose a constrained sampling framework based on Markov Chain Monte Carlo (MCMC) that operates strictly within the space of grammar-valid sequences. Rather than relying rejection of ungrammatical outputs, our method uses grammar-constrained decoding (GCD) to iteratively refine samples through local proposals that are always constraint-satiifyinng GCD. This framework provides a principled mechanism to balance computational cost and sampling fidelity: the chain progresses, it converges toward the true commar--lligner distribution. Intuitively, our approach uses MCMC to turn any GCD implementation into a grammar- -ligned sampler.
property guaranteed by
3.1 Constrained Generation via Metropolis-Hastingg
We use the Metropolis- Hastinns algorithm 23 standard MCMC method, to construct a Markov chain whose stationary distribution matches a desired target æ over a set of states S. Given a proposal distribution g(y) r). which defines how to sample candidate state y from a current state x, the algorithm accepts the proposed candidate with probability a<x,, y), defined as:
o(r,y) = min { <1))(x y)
(2)
x<)g(V xx)

---

Algorithm 1: The Metropolis-Hastinn algorithm instantiated for grammar-aligned sampling.
Data: the LM P, the grammar G, parameter l denoting the chain length, and configurable distribution Pros for sampling a random prefix from a given sequence.
Result: a proposed sequence s'.
We t a GCD sample;
8 Function Propose (w):
2 foreach i 1. ... do
9 f- index sampled from prosi
w < Propose (w:-1);
w" + Wi:i
a f a w);
11 return GCD sample with the prefix w":
b < Bernoulli
b then wi + w else wi f- w;-1;
return wks
This acceptance rule compares how likely is under the target distribution to how likely is, adjusted by the relative likelihood of proposing each direction, q(x y) and q(y xx). Intuitively, proposals that improve the target probability are usually accepted, while worse ones are accepted with a controlled probability to maintain exploration. The acceptance rule ensures detailed balance- property that guarantees the target distribution is stationary for the Markov chain-which in turn ensures that the chain will converge to the desired distribution over time.
Alg. presents our instantiation of the Cetropolis-HHastinge algorithm for grammar- aliignd sampling, where the target distribution is the constrained distribution pe (w). The algorithm starts with random GCD sample (Line 1) >>-wich is guaranteed to be constraint-satisfyy the target distribution p9 (w) by running the constructed Markov chain for steps (Lines 2-7). In each step, the algorithm simulates the Markov chain by first drawing new sample from the proposal distribution (Line 3) and then accepting it with probability (ww;-,, (Lines 4-)). Finally, the last sample is returned as the result (Line 8).
and refines it toward
One important point to note the computation of the acceptance probability a(w;- w²) (Line 4), whose definition relies on the target probabilities ps (w:-1) and (w")), However, these probabilities are difficult to compute practice because their normalization factor Σn 1[ E C(g)) P(w") requires summing over the whole language, which is typically intractably large. Fortunately, this factor cancels out from the acceptance probability after unfolding the target probabilities, as shown below, which induces efficient implementation for the function o:
alw, w') = min {
pG ((())((]] ( min 1, p9 (w)q(ww ww)
1 Iw' e C(G))- q(w w()
11 [[ E [(G)] P(w)) g(w" w)
The last component in Alg. is the proposal distribution (Line 3). The Metropolis- Hasttins algorithm offers considerable flexibility in this distribution any choice satisfying some mild conditions (i.e., irreducibility and aperiodicity) can yield a theoretically sound sampler. Hence, we propose a parameterized family of proposal distributions for grammar-alignesr sampling to fit different scenarios (Lines 9-12), which we elaborate on Section 3.2
3.2 Proposal Distributions for Grammar-Aligned MCMC
The performance of MCMC for grammar-aligned sampling is tied to the proposal distribution. Different proposals make different trade-offs: some are simple to implement but mix slowly, while others complex ones may offer faster convergence. There is no single best choice across all settings.
In this section, we present a parameterized family of proposal distributions that (i) tailored to sequences generated by a language model, and (ii) maintains constraint satisfaction by construction. As shown Lines 9-12 of Alg. the proposal mechanism operates by selecting prefix of the current sequence and resampling the remainder using GCD. Given sequence w and a distribution Pios over the token positions [o. |w]]. we sample an index i from plas and extract the prefix Wi;i- A new candidate w/ is then generated by running grammar- conntarn-nn decoder (GCD) conditioned on this prefix. This strategy allows local, structured edits while ensuring that every proposed sequence remains within the constrained language. For example, consider a grammar describing only sequences of and is and let's assume GCD has produced the sequence 01001. Our MCMC algorithm can sample any prefix of this sequence, let's 'ss say 010, and produce from it continuation using GCD, e.g..
5

---

it could produce the sequence 01011111. Whether the new sequence will be accepted depends on the likelihood of the two sequences according to the LM.
Under this framework, we prove Alg. exhibits the desired properties a grammar-aligned sampler satisfying both the constraint satisfying and monotonically converging properties (Sec. 2.2) if the truncation distribution pros always assigns non-zero probability to the empty prefix (Appendix F).
To conclude this section, we describe three concrete instantiations of this framework, each corre- sponding to a different choice of prefix distribution, Pros
Uniform. This proposal distribution samples truncation point uniformly at random from the positions in the current sequence -ie., Pras is the uniform distribution. This proposal creates local moves that preserve partial structure while allowing for diversity in continuations.
Priority. This proposal biases the truncation toward parts of the sequence where the model is uncertain or poorly aligned with the grammar, enabling targeted refinement of weaker regions. We use perplexity, a common measurement of uncertainty, to carry in this bias and the truncation distribution Pros to the LM's token-level perplexity, i.c., Pros (i) x PP(P(-] w):)). In this way, positions with higher uncertainty will have a greater probability be resampled.
The simplest proposal always discards the current sample and generates a new one from scratch using GCD Pros selects position 0 with probability 1. Since the proposal is independent of the current state, this reduces to resampled importance sampling [14].
Restart.
4 Experiments
In this section, we show that MCMC yields better samples than existing approaches in a compute- matched setting. In Sec. 4.1 we demonstrate empirically that MCMC converges to p9 using fewer samples on constrained generation benchmarks proposed in Park et al. [43] and Lipkin et al. (37]. In [Seecc. 4.2 we show that MCMC, when compared to alternative sampling techniques, improves the quality of seeds needed to bootstrap fuzzing algorithms.
For the alternative sampling methods, we compare against vanilla GCD 199 ASAp 43 and
SMC+AWRS (38 (37, a recently proposed constrained sampling algorithm that has goals similar to ours. SMC+AWRS performs Sequential Monte Carlo on particles (sequences), each of which is extended using token-level adaptive rejection sampling; we compare this setting to running MCMC for steps. In addition, also evaluated the performance of rejection sampling in all of these domains, but found it exhibits impractically low acceptance rates (<1%), so we do not report it as baseline in evaluation. The main text presents results for Llama-3. --SB-Instruct; additional models are evaluated in Appendix [ and Appendix E. We implemented our MCMC framework as an extension of the Transformers-Gie GAD library 43
4.1 Domain-Speeific Constrained Generation
We first evaluate the different sampling methods on four grammar-constraing generation tasks proposed by Park et al. [43 and Lipkin et al. [37 From 43 two of our tasks involve synthesizing expressions in an extension of linear integer arithmetic (SLIA) and loop invariants with bit-vector arithmetic (BV4). The problems are expressed as Syntax-Guidee Synthesis problems (SyGuS) 4, a standardized format where logical specification and context-free grammar of first-order terms are provided and the goal is to synthesize a term the grammar that satisfies the specification. The prompts consist of 3 in-context examples of the form [specification, solution] and the grammar is then provided as a constraint for alimaar-aligned sampling. Our third task is the constituency parsing (CP) task already used in prior GCD work [19] where the grammar is used to help the model produce well-parenthesizer parse trees for English sentences. For our fourth domain, we draw the Molecular Synthesis (MS) task from (37), where the objective is to generate drug-like compounds in the SMILES format from in-distribution examples. In total, our evaluation set contains 15 SLIA problems, 14 BV4 problems, 6 CP problems and MS problem.
We run all sampling techniques and compare them a compute-matched setting, each with a budget of n generated sequences for sample, for E [1...., 10). We write MCMC-T (k n) to denote the final sample after running MCMC with proposal distribution TE [Uniform, Priority, Restart) for steps. Similarly, we write ASAp (k = n) to denote sample from the distribution learned

---

find bvage, byneg
A54a SMC--AWRS
Divergeence
GCD
SMC AWWIR /MMMC
DCM.-trdlem (+)
VCW Piorly ont VCW Restan
(compute)
(compute)
(a)
(b)
Figure 2: (a) KI. divergence of different sampling methods, on a representative SYGUS task. (b)
Geomean ratio between KI. divergence of MCMC vs SMC, across all tasks (> is better).
after having observed samples. Finally, SMC+AWRS (k n) denotes a Particle Filter run with particles, and a final resample step to obtain single, final sequence.
Measures. An ideal measure to compare sampling approaches the distance between the sample distribution and the target p9, It is, however, impractical because can neither ex- haust the infinite sequence domain nor evaluate any probabilities in ps. Therefore, we fol- low Park et al. 43 to use approximate measure instead, which is the KI. divergence to the LM distribution on the finite set all observed samples. This approximation aligns well to the ideal measure because the LM's distribution P' is proportional to the target ps on valid samples:
pi log P -Epo log
po
pe =E log pe
log (
C-P4
log C, where pG denotes the sample distribution, and
constant.
For each individual task, MCMC variant, and number of steps, we obtain 100 samples and use bootstrapping [16] report mean KL divergence and 95% confidence interval. We do analogously for AS and SMC+AWRS.
Results and Findings. Figure 2a illustrates how the KL divergence for our MCMC approaches monotonically decreases with the number of steps for representative problem from the SYGUS benchmark (the other tasks show similar trends). The KL divergence decreases and converges in trend for all variants of MCMC, though with some fluctuation caused by randomness. Nonetheless, for any given number of steps, MCMC samples are always closer in distribution to p9 than GCD, All variants of MCMC display large reductions in KI. divergence with respect GCD handful of steps (at 3 steps: geomean. 1.57 reduction for Uniform, 1.79x for Priority, and 3.10x for Restart; at 10 steps: geomean. 2.11x for Uniform, 2.42x for Priority, and 5,07 x for Restart).
after
In contrast, although ASAp also converges to p9 in the limit, it does not exhibit monotonic con- vergence, and in practice it yields worse KL divergence than GCD in many cases. For this reasong, larger reductions are observed on average when comparing MCMC to ASAP for the same number of steps (at 3 steps: geomean. 1.86x reduction for Uniform, 1.98x for Priority, and 3.36x for Restart; at 10 steps: geomean. 2.25 x reduction for Uniform, 3.53x for Priority, and 5.42x for Restart).
SMC+AWRS also displays convergence to the target distribution. Interestingly. it tends to perform worse than GCD with a small number of particles (< 3); this might be an artifact of the AWRS token-level sampler since, in theory, when using the standard token-masking approach, SMC (k- 1) equivalent to GCD, as is the case for MCMC (k = 1) and ASAp (k 1). All variants of MCMC display better performance than SMC+AWRS in low-compute regime (n < 5), whereas the latter overtakes MCMC-Uniform when more generations are allowed. This trend illustrated in Figure 2b Points above y 1 indicate that the corresponding MCMC variant results in lower KL divergence for the same number sequences used. MCMC- MCMC-Priority and MCMC-Restar outperform SMC+AWRS for the evaluated compute (> 1.1x and 1.7x, resp.).
Across tasks, MCMC-Restanl consistently exhibits better quality of approximation than the rest of the sampling methods for equivalent compute, including MCMC-Unifore and MCMC-Priorts This
7

---

is a notable result, since MCMC- does not accumulate any information about previous states in the Markov Chain random walk.
4.2 Fuzzing experiments
eiverage-guidet fuzzing [10] iteratively mutates seed inputs to randomly generate test cases that exercise as many exccution paths as possible a target binary (a practice that can often reveal bugs in the code under test). The quality of the initial seed caapuuspartiiulaatt their structural validity and diversity- can significantly impact downstream coverage, i.e., how many execution paths the fuzzer exercise [44] In this section, evaluate whether different techniques for wrammar-constrainge sampling can be used to produce high-quality seeds for a satt--of-the-ane program fuzzer, AFL++ [17]. In our experiment, the grammar is used to guarantee that the LM produces inputs for the library under test that are valid (they will not be immediately rejected by the program) and can trigger execution of specific components of library (e.g, forcing the SQLite timeout directive).
Benchmarks. We evaluate our approach on two widely adopted, grammar- intennsie- targets: XML (using the libxml2 parser (56)) and SQL (using the SQLite engine 25.). To reflect realistic use cases where general user prompt remains fixed while grammar constraints evolve to target different code components, we employ one high-level prompt per library (e.g., the one in Figure [a] and introduce domain-specific constraints that can trigger different code components directly into the grammar. Our grammars are specializations of publicly available EBNF grammars for XML and SQL [22 21 62] For XML, we modify the grammar to enforce mandatory <!ENTITY> and <! ELEMENT declarations within the DOCTYPE, while for SQL we mandate set timmouu 60000 directive within each test file. A snippet of the grammar we use to test the SQL engine is given in Figure [Trre[[baaam the full list of targets, versions, and seed formats is given in Appendix EI.] A user of the fuzzer can modify these grammars to stress test different components of the software under test.
Mcasures. Aside from the KL divergence, which we measure in the way discussed in Section 4.1 we want to measure whether a better sampler leads to the fuzzer having higher branch coverage- -.e., the number of unique executed code branches over the total number of branches in the software under test (computed via LLVM instrumentation
We evaluate our methods across two dimensions: seed quality and computational budget. First, to assess seed quality, we generate 100 seeds per method, using GCD, ASAp: SMC+AWRS, MCMC- Priority, MCMC-Restart, and MCMC-Uniform with varying number of steps (k E {2,5. 10)). Second, to evaluate the trade-off between seed quality and quantity, we vary the number of initial seeds (N E (50, 100, 200, 500}) for compute-matched comparisons- since MCMC with A = 10 takes approximately 10x longer per seed than GCD, can compare how fuzzing coverage varies when using 50 MCMC seeds versus 500 GCD seeds generated in the same amount of time.
We also include bascline Grammarinator (26), fuzzing tool for generating random strings in a grammar that does not use LMs. For these benchmarks, rejection sampling exhibits impractical acceptance rates (<1%) (Appendix (E.6) and we therefore exclude it from our comparison as it would take more than 10,000 samples to produce 100 valid seeds.
We describe the full fuzzing protocol in Appendix E.4 In summary, for every benchmark and method, we generate N E (50, 100, 200, 500] seeds for AFL++ and run it for 6 hours (in this time AFL++ generates thousands of new inputs based on the seeds and executes the software on them). We then measure mean branch coverage at different time steps with bootstrapped 95% confidence intervals over five independent 6-hour-long fuzzing trials, following standard fuzzing-evaluation protocols 31).
Findings. We present representative results for the SQL benchmark using Llama-3.. 1.a.-3..------ttuute (full results in Appendix E..1). Figure 3a illustrates how the KL divergence changes at different steps in similar way as observed in Section 4.1 for synthetic benchmarks decreases and converges in trend for all variants of MCMC, though with some fluctuation caused by randomness.
The key result is given in Figure 3b To avoid Fluuter,Figuuee B only reports the results for MCMC when run for 10 steps (the versions for 2 and 5 can be found in Appendix E.8 and E.10).
8

---

NCMCAU form
MCMC oNi
NCMCR DN ASSA 0-)
SMC-AABRS 363
KL (LDveggence
GCD
Coverage
200
(32)
MCNC- Prienty
306
ASAo
(1.)
(compute)
Time (soconds)
(a) divergence
(b) Branch coverage
Figure 3: SQL benchmark: (a) KL divergence for different sampling methods. (b) Branch coverage over time (100 sceds, 6-hour runs).
Fuzzing using seeds produced via MCMC and SMC+AWRS leads to significantly higher branch coverage than Grammarinator, GCD, and ASAp. Grammarinator, relying solely on grammar, achieves the lowest coverage, followed by GCD and then ASAp. Among all approaches, MCMC-Priority (ks = 10) is the most effective, delivering branch coverages of 36.69% on SQL and 12.79% on XML- corresponding gains of 1.17x and 1.15x over GCD (31.52%, 11.08%) and 1.12x and 1.13x ASAp (32.61% %, 11.30%) on the SQL and XML benchmarks, respectively. SMC+AWRS (k = 10) achieves competitive performance with 36.44% SQL and 12.63% on XML., demonstrating 1.14x and 1.13x gains over GCD while remaining 1.04x below to MCMC-Priority.
This result underscores the benefit of MCMC in diversifying the kind of samples an LM can produce. As expected the versions of MCMC with (k = 5) provide coverages that are lower than at (k 10), but higher than GCD; at (k 2) the coverage is quite similar that of GCD.
Intriguingly, the MCMC methods coverage ranking (Figure 3b) is inversely mirrored by their KL divergence from the true conditional grammar-conse conttarr-onttriieedd distribution (Figure Ba), though the overall differences are relatively minor. This phenomenon suggests that while LMs provide a strong foundation for producing diverse outputs, approaches like MCMC-Priority may be better at exploring "variants" of the same output, which in turn are better for exercising branch coverage fuzzing.
Since MCMC with = 10 takes approximately 10x longer than GCD per seed (Appendix F..)) we compared MCMC with 50 seeds against GCD with 500 seeds (compute-matched), Remarkably, MCMC-Priority with just 50 seeds achieved 34.48% coverage on SQL, surpassing GCD with 500 seeds 31.70% (see Appendix E.8 for complete results across all models). This experiment demonstrates that sampling fidelity dominates sheer quantity for fuzzing effectiveness, likely because high-quality diverse seeds enable the fuzzer to explore more productive regions of the input space and avoid wasting time mutating low-quality seeds.
In summary, the results support the claim that MCMC-based constrained sampling monotonically converges to the desired distribution, and convergence is indicative of higher coverage in fuzzing.
Related Work
Grammar-Alignee Sampling. Several recent works have emphasized the importance of sampling multiple outputs from LMs to approximate the model's 's distribution [29 48 43 However, when hard
constraints are introduced, typical decoding strategies like top-k, nucleus, or beam search become unreliable estimators of the constrained distribution.
Park al. 43 introduced the ASAp approximate the true constrained distribution, which it has been studied further by Melcer et al. [2]. However, these methods are slow to converge, requiring thousands of samples, and therefore inefficient in practice.
introduces alternative Monte Carlo and resampling algorithms for correcting the distortion problem induced by locally constrained decoding. Ahmed et al. [ takes a three-step approach of first obtaining an unconstrained (and unbiased) sample, project to constrained space via psendolikelihood function, and finally apply resampled importance sampling to correct for bias.
Recent work 3 37 38

---

Loula et al. [38] combine Sequential Monte Carlo and Importance Sampling to enforce not only local constrains, but also semantic constraints via expensive potentials that cannot be evaluated incrementally. Both SMC and MCMC are theoretically guaranteed to produce samples from the target distribution as the number of particles or steps, respectively, goes to infinity, but neither directly reduces to the other in the general case. From the implementation perspective, in SMC, the number of particles needs to be fixed beforehand and all must be kept in memory during execution, whereas MCMC is an anytime algorithm, and only a single, complete sequence is maintained at all times.
Lipkin al. [37 presents token-level adaptive rejection sampling algorithm (AWRS) which, combined with SMC sequence sampling, yields strong baseline for constrained generation. The AWRS sampler can be integrated other constrained generation algorithms including MCMC; we leave the details and further analysis as future work.
Controlled Generation. A large body of work has investigated constrained decoding methods that modify the bakknnby-tooen decoding process of LMs to enforce syntactic or lexical restrictions. or context-free grammars As discussed Section 2.1
These constraints are often specified using regular languages 41
58
(CFGs) 9 13
19
45
50
53
55
36
28
39
46
and as observed by Park et al.
43 many approaches that enforce constraints incrementally distort
the LM distribution and do not converge to the target constrained distribution.
Gradient-based sampling methods [5] 32 35 47 offer a softer alternative, guiding generation toward constraint satisfaction by using relaxed, differentiable surrogates. These methods are better suited for soft or semantic constraints but still suffer from inefficiency and are not guaranteed to produce constraint-satisfyinn outputs.
Methods such as Go [60] and Ctrl-G 61 combine autoregressive language models with Hidden Markov Models (HMMs) to guide generation based constraints. These techniques specifically designed for constraints that can be represented as deterministic finite automata (DFA). Given a prefix, pretrained HMM is used to approximate the probability that subsequently generated suffix will satisfy the DFA constraint, effectively estimating the likelihood of a valid continuation. However, this approach is limited to DFA-representable constraints and cannot be easily extended more general grammars like context-free grammar. Furthermore, these methods require training separate surrogate models. Crucially, they also do not guarantee convergence to the ideal distribution, a limitation they share with other techniques that use approximate inference for intractable conditional distributions (e.g., Feynman- -ac Transformer Models) 47
Proposal Distributions. Our work implements vanilla Metropolis-Haste Hastinggs sampler with proposal distributions that arise naturally from the autoregresive nature of language models. Related ideas from the literature on sampling form energy-based models 49 33 could yield further improvements. Proposal distributions that leverage infilling [8) the constraining grammar, or learning [5l] seem promising to incentivize exploration of more promising regions sequence space. Further perfor- mance improvements are applicable to MH when the proposal distribution is independent from the current state 77), as is the case with our MCMC-Restar variant.
6 Conclusion
We introduced simple yet effective MCMC-based framework for constrained decoding. Unlike prior approaches that suffer from slow convergence or rely on inefficient rejection sampling, our method directly samples from within the constrained space while asymptotically preserving the target distribution defined by the LM. Our framework leads to practical improvements in real-world applications where sampling diverse inputs is crucial most notably, program fuzzing, where high- quality diverse samples translate into higher code coverage.
Our evaluation spans program synthesis benchmarks (SLIA, BV4, constituency parsing) and two grammar-ing inteenivveeeeivveeeeee fuzzing targets (libxml2 and SQLite), each with one high-level prompt per task. While we find consistent trends across different language models and extended 6-hour fuzzing runs, broader evaluation across additional domains (e.g., protocol parsers, configuration languages) and longer campaign durations (24+ hours) would further strengthen generalizability claims. While we study three MCMC proposal distributions, our framework opens the door for exploring richer proposal mechanisms and integration with other decoding strategies.
10

---

Acknowledgments
This work was supported in part by a Microsoft Faculty Fellowship: UCSD JSOE Scholarship; Google's s Gemma Academic Program GCP Credit Award; and NSF under grants CCF-2422214 CCF-2402833 and CCF-221 1968. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors, and do not necessarily reflect the views of the sponsoring entities. Loris D' Antoni holds concurrent appointments as Professor at the University of California San Diego and as an Amazon Scholar. This paper describes work performed at the University California San Diego and is not associated with Amazon. The authors deeply thank Nadia Polikarpova for her insightful feedback and guidance during the development of this project.
References
[1] 2025. -lvm-cov-ent - coverage information. 1lvm-cov.
[2] Lakshya A Agrawal, Aditya Kanade, Navin Goyal, Shuvendu K. Lahiri, and Sriram K. Raja- mani. 2023. Monitor-guided decoding of code lms with static analysis of repository context In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10- 16, 2023.
[3] Kareem Ahmed, Kai- Kai-Wei Chang, and Guy Van den Broeck. 2024. Controllable generation via locally constrained resampling
[4] Rajeev Alur, Dana Fisman, Saswat Padhi, Rishabh Singh, and Abhishek Udupa. 2019. Sygus comp 2018: Results and analysis
[5] Afra Amini, Li Du, and Ryan Cotterell. 2024. Structured voronoi sampling. Advances in Neural Information Processing Systems, 36.
[6] Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016. Guided open vocabulary image captioning with constrained beam search. arXiv preprint arXiv:1612.00576.
[7] Yves F. Atchadé and François Perron. 2005. Improving on the independent metropolis-hastings algorithm Statistica Sinica, 15(1)33-18
[8] Mohammad Bavarian, Heewoo Jun, Nikolas Tezak, John Schulman, Christine McLeavey, Jerry Tworek, and Mark Chen. 2022. Efficient training of language models to fill in the middle
[9] Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. 2023. Prompting is programming: A query language for large language models Proc. ACM Program. Lang.. 7(LDD)).
[10] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coverage- based greybox fuzzing as markov chain, In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '1,, page 1032-1043, New York, NY, USA. Association for Computing Machinery.
[11] Marcel Böhme, László Szekeres, and Jonathan Metzman. 2022. On the reliability of coverage based fuzzer benchmarking In Proceedings of the 44th International Conference on Software Engineering, ICSE '22, page 1621-1633, New York, NY, USA. Association for Computing Machinery.
[12] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer,
11

---

Peter Welinder, Bob McGrew, Dario Amodei. Sam McCandlish, llya Sutskever, and Wojciech Zaremba. 2021. Evaluating large language models trained on code. CoRR, abs/2107.03374.
[13] Yihong Dong, Xue Jiang, Yuchen Liu, Ge Li, and Zhi Jin. 2022. Codepad: Sequence-based code generation with pushdown automaton. arXiv preprint arXiv:2211.00818
[14] Arnaud Doucet, Nando de Freitas, and Neil Gordon. 2001. Sequential Monte Carlo Methods in Practice. Springer.
[15] Rick Durrett. 2010. Probability: Theory and Examples, 4th Edition Press.
Cambridge University
[16] B. Efron. 1979. Bootstrap Methods: Another Look at the Jackknife The Annals of Statistics, 7(1):1-2 26.
[17] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. 2020. AFL++ Combining incremental steps of fuzzing research In 14th USENIX Workshop on Offensive Technologies (WOOT 20). USENIX Association.
[18] Saibo Geng, Hudson Cooper, Michal Moskal, Samuel Jenkins, Julian Berman, Nathan Ranchin. Robert West, Eric Horvitz, and Harsha Nori. 2025, Jsonschemabench: A rigorous benchmark of structured outputs for language models
[19] Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023. Grammar constar--on decoding for structured task without finetuning, In Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing, Singapore. Association for Computational Linguistics.
[20] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, et al. 2024. The Llama
3 herd of models
[21] W3C XML Core Working Group. 2009. Namespaces in xml 1.0 (third edition).
https
/www.w3. org /ts//RRxmlll names/
[22] W3C XMI. Working Group. 2008. Extensible markup language (xml) 1.0 (fifth edition). https://www w3. otg//R//mll x//
[23] W. K. Hastings. 1970. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(19977-109
[24] Adrian Herrera, Hendra Gunadi, Shane Magrath, Michael Norrish, Mathias Payer, and Antony L. Hosking. 2021. Seed selection for successful fuzzing Proceedings the the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2021, page 230-243, New York, NY, USA. Association for Computing Machinery.
[25] D. Richard Hipp. 2000.
Sqlite
[26] Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2018. Grammarinator: grammar- based open source fuzzer In Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, A-TEST 2018, page 45 48, New York, NY, USA. Association for Computing Machinery.
[27] Chris Hokamp and Qun Liu. 2017. Lexically constrained decoding for sequence generation using grid beam search. arXiv preprint arXiv:1704.07138
[28] J Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. 2019. Improved lexically constrained decoding for translation and monolingual rewriting. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 839-850.
[29] Linghan Huang, Peizhou Zhao, Huaming Chen, and Lei Ma. 2024. Large language models based fuzzing techniques: A survey
12

---

[30] Binyuan Hui, Jian Yang, Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Lei Zhang, Tianyu Liu, Jiajun Zhang, Bowen Yu, Keming Lu, Kai Dang, Yang Fan, Yichang Zhang, An Yang. Rui Men, Fei Huang, Bo Zheng, Yibo Miao, Shanghaoran Quan, Yunlong Feng. Xingzhang Ren, Xuancheng Ren, Jingren Zhou, and Junyang Lin. 2024. Qwen2.5-coder technical report
[31] George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018. Evaluating fuzz testing In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communi- cations Security, CCS 18, page 2123-2138, New York, NY, USA. Association for Computing Machinery.
[32] Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. 2022. Gradient-bascl constrained sampling from language models. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2251-2277
[33] John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference Machine Learning, ICML '01, page 282-289, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
[34] Alexander K. Lew, Tan Zhi- Xuan, Gabriel Grand, and Vikash Mansinghka. 2023. Sequential monte carlo steering of large language models using probabilistic programs In ICML 2023 Workshop: Sampling and Optimization in Discrete Space.
[35] Xiang Li, John Thickstun, Ishaan Gulrajani, Percy S Liang, and Tatsunori B Hashimoto. 2022. Diffusion-Im improves controllable text generation. Advances in Neural Information Processing Systems, 35:4328-43433
[36] Yixuan Li. Julian Parsert, and Elizabeth Polgreen. 2024. Guiding enumerative program synthesis with large language models. In International Conference on Computer Aided Verification, pages 280-301. Springer.
[37] Benjamin Lipkin, Benjamin LeBrun, Jacob Hoover Vigly, João Loula, David R. MacIver, Li Du, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Timothy O' Donnell, Alexander K. Lew, and Tim Vieira. 2025. Fast controlled generation from language models with adaptive weighted rejection sampling
[38] João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O'Donnell. 2025. SSntactiic and semantic control of large language models via sequential monte carlo
[39] Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. 2022. NeuroLoggie =eequu decoding: Constrained text generation with lookahead heuristics] In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 780-799, Seattle, United States. Association for Computational Linguistics.
[40] Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2021. NeuroLogic decoding: (un)supervised neural text generation with predicate logic constrrintt) In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4288 4299, Online. Association for Computational Linguistics.
[41] Daniel Melcer, Nathan Fulton, Sanjay Krishna Gouda, and Haifeng Qian. 2024. Constrained decoding for code language models via efficient left and right quotienting of context-sensitive grammars. arXiv preprint arXiv:2402.17988
[42] Daniel Melcer, Sujan Gonugondla, Pramuditha Perera, Haifeng Qian, Wen-Hao Chiang. Yanjun Wang, Nihal Jain, Pranay Garg, Xiaofei Ma, and Anoop Deoras. 2024. AAproxximately aligned decoding
13

---

[43] Kanghee Park, Jiayu Wang, Taylor Brng-Kiikpatrick, Nadia Polikarpova, and Loris D' Antoni. In The Thirty-eighth Annual Conference on Neural Informa-
2024. GGramaar -lagnne- aligned decoding lion Processing Systems.
[44] Kanghee Park, Timothy Zhou, and Loris D' Antoni. 2025. Flexible and efficient grammar- constrained decoding
[45] Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022. Synchromesh: Reliable code generation from pre-trained language models. arXiv preprint ar arXiv:220.111227.
[46] Matt Post and David Vilar. 2018. Fast lexically constrained decoding with dynamic beam allocation for neural machine translation. arXiv preprint arXiv:/804.06600
[47] Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. 2022. Cold decoding: Energy- based constrained text generation with langevin dynamics. In Advances in Neural Information Processing Systems.
[48] Alex Renda, Aspen K. Hopkins, and Michael Carbin. 2023. Can LLMs generate random numbers? evaluating LLM sampling in controlled domains In /CML Workshop: Sampling and Optimization in Discrete Space.
[49] Ronald Rosenfeld, Stanley F. Chen, and Xiaojin Zhu. 2001.
Whole-sentence exponential Computer Speech & Language,
language models: vehicle for linguistic-statistica integration
15(1):55-73.
[50] Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021. PICARD: Parsing incremen
tally for constrained auto- rego-segressive decoding from language models] In Proceedings of the 2027 Conference on Empirical Methods in Natural Language Processing, pages 1895-9901. Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
[51] Tianlin Shi, Jacob Steinhardt, and Percy Liang. 2015. Learning Where to Sample in Structured Prediction In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 875-884, San Diego, California, USA. PMLR.
[52] Richard Shin, Christopher H Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Anto- nios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. 2021. Con- strained language models yield few-shot semantic parsers. arXiv preprint arX1v:2104.08768
[53] Elias Stengel-Eskin Kyle Rawlins, and Benjamin Van Durme. 2023. Zero and few-shot semantic parsing with ambiguous inputs. arXiv preprint arXiv:2306. 00824.
[54] Zhi Rui Tam, Cheng- Kuang Wu, Yi-Lin Tsai, Chieh- Yen Lin, Hung-yi Lee, and Yun-Nung Chen. 2024. Let me speak freely? a study on the impact of format restrictions on large language model performance. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Prucessing: Industry Truck, pages 1218-1236, Miami, Florida, US. Association for Computational Linguistics.
[55] Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. 2024. Improving Ilm code generation with grammar augmentation. arXiv preprint arXiv:2403.01632.
[56] Daniel Veillard. 1998. libxml2: The XML parser and toolkit of gnome
[57] Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. 2023, Grammar prompting for sppeif- language generation with large language models!
[58] Brandon T Willard and Rémi Louf, 2023. Efficient guided generation for large language models. arXiv e-prints, pages ar3iv-2307.
[59] Kaiyu Yang, Aidan Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan Prenger, and Anima Anandkumar. 2023. LeanDojo: Theorem proving with retrieval-augmented language models. In Neural Information Processing Systems (NeurIPS).
14

---

[60] Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. 2023. Tractable control for autoregressive language generation. In International Conference on Machine Learning. pages 40992-409443 PMLR.
[61] Honghua Zhang, Po-Nien Kung, Masahiro Yoshida, Guy Van den Broeck, and Nanyun Peng. 2024. Adaptable logical control for large language models In Advances Neural Information Processing Systems, volume 37, pages 115563-115583 155887. Curran Associates, Inc.
[62] zxteloiv. 2025. complex-qa [source code]. httpa://gghaabb.ccc/zzteeello//p Accessed: 2025-05-13.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims are well-supported by the algorithm formalization and theoretical results in Section [ and comprehensive experiments in Section and further results the supplementary material.
Justification:
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We provide detailed limitations in Sections and
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems are accompanied by formal proofs in Appendix
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
in Appendix B model checkpoints in Appendix [[aadd experimental details in Appendix [ and to support the reproducibility of our experiments. The codebase and datasets with detailed instructions will also be released.
Justification: We provide all the hyperparameters
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We will attach datasets we covered in this paper during submission and the code will be released with detailed instructions.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Hyperparameters are included in Appendix All experimental details in- cluding fuzzing protocol (Appendix [.4 timing analysis (Appendix and benchmark specifications are included in Appendices D and to facilitate reproduction of our results.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report mean + standard deviation over five independent runs using different random seeds. These statisties are reported Tables and 6 This captures variability due to sampling and fuzzing nondeterminism in experiments.
16

---

8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We provide hardware and software details in Appendix A and approximate wall-clock times in Appendix E.7
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The authors have read the NeurIPS Code of Ethics and made sure the paper follows the NeurIPS Code of Ethics in every aspect.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper simply improves sampling. Existing L.M approaches will benefit from it, but the work will not directly lead to specific broader impacts.
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper properly cites the original paper or sources whenever an asset is used. URL of the model checkpoint is included in Appendix C
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will attach the datasets as part of our submission and the code will be released with well-documented instructions.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects. 15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
17

---

Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
16. Declaration LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were only used for editing.
18

---

Appendix
A Hardware and Software
Our experiments were conducted on Ubuntu 22.04 LTS nodes with Intel Xeon Gold 6230 CPUs (2.10 GHz, 10 cores, 20 threads allocated) and 384 GB RAM. For GPU-accelerated workloads, we provisioned 2x NVIDIA RTX A6000 GPUs. Our implementation based on Python 3.10.12 12, PyTorch 2.6.0+cu124, +FL++ 4.00c and LLVM 14.0.0.
B Hyperparameters
For madguage-model decoding, we set temperature to 1.0, top-p to 1.0, and top-k to to allow sampling from the full token vocabulary. We limited the maximum number of newly generated tokens 512 for XML, and 1024 for SQL test scripts.
C Model Checkpoints
We evaluate on two instruction-tuned models representing different architectural aiffferraaachieecttura families:
JJama-331-8B-Instruut 20
http:://hagginn/aacccco//ttaasao L1ama-3 B-8B-1 Instruct (commit 0e9e39f)
Qwee225-Cooder-7BBnssrre
30
https://huggingfaccc..c//eeee Qwen2
5-Coder Instrruct (commit c03e6d3)
All models use BF16 precision with their default tokenizers and system prompts.
D Domain-Specific Generation Benchmarks
We evaluate the convergence properties of Grammar-Aligned MCMC Sampling empirically on the benchmark tasks proposed by Park et al. (3). Fig. 4 relates the [L[P MCMC-T(k)) for & = 10, for 7 (Unnforrm, Priority, Restart). Each point represents a single task. Points below the diagonal indicate tasks where MCMC approximates pe better than GCD. g. displays the same information, but for ASAp(10) instead of GCD.
and
Fig.
Fig. 7 Fig. 8 compare the distance to pe of the different sampling strategies as compute increases, across all the benchmark tasks. Lower KL-Divergence indicates a better approximation ps.
The distributions induced by different sampling methods all approximated using 100 samples, and pc approximated using all the samples acquired across all runs for the same task. 95% confidence band is shown for convergence plots, computed via Bootstrapping.
pririty
petaniy moter
MCMCIX- 10) Divergence
metion
MONOUE 10) KL Divergence
MCMCI--10 (0) XL Divergence
nwtsrt
Divergence
Divergence
Diverreecce
Figure 4: KL-Divergence for GCD vs MCMC(K = 10) by subset
19

---

BV4
Leform praatiy
Leforn pelorty rnttrr
unfom prorty retart
MCMC(K-10) KL Divergence
MCMCCE XL Divergence
MCMC XL Divergence
ASAP(k=10) Divergence
ASAR(k-10) Diverpence
ASAPik-101 Divergence
Figure 5: KL-Divergence for ASAp(k 10) vs MCMC(K = 10) by subset
Oonsme shot
02 02-reme-ott camme--mmmtre-4 eost
combere 2-leng repert
MONE
MgcChertty X0
MODCC Prart X0
Romty SPCAMIRS1
Jel seiis
DEAER 2 thar
Icompr
00
02
10 Labert
PORCIA CoNCANe
Mike
(rooopatt)
kil
Cca rouue)
Figure 6: KL-Divergence of sampling methods in SLIA subset
20

---

05-tnd inv Ixfanr 481
23.indd by braqt Eveatel 42E
D0-tid Ite IE 2oud 11 42t
10-0rd BYA THE boadd LD dot
MONCA M
01-fed bournes the
02-fnd borenb tht
02-fnd butge bunct IN!
07-ded iyy Musi dedacio
bureg tht
sprccnedie bi one 300
tonrestel
tooreste!
Hasi Pomty ar
Horty
Coatt accr)o
Ge" p4
12-irdl basgl 200r
35-frd beard)
(conguue)
(comnuuee)
Figure 7: KL-Divergence of sampling methods in BV4 subset
02-CP 2434
01-2P
10:CP
00:CP 2th 2015
Wosk decart
Portye
CCa Tokue)
Figure 8: KL-Divergence of sampling methods in CP and MS subset
21

---

E
Fuzzing Experiments Details
E.1 Benchmarks
Table summarizes the libraries, versions, and seed formats for each target.
Table
Benchmarks, versions, and seed formats.
Target
Library
Version
Seed format
XML
libxml2
2.15.0
xm1
SQL
X
sqlite
3.49.2
test
E,2
Parse-Tree Illustration
Figure shows comprehensive parse tree for SQLite test case, derived from the grammar in Figure
beat
Pooucce
Ldentifiez
"set
Best block
itcapable block
bloc_ Tixt
srpactad, PARNTE
Sourna Loode
boot.block
stateent
sel_velue
talev
caschoo)_ commund
Hitrrll
catchagg
liberal
Jntabasentx
gragna_attes
ideasifier
Figure Condensed parse tree for the example SQLite test script used in Figure 1 Purple boxes denote non-terminals, green boxes denote grammar terminals, and blue italics show literal terminal values substituted during this derivation. Subtrees unrelated the header and the first do_ do_execsq]__ test block are elided for brevity.
22

---

E.3 Prompts and Constraints
For all benchmarks, we use a standard in-context learning format where the prompt consists of single (specification, solution) pair, followed by new specification for which the model must generate a solution. A representative prompt for the XML benchmark is shown in Figure I0a along with its corresponding grammar in Figure [0b
root :18
(prolog)7
(doctype we)?
elenent
prolog xmldecl (va misc)
Queation 1:
Generate single, Include variety of XNL features and various markup daclarations.
complex document.
...
elenent 11-
reuse previous
starttag content endtag amptyalenent
Solution 1:
<7xm1 version="L.0" encoding="UTFF-"7>
endtag
<IDOCTYPE document [
"c/" name "5*
<IENTITY }>
<document mitns="httpp//ezaalee.omm
11
(chardata
</documant>
element
comnent
pi edata)
Question Cenerate single, short but. complex XML document.
Include variety of XML features and various narkup declarations. Do previous solutions.
11m
"cl--" [--]+ "-->" we
whito__ppce]-
Solution
(a) Prompt
(b) Grammar
Figure 10: (a) Prompt given to a LM to generate seed test cases for fuzzing the XMI. parser. (b) Simplified version of the XML. 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.
E,4 Fuzzing Protocol and Environment
All fuzzing experiments were conducted using AFL++ 4.00c on the hardware and software setup described in Appendix A Each (benchmark, method) pair was evaluated in N 5 independent, single-instance AFL++ runs of exactly 21600 (six hours). We set 'AFL RALDOM SEED to 42 + i, (i 1...5) for reproducibility and configure standard environment variables ensure interactive execution. All other AFL++ parameters remained at defaults to isolate the impact of seed corpus quality. Complete build and execution scripts are provided in the supplementary materials.
E.5 Coverage Measurement via LLVM Instrumentation
coverage using LLVM's instrumentation toolchain pooverage-mappinng which adds 2% runtime over- head. Raw profiles were collected during execution and aggregated post-trial using IIvm-profdata and Ilvm-cov.
We measured branch seerofile-instt-eenee
Rationale. We report branch coverage rather than crash counts because the experiment isolates seed quality - all methods receive the same fixed prompt per benchmark, so coverage a good measure how their seeds exercise the code.
23

---

E.6 Rejection Sampling Acceptance Rates
We quantified the viability rejection sampling under the same grammar constraints used by our MCMC framework in Section 4.2 Across 500 attempted samples per benchmark, the proportion of syntactically and semantically valid outputs was consistently below 1%.
E.7 Generation Time Analysis
Table reports the average wall-clock time required to generate single seed across different methods using 1-ttaa-.1--B-Insteee and expected, MCMC with k = 10 steps takes approximately 10x longer than GCD per sample, while ASAp is significantly more expensive. This timing difference motivates our compute-me matched seed count experiments (Appendix (E.)), where we evaluate whether generating more GCD seeds within the same time budget can compensate for MCMC's per-seed quality advantage.
1x NVIDIA RTX A6000 GPU As
Table Average generation time per seed (seconds) for each method.
Llama-3.1 1-Bt---teett
(b) Siwe2..-Coodrs Codee--B-Instruet
Method
XML
SQL
Method
k
XML
SQL
MCMC-Uniform
MCMC-Uniform
14
21
2
12
18
36
56
5
31
48
10
71
112
10
63
98
MCMC-Priority
MCMC-Priority
14
21
2
12
18
36
5
49
10
71
112
10
64
99
MCMC-Restart
NCMC-Restar
14
21
2
12
18
36
56
5
32
49
10
71
112
10
64
100
SMC+AWRS
SMC+AWRS
31
46
2
27
40
111
5
138
10
161
214
10
142
188
ASAp
461
714
ASAp GCD
402
628
GCD
7
11
9
E.8
Seed Count Ablation
To evaluate whether seed quality quantity matters more for fuzzing effectiveness, we conducted compute-matched experiments varying the number of initial seeds N E (50, 100, 200, 500). Since MCMC (10) takes approximately 10x longer than GCD per seed (Appendix E.7), comparing 50 MCMC seeds against 500 GCD seeds represents equivalent computational budgets.
Tables and show branch coverage after 6-hour fuzzing runs for both Llama-3. IB---Instrect and Owen2.5-Coder. - Remarkably, MCMC methods with just 50 seeds consistently outperform GCD with 500 seeds, demonstrating that sampling fidelity dominates sheer quantity for fuzzing effectiveness.
E.9 Branch Coverage and KL Divergence Across Models
Figures II and 12 show branch coverage and KL divergence results for both Llama-3. --B......B-Bimmn --I-rruttt and Owen2.5-Codee. BB-Instruc - the SQL and XML benchmarks, respectively. The trends observed in the main text (Figure for SQL with Llama-3.1 3.1-.B..BBBBB. 1-8B-Instruch hold consistently across both models:
PSMC+WWRS (A: 10) evaluated on 1x H100 GPU (120GB) due higher memory requirements.

---

Table SQL benchmark: Branch coverage (mean std) over five trials after 6-hour fuzzing runs with varying seed counts. Best entries per seed count in green.
Method
N=50
N=100
N=200
N=500
Llama-3.
MCMC-Uniform
30.72 02.72.00 0.60
33.69
0.66
33.41 + 0.66
33.39 0.66
32.07 + 0.45
34.37 + 0.48
34.25
+ 0.48
35.53
0.49
10
33.88 + 0.64
36.47 = 0.69
35.49
+ 0.67
37.03 + 0.70
MCMC-Priority
2
32.04 + 1.16
33.89 + 1.23
33.95 + 1.23
33.98 + 1.23
33.10 1 0.25
36.21 0.27
36.18 - 0.27
36.01 0.27
10
34.48 0.74
0.78 36.69
37.02 0.79
37.17 0.79
MCMC-Restart
31.12 0.46
33.38
0.49
33.09 0.49
33.56 0.50
32.22 1 0.86
33.36 1 0.90
34.63 1 0.93
34.08 0.91
10
33.05 1 0.68
36.25 + 0.74
36.81 + 0.75
36.64 1: 0.75
SMC+AWRS
2
33.20 + 1.09
32.93 + 1.08
$3.71
33.39 + 1.10
34.63 = 0.43
35.16 = 0.44
0.44
35.74 0.45
10
35.85 0.75
36.44 0.77
3.79
36.23 0.76
ASAp
10
33.09
0.55
32.61
0.54
33.65 +
33.39 0.55
GCD
30.47 0.91
31.52 0.94
3.93
31.70
Grammarinator
25.47 + 0.49
26.50 - 0.51
28.39 + 0.55
27.92 0.54
Qwen2.5-Coders 7n-tsrucc
MCMC-Uniform
30.85 1 0.61
32.79 1 0.64
33.65 1 0.66
33.07 0.65
5
32.35 1 0.45
34.91 1 0.49
34.48 1 0.48
35.45 0.49
10
33.29 0.63
36.87 = 0.70
36.70
35.91 0.68
MCMC-Priority
2
31.87 1.15
34.72 = 1.26
34.80 = 1.26
34.87 1.26
34.67 0.26
35.56 0.27
36.21
35.89
10
35.80
0.77
36.41 = 0.80
37.22 + 0.80
36.85 0.79
MCMC-Restart
31.30 + 0.46
32.77 = 0.48
33.31 + 0.49
33.36 + 0.49
5
32.98 +: 0.89
33.94 = 0.91
33.46 + 0.90
34.45 1: 0.92
10
34.38 + 0.70
35.69 = 0.73
35.99 + 0.74
35.79 + 0.73
SMC+AWRS
2
33.50 +: 1.10
33.37 1.10
32.83 1.08
32.94 + 1.08
34.50 0.43
35.35 = 0.44
0.44
35.17 0.44
10
36.79 1 0.77
35.84 0.75
0.70
36.57 0.77
ASAp
10
32.67 0.54
32.47 0.54
32.58 3.57
GCD
29.51 0.88
31.41 0.94
3194440044
31.49
Grammarinator
25.47 + 0.49
26.50 = 0.51
28.39 28.39 0.55
27.92 0.54
(i) KL divergence decreases with more MCMC steps, indicating convergence toward the target distribution, and (ii) MCMC-based methods achieve higher branch coverage than GCD and ASAp, with MCMC-Priority (k = 10) delivering the best performance. Qwen2 Ceone..--Codr-----nsssne exhibits similar relative performance across methods, though with slightly different coverage values due to model model-specific generation characteristics.
E.10
Overall Coverage Results
Tables and 6 show that the improvements achieved by our grammar-based MCMC sampler on branch coverage translate consistently to both function and line coverage across both the SQL. and XML benchmarks using 100 seeds over 6-hour fuzzing runs. Coverage grows monotonically with
25

---

Table XML benchmark: Branch coverage (mean + std) over five trials after 6-hour fuzzing runs with varying seed counts. Best entries per seed count in green.
Method
N=50
N=100
N=200
N=500
Llama 3.1 1-1----nnstruc
MCMC-Uniform
12.41 + 0.15
12.51
0.16
12.45 + 0.16
12.43
0.15
12.29
+ 0.13
12.45 + 0.13
12.88 + 0.14
12.99 + 0.14
10
12.47
+ 0.04
12.76 = 0.05
12.97 + 0.05
12.96 + 0.05
MCMC-Priority
2
11.91 0.06
12.60 + 0.07
12.96 + 0.07
12.68 + 0.07
12.13
12.82 0.07
-.00
13.05 0.07
10
12.52 0.27
12.79 0.28
12.94 0.28
12.88 0.28
MCMC-Restart
0.08
11.70 0.08
11.99 0.08
12.07 1
11.69 1 0.05
12.11 + 0.05
12.44 0.06
12.24 0.06
10
12.08
1 0.07
12.58 + 0.08
12.85 + 0.08
12.61 +: 0.08
SMC+AWRS
2
12.60 + 0.08
12.54 + 0.08
12.38 + 0.08
12.63 0.08
12.60 0.04
12.53 = 0.04
1.00
12.68 0.04
10
12.54 +
12.63 0.13
0.13
12.79 0.13
ASAp
10
11.06 0.08
11.30
0.08
11.34
11.04 + 0.08
GCD
11.19 0.07
11.08 0.07
0.007
11.27 0.07
Grammarinator
9.01 + 0.16
8.99 - 0.16
9.21
8.94
Owee2.5-CCoder-7B-me
MCMC-Uniform
12.20 1 0.15
12.13 1 0.15
12.69 0.16
12.76 0.16
5
12.33 1 0.13
12.57 1 0.13
0.114
12.78 0.13
10
12.76 0.05
12.65 = 0.05
0.07
13.26 0.05
MCMC-Priority
2
12.81 1.81:0007
12.75 0.07
12.73
12.77 + 0.07
0.07
12.92 = 0.07
13.04
13.03 0.07
10
12.89 + 0.28
12.68 0.27
12.84 0.28
13.27 + 0.29
MCMC-Restart
11.93 + 0.08
11.69 + 0.08
11.83 + 0.08
12.26 0.09
5
12.05 0.05
12.35 + 0.06
12.58 0.06
10
12.62 + 0.08
12.45 = 0.08
12.80 + 0.08
12.73 0.08
SMC+AWRS
2
12.43
12.64 = 0.08
12.59
12.69 0.08
1.07
12.70 0.04
1..4
12.60 0.04
10
12.83
12.82 = 0.13
0.10
12.90 0.13
ASAp
10
11.44
11.32 0.08
11.39
11.26 0.08
GCD
0.07
11.39 = 0.07
0.05
11.99 0.00
Grammarinator
9.01 0.16
8.99 = 0.16
9.11
8.94
the number of steps however, k already captures 295% of the gain realized by k 10 on both benchmarks. Even the weakest setting (k = 2) surpasses GCD's final coverage by 4-6%, demonstrating that MCMC proposals yield coverage gains over heuristic constrained decoding with very few sampling steps. Additionally, seed count ablation results (Appendix FE8) and generation timing analysis (Appendix [F.7) demonstrate that MCMC's quality advantages persist even under compute-matche matchte comparisons.
26

---

MCMC-Unifam
MCMC-Priority (n)
35-
MCMC Restart (n)
SMC+ AWRS (n)
Branch Coverage (%)
D.iiergence
GCD
23
20-
190
15
MCMC-Uniform
MCMC- PiCC-Prirtty (10)
100
ASAp (10)
SMC+AWRS (10)
50
GCD
Grammerinator
10
3000
10000
15000
20000
(compute)
Time (seconds)
(a) KL divergence (Llama-3.1) -----....----tttu-ete -B-Instruutt)
(b) Branch coverage (Llama-3. 1.tna-3.1180 1B--Instruct
MCMC-Unifom
120
MCMC-Priority (n)
25
MCMC-Restart In)
ASAp (n)
100
SMC+ AWRS (n)
KL. Divergence
Branch Coverage
23
80
90
15
MCMC-Uniform (10)
MCMC-Prority (10)
46
MCMC-Restart (10)
ASAp (10)
GCD
Grammaninator
(compute)
(seconds)
KT. divergence (0wen2.--Coalrr----nnnrrr
(d) Branch coverage (Qwen2.5-Coder-77 -odder--B--nstrucc))
Figure 11: SQL benchmark: KL divergence and branch coverage over time for both language models (100 seeds, 6-hour runs). Top row shows Llama-3 3.1 3.B-BB--.. Instrrcttt results; bottom shows Qwen2.5- Coder-7B-Instruct results.
F Properties and Proofs
In this section, formalize and prove the two key properties of our sampler (Alg. 1). constraint satisfying (Thm. 1) and monotonically converging (Thm. 3).
The first property follows directly from the procedure in Alg.
Theorem 1 (Constraint Satisfying). For any LM P, any grammar G, any chain length k, and any truncation distribution Pros, the result of Alg. is always inside L(G).
Proof. The output of Alg. can only be generated from either Line or Line 11, both of which call the GCD procedure. Since GCD samples only from the constrained language L(G), the result of Alg. must also fall within L(G).
As for monotonically converging, we prove it by applying the following theorem for Markov chains. Theorem (Thm. 5.6.6 in (15).. Let p be a Markov chain with countable states, and let l|g, d'llTv denotes the lotal variance distance of two distributions, i.e., E. lq(x) - d(xx)]-
When is irreducible, aperiodic, and has stationary distribution then for any state state (p z), T| will converge to as approaches to oc.
Theorem 3 (Monotonically Converging). For any LM P. any grammar G, and any truncation distribution Pros. if p (0) > for all sequences L(G), then the output distribution of Alg.
27

---

120
MCMC-Uniform (n) PEMM-Pri
14
MCMC-Restart
ASAp (n)
Branch Coverage (%)
Divergence
GCD
10
MCMC-Unifarm
80
MCMC- Peccc-riorityyyo (10)
(10)
ASAp (10)
SMC+AWRS (10)
Grammerinator
10
0
5000
10000
15000
20000
(compute)
Time (seconds)
(a) KL divergence (Llama-3..) 3.1-8B-Instruct)
(b) Branch coverage (Llama-3. 3.1 1-B8-BB- (B-IInstruct
MCMC-Unifomm
50
Paiioiyy (n)
MCMC-Restart in)
ASAp (n)
12:
SMC+ AWRS In)
Branch Coverage (96)
KL Divergence
20-
MCMC-Uniform (10)
25
MCMC-Prioiit (10)
MCMC-Restart (10)
ASAp (10]
GCD
Grammerinator
(compute)
(seconds)
KT. divergence (Qwem225-CCaler-7---nnnrru
(d) Branch coverage (Qwen2.5-Coder-7B BB-ntruuct)
Figure 12: XML benchmark: KL divergence and branch coverage over time for both language models (100 seeds, 6-hour runs). Top row shows Llama-3.1 1-8---nnsttuct Instruct results; bottom row shows Qwen2.5-Coder-777 IB-sstrrcc results.
will monotonically converge to pe the chain length le approaches to infinite, as shown below.
lim || p9 TV =
(3)
k-
4k,
I p |TT > 1 pd ||
where Pe denotes the output distribution of Alg. 1 when the chain length is
Proof. We prove the convergence Eq. 3 by applying Thm. 2 to our case, by verifying that the Markov chain constructed in Alg. satisfies all prerequisites of Thm. 2
(Countable states) In our Markov chain, the state set comprises sequences with non-zero probability in pč, denoted as S. This set is countable since the set of all sequences is countable.
2. (Irreducibility) Let be the proposal distribution of our Markov chain. We start by showing that yvy x) > for all v, S. Consider the event where the empty prefix is selected in Line 10, and is selected by GCD in Line 11. The probability of this event is phas (0) PGCD(y), which non-zero. On the other hand, q(v æ)) no smaller than this probability, hence it must also be non-zero.
28

---

Table SQL benchmark coverage (mean std) over five trials after 6-hour fuzzing runs with 100 seeds.
Best entries highlighted in green.
Method
k
Branch (%)
Function (%)
Linc (%)
Llama-3. 3.1-8B-Instruce
MCMC-Uniform
2
33.69 = 0.66
52.17 + 0.53
42.07 + 0.32
5
31.37 = 0.48
56.25 + 0.76
44.51 + 0.37
10
36.47 = 0.69
57.44 + 0.89
45.98 + 0.79
MCMC-Prioriie
2
33.89 = 1.29
53.48 + 1.60
43.32 + 1.59
5
36.21 0.27
57.27 + 0.86
45.96
+ 0.45
10
36.69 = 0.78
58.87 1 0.82
47.18 1.02
MCMC-Restart
2
33.38 = 0.49
52.50 1 0.78
42.17 1 0.74
5
33.36 = 0.90
55.03 1 0.99
43.50 1 0.92
10
36.25 = 0.74
56.31 + 0.76
45.24 + 0.71
SMC+AWRS
2
32.93 = 1.08
53.01 + 1.26
43.05 + 0.96
5
35.16 = 0.44
57.10 0.65
45.79 + 0.44
36.44 = 0.77
58.70 = 0.57
46.76
+ 0.54
ASAp
10
32.61 0.54
52.69 + 0.94
43.26 + 0.74
GCD
31.52 = 49.38 - 0.60
39.25 +
Grammarinator
26.50 = 0.51
44.80 + 1.09
35.66 1 1.20
2wen2.5-Coder 7B-Instruct
MCMC-Uniform
2
32.79 = 0.64
49.62 1 0.56
39.93 1 0.43
5
34.91 = 0.49
56.07 1 0.72
44.21 1 0.29
10
36.87 0.70
57.61 = 0.71
46.08 + 1.14
MCMC-Priority
2
34.72 = 1.26
51.66 + 1.30
41.90 + 1.69
5
35.56 = 0.27
55.67 = 0.73
+ 44.87
10
36.41 = 0.80
58.27 = 0.62
47.41 + 0.86
MCMC-Restart
2
32.77 = 0.48
50.98 + 0.77
41.02 1 0.64
5
33.94 = 0.91
54.37 + 1.03
42.99 1 0.89
10
35.69 = 0.73
57.46 + 0.96
46.29 + 0.82
SMC+AWRS
2
33.37 = 1.10
49.75
40.27 0.92
5
35.35 = 0.44
55.70 0.50
44.67 + 0.48
10
35.84 = 0.75
57.00 0.52
45.56 + 0.65
ASAp
32.47 = 0.54
49.05
39.17 + 0.77
GCD
31.41 = 0.94
48.32 1.02
39.41 + 0.55
Grammarinator
26.50 = 0.51
44.80 = 1.09
35.66 + 1.20
Then, by the definition of the transition probability p in the Metropolis-Hastings algorithm
E plu (x) 2 4(v x²) a(x,v) = 4(v a:) max {1,
P(y)q(1 v)
P(x) x))
All values the right-hand side are positive, so p(y x) must also be positive, implying the irreducibility of the Markov chain.
3. (Aperiodicity) By the above analysis, p(x x)) 0 for any state æ, implying aperiodicity.
The theater-than part of the first inequality captures the special where y.
29

---

Table XML benchmark coverage (mean = std) over five trials after 6-hour fuzzing runs with 100
seeds. Best entries highlighted in green.
Method
k
Branch (%)
Function (%)
Line (%)
Llama-3. 3.1-8B-Inssruc
MCMC-Uniform
2
12.51 = 0.16
18.89 + 0.16
13.59 + 0.09
5
12.45 = 0.13
19.23
+ 0.06
13.82 + 0.10
10
12.76 = 0.05
19.28
= 0.05
13.98 1 0.03
MCMC-Prioriie
2
12.60 = 0.07
19.21 + 0.05
14.05 + 0.06
5
12.82 0.07
19.26 + 0.08
13.99 + 0.10
12.79 =
19.44 0.37
14.22 1
MCMC-Restart
2
11.70 =
18.46 1
13.23 0.10
5
12.11 = 0.05
18.62 1 0.04
13.45 1 0.05
10
12.58 = 0.08
19.26 + 0.19
13.79 1 0.09
SMC+AWRS
2
12.54 = 0.08
19.18 + 0.08
13.85 + 0.04
5
12.53 0.04
19.36 = 0.06
13.96 + 0.06
12.63 =
19.42 0.18
14.21 + 0.11
ASAp
10
11.30 0.08
17.54 + 0.02
12.53 + 0.04
GCD
11.08 =
17.21 + 0.03
12.41 +
Grammarinator
8.99 - 0.16
15.18 + 0.29
10.60 + 0.14
Qwen2.5-Coder-78 7B-Instruct
MCMC-Uniform
2
12.13 = 0.15
20.77 1 0.23
15.13 0.18
5
12.57 = 0.13
21.23 1 0.13
15.45 0.15
10
12.65 0.05
20.53 = 0.42
15.13 0.22
MCMC-Priority
2
12.75 = 0.07
21.63 = 0.06
15.80 + 0.06
5
12.92 = 21.24 =
15.60 +
10
12.68 = 0.27
20.81 + 0.11
15.51 + 0.09
MCMC-Restart
2
11.69 = 0.08
19.86 + 0.26
14.32 1 0.11
5
12.05 = 0.05
19.89 + 0.08
14.60 1 0.13
10
12.45 0.08
20.90 + 0.23
14.98 + 0.13
SMC+AWRS
2
12.64 = 0.08
21.46 + 0.09
15.61 + 0.14
5
12.70 = 0.04
21.23 + 0.05
15.32 + 0.10
10
12.82 = 0.13
21.04 0.24
15.38 + 0.09
ASAp
11.32 = 0.08
18.83
13.80 0.10
GCD
11.39 = 0.07
17.46 0.06
12.54 0.12
Grammarinator
8.99 = 0.16
15.18 = 0.29
10.60 + 0.14
4. (Stationary distribution) The Metropolis-Hastinee algorithm ensures that the target distribu- tion p9 is stationary distribution of the constructed Markov chain.
Hence, all prerequisites of Thm. are satisfied, then Eq. follows directly from it.
30

---

Then, we prove the monotocity by the following derivation, where (ww w') denotes the probability for our Markov chain to move from w' w.
R+10 pC ITv
2 Σl
P - (0(1))
Σ P (w') p (w(')) p(w w')
$ 2
(w'))
(w') - -P0(w)) p(w ww)
1
PR (w') (w(') - po (no') <E p(w I w')
2
Σl
k (w') - p0(1')) = =11P2: 1|T
2
W
31


Reviews:
[{"review_id": "Qq2dcpno3V", "reviewer": "Reviewer_Q6rk", "summary": "This paper presents a Monte Carlo method for grammar-constrained sampling from language models.\nVanilla grammar-constrained decoding (GCD) results in a skewed distribution that is far from the target constraint distribution.\nTo solve this problem, this paper proposed a conceptually simple method (a slightly modified Metropolis-Hastings algorithm that allows decoding a new sample from the prefix generated in the previous step rather than from scratch) and showed it to be effective on two tasks.", "questions": "Please also refer to the Strengths and Weaknesses part:\n* When does the proposed sampling method perform better than a simple resampled importance sampling?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* The paper is well-written and easy to follow.\n* The proposed method is simple and effective.\n\n\nWeaknesses:\nMy major concern is about the results presented in Fig. 2 (a) and Fig. 3 (a):\nFrom the KL divergence curves, it seems the 'restart' achieves the fastest convergence compared to more sophisticated choices of $p_{pos}^w$, which means a simple resampling importance sampling is sufficient for the task. In that case, how does the extra flexibility in proposal distribution help?\n\nMinor points:\n* Experimental results are only reported on two tasks.\n* The paper lacks of discussion of and comparison with other Monte Carlo methods, e.g., https://arxiv.org/pdf/2504.13139", "was_revised": true, "final_justification": "My concerns regarding the proposed method vs. 'restart' are mostly resolved. Thus, I raise my score.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. We appreciate the positive comments on the clarity of the writing and the simplicity and effectiveness of our proposed method.\n\n> My major concern is … it seems the 'restart' achieves the fastest convergence … how does the extra flexibility in proposal distribution help? When does the proposed sampling method perform better than a simple resampled importance sampling?\n\nThanks for the observation. It is true that MCMC-restart generally achieves faster convergence in practice than MCMC-uniform and MCMC-priority, although the difference in convergence speed and final KL-divergence value between the three approaches is not drastic. The main advantage of subsequence resampling proposals, and in particular of MCMC-priority, comes from the “local” diversity they induce in samples—e.g., they produce more variants of one program rather than more different programs. This local diversity is beneficial in the fuzzing task (see Figure 3 in the paper), where although MCMC-restart converges a little faster than MCMC-priority, the samples produced by MCMC-priority result in higher coverage when actually running the fuzzer (i.e., MCMC-priority has better downstream performance).\n\nThe motivation for MCMC-uniform and MCMC-priority comes from similar analogous approaches for proposal design that have been successful in stochastic program synthesis [1,2,3]. These instances rely on proposals that locally perturb a substructure of the current candidate. We will clarify and expand on these points in the final version.\n\nAs for comparison with resampled importance sampling, we ran a preliminary evaluation comparing our proposed method with the SMC method proposed in [4], which itself is reported to be stronger than Resampled Importance Sampling. On a subset of the BV4 program synthesis tasks, we observe that MCMC-restart achieves 1.86x (geo. mean) better KL-divergence on compute-matched runs (k=10 steps vs k=10 particles) vs SMC. We will add a detailed version of this experiment to the paper.\n\n[1] Eric Schkufza, Rahul Sharma, and Alex Aiken. 2013. Stochastic superoptimization. ASPLOS '13\n\n[2] Aditya V. Nori, Sherjil Ozair, Sriram K. Rajamani, and Deepak Vijaykeerthy. 2015. Efficient synthesis of probabilistic programs. PLDI '15\n\n[3] Feras A. Saad, Marco F. Cusumano-Towner, Ulrich Schaechtle, Martin C. Rinard, and Vikash K. Mansinghka. Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling. POPL 2019\n\n[4] Loula, J., ... & O'Donnell, T. J. (2024). Syntactic and semantic control of large language models via sequential monte carlo. arXiv preprint arXiv:2504.13139.\n\n\n\n\n\n\n\n> Experimental results are only reported on two tasks\n\nWe are grateful for the reviewer’s observation and the opportunity to clarify this point. We consider 2 domains: program synthesis and program fuzzing, with 35 problems for synthesis across 3 splits of tasks (15 for SLIA, 14 for BV4, and 6 for CP) and 2 problems for fuzzing (XML and SQL). \n\nOur rationale when choosing the benchmarks was as follows. First, we chose the three types of program synthesis benchmarks as they are the main evaluation component of the previous work we evaluated against [1]. Second, we designed the program fuzzing evaluation since we were not aware of any task where the quality of the full empirical distribution is paramount; other GCD tasks are mostly concerned with finding one solution rather than exploiting the diversity of the distribution. To our knowledge, our fuzzing task is the first to explicitly evaluate example diversity in this way and we consider the design of this task itself a contribution to the paper.\nWe can incorporate relevant domains proposed in the suggested related work for the final version of this work.\n\n[1] Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D'Antoni. Grammar Aligned Decoding. NeurIPS 2024\t\n\n\n> The paper lacks of discussion of and comparison with other Monte Carlo methods, e.g., https://arxiv.org/pdf/2504.13139\n\nBoth our approach and the referenced one [1] apply Monte Carlo methods over token sequences to approximate $P^G$ ($g$ if using the notation from [1]). Whereas we approach this problem by using MCMC, [1] implements both Resampled Importance Sampling and Sequential Monte Carlo (SMC) or Particle Filtering. Any of these methods are theoretically guaranteed to produce samples from the target distribution when $N$ tends to infinity, but MCMC does not directly reduce to any of the other two algorithms or vice versa. \n\nBefore moving to the theoretical comparison of the two approaches, we ran a preliminary evaluation comparing our proposed method with the SMC method proposed in [1]. On a subset (due to timing constraints) of 8/14 BV4 program synthesis tasks, we observe that MCMC-restart achieves 1.86x (geo. mean) lower (i.e., better) KL-divergence on compute-matched runs (k=10 steps vs k=10 particles) vs SMC. We will add a detailed, more comprehensive version of this experiment to the paper.\n\nA clear advantage of the alternative methods in [1] is the inclusion of expensive potentials to score the quality of generations. This is done by adjusting the probability of sequences by the (ratio of) change of potential induced by each of its next-token completions. This is a nice way of integrating such signals into the decoding process, and the details on how to add an analogous factor to the Metropolis-Hastings equations could be a direction of further research. However, in the case of simple grammar-constrained decoding which we study, this notion goes unused, and these approaches reduce to the vanilla versions of IS and SMC.\n\nThere are further connections that can be drawn between our approach and those presented in [1]: Importance Sampling and MCMC-restart lend themselves to more aggressive parallelization, since one can draw N complete samples independently and perform one final round of drawing to obtain a final sample. On the other hand SMC is more similar to MCMC-uniform or MCMC-restart, in the sense that some additional computation has to be made at each generation step of the sequences, although for MCMC this computation is only dependent on the previous state of the same sequence, whereas for SMC it depends on the state of the rest of the particles as well.\n\nOverall, we find no strong formal argument to position either one with clear advantage over the others in the setting of grammar constrained decoding. We will add a detailed comparison to our paper.\n\n[1]  Loula, J., ... & O'Donnell, T. J. (2024). Syntactic and semantic control of large language models via sequential monte carlo. arXiv preprint arXiv:2504.13139."}, {"review_id": "dwE1kO103S", "reviewer": "Reviewer_gYBz", "summary": "This paper presents a constrainted sampling setup inspired by the MCMC framework. The proposed approach aims to address some of the challenges faced in current constrainted sampling setups where classic approaches can be inefficient and do not guarantee to recover the original distribution. The proposed approach iteratively refines the generated sample while uses a grammar-constratined decoding setup. The paper evalutes the proposed approach to show certain properties are presevered and further experiments on a practial application of fuzzing to demonstrate practical impact of the approach.", "questions": "- How does different tokenization setups of the different LLMs affect the approach? For example, a different LLM may tokenize a particular piece or terminal of CFG differently, does the proposed approach require much changes to be able to handle that?\n- What is the initial coverage of the 100-seed problems generated by each approach? How does the coverage change as we increase the number of seeds to 1000 programs?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## strengths\n- To the best of my knowledge the proposed approach to perform constrained decoding using MCMC algorithm has not been previously done\n- The motivation of this work with regards to the prior approaches and what their limitations are: inefficiency in rejection sampling and disrupting the underlying distribution when doing classic constrained decoding is extremely clear and presented in a nice way\n- The idea presented in the paper is simple and intuitive to understand\n- The additional practical evaluation in terms of fuzzing to showcase the practical impact of adopting the proposed technique is well-appreciated \n\n## weaknesses\n- The main weakness of the work is the limited evaluation in terms of the model used. The work only really uses a single model, it's unclear why this model is chosen or if the technique will work different or require additional work when we switch to a different model (say with a different tokenization scheme)\n- Furthermore, \"out of 500 samples produced by Llama-3.1-8B-Instruct,\n98 only 2 (0.4%) satisfied the constraint imposed by the grammar.\" This point raised by the author I would guess is only true because of the small size of the model. A larger sota model would like produce many samples with valid grammar (hence the increase in popularity of rejection sampling)\n- For the fuzzing experiments, it's unclear why the authors only evaluated 100 seed settings. It would be much more interesting to show how the coverage changes as we increase the number of seeds (i.e., how much \"good\" coverage can be produced in the seed programs). This would show how the technique gives better diversity \n\nNevertheless, these are small limitations which should be simple and easy for the authors to address in the incoming revisions\n\n### minor\n\n- line 47 has additional period in the middle of sentence", "was_revised": true, "final_justification": "In my opinion the motivation of this work with regards to the prior approaches and what their limitations are: inefficiency in rejection sampling and disrupting the underlying distribution when doing classic constrained decoding is quite clear and easily understandable. I also believe that the authors proposed an easy and intutive approach which works. Furthermore the authors have also added additional experimental results which answered some of my concerns. As such I remain positive regarding this work.", "rebuttal": "We thank the reviewer for their thorough and constructive feedback. We are pleased that the novelty, clarity, and practicality of our approach—particularly its application to fuzzing—were well recognized. We also appreciate the thoughtful questions and suggestions regarding model choice, evaluation scale, and the impact of tokenization, which we will carefully address in our revision.\n\n\n> only really uses a single model…How does different tokenization setups of the different LLMs affect the approach? \n\nWe agree with the reviewer’s assessment and have run additional evaluation for a subset of our benchmark tasks during the response period, and will include comprehensive runs of these experiments in the final version. We emphasize that no modifications to our implementation are needed to switch to different models and their specific tokenization schemes..\n\nFor the program synthesis benchmarks, we have run the BV4 benchmarks with 3 additional SOTA models: `Qwen2.5-Coder-7B-Instruct`, `gemma-2-9b-it`, and `deepseek-coder-7b-instruct-v1.5`. Across all 14 tasks and 3 models, we see that samples from each of the MCMC instances have lower KL-divergence w.r.t  $P^G$  than GCD, with improvements rates presented in the following table\n\n|  | Uniform | Priority | Restart |\n|--|--|--|--|\n| Qwen2.5-Coder-7B-Instruct | 1.23x | 1.42x | 2.71x |\n| gemma-2-9b-it | 1.78x | 2.11x | 3.83x |\n| deepseek-coder-7b-instruct-v1.5 | 2.86x | 3.45x | 4.27x | \n\nThese numbers align with the results we originally reported in the main text. Generally, the convergence curves for the new models strongly resemble those from our original evaluation, with fast convergence at the first few steps, tapering off closer to k=10. Also, MCMC-restart continues to display faster convergence than the other 2 proposals, although the final KL-divergence value at k=10 is similar for all flavors. \n\nWe also ran the fuzzing tasks from Section 4.2, using Qwen2.5-Coder-7B-Instruct (due to the limited time and resources, we could not run more models on this benchmark). The detailed results are shown in the tables below, but in summary the results for this new model are consistent with our reported findings: MCMC-based methods again demonstrate similar KL-divergence trends and a sustained advantage in coverage over the GCD and Grammarinator baselines. The relative performance ordering of all methods remained the same across both language models. \n### XML KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):\n| **Method**  | **k=2** | **k=3** | **k=4** | **k=5** | **k=6** | **k=7** | **k=8** | **k=9** | **k=10** |\n| ------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ----------- |\n| MCMC-Uniform  | 167   | 149    | 148     | 140   | 133   | 131    | 126      | 133      | 128         |\n| MCMC-Priority    | 126    | 113      | 102  | 101     | 104   | 99  | 100    | 96         | 94          |\n| MCMC-Restart   | 75     | 66        | 67    | 73       | 74      | 72      | 69    | 71    | 77          |\n\n### SQL KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):\n\n| **Method**   | **k=2** | **k=3** | **k=4** | **k=5** | **k=6** | **k=7** | **k=8** | **k=9** | **k=10** |\n| ------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ----------- |\n| MCMC-Uniform   | 134      | 117      | 107      | 104      | 99       | 90       | 89     | 87  | 78        |\n| MCMC-Priority   | 77       | 78       | 75       | 72       | 68       | 59       | 55       | 58       | 68        |\n| MCMC-Restart   | 76       | 70       | 47       | 44       | 41       | 41       | 45       | 46       | 47        |\n\n### XML branch coverage after 1 hour of fuzzing:\n| **Method**       | **Llama-3.1-8B** | **Qwen-2.5-7B** |\n| ---------------- | ---------------- | --------------- |\n| GCD              | 10.67            | 10.76           |\n| Grammarinator    | 8.49             | 8.41            |\n| MCMC-Uniform-10  | 12.16            | 11.98           |\n| MCMC-Priority-10 | 12.81            | 12.02           |\n| MCMC-Restart-10  | 12.00            | 11.76           |\n\n### SQL branch coverage after 1 hour of fuzzing:\n\n| **Method**       | **Llama-3.1-8B** | **Qwen-2.5-7B** |\n| ---------------- | ---------------- | --------------- |\n| GCD              | 28.26            | 26.32           |\n| Grammarinator    | 25.04            | 23.48           |\n| MCMC-Uniform-10  | 32.93            | 30.15           |\n| MCMC-Priority-10 | 33.70            | 31.05           |\n| MCMC-Restart-10  | 32.36            | 30.44           |\n\n\n\n> A larger sota model would likely produce many samples with valid grammar (hence the increase in popularity of rejection sampling)\n\nTo address the reviewer's question, we performed a new rejection-sampling experiment with Qwen2.5-Coder-7B-Instruct and a larger Qwen2.5-Coder-32B-Instruct model. The results are consistent with our original findings: the success rates remained low, at 0.6% (3/500 valid samples) for the 32B model, and 0.2% (1/500 valid samples) for the 7B model.\nWe agree with the reviewer that for simple or cleverly prompted constraints, larger models can improve the effectiveness of rejection sampling.\n\n> How does the coverage change as we increase the number of seeds?\n\nWe embraced the reviewer’s suggestion and conducted a new set of experiments extending our original methodology. For each generation method, we ran 1-hr fuzzing campaigns with varying numbers of initial seeds: 50, 100, 200, and 500 (we show results for Llama-3.1-8B as well as one of the additional models, Qwen2.5-Coder-7B-Instruct, used in the rest of the author response to show that our results are not specific to one model). (We can include an experiment with 1000 seeds for the final version of the paper as such an experiment requires more time than we had available). This experiment directly measures how the diversity and quality of the initial seed pool impact the fuzzer's ability to discover new coverage over a sustained run.\n\nThe tables below show:\n- Adding more seeds generally improves coverage for all methods \n- Our MCMC-based methods outperform the baselines (GCD and Grammarinator) at every seed count. Particularly, even at the lowest seed count (50) the MCMC methods all achieve a higher coverage than the GCD baseline with the highest seed count (500). We will gladly add this experiment to the paper to show the importance of diversity in samples (rather than quantity).\n### XML branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):\n| **Method**               | **N=50**   | **N=100**  | **N=200**  | **N=500**  |\n|--------------------------|------------|------------|------------|------------|\n| GCD                      | 10.65   | 10.67   | 10.76   | 10.88   |\n| Grammarinator            | 8.41    | 8.49   | 8.51    | 8.53  |\n| MCMC-Uniform-10          | 12.10   | 12.16   | 12.38   | 12.47   |\n| MCMC-Priority-10         | 12.21   | 12.81   | 12.86   | 12.90   |\n| MCMC-Restart-10          | 11.69   | 12.00   | 12.02   | 12.15   |\n### SQL branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):\n| **Method**                | **N=50**    | **N=100**   | **N=200**   | **N=500**   |\n|--------------------------|-------------|-------------|-------------|-------------|\n| GCD                      | 27.27  | 28.26  | 28.46    | 28.39  |\n| Grammarinator            | 23.48  | 25.04   | 26.08  | 26.01    |\n| MCMC-Uniform-10          | 30.72   | 32.93  | 32.94   | 33.09    |\n| MCMC-Priority-10         | 31.08   | 33.70   | 33.80    | 33.83    |\n| MCMC-Restart-10          | 30.57   | 32.36  | 32.84   | 32.89    |\n\n\n### XML branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds N):\n\n| **Method**                | **N=50**   | **N=100**  | **N=200**  | **N=500**  |\n|--------------------------|------------|------------|------------|------------|\n| GCD                      | 10.76  | 10.80   | 10.81   | 10.78  |\n| Grammarinator            | 8.41  | 8.49   | 8.51    | 8.53  |\n| MCMC-Uniform-10          | 11.98   | 12.02   | 12.18   | 12.27  |\n| MCMC-Priority-10         | 12.02   | 12.09   | 12.21  | 12.25  |\n| MCMC-Restart-10          | 11.76   | 11.80   | 11.90   | 12.06  |\n\n### SQL branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds N):\n\n| **Method**       | **N=50** | **N=100** | **N=200** | **N=500** |\n| ---------------- | -------- | --------- | --------- | --------- |\n| GCD              | 26.32    | 28.15     | 28.37     | 28.15     |\n| Grammarinator    | 23.48    | 25.04     | 26.08     | 26.01     |\n| MCMC-Uniform-10  | 30.15    | 32.20     | 32.32     | 32.36     |\n| MCMC-Priority-10 | 31.05    | 32.75     | 32.97     | 33.00     |\n| MCMC-Restart-10  | 30.44    | 31.85     | 31.85     | 32.02     |\n\n\n\n> How does different tokenization setups of the different LLMs affect the approach? For example, a different LLM may tokenize a particular piece or terminal of CFG differently, does the proposed approach require much changes to be able to handle that?\n\nOur implementation builds on existing grammar-constrained decoding (GCD) implementations and does not require any changes when changing the model, as long as the model is supported by the underlying GCD library. That is, the problem of dealing with how different tokens match different terminals in the grammar is handled by the GCD implementation and our sampling approach does not have to worry about it."}, {"review_id": "1uN7ePWCAK", "reviewer": "Reviewer_NeNk", "summary": "The manuscript proposes a grammar-aligned Markov-Chain Monte-Carlo (MCMC) framework that turns any grammar-constrained decoder (GCD) into a provably correct sampler for language-model outputs under hard constraints. The authors apply a Metropolis–Hastings acceptance test based on the language model likelihood. The framework ensures three key properties of the generated chain:\n- It never violates the grammar.\n- It converges monotonically to the true conditional distribution.\n- In practice, it yields high-quality samples after only a few rejection steps.\n\nExperiments on the SyGuS synthesis benchmark, constituency parsing, and real-world fuzzing of libxml2 and SQLite show large reductions in empirical KL-divergence compared to GCD or ASAp.\nThe authors investigate three concrete proposal distributions: Restart, Uniform, and Priority, which offer different speed/quality trade-offs for constrained sampling.", "questions": "1. Beyond CFGs: How would the Metropolis–Hastings acceptance behave for grammars that are not context-free?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Weaknesses\n- Limited model diversity in experiments: all experiments use only Llama-3.1-8B-Instruct. It is unsure how the behavior of constrained sampling may vart from a model to another, especially larger models.\n\n- Narrow experimental scope: the authors experiment with just two fuzzing targets and use single-hour runs. Other targets/domains remain untested (e.g., dialogue).\n\n- Restriction to CFGs: it seems the method does not extend to context-sensitive or semantic constraints enforced by validators.\n\n## Strengths:\n- Clear theoretical grounding: the paper formalizes three desiderata (constraint-satisfying, monotonically converging, efficient) and proves the proposed algorithm meets the first two.\n\n- Simplicity and practicality: wraps any off-the-shelf GCD. There is no need for retraining or surrogate models.\n\n- Consistent empirical evidence: lower KL on three benchmark suites and up to 1.2 × branch-coverage gains in fuzzing compared with prior samplers.", "was_revised": true, "final_justification": "The additional ablations performed by the authors strengthen the paper and make it an important work for constraint decoding. Therefor,e I have updated my score to recommend acceptance of the paper.", "rebuttal": "We thank the reviewer for their detailed and thoughtful evaluation of our work. We appreciate the recognition of the theoretical grounding, simplicity, and empirical effectiveness of our proposed framework. We also value the constructive comments regarding model diversity, experimental scope, and the limitations to context-free grammars, which we will address in the revised version.\n\n\n> Limited model diversity in experiments: all experiments use only Llama-3.1-8B-Instruct. … especially larger models.\n\nWe agree with the reviewer’s assessment and have run additional evaluation for a subset of our benchmark tasks during the response period, and will include comprehensive runs of these experiments in the final version. We emphasize that no modifications to our implementation are needed to switch to different models and their specific tokenization schemes..\n\nFor the program synthesis benchmarks, we have run the BV4 benchmarks with 3 additional SOTA models: `Qwen2.5-Coder-7B-Instruct`, `gemma-2-9b-it`, and `deepseek-coder-7b-instruct-v1.5`. Across all 14 tasks and 3 models, we see that samples from each of the MCMC instances have lower KL-divergence w.r.t $P^G$ than GCD, with improvements rates presented in the following table\n\n|  | Uniform | Priority | Restart |\n|--|--|--|--|\n| Qwen2.5-Coder-7B-Instruct | 1.23x | 1.42x | 2.71x |\n| gemma-2-9b-it | 1.78x | 2.11x | 3.83x |\n| deepseek-coder-7b-instruct-v1.5 | 2.86x | 3.45x | 4.27x | \n\nThese numbers align with the results we originally reported in the main text. Generally, the convergence curves for the new models strongly resemble those from our original evaluation, with fast convergence at the first few steps, tapering off closer to k=10. Also, MCMC-restart continues to display faster convergence than the other 2 proposals, although the final KL-divergence value at k=10 is similar for all flavors. \n\nWe also ran the fuzzing tasks from Section 4.2, using Qwen2.5-Coder-7B-Instruct (due to the limited time and resources, we could not run more models on this benchmark). The detailed results are shown in the tables below, but in summary the results for this new model are consistent with our reported findings: MCMC-based methods again demonstrate similar KL-divergence trends and a sustained advantage in coverage over the GCD and Grammarinator baselines. The relative performance ordering of all methods remained the same across both language models. \n### XML KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):\n| **Method**  | **k=2** | **k=3** | **k=4** | **k=5** | **k=6** | **k=7** | **k=8** | **k=9** | **k=10** |\n| ------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ----------- |\n| MCMC-Uniform  | 167   | 149    | 148     | 140   | 133   | 131    | 126      | 133      | 128         |\n| MCMC-Priority    | 126    | 113      | 102  | 101     | 104   | 99  | 100    | 96         | 94          |\n| MCMC-Restart   | 75     | 66        | 67    | 73       | 74      | 72      | 69    | 71    | 77          |\n\n### SQL KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):\n\n| **Method**   | **k=2** | **k=3** | **k=4** | **k=5** | **k=6** | **k=7** | **k=8** | **k=9** | **k=10** |\n| ------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ----------- |\n| MCMC-Uniform   | 134      | 117      | 107      | 104      | 99       | 90       | 89     | 87  | 78        |\n| MCMC-Priority   | 77       | 78       | 75       | 72       | 68       | 59       | 55       | 58       | 68        |\n| MCMC-Restart   | 76       | 70       | 47       | 44       | 41       | 41       | 45       | 46       | 47        |\n\n### XML branch coverage after 1 hour of fuzzing:\n| **Method**       | **Llama-3.1-8B** | **Qwen-2.5-7B** |\n| ---------------- | ---------------- | --------------- |\n| GCD              | 10.67            | 10.76           |\n| Grammarinator    | 8.49             | 8.41            |\n| MCMC-Uniform-10  | 12.16            | 11.98           |\n| MCMC-Priority-10 | 12.81            | 12.02           |\n| MCMC-Restart-10  | 12.00            | 11.76           |\n\n### SQL branch coverage after 1 hour of fuzzing:\n\n| **Method**       | **Llama-3.1-8B** | **Qwen-2.5-7B** |\n| ---------------- | ---------------- | --------------- |\n| GCD              | 28.26            | 26.32           |\n| Grammarinator    | 25.04            | 23.48           |\n| MCMC-Uniform-10  | 32.93            | 30.15           |\n| MCMC-Priority-10 | 33.70            | 31.05           |\n| MCMC-Restart-10  | 32.36            | 30.44           |\n\n\n\n\n> … just two fuzzing targets and use single-hour runs. Other targets/domains remain untested (e.g., dialogue).\n\nThanks for the observation. To evaluate the long-term impact of the generated seeds, we have conducted new, longer fuzzing experiments for up to 6 hours (see tables below). \n\nIn the 6-hour runs, we see that for the XML target, coverage gains are minimal after the first hour. However, for the SQL target we observe sustained coverage growth over the 6 hours. Remarkably, the performance advantage of the MCMC methods widens over time. \nWe will gladly include this longer running experiment (as well as a 24-hr one in the paper).\n\n### XML branch coverage for corpus of 100 seeds (Llama-3.1-8B, varying fuzzing duration T):\n\n\n| **Method**       | **T=1 h** | **T=2 h** | **T=3 h** | **T=6 h** |\n| ---------------- | --------- | --------- | --------- | --------- |\n| GCD              | 10.67     | 10.71     | 10.72     | 10.73     |\n| Grammarinator    | 8.49      | 8.56      | 8.59      | 8.63      |\n| MCMC-Uniform-10  | 12.16     | 12.19     | 12.20     | 12.21     |\n| MCMC-Priority-10 | 12.81     | 12.82     | 12.84     | 12.85     |\n| MCMC-Restart-10  | 12.00     | 12.06     | 12.07     | 12.09     |\n\n### SQL branch coverage for corpus of 100 seeds (Llama-3.1-8B, varying fuzzing duration T):\n\n| **Method**       | **T=1 h** | **T=2 h** | **T=3 h** | **T=6 h** |\n| ---------------- | --------- | --------- | --------- | --------- |\n| GCD              | 28.26     | 29.84     | 31.04     | 32.49     |\n| Grammarinator    | 25.04     | 26.15     | 27.84     | 28.96     |\n| MCMC-Uniform-10  | 32.93     | 33.91     | 35.62     | 37.23     |\n| MCMC-Priority-10 | 33.70     | 35.12     | 37.43     | 39.85     |\n| MCMC-Restart-10  | 32.36     | 33.54     | 34.78     | 36.12     |\n\nWe were not able to run a completely new application within the time of the rebuttal, but we will gladly add one more domain in the final version.\n\n\n\n\n> Restriction to CFGs: it seems the method does not extend to context-sensitive or semantic constraints enforced by validators. Beyond CFGs: How would the Metropolis–Hastings acceptance behave for grammars that are not context-free?\n\nThis is an excellent point, and we are happy to elaborate further on it. While our method is presented in the context of grammar-constrained decoding, it is important to note that it is not limited to it, and in fact it is generally applicable whenever the constraint is checkable in an incremental way for sequence prefixes. For instance, [1] presents a benchmark of context-sensitive pattern matching tasks, where an incremental pattern validator is available. Another example is Type-Constrained Code Generation [2], an exciting application where constraints are also computed in an incremental manner. For both of these constrained decoders, our approach could be applied.\n\n[1] Lipkin, B., ... & Vieira, T. (2025). Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling. arXiv preprint arXiv:2504.05410.\n\n[2] Niels Mündler, Jingxuan He, Hao Wang, Koushik Sen, Dawn Song, and Martin Vechev.. Type-Constrained Code Generation with Language Models. PLDI 2025"}, {"review_id": "CbjrhHjnLe", "reviewer": "Reviewer_4jfZ", "summary": "The authors present a general approach to conditionally sampling from language models subject to constraints (here specifically membership in a context-free language). They note drawbacks with existing approaches: rejection sampling yields valid samples but runtime scales unfavorably when the marginal likelihood of satisfying the constraint under the unconditional model is low, grammar-constrained decoding (GCD) yields constraint-satisfying samples by design, but distorts the distribution over completed strings. They propose a simple MCMC algorithm leveraging GCD in the proposal distribution (with a few different methods attempted for editing sampled traces), then accept/reject edits via MH using the LM likelihood. This yields a correct inference algorithm targeting the true conditional posterior as time grows. The authors present both intrinsic results showing that this procedure empirically begins to converge within a reasonably small number of steps by showing a decrease in a Monte Carlo KL estimator. They also present extrinsic quality results, finding that this approach yields more diverse branch coverage in a downstream program fuzzing task.", "questions": "Can you include some plots/tables of how long it takes to generate the seed samples across the different conditions? Since it presumably takes ~10x longer to produce 100 samples from the MCMC (k=10) condition than GCD, using 100 seed samples from each seems to be an odd comparison as MCMC spends considerably more time refining each sample. A more fair comparison might be to produce however many K samples you can from each condition in some fixed time budget then use all those seeds.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and the problem presentation is clear. This is an important issue worth focusing on. The algorithm is a reasonable candidate solution, and the evaluation domain is well-suited for the goal of measuring diversity.\n- I like the comparison between the uniform, priority, and restart proposals.\n\nWeaknesses:\n- The paper neglects a body of highly related work, missing high-performing baselines. Loula et al (2024), Ahmed et al (2024), and Lipkin et al (2025) also presented this same problem of GCD distortion. All these works presented solutions using GCD as proposal distributions that are then updated using sequential importance sampling and resampling. The methods presented in these papers yield a different set of asymptotic guarantees (convergence in number of particles rather than time), yet can be parallelized as opposed to sequential editing, yielding faster empirical runtimes. It would be good to see some empirical comparison to this family of SMC algorithms, as they’re a much stronger baseline than GCD or ASAp. For example, even ignoring parallelism speedups, MCMC restart for k=10 steps vs. SMC with k=10 particles followed by a final resample proportional to the weights should give a compute-matched (FLOPs) way to generate 1 sample. It would be ideal to see these experiments. Minimally, I would like to see this comparison further discussed and this paper more accurately put into the context of related work.\n- Very limited evaluation: 1 model and 1 task with 2 domains and weak baselines.\n\nReferences\n- Loula, J., ... & O'Donnell, T. J. (2024). Syntactic and semantic control of large language models via sequential monte carlo. arXiv preprint arXiv:2504.13139.\n- Ahmed, K., Chang, K. W., & Broeck, G. V. D. (2024). Controllable Generation via Locally Constrained Resampling. arXiv preprint arXiv:2410.13111.\n- Lipkin, B., ... & Vieira, T. (2025). Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling. arXiv preprint arXiv:2504.05410.", "was_revised": true, "final_justification": "This is an important topic area with a clear problem presentation and sound approach. The new analyses presented during reviews cover my key concerns surrounding inadequate baselines and discussion of related work. Should these additions be incorporated, and the paper narrative updated to put the results into appropriate context, I recommend acceptance of this paper.", "rebuttal": "> The paper neglects a body of highly related work, missing high-performing baselines. Loula et al (2024), Ahmed et al (2024), and Lipkin et al (2025) also presented this same problem of GCD distortion. …  even ignoring parallelism speedups, MCMC restart for k=10 steps vs. SMC with k=10 particles followed by a final resample proportional to the weights should give a compute-matched (FLOPs) way to generate 1 sample. It would be ideal to see these experiments. Minimally, I would like to see this comparison further discussed and this paper more accurately put into the context of related work.\n\nWe thank the reviewer for highlighting this highly relevant literature. We acknowledge that these works were not cited in our original submission. Notably, two of the references were either unpublished or had only very recently appeared at the time of submission, which contributed to their omission. We agree with the reviewer that comparison with this concurrent work adds to the quality of our paper.\n\nThe approaches presented in [1] are the ones most similar to our proposed method, since both apply Monte Carlo methods over token sequences to approximate $P^G$ ($g$ if using the notation from [1]). Whereas we approach this problem by using MCMC, [1] implements both Resampled Importance Sampling and Sequential Monte Carlo (SMC) or Particle Filtering. Any of these methods are theoretically guaranteed to produce samples from the target distribution when $N$ tends to infinity, but MCMC does not directly reduce to any of the other two algorithms or vice versa. \n\nBefore moving to the theoretical comparison of the two approaches, we addressed the reviewer's suggestion and ran a preliminary evaluation comparing our proposed method with the SMC-AWRS method proposed in [1] and [3]. On a subset (due to timing constraints) of 8/14 BV4 program synthesis tasks, we observe that MCMC-restart achieves 1.86x (geo. mean) lower (i.e., better) KL-divergence on compute-matched runs (k=10 steps vs k=10 particles) vs SMC. We will add a detailed, more comprehensive version of this experiment to the paper.\n\nA clear advantage of the alternative methods in [1] is the inclusion of expensive potentials to score the quality of generations. This is done by adjusting the probability of sequences by the (ratio of) change of potential induced by each of its next-token completions. This is a nice way of integrating such signals into the decoding process, and the details on how to add an analogous factor to the Metropolis-Hastings equations could be a direction of further research. However, in the case of simple grammar-constrained decoding which we study, this notion goes unused, and these approaches reduce to the vanilla versions of IS and SMC.\n\nThere are further connections that can be drawn between our approach and those presented in [1]: Importance Sampling and MCMC-restart lend themselves to more aggressive parallelization, since one can draw N complete samples independently and perform one final round of drawing to obtain a final sample. On the other hand SMC is more similar to MCMC-uniform or MCMC-restart, in the sense that some additional computation has to be made at each generation step of the sequences, although for MCMC this computation is only dependent on the previous state of the same sequence, whereas for SMC it depends on the state of the rest of the particles as well.\n\nOverall, we find no strong formal argument to position either one with clear advantage over the others in the setting of grammar constrained decoding. We will add a detailed comparison to our paper.\n\nWith respect to [3], we find that the goal of this paper is slightly different from ours. Whereas we deal with the problem of approximately sampling from the constrained distribution across sequences of tokens, [3] is concerned about sampling from the constrained distribution of possible next-tokens given a prefix [3] (Eq. 1). The goal is to avoid potentially expensive masking operations over the entire vocabulary of LMs, and replace them with a rejection sampling approach. The main algorithm proposed, AWRS, is evaluated as a subcomponent of the SMC algorithm, where it in fact yields performance improvements. The question then arises of whether AWRS can be integrated into our MCMC approach. We lean toward the positive, and leave further analysis to future work.\n\nFinally, [2] introduces another solution to the locally constrained decoding distortion problem by sampling a constrained sequence in a 3-step fashion: 1) obtain an unconstrained sample via the autoregressive distribution, 2) project into a constrained space from the pseudolikelihood induced by the unconstrained sample 3) apply resampled importance sampling to correct for bias. The idea of starting from an unconstrained (and undistorted) sample and projecting that to the constrained set is appealing as a proposal distribution for the MCMC approach as well. The projection operator introduced in [2] however seems to require a non-trivial implementation and it is not clear whether it is optimal or an alternative could be more effective in practice. This is again a direction worth exploring and integrating in the future.\n\nIn summary, the various existing solutions to the problem we explore in our paper, are largely orthogonal and have merits of their own, and their different components are amenable to be integrated directly into our proposed solution, or vice versa, as part of future research in this area.\n\n[1]  Loula, J., ... & O'Donnell, T. J. (2024). \n\n[2]  Ahmed, K., Chang, K. W., & Broeck, G. V. D. (2024). \n\n[3]  Lipkin, B., ... & Vieira, T. (2025).  \n\n> Very limited evaluation: 1 model and 1 task with 2 domains and weak baselines.\n\nDue to space limitation in the response, we kindly ask the reviewer to consult the answers to Reviewer 2 for additional experiments involving further models and to Reviewer 1 for a clarification that our evaluation involves more than just one task.\n\n> Can you include some plots/tables of how long it takes to generate the seed samples across the different conditions? Since it presumably takes ~10x longer to produce 100 samples from the MCMC (k=10) condition than GCD, using 100 seed samples from each seems to be an odd comparison as MCMC spends considerably more time refining each sample. A more fair comparison might be to produce however many K samples you can from each condition in some fixed time budget then use all those seeds.\n\nThis is a very good point and we thank the reviewer for this question. To answer it we performed two additional experiments:\n\n- **Time taken to generate**: On our hardware (8x NVIDIA RTX 2080 Ti), for the fuzzing application in Section 4.2, producing a single GCD sample takes ~20 seconds. Our MCMC methods with k=10 steps take ~210 seconds per sample (as expected, ~10x longer), as they perform 10 MCMC steps (though the individual samples of the Restart method could be parallelized). We will add detailed tables. \n- **Adapting number of seeds based on time taken to generate**: To answer the second part of the reviewer’s question, we ran the fuzzer using different numbers of seeds. Our experiment (see Tables below) shows that fidelity in sampling is more important than quantity: our MCMC methods with just 50 seeds (sampled with k=10) are able to achieve higher coverage than GCD using 500 seeds (i.e., the seeds sampled using within the same time budget). We believe that having more high-quality seeds decreases the fuzzer performance as it dilutes its mutation budget across multiple seeds (if the seeds are not good, this results in low coverage).\n### XML branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):\n| **Method**               | **N=50**   | **N=100**  | **N=200**  | **N=500**  |\n|--------------------------|------------|------------|------------|------------|\n| GCD                      | 10.65   | 10.67   | 10.76   | 10.88   |\n| Grammarinator            | 8.41    | 8.49   | 8.51    | 8.53  |\n| MCMC-Uniform-10          | 12.10   | 12.16   | 12.38   | 12.47   |\n| MCMC-Priority-10         | 12.21   | 12.81   | 12.86   | 12.90   |\n| MCMC-Restart-10          | 11.69   | 12.00   | 12.02   | 12.15   |\n### SQL branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):\n| **Method**                | **N=50**    | **N=100**   | **N=200**   | **N=500**   |\n|--------------------------|-------------|-------------|-------------|-------------|\n| GCD                      | 27.27  | 28.26  | 28.46    | 28.39  |\n| Grammarinator            | 23.48  | 25.04   | 26.08  | 26.01    |\n| MCMC-Uniform-10          | 30.72   | 32.93  | 32.94   | 33.09    |\n| MCMC-Priority-10         | 31.08   | 33.70   | 33.80    | 33.83    |\n| MCMC-Restart-10          | 30.57   | 32.36  | 32.84   | 32.89    |\n\n\n### XML branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds N):\n\n| **Method**                | **N=50**   | **N=100**  | **N=200**  | **N=500**  |\n|--------------------------|------------|------------|------------|------------|\n| GCD                      | 10.76  | 10.80   | 10.81   | 10.78  |\n| Grammarinator            | 8.41  | 8.49   | 8.51    | 8.53  |\n| MCMC-Uniform-10          | 11.98   | 12.02   | 12.18   | 12.27  |\n| MCMC-Priority-10         | 12.02   | 12.09   | 12.21  | 12.25  |\n| MCMC-Restart-10          | 11.76   | 11.80   | 11.90   | 12.06  |\n\n### SQL branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds N):\n\n| **Method**       | **N=50** | **N=100** | **N=200** | **N=500** |\n| ---------------- | -------- | --------- | --------- | --------- |\n| GCD              | 26.32    | 28.15     | 28.37     | 28.15     |\n| Grammarinator    | 23.48    | 25.04     | 26.08     | 26.01     |\n| MCMC-Uniform-10  | 30.15    | 32.20     | 32.32     | 32.36     |\n| MCMC-Priority-10 | 31.05    | 32.75     | 32.97     | 33.00     |\n| MCMC-Restart-10  | 30.44    | 31.85     | 31.85     | 32.02     |"}]

Author rebuttal:

Meta-review: **Contribution:** This is a straightforward method for correcting (debiasing) the naive left-to-right algorithm for constrained sampling from autoregressive LMs.  It's MCMC where a proposal consists of throwing away some suffix and regenerating it.  The simplest and most effective version is to throw away the whole string and regenerate it - the independent Metropolis algorithm.  A couple of other heuristics are tried as well.

**Strengths:** The method is unbiased in the limit (for what that's worth), requires no training, is demonstrated to be practical in a situation where rejection sampling is not, and works well enough that it should be considered as a simple baseline beyond rejection sampling by papers that are presenting more complicated methods such as SMC.  There's an interesting downstream evaluation.

**Weaknesses:** The evaluation is mostly internal among variants of the proposal distribution.  It didn't originally compare with other constrained sampling methods.  In the rebuttal, the authors finally gave a preliminary comparison showing that they beat a strong competitor; but it was only under one condition, not a systematic study varying the target distribution and the amount of computation.

Personally, I would also have liked to see study of [additional proposal distributions](https://openreview.net/forum?id=M1b7IuY6Co&noteId=zIDosfH7ka), more constrained generation settings, and [additional evaluation metrics](https://openreview.net/forum?id=M1b7IuY6Co&noteId=LqDKXB2Vz5).  However, the authors did not have an opportunity to reply to these AC comments.

**Most important reason to accept:** Consensus among reviewers.  

**Discussion during the rebuttal period:** This was where the authors compared to other methods from the literature (SMC, as well as rejection sampling), which should have been done in the original submission.  However, this comparison was only a "preliminary evaluation"; they promised to "add a detailed version of this experiment to the paper."

The authors also evaluated on additional LLMs as requested by the reviewers, although this may be less important.

-------
# Comments from AC to reviewers during discussion period

Shared here because they may be useful to authors.

## Comment from AC

I believe the problem is presented as drawing a single sample from the target distribution.  

However, the proposed MCMC methods actually draw many samples from the proposal distribution; so do the alternatives considered (rejection sampling, importance sampling, SMC).  Each of the proposed and alternative methods can convert its sequence of samples into a unweighted or weighted ensemble of samples, which is biased but becomes unbiased in the infinite-sample limit.  That is commonly used for Monte Carlo estimation of an expectation under the target distribution.  

Such an ensemble is an estimate of the probability distribution and should be evaluated on its divergence from the (estimated) target distribution. This is better than simply evaluating the single-sample case as done in the submission, because 
* it reduces the variance of the evaluation metric (line 237)
* it allows the computation of other evaluation metrics, such as total variation distance (TVD) (which can be used to bound the error of Monte Carlo expectation estimation)
* the evaluation in the paper favors the MCMC methods because it uses only the last sample from the Markov chain, which is closer in distribution to the target than the earlier "burn-in" samples were.  I believe that with only the last sample, TVD converges faster under independent MH than under resampled importance sampling, but that neither method dominates [the earlier samples are used as well](http://users.stat.umn.edu/~geyer/mcmc/one.html).  So the MCMC methods should be compared to resampled importance sampling (and SMC) in both settings, not just the one that favors the MCMC methods.

Pro tip: For independent Metropolis-Hastings (the paper's MCMC-Restart method), the unweighted ensemble of MCMC states can be converted to a better weighted ensemble by Rao-Blackwellizing the order of the samples ([Atchadé and Perron, 2005](https://www3.stat.sinica.edu.tw/statistica/oldpdf/A15n11.pdf)).

## Comment from AC
Thanks to all of you for your reviews and your discussions with the authors, which I think will improve the paper and help situate it better with respect to other work.

The paper appears to be a good practical nugget - it's nice when simple techniques work.  It seems that you are all recommending acceptance at this point.

I think this algorithm was not entirely unknown in the structured prediction community.  I remember discussing it around 15 years ago :), in the context of Gibbs or MH sampling from an energy-based distribution over the accepting paths of a finite-state automaton (or derivations from a context-free grammar).  However, I can't turn up a mention in the literature.

There are natural generalizations too, including infilling versions that replace an infix rather than a suffix, versions that incorporate the automaton (or grammar) into the proposal distribution, and population-based methods with crossover (evolutionary Monte Carlo).

What do you think of the prioritization heuristic used in this submission (line 202)?  As I read it, it considers the perplexity only at the single next token, which seems surprisingly local and tokenizer-dependent to me.  Also, I wonder why perplexity and not, say, log-perplexity (= entropy).  There is a bunch of prior work on learning where to sample, e.g., https://proceedings.mlr.press/v38/shi15.html , which should be cited, although I suppose this paper is trying to avoid any modeling or learning in the interest of simplicity.

### Reply from Reviewer 4jfZ

Agreed re this problem being known in the structured prediction community for sampling from globally normalized energy-based models. Here are a couple of the earliest works I know that characterized this problem: (1) Lafferty et al (2001) on CRFs and "label bias" in structured prediction (2) Rosenfeld et al (2001) on whole-sentence exponential language models and sampling from these models via MCMC.

That being said, while this issue was better understood by the classical NLP community, it has been mostly ignored as part of the modern LLM discourse, and is worth being restated. There are also unique challenges to this modern instantiation, e.g., alignment mismatch between grammar terminals and LM tokens, very large token vocabulary sizes, etc., that yield different practical tradeoffs with some classical approaches.

Re the priority heuristic, I think it seems reasonable to use these points for refinement. Yes, you are right that this is quite local, i.e., each next-token probability yields the marginal probability over suffixes without the constraint, and after applying the constraint conditional next-token probabilities would change. That being said, doing something more global would require solving an additional inference problem of the same form as the original problem, and this needs to bottom out to a heuristic at some point. The general idea of targeting search at points of "uncertainty" is reasonable at a high-level. I would have found entropy more intuitive, but perplexity is fine. It is probably worth noting, though, that these decisions are relatively arbitrary and that there are plenty of other options one could have considered.

#### Reply from AC
To clarify, I wasn't saying only that the problem was known, but that this particular MCMC sampler was known.
Evaluating it in a modern setting against modern alternatives may still be helpful.
Decision: Accept (poster)