Pith. sign in

REVIEW 4 major objections 6 minor 4 cited by

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

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that wrapping grammar-constrained decoding in Metropolis-Hastings steps yields a sampler whose outputs are always grammar-valid and whose distribution converges monotonically to the language model's conditional…

desk verdict A sensible MH-based sampler for grammar-constrained LM sampling, but the paper never defines the proposal probabilities needed for the acceptance ratio, so the central convergence theorem is unverified as written. read the letter →

arxiv 2506.05754 v1 pith:JTGW2HBA submitted 2025-06-06 cs.AI cs.CLcs.LG

Emmanuel Anaya Gonzalez , Sairam Vaidya , Kanghee Park , Ruyi Ji , Taylor Berg-Kirkpatrick , Loris D'Antoni This is my paper
classification cs.AIcs.CLcs.LG
keywords constrainedsamplingMetropolis-HastingsMarkovchainMonteCarlogrammar-constraineddecodingcontext-freegrammarprogramfuzzingcoverage-guidedlanguagemodels
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish that constrained sampling from a language model over a context-free grammar need not trade validity for faithfulness. It proposes a Metropolis-Hastings chain whose proposals are grammar-constrained continuations of randomly truncated prefixes of the current sample, and proves that every output is grammar-valid while the output distribution converges monotonically to the true conditional distribution $P^G$ in total-variation distance. The practical stake is program fuzzing and other tasks that need diverse, valid documents: faithful sampling should give fuzzers better seed corpora, and the experiments report higher branch coverage than grammar-constrained decoding and adaptive sampling baselines. If correct, the result says any grammar-constrained decoder can be upgraded into a principled sampler with only a few extra steps.

What carries the argument

