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.

We 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.

The 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.

Before 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.

A 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.

There 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.

Overall, 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.

With 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.

Finally, [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.

In 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.

[1] Loula, J., ... & O'Donnell, T. J. (2024).

[2] Ahmed, K., Chang, K. W., & Broeck, G. V. D. (2024).

[3] Lipkin, B., ... & Vieira, T. (2025).

Very limited evaluation: 1 model and 1 task with 2 domains and weak baselines.

Due 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.

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.

This is a very good point and we thank the reviewer for this question. To answer it we performed two additional experiments:

• 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.
• 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).

XML branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):

SQL branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):

XML branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds N):

SQL branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds N):

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.

Limited model diversity in experiments: all experiments use only Llama-3.1-8B-Instruct. … especially larger models.

We 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..

For 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

These 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.

We 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.

XML KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):

SQL KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):

XML branch coverage after 1 hour of fuzzing:

SQL branch coverage after 1 hour of fuzzing:

… just two fuzzing targets and use single-hour runs. Other targets/domains remain untested (e.g., dialogue).

Thanks 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).

In 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. We will gladly include this longer running experiment (as well as a 24-hr one in the paper).

XML branch coverage for corpus of 100 seeds (Llama-3.1-8B, varying fuzzing duration T):

SQL branch coverage for corpus of 100 seeds (Llama-3.1-8B, varying fuzzing duration T):

We 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.

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?

This 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.

[1] Lipkin, B., ... & Vieira, T. (2025). Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling. arXiv preprint arXiv:2504.05410.

[2] Niels Mündler, Jingxuan He, Hao Wang, Koushik Sen, Dawn Song, and Martin Vechev.. Type-Constrained Code Generation with Language Models. PLDI 2025

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.

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?

Thanks 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).

The 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.

As 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.

[1] Eric Schkufza, Rahul Sharma, and Alex Aiken. 2013. Stochastic superoptimization. ASPLOS '13

[2] Aditya V. Nori, Sherjil Ozair, Sriram K. Rajamani, and Deepak Vijaykeerthy. 2015. Efficient synthesis of probabilistic programs. PLDI '15

[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

[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.

Experimental results are only reported on two tasks

We 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).

Our 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. We can incorporate relevant domains proposed in the suggested related work for the final version of this work.

[1] Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D'Antoni. Grammar Aligned Decoding. NeurIPS 2024

The paper lacks of discussion of and comparison with other Monte Carlo methods, e.g., https://arxiv.org/pdf/2504.13139

Both 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.

Before 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.

A 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.

There 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.

Overall, 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.

[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.

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.

only really uses a single model…How does different tokenization setups of the different LLMs affect the approach?

We 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..

For 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

These 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.

We 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.

XML KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):

SQL KL-divergence for different MCMC-methods (Qwen-2.5-7B, step count k):

XML branch coverage after 1 hour of fuzzing:

SQL branch coverage after 1 hour of fuzzing:

A larger sota model would likely produce many samples with valid grammar (hence the increase in popularity of rejection sampling)

To 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. We agree with the reviewer that for simple or cleverly prompted constraints, larger models can improve the effectiveness of rejection sampling.

How does the coverage change as we increase the number of seeds?

We 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.

The tables below show:

• Adding more seeds generally improves coverage for all methods
• 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).

XML branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):

SQL branch coverage after 1 hour of fuzzing (Llama-3.1-8B, varying number of seeds N):

XML branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds N):

SQL branch coverage after 1 hour of fuzzing (Qwen-2.5-7B, varying number of seeds 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?

Our 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.