Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo
Authors: 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
Timothy J. O'Donnell
Venue: ICLR 2025 Oral (2025)
Keywords: Sequential Monte Carlo
Language Models
Semantic parsing
Bayesian inference
Probabilistic programming
SMC
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We introduce a sequential Monte Carlo framework for controlling LMs at inference time via both syntactic and semantic constraints.

Abstract: A wide range of LM applications require generating text that conforms to syntactic or semantic constraints. Imposing such constraints can be naturally framed as _probabilistic conditioning_, but exact generation from the resulting distribution—which can differ substantially from the LM’s base distribution—is generally intractable. In this work,
we develop an architecture for controlled LM generation based on sequential Monte Carlo (SMC). Our SMC framework allows us to flexibly incorporate domain- and problem-specific constraints at inference time, and efficiently reallocate computational resources in light of new information during the course of generation. By comparing to a number of alternatives and ablations on four challenging domains---Python code generation for data science, text-to-SQL, goal inference, and molecule synthesis—we demonstrate that, with little overhead, our approach allows small open-source language models to outperform models over 8$\times$ larger, as well as closed-source, fine-tuned ones. 
In support of the probabilistic perspective, we show that these performance improvements are driven by better approximation to the posterior distribution. 
[Our system](https://github.com/probcomp/genlm-control) builds on the framework of Lew et al. (2023) and integrates with its _language model probabilistic programming language_, giving users a simple, programmable way to apply SMC to a broad variety of controlled generation problems.

Published as a conference paper at ICLR 2025
SYNTACTIC AND SEMANTIC CONTROL OF LARGE LANGUAGE MODELS VIA SEQUENTIAL MONTE CARLO
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!1,7 Tim Vieira Timothy O'Donnell
MITT 2ETH Zürich McGiil *Canada CIFAR Al Chair 'Mila JJohn Hopkins Yale IIST genlmêmi t. edu
ABSTRACT
A wide range of LM applications require generating text that conforms syntactic or semantic constraints. Imposing such constraints can be naturally framed as probabilistic conditioning, but exact generation from the resulting wistributionwwhich can differ substantially from the LM's base distribution-is generally intractable. In this work, we develop an architecture for controlled LM generation based sequential Monte Carlo (SMC). Our SMC framework allows us to flexibly incorporate domain- and problem-speciff constraints at inference time, and efficiently reallocate computational resources in light of new information during the course of generation. By comparing to a number of alternatives and ablations on four challenging domains-Python code generation for data science, text-to-SLL, goal inference, and molecule synthesis- demonstrate that, with little overhead, our approach allows small open-source language models to outper- form models over x larger, as well as closed-source fine-tuned ones. In support show that these performance improvements
of the probabilistic perspective, are driven by better approximation to the posterior distribution. Our system builds (2023) and integrates with its language model
on the framework of Lew probabilistic programming language, giving users simple, programmable way to apply SMC to a broad variety of controlled generation problems.
O httpp::///hh wwtp:///robccom/////mmmmooooommo
INTRODUCTION
The goal of controlled generation from language models (LMs) is to produce text guided by of syntactic or semantic constraints. One prominent example is semantic parsing, or code generation, which involves producing text in programming (or other formal) language. typically from a natural language prompt. We may wish to use diverse signals to guide code generation, for example:
Checking (partial) code statically (type-checking, linting, partial evaluation);
Running (partial) code on test case and checking if it raises an eтror or returns the wrong answer; Simulating environments (e.g., in robotics or chemistry) and assigning score the resulting state; Rolling out possible completions of partial code and computing their max, min, or average score; Asking another language model to critique the code generated so far.
Such signals vary along several important dimensions: some are cheap to compute (linting), others are more costly (simulations); some can be evaluated incrementally with each sampled token (language model critique), others provide sparser guidance (running code); some enforce binary hard constraints (type-checking), others yield soft continuous scores (scoring).
One way to represent such signals uniformly is potential functions d(x) assigning non-negative scores to sequences of tokens æ. Given a set & of such potentials, we will write (x)) = II o (x). We frame the problem of controlled generation probabilistically: We wish to sample from the global
co-first authorship, "co-senior authorship.

---

Published as a conference paper at ICLR 2025
product of experts distribution complete sequences æ::
1 g(æ) Z p()))(())
where p is a distribution over complete token sequences defined by an autoregressive LM, and Z is a normalizing constant. The distribution g can be interpreted as posterior with as the prior and + as the likelihood function. Importantly, even when both sampling from p and evaluating ((x) are efficient, sampling exactly from y is generally intractable (Rosenfeld et al., 2001).
Two popular sampling-base approaches that avoid the intractability of g are locally constrained decoding and sample reranking (see Appendix F for detailed review of related work, including other approaches such as MCMC). Locally constrained decoding uses per-token logit biasing or masking to incorporate signals at each step, for example to ensure that the complete sequence will fall in a specified regular or context-free free language (e.g.. Shin et al., 2021; Scholak et al., 2021; Poesia et al., 2022; Willard & Louf, 2023; Moskal et al., 2024; Ugare et al., 2024). mauplle-errnn-bbseee approaches first generate complete sequences and then rerank or reweight these based on the specified set of signals. Examples of this approach include best-of-n reweighting with a reward model (Nakano et al., 2021; Krishna et al., 2022; Zhou et al., 2023; Gui et al., 2024; Mudgal et al., 2024; Ichihara et al., 2025) or filtering samples with verifier (Olausson et al., 2023: Chen et al., 2024; Lightmnn ct al., 2024; Xin et al., 2024). Each approach suffers from significant weaknesses. Locally constrained decoding requires the guiding signals O to be cheap enough to evaluate very frequently (for instance on the full token vocabulary at every step of generation). Moreover, it often introduces greedy approximations that badly distort the distribution (relative to g. Lew et al., 2023; Park et al., 2025). Sample-rerank does not impose constraints & until full sequences have been sampled and, thus, cannot make use of information available incrementally during generation; this can significantly increase the number of samples needed to find high probability, messtraint-satisfyiin sequences.
Sequential Monte Carlo (SMC) has been proposed as an effective approach to approximate inference for such intractable distributions in other difficult language modeling problems, such infilling, prompt engineering, and prompt intersection as well as for more traditional tasks in natural language processing (Börschinger & Johnson, 201 I; Dubbin & Blunsom, 2012; Buys & Blunsom, 2015; Lin & Eisner, 2018 8; Lew et al., 2023; Zhao et al., 2024). In this paper, we use SMC to tackle a number of challenging semantic parsing problems, guiding generation with incremental static and dynamic analyses. When these signals are efficient enough to be used incrementally, our approach incorporates them into proposal distributions, gaining the benefits of locally constrained decoding; more costly potentials as often used in sample-rerank approaches- are incorporated as twist functions that reweight partial sequences to favor promising paths (Naesseth et al., 2019). Our approach emphasizes programmable potentials and proposals that can easily be specialized for specific tasks problems (e.g., by integrating libraries for molecular structure or robotic planning, see 13.1). We contrast this with the use of learned proposals or twist functions (Lawson et al., 2022: Zhao et al., 2024), which requires costly, problem- specific fine-tuning.
Our paper makes the following contributions:
SMC for constrained semantic parsing. We develop an architecture specializing SMC for code generation under diverse syntactic and semantic constraints ($2). Unlike many previous frameworks for constrained decoding, our algorithm can integrate constraints that cannot be incrementally evaluated over the entire token vocabulary, as well as constraints that can only be evaluated at irregular intervals during generation. The framework emphasizes programmable inference (Mansinghka al., 2018), allowing users to deploy proposals and potentials that exploit the structure of application domains. Our system also fully integrates with the language model probabilistic programming framework of Lew al. (2023).
Empirical evaluation of performance in diverse domains. We apply our approach- and six alternatives to four challenging problem domains: Python code generation for data science, text-to-SQIe SQL, goal inference, and molecule synthesis ($3.1). We find that, with little overhead, our approach significantly improves performance across domains, allowing small open-source language models to outperform models over 8x larger, as well as closed-source fine-tuned models. We additionally find that, with 5-10x fewer particles, SMC outperforms approaches that only incorporate constraints at the end of generation ($3.2).
Empiriaal evaluation of algorithm components. We run ablation experiments and find that improved performance can be attributed to three algorithmic components: weight correction, which
2

---

Published as a conference paper at ICLR 2025
Excsing partoliss
Grammar constrined generalion Enfercea guamral
Accuracy by method across domains
neech.-teee teenert
0.4
C.A.
ustleck
0.2
Weight conection
Expensive polantial
Accuracy 00 tock
galle grocdinoss
Incorporatis couily signuls
0.0
torth, ine
X
ValuEErox
0.0
0.0
Moleculer synthesis
Text-to- SQL
077
1-0
torth, torth.stacc tensoot
0.6
0.6
0.5
tordhvoalach tomeraal
0.4
Updated particles
Recampling
prommiig partides
0.0
LM MT expensive posendal
tarch, tenorrs
tarch.nttaciitesssrr:
(curulative)
retampiing
0.22
0.10 Lorch Soneari
Figure 1: Controlled generation from LMs via sequential Monte Carlo. Left: We use sequential Monte Carlo to sample from high-quality approximations to posteriors over LM outputs. Partial sequences are repeatedly extended via commarr-constainge generation. We then apply weight corrections mitigate the greediness of locally constrained decoding, as well expensive potentials encode rich information that cannot included logit masks. Finally, resampling focuses computation on promising particles. Right: Accuracy gains from these innovations on challenging data science, text-to-SQL, goal inference, and molecule synthesis benchmarks.
mitigates the greediness of locally constrained decoding; expensive potentials, which incorporate useful signals that several baseline methods cannot integrate; and adaptive resampling, which adaptively refocuses computation on partial sequences that look more promising.
Empirical validation of the probabilistic perspective. We derive estimators of the KL divergence from each method's 's output distribution to the global product of experts (Appendix D). We find that the perforerf methods (i) have outputs that are closer in KL divergence the global product of experts within each problem instance, and (ii) assign probabilities that are more correlated with downstream performance across problem instances ($3.3).
2 MONTE CARLO INFERENCE FOR CONSTRAINED SEMANTIC PARSING
Notation. We æ to refer to sequence of tokens, with x; being the 7th token in the sequence. Let Vet def Ø ... Tt-1. Let e denote the empty sequence. We use juxtaposition (e.g., æ y) to denote sequence concatenation. Let A be a vocabulary of tokens, and let A² denote the set of all finite sequences of tokens in AA. We refer to the set A as the set of partial sequences. We use EOS & A to denote special token marking the end of sequences not included in A. We define Agos def (EOS) A*
and the of complete sequences EOS
def
{ EOS
Language models. A language model is probability distribution over complete sequences (i.e., En Eos p(x)= = 1). We assume that p provides a conditional distribution p(æ' x)) over its next token x' E Aeos given any sequence E A"; the probability of any complete sequence factors
[=]
p(x)
II
p( x<))
t=1
We find it convenient to extend the definition of p(x) from Eq. (2) to partial sequences x E A": note, however, that p(z) is prefix probability,' so p not probability distribution over partial sequences. With this extended definition, we have p(æ'
z') provided p(x) > 0.
x:) p(m)
Potential functions. We consider set & of domain- task-specific potential functions that encode relevant constraints or preferences as nonnegative scores. Each potential function Φ E & has the type o: (A* U EOS) -> R meaning that it assigns non-negative real d(x) when evaluated on some sequence freely using any structure in the sequence so far regardless of whether æ
I..., p(x)) is the prohability that complete sequence a' ~ has the partial sequence a as prefix.
3

---