The central device is the prefix-resampling proposal: from the current sequence $w$, sample a truncation index $i$ from a distribution $p^w_{\mathrm{POS}}$, keep the prefix $w_{1:i}$, and complete it with grammar-constrained decoding to obtain a candidate $w'$. Its role is to generate constraint-satisfying candidates while preserving the possibility of large moves; the proof uses the fact that when the empty prefix has positive probability, every valid sequence can be proposed from every state, giving irreducibility and aperiodicity. The acceptance ratio $\alpha(w,w') = \min\{1, P(w')q(w\mid w') / (P(w)q(w'\mid w))\}$ uses raw language-model likelihoods because the grammar normalization constant of $P^G$ cancels, so the chain can be run without enumerating the language.

What would settle it

Take a small grammar with a finite language, enumerate all valid sequences, compute $P^G$ exactly, and run Algorithm 1 with $q(w'\mid w)$ evaluated exactly for the prefix-resampling proposal; if the long-run empirical output distribution differs from $P^G$ by more than sampling noise, the monotone-convergence claim fails. A cheaper check is to enumerate all valid completions of a short prefix and test whether top-$p$=0.9 grammar-constrained decoding assigns positive probability to each; any valid continuation with zero probability violates the irreducibility premise of Theorem 3.

Watch

Extended reading notes

Core claim

The paper's central claim is that a Metropolis-Hastings chain operating entirely inside $L(G)$ can be built by reusing any grammar-constrained decoder as the proposal. Starting from a GCD sample, each step truncates the current sequence at a random position and resamples the suffix with GCD; the move is accepted with the usual Metropolis-Hastings rule using the raw language-model probabilities. The authors prove that every state of the chain is grammar-valid, and that when the truncation distribution gives positive mass to the empty prefix, the chain is irreducible and aperiodic with stationary distribution $P^G$, so the output distribution converges to $P^G$ in total-variation distance and does so monotonically in the chain length. They instantiate three proposals -- uniform truncation, perplexity-biased truncation, and restart-from-scratch -- and report that each converges faster in KL divergence than grammar-constrained decoding and adaptive sampling on synthetic grammar benchmarks, and that fuzzing seeds produced this way improve branch coverage.

Load-bearing premise

The load-bearing premise is that the proposal probabilities $q(w\mid w')$ and $q(w'\mid w)$ for the prefix-resampling move are known and computed exactly in the acceptance ratio, and that every valid continuation has positive probability under the decoder; the paper does not supply either the computation or the support guarantee.

Editorial extensions

If this is right

  • Any grammar-constrained decoder becomes a grammar-aligned sampler when wrapped in the Metropolis-Hastings update, so constraint satisfaction is preserved by construction.
  • The output distribution of the chain approaches $P^G$ monotonically in total variation as the chain length grows, provided the empty prefix has positive proposal probability.
  • A few steps (around 5 to 10) already reduce KL divergence to $P^G$ by roughly 2 to 8 times relative to GCD and ASAp, and further steps saturate.
  • Fuzzers seeded with MCMC samples reach higher branch coverage than GCD, ASAp, or grammar-only baselines, with the largest gains for the priority proposal at 10 steps (33.70% versus 28.26% for GCD on the SQL benchmark).
  • The restart proposal, which discards the previous state and resamples from scratch, converges fastest in the experiments, suggesting that independent GCD samples are already a strong proposal.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not provide an algorithm for computing the proposal probabilities $q(w\mid w')$ and $q(w'\mid w)$ that the acceptance ratio requires; an implementation that approximates or drops this term is not sampling from $P^G$, so the open question is whether exact computation is tractable for realistic grammars.
  • The theoretical guarantee also assumes every valid continuation has positive probability under the GCD proposal; sampling with top-$p$=0.9, as done in the experiments, can violate this, so the practical convergence claim should be tested with exact enumeration on a small grammar.
  • Because the proposal family is decoupled from the chain, richer truncation distributions (for example, ones informed by expected future grammaticality) are a natural next step and could be compared on the same benchmarks.
  • The coverage experiments isolate seed quality, so a stronger downstream test would seed the fuzzer with exact samples from $P^G$ (computable only for finite grammars) and compare coverage against the MCMC seeds.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes a Metropolis-Hastings (MH) framework for constrained sampling from a language model conditioned on a context-free grammar. The target distribution is the grammar-restricted conditional distribution P^G. The sampler (Algorithm 1) starts from a grammar-constrained decoding (GCD) sample and iteratively proposes new valid sequences by resampling from a random prefix via GCD, accepting or rejecting according to an MH ratio that cancels the intractable normalization constant. Three proposal families are instantiated (Uniform, Priority, Restart). The paper claims that every output satisfies the constraint, that the output distribution converges monotonically in total variation distance to P^G, and that empirically the sampler converges faster than GCD and ASAp on synthetic benchmarks and yields higher fuzzing coverage on libxml2 and SQLite. Proofs are deferred to Appendix E, and experiments use Llama-3.1-8B with top-p=0.9 sampling.

Significance. If the central claim holds, this is a useful conceptual contribution: it shows that any GCD implementation can be wrapped in an MH loop to correct the distribution distortion of constrained decoding, and the empirical fuzzing results suggest practical benefits for seed generation. The convergence argument is standard MH theory plus a simple contraction step, which is appropriate and mostly correct. The paper also deserves credit for running a careful fuzzing evaluation with repeated trials and multiple coverage metrics. However, the load-bearing gap is that the proposal probabilities q(w'|w) used in the MH acceptance ratio are never defined or computed, so the central 'provably guarantees' claim is not currently verified as stated. The irreducibility assumption also conflicts with the experimental top-p setting. These issues are fixable within the scope of the manuscript, but they are not merely presentation problems.

major comments (4)
  1. [Section 3.2 / Algorithm 1 / Eq. (2)] The acceptance probability alpha in Eq. (2) is not computable as written because the proposal probabilities q(w'|w) for the prefix-resampling proposal in Section 3.2 are never defined. Section 3.2 specifies only how to sample a candidate (draw i from p^w_POS, run GCD on prefix w_1:i), but the numerical probability q(w'|w) = sum_i p^w_POS(i) * P_GCD(w' | w_1:i) requires the exact GCD completion probability P_GCD(·|prefix), which is not given. Algorithm 1's Line 4 invokes alpha(w_{i-1}, w), and Appendix E's proof of Theorem 3 treats q(y|x) as a known positive quantity and invokes the textbook MH stationarity result, but without an expression for q the detailed-balance step cannot be checked. If the implementation approximates or omits the proposal-ratio term, the chain's stationary distribution is not P^G and the theorem's conclusion is unsupported. Please provide an explicit computable expression for q, or state and prove a variant of the guarantee that holds for the actual implemented acceptance test.
  2. [Appendix E, Theorem 3 proof, irreducibility step] The irreducibility proof requires q(y|x) > 0 for all x, y in S, and derives this from p^x_POS(0) * P_GCD(y) > 0. This requires P_GCD(y) > 0 for every valid y. However, the experiments use top-p = 0.9 (Appendix B), so GCD assigns zero probability to any completion that would require a token outside the nucleus at some step; many valid sequences therefore have P_GCD(y) = 0. Thus Theorem 3 is proved for exact GCD without truncation, but the empirical configuration does not satisfy its hypotheses. Please either state and prove the theorem for the actual top-p sampler, or adjust the experimental protocol to match the assumptions of the theorem.
  3. [Section 3.2, Priority proposal] The Priority proposal defines p^w_POS(i) proportional to the token-level perplexity PP(P(·|w_1:i)), but this is incomplete for i = 0, since the perplexity of the empty prefix is not defined. Because Theorem 3 explicitly requires p^w_POS(0) > 0 for all w, the Priority proposal as written may fail the hypothesis of the theorem unless the empty-prefix case is specified. Please define p^w_POS(0) explicitly, or state the restricted guarantee that applies to Priority.
  4. [Section 4.1 / Appendix F] The empirical evaluation approximates the target P^G using 'all the samples acquired during the runs of MCMC and ASAp' (Appendix F). This makes the KL-divergence estimates partly circular: the same samples that define the reference distribution also determine the estimated distance from each method to that reference. Since the 'efficient' and 'monotonically converging' claims are supported by these comparisons, please also report KL values computed against an independently estimated reference (for example, a held-out set of samples) or discuss the direction and magnitude of the bias this introduces.
minor comments (6)
  1. [Abstract] The phrase 'generatediverseandvalid' in the abstract is missing spaces and should read 'generate diverse and valid'.
  2. [Section 1] The Introduction says 'an significant challenge'; it should be 'a significant challenge'.
  3. [Section 4.1] The notation for the proposal families is inconsistent: Section 3.2 defines Uniform, Priority, and Restart, while Section 4.1 and Tables 2 and 3 use 'Prefix' in some places and 'Priority' in others. Please align the names throughout.
  4. [Section 4 / Appendix B] The description of the decoding hyperparameters says 'top-k to 0 to allow sampling from the full token vocabulary' while top-p = 0.9 is also set; please clarify whether top-p truncation is applied before or after the top-k setting, since both are mentioned.
  5. [Appendix E] The proofs use 'total variance distance' where the standard term is 'total variation distance', and Theorem 3 says 'k approaches to infinite' instead of 'k approaches infinity'.
  6. [Section 6] The Limitations paragraph contains the typo 'sqllite' for 'SQLite'.

Circularity Check

1 steps flagged · score 2.0 of 10

One mild self-referential issue in the empirical KL reference distribution; the central MCMC convergence proof is not circular because it relies on standard, externally established Metropolis-Hastings theory.

  1. other [Appendix F, 'Benchmarks by Park et al. [34]'; see also Section 4.1 'Measures']
    "we follow Park et al. [34] to use an approximate measure instead, which is the KL divergence to the LM distribution P on the finite set of all observed samples. ... GCD, MCMC(k) and ASAp(k) are all approximated using 100 samples, and P G is approximated using all the samples acquired during the runs of MCMC and ASAp."

    The empirical target used for the reported KL divergences is not a fixed, independently specified P^G; it is an empirical reference built from outputs produced by the evaluated methods themselves. Appendix F states that P^G is approximated using all samples acquired during runs of MCMC and ASAp, while Section 4.1 defines the finite-set KL target as the LM distribution over all observed samples. Consequently, each method's KL score is measured against a reference that contains its own samples and the samples of its competitors, so the comparison is partially self-referential. The reported 'convergence to P^G' is therefore partly convergence to a pooled estimate of the methods' own output distributions rather than to the true grammar-conditioned LM distribution.

full rationale

The paper's central theoretical contribution is not circular. Algorithm 1 is a Metropolis-Hastings sampler whose acceptance ratio cancels the intractable normalization constant of P^G, and Theorem 3 is proved by instantiating standard MCMC theory (Hastings 1970; Durrett Theorem 5.6.6). The detailed-balance/stationarity step is a textbook result about MH samplers in general, not a restatement of the paper's own claims. The paper does reuse definitions, benchmarks, baselines, and the Transformers-GAD implementation from the authors' earlier ASAp work [34], but those citations are not load-bearing for the new sampler's validity: the GCD-distortion formula in Section 2.1 is explicitly derived rather than merely imported, and the MCMC convergence proof does not depend on [34]. The main substantive concerns are correctness gaps, not circularity: the proposal probabilities q(w'|w) are never defined algorithmically, so the acceptance ratio in Eq. (2) cannot be computed as written, and the proof of irreducibility assumes P_GCD(y)>0 for every valid y in a setting where top-p=0.9 sampling may assign zero probability to some valid completions. These are unverified assumptions about the implementation, not reductions of the result to its inputs. On the empirical side, the KL-divergence measure is contaminated because P^G is approximated from the pooled samples of the very methods being compared, which is a mild self-referential evaluation rather than a forced conclusion. Overall, the derivation chain is substantially independent of prior work, so the circularity score is low.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim draws its correctness from standard MCMC theory and from assumptions about the grammar-constrained decoder, not from fitted parameters or new postulated entities. No free parameters are fitted; the priority proposal's perplexity weighting is derived from the model rather than tuned to data.

assumptions (3)
  • standard math Metropolis-Hastings with exact proposal probabilities has P^G as stationary distribution.
    Used to derive the acceptance criterion in Equation (2); the paper relies on textbook MH convergence, citing Hastings [18] and Durrett [12].
  • domain assumption GCD can generate every valid sequence with positive probability and its continuation probabilities are computable.
    Theorem 3 requires q(y|x)>0 for all valid x,y via the empty-prefix proposal; with top-p=0.9 (Appendix B) some low-probability continuations may have zero probability, so the assumption may not hold in the empirical setup.
  • domain assumption Any prefix of a valid sequence is a valid prefix and GCD can extend it to a full valid sequence.
    Used in Algorithm 1's Propose function; required for every proposal to satisfy the grammar.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective." pith.science (2026). https://pith.science/paper/JTGW2HBA

@misc{pith2026250605754,
  author       = {Pith},
  title        = {Pith review of: Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JTGW2HBA}},
  note         = {Machine review of arXiv:2506.05754}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2506.05754 by the authors.

Figure 1
Figure 1. (a) Prompt to generate seed test cases for fuzzing the SQLite engine. (b) Simplified version [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. (a) KL divergence for varying number of steps for a representative [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. SQL benchmark: (a) KL divergence for MCMC with varying number of steps. (b) Branch [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (14 more)
Figure 4
Figure 4. Figure 4: Condensed parse tree for the example SQLite [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: (a) Prompt given to a LM to generate seed test cases for fuzzing the XML parser. (b) [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: (a) KL divergence (mean ± 95 % CI, hundred runs per approach) for MCMC with varying number of steps for the XML Benchmark. (b) Branch coverage over time (mean ± 95 % CI, five trials per method) for the XML Benchmark. (a) Priority (b) Restart (c) Uniform [PITH_FULL_IMA…
Figure 7
Figure 7. Figure 7: XML: branch-coverage ablation. Line style encodes the number of steps k ∈ {2, 5, 10} (dotted, dashed, solid). D.9 Function and Line Coverage To corroborate the branch-coverage trends reported in the main text, we additionally measure both • Line coverage: the fraction …
Figure 8
Figure 8. Figure 8: SQL: branch-coverage ablation. Line style encodes the number of steps k ∈ {2, 5, 10} (dotted, dashed, solid). (a) Priority (b) Restart (c) Uniform [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: XML: function-coverage. Line style encodes the number of steps k∈ {2, 5, 10} (dotted, dashed, solid). Proof. The output of Alg. 1 can only be generated from either Line 1 or Line 11, both of which call the GCD procedure. Since GCD samples only from the constrained lang…
Figure 10
Figure 10. Figure 10: SQL: function-coverage. Line style encodes the number of steps k∈ {2, 5, 10} (dotted, dashed, solid). (a) Priority (b) Restart (c) Uniform [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]
Figure 11
Figure 11. Figure 11: XML: line-coverage. Line style encodes the number of steps k ∈ {2, 5, 10} (dotted, dashed, solid). PGCD(y), which is non-zero. On the other hand, q(y | x) is no smaller than this probability, hence it must also be non-zero. Then, by the definition of the transition pr…
Figure 12
Figure 12. Figure 12: SQL: line-coverage. Line style encodes the number of steps k∈ {2, 5, 10} (dotted, dashed, solid) [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: KL-Divergence for GCD vs MCMC(k = 10) by subset [PITH_FULL_IMAGE:figures/full_fig_p021_13.png]
Figure 14
Figure 14. Figure 14: KL-Divergence for ASAp(k = 10) vs MCMC(k = 10) by subset 21 [PITH_FULL_IMAGE:figures/full_fig_p021_14.png]
Figure 15
Figure 15. Figure 15: KL-Divergence for ASAp(k) and MCMC(k) in SLIA subset 22 [PITH_FULL_IMAGE:figures/full_fig_p022_15.png]
Figure 16
Figure 16. Figure 16: KL-Divergence for ASAp(k) and MCMC(k) in BV4 subset [PITH_FULL_IMAGE:figures/full_fig_p023_16.png]
Figure 17
Figure 17. Figure 17: KL-Divergence for ASAp(k) and MCMC(k) in CP subset 23 [PITH_FULL_IMAGE:figures/full_fig_p023_17.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Continuous Diffusion Models Can Obey Formal Syntax

    cs.LG 2026-02 conditional novelty 7.0 of 10

    Training-free gradient guidance, based on the exact regex-acceptance probability under the decoder's unigram distribution, lets continuous diffusion language models satisfy regular-expression constraints.

  2. Length Value Model: Scalable Value Pretraining for Token-Level Length Modeling

    cs.CL 2026-04 unverdicted novelty 6.0 of 10

    LenVM trains a token-level value head to predict discounted remaining length, enabling length control and efficiency steering on LLMs and VLMs.

  3. The Format Tax

    cs.CL 2026-04 conditional novelty 6.0 of 10

    Structured-output instructions alone impose a large accuracy tax on open-weight LLMs; decoupling freeform reasoning from formatting recovers most of it, while recent closed models largely avoid the tax.

  4. Constrained Adaptive Rejection Sampling

    cs.AI 2025-10 conditional novelty 6.0 of 10

    CARS is an exact constrained-sampling algorithm that prunes all constraint-violating token continuations encountered along sampled paths, monotonically raising acceptance rate while preserving the target conditional d...

Reference graph

Works this paper leans on

59 extracted references · 51 canonical work pages · cited by 4 Pith papers

  1. [1]

    llvm-cov — emit coverage information

    2025. llvm-cov — emit coverage information. https://llvm.org/docs/CommandGuide/ llvm-cov.html

    work page 2025

  2. [2]

    Lahiri, and Sriram K

    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. InAdvances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023

    work page 2023

  3. [3]

    Rajeev Alur, Dana Fisman, Saswat Padhi, Rishabh Singh, and Abhishek Udupa. 2019. Sygus- comp 2018: Results and analysis

    work page 2019

  4. [4]

    Afra Amini, Li Du, and Ryan Cotterell. 2024. Structured voronoi sampling.Advances in Neural Information Processing Systems, 36

    work page 2024

  5. [5]

    Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016. Guided open vocabulary image captioning with constrained beam search.arXiv preprint arXiv:1612.00576

    work page Pith review arXiv 2016

  6. [6]

    Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. 2023. Prompting is programming: A query language for large language models.Proc. ACM Program. Lang., 7(PLDI)

    work page 2023

  7. [7]

    Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coverage-based greybox fuzzing as markov chain. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, page 1032–1043, New York, NY , USA. Association for Computing Machinery

    work page 2016

  8. [8]

    Marcel Böhme, László Szekeres, and Jonathan Metzman. 2022. On the reliability of coverage- based fuzzer benchmarking. InProceedings of the 44th International Conference on Software Engineering, ICSE ’22, page 1621–1633, New York, NY , USA. Association for Computing Machinery

    work page 2022

Show all 59 references
  1. [9]

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

    2021 arXiv

  2. [10]

    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

    2022 arXiv

  3. [11]

    2001.Sequential Monte Carlo Methods in Practice

    Arnaud Doucet, Nando de Freitas, and Neil Gordon. 2001.Sequential Monte Carlo Methods in Practice. Springer. 10

    2001

  4. [12]

    2010.Probability: Theory and Examples, 4th Edition

    Rick Durrett. 2010.Probability: Theory and Examples, 4th Edition. Cambridge University Press

    2010

  5. [13]

    Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. 2020. AFL++ : Combining incremental steps of fuzzing research. In14th USENIX Workshop on Offensive Technologies (WOOT 20). USENIX Association

    2020

  6. [14]

    Saibo Geng, Hudson Cooper, Michał 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

    2025

  7. [15]

    Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023. Grammar-constrained decoding for structured NLP tasks without finetuning. InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, Singapore. Association for Computational Linguistics

    2023

  8. [16]

    W3C XML Core Working Group. 2009. Namespaces in xml 1.0 (third edition). https: //www.w3.org/TR/xml-names/

    2009

  9. [17]

    W3C XML Working Group. 2008. Extensible markup language (xml) 1.0 (fifth edition). https://www.w3.org/TR/xml/

    2008

  10. [18]

    W. K. Hastings. 1970. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97–109

    1970

  11. [19]

    Adrian Herrera, Hendra Gunadi, Shane Magrath, Michael Norrish, Mathias Payer, and Antony L. Hosking. 2021. Seed selection for successful fuzzing. InProceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2021, page 230–243, New York,...

    2021

  12. [20]

    Richard Hipp

    D. Richard Hipp. 2000. Sqlite

    2000

  13. [21]

    Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2018. Grammarinator: a grammar-based open source fuzzer. InProceedings 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. Associati...

    2018

  14. [22]

    Chris Hokamp and Qun Liu. 2017. Lexically constrained decoding for sequence generation using grid beam search.arXiv preprint arXiv:1704.07138

    2017 arXiv

  15. [23]

    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. InProceedings of the 2019 Conference of the North American Chapter of the Associati...

    2019

  16. [24]

    Linghan Huang, Peizhou Zhao, Huaming Chen, and Lei Ma. 2024. Large language models based fuzzing techniques: A survey

    2024

  17. [25]

    George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018. Evaluating fuzz testing. InProceedings 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

    2018

  18. [26]

    Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. 2022. Gradient-based constrained sampling from language models. InProceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2251–2277

    2022

  19. [27]

    Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash Mansinghka

    Alexander K. Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash Mansinghka. 2023. Sequential monte carlo steering of large language models using probabilistic programs. InICML 2023 Workshop: Sampling and Optimization in Discrete Space

    2023

  20. [28]

    Xiang Li, John Thickstun, Ishaan Gulrajani, Percy S Liang, and Tatsunori B Hashimoto. 2022. Diffusion-lm improves controllable text generation.Advances in Neural Information Processing Systems, 35:4328–4343. 11

    2022

  21. [29]

    Yixuan Li, Julian Parsert, and Elizabeth Polgreen. 2024. Guiding enumerative program synthesis with large language models. InInternational Conference on Computer Aided Verification, pages 280–301. Springer

    2024

  22. [30]

    Smith, and Yejin Choi

    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. NeuroLogic a*esque decoding: Constrained text generation with lookahead heuristics. In Proceedings of th...

    2022

  23. [31]

    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 constraints. InProceedings of the 2021 Conference of the North American Chapter of the Association fo...

    2021

  24. [32]

    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

    2024 arXiv

  25. [33]

    Daniel Melcer, Sujan Gonugondla, Pramuditha Perera, Haifeng Qian, Wen-Hao Chiang, Yanjun Wang, Nihal Jain, Pranav Garg, Xiaofei Ma, and Anoop Deoras. 2024. Approximately aligned decoding

    2024

  26. [34]

    Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D’Antoni

  27. [35]

    Kanghee Park, Timothy Zhou, and Loris D’Antoni. 2025. Flexible and efficient grammar- constrained decoding

    2025

  28. [36]

    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 arXiv:2201.11227

    2022 arXiv

  29. [37]

    Matt Post and David Vilar. 2018. Fast lexically constrained decoding with dynamic beam allocation for neural machine translation.arXiv preprint arXiv:1804.06609

    2018 arXiv

  30. [38]

    Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. 2022. Cold decoding: Energy- based constrained text generation with langevin dynamics. InAdvances in Neural Information Processing Systems

    2022

  31. [39]

    Hopkins, and Michael Carbin

    Alex Renda, Aspen K. Hopkins, and Michael Carbin. 2023. Can LLMs generate random numbers? evaluating LLM sampling in controlled domains. InICML 2023 Workshop: Sampling and Optimization in Discrete Space

    2023

  32. [40]

    Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021. PICARD: Parsing incremen- tally for constrained auto-regressive decoding from language models. InProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 9895–9901, Online and Pu...

    2021

  33. [41]

    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 arXiv:2104.08768

    2021 arXiv

  34. [42]

    Elias Stengel-Eskin, Kyle Rawlins, and Benjamin Van Durme. 2023. Zero and few-shot semantic parsing with ambiguous inputs.arXiv preprint arXiv:2306.00824

    2023 arXiv

  35. [43]

    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. InProceedings of the 2024 Conference on Empirical Methods in Natural Language P...

    2024

  36. [44]

    Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. 2024. Improving llm code generation with grammar augmentation.arXiv preprint arXiv:2403.01632

    2024 arXiv

  37. [45]

    Daniel Veillard. 1998. libxml2: The XML c parser and toolkit of gnome

    1998

  38. [46]

    Saurous, and Yoon Kim

    Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. 2023. Grammar prompting for domain-specific language generation with large language models

    2023

  39. [47]

    Brandon T Willard and Rémi Louf. 2023. Efficient guided generation for large language models. arXiv e-prints, pages arXiv–2307

    2023

  40. [48]

    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. InNeural Information Processing Systems (NeurIPS)

    2023

  41. [49]

    Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. 2023. Tractable control for autoregressive language generation. InInternational Conference on Machine Learning, pages 40932–40945. PMLR

    2023

  42. [50]

    Honghua Zhang, Po-Nien Kung, Masahiro Yoshida, Guy Van den Broeck, and Nanyun Peng

  43. [51]

    set test

    zxteloiv. 2025. complex-qa [source code]. https://github.com/zxteloiv/complex-qa. Accessed: 2025-05-13. 13 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 38...

    2025

  44. [52]

    InAdvances in Neural Information Processing Systems, volume 37, pages 115563–115587

    Adaptable logical control for large language models. InAdvances in Neural Information Processing Systems, volume 37, pages 115563–115587. Curran Associates, Inc

  45. [54]

    Number of steps matters, but saturates.Coverage grows monotonically with k; however, k=5already captures≥95 % of the gain realised byk=10on both benchmarks

  46. [55]

    2Grammarinator is omitted for clarity; its curve lies far below all others and does not alter the ordering

    All MCMC variants beat GCD.Even the weakest setting ( k=2) surpasses GCD’s final coverage by 4-5%, demonstrating that MCMC proposals yield coverage gains over heuristic constrained decoding — even with very few sampling steps. 2Grammarinator is omitted for clarity; its curve l...

  47. [56]

    This set is countable since the set of all sequences is countable

    (Countable states) In our Markov chain, the state set comprises all sequences with non-zero probability in P G, denoted as S. This set is countable since the set of all sequences is countable

  48. [57]

    We start by showing that q(y|x)>0 for all x, y∈S

    (Irreducibility) Let q be the proposal distribution of our Markov chain. We start by showing that q(y|x)>0 for all x, y∈S . Consider the event where the empty prefix is selected in Line 10, and y is selected by GCD in Line 11. The probability of this event is px POS (0)· 18 (a...

  49. [58]

    (Aperiodicity) By the above analysis,p(x|x)>0for any statex, implying aperiodicity

  50. [59]

    Hence, all prerequisites of Thm

    (Stationary distribution) The Metropolis-Hastings algorithm ensures that the target distribu- tionP G is a stationary distribution of the constructed Markov chain. Hence, all prerequisites of Thm. 2 are satisfied, then Eq. 3 follows directly from it. 3The greater-than part of ...

  51. [2024]

    InThe Thirty-eighth Annual Conference on Neural Informa- tion Processing Systems

    Grammar-aligned decoding. InThe Thirty-eighth Annual Conference on Neural Informa- tion Processing Systems

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.