Published as a conference paper at ICLR 2025
is partial complete sequence. For technical reasons, assume that all potentials satisfy ((x) =0 = p x y) = 0, for all æ and y such that x y E A EOS.
Target distribution. We formalize the goal of controlled generation as sampling sequences æ A'EOS
A EOS from the target distribution given by the global product of experts between p and क.?
1 ((ar)((a))
g(x) Z
where
7. = Σ p(y)
yEAA-EOS
For intuition, if ((x) {0,1} for all in A EOS, the global product of experts can be understood as the rejection sampling distribution that arises by repeatedly generating æ ~ p. and rejecting if ( O. The normalizing constant Z is the rate which samples are accepted. Thus, the expected runtime of rejection sampling is 1/2 per accepted sample, making it expensive if Z is small. Our work aims to accurately approximate the global product of experts with much less computation.
Locally constrained decoding. A popular approach² to enforcing constraints at inference-time is to apply them before sampling each token. In this approach, at each time step t, the current sequence aezt is extended with new token St Co(. (F<))) (until 2i. EOS) where*
L x+ def p(at xx ((mcet)
(m
((xee()) p(x' x<() ((x<1)
where (x(x<1) def Σ EBEs
(4)
L (XE
[- (x Teet) for either the probability of x E A'EOS or the prefix probability of E A Note that in the former case, la is a distribution over complete sequences. We call it a local product of experts model because normalization is performed locally (at each step of the sequence), rather than globally (once per complete sequence).
We write (o def
Despite its popularity, locally constrained decoding has two important shortcomings. First, for most practical potential functions, the local and global product of experts do not define the same distribution (Lew et al., 2023; Park al., 2025). In particular, while the global product of experts is defined with respect to complete sequences, the local product typically only has access to the string generated so far and single token of lookahead poor solutions. In principle, this problem can be mitigated by the choice of intermediate potentials (2(x) for æ AA"), which implement more aggressive forms of lookahead. In particular, locally constrained decoding is an exact sampler when ((x) "x(x), the expected future potential of a, (>(xr) def Eg (xx') x: is prefix of a²). Unfortunately, much like Z, computing th exactly is typically intractable. Although we may seek to approximate it, for example, by learning (Zhao al., 2024) or adaptive methods (Park et al., 2025), here we instead focus on variants of locally constrained decoding which marginalize over the immediate next token as in Eq. (4); see Footnote 3. Our experiments ($3) compare our method to this dominant form of local decoding from the literature, using efficient tests for whether the addition of a single candidate token can satisfy the constraint.
can lead to myopic sampling down paths that lead to globally
The second, related problem with locally constrained decoding is that the local product of experts can only be sampled efficiently when it is possible to cheaply evaluate the potentials á & on all possible one-token continuations Te:t 2n of the current sequence. For some constraints (e.g.. checking membership or prefixhood in the language of a regular expression or context-free grammar), algorithms exist for efficient parallel evaluation across tens of thousands of possible continuations. However, for many of the constraints of interest in the present paper (including several listed in Table 1, for example, error-checking with test cases) this is not feasible. In what follows, we will assume that the set of potentials & can be partitioned into expensive potentials Dexp. which are too costly to use as part of locally constrained decoding, and efficient potentials Paff, which can be used in sampling from the local product of experts.
Importance sampling. The shortcomings of local decoding can be addressed with importance sampling, a Monte Carlo technique for approximating intractable distributions. We describe a
Note that care has be taken ensure that the sum which defines the normalizing constant in Eq. (3) converges. One sufficient (but not necessary) condition ensuring this if 9 bounded above by a constant.
E.gg. Shin et al. (2021): Scholak et al. (2021): ) Poesia et al. (2022); Willard & Louf (2023); Ugare et al. (2024).
Here our assumption that ((x) 0
((x g) 0 ensures that whenever ((x<)) 0, all extensions will
be O well, making it safe in such cases to define (( ((कस(1) O.
" is also known in the SMC literature as the optimal twist function (e.g., Zhao al., 2024).
4

---

Published as a conference paper at ICLR 2025
particular application of the technique specialized our setting. Here, we use the local product of experts model Pq... (abbreviated feft) with respect to just Penl as a proposal distribution, from which we sample multiple complete particles xx)), x(N) tnd. Lett. For each particle x!1)) we define its importance weight (+) as
(9)
w der p(x()) )(z())
II
Len (z(())
-Pexp (x)
(5)
fett (x
The numerator is an unnormalized variant of the target distribution g. which we write as g hereafter, while the denominator left is the proposal distribution that was used to draw the sequence. These
weighted particles define the following posterior approximation: g(z) def ΣN w 2/==<==="")
Σ/=1 mnd)
which under mild conditions converges to as N grows. Our importance weights simplify as shown in Eq. (5), and we note how they correct for the two problems we identified with Left. The first
factor, I [ Lef (z) corrects for the greediness of left, penalizing partieles where all possible continuations 2, E Agos score poorly in context. The second factor, Peep (z()). incorporates the expensive potentials that could not be used in lefl. These importance weights can be computed efficiently: the first factor is already computed as a byproduct of sampling from Loft. and the second factor is computed by running each of the expensive efficient potentials once on each x:(
Sequential Monte Carlo. While importance sampling addresses several shortcomings of local decoding, it too suffers from a major weakness: weight corrections and expensive potentials are not integrated until after complete sequence has been generated from the proposal. This is despite the fact that critical information about whether a sequence can satisfy constraint is often available much earlier and can be used to avoid large amounts of unnecessary computation. Sequential Monte Carlo (SMC; c.g., Chopin & Papaspiliopoulos, 2020), is a natural generalization of importance sampling that constructs importance- weighted samples from a sequence of unnormalized target distributions (g to arrive at the final unnormalized target In our case, we consider intermediate targets 9. defined the sequence of spaces (At) def (xc A" |a| t) U {ar EOS |ar| S t). that is, partial sequences of length equal to t and complete sequences of length less than or equal to t.
The targets defined
ge ( for ((1
(6)
Note that ğ and 9i are unnormalized distributions over different spaces: A EOS and A(t)) respectively. Whereas g only considers potentials on complete sequences, T. depends also on the behavior of the potentials <xxp when applied partial sequences. But as t -> oo, there is less and less mass on partial sequences, and Y/ approaches ÿ no matter how the partial potentials are defined.
The particles for Ht drawn prefixes from lat (stopping length if EOS has not been reached), again requiring an importance weighting correction. The importance weight at time / can be re- expressed as the importance weight from time times correction factor for step t:
Fe (w (2)
w/
(7a)
lall (xr x..)
(1)
-x( (1)
9e (x: ce B/y
(7b)
(5) loft (Te x (
==1 Gr (x
<t'
(3) (5)
ge x xt
(7c)
9--1 x 21)
Lest (2t
x(
(1)
(1)
Lon exp
(7d)
The sequential Monte Carlo algorithm generates approximations to each intermediate target ğr. using resampling steps to reallocate computation from less more promising partial sequences. We begin with a collection of N weighted particles (x((), (0) (s, 1), where & is the empty
'However, the number of particles required to obtain good approximation of the target distribution is exponential in the KI. divergence between target g and proposal for (Chatterjee & Diaconis, 2018).
5

---

Published as a conference paper at ICLR 2025
sequence of tokens. Then, starting at t 1, repeat the following three steps until all particles EOS-terminated (i.e., (+) E A EOS for all i):
1. Extend. For each incomplete particle x(1,, sample zt ~eat( (-1 (x) and update x0() t (+)
I
2. Reweight. For each extended particle xe1),, update the weight (+) +- w(() Leff (xc
(6) Peupp
Deopl (20
Resample. Sample ancestor indices (1),, ,,.,,
(N)) Lid. Categorical
(n W W.m.
where W
W
Ei w Then, reassign all particles (x(*), w()) (ax(aft))
W. N
for all simultaneously."
The extension step extends each incomplete particle with a next token proposed by the local product of experts bett- The reweighting step computes the updated importance weight, incorporating new factor for the new token. The resampling step exploits any early signal available in the updated weights at time to abandon some less promising incomplete particles (which are unlikely to be chosen as ancestors) and focus more future computation on more promising particles (which are likely to be chosen as ancestors multiple times and then will be extended in multiple ways at time f + 1). This reallocation of computation often leads to dramatic improvements in inference quality-without -withuut it, SMC would reduce to the previous importance sampling method.
Further extensions. We further extend our SMC implementation in two ways. First, potentials in Pott may still be modestly expensive to evaluate on the entire vocabulary. In these cases, we develop cheap stochastic approximations to the local product of distributions and use these as proposals during the Extend step. The incremental weight computation must also be corrected to account for these approximations; we derive stochastic unbiased estimators of the incremental weights that can be soundly used within SMC (see Appendix C). Second, the intermediate targets do not need to advance token-by-token; in some domains, it beneficial to consider more semantically meaningful increments. For example, in one of our experiments, the intermediate target pt is defined over the space of all partial Python programs containing t or fewer lines of code (rather than tokens); the Extend step then samples different number of tokens per partiele, waiting in each partial sequence until a new full line has been generated. Such strategies can lead to better particle alignment (Lundén et al., 2018), making resampling more effective.
3 EXPERIMENTS
We compare seven approaches to constrained generation:
Language model (Base LM). This method simply samples from the base language model p (see $3.1 for details on the language models used).
Language model with grammar constraint (Locally constrained decoding). This is the approach used by much prior work (Footnote 3). In each of our domains, we formulate a context-free grammar (CFG) encoding notion of syntactic
follmfreeedees appropriate for the domain (see $3.1). We let heff encode the binary function that determines whether its input is prefix of some valid sequence in the grammar's 's language. This baseline directly samples from beft, i.e. it uses per-token logit masking to greedily enforce the CFG constraint.
3. Language model with grammar constraint and weight correction (Grammar-only IS). This method generates particles from Eatt, then computes importance weights correct toward the global product of p and a These weights mitigate some of the greediness of local- praul-prouucoff-expert sampling, but do not yet integrate any potentials beyond D.fr.
4. Language model with grammar constraini, weight correction, and resampling (Grammar-only SMC). This method is a straightforward application of Lew al. (2023) locally constrained decoding and is similar to Park et al. (2025), which also attempts to correct for the greediness of locally constrained decoding. As in the previous method, targets the global product of p and Pcitt but uses resampling to reallocate computation to promising particles.
Language model with grammar constraint and expensive potential (Sample- Rerank). Sample- Rerank is a common family of approaches for incorporating an external signal into an LM's generations post-hoc, for instance by choosing the best-of-n particles via a reward model (Nakano et al., 2021; Krishna et al., 2022; Zhou et al., 2023; Gui et al., 2024; Mudgal et al., 2024; Ichihara
In practice, we only resample if the effective sample size N def (CN ()
EN (w0 is under a threshold (c.g.. 3)

---

Published as a conference paper at ICLR 2025
Table I: Summary of tasks and potential functions. Examples are truncated for brevity. Full prompts include additional information.
Potentials
Examples
Task
4Pff
Peepp
Prompt
Output
Write the STRIPS goal condition for the planning problem
(:goal (and
STRIPS parser
Goal Inference
Plan simulation
described below [..]] The
(arm-empty) (on-table b1) [..]]
STRIPS initial condition is: [..]
Here is a sample dataframe: [..]] I'd like add inverses of each existing column to the dataframe
Error-checking with test cases
result: df. join(df apply(1ambda x: 1/x) [...]
Python Data Science
[..]]
Alius and table-column checking Incremental molecule
Here databuse schema: [...] For each stadium, how many concerts are there?
SELECT name, (OUNT(*) FROM concert T1 I...]
SQL. parser
Text-to-SQL
Given the following list of molecules in SMILES formar, write an additional molecule [...]
SMILES
Molecular Synthesis
CC1=CC2(00=))((=0) [...]
parser
validation
et al., 2025) or filtering via verifier (Olausson al., 2023; Chen et al., 2024; Lightman et al., 2024; Xin et al., 2024). In each domain, we formulate an additional potential 4 eexp that encodes task-specific signals of sequence quality (see $3.1). This baseline generates grammar-constraind sequences from the local product of experts, then reweights each sequence a by Pexp (xx) Language model with grammar constraint, weight correction, and expensive potential (Full IS). This is the full importance sampling method described in $2, with &b Detf U 4 Lexp- Unlike in the previous method, the importance weights here include correction terms that mitigate the greediness of local sampling, targeting the global product g. We include this method primarily as an ablation of our next method (SMC). modified not to include incremental resampling.
7. Language model with grammar constraint, weight correction, expensive potential, and resampling (Full SMC). This method includes all of the algorithmic contributions our approach. is the full sequential Monte Carlo algorithm, with Φ- ooff Pexp- It targets the same global posterior g as the previous method but uses resampling to reallocate computation to promising particles.
We report results using N 10 particles; Appendix A.2 and Fig. for downstream accuracy results for a varying number of particles. We ran experiments on GCP instances with 1 A A100 GPU and 12 vCPUs (our CFG parser is implemented for CPU and is parallelized across particles), with the exception of the Data Science domain, for which we used 4 H100 GPUs and 64 vCPUs.
3.1 DOMAINS
We study the performance of our proposed sampling methods on four challenging semantic parsing domains, summarized in Table I; see Appendix E for further details.
Goal inference (Planetarium). Task: Formally specify an agent's goal in the STRIPS subset of the PDDL planning language, based on a natural-language description of the goal and PDDL code detailing the agent's ' initial conditions and plan for achieving it. Data: Blocksworld tasks with up to 10 objects from the Planetarium benchmark (Zuo et al., 2024). Metric: Accuracy with respect to ground-truth PDDL goal. Base LM: Llama 3.1 8B. Grammar: STRIPS syntax for goals within Planetarium Blocksworld's domain definition. Expensive potential: Run a simulation with ground-truth plan and check whether the resulting state conforms to the predicted (partial) goal. Python for data science (DS-1000). Task: Generate Python code that standard data science libraries (NumPy, PyTorch, Pandas, etc.) to solve a task specified in natural language and via (executable) test cases. Data: DS 10-1000 benchmark (Lai al., 2023). Metric: Accuracy of the generated program with respect to the provided test cases. Base LM: Llama 3 70B. Grammar: We use a trivial potential a (a) 1, as we find that the unconstrained LM reliably generates grammatical Python (that may nonetheless induce runtime errors). Expensive potential: Given a partial program x, Lexp truncates æ to the longest prefix of the sequence that consists only valid Python statements (discarding any incomplete material at the end), and executes the resulting (partial) program on the provided test case, checking for runtime errors.
Text-to-SQL (Spider). Task: Generate SQL queries from natural language question and database schema. Data: Spider development split (Yu et al., 2018). Metric: Execution accuracy (whether the generated SQI. query, when against test database, produces the same results
7

---

Published as a conference paper at ICLR 2025
Table Comparison method performance across domains with bootstrapped 95% confidence intervals. For
brevity, grammor constraint and weight correction are abbreviated as grammar and correction, respectively.
Score
Mothod
Goal inference
Molecular synthesis
Data science
Texi-to-QLL
Base I.
D.83 (0.05, 0.08)
0.132 (0.12, 0.15)
0.213 (0.19, 0.24)
01531 (0.51, 0.55)
grummur constratmi (Lucally cunstrained Decoding)
0.189
0.559
grammor weight correction Graamssn-onl 1S)
(0 06. 0.11)
0.228 (0:21, 0.25)
0.597 (0.57. 0.62)
of grammor, poleniial (Sample Berank)
0.289 (0.21. 0.34)
0.392 (0.36, 0:12)
0.581 (0.56. 0.60)
correction, and resumpliny (Gramman--nll SMC)
0:401 (0.34, 0.46)
0.205 (0. 18.18.00 0.23)
0.59 (0.57. 0.62)
grammar, potential, correction IS)
(0.31. 0.39)
uf grammas potraaioll correction, and resaupling (Pull SMC)
0.419 (0.37, 0.48)
0.577 (0.56, 0.59)
0.407 (0.36, 0.45) 0.620 (0.60, 0.64)
Dap Sciece
Gool slanence
MORCEN Synbwedd
64
0.5
0d
Store
Scare
0.1
02
Model
Method
Mathod
Bas LM
PLIS
PLE
Partices
Figure 2: Left: Performance on the Data Science task (DS-1000) for different models and methods. Codex-002 performance reported in Lai et al. (2023). Right: Performance across all tasks for Full IS and Full SMC with 5, 10. and 50 particles. Error bars: bootstrapped 95% confidence intervals.
the ground-truth SQL query). Base LM: Llama 3.1 8B-Instruct. Grammar: SQL context-free grammars released by Roy et al. (2024), which enforce valid SQL syntax. Expensive potential: Check whether column names in the generated (partial) query actually belong the queried tables, modulo aliasing. (The grammar ensures only that the column names exist in some table.)
Molecular synthesis (GDB-17). Task: Generate drug-like molecules in SMILES for- mat (Weininger. 1988). Data: Few-shot prompts constructed by repeatedly choosing 20 random examples from the GDB-17 dataset (Ruddigkeit et al., 2012). Metric: Quantitative Estimate of Drug-likeness (QED; Bickerton et al., 2012), standard molecular fitness function. Base LM: Llama 3.1 8B. Grammar: SMILES syntax for molecules. Expensive potential: A SMILES prefix validator implemented in the Python partialsmiles library (O' (O'Boyle, 2024).
3.2 EVALUATION OF DOWNSTREAM PERFORMANCE
We begin by investigating whether our approach leads to significant performance gains. Table 2 reports posterior-weigheed accuracy for our approach and ablations its components: grammar constraints, weight corrections, expensive potentials, and resampling. We first summarize the observed effects of each component in our approach:
Grammar constraints. line with previous literature (e-g., Shin et al., 2021; Scholak et al., 2021; Poesia et al., 2022; Wang et al., 2024), we find that the addition of a grammar constraint via Pat improves downstream accuracy relative to the base LM across all domains which it is used, even without the use of weight corrections.
Expensive potentials. Furthermore, we observe that integrating expensive potentials Pexp improves accuracy in models. Even without any weight corrections, the improvement in the goal inference, data science, and molecular synthesis domains is large; in the text-to-SQI. domain, it is smaller but statistically significant (paired permutation test, p 0.01). This suggests that making use of information that cannot be efficiently encoded in logit masks can greatly improve performance.
Weight corrections. Although the use of del and Pexp alone leads to significant gains in downstream accuracy, these gains can be amplified with the addition of weight corrections. In cases without the expensive potential, weight corrections provide significant albeit relatively small gains in accuracy across three domains; in goal inference, it does not significantly affect performance. the presence of the expensive potential, adding weight corrections improves accuracy for text-to-SQL. and has no effect on goal inference and molecular synthesis. Overall, these results indicate that debiasing samples from local product of experts to correctly target the global product of experts often significantly improves downstream accuracy and never harms it. That said, the accuracy gains attributable to weight corrections are modest compared to other components of the algorithm, which suggests that the bias from locally constrained decoding may be less severe in these semantic parsing domains than has been observed in other domains (e.g., constrained generation of natural language, Lew al., 2023).
8

---

Published as a conference paper at ICLR 2025
Figure 3: Estimated between algorithm and the global product experts for a representative problem instance in each domain, Values closer to 0 indicate that the algorithm is hetter at approximating g. Significant differences are indicated with ** for p < 0.01 and for p < 0.001 (t-test). Algorithms use N 10 partieles.
Data scrence
Goal Inference
Motec.le werculer syclitesis
Tec--to-0
Estimated log Z KLLd.
0.5
1.5
6+4
potential
Method
IN with condtrwn porernial and conecctin
UK with grammar constrantt poternial weight correction and ressmpling
Resampling. We observe that the addition resampling steps improves downstream accuracy in all domains except text-to-SQL, for which they neither significantly improve nor hurt performance. These results motivate adaptively focusing computation on promising partial sequences.
Other Evaluations. Next, we study the effects of varying the base language model, the number of particles used by different methods, and the computational cost of our approach: Tables 4, 6 and 8 in the appendix report the results these experiments. We summarize key findings:
Our approach allows smaller LMS to outperform larger ones: In 3 out of 4 domains (Data Sci- ence, Molecular Synthesis, Goal Inference), Full SMC allows small language models to outperform models over 8 times larger (see Tables 2 and 4). These gains persist on larger models: Fig. 2 shows how our method allows Llama 3.1 70b to outperform Codex-002 which has 175b parameters and is fine-tuned for coding tasks.
Our approach makes better use of resources than approaches that apply constraints only at the end of generation: In out of domains (Data Science, Molecular Synthesis, Text-to-SQI), Full SMC performs as well as or better than Full IS while using one-tenth of the particles (see Fig. 2 and Table 6); in the remaining domain (Goal Inference). Full SMC outperforms IS with one fifth (10 vs 50) or one half (5 vs 10) of the particles. This is in line with the arguments drawn in $2 for the poor scaling importance sampling and the benefits of resampling.
Our approach incurs minimal computational overhead: At every token, SMC approach incurs two computational overheads relative to a simple locally constrained decoding baseline: resampling and computing expensive potentials. Though the cost of resampling is negligible, computing expensive potentials presents a more significant cost that varies across domains: Table shows that cost rarely rises above ~30ms per token. In general, this cost is reduced by two factors: (i) expensive potentials often need to run expensive computations only at larger, semantically meaningful units (for instance, the end of SQL clause Python statement) rather than at every token-therefore significantly lessening the average cost per token, (ii) expensive potentials operations are often performed on CPU rather than GPU, and therefore cost fewer dollars per hour.
3.3 VALIDATION OF THE PROBABILISTIC PERSPECTIVE
The best-perforning methods from the previous section were designed to approximate the global product of experts distribution. In this section, we investigate how closely each of these methods approximates this global distribution and whether the downstream performance results from the previous section are driven by the quality of the probabilistic inference. particular, find:
Within each problem instance, the best-performing methods have outputs that are closer in KL divergence to the global product of experts. We consider the distribution over sequences Lag (ar) defined by each algorithm (see Appendix D for details and derivations). For each dag. estimate tractable correlate of the KL between the algorithm and the global product of experts: log 7 KL g). We refer to this quantity as the approximation quality. Since the term log is algorithms to determine which ones have lower KL divergence relative to the global product of experts. However, because log Z is instance-specific, these comparisons can only be made at the instance level. Accordingly, for each domain, select the instance with the median unique accuracy
we can directly compare the estimated approximation quality across

---

Published as a conference paper at ICLR 2025
Table 3: Pearson correlation between relative particle weights and accuracy scores for all weighted methods.
Greater correlation indicates that relative weights are more strongly associated with downstream performance.
Correlation between relative weight and score
Method
Goal inference
Molecular synthesis
Data science
Text-to-SQL
LM with grammur construints and weight cor-
0.138 (0.10, 0.18)
0.218 (0.16, 0.28)
0.217 (0. 18, 0.26)
0.810 (0.79, 0.83)
rection (Grammar-Only IS)
LM with grammar constrainis, potential, and
0.677 (0.64, 0.71)
0.570 (0.53, 0.61)
0.289 (0.25, 0.33)
0.796 (0.78, 0.81)
weight correction (Full IS)
LM with grammar constraints, potential, weight correction, and resampling (Full SMC)
0.793 (0.76, 0.82)
0.826 (0.81,
0.370 (0.31. 0.42) 0.810 (0.79, 0.83)
Figure 4: Distributional properties of compounds generated by different methods. Middle: Distribution of drug-likeness as measured by QED score (Bickerton al., 2012). Right: Means for other properties of interest such as diversity and novo similarity (details Appendix E.2).
Model
10-
LM
68-
grammar constraint
co-
weight correction
expensive potential
CA-
resampling
12-
Target dietribution
60
00
02
0.6
0 Guartaabve Caterate of Drugekeensos (2E.0)
as a representative example. Fig. 3 visualizes estimated approximation quality on these examples across all methods, which include 4 Pexp- Estimates were computed across 100 runs of each algorithm.
In all domains, sampling from the local product of experts without weight correction leads to significantly lower approximation quality relative to the methods that approximate the global product. The addition of resampling steps also significantly improves approximation quality in the data science and goal inference domains, but does not significantly change quality in the molecular synthesis and text-to-SQL domains. These trends in approximation quality are consistent with those observed in our evaluation of downstream accuracy: for example, we find that text-to-SQL. the domain in which weight corrections led to the most significant improvement in approximations of the global posterior, as well as the domain in which weight corrections most improve downstream performance. This suggests that the probabilistic formulation of the problem leads to practical gains in performance. Furthermore, these benefits can extend beyond our main performance metric; for instance, resampling during molecular generation yields simultaneous improvements along number of additional dimensions interest, including de-novo similarity and diversity (Fig. 4).
Across problem instances, the best-performing methods assign probabilities that are more correlated with downstream performance In each of our experiments, we group output particles by semantic equivalence, and estimate the probability of each equivalence class under the method's approximation to the global product of experts, by summing the normalized weights of the members of each equivalence class (this is similar to the postprocessing performed in Shi et al., 2022). We then measure the correlation between the estimated probability of result and its score the task-specific metric. Table shows sequential Monte Carlo overall exhibits high correlation between (approximate) posterior probabilities and downstream performance, and that the differences in correlation between methods closely track the differences in performance in $3.2. In the goal inference, molecular synthesis, and data science domains, where expensive potentials and resampling greatly increase performance, we find that the same features also result in higher correlation between result probability and performance, whereas in text-to-SQI, where the performance gains are slimmer, we find that all methods correlate and score equally well. Together, these results validate the probabilistic approach, suggesting that the global posterior captures semantically meaningful uncertainty.
CONCLUSION
This paper presents principled formulation of constrained generation sampling from global product of experts distribution. To solve this sampling problem, we introduce a sequential Monte Carlo (SMC) algorithm that can flexibly incorporate different constraints, making incremental use of their signals. In a series of experiments, we show that this approach allows smaller models to outperform larger and fine-tuned models, that the incrementality of SMC makes it order of magnitude more efficient than non- inn-iceeementl approaches, and that downstream performance is linked to the quality of the posterior approximation, providing support for our probabilistic perspective.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like thank Manuel de Prada Corral, Brian DuSell, Joshua B. Tenenbaum, and Tan Zhi Xuan for valuable discussions, suggestions, and coding support that improved this work. The last author gratefully acknowledges the Canada CIFAR Al Chair program for support.
AUTHOR CONTRIBUTIONS
First Authors
João Loula (jloula@mit, edu): research conception and development, writing, experiment devel- opment, software development (prototype)
Benjamin LeBrun (benjamin lebrun@mail. mcgill 11., ca): research conception and development, lead software engineer, experiment development, writing
Li Du (leoduêcs, jhu.
(...eduu).)) edu): experiment development, software development (parser)
Contributors
Ben Lipkin (lipkinbêmi t. edu): software development (grammar interfaces, testing, and integra-
tion), writing
Clemente Pasti (clemente. pasti pasti@inf.... ethz. software and algorithm development (context-
free grammars), writing
Gabriel Grand (grandg@mit edu): software development (testing and integration), analysis and
presentation of molecular synthesis experiments
Tianyu Liu (tianyu.liueinf liu@inf ethz. cch: software development (vLLM integration, testing)
Yahya Emara ayemar ch): software development (testing and integration), writing
Marjorie Freedman (mrf@isi. edu): organization management, writing
Jason Eisner (jasonêcs, jhu.edu): technical advice, writing, project advising and mentorship
Ryan Cotterell (ryan. cotterell@inf wwt...thhcch.. organization management, senior project lead- ership, research conception and development, writing
Senior Authors
Vikash Mansinghka (vkm@mit.. edu): organization management, research conception and develop-
ment, project advising and mentorship
Alexander K. Lew (alexander. lew@yale. senior project leadership, research conception
and development, project narrative development, writing, software development (prototype)
Tim Vieira (tim. f. vieira@gmail com): senior project leadership. full-stack software contributor, research conception and development, project narrative development, writing, software system design and implementation
Timothy J. O'Donnell (timothy odonnel aelonnell@mcee l@megi 11. ca): overall team leadership and direction, organization management, senior project leadership, research conception and development, project advising and mentorship. project narrative development, writing
REFERENCES
Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho. Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Eric Jang, Rosario Jauregui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Kuang-Huei Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kanishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Mengyuan Yan, and Andy Zeng. Do as can, not as say: Grounding language robotic affordances. arXiv preprint arXiv:2204.01691, 2022. URL https:
orgg/bb///////////// 2tt.//222.....1.... (Cited p. 33)
Afra Amini, Tim Vieira, Elliott Ash, and Ryan Cotterell. Variational best-of-N alignment. In Proceedings of International Conference Learning Representations, 2025. URL https://
(Cited on p. 33)
Christophe Andrieu and Gareth O. Roberts. The pseudo-marginal approach for efficient monte carlo computations. arXiv: Statistics Theory, 2009. URL https: /api. wemanticscholar..oggg
CorpusID: 5661 729. (Cited p. 28)
11

---

Published as a conference paper at ICLR 2025
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini. Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Hatfield-Dodde Ben Mann. Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. Constitutional Al: Harmlessness from Al feedback. arXiv preprint arXiv:22 2022. URL hwtps:: org/ wttp:/bbb//22..000777777 (Cited on p. 32, 33)
Martin Berglund, Willeke Martens, and Brink Van der Merwe. Constructing BPE tokenization DFA. In International Conference on Implementation and Application of Automata. Springer, 2024. URL https: //ll acm. org/ /ooo/bb///////oo/////////a 1007/978-3 3-00-1---1--1101 1 (Cited on p. 33)
G. Richard Bickerton, Gaia V. Paolini, Jérémy Besnard, Sorel Muresan, and Andrew L. Hopkins. Quantifying the chemical beauty of drugs. Nature Chemistry, 4(2), 2012. URL https://www. nature. com/ www.///at/eeeeeeeeeeeooomeeeeeee
1243. (Cited on p. 8, 10,30) 30)
Benjamin Börschinger and Mark Johnson. A partiele filter algorithm for Bayesian wordsegmentation. In Proceedings of the Australasian Language Technology Association Workshop, December 2011 1. 1 org/U1111004/ (Cited on p. 2, 32)
URL https: hcl.atoooooottooo..ooooo
Jan Buys and Phil Blunsom. A Bayesian model for generative transition-hased dependency parsing.
In Proceedings of the International Conference on Dependency Linguistics, 2015. URL https:
//acl //aclanthology org hetgg//152222 2108// (Cited on 2, 32)
Kris Cao and Laura Rimell. You should evaluate your language model on marginal likelihood over tokenisations. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. 2021. URL https: / http::////acaanttoooo.rrrgo org/2021. emnlp-maine 161.pdf. (Cited on p. 33)
Sourav Chatterjee and Persi Diaconis. The sample size required reqqurrer importance sampling. The Annals of Applied Probability, 28(2), 2018. URL https://www. http://wwwww.....oo/////./o... http:/ttae//////5423//// pdff. (Cited on p. 5)
Lingjaa Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei A. Zaharia, and James Y. Zou. Are more LLM calls all you need? towards the scaling properties of compound AI systems. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, De- cember 10- 15, 2024, 2024. URL http: http:://apprr..nneee///// wiwpaperr..nisss.. httpl/pppppppa//lllllllllaapeeee httees/paper/222444 5117ccf34c5fcc7776444f6fcf Aatrrr/-bbbtttttttaeeeeee Abbsttract-Cooeeeeeceee Coseea/eteeetiaaaaaaaaaaaooooeee
html. (Cited on 2, 7)
Emily Cheng, Marco Baroni, and Carmen Amo Alonso. Linearly controlled language generation with performative guarantees. NeurlPS Workshop on Foundation Model Interventions, 2024. URL
https:///ppnrreveew net wdwpp/ddvdxxd01111111 Xtu. (Cited on p. 32, 33)
Nadezhda Chirkova, Germán Kruszewski, Jos Rozen, and Marc Dymetman. Should you marginalize over possible tokenizations? In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2023. URL httpt:tt/tcclsaate http:///acaaaalaaaaeee org 2222 acl-shorts 1. 1.pff. (Cited on p. 33)
Nicolas Chopin and Omiros Papaspiliopoulos. An Introduction to Sequential Monte Carlo, volume 4. Springer, 2020. URL https://link.springer.. worikksr.sin....... /ttp:///oo0001111//7------------ (Cited on p. 5, 24)
Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung. Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. Plug and play language models: A simple approach to controlled text generation. arXiv preprint arXiv:1912.0216. 2019. URL htthttss:/// httttp:://axxxv..orr hwtp:/iwwwwogppp///////oo/////// 64 (Cited on p. 33)
12

---

Published as a conference paper at ICLR 2025
Daniel Deutsch, Shyam Upadhyay, and Dan Roth. A veneral-purpose algorithm for constrained sequential inference. Proceedings of the Conference on Computational Natural Language Learning, 2019. URL httpss:/aclanthollee
org/k199-045// (Cited on p. 32)
Li Du, Afra Amini, Lucas Torroba Hennigen, Xinyan Velocity Yu, Holden Lee, Jason Eisner, and Ryan Cotterell. Principled gradient- MCMC for conditional sampling of text. In Proceedings of the International Conference on Machine Learning. 2024. URL http::///ppoceedingge mlr.
press/ du24a, html. (Cited on p. 33)
Gregory Dubbin and Phil Blunsom. Unsupervised part of speech inference with particle filters. In Proceedings of the NAACL HLT Workshop Induction of Linguistic Structure, Montréal, QC, 2012. URL hattps://allattiiie hwwptthoooooooooooooooooooooooee org/w1 2- 1t1.990pd.. pdf.. (Cited on p. 2, 32)
Jay Earley. Efficcent Context- Pursing Algorithm. PhD thesis, Carnegie Mellon University, 1968. URL https: //dl://lll. acm. http//dii/ddf///////// /10. 1145/362007 362035. (Cited on p. 23)
Richard E Fikes and Nils J Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3-4), 1971. URL https: hopps:/wwww /wwww//wwwww/// rect.. 05. (Cited on 31)
com/sciiecc//rtiiclee http://ccennceerrrrreeee///////p httee//bbb//pp1///443377777777//
Daniel Flam-Shepherd, Kevin Zhu, and Alán Aspuru-Guzik, Language models can learn complex molecular distributions. Nature Communications, 13(1), 2022. URL https: //tps:///www nature. com/ 30839-0 x. pdf. (Cited on p. 30)
artiicles/<4146-022--883
Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West, structured NLP tasks without finetuning. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. 2023. URL https: /taps:://acllas htt///aaaaaannooogeoeeee org.org/////// 3rg//023..r 2023.emnlp pamain. .df. (Cited on p. 32)
decoding for
Malik Ghallab, Adele Howe, Craig Knoblock, Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, and David Wilkins. PDDL-the planning domain definition language. Technical report, Yale Center for Computational Vision and Control, 1998. URL https: / //www. cs. cmu. edu/~mmv/plane http:/mm/pplamaiinggrrddang////l PDDdiippppPDDP.ppf (Cited on 31)
Joshua Goodman. Semiring parsing. Computational Linguistics, 25(4), 1999. URL https://
aclanthology.org wtt/ (Cited on 23)
Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Lever- aging pre-trained large language models to construct and utilize world models for model-based task planning. In Advances in Neural Information Processing Sys- tems, 2023. URL https: neurips. cc/ wwtppprrr.pppppppppppp//p paper_files// silees/paper www.ss/aaper//223///5/ /tt///2222feee http///cbbbffeeffffddda4/1111111 Ponfaapeeerrrereeeeeeeeeea pdf. (Cited on p. 31)
Lin Gui, Cristina Garbacea, and Victor Veitch. Bonbon alignment for large language models and the sweetness of best-of-n sampling. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15, 2024. 2024. URL http: /ttpt:::://pprpraa/ /wwpr//apppppp//a///e//eeeeeeeee nips. cc/ httc//pppr_fffiieeeeeeeeee fiwes//ppprr////// 0e224/hash//555211220 65666662212222211222222222266660 aaboreeeeeee-bbbatrttt---ooooeee 2, 6)
html. (Cited on p.
Malte Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26, 2006. URL https:://wwwwwttt
10457. (Cited on p. 31)
Brian Hie, Salvatore Candido, Zeming Lin, Ori Kabeli, Roshan Rao, Nikita Smetanin, Tom Sercu, and Alexander Rives. A high-level programming language for generative protein design. bioRxiv, 2022. URL https://www biorxiv. wwtorxiv.org//ooo orgg//ontee//1.... 1101 /2022. 12. 521526v1. fullllllfff (Cited on 33)
John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computa- tion. Addison-Wesley, 1979. ISBN 0-201-02988-X. (Cited on p. 23)
Daniel G. Horvitz and Donovan J. Thompson. A generalization of sampling without replacement
from a finite universe. Journal of the American Statistical Association, 47(260), 1952. URL https://ww.. jstor. org/ org/stable/pdff httaabeepddf/2287/44444 pdf.. (Cited on p. 25)
13

---

Published as a conference paper at ICLR 2025
R. Howey, D. Long, and M. Fox. VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL. In IEEE International Conference on Tools with Artificial Intelligence, 2004. URL
wrg. orgg/ocument/////ooooooooo/o/c// /2///33742999 (Cited p. 31)
Wenlong Huang, Fei Xia, Dhruv Shah, Danny Driess, Andy Zeng, Yao Lu, Pete Florence, Igor Mordatch, Sergey Levine, Karol Hausman, and Brian Ichter. Grounded decoding: Guiding text generation with grounded models for embodied agents. In Advances in Neural Information Processing Systems, volume 36, 2024, URL https: http://poceedinn...eeeeeee neurips cttpsscccpppprreeeeeeeeeeeepeepe http/ppper__iiiee files/ caper/2023/filll http://///.ee/33ccccc22222222222 p. 32, 33)
(et.de66611111111 eeteeeff1119fffeeeee Pappre/ee----pee---rreeeeeeeeee pdf. (Cited on
Yuki Ichihara, Yuu Jinnai, Tetsuro Morimura, Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Eiji Uchibe. Evaluation of best-of-n sampling strategies for language model alignment. Transactions on Machine Learning Research, 2025. ISSN 1835-8856 URL http:: htpps:///pen wttprreewiiiiwteeerfrreeeeee net/forum?
id-H4S4ETc8c9. (Cited on p. 2, 6)
Terry Koo, Frederick Liu, and Luheng He. Automata basted constraints for language model decod- ing. In Conference on Language Modeling, 2024. URL https://openrreiiew www.:/eetfoofimececcmmmm BDBdblmyzY. (Cited on p. 32)
Tomasz Korbak, Ethan Perez, and Christopher Buckley. RL with KL penalties is better viewed as Bayesian inference. In Findings of the Association for Computational Linguistics: EMNLP 2022, 2022. URL
thology org/ 2022. findings-emnlp. e 77. (Cited on p. 33)
Kalpesh Krishna, Yapei Chang, John Wieting, and Mohit lyyer. Rankgen: Improving text generation with large ranking models. In Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022. Association for Computational Linguistics, 2022. URL https: //t/:///oo// org/r0////// /00. 18653/v1/ 2022. emnlp- 1aalp--man..11 15. (Cited on p. 2, 6)
Michael Kuchnik, Virginia Smith, and George Amvrosiadis. guage models with RELM. Proceedings of Machine Learning and Systems, URL https://proceeddings mlsys. www.ss.ogg/a.....p.oooo 93c7d9da61 207700000cc2220000e2222efaaaa-00
Validating large lan-
2023.
www.rorgrrrrpppeeeeeeeeeeee _ateappper_eee_e____eeaa_aareeee waarrfffllspppppee Lattes//pper///eee ppppp//223/fflll/ /2023/file/
pdf. (Cited on p. 32, 33)
Sachin Kumar, Eric Malmi, Aliaksei Severyn, and Yulia Tsvetkov. Controlled text generation as continuous optimization with multiple constraints. Advances in Neural Information Processing Systems, 2021. URL https::/pproceedlnggs neurips. cc/ cc/ccc/ppppao pppper_files www.fieepppeeeeee /22.///////////1lle
79ec2a4246feb21 2eteee/22222244444444480222222-0
pdf. (Cited on p. 33)
Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. Gradient- constrained sampling from language models. In Proceedings of the 2022 Conference on Empirical Methods in Nat- ural Language Processing. Association for Computational Linguistics, 2022. URL https:
//aclanthology www.orgg/// wwtpg/2222eenepp.....m main. 144/. (Cited on p. 33)
Yuhang Lai, Chengxi Li. Yiming Wang, Tianyi Zhang, Ruiqi Zhong, Luke Zettlemoyer, Wen-tau Yih, Daniel Fried, Sida Wang, and Tao Yu. DS-1000: A natural and reliable benchmark for data science code generation. In International Conference on Machine Learning. Proceedings of Machine Learning Research, 2023. URL htw.ttts/s/poroeeeinngee http://ppccceediin.lll.ll..eeeee /tt....pees////2//l/13/////1i1 .dd... (Cited on p. 7, 31))
Greg Landrum. RDKit: Open-source cheminformaties software. httpps///github...oorrkkkk/ ctt.httbb.ooooddtt/o/co rdkit, 2024. (Cited on p. 30)
Dieterich Lawson, Allan Raventós, Andrew Warrington, and Scott Linderman. Sixo: Smooth- ing inference with twisted objectives. Advances in Neurul Information Processing Sys- tems, 2022. URL https::/proceeedingg www.:is..euris...comm ccppaprr httc:/aaerffllespppppeeeeeeee palles/paper/2222/// pdf. (Cited on p. 2)
Alexander Lew, Marco Cusumano- Towner, and Vikash Mansinghka. Recursive Monte Carlo and variational inference with auxiliary variables. In Uncertainty in Artificial Intelligence. Proceedings of Machine Learning Research, 2022. URL https: http://///ococeee////e/ mlr, wwtppp/eeee/eeeeeeeeeepe lew22a. pdf. (Cited on p. 24, 27, 28)
14

---

Published as a conference paper at ICLR 2025
Alexander K Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash Mansinghka. Sequential Monte Carlo steering of large language models using probabilistic programs. In ICML Workshop: Sampling and Optimization in Discrete Space, 2023. URL https:tt//pppee http:///ppperrreeeeeeeeeerrrmmma nett:/orrummmddddll2/akkkk (Cited on 1, 2, 4, 6, 8, 21, 32, 33)
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lec, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: /ttttp:://pppprreeee http://///peeeeeeee/e/e/e. net mett/oorumidddwll@ppppe 0pN6E0i.. (Cited on 2, 7)
Chu-Cheng Lin and Jason Eisner. Neural particle smoothing for sampling from conditional sequence models. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2018. URL httt::://aclanthhooogyy org/N18- (Cited on p. 22)
Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. LLM+P: Empowering large language models with optimal planning proficiency. arXiv preprint 11477 2023. URL https: org/pdf / 2304. 11477. (Cited p. 31)
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, al. Neurologic A esque decoding: Constrained text generation with lookahead heuristics. arXiv preprini arXiv: 12.0812....... 2021. URL https:
//aclanthology.
org org 2022. naacl-aaaiaaaa 57. .pdf. (Cited on p. 33)
Daniel Lundén, David Broman, Fredrik Ronquist, and Lawrence M Murray, Automatic alignment of sequential Monte Carlo inference in higher-order probabilistic programs. arXiv preprint 07439. (Cited on p. 6)
arXiv:1812.07439, 2018. URL https::/arxxv..rg/// httpi//w.wrg////////////e/////// /1812
Vikash Mansinghka, Uirich Schaechtle, Shivam Handa, Alexey Radul, Yutian Chen, and Martin Rinard. Probabilistic programming with programmable inference. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2018. URL
https://dl. acm. org/ httgg/ooi/aan http://oo/ab//.111////111111 (145/3192266 3192409. (Cited on p. 2)
Clara Meister, Tim Vieira, and Ryan Cotterell. If beam search is the answer, what was the question? arXiv preprint NKI::20100006500 2020. URL https::/aclantthllooe www.goy..ooooooooooooooooo.ooo.. org/2020. wtt.2.000mmm1.....mmmmmmmm emnlp-man main. 170/. (Cited p. 33)
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: Constrained sentence generation by cetrroollishassting sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, number 01, 2019. URL https://ojs. aaai, bagi htt//nndxx...m http:////////aatti////ee//////// (Cited on p. 33)
Ning Miao, Yuxuan Song, Hao Zhou, and Lei Li. Do you have the right scissors? tailoring pre- trained language models via Monte-Carlo methods. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2020. URL https://aclantholl/ .rg org.2020. acl-main. 314/. (Cited on p. 32)
Michal Moskal, Madan Musuvathi, and Emre Kicıman. AI Controller Interface. https://githhr com/miiroosoft/acch 2024. (Cited p. 2, 32)
Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang, Yanping Huang, Zhifeng Chen, Heng-Tze Cheng. Michael Collins, Trevor Strohman, Jilin Chen, Alex Beutel, and Ahmad Beirami. Controlled decoding from language models. In Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https://openrevieww ( (Cited on p. 6)
Christian A. Naesseth, Fredrik Lindsten, and Thomas B. Schön. Elements of sequential monte carlo. Found. Trends Mach. Learn., 12(3), 2019. doi: 10.1561/2200000077, URL https: //doi.org/1e /201/2200000774 (Cited on p. 2)
15

---

Published as a conference paper at ICLR 2025
Rejichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, Xu Jiang, Karl Cobbe, Tyna Eloundou, Gretchen Krueger, Kevin Button, Matthew Knight, Benjamin Chess, and John Schulman. WebGPT: Browser-assisted question-answwrrigg with human feedback. arXiv preprint urXiv:2/12.093322 2021. URL htwpptttss::sii..ttt// wwwpg//pppp////// 09332. (Cited on p. 2, 6)
Franz. Nowak and Ryan Cotterell. A fast algorithm for computing prefix probabilities. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2023. URL https: //aclanthology..o 2223 acl-short. 6/. (Cited on 23)
Noel O'Boyle. partialsmiles: A validating SMILES parser, with support for incomplete SMILES, 2024. URL https: /ttttps://gttie htwp::/b./htttu..eeeeee htt.uu..oomaaooii//i httm/bbailleachhpaaaaa partiallmiless (Cited on 8, 30)
Theo Olausson, Alex Gu, Ben Lipkin, Cedegao Zhang, Armando Solar-Lezama, Joshua Tenenbaum, and Roger Levy. LINC: A neurosymbolic approach for logical reasoning by combining language models with first-order logie provers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2023. URL https: /aals////caaaaaoaoaaaoee .wr.ooyyooorgooooooooooooooo wrrg/222...2 20t.........mmmmammmmmmmmmmmmm emnlp-main. 31 313/. (Cited on p. 2, 7)
João CA Oliveira, Johanna Frey, Shuo-Qing Zhang, Li-Cheng Xu, Xin Li, Shu-Wen Li, Xin Hong, and Lutz Ackermann. When machine learning meets molecular synthesis. Trends in Chemistry, 4(10), 2022. URL https: http://wwwwwceee cell. ctmm wtt.et//cemmistrr//////oc http:/sssssasaattts/////-////// 7. (Cited on p. 30)
Andreas Opedal, Ran Zmigrod, Tim Vieira, Ryan Cotterell, and Jason Eisner. Efficient semiring- weighted Earley parsing. In Proceedings of the Annual Meeting of the Association for Computa- fional Linguistics, 2023. URL htaps::/aaclathhann 23)
www. long. 204/. (Cited on p.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow in- structions with human feedback. In Advances in Neural Information Processing Sys- tems, 2022. URL
neurips. cc/paper http//ppppeelleeeee wtt.ef//papee///////// /222////222//lle// pdf. (Cited on p. 32, 33)
Kanghee Park. Jiayu Wang. Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D' D'Antoni. Grammar-aligee aligned decoding. In Advances in Neural Information Processing Systems, 2025. URL https::/prooceeddngs..oo happr///eernnrrrprreecerepprrrre httcc/ppperfllee/p/eeeeeeeeeeeee
filles/paper2222////
2bdc2267c3d7d015222 1ataaa/eeaaaaaaaa333aaeeerrreeee
pdf. (Cited on p. 2, 4, 6, 32, 34)
Damian Pascual, Beni Egressy, Clara Meister, Ryan Cotterell, and Roger Wattenhofer. A plug-and- play method for controlled text generation. In Findings of the Association for Computational Linguistics: EMNLP 2021. Association for Computational Linguistics, November 2021. URL nttps://aclantthll.. orgo 2021. mendinggseenlp. 334/. (Cited on 32, 33)
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations, 2022. URL https://openreviiee net/
forum?iid-KttVD97JJ3e (Cited on p. 2, 4, 8, 32, 33)
Isha Puri, Shivehander Sudalairaj, Guangxuan Xu, Kai Xu, and Akash Srivastava. A probabilistic inference approach to inference-time scaling of LLMs using particle-based Monte Carlo methods. arXiv preprint arXiv:2502.0 01618, 2025. URL ht https:://are http:://aaxxvv.og//dd///// prgppdf/2522..c.mmm 01618. (Cited on p. 32)
Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. Cold decoding: Energy- constrained text generation with langevin dynamics. Advances in Neural Information Processing Systems, 2022. URL https:// newrips....p. cc/paper_raieeeeeeeeeeeeeeeeee/e files/ paape//ppp/////e /2////22222feeee 1r22531ff777bkeeefffceeeeeerrrr0
pdf. (Cited p. 33)
16

---

Published as a conference paper at ICLR 2025
Ronald Rosenfeld, Stanley Chen, and Xiaojin Zhu. Whole-sentence exponential language models: A vehicle for hntpps//wwwt www.:sscceeneerret.cccmmm com http:///ccceeeeertta.e////a///// on p. 2)
integration. Computer Speech & Language, 15, 2001. URL
(Cited
Subhro Roy, Samuel Thomson, Tongfei Chen, Richard Shin, Adam Pauls, Jason Eisner, and Benjamin Van Durme. BenchCLAMM: benchmark for evaluating language models on syn- tactic and semantic parsing. In Advances in Neural Information Processing Systems, vol- ume 36, 2024. URL https::/proceedinggggt neur is.. pttp//aappere////////aaaa wailes/paper//eeeeeeeee papprr/223/filee ottpa//e00....eeeooodeoooo0aaarr aatiettts__adddBeehaanrks www.ceannchhheeeeem pdf. (Cited on p.
8, 30)
Lars Ruddigkeit, Ruud Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database GDB-17. Journal of Chemical Information and Modeling. 52(1 I), 2012. URL https://pubs... acs org/ htt//////////////// 1021/ //1///13304110 5d. (Cited on p. 8, 30)
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of the Conference Empirical Methods Natural Language Processing, 2021. URL httpss//aat hatpss///caaathlogg.. orrg/ 2022. emnlp mamnppmmiin..... 39/. (Cited on p. 2, 4, 8,
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida Wang. Natural language to code translation with execution. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2022. URL https: https://aclantthoogg) org/ org//022 2022. 2022.emnlpp...p. emnlp-ma main. 231/. (Cited p. 10)
Richard Shin and Benjamin Van Durme. Few-shot semantic parsing with language models trained on code. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2022. URL htttss://aclattee org/2022. www.naaacllmm aaaacl-mainn.. 396/ (Cited on 32)
Richard Shin, Christopher Lin, Sam Thomson, Charles Chen Jr, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language models yield few-shot semantic parsers. In Proceedings of the Conference Empirical Methods in Natural Language Processing, 2021. URL http::///:/// ptttps://accle /ttp://aaaaaatoog.....ooo wrgg///g//1// eetp/2m22111ppppppemmmmmmmmm emnlp-manll main.
608/. (Cited p. 2, 4, 8, 32)
Tom Silver, Varun Hariprasad, Reece S Shuttleworth, Nishanth Kumar, Tomás Lozano-Pérez and Leslie Pack Kaelbling. PDDL planning with pretrained large language models. In Foundation Models for Decision Making Workshop, 2022. URL https: / ii 1QMMUB42F1, (Cited on 31)
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. In Advances in Neural Information Processing Systems, vol- ume 33, 2020. URL https://proceedding neur surrips.. pttppppppppppppppppppppppppppppp cctppppr_rcceceeeceeeeeeeee saaper__flls__ (F9988dd55999998de11998444888888
pdf. (Cited on p. 32, 33)
Andreas Stolcke. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2), 1995. URL https://aclantthol.gg org/ J95- 295-2002.pdo (Cited on p. 23)
Fahim Tajwar, Anikait Singh, Archit Sharma, Rafael Rafailov, Jeff Schneider, Tengyang Xie, Ste- fano Ermon, Chelsea Finn, and Aviral Kumar. Preference fine-tuning of LLMs should leverage suboptimal, oolpoy data. In International Conference on Machine Learning. 2024. URL https://proceedinggs www.mmlr.rrrrree.. S....prress//2//taaviee htmml. (Cited on p. 33)
html.
Zhi Rui Tam, Cheng-Kuang Wu, Yi-Lin Tsai, Chieh- Yen Lin, Hung-yi Lee, and Yun-Nung Chen. Let speak freely? A study the impact of format restrictions performance of large language models. arXiv preprint 2xXiv:2408.02442 2024. URL https: //s: http//xxvvvv.//// www.pdfff /400 62442.
(Cited on p. 33)
17

---

Published as a conference paper at ICLR 2025
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. SynCode: Improving LLM code generation with grammar augmentation. arXiv preprint arXiv:2403.01632, 2024. URL https:///rxiv org/pdf / 2403. 01622.. (Cited on p. 2. 4, 32)
Tim Vieira, Ben LeBrun, Mario Giulianelli, Juan Luis Gastaldi, Brian DuSell, John Terilla, Timothy O'Donnell, and Ryan Cotterell. From language models tokens to language models characters. arXiv preprint arXiv:2412.037799 2024. URL https://arae /ttpp//f//12..../////////// (Cited on p. 33)
Bailin Wang. Zi Wang, Xuezhi Wang, Yuan Cao, Rif A Saurous, and Yoon Kim. Grammar prompting for domain-specific language generation with large language models. Advances in Neural In- formattion Processing Systems, 2024. URL https:/ https:///ppeees http:///pperreeeeeee/eeee/ www.nnt//orummiddB4tt...oo noteld=BaPOkL142Y, (Cited on p. 8, 30, 32)
David Weininger. SMILES, chemical language and information system. Journal of Chemical Information and Computer Sciences, 28(1), 1988. URL httpps://pbbs acs. .orss.rg// org wwt.o/////gggooo/ooo//oo/g /10 1021/c100057a005 (Cited p. 8, 30)
Brandon Willard and Rémi Louf. Efficient guided generation for large language models. arXiv preprini arXiv:2307.09702, 2023. URL https://arxi:n org/ wttgpdf/2300 09702. (Cited p. 4, 32)
Lionel Wong, Jiayuan Mao, Pratyusha Sharma, Zachary S Siegel, Jiahai Feng. Noa Korneev, Joshua B Tenenbaum, and Jacob Andreas. Learning adaptive planning representations with natural language guidance. arXiv preprint 1rXiv:2312.08500 2023. URL. httph::ts///siiiii org/ wttp /2112.21222222 08566. (Cited on 31)
Yaqi Xie, Chen Yu, Tongyao Zhu, Jinbin Bai, Ze Gong, and Harold Soh. Translating natural language to planning goals with large-languas models. arXiv preprint arXiv:2302.05118, 2023. URL https://arxxw.org//dff
2302.05128. (Cited on p. 31)
Huajian Xin, Daya Guo, Zhihong Shao, Zhizhou Ren, Qihao Zhu, Bo Liu, Chong Ruan, Wenda Li, and Xiaodan Liang. Deepseek-proved Advancing theorem proving in lims through large-scale synthetic data. arXiv preprint arXiv:2405. 14333, 2024. URL https: //trxiaaaiii.//// www.orgg///p.... httgg/dd/2240555/ 14333. (Cited on 2,
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for RLHF under KL-constraint. International Conference on Machine Learning. 2024. URL
https://proceedingg mlr. wtt..press/225/xxong//// html. (Cited on p. 33)
Kevin Yang and Dan Klein. FUDGE: Controlled text generation with future discriminators. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Techmologies, 2021. URL https: /aclsnthhllaanoogy....ooomo org//021. maacl-maine 276/. (Cited p. 32)
Yi Yang and Jacob Fisenstein. A log-linear model for unsupervised text normalization. In Proceedings of the Conference Empirical Methods in Natural Language Processing, 2013. URL https: / //aclanthology.orr hwwplloyy..ggg/000 org/D13 20tg/D111100 1007/. (Cited on 32)
Lance Ying, Katherine M Collins, Megan Wei, Cedegao E Zhang, Tan Zhi-Xuan Adrian Weller, Joshua B Tenenbaum, and Lionel Wong. The neuro-symbolic inverse planning engine (NIPE): Modeling probabilistic social inferences from linguistic inputs. In Workshop on Theory of Mind in Communicating Agents, 2023. URL /tttps://openrevieee wwwp:/orumidd-uuyyzzzeeee on p. 31)
(Cited
Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao. Shanelle Roman, Zilin Zhang, and Dragomir Radev. Spider: A large-scale lamalel dataset for complex and cross- cross-domain semantic parsing and text-to-SQL task. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2018. URL https://aclanttoology otw1:////ooooo///11122110 (Cited p. 7)
18

---

(Cited on Published as a conference paper at ICLR 2025
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autore- gressive language generation. In International Conference on Machine Learning. Proceedings of Machine Learning Research, 2023a. URL https://proceediing mlr
zhang23g. pdf. (Cited on p. 32, 33)
Maosen Zhang, Nan Jiang, Lei Li, and Yexiang Xue. Language generation via combinatorial con- straint satisfaction: A tree search enhanced Monte-Carle approach. In Findings of the Association for Computational Linguistics: EMNLP 2020. Association for Computational Linguistics, 2020.
URL https: haap:s//cclanthoologg... .rg. 2020. findings- penddnngg-eel...... 115/. (Cited on p. 33)
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B Tenenbaum, and Chuang Gan. Planning with large language models for code generation. In The Eleventh International Conference Learning Representations, 2023b. URL
(Cited on 33)
Tianyi Zhang, Li Zhang, Zhaoyi Hou, Ziyu Wang. Yuling Gu, Peter Clark, Chris Callison- Burnh, and Niket Tandon. PROC2PDDL: Open-domain planning representations from texts. In Proceedings of the Workshop on Natural Language Reasoning and Structured Explanations, 2024. URL nttps://aclanthol.e
org/2024 nnrse-1 1.2s- 2/. (Cited p. 31)
Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse. Probabilistic inference in language models via twisted sequential Monte Carlo. In Proceedings of the International Con- ference Machine Learning. 2024. URL https://proceeddingg mlr www.mm.r...s..e.....mmmmmm ptt.pp/es///////// zhao24c. html. (Cited on p. 2, 4, 27, 28, 29, 32)
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, lon Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. SGLang: Efficient execution of structured language model programs. In Advances in Neural Information Processing Systems, 2024. URL https: /atsss////peeeeieee net/forummiddVgkaaaaaa
p. 32)
Rui Zheng, Shihan Dou, Songyang Gao, Yuan Hua, Wei Shen, Binghai Wang. Yan Liu, Senjie Jin, Qin Liu, Yuhao Zhou, Limao Xiong. Lu Chen, Zhiheng Xi, Nuo Xu, Wenbin Lai, Minghao Zhu, Cheng Chang, Zhangyue Yin, Rongxiang Weng, Wensen Cheng, Haoran Huang, Tianxiang Sun, Hang Yan, Tao Gui, Qi Zhang, Xipeng Qiu, and Xuanjing Huang. Secrets of RLHF in large language models part I: PPO. arXiv preprint arXiv:2307.04966 2023. URL hittps://are org/pdf /2307. 04964. (Cited on 33)
Tan Zhi-Xuan, Lance Ying, Vikash Mansinghka, and Joshua B Tenenbaum. Pragmatic instruction following and goal assistance via cooperative seeguage--uideed inverse planning. In Proceedings of the International Conference Autonomous Agents and Multiagent Systems, 2024. URL
https:: /dl. acm. wrg.doi///aoaeoooooooooooooooooo aa/////.///..../ 5555/3635637, 3663074. (Cited on p. 31)
Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models human-level prompt engineers. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https: http::::////ppeeeiiieee http:/iwwwwwwweeeeoo..ee w0-ggw/----9g (Cited on p. 2, 6)
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or K-wise comparisons. In International Conference Machine Learning. Proceedings of Machine Learning Research, 2023. URL https://proceedingg www.nn...........m............em mlr.press/ v202/zhu23f/zhu23F pdf.. (Cited p. 33)
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford. Dario Amodei. Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: 33)
2019. URL wwwphhtps///aate http:s:://xxvvoor//eee httgg/dff/99// /19//////.../ 08593. (Cited on p. 32,
Max Zuo, Francisco Piedrahita Velez, Xiaochen Li, Michael L Littman, and Stephen H Bach. Planetarium: A rigorous benchmark for translating text to struetured planning languages. arXiv preprint arXiv:2407.033211 2024. URL https: //arsvv///vv... http//awwwv...../o///////o http:/orggp////////////o//// /2407 03321. (Cited on p. 7, 31)
19

---

Published as a conference paper at ICLR 2025
Table 4: Downstream accuracy of different methods with a smaller hase language model (Ilama 3.1 8B in Data science and Ilama 3.2 IB in all other domains). Errors are hootstrapped 95% confidence intervals. Instruct model is used for Text-to-SQI..
Method
Score
Goal inference
Molecular sy synthesis
Data science
Text-to-SQI.
LM
0.012 (0.01, 0.02)
0,032 (0.02, 0.04)
0.114 (0.09, 0.14)
0.224 (0.207, 0.241)
grammar construint (Locally constrained Decoding)
0.06)
0.031 (0.02, 0.04)
(0.252, 0.270)
w/ grammur, weight correction (Grumnar-only IS)
0.037 (0.02. 0.06)
0,041 (0.03, 0.05)
0.301 (0.281, 0.323)
w/ grammur, potential (Sample-Reannk)
0.087 (1066, 0.12)
0.119 (0.19, 0.16)
0.299 (0.278, 0.321)
w/ grammar correction, and resampling (Grammar-unly SMC)
0.052 (0.03, 0.08)
0.050 (0.011 0.05)
0.302 (0.281. 0.324)
goummuc polemiaal,
(IS)
(0.05. 0.11)
0.122 (0.09, 0.16)
0.225
(0.326, 0.372)
w/ grammor, potentiol, correction, and resampiiing (SMC)
0.125 (0.09, 0.16)
0.517 (0.48, 0.55)
0.2N5 (1.24, 0.34)
0.348 (0.325, 0.374)
Table 5:
Downstream accuracy of different methods with a larger (relative Table 4) base language models that were used in the main experiments (Llama 3.1 70B in Data science and Llama 3.1 8B all other domains). Errors are bootstrapped 95% confidence intervals. Instruct model used for Text-to-SOL. This table is identical to Table 2 in the main text and is repeated in the appendix for easier comparison.
Method
Score
Goal inference
Molecular synthesis
Data science
Texi-to-SQL
LM
0.06 (0.05, 0.08)
0.132 (0.12, 0.15)
0.213 (0.19, 0.24)
01531 (0.51, 0.55)
constraint (Locally constrained Decoding)
0.086 (0.07. 0.11)
0.189 (0.17. 0.21)
0.559 (0.54, 0.58)
granmor weight correction (Grammar-only 18)
0 (0.06, 0.11)
0.278 (0:21, 0.25)
0.597 (0:57. 0.62)
w/ grommor. polential (Sampl- Betank)
0,289 (0.24. 0.34)
0.392 (0.36, 0.12)
0,581 (0.56. 0.60)
w/ correction, and resumpling (Grammanr-nll SMC)
0.401 (0.34, 0.46)
0.205 (0. 18.18.00 0.23)
01596 (0.57. 0.62)
grammar, potential, and correction (Full IS)
(0.21, 0.31)
0.404 (0.377.
0.346 (0.31. 0.39)
(0.59.
w/ grammur, potential, correction, and resompling (Full SMC)
0.419 (0.37, 0.18)
0.577 (0.56, 0.59)
0.407 (0.36, 0.45)
0.620 (0.60, 0.6-1)
A ADDITIONAL EXPERIMENTS
A.1 SMALLER BASE LMS
This section evaluates downstream accuracy across methods using smaller base language models (relative to Table in the main text, reproduced in Appendix Table for casier comparison). For the Text-to-SQI. Molecular Synthesis, and Goal Inference domains, which in the $3.2 experiments used Ilama 3.1 (8B), we substitute I. Llama 3.2 (1B). In the Data Science domain, which used Ilama 3 (70B) in the $3.2 experiments, we substitute Llama 3.1 (8B). All experiments were run with N 10 particles, and the instruct version of Llama 3.2 (1B) was used in the text-to-SQL domain to remain consistent with the model variants used in the main paper.
We report posterior-wer westerior-wiighted accuracy using the smaller LMs across all methods and domains in Table Although accuracy is significantly lower compared to the larger LMs, we find that weight corrections, expensive potentials, and resampling steps still improve model performance. We also find that, in general, the relative gains in accuracy provided by our method are more pronounced for smaller language models. For easier comparison, Table 5 presents an identical version of Table 2, showing the results for the larger base LMS which were reported in $3.2. With the exception of Text-to-SQL, we observe that our approach with the smaller LM outperforms the locally constrained decoding baseline (LM w/ grammar constraint) using the larger LMM In the Data Science domain, our Full SMC approach with the smaller LM outperforms the larger base LM. These results suggest that our approach can dramatically improve the performance of smaller LMs.
A.2 ACCURACY BY NUMBER OF PARTICLES
This section investigates how performance improvements vary with the number of particles. Table 6 reports downstream accuracy for N = 5, N = 10, and N = 50 particles using the Llama 3.1 (8B) models. Note that we only include methods in which samples are generated from an approximation that is constructed from a set of importance-weighheed particles. For the base I.M and locally constrained decoding baselines, samples are generated through direct ancestral sampling. As result, the number of particles does not influence accuracy in these cases (though additional particles can provide a better estimate of the true model accuracy), so we omit these methods from the analysis.
The main effect we observe is the more efficient use of computational resources by Full SMC compared to methods that do not incorporate incremental information, such as Full IS: the former outperforms the latter with one tenth of the particles in 3 out of 4 domains (Data Science, Molecular Sythesis, Text-to-SQU SQL) and one fifth of the particles in the other domain (Goal Inference, see Fig. in the main text for visualization). We note an additional patterns of results: in the Text-to-SQL. and
20

---

Published as a conference paper at ICLR 2025
Table 6: Accuracy by number particles across methods, Errors are bootstrapped 95% confidence intervals.
Llama 3.1 8B is used as the base LM for all domains. Instruct model is used for Text-to-SQI.
Method
Score
inference
Melecular syuthesis
Data scieace
Text-to-SQL.
Partices
w/ grommar constraint, correction (Grammar only
0.106
growsar consruint, patennal (Sample RReannk)
(0.17,0.00)
n/ grausar contralat, correctlon, resumpling (Cimmmaar only SMC)
0.330 0.37)
0.209
0.24)
(0.57, 0.62) 0.611
w/ gomwar contriia, potemtial cormition (S)
(0.17,0 (.))
(0.37) 0.45)
(0 0.25)
0.63)
LM w/ gronwar consroint, patentaal, correction, and resomping (Full SMC)
0.319 (0.27, 0.37)
0.552 (0.32, 0.58)
0.224 0.27)
0.620 (0.59, 0.64)
Purtices
LM n/ guauar constraltt weight correction (Grammar only 1S)
0.083 (0L06, 0.11)
0.228 (0.21, 0.25)
0.597 (0.57, 0.62)
TM w/ gromsur contmmins potamiial (Sampl-Reend))
0.289 (0.24, 0.34)
0.392 (0. 16,3,, (.42)
0.581 (0.56, (1)
LM w/ grommar consroint, cortection, and resemplig (Grmmmrr-nnly SMC)
0,401 (0.34, 0.46)
0.205 (0.18, 0.23)
0,596 (0.57. 0.62)
LM w/ gramsar construlas potentiat and currection (Pall 1S)
0:257 (0.21, 0.31)
0.204 (0.27, 0.44)
0.223 (0119, 0.27)
0.615 (0.59, (164)
MM w/
comstrinn, potentall, corrctiinn and resompling (Full SMC)
0.419 (0.37,0 48)
0.577 (0 0.
0.265 (0 26, 0.32)
0.620 (0.60, 0.64)
50 Purticlos
LM w/ grammar constuint, correction (Grammar only 1S)
0.069 (0.05. 0.09)
0.211 (0.20, 0.22)
0.603 58, 0.63)
constrlaa, potential (Sample Kerank)
0.436 0.47)
0.40)
0.61)
conoppling (Gimmnsr-eely SMC)
(.65)
0.213 (0 0.23)
growsar consrrint, potential, correction IS)
(0.35, 0.45)
0.40)
0.218 0.25)
(0.60) 0.292 (0.25, 0.33)
w/ grannar constraiat, potential corrcttinn, and resompting (Pull SMU)
0.611 (0.56, 0.66)
0.569 (0.56, 0.58)
(0.64), 0.65)
Table Downstream accuracy comparison with the SMC Steering method from Lew et al. (2023) the text-to- SQL domain. Errors are bootstrapped 95% confidence intervals. Both methods include expensive potentials. Our method is run with 10 particles. SMC Steering is run with 5 particles and beam size of 3. Both methods are with Llama 3.1 8B Instruct.
Method
Score
Full SMC
0.620 (0.60, 0.64) 0.607 (0.58, 0.63)
SMC Steering (Lew al., 2023)
Molecular synthesis domains, increasing the number of particles has a marginal impact on downstream accuracy; however, Goal inference and Data Science, we observe that a greater number of particles can lead to significantly better downstream accuracy (though only when increasing from 5 to 10 particles in the Data Science domain). Given that Goal Inference and Data Science are the two tasks where our expensive potentials are most informative, this pattern of results seems to be reflective of the fact that richer potentials require more computation to fully exploit.
A.3 RESAMPLING WITHOUT REPLACEMENT (LEW AL., 2023)
This section evaluates our approach using the without- rethouu-replacementt resampling method introduced in Lew et al. (2023). Specifically, we use Full SMC algorithm with expensive potential (LM w/ grammar constraint, potential, correction, and resampling). and replace multinomial resampling steps with Lew al. (2023)'s without replacement scheme. For comparison, replacement bascline (SMC Steering) with N 5 particles and beam size of 3, alongside our approach using multinomial resampling with N 10 particles (and an ESS threshold of 0.9). These settings effectively give the SMC Steering method particle count of N = 15, giving it an advantage in the comparison.
the without
Table 7 reports weighted accuracy for these methods in the text-to-SQU domain (we restricted this analysis single domain because of limitations in computational resources). We observe that without-replacement resampling steps slightly hurt performance compared to multinomial resampling.
A.4 COMPUTATIONAL. COST
Though we have shown that practitioners can improve over locally constrained decoding by using our proposed SMC method, in practice, there is additional computational cost stemming from two sources: resampling and computing expensive potentials Pexp- The cost of resampling is negligible, consisting only of simple sum, softmax, and categorical sampling operations at every token. The cost of computing expensive potentials, the other hand, is more significant and varies across domains. Table 8 shows the average per token cost of computing expensive potentials for all of our domains: see that it rarely goes above about 30ms.
21

---

Published as a conference paper at ICLR 2025
Table Average per token cost (in seconds) of computing the expensive potential Pexp each of our domains.
Intervals are hootstrapped confidences estimated by selecting 10 SMC generations at random for cach domain.
Method
Goal Inference
Molecular Synthesis
Data Science
Text-to-SQL
Peep seconds per loken
0.011 (0.007, 0.016) 0.0003 (0.0002, 0.0004) 0.007 (0.0009, 0.023) 0.031 (0.0204, 0.0413)
In general, the computational cost of expensive potentials lessened by two factors: 1) expensive potentials often change not every token, but only at larger, semantically meaningful units (for instance, the end of a SQL clause or a Python statement)- computational cost, 2) expensive potentials are often CPU rather than GPU computations (and the cost of computation is much cheaper).
can therefore significantly lessen
22

---

Published as a conference paper at ICLR 2025
B SHAMMAR-BASED POTENTIALS AND PARSING ALGORITTMSS
We briefly describe how we implemented the parser, i.c., grammar-based potential functions, used in our experiments ($3). These potentials derived from context-free grammar (CFG; see, e.g.. Hopcroft & Ullman, 1979), a rule-based formalism for assigning non-negative values to strings. the setting of our experiments, these {0, ]]-valued judgments of syntactic validity, e-g., whether or not a string is a well-formed SQL query. We note, however, that context-free grammars can be easily generalized the more general case of assigning nonnegative scores to these sequences (Goodman, 1999), not just boolean values, even though we do not leverage this flexibility in our experiments.
CFG defines a boolean-valuce function G: E {0,1), where > is an alphabet of terminal symbols. We call L(g) = supp(g) the language of G, where supp(g) denotes the support of g. Intuitively, we can define grammar-based potential @g as a function that evaluates whether a string is prefix of some string in L(g). Formally we write this Φc(y) 1[3y' E E' y' y E L(g)). for every y E Σ- EOS,, where 3 y' means that y is a prefix of y'. In this work, we assume that the terminal symbols are characters- or, more precisely. bytes that they may be aligned to the token vocabulary A used by the language model p. This approach assumes that each token A is equivalent to sequence of bytes."
We implemented a specialized algorithm" "I to efficiently infer grammar- based potentials og y/) for all terminals 5 Σu (EOS) (simultaneously) given prefix y Σ'. Note that in principle, we could transform the potential function to have the type (A" U A EOS) - {0, 1} by scoring each token y E Asas based on its decoded byte sequence; however, the number of tokens is very large, making too expensive to evaluate the potential for each token's 's byte sequence, in practice. In Appendix C.2, we describe an efficient strategy for (approximately) sampling tokens the locally constrained proposal distribution (Eq. (4)), which comes with some useful probabilistic guarantees.
Thiis may achieved by adding additional rules to the CFG that expand each of its terminal symbols into its constituent byte sequence.
9 An alternative approach is to transform byte-level CFG into token-level CFG; however, this can make the grammar extremely large.
II practice, this may require a lookup table to convert each token identifier to its representation as a byte string.
Our algorithm is based Farley (1968); Stolcke (1995); Nowak & Cotterell (2023); Opedal al. (2023).
23

---

Published as a conference paper at ICLR 2025
C THE SET-BASED PROPOSAL SPEEDUP
This section describes set-based proposal speedup (Appendix C. We instantiate the speedup in Appendix C.2 for the special case of character-level potential functions, such parsing.
C.I FRAMEWORK
The reweight step of our sequential Monte Carlo algorithm requires us to evaluate Leff (xx), and the extend step requires us to sample from the locally constrained distribution latt( x). Both of these operations can be moderately expensive because they require the evaluation of Peft (a: x²) for all tokens x' E AEos- In this section, we describe a general scheme for speeding up both steps by approximately sampling Left x) and approximately evaluating Left (z). If we are careful about how we carry out this approximation, it will not change the intermediate targets Zr (œ), defined Eq. (6), that control the behavior of the sequential Monte Carlo algorithm.
Sequential Monte Carlo with approximate Extend and Reweight steps. The key invariant main- tained by sequential Monte Carlo is that at each step, the distribution of each particle (ar) w (8) is properly weighted for the intermediate target Øt-
Definition 1. Let p(x) Z, p(x) be an unnormalized distribution on a space X, with normalizing
constant Zy. Let q be a probability distribution on weighted pairs (z,, w) E X x R20. We say that q
is properly weighted for p if. for any function f.
IR
W f(x)) = Up E [[x)]
(8)
(sr,0))~q
zupp
The extend and reweight steps of the algorithm, which update a previous particle (x w by sampling (8) Lon (x and returning the new particle
(8) (1) m <t Fi - Lefft (x: <t
Poxp
(x
(1) 2I
exp
are justified by the fact that if (x w(2n) properly weighted for 9t- then the new pair is properly weighted for St- We are looking to improve runtime performance without compromising soundness, so we seek ways of modifying the extend and reweight steps that do not break this invariant.
In particular, suppose that instead of sampling st ~ latt (-
a and computing the exact weight
update w.(" (i) def (2, Le x (4)
instead generate (I,, W) from proposal q that properly weighted for the unnormalized local product of experts E(x) def Lea (ar then compute the alternative weight update
Pexp (mn (4) 2(1)
Peep (x)
(x 2
(5) w 2-1 W. Lexp (xc
(1) def
(0)
21 x)
exp 2
The key observation is that, by the fact that q properly weighted for E, we know that for every possible previous particle (x w
and every function f-
E (w
[
(9)
1xx (8) x) =
E (x,W)r
w
(6)
W.
Loxp 2) [(x
Pexple
(1)
(10)
Lost (1)
E
W
(
Posp 2e 5
(8) (1)
f(a
f(a (
(1))
(11)
z Meate ( (1)
Pexp (1
E
W f(x 2i
(12)
(1)
Therefore, if the overall proper weighting invariant (with respect to the intermediate target ği) holds for the original update, then will also hold for this modified sttend-and-reweighe procedure. For more on SMC with estimated weights, see Chopin & Papaspiliopoulos (2020) and Lew et al. (2022).
family of properly weighted updates based on the Morvitz-Thompson estimator. We now introduce useful family of properly weighted proposals for our setting. It will allow us generate
24

---

Published as a conference paper at ICLR 2025
weighted next-token proposals (x, W) while only evaluating the potentials Peat a (randomly chosen) subset 5 C AEOS- Our procedure inspired by the Horvitz- -rrvitz-Thomson estimator (Horvitz Thompson, 1952).
First, reduce notational clutter, we define the following shorthand: [(x')/L= leat (x' x.).
def Lea (2)), and {(x')
Definition 2. Given a probability distribution over subsets of Acos. we define the set-based proposal speedup by the following generation procedure:
Sample subset S ~ q where q is a probability distribution over subsets of Aeos-
Compute the local weight wxx) def Blx)) of each token x S where (g(x) the inclusion
=(x)
probability (2) Pr [xr E Es S'mq
E S.), ie., the probability that x ends in
any sampled S' ~ q.
3. Compute the set-conditioned distribution q( |) def wxx) w(x) [(EES) where Ws = =Eoes w(z).
Ws
4. Sample q(- S)).
Return (x, Ws)
Then, as described above, we modify the SMC algorithm to use the sampled token x instead of ~ l.tt(: x) in the extend step, and the weight Ws instead of Left (æ) in the reweight step.
We justify this approach by showing that produces properly weighted samples.
Proposition 1. The set-based proposal speedup's 's distribution q (Def. 2) properly weighted proposal for f.
Proof. Let f be an arbitrary real-valued function.
E
[f(#) = > f(x) Σ g( S))(SSWs
(13a)
(n,Wo)~q
Σ f() Σ w(x) 1xr E
(SS
(13b)
Ws
Σ ((x)(()))
1 1(x ()
(13c)
(xx)
5
(T(1) (x)
(13d)
L Σ (())(())
(13e)
= L E [(())
(13f)
and
C.2 CHARACTER- BAASED PROPOSAL
Our character- based proposal distribution is an instance of the framework of the previous section. In particular, samples sets of tokens S by sampling sequence of characters. We provide the pseudocode for this algorithm in Alg. 1, and define two key data structures used by this proposal:
Definition 3. Our trie data structure T is a labeled, tree-structured graph that is defined as follows:
Let Acos be the LM's vocabulary of tokens where we represent each token as its strings of characters ending with a designated end-of-token marker EOT. 13 Let E denote the set of characters (or bytes).
Let P be the prefix closure of the set Acos: P that p is prefix of x.
del {p E Σ* p 1 F. E AEOS} where p 3 x denotes
We require to he such that every token has a positive inclusion probability (T( >> 0 for all x Agos-
Note that EDS is handled specially is string af characters.
25

---

Published as a conference paper at ICLR 2025
Let = EN be a labeled graph with node and labeled edges = {p 2 pa p. (pa) E p]
Definition 4, Let mass a mapping N - [0, 11. defined as follows.
mass(x') = p(z' x). for E AAeos
(14a)
mass (p) = Σ mass(pa):
for p PMPEP)AS
(14b)
P-EEEE
This procedure implements properly weighted proposal distribu- tion for the unnormalized version of the locally constrained distribution ((og) (- x)).
Algorithm 1 Character proposal:
procedure Character_proposalle mass + Apply Eq. (14) to p(: x))
1. p
start at trie root node D path weight under de
4.
C
3. < {
S 0
T ++ 0
7.
(s)) -
9.
while true:
a: aase(pa)
for 4 pa E E
10.
P1
masa(p)
a: se pa) for a E Σ
11.
P2
(app)
12
i
EDT
EOT E E:
D End of token available (Le., Acos)
13.
(p())
BDTT(
T(p)
S S (p)
15.
9t (1)pp(a)))))) (2(a) for a E}
D Note: BOT & X.
Q+ EeEr
17.
ifQ = 0:
D. camnot continue farther
break
a~T/Q
Sample next character proportional
T(pa) t π (p) QQ))/Q
20.
p pa
extend the prefix transition the node)
Ct C..p (a)
W+ W+ENes w(x')
24
2 ~ w()) w
return (x, W
is straightforward to verify that the character proposal an instance of set-based proposal speedup (Def. 2), which is properly weighted according Proposition 1.
26

---

Published as a conference paper at ICLR 2025
Name
Proposal
Target
Inference alg.
Language model
p
P
Exact
grammar constrain!
Eeft
left
Exact
grammar constraint, weight correction
Eeft
9ctt
w/ grammar constraint, potential
Eeft
feft Pexp
IS
w/ grammar constraint, potential, and correction grammar constraint, potential, correction, and resampling
Eeft
IS
faft
g
SMC
Table 9: Potentials, models, and inference algorithms. Note that goif differs from g. as the former only incorporates the product of efficient potentials Defi, Consistent with our approach throughout the paper, we also assume that the local product of experts lett, only features the product with efficient potentials Peft.
D ESTIMATING INFERENCE QUALITY
The KI. divergence KT.(g g) measures how well the distribution q approximates the global product of experts g. The exact KL,(q || g) is generally intractable, for reasons: g is known only up to normalizing constant, and q (which, for us, represents the marginal distribution of a particle at the end of inference) is not known closed form. To address the first difficulty, we instead measure the approximation quality log Z KL(g g): because Z is function only of g and not of the inference algorithm, as we vary the inference algorithm, the resulting variation in approximation quality is caused solely by changes to the KL term. To address the second difficulty, we work over extended state spaces to obtain lower bounds on the approximation quality (Lew et al., 2022; Zhao et al., 2024). In Appendix D.1 show how to estimate this quantity in general setting, and in Appendix D.2 we explain how to adapt this result to the setting where incorporates hard constraints (making the KL divergence discussed above potentially infinite).
D.1 IMPORTANCE SAMPLING AND SEQUENTIAL MONTE CARLO
We begin by considering the case of a generic importance sampling algorithm, which draws K particles (6) EOS from a proposal distribution q to approximate the target distribution a. For each particle, the algorithm computes importance weight relative to the unnormalized target distribution ō (x) = o where Z, > the unknown normalizing constant.
Estimating the quality of 1-particle inference. very simple inference strategy use the proposal to generate a single sample æ, without further correction. A reasonable measure of inference quality would be KT.(q || r). However, due the unknown normalizing constant of o, the quantity that we can more easily estimate unbiasedly is log Zo KL(q σ) Ex [log ø (xx) log q(x)) As the expression suggests, we can estimate this quantity by sampling many sequences æ independently from and computing the average across samples of log ō (ax) log ((x). Because Z., depends on only o, and not the inference algorithm, we can compare proposals y by estimating this quantity; higher is better, implying lower KL(q o).
Estimating the quality of K- --particle IS. In K-particle IS, we consider the posterior approximation be the distribution obtained by running importance sampling and resampling a particular particle (k) with probabilities proportional the normalized particle weights. Formally, let S A" EOS x E be the space of K-particle collections with distinguished, chosen particle; we write elements of S as (xx(k) x -k), where x (x((0 i 1 K * k} the K unchosen particles. The importance sampling procedure defines the following distribution over S:
(x))
Øns (k) x
def
II (((x
(15)
Di=1
where w(x of the marginal posterior approximation
(( प(
is the importance weight for particle (0)) We are interested in the quality
dis
Σ
qis (1x (M) xx))) 1/x (k))
(16)
(z)(k) x E)
x)
Although we can generate samples from 9s (by running importance sampling and selecting a chosen particle), we cannot evaluate its density exactly, so cannot directly compute unbiased Monte
27

---

Published as a conference paper at ICLR 2025
Carlo estimates of log Z. distribution a to obtain a new distribution dis over S, following Andrieu Roberts (2009):
KL o) before. Instead, extend the state space of the target
Tis (2)) , dil < x (o( where o (()) der II IQ( (17)
17t
We write ōis Zs for the unnormalized extended target.
Note that the marginal distribution of the extended target,
o (2)
(ss(( I 1)) = x(0)
(18)
(2e(*) x1)SS
is equal to (xx). The KL divergence between two joint distributions is lower-bounded by the KL divergence between their marginals, so we have KL(gis o) I KL( || dis).
Both @s and ois have tractable joint densities, repeatedly generating (x(*), _b) gis and computing the log density ratio, which simplifies into log average particle weight.
estimate log Z. KL ois) by
Proposition 2 (Estimating log Zo KI 11 σ)). Consider K particles x!() generated from the proposal q and let w(xx(() = ((x(0)//((()) be their importance weights. Then K > w(x( is lower bound on log Zo KL(gis o).
log 1
Proof.
log Zn - KL( o) 2 log Zo - KL( || lss)
(19a)
ãss((x(()) _k=k))
log
(19b)
ais (x)((((()), xx=x))
R (zx(1()) Tiiek ((xx))
log
(19c)
oss
(x(11)
(o(a(t))
IIse ((x(11)
DK w((((1)
1 R (xx((())
Ilise ((x)))
log
(19d)
9is
(x((1) (/an("))/(((("
Ilisk ((xx(0)
E w(
log
(19e)
9is
A ((((()))
E
log
(1)
(19f)
K
Hence, log + EK
wxx(1)) can be seen as single sample estimate of log Z,- - -KL(qis o). with (aliin((((ee (x)) x x= x (k)) ) ons (is(2x (t) x_ (())), which decreases as the number of particles increase (Lew et al., 2022). As before, the term log Zg is constant that independent of the inference algorithm, so this estimate can be used as measure of inference quality across algorithms, where higher is better.
negative bias. The precise bias can be shown to be (L
Estimating the quality of SMC. The same logic as above can be applied to SMC (Andrieu & Roberts, 2009; Lew al., 2022; Zhao et al., 2024). As in the IS case, use extended target aswc such that the density ratio works out to exactly the average particle weight at the end of the algorithm.
D.2 ESTIMATING INFERENCE QUALITY FOR REJECTION-SAMPLA VARIANTS
When attempting to estimate the discrepancy between samples for algorithms qalg and g. one difficulty that (T 9) can be infinite when g incorporates hard constraints. This is because, in those
28

---

Published as a conference paper at ICLR 2025
cases, there is positive probability on the outcome that all generated proposals fail to meet the constraints, and thus have mass under g. A potential solution to this issue, explored by Zhao et al. (2024), is to instead estimate (g(99gg))) But this requires exact samples from g, which are impractical to obtain our setting. We thus take different approach and consider rejection-sampled versions of each of our algorithms, Gag which draw samples Bag repeatedly until Julg 0. In this case, we have
(ar g(x)
Laig (ar)
(L
Endas
log
(20a)
qaig (z)
Enias
log
(20b)
g (xx) Zalg
galg (alg(Z) g(x)
log
log Lalg
(20c)
where 7 the acceptance rate of Gag (which we can estimate with standard Monte Carlo), and we
can estimate the first term in Eq. (20c) up to an instance-specific constant by the derivations above.
29

---

Published as a conference paper at ICLR 2025
Table
Columns
singer
singer_id name, concert_id, concer taamert_name,....
concert
Example schemn
Query
off
4 Pexp
Description
SELECT song_id id FROM singer ...
X
Invalid column name Invalid column name for table Valid column name for table
SELECT singer_id FROM concert...
x
SELECT singer_id FROM singer...
(h) Example queries potential values
Table 10: Overview of potentials used in Spider experiments for given schema. We condition the base language model using two potentials. Pat ensures syntactically valid SQL queries that only include table and column names present in the schema. 4 Peepp further restricts SQI. queries by ensuring correct correspondence hetween column and table names.
E DOMAIN DETAILS
This section provides further details on the domains used in the experiments.
E.1 TEXT-TO-SQL (SPIDER)
Spider is a large-scale text-to-SQL dataset of natural language questions and database schemas. Given a natural language question and schema, the task is to generate valid SQL query that is semantically equivalent to ground-truth query. In this domain, Peif is used to enforce valid SQL syntax according to the SQL grammars released by Roy et al. (2024). These grammars include schema-specific constraints that limit table and column names to those present in the given schema but do not ensure correct table-column associations. Thus, we use Pexp to verify whether the (partial) SQL query references column that exists table, returning 0 in the case that it does not and 1 otherwise. Table 10 provides an example of oeft and Dexp applied to an SQL query. Since &esep is only semantically meaningful when generated query has fully specified the necessary table alias information to check correspondences, we only run the table-column verification at clause boundaries once the FROM clause has been completed. We evaluate on the development split of Spider with execution accuracy, which checks whether the predicted SQL query's output matches that of the ground truth query. We define p(x)) by prompting Llama-3.1 (8b) instruct with examples followed by rendering of the database and the natural language question.
E.2 MOLECULAR SYNTHESIS (GBD-17)
A recent line of work has applied LMs to the problem of molecular synthesis, with the aim of generating candidate molecules with properties similar to molecules from known databases (see Oliveira et al., 2022, for review)-most commonly (e.g. Flam-Shepherd al. (2022); Wang et al. (2024)) by prompting with examples of molecules in SMILES format (Weininger, 1988). We follow this approach, constructing prompts from random subsets of 20 molecules from the GDB- 17 dataset (Ruddigkeit et al., 2012). We evaluate generations using the standard molecule fitness function Quantitative-Estimall
Drug-likeness. (QED; Bickerton et al., 2012) implemented in the Python RDKit library (Landrum, 2024). This metric combines eight physicochemical properties of compound: Molecular weight, LogP, H-bond donors, H-bond acceptors, Charge. Aromaticity, Stereochemistry, and Solubility. Here, 2.f enforces SMILES syntax. To enforce properties not molecule validator that can be applied to partial
encoded by this syntax, we define T Pexppusnng SMILES strings, implemented in the Python partialsmiles library (O' Boyle, 2024). The validator checks the SMILES prefix to ensure that the atom's 's valences are in a list allowed valences, and attempts to find alternating patterns of single and double bonds to cover all aromatic systems in the partial string. The additional metrics reported in Fig. 4 are Validity (proportion of valid SMILES), Weight (exact molecular weight), De Novo Similarity (average pairwise Tanimoto similarity to the target distribution, excluding exact duplicates), and Diversity (inverse average pairwise Tanimoto similarity among compounds generated by particular method).
30

---

Published as a conference paper at ICLR 2025
E.3 GOAL INFERENCE (PLANETARIUM)
Recent work has explored using LMs for planning with languages like the Planning Domain Definition Language (PDDL) (Ghallab al., 1998), by either generating plans directly (Silver et al., 2022; Wong et al., 2023; Ying et al., 2023; Zhang et al., 2024; Zhi-Xuan et al., 2024), or generating descriptions of a task's initial and/or goal conditions, which classical planning algorithms for plans (Liu et al., 2023; Xie et al., 2023; Guan et al., 2023). In the spirit of the latter, we use the Blocksworld tasks from the Planetarium benchmark (Zuo al., 2024), which provides natural language descriptions of a task's 's initial and goal conditions along with their ground-truth symbolic representations in the STRIPS subset of PDDL (Fikes & Nilsson, 1971). The original dataset is extremely challenging, requiring the LM to output full STRIPS description of tasks with up to 100 objects-Zuu et al. (2024) report fewer than 2% of the outputs of Gemma 1.1 7B to even parseable. We therefore simplify the task by limiting our evaluation to examples with fewer than 10 objects. and requiring the LM to generate only the goal conditions by appending the ground boound-truth initial conditions to the pre-prompt. Here, Def encodes STRIPS syntax for goals within Planetarium 's Blocksworld domain definition; Fexpp uses a gold-standard plan known to satisfy the ground- truth task description, and calls the VAL plan validator (Howey al., 2004) to test whether partial goal descriptions according to that plan. The gold-standard plans for each instance were derived using the fast downward algorithm (Helmert, 2006). Note that is only possible to apply this Lexp potential to partial strings if goal descriptions are monotonic, that is, if any goal prefix describes a superset of the states that the full goal describes. This is the case for STRIPS, where goals must be described as conjunctions of literals, so that we can evaluate the potential after each literal in the conjunction is completed.
use search
valid
E.4 DATA SCIENCE (DS1000)
DS-1000 (Lai et al., 2023) is a challenging code generation benchmark on data science problems in Python, split into subsets requiring the use of six popular libraries: Pandas, NumPy, Scikit-Leann SeiPy, TensorFlow, and PyTorch. For each problem instance, the language model is prompted with an English description of the problem and sample test case in Python and is tasked with generating code that solves the problem and passes the test case. Each test case includes a result variable, and success depends the execution. In preliminary experiments, we observed that our language model was able to generate syntactically correct Python programs for every sample. We, therefore, set Doff for our experiments in this domain. Thus, unlike the other three domains, the proposal distribution for all evaluations of DS1000 was simply In this domain, 2oxp simply executes the test cases provided in the prompts from Lai al. (2023) on generated (partial) Python programs, and returns 1 if no errors are produced and otherwise (in particular, we did not make use of the output of test cases). Note that it is only possible to execute Python code when the generated sequence x consists entirely of well-formed Python statements, thus in this domain oa can only be meaningfully applied at the boundary of statements- this motivates aligning SMC particles using statements as their steps, explained in the "Further extensions" section in ($2).
31

---

Published as a conference paper at ICLR 2025
F RELATED WORK
Our contributions are primarily situated among several bodies of work.
First, there is large body of work leveraging LMs for semantic parsing or code generation tasks, while forcing adherence to a grammar or other constraints (Shin et al., 2021; Scholak et al., 2021; Poesia et al., 2022; Shin & Van Durme, 2022; Geng et al., 2023; Zheng et al., 2024; Moskal et al., 2024; Wang et al., 2024; Ugare et al., 2024). Closely related is series of algorithmic advances that enable the efficient construction and application of grammar constraints for sequential inference problems via compilation to automata (Deutsch et al., 2019; Willard & Louf, 2023; Kuchnik et al., 2023; Koo et al., 2024). This space is further discussed in Appendix F.1.
Second, there is large body of work that aims generate from LMs subject to hard soft constraints. Many such strategies are based in reinforcement learning (RL) (Ziegler et al., 2019; Stiennon et al., 2020; Bai et al., 2022; Ouyang et al., 2022), classifier-guide control (Cheng et al., 2024), efficient probabilistic inference through tractable proxy models (Zhang et al., 2023a), and locally applied logit biasing or masking based domain-specifie potential functions (Pascual al., 2021; Huang et al., 2024). This is further discussed in Appendix F.2. In addition, there is growing set of approaches that cast constrained sequential generation as probabilistic conditioning, leveraging the toolkit of probabilistic inference to derive principled generation strategies (Miao et al., 2020; Yang & Klein, 2021; Lew et al., 2023; Zhao al.. 2024; Park al., 2025; Puri et al., 2025). These works themselves are motivated by rich history of conditioning autoregressive models in NLP, often in combination with particle-based inference methods (Börschinger & Johnson, 2011: I; Dubbin Blunsom, 2012: Yang& & Fisenstein, 2013; Buys & Blunsom, 2015; Lin & Fisner, 2018), 8). A discussion of the most relevant works is expanded in Appendix F.3.
In this work, our algorithms aim to unify and improve on each of these bodies of preceding work, tackling semantic parsing and code generation tasks with a combination of grammar constraints (Dea), ) expensive potentials (Pexp), and asymptotically correct inference (via SMC).
F.1 GRAMMAR-CONSTIE
SEMANTIC PARSING WITH LMS
Shin et al. (2021) presented a system allowing LMs be locally intersected with (boolean) CFGs to restrict generations to conform to target formal languages, and that with only a few in-context exam- ples, such an inference-time strategy could outperform more substantial fine-tuning. Concurrently, PICARD (Scholak et al., 2021) presented an approach for intersecting LMs with an incremental parsing algorithm and showed how additional context-sensitive constraints could imposed, such as requiring table-column matching for SQL. generation via the use of programmable "guards". Synchromesh (Poesia et al., 2022) generalized these frameworks and extended the idea of incremental guards that can impose semantic restrictions during generation-such typing and scoping rules-by dynamically constructing constraints as regular expressions on the fly. A great deal of other work has explored variants of Arggmammar intersection including the effectiveness of pre-training models on code for these settings (Shin& & Van Durme, 2022), the runtime compilation of individual task instances into highly specific, aas-specialized grammars (Geng al., 2023), and even using the LM to generate grammars directly at runtime, that then restrict their own generation to solve a task (Wang al., 2024). Other work has focused more closely on the standard syntactic-constrain problem but with an emphasis on optimizing efficient data structures and algorithms for fast LM-CFG intersection (Ugare et al., 2024; Zheng et al., 2024; Moskal et al., 2024).
A parallel line of work in this space has been concerned with the efficient construction and application of constraints for sequential inference problems. Deutsch et al. (2019) first noted that regular and context-free grammar constraints could be pre-compiled to iilomata-thhsse could then be used during sequential inference to impose constraints with near-zero runtime overhead. This approach was independently developed and efficiently implemented in the context of restricting LM generations to regular expressions by the Outlines (Willard & Louf, 2023) and ReLM librarics (Kuchnik et al., 2023). Similar work was later developed by Koo al. (2024), who extended several formal automata- theoretic characteristics of these constructions.
This work has noted the complications of efficiently intersecting grammars whose atoms are terminals and LMs whose atoms are tokens, which we refer to as the efficient and accurate solution this problem space was one of several desiderata for our proposal
alignment problem. An
32

---

Published as a conference paper at ICLR 2025
algorithm (see Alg. 1 in Appendix C for more details). These works have also discussed considerations that arise in the construction of automata, whose arcs are tokens, in the assigmment of probabilities to strings. Namely, there are exponentially many latent token trajectories that correspond to generated sequence. While the correct method for assigning string probabilities involves marginalizing over these trajectories (Cao & Rimell, 2021), in practice, simply using the canonical tokenization accounts for the overwhelming majority of the probability mass and can be justified (Chirkova et al., 2023; Kuchnik et al., 2023; Berglund et al., 2024; Vieira et al., 2024). In the present work, we do not enforce this assumption and allow all token trajectories.
F.2 CONDITIONAL. GENERATION SUBJECT TO CONSTRAINTS
Language models pre- pre-trained on a next-word objective reflect the distribution of their pre-training corpora, but often the inference-time needs of tasks necessitate that LMs modify this base distribution.
One approach to this class of problems is fine-tuning or reinforcement learning via some set of data that more closely mirrors the target task, such as via reinforcement learning from human feedback (RLHF) (Ziegler et al., 2019; Stiennon et al., 2020; Bai et al., 2022; Ouyang et al., 2022). but this method comes with challenges such as hyperparameter sensitivity and distributional collapse (Zheng et al., 2023; Zhu et al., 2023; Xiong et al., 2024). Some of these drawbacks can be mitigated by utilizing on- on-policy data (Tajwar et al., 2024) and imposing a KL penalty that penalizes shifting an LM too far from its prior distribution, casting optimization as variational inference problem (Korbak et al., 2022; Amini et al., 2025).
Another time approach to controlled generation for an LM is via direct modification to the LM's sampling distribution. This may be done via controlling intermediate layer activations with classifier guidance (Cheng et al., 2024), guiding autoregressive generation with proxy probabilistic model for which estimation of the conditional density is tractable (Zhang et al., 2023a), or most commonly by directly intervening on the final logits before sampling to impose intersection with potential function. Pascual et al. (2021) presented an early variant of such logit-biasing to encourage the presence of predefined guide words in generations.
This pattern is employed more broadly for hard constraints via logit-masking, setting the probability associated with particular tokens to zero, forcing the LM to sample from subset of its distribution over sequences. This approach is used in most of the grammar-consstrined semantic parsing work outlined in the previous section. Most recently, there have been attempts to restrict and re-weight generations not only via grammars but through additional expensive potentials such as grounded affordances in robotics settings (Ahn et al., 2022: Huang et al., 2024). However, in all of these works, constraints are imposed greedily, resulting in local product of experts construction, and care is not taken to appropriately target the implied global product of experts. should then come as no surprise that while standard approaches to wvammar-constraines generation have been successful, they have been far from silver bullet (Tam et al., 2024).
F.3 APPROXIMATE POSTERIOR INFERENCE IN LARGE LANGUAGE MODELS VIA SAMPLING
This leads to a third line of work that formulates constrained generation from language models as posterior inference (Zhang et al., 2023a), and employs approximate inference to sample from the desired target distribution. This is in contrast to yet another line of work that views constrained decoding as an optimization problem, and tackles it via search (Meister et al., 2020; Lu et al., 2021; Zhang et al., 2023b) or continuous optimization (Dathathri et al., 2019; Kumar et al., 2021).
Several approximate inference algorithms have been explored for generating constrained samples from LMs, including rejection sampling (Poesia et al., 2022), as well as MCMC (Miao et al., 2019; Hic et al., 2022: Zhang et al., 2020; Qin et al., 2022; Kumar al., 2022; Du et al., 2024). A weakness of MCMC-based approaches is that they do not fully exploit the autoregressive factorization of modern language models; each edit to candidate sequence requires re-evaluating the entire sequence (or at least the entire suffix) to compute a new target density.
Lew et al. (2023) propose SMC steering of LMs via probabilistic programming specifications. This work enables provably accurate posterior sampling from such conditional targets, globally steering generation while only ever computing local constraints. Our approach builds their work.
33

---

Published as a conference paper at ICLR 2025
Shortly thereafter, Zhao al. (2024) independently developed framework for expressing various LM tasks as probabilistic inference problems that can be tackled with SMC. Similar to our work, Zhao et al. (2024) guide SMC with intermediate targets in their case, learned twist functions via a novel contrastive method-that enable estimation of the expected future value of each candidate partial sequence. Their work also developed methods for evaluating LMM inference algorithms via bi-directional bounds on the log- oog-partition function that can be used to estimate the KL divergence between the inference and target distribution. In contrast to this prior work, our approach SMC leverages incremental static and dynamic analyses to inform our proposal distributions and twist functions, as opposed to learning components of these algorithms procedure. In addition, our results directly relate the quality of our posterior approximation to improved performance on series of standard, difficult benchmark tasks.
a costly contrastive fine-tuning
Concurrent with our work, Park et al. (2025) have highlighted the distinction between the prevalent locally constrained decoding approach and the more accurate targeting of the global distribution that arises from combining language models with constraints. Park et al. (2025)'s approach to approximate the global distribution is based on the concept expected future grammaticality, which the probability that the completion to be sampled from the LM will be compliant with the given grammar. The authors describe an iterative algorithm that approximates the global distribution by refining the estimates of the expected future grammatically. However, the proposed strategy shows relatively slow convergence, was specifically designed for a CFG constraint, and may not be easily adaptable to constraining with multiple potential functions.
34


Reviews:
[{"review_id": "i4kzsY3OWv", "reviewer": "Reviewer_MMNX", "summary": "Controlling LLM generation to follow logical, syntactical or semantical (soft) constraints is a challenging task. The authors propose to unify controllable generation as sampling from the un-normalized distribution p_{LM}(x) \\phi(x) where \\phi is an energy function specifying the constraints. The authors propose to leverage sequential Monte Carlo to sample from the desired un-normalized conditional distribution. The authors conducted extensive evaluation of their approach on various downstream tasks with different combinations of constraints and  have demonstrated significant improvement compared to the LLM baseline. One important ablation study has suggested the positive correlation between approximation accuracy and generation quality, motivating for further research on improving the sampling algorithm or the proposal distribution.", "questions": "What are the other (potentially better) proposal distributions? E.g. LLM fine-tuned/prompted with task-specific supervision.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work solves one important problem with some of the widely adopted constrained/structured generation such as Guidance, SGLang and Outlines: that is, these framework achieves control by masking out next-tokens that would violate the constraint, leading to biased sampling (compared to the ground-truth conditional distribution). By leveraging sequential Monte Carlo, the proposed technique is able to approximate unbiased sampling in a relatively practical/scalable way. Empirical evaluations demonstrate strong performance on challenging real-world problems.", "weaknesses": "Some detailed analysis/case study on the sample complexity of SMC would provide more insights, especially how much better SMC is compared to naive importance sampling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eqnX0FgPTf", "reviewer": "Reviewer_gr6N", "summary": "The authors apply sequential Monte Carlo to tackle semantic parsing problems involving global constraints. They introduce an enhanced SMC approach, incorporating efficient stochastic approximations of full token-masking distributions and semantic potential to boost performance across five diverse datasets. Additionally, they estimate the KL divergence between each method’s output distribution and the global product-of-experts distribution, demonstrating that the latter is well-calibrated.", "questions": "See weaknesses. \n\nAlso minor writing issues for clarity, the authors should specify what is meant by \"some\" in lines 41-44 and clarify the specific applications referenced in lines 157-158.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose adapting SMC methods to novel semantic parsing tasks, resulting in notable performance improvements. \n\nThe author conduct a interesting analysis and shows that resampling improves the approximation of the global product-of-experts distribution and approximation quality are consistent with those observed in downstream accuracy evaluation.", "weaknesses": "In terms of experiments: \n- The authors do not emphasize their unique algorithmic contributions within the experiments. The authors could also report the performance of LM with grammar constraint, weight correction and resampling as a regular SMC baseline to further show the effectiveness of semantic potential. Additionally, the authors lack a detailed comparison between their method and the highly relevant SMC method in https://arxiv.org/pdf/2306.03081, and should report it as a baseline, e.g., including without-replacement resampling. \n- For ablation studies, how the number of particles will affect the final performance should be analyzed.\n\nThere is no mention of the computation cost, it would be very useful if the authors could evaluate the efficiency of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "acNKJCdHnU", "reviewer": "Reviewer_8wBr", "summary": "The paper concerns inference-time approaches for controlled generation with language models. Building on [Lew et al 2023], the authors develop a method based on sequential Monte-Carlo. The method proceeds segment-by-segment, first extending the segment (e.g. generating a next-token) subject to a token-level score (e.g., arising from a grammar constraint), then reweighting the candidates based on a partial sequence score (e.g., whether the code-so-far has a runtime error), then determining the next set of candidates by resampling candidates based on their weights.\n\nThe authors evaluate the method using prompted Llama 3 (base or instruct, varied by task) on 4 tasks. In each task, they construct task-specific token-level and partial-sequence level potentials, and provide an ablation of each of their three proposed components. The authors study the divergence between the target distribution and the distribution induced by running the algorithm, finding that each component leads to a lower KL divergence. Additionally, they provide a nice visualization of the sampling distributions and target distributions for their molecular generation task, and show that samples from their method improve along various dimensions. \n\nIn general the paper is written quite precisely, and several intuitive ideas (e.g., token masking or filtering out a sequence if its code doesn't run) are placed into a probabilistic framework.", "questions": "Please see the questions in the Weaknesses above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality\n- To my knowledge, the extension of sequential Monte-Carlo to the task settings in the paper, and the specific generation receipe (re-weighting, resampling) are new. However, I am not closely familiar with [Lew et al 2023] or its subsequent papers (which are mentioned several times by the authors). Therefore, my evaluation of novelty may be slightly off. \n- Placing ideas such as token-masking, filtering out partial sequences, and selecting partial sequences to explore next in a probabilistic framework is a nice contribution (with the same caveats in the point above).\n\nQuality\n- The experimental evaluation presents a controlled study that ablates each component in the model.\n- Derivations and the divergence analysis seem to be of high quality.\n\nClarity\n- Once the reader becomes familiar with the terminology, the paper is written clearly and precisely. \n\nSignificance\n- The method could potentially be useful in settings where token-level and partial-sequence level constraint functions are available (e.g., those in the experiments). This has some generality (though could also be viewed as a limiting factor).\n- Placing more domains and settings into the probabilistic framing from [Lew et al 2023] helps to further the probabilistic perspective on sequence generation.", "weaknesses": "My primary concerns were on the experimental validation. The paper performs a self-contained, controlled experiment using one Llama 3 model on a set of tasks. As a result, it was unclear how the findings generalize to other models, or how they compare in terms of performance to other methods in the literature.\n\n1) For example, taking the example of DS-1000, the absolute numbers are quite low: the DS-1000 paper reports up to 39.2 performance (with Codex-002) versus 28.5% here (with Llama 3). These are *not* comparable since they use different models, but it would be nice to see how this method performs for models closer to the state of the art. Similarly, Lever [1] reports numbers on Spider from previous work that range from 67.0% to 81.9% [1]. The reason this is important is that the exact experiment setup can lead to different conclusions on the performance of methods, so it was concerning that the absolute numbers seemed low. However, the authors could potentially clarify this.\n\n2) It was also unclear why 10 particles was selected, since in these sampling methods the number of samples can impact performance, and we often want to understand how performance varies with the sampling budget. How does the method vary as the number of particles varies? Is there a sample-and-rerank approach that could outperform this method if it drew a large number of samples?\n\n[1] LEVER: Learning to Verify Language-to-Code Generation with Execution, Ni et al ICML 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xDvRh2l8iF", "reviewer": "Reviewer_4hyJ", "summary": "The paper introduces a Sequential Monte Carlo (SMC) approach for constrained generation in language models to address semantic and syntactic constraints that traditional methods fail to handle effectively. The novel elements include integrating domain-specific constraints via potential functions, weight correction to mitigate the bias from locally greedy decoding, and adaptive resampling that focuses computational effort on promising sequences. The method was tested on four challenging tasks: Python code generation, text-to-SQL translation, goal inference, and molecular synthesis. The experiments compared the SMC-based approach to several baselines and showed that incorporating weight correction and semantic potentials significantly improved performance, while adaptive resampling further enhanced results by reallocating resources to better particles. The total SMC method outperformed the ablated SMC variants on the selected task.", "questions": "-Is there a difference between the right part of Figure 1 and Table 2? I would suggest the authors keep only one to avoid redundancy.\n\n-Why was the instruct version of Llama 3.1 used for the SQL task but not the others?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-Good motivation from analysis of weight formulations for importance sampling.\n\n-Benchmarks validate claims that the proposed algorithmic components improve downstream performance. Additionally, authors chose a sensible set of benchmarks.\n\n-Weight correction and resampling seem to be novel components.", "weaknesses": "-The method was not benchmarked against alternative methods. While the ablation study is useful, how does the method compare against other SMC-based techniques such as the ones cited in the related works section that are particularly relevant to this work? E.g. comparisons against the method in Lew et al. and Zhao et al. would be beneficial. There are other non-SMC-based methods that could also be benchmarked against.\n\n-Only Llama 3.1 8-B was evaluated. The manuscript would benefit from benchmarks on additional LLMs to see if results are consistent across similar sized LLMs. I would be curious to see if the benefits are as substantial on larger models, but I understand the authors may have limited computational resources for such analyses.\n\n-There is a lack of theoretical grounding as to the benefits of the components. E.g., a theorem rigorously showing the reduction in KL-Divergence shown in Figure 2 would strengthen the manuscript.\n\n-Notation can be difficult to follow at times. Exposition can be a bit drawn out in certain places, e.g. section 2. I appreciate the authors trying to point out the inefficiencies in each component of MC in order to justify their approach, but I think the exposition would benefit from a condensed explanation of, e.g., the computational burdens of IS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)