Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling
Authors: Ben Lipkin
Benjamin LeBrun
Jacob Hoover Vigly
João Loula
David R. MacIver
Li Du
Jason Eisner
Ryan Cotterell
Vikash Mansinghka
Timothy J. O'Donnell
Alexander K. Lew
Tim Vieira
Venue: COLM 2025 (2025)
Keywords: Controlled generation
Bayesian inference
Approximate sampling
Decoding methods
TL;DR: We introduce a fast, principled, and adaptive sampler for controlled generation.

Abstract: The dominant approach to generating from language models subject to some constraint is locally constrained decoding (LCD), incrementally sampling tokens at each time step such that the constraint is never violated. Typically, this is achieved through token masking: looping over the vocabulary and excluding non-conforming tokens. There are two important problems with this approach. (i) Evaluating the constraint on every token can be prohibitively expensive---LM vocabularies often exceed 100,000 tokens. (ii) LCD can distort the global distribution over strings, sampling tokens based only on local information, even if they lead down dead-end paths. This work introduces a new algorithm that addresses both these problems. First, to avoid evaluating a constraint on the full vocabulary at each step of generation, we propose an adaptive rejection sampling algorithm that typically requires orders of magnitude fewer constraint evaluations. Second, we show how this algorithm can be extended to produce low-variance, unbiased estimates of importance weights at a very small additional cost---estimates that can be soundly used within previously proposed sequential Monte Carlo algorithms to correct for the myopic behavior of local constraint enforcement. Through extensive empirical evaluation in text-to-SQL, molecular synthesis, goal inference, pattern matching, and JSON domains, we show that our approach is superior to state-of-the-art baselines, supporting a broader class of constraints and improving both runtime and performance. Additional theoretical and empirical analyses show that our method's runtime efficiency is driven by its dynamic use of computation, scaling with the divergence between the unconstrained and constrained LM, and as a consequence, runtime improvements are greater for better models.

Published as a conference paper at COLM 2025
Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling
Benjamin Lipkin'1 Benjamin LeBrun'3 Jacob Hoover Vigly! João Loula! David R. MacIver Li Du Jason Eisner Ryan Cotterel12 Vikash Mansinghka'
Timothy J. O'Donnell13.4 Alexander K. Lew+1.7 Tim Vieira
'MTT 2ETH Zürich McGGill +Canada CIFAR AT Chair Mila
'Johns Hopkins Yale 8CHI FRO
Abstract
The dominant approach to generating from language models subject to some constraint is locally constrained decoding (LCD), incrementally sampling tokens at each time step such that the constraint is never violated. Typi- cally, this is achieved through token masking: looping over the vocabulary and excluding non-conforming tokens. There are two important problems with this approach.
(i) Evaluating the constraint on every token can be prohibitively expensive-LM vocabularies often exceed 100, 000 tokens. (ii) LCD can distort the global distribution over strings, sampling tokens based only on local information, even if they lead down dead-end paths. This work introduces new algorithm that addresses both these problems. First, to avoid evaluating a constraint on the full vocabulary at each step of generation, we propose adaptive rejection sampling algorithm that typi- cally requires orders of magnitude fewer constraint evaluations. Second, we show how this algorithm can be extended to produce low-variance, unbiased estimates of importance weights at a very small additional cost estimates that can be soundly used within previously proposed sequential Monte Carlo algorithms to correct for the myopic behavior of local constraint enforcement. Through extensive empirical evaluation in text-to-SQL, molec- ular synthesis, goal inference, pattern matching, and JSON domains, we show that our approach is superior state-of-the-art baselines, supporting a broader class of constraints and improving both runtime and performance. Additional theoretical and empirical analyses show that our method's run- time efficiency is driven by its dynamic use of computation, scaling with the divergence between the unconstrained and constrained LM, and as a consequence, runtime improvements are greater for better models.
O https:///gi http:///httb..mmmmmmmm/gggeneoo/
1 Introduction
Many tasks in scientific and engineering disciplines can be approached through controlled generation of strings from a language model subject to hard constraints. For example, API call that matches an endpoint, produce SQL queries that
may seek to generate are consistent with the schema of a database, or design molecule that satisfies a target specification. The dominant approach in these settings is locally constrained decoding (LCD), which forces each sampled token to conform to the constraint (Lu et al., 2021; Shin et al., 2021; Scholak et al., 2021; Lu et al., 2022; Poesia et al., 2022; Shin & Van Durme, 2022; Geng et al., 2023; Beurer-Kellner et al., 2024; Huang et al., 2024; Moskal et al., 2024; Ugare et al., 2024; Wang et al., 2024a; Zheng et al., 2024; Banerjee et al., 2025).
*co-first authorship, fco-senior authorship. contact: lipkinbemi t. edu tim. diviiirrae v.eeir@@gaall.....mm com This paper focuses runtime control, but we note that many training- based control methods exist (e.g., Ziegler et al., 2019; Stiennon et al., 2020; Bai et al., 2022; Ouyang al., 2022; Rafailov et al., 2023).
1

---

Published as a conference paper at COLM 2025
This approach suffers from two critical drawbacks. First, the typical method for sampling from this distribution by enumerative token masking can be slow. Full masking requires checking the constraint against every item in the vocabulary-whie can often consist of more than 100, 000 lokens-before before finally filtering, renormalizing, and sampling. In some special cases, such as when the constraint can be expressed as regular or context-free gram- mar, optimizations are available that make checking every token feasible (Willard & Louf, 2023; Kuchnik et al., 2023; Koo al., 2024; Ugare al., 2024; Dong al., 2024; Cognetta et al., 2025; Park et al., 2025). However, for black-box constraints, such optimizations do not apply. Second, as often observed (e.g., Lew et al., 2023; Park et al., 2024; Gareev et al., 2024; Ahmed et al., 2025; Loula et al., 2025; Kempton& & Burrell, 2025; Ye et al., 2025), by renormalizing only the local distribution (over tokens), this approach can distort the global distribution (over strings). Because LCD myopically enforces constraints at each step, it can sometimes greed- ily sample its way into low-probability regions of sequence space (see $2 for discussion).
Several papers have noted this problem and proposed approaches that recast controlled generation as probabilistic conditioning, treating the problem as posterior inference (Rosen- feld et al., 2001; Miao et al., 2020; Krause et al., 2021; Yang & Klein, 2021; Meng et al., 2022; Qin et al., 2022; Shih et al., 2023; Zhang et al., 2023; Hu et al., 2024; Zhang et al., 2024a;
Faria & Smith, 2025). In this framework, approximate inference methods e-thods-e-g- importance sampling (IS) or sequential Monte Carlo (SMC)-can can be used to correct sampled sequences from the locally constrained distribution to the target global posterior (Börschinger & John- son, 2011; Dubbin & Blunsom, 2012; Yang & Eisenstein, 2013; Buys & Blunsom, 2015; Lin & Eisner, 2018; Lew et al., 2023; Zhao et al., 2024; Puri et al., 2025; Loula et al., 2025).
A key diagnostic quantity for assessing the quality of a generated sequence the marginal probability of the constraint under the LM's local next-token distribution at each timestep,
del Σxex cc) where Po is the LM next-token-distribttoon over the vocabulary X, and lc checks whether given token conforms to the constraint at the current time step. Within sequential IS or SMC, Z arises as an incremental importance weight update. When this quantity is low, we have reached a point in generation where it is difficult to sample any continuation of the sequence that satisfies the constraint. For SMC specifically, this can be used signal for reallocating computation to more promising sequences during subsequent resampling. Using token masking, it is clear how to compute Z-simply sum over all unmasked tokens. However, if we would like to sample from the local constrained token distribution without evaluating L. over the entire vocabulary, this quantity may not be directly available, and we must seek estimate it.
In this paper, we introduce an exact sampler for constrained token distributions whose runtime is faster than token masking, often by orders of magnitude. Our algorithm is based on rejection sampling and, thus, is a Las Vegas algorithm, i.e., an exact algorithm with stochastic runtime. Rather than using fixed compute for each step, compute scales dynamically based on need. Furthermore, we derive unbiased estimators of Z for this algorithm that can be used to correct samples globally within an SMC framework.
Our core contributions are as follows:
A fast Las Vegas sampling algorithm compatible with any constraint. We develop adap- tive weighted rejection sampling (AWRS), sampling algorithm for constrained generation. Like other rejection sampling algorithms, the cost of our approach scales with the diffi- culty of the constraint. However, our adaptive algorithm outperforms standard rejection sampling by capitalizing on the statistical structure of the next token distribution. Due to the speed of this algorithm, we can comfortably evaluate arbitrary black-box constraints. Stochastic estimates of 7 to correct for greediness. We develop an approach to calculate low-variance, unbiased estimates of Z. for AWRS, supporting its integration within approximate inference methods like SMC.
Runtime analysis. We theoretically and empirically characterize the work done by constrained decoding in terms of the probabilistic update between the LM's unconditional next token distribution and the conditioned target distribution. Critically, AWRS runs
2See App. A for detailed discussion of language modeling as probabilistic conditioning, importance sampling, and sequential Monte Carlo.
2

---

Published as a conference paper at COLM 2025
Enumerative Token Masking
Check every token.
Z. = Erex (c(x)
log Pu
Adaptive Weighted Rejection Sampling
Check tokens ~ Pg (1 (o) +
Figure 1: Our approach (bottom) compared to enumerative token masking (top). Only subset of the tokens are checked while sampling from the same distribution.
faster when the base model is better able to capture the meniiinn that our approach is more efficient for more accurate LMs LMs-aligning with scaling trends.
Empirical evaluations. We evaluate AWRS alongside several state-of-the-ae baselines five challenging controlled generation benchmarks. AWRS yields improvements to expressiveness, runtime, and accuracy across relevant comparisons.
Background
Locally Constrained Decoding (LCD), A language model Po over an alphabet A' probability distribution over the set of strings X We write for individual tokens and for complete strings. A global constraint function c X' + {0,1} encodes the set of valid strings L C X
The problem of controlled generation can be expressed as sampling ~ P,
where def Po x E C), ie., sampling a complete string from the LM that satisfies the constraint while preserving the relative probabilities of possible strings. This latter property is what distinguishes proper global conditioning from arbitrary constrained sampling.
During the autoregressive generation of string, it is sometimes possible to evaluate whether sampling any given token would cause an immediate violation of the constraint. For example, if constraint requires writing sentence where no word exceeds 5 characters, the only possible continuations to "north" should induce word boundaries, rather than continuing with "ern" "east". At each step of generation, based
current string prefix Xp, we assume access to a local constraint function Le: X' + {00, 1}, encoding a set of valid Vx,: Xp Xx & L. That is, if the local constraint function rejects a token x, there is no valid continuation of xp that begins with x.3
next tokens C C X, such that x & C =
Fixing a prefix Xp, let Po denote the LM's local prior distribution over the next token note this distribution is conditioned on the preceding tokens. At each step, LCD samples a next token from the local posterior distribution p induced by the local constraint function:
1 Z ((x)
p(x) def
p(x) del Po(x) 1e(x)
def Σ (xx)
(1)
X
where is its unnormalized density and Z is its normalizing constant. (Note 0 < < 1.) Intuitively, Z is the total probability of satisfying the local constraint under Po- The most common approach to implementing LCD token masking: computing exactly during generation, by evaluating Le every item in the vocabulary, zeroing impossible tokens, summing Po(x) over the remainder to compute Z, and renormalizing to obtain (Fig. 1, top).
By applying constraints locally at every token, LCD can greedily sample its way into www-prbabilltty sequences that are difficult or impossible to recover from. For example, continuing with the constraint of generating sentence where no word may exceed characters, an LM will struggle to complete the prefix "The Fed says the cost of a 30-yr fixed mortg", despite there having been no issues up until that point (see Lew et al., 2023).
3See App. 1.2 for more detailed discussion of mapping global constraints to local constraint checkers.
3

---

Published as a conference paper at COLM 2025
Interestingly, such dead-ends can be readily detected using precisely the quantity Z com- puted as a byproduct of LCD. When Z is very low, we have reached a point in string generation where only very few, improbable tokens can continue the string. This local Z can be used in sequential Monte Carlo (SMC) to reweight partial generations (particles) for subsequent re-sampling steps, which tend to eliminate unpromising string prefixes and duplicate more promising ones (App. A and Alg. 1). In this certing-wweet LCD is used as proposal distribution within SMC-Z is precisely the incremental correction factor that can be derived by simplifying the importance weights (Naesseth et al., 2019).
Since Z is computed as byproduct of token masking, this algorithm provides its own correction factors when used as a part of proposal distribution in SMC. Unfortunately, however, modern LMs often have vocabularies exceeding 100, 000 tokens; evaluating 1c on every token in this set-and, thus, exactly computing Z-is often prohibitively slow. It would initially appear that exact sampling from the local posterior p and exact weight correction with Z are impractical in these cases.
In the next sections, exact, tractable for large vocabularies, typically fast in terms of average time, and provides correction factors to correct the greediness of LCD.
develop approach to sampling from the local posterior p that is
Simple rejection sampling. Simple rejection sampling is an algorithm that can provide exact samples from without looping through the entire token vocabulary. It works by drawing a token Po, then checking whether the token satisfies (x).. if does, the token is returned; otherwise, this process is repeated. The returned token is an exact sample from p.
Compared to the constant cost of token masking, this algorithm is Las Vegas algorithm, ie., an exact algorithm with a stochastic runtime. is easy to show that the expected number of samples drawn by the algorithm before meeting the constraint is 3; it can furthermore be shown that DxL (p |l Po) = log Z (Levy, 2008; Freer et al., 2010), and thus that the expected runtime exponential in DKT. (p Po). When the constraint is relatively easy to satisfy (i.e., when Z ~ so Dxz. (p || Po) is low), this can lead to runtimes that are much faster than those required by full-vocabulary token masking. However, when Z. is very small (Z < )),, rejection sampling's 's runtime can be even worse than that of token masking.
Adaptive rejection sampling (ARS). Adaptive rejection sampling (Gilks Wild, 1992; Mansinghka et al., 2009) is version of rejection sampling that is never slower than token masking and often significantly faster. In ARS, we adaptively remove each invalid token encountered while rejection sampling, that we never sample the same rejected token twice. This simple modification can dramatically improve the runtime of the algorithm (Fig. E2).
Both rejection sampling approaches evaluate 1c only on the samples they draw and, thus, can be more efficient than token masking. However, neither provides a direct way to exactly compute Z. A solution to this problem arises from the observation that for SMC, it suffices to use independent unbiased estimates of each local Z, rather than the exact quantities, as correction factors (App. A and Alg. 2; Naesseth et al., 2015).
3 Our Algorithms
In lieu of the exact but expensive correction factors obtained as byproduct of token masking, wish to find cheap, unbiased estimates of Z that we can compute as byproduct of simple or adaptive rejection sampling.
Our first observation toward this goal is that the nunber of rejected tokens sampled before generating a valid next token x contains signal about the magnitude of Z: when many
*Why Z and not sequence probability? While methods optimizing sequence probability, like beam search, partially address the sample quality desiderata, there are caveats. there are many valid tokens, whose sum is large, but each individual token has low probability, sequence probability will unfairly penalize any token (Koehn & Knowles, 2017; Murray & Chiang, 2018; Cohen & Beck, 2019; Stahlberg & Byrne, 2019). Methods that account for 7. do not suffer this drawback.
4

---

Po through no Published as a conference paper at COLM 2025
rejected tokens are generated, this suggests Z is small, and can serve sign that the current prefix Xp has landed us in a low-probability region of the global posterior P.
Indeed, in simple rejection sampling, the number of trials no + 1 (that is, No rejections plus the final success) is an unbiased estimate 1/Z.. Unfortunately, 1/ (110 + +1) is not an unbiased estimate of Z, and we require unbiased estimates of Z for sound use within SMC.
3.1 Warm-up: Weighted Rejection Sampling (WRS)
In the simple rejection sampling setting, we can collect more data about Z. by running 1. > additional rejection loops. In addition reducing variance, this also supports calculation of an unbiased estimate of Z. The total number of trials T (rejections and successes) required to reach successes follows a negative binomial distribution with parameters and L + 1.
Letting E be the total number of rejections across the L + loops,
L
del T
(2)
(L++))))
H1 + L
is the minimum variance unbiased estimator (MVUE) for the Z. parameter of the negative binomial distribution, provided that I. > 1 (Forbes et al., 2011, App. C.1). This allows to define the following algorithm for jointly generating a next token x from alongside an unbiased estimate Ż of Z.
Definitio 1. Given an unnormalized target p as above, weighted rejection sampling generates (x, 7.) ~ QWRS as follows:
1. Run rejection sampling to obtain a valid sample x: Sample T1,.. ,ngg x rejections Yj until obtaining an accepted token C.
itd.
~
2. For budget of L 1 additional loops, repeat step 1 and count the number of rejections on each loop ni.., RL.
3. Calculate the estimate 2 del - atI, where -E ni.
4. Return (x, 2)
An implementation in NumPy can be found in Listing 1.
Proposition 1. For (x, 7.) ~ QwRs, x is distributed according to and [ Z.
(App. C.)
Proposition 2. The expected runtime of QwRS scales with O ())
(App. G.1)
Using these estimates, simple rejection sampling may be soundly integrated into SMC as a proposal distribution, supporting the correction of LCD's greediness. L = 1 is enough to ensure unbiasedness, and we find to work well in practice, but L. can be increased to trade higher runtime for reduced variance (Fig. F.1).
3.2 Adaptive Weighted Rejection Sampling (AWRS)
In the adaptive setting, the expected number of rejections is reduced, and the negative binomial estimator can no longer be used. However, an auxiliaryvvariable argument based on the framework of Lew et al. (2022) can be used to derive an alternative formula for the adaptive case based on not just the number of rejections but also the probability mass removed from po during adaptation.
Definition Given an unnormalized larget p. AWRS generates (x, Z) QAWRS as follows:
1. Sample (ri,.., T.g x) as follows: draw ny unique rejections r; until obtaining E C. Note that beyond the first step, we do not sample from po, but re-normalized distribution on X Izc.
Calculate Yo = 5N0 Po(r:)-
Generate one additional trace (si,.., Smy,"" x"), by continuing to sample as above from the remain- ing notjyet-r elements, through an additional nı new unique rejections, until finding an element x". Note that x* could be the same as x, since acceptances are replaced (unlike rejections).
4. Calculate the estimate 7, del 1 Vo where
n1 + n2.

---

Published as a conference paper at COLM 2025
5. Return (x, Z)
An implementation in NumPy can be found in Listing 2.
Proposition For (x, 2. ~ QAWRS, x is distributed according to p and EE|] Z.
(App. D)
Proposition 4. The expected runtime of QAwRS scales with (Ext Txx,, where
7x
def
Po(x) Po(x)+Z' i.e, the probability of each non-conforming token relative Z.
(App. G.2)
As above, AWRS generates next tokens and correction factors suitable for use within SMC. In addition, AWRS offers considerable runtime benefits. Trivially, since we cannot resample rejections, we must succeed after at most | \ C| rejection steps-the number of invalid tokens-no no matter how small Z is. AWRS also has lower expected runtime. Intuitively, we may think of the time it takes sample an acceptance as follows. Each non-conforming token may be considered a distractor if its individual mass is comparable to or higher than Z, the sum of all conforming tokens. Rather than all non-conforming tokens contributing equally, expected runtime is dominated by only these typically rare- distractor tokens. The exact value is derived and further explored in App. G.2. We also propose several extensions of AWRS with beneficial properties in App. H, including support for partial concurrency, properly weighted approaches to early stopping based on either mass explored or steps taken, and methods for combination with truncation sampling.
Experiments
Our experiments measure the practical impact of our methods on accuracy and runtime for tasks in different domains.5 We use task-specific metrics rather than evaluating the sampler's 's internal behavior (e.g., how accurately it estimates Z), but see Fig. 2 and App. F. We compare AWRS to strong baselines through consideration of two versions: ARS-LCD, which performs simple LCD using unweighted adaptive rejection sampling, and AWRS-SMC, which uses the weighted version within SMC.
Methods. We first compare the following uncorrected methods in terms of both runtime and downstream task accuracy. Methods in this section yield M = 1 unweighted samples:
Base language model (Base LM). Sample sequences of tokens from the language model (without forcing any constraints), i.., sample x ~ Po.
Locally constrained decoding with token masking (TM-LCD). The standard approach to
constrained decoding. We mask the entire token vocabulary, re-normalize, and sample. 6 Locally constrained decoding with adaptive rejection sampling (ARS-LCD). A faster implementation of LCD: rather than masking the entire vocabulary, we draw a sample from the same LCD distribution using ARS. (We do not yet use an importance-weight correction, so we run only the first rejection loop.)
The baselines above allow us gauge the degree which adaptive rejection sampling improves runtime. Our next set of methods go beyond LCD, returning a weighted ensemble of M strings such that the expected weight of in the ensemble is Po(x) lx(x & P(x).
Sample-Verify. Sample M complete strings from the LM and weight them according to 1 (which amounts to discarding strings & 2).
We note that our implementations are all written in pure Python and are relatively unoptimized. Runtime improvements presented in this work are driven purely by algorithmic advancement. Being flexible plug-and-pla method, we encourage talented systems practitioners to capture the many untapped speedups.
'Dee to the high cost of full token masking, we only include this baseline for one benchmark, from speed-up.
which we illustrate our ofders-of-magninn
This baseline a common approach for incorporating constraints into an LM generation pipeline (Cobbe et al., 2021; Hendrycks et al., 2021; Nakano et al., 2021; Ahn et al., 2022; Shi et al., 2022; Uesato et al., 2022; Olausson et al., 2023; Lightman et al., 2023; Ankner et al., 2024; Gandhi et al., 2024; Wang et al., 2024b; Xin et al., 2024; Zhang al., 2024b).

---

Published as a conference paper at COLM 2025
Sequential Monte Carlo with constraint twist (Twisted SMC). Sample tokens directly from the LM, but use Lx(x) as a twist function to filter partial sequences after they have been extended with token x. Note that this is programmable twist as in Loula et al. (2025), rather than a learned twist (Naesseth et al., 2019; Lawson et al., 2022).
Sequential Monte Carlo with AWRS proposal AWRS-SMC). Use the AWRS algorithm as proposal distribution for SMC. Like ARS-LCD, this method generates tokens using
an adaptive rejection sampling loop, but does calculate the correction factor.
Metrics.
Accuracy. The accuracy of a returned string is defined by the benchmark. For methods that construct a weighted ensemble, we report the expected accuracy of random string returned from this ensemble (with probability proportional to its weight). Runtime. The average number of seconds it takes to generate the M complete strings.
Benchmarks.
Text-to-SQL (Spider). Task: Generate SQL queries from a natural language question paired with its corresponding database schema. Data: Development split of the Spider dataset (Yu et al., 2018). Metric: Execution accuracy (checking if the produced SQL query, test database, yields the same results as the ground-trutt query). Base LM: Llama 3.1 8B-Instruct. Constvaint function: A Python parser for the SQL context-free grammars provided by Roy et al. (2024) to enforce syntactically valid SQI..
when executed
JSON. Task: Generate documents that conform to a specific JSON Schema. Data: The validation splits of the Github-trivial, -easy and -medium tasks in the JSONSchemaBench dataset (Geng et al., 2025). Metric: Whether a valid JSON document conforming to the schema is generated. Base LM: Llama 3.1 8B-Instruct. Constraint function: Check the output parses as JSON, and validate using the Python jsonschema library. Parsing is done with a streaming JSON parser, which allows incremental detection of some schema violations before the full document has been generated.
Goal inference (Planetarium). Task: Formally define an agent's goal within the STRIPS subset of the PDDL planning language, using a natural-language description of the goal alongside PDDL code that specifies the agent's starting conditions and plan to reach it. Data: Blocksworid tasks featuring up to 10 objects from the Planetarium benchmark (Zuo et al., 2024). Metric: Equivalence to the ground-trus
PDDL description. Base LM: Llama 3.1 8B. Constraint function: Check STRIPS syntax for goals as defined in the Plaaetarium Blocksworld domain + execute a simulation using ground-truth plan to verify if the resulting state matches the predicted (partial) goal.
Molecular Synthesis Tiss: Produce drug-like compounds using the SMILES nota- tion (Weininger, 1988). Data: Few-shot prompts created by repeatedly selecting 20 random samples from the GDB-17 database (Ruddigkeit et al., 2012). Metric: Quantita- tive Estimate of Drug-likeness (QED; Bickerton et al., 2012), a widely used measure of molecular quality. Base LM: Llama 3.1 8B, Constraint function: A SMILES prefix validator implemented via the Python partialsmiles library (O'Boyle, 2024).
Pattern matching. Task: Generate strings that conform to expressive pattern-matching specifications. Compared to formal regular expressions, these patterns contain explicit features that cannot be fully captured by deterministic finite-state automata, including unbounded center embedding and conditionals. Data: Over 400 pattern-matching spec- ifications generated via the pipeline in App. J. Base LM: Llama 3.1 8B-Instruct. Metric: Adherence to the specified pattern. Constraint function: An incremental pattern validator that checks whether a complete match remains possible given a prefix (Barnett, 2014).
8 The rationale is that the probability of returning x then approaches P(x) as M grows, so we approxi- mately return x ~ P, just as Base LMM returns x ~ Pg- Note that we could plausibly improve accuracy further by selecting the most probable string from the ensemble, more generally, by the minimum Bayes risk method of selecting or constructing "consensus string" with low expected task loss under the weighted ensemble.
9Our runtimes scale sublinearly in M because use parallel hardware (a GPU) Specifiicff, the calls to obtain the next-token distribution po from the I.I. are batched over the M strings
7

---

Published as a conference paper at COLM 2025
Method
Accuracy
Runtime (seclex)
Method
Accuracy
Runtime (sec/ex)
Base LM
0.523 (0.50, 0.54)
0.78 (0.76, 0.80)
Base LM
0.688 (0,66, 0.72)
2.35 (2.20, 2.52) 4.41 (4.08, 4.76)
ARS-LCD
0.572 (0.55, 0.59)
1.02 (0.98, 1.06)
ARS-LCD
0.773 (0.74, 0.80)
Sample-Verify Verify
0.609 (0.59, 0.63)
2.71 (2.61, 2.82)
Sample-
(0.83, 0.88)
6.18 (5.81, 6.56)
Twisted SMC
0.608 (0.59, 0.63)
2.60 (2.48, 2.72)
Twisted SMC
0.871 (0.84, 0.90)
5.17 (4.65, 5.71)
AWRS-SMC
0.600 (0.58, 0.62)
3.02 (2.90, 3.14)
AWRS-SMC
0.898 (0.87, 0.92)
12.71 (11.58, 13.87)
(a) Text-to-SQL
(b) JSON
Method
Accuracy
Runtime (seclex)
Method
Accuracy
Runtime (seclex)
Base LM
0.032 (0.01, 0.06)
1.07 (0.97, 1.17)
Base
0.271 (0.25, 0.29)
0.69 (0.67, 0.71)
ARS-LCD
0.18 (0.11, 0.26)
0.77 (0.68, 0.86)
ARS-LCD
0.522 (0.51, 0.54)
0.97 (0.93, 1.02)
Sample-Verify
0.205 (0.13, 0.28)
4.55 (4.25, 4.84)
Sample- Verify
0.594 (0.59, 0.60)
1.83 (1.79, 1.86)
Twisted SMC
0.479 (0.39, 0.57)
3,20 (2.93, 3.47)
Twisted SMC
0.591 (0.59, 0.60)
1.53 (1.51, 1.56)
AWRS-5MC
0.528 (0.44, 0.62)
(2.42, 2.82)
AWRS-SMC
0.615 (0.61, 0.62)
3.41 3.50)
(c) Goal Inference
(d) Molecular Synthesis
Method
Accuracy
Runtime (sec/ex)
Method
Accuracy
Runtime (sec/ex)
Base LM
0.562 (0.51, 0.61)
0.10 (0.09, 0.11)
Sample-Verify
0.786 (0.75, 0.83)
0.26 (0.23, 0.29)
ARS-I CD
0.980 (0.97, 0.99)
0.16 (0.13, 0.20)
Twisted SMC 0.813 (0.77, 0.85)
0.19 (0.18, 0.21)
TM-LCD
0.978 (0.96, 0.99)
6.91 (5.68, 8.46)
AWRS-SMC
0.990 (0.98, 1.00)
0.43 (0.35, 0.52)
(e) Pattern Matching
Table Comparison of method accuracy and runtime across domains with 95% boot- strapped confidence intervals. Runtime represents the average execution time (in seconds) across all instances in the dataset. Sample-Verify and Twisted SMC were run with M 10 particles. AWRS-SMC was run with M = 5 particles.
The runtime costs associated with each benchmark's constraint checker, along with further practical discussion of constraint programming, can be found in App. 1.1.
5 Results & Discussion
AWRS Outperforms State-of-the-Art Controlled Generation Methods. Tab. shows the accuracy and runtime of each method in each domain. We observe the following results:
Controlled generation outperforms uncontrolled generation. With little overhead to runtime, ARS-LCD improves accuracy over Base LM across all benchmarks.
Adaptive sampling is much faster than token masking, with no loss of accuracy. On the pattern matching domain - the only one where it was computationally feasible to
TM-LCD - ARS-LCD matches its accuracy while being > 50x faster. 10
Correcting for greediness improves accuracy. AWRS-SMC always matches or beats ARS-LCD, significantly improving it in four domains (Goal Inference, JSON, Text-to-SQL, Molecular Synthesis). The other domain (Pattern Matching) suffers somewhat less under greediness because its local constraint c is more precise, allowing prefix only if it has valid continuation.
AWRS-SMC outperforms existing approaches that correct for greediness. With half the number of particles, AWRS-SMC attains accuracy comparable to or higher than Sample-Veriie Verify and Twisted SMC in all benchmarks.
Next, we investigate how AWRS-SMC scales with LM size (Fig, L.1) compared to existing methods that sample from the global distribution.
AWRS-SMC with smaller LMs outperforms existing SMC approaches with larger LMs. Fig. L.1 shows how AWRS-SMC using Llama 3.2 1B yields better runtime and accuracy than Twisted SMC using Llama 3.1 8B and Llama 3.3 70B. This suggests that including
10This 50x speedup is at the level of complete sequence generation, including all time spent on LM computation. The speedup factor modulo this constant much greater.
8

---

Published as a conference paper at COLM 2025
Pacir nolt
Call
107
18
Liamna 8B
1o14
Z Li
13%
Dys (Fl (o) log
I Lama 708
Llama 1B
16
Figure 2: The number of AWRS calls to 1 (y-axis) scales with DRL (p Il po) (Nats; x-axis).
informative constraints in the proposal is compute-efficient way to make small models punch above their weight.
AWRS Achieves Speedups by Allocating Computation Dynamically. As shown through our extensive theoretical and empirical runtime analyses (App. G.2 and Figs. G.1 and F.2,, AWRS scales with the difficulty of constraint conformance DxL (p po), taking less time to
sample a token when the constraint is expected and more time when it is not. We analyzed the I'M-CCD results of the pattern-matchinn exact calculation of the ground truth DRz. (p po) for each token sampling step. We then ran AWRS for each of these steps, illustrating a few key results (Fig. 2).
benchmark, where token masking supports the
1. DxL (p || Po) is small in most sampling steps; AWRS typically checks only 2 or 3 tokens. As DKL (p Po) increases for the hardest cases, the runtime of AWRS scales dynamically. An interesting consequence is that AWRS samples faster for more accurate base models.
3. As DxL (p Po) grows, AWRS generally does not deteriorate. AWRS is roughly bounded by the number of non-conforming tokens whose individual probabilities are close to or exceed Z. This set is typically small, and it turns out empirically that more accurate models seem reduce the size of this set. Even when a model's 's top choice is wrong, often still prefers constraint-conforming tokens to arbitrary non-conforming tokens.
6 Related Work
One approach to accelerating constrained decoding has been to pre-compile restricted constraint classes to reduce runtime overhead. Engineering advances have enabled at least partial compilation of constraints expressible as membership in regular (Deutsch et al., 2019; Willard & Louf, 2023; Kuchnik et al., 2023) or context-free (Koo et al., 2024; Ugare et al., 2024; Dong et al., 2024) languages as well as restricted classes of Boolean circuits (Ahmed et al., 2025). In comparison, our approach supports arbitrary programmable constraints.
Another approach has explored limiting the number of constraint evaluations. Poesia al. (2022) and Ugare et al. (2025) allow the LM to proceed unrestrictedly and then backtrack on errors. Scholak et al. (2021) and Shin & Van Durme (2022) use top-k truncation within beam search. Loula et al. (2025), in a similar spirit to Morin & Bengio (2005), hierarchically stratify the vocabulary and incrementalize the constraint checker to byte sequences. A subset of the Outlines library (v.0. 2. Willard & Louf, 2023) uses a variant of deterministic probability search, first sorting tokens by their logits and then yielding the first conforming token. Botta et al. (2025) and Mündler et al. (2025) propose related variants of simple unweighted token-level rejection sampling. Our work builds on these approaches within probabilistic framework, deriving an exact sampler equivalent to token masking (ARS-LCD) alongside importance weights supporting the sound use of such samples in SMC (AWRS-SMC).
Several recent papers have used SMC to correct the greediness of LCD (Lew et al., 2023; Zhao et al., 2024; Loula et al., 2025). These approaches come with significant limitations: Zhao et al. (2024) require an expensive fine-tuning procedure for learning twists, whereas Loula et al. (2025) require constraints to be decomposable into slow and fast components,

---

Published as a conference paper at COLM 2025
the latter of which must still be evaluated over large sets of tokens. In contrast, our approach works with any constraint out of the box and evaluates it frugally, being typically more accurate than twisted SMC for any fixed runtime.
7 Conclusion
Locally constrained decoding is both slow and greedy. In this paper, we address these weaknesses respectively by introducing (i) adaptive rejection sampler requiring orders of magnitude fewer constraint evaluations, and (ii) an algorithm computing weights for transforming this local sampler into global one. Across many challenging controlled generation domains, we find that our method is faster and more accurate than existing methods, even when using fewer particles and smaller LMs. Finally, we use theoretical and empirical analyses to show that the number of constraint evaluations our method makes scales with the KL divergence between the unconstrained and constrained LM distributions-ar as consequence, our method is faster for more powerful LMs.
Reproducibility
The most up-to-date and performant AWRS-SMC reference implementation can be found in the following actively maintained library: https: com/ genlm/ her//geeemmnooooo control
The source code and data to replicate this paper's experiments can be found in the following repository: https: thub. com/ /ttp://///wsss-oommmm222222
Author Contributions
First Authors
Benjamin Lipkin (lipkinbemit. :dd):: research conception, formal analysis (algorithms, proper weighting), software development (samplers), experiment development (simula- tion, pattern matching), visualization, writing
Benjamin LeBrun (benjamin. lebrun@mail www.ueeeeemmmmll.e.... ..m.illlcc.... lead software engineer (in- frastructure, interfaces, SMC), experiment development (text-to-SQL, JSON, pattern- matching), visualization, writing
Contributors
Jacob Hoover Vigly (jahooêmit t. edu): formal analysis (runtime complexity, parameter estimator), technical advice (sampling algorithms), visualization, writing
João Loula (jloula@mit ::d):: software development (algorithm optimization), experi-
ment development (goal inference, molecular synthesis), visualization, writing
David R. MacIver (davi Slavid@rrmcciver com): experiment development (JSON) and
bounded cost extensions to AWRS.
Li Du (leoduêcs. jhu. edu): software development (grammar parsing prototype)
Jason Eisner (jason@cs. jhu. edu): technical advice (sequential inference), writing
ethz. ch): organization management, writing Vikash Mansinghka (vkm@mi t. edu): organization management
Ryan Cotterell (ryan. cotterelleinf eetz.
Senior Authors
Timothy J. O'Donnell (timothy. (timothy.odonmelleeer. odwnneel@mcgilll......11111 ca): organization management, senior
project leadership, project narrative development, writing
Alexander K. Lew (alexander. Leweyale edu): senior project leadership, research concep-
tion, formal analysis (proper weighting), project narrative development, project advising and mentorship, writing
Tim Vieira (tim.f. fiim.f.r r.vieir@@gaill.. com): senior project leadership, research conception, formal analysis (algorithms, sequential inference), software development (grammar parsing), project narrative development, project advising and mentorship, writing
10

---

Published as a conference paper at COLM 2025
Acknowledgments
BLi is supported by National Science Foundation Graduate Research Fellowship under Grant No. 2141064. JHV is supported by a National Science Foundation SBE Postdoctoral Research Fellowship under Grant No. SMA-2404644. This research was enabled in part by compute resources provided by Mila (mila.quebec).
11

---

Published as a conference paper at COLM 2025
References
Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. Controllable generation via locally constrained resampling. In International Conference on Learning Representations, (Cited on p. 2, 9, 20, 21)
2025. URL https://openreviee net www.:nnee/dfffff
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 Jau- regui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Kuang-Huel 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 can, not as I say: Grounding language in robotic affordances. arv preprint arXiv:2204.01691, 2022. URL https://arxil: org/ a2s4 01691. (Cited on p.
Afra Amini, Li Du, and Ryan Cotterell. Structured Voronoi sampling. In Advances in Neural Information Processing Systems, 2023. URL https://openreview/ http://ppeeeeiii...efffouurmeeee fwt.oo/mmfd vf77fTbgG3. (Cited on p. 20)
Zachary Ankner, Mansheej Paul, Brandon Cui, Jonathan Daniel Chang, and Prithwiraj Ammanabrolu. Critique-out-loud reward models. In Pluralistic Alignment Workshop at NeurlPS 2024, 2024. URL https://arxiv http:///aaaxiiioo///////////////
11008..1175 11791. (Cited on p. 6)
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, Jamúe Kerr, Jared Mueller, M 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-Lawtor Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac HatfieldDoodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. Constitutional AI: Harmlessness from AI feedback. arXiv preprint ar Xiv:2212.08073, 2022. URL
org/abs/2212 08073. (Cited on p. 1)
Debangshu Banerjee, Tarun Suresh, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh. CRANE: Reasoning with constrained LLM generation. ar Xiv preprint ar XrXiv:2502.09061, 2025. URL https://arxixs .rriiiioorrg/ge org/ 2502. 09061. (Cited on p. 1)
Matthew Barnett. regex, 2014. URL https: //gi thub. wtt.:/oo/mmo//e http://////mmbbbbeeeett//arrreee (Cited on p. 7, 48)
Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. Guiding LLMs the right way: Fast, non-invasive constrained generation. In International Conference Machine Learning, PP. 3658-3673, 2024. URL https://proceeddnng: mlr. pttp:ssss////////rreeeeeeeeeeeee html. (Cited on p.
G Richard Bickerton, Gaia V Paolini, Jérémy Besnard, Sorel Muresan, and Andrew Hopkins. Quantifying the chemical beauty of drugs. Nature Chemistry, 4(2)990-98 2012. URL https::/www.nattteeeee wwwp::/watteeccc. ar htr//attica aiccceescccchemm 1243. (Cited on p. 7)
Benjamin Börschinger and Mark Johnson. A particle filter algorithm for Bayesian word- segmentation. In Proceedings of the Australasian Language Technology Association Workshop, December 2011. URL https: htttps://aalantholloo.
org/U1 1-1004/. (Cited on p. 2, 20)
Edoardo Botta, Yuchen Li, Aashay Mehta, Jordan T Ash, Cyril Zhang, and Andrej Risteski. On the query complexity of verifier-assisted language generation. In ICLR 2025 Workshop on Deep Generative Model in Machine Learning: Theory, Principle and Efficacy, 2025. URL https://openrevieewneett wttprr/eeeeee.eeoooooooiioetttto (Cited on p.
12

---

Published as a conference paper at COLM 2025
Jan Buys and Phil Blunsom. A Bayesian model for generative transition-based dependency parsing. In Proceedings of the International Conference on Dependency Linguistics, 2015. URL
sttpss//aclanthooogy..rrrr
2108/. (Cited on p. 2, 20)
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers solve math word problems. arXiv preprint
(rXxio2110.14168, 2021. URL https:
14168.
(Cited on p. 6)
Marco Cognetta, David Pohl, Junyoung Lee, and Naoaki Okazaki. Pitfalls, subtleties, and techniques in automata-based subword-level constrained generation. In ICML 2025 Tokenization Workshop, 2025. URL https://openrev/ net/ foofoorrnndd-FoooeeGa (Cited on p. 2, 46)
Eldan Cohen and Christopher Beck. Empirical analysis beam search performance degra-
dation in neural sequence models. In International Conference on Machine Learning, pp. 1290- 1299, 2019. URL https://proceediing mlr. mwt..prees/v9//coeeeese / /9a/coeen99 aaannn9...ppp... pdff. (Cited on p. 4)
Daniel Deutsch, Shyam Upadhyay, and Dan Roth. A general-purpose algorithm for con- strained sequential inference. In Proceedings of the Conference on Computational Natural Language Learning, 2019. URL RRLLhttts://aalaathollo
org/oogg//////o (eorg/K19-1000 9-15/
(Cited on p.
Yixin Dong, Charlie F Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, and Tianqi Chen. XGrammar: Flexible and efficient structured generation engine for large language models. Xrv preprint arXiv:2411.15100, 2024. URL https:://aaiiii org/ org/pdf/ 2411. 15100.
(Cited on p. 2, 9, 9,6)
Li Du, Afra Amini, Lucas Torroba Hennigen, Xinyan Velocity Yu, Holden Lee, Jason Eisner, and Ryan Cotterell. Principled gradient-based MCMC for conditional sampling text. In International Conference Machine Learning, pp- 11663-11685, 2024. URL https:// poccedings.mlr... wttpppess////duuesppp procee/igggsllll..prse/2/2222222 html. (Cited on 20)
Gregory Dubbin and Phil Blunsom. Unsupervised part of speech inference with particle filters. In Proceedings of the NAACL HLT Workshop on Induction of Linguistic Structure, Montréal, QC, 2012. URL https: ////a/caaannooooo org/w12-1907, pdf. (Cited on p. 2, 20)
Gonçalo Faria and Noah A Smith. Sample, don't 't search: Rethinking test-time alignment for language models. Xiv preprint arXio:2504.03790 2025. URL hitpss///rxxtr org/ 03799. (Cited on p.
Catherine Forbes, Merran Evans, Nicholas Hastings, and Brian Peacock. Statistical Distribu- tions. John Wiley & Sons, 2011. (Cited on p.
Cameron Freer, Vikash Mansinghka, and Daniel M Roy. When are probabilis- tic programs probably computationally tractable. In NIPS Workshop on Monte Carlo Methods for Modern Applications, pp. 41, 2010. URL https://web. mit. edu/ /k//wwn//
FreerManRoy-NIPSMC. 2010 pdf. (Cited on p. 4)
Kanishk Gandhi, Denise HJ Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah Goodman. Stream of Search (SoS): Learning to search in language. In First Conference on Language Modeling, 2024. URL https://openreww// wttpe/rwwweee.eeee/deeeeeeeeeeee wwwp/ntt//dd/eee 2t112/222ji (Cited on p. 6)
Daniel Gareev, Thomas Hofmann, Ezhilmathi Krishnasamy, and Tiago Pimentel. Local and global decoding in text generation. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 14577-14597, 2024. URL findings-emnlp 854. (Cited pnp.))
www.olllooyooogg////// org/2024.
Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. cramtaa--onstrained decoding for structured NLP tasks without finetuning. In Proceedings of the Conference Empirical Methods in Natural Language Processing, 2023. URL https: httpss://aalaahhooog..oooo 2023. mailp-main... 674. pdf.. (Cited on p. 1)
13

---

Published as a conference paper at COLM 2025
Saibo Geng, Hudson Cooper, Michai Moskal, Samuel Jenkins, Julian Berman, Nathan Ranchin, Robert West, Eric Horvitz, and Harsha Nori. Generating structured outputs from language models: Benchmark and studies, 2025. URL http:::/aarvvv.orr/abbb//////// 10868. (Cited on p.
Walter R. Gilks and Pascal Wild. Adaptive rejection sampling for Gibbs sampling. Journal of the Royal Statistical Society; Series C (Applied Statistics), 41(2):337-348, 1992. (Cited on p. 4)
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with APPS. arXiv preprint arXiv:2105.099335 2021. URL / 09938. (Cited on p. 6)
https://arxtt org/pdf
Edward J. Hu, Moksh Jain, Eric Elmoznino, Younesse Kaddar, Guillaume Lajoie, Yoshua Bengio, and Nikolay Malkin. Amortizing intractable inference in large language models. In International Conference on Learning Representations, 2024. URL https: //tp://eeee.....e///// net/pdffii==ujjp4ccc (Cited on 2,
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 Infor- mation Processing Systems, 2024. URL https: htttopp://pooceedinggss nerpeps.ccpcppppppppr sfiles/ http:///8/.aaatttteeee/////66e12
pdf. (Cited
on p. 1)
Tom Kempton and Stuart Burrell. Local normalization distortion and the thermodynamic for- malism of decoding strategies for large language models. arXiv preprint arXiv:2503.21999, 2025. URL https: /aaxxiv wtg/pdf 2503. 219299,199 (Cited p. 2)
Philipp Koehn and Rebecca Knowles. Six challenges for neural machine translation. In Proceedings of the First Workshop Neural Machine Translation, PP- 28-39, 2017. URL https:///ccannthologs wtt.eaanooooooooooooooo.. Mrrg/W1733288 pdf. (Cited on p. 4)
Terry Koo, Frederick Liu, and Luheng He. Automata-based constraints for language model decoding. In Conference on Language Modeling, 2024. URL https://openrevieww net/
forum??d-80Bddllyyy2 (Cited on p. 2, 2)
Ben Krause, Akhilesh Deepak Gotmare, Bryan McCann, Nitish Shirish Keskar, Shafiq Joty, Richard Socher, and Nazneen Fatema Rajani. GeDi: Generative discriminator guided sequence generation. In Findings of the Association for Compulational Linguistics: EMNLP 2021, pp. 4929 4952, 2021. URL. https: /aclanthoooy org/2021 undings-emnla 424. pdf. (Cited on p. 2, 20)
Michael Kuchnik, Virginia Smith, and George Amvrosiadis. Validating large language models with RELM. Proceedings of Machine Learning and Systems, 5, 2023. URL https://proceedingg .aapinnggs..lllss........ mlsys. www.ooggppppeeeee http/appr__fiiii ffles/iil//pl/eeeeeeee wwwes//pppe//////// paper/2823/file) pdf. (Cited on 2.
Dieterich Lawson, Allan Raventós, Andrew Warrington, and Scott Linderman. SIY'O: Smoothing inference with twisted objectives. Advances in Neural Information Processing Systems, pp. 38844-38858, 2022. URL https: httttp::/pproceeddnggg neurips. cc/paper_fill malee_files/
oataarrrr000..fccccoa22222aaaaar p.
(Cited
Roger Levy. Expectation-based syntactic comprehension. Cognition, 106(3):1126-1177,22 2008.
URL https:://oii.org///// www.///oo.ooiiiiionoooooo 2007.00.200 .0..00000000.. 006. (Cited on p. 4)
Alexander K. Lew, Marco Cusumano-Townee, and Vikash K. Mansinghka. Recursive Monte Carlo and variational inference with auxiliary variables. In Uncertainty in Artificial Intelligence, pp. 1096,110,, 2022. URL https://prooceeding http:iiinnnnmm....sss//eee Tatsss//v8//eew222 lew22a. pdf. (Cited on p. 26)
14

---

Published as a conference paper at COLM 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 2023 Workshop: Sampling and Optimization in Discrete Space, 2023. URL https://openrevvew.
htt/pddfddd-u1KKQxxxx (Cited on p. 2, 3, 9, 20, 21)
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In International Conference on Learning Representations, 2023. URL https://openreview.
net/pdffidd=v8LepNEEE (Cited on p.
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 hps: //aclanthology. org//18- 1085// (Cited on p. 2, 20)
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, Alex Lew, Tim Vieira, and Tim O'Donnell. Syntactic and semantic control of large language models via sequential Monte Carlo. In International Conference Learning Representations, 2025. URL https: /ttp///epppeeeeeee//eeeeeeeeeeee net
(Cited on p. 2, 7, 9, 20, 23, 49)
Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. NeuroLogic Decoding: (un)supervised neural text generation with predicate logic constraints. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Techmologies, pp. 4288 (888,,299,,0 2021. URL www.ttts//acllathllllote/ . org/ /wwgg/2211.../ maacl-mainn 339. 339.pdf. (Cited on p. 1)
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ro- nan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah Smith, and Yejin Choi. NeuroLogic A+ Ateqque decoding: Constrained text generation with lookahead heuris- tics. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 780-799, 2022. URL org/2022 naacl-main, 57 37.pdf. (Cited on p.
Scott Lundberg, Marco Ribeiro, Richard Edgar, and Harsha Nori. Guidance: a guid- ance language for controlling large language models. 2024. URL t/gitbb. com/ guidance-ate waapenceeaaiggiicee ai/guidance. (Cited on p. 46)
Vikash Mansinghka, Daniel Roy, Eric Jonas, and Joshua Tenenbaum. Exact and approximate sampling by systematic stochastic search. In Artificial Intelligence and Statistics, pp. 400-407, 2009. URL https: http:///poeeeen...eeeec mlr http:eeeeiini..l..prree///////aa /ar. html. (Cited on p. 4)
Megalng. interegular, 2019. URL https:///itthui http:///ttttttoooo//gg/gg/////tt (Cited on 48)
Tao Meng, Sidi Lu, Nanyun Peng, and Kai-Wei Chang. Controllable text generation with neurally-decomposed oracle. Advances in Neural Information Processing Systems, pp. 28125-28139, 2022. URL https: h/proeeed/s//oeeeenn/s/... neurips. cc/ paper loaper_fille wwl.fflllpppppe pttes//pppr//222//
pdf. (Cited on p. 2, 20)
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: hatp::///clanhhloggy
org/2020.acl- acl-minn. 314/. (Cited on p. 2, 20)
Frederic Morin and Yoshua Bengio. Hierarchical probabilistic neural network language model. In International workshop on artificial intelligence and statistics, pp. 246-252, 2005. URL https::/
prwss/ /ttpss/////mmrrrn/mm//mnnnnnnn pdf.. (Cited on mmp.9
Michal Moskal, Madan Musuvathi, and Emre Kıeman. AI Controller Interface. https:
//gi thub. httbb///mm/mmccoosttaacccc////// 2024. (Cited on p.
15

---

Published as a conference paper at COLM 2025
Niels Mündler, Jingxuan He, Hao Wang, Koushik Sen, Dawn Song, and Martin Vechev. Type-constrained code generation with language models. arXio preprint ar Xii::2504.092446 2025. URL https: / /arxiv. org/pdf 2204. 09246. (Cited onp. p. 9)
Kenton Murray and David Chiang. Correcting length bias in neural machine translation. In Proceedings of the Third Conference on Machine Translation: Research Papers, pp. 212-223, 2018. URL https: /aclaaaoooonooy.o... org/W13 8 6.-..32...p.... pdff. (Cited on p. 4)
Christian Naesseth, Fredrik Lindsten, and Thomas Schon. Nested sequential Monte Carlo methods. In International Conference Machine Learning, Pp. 1292-1301, 2015. URL https://proceedingg wttp:nnssmmmr..resssseeee wtt..pees///33/naeeeeeeee
html. (Cited on p.4)
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/2000000
URL
https://doi. /rgorrg////// /0rrg/10..0 10. 1561/2200000744 (Cited on p. 4,
Reichhrro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher 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: srowser-assisted question-answering with human feedback. Xrviv preprint arXir:2112.00980 2021. on p. 6)
URL https::/arxiv.oot hdtpppdf/1111 /2112. 09332. (Cited
Noel O'Boyle. partialsmiles: A validating SMILES parser, with support for incomplete http:///olllaaccaaaaaaaaalaaaa SMILES, 2024. URL /tt.a/////ttt/////ttttaooooooaaa
(Cited on p. 7)
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 logic provers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2023. URL http::://aclantholoog.oooooo org/2023. emnlp- main. 313/. (Cited on p. 6)
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 instruc- tions with human feedback. In Advances in Neural Information Processing Systems, pp- 27730-27744, 2022. URL htttp:://proceeddngggn nwwrips. ips. cc/ paper cc/paper sfillslllls__leeeee Latles/ppper////e paper/20221
pdf. (Cited on p. 1)
Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D' A'Atoni.. Grammar-aligned decoding. Advances in Neural Information Processing Systems, pp. 24547-24568, 2024. URL https://proceeedings neurips cc/paper filles/aperr/222 htt.://caae....eeeeaaaaaaaaaaaaa
pdf. (Cited on p. 2, 20, 21)
Kanghee Park, Timothy Zhou, and Loris D'Antoni. Flexible and efficient grammar- constrained decoding. In International Conference Machine Learning, 2025. URL (Cited on p.
/tt.///255/psstrr/55555 http:://icll.ccciicuuaa//////// https://icml..c///
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:// wtt.:n//oooommmddddtttt////
(Cited p. 1,9)
Isha Puri, Shivchander Sudalairaj, Guangxuan Xu, Kai Xu, and Akash Srivastava. A probabilistic inference approach to inference-time scaling of LLMs using particle-based Monte Carlo methods, Xiv preprint arXiv:2502.01611 2025. URL https://arxiv.orr pdf/2502. 01618. (Cited on 2)
Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. COLD decoding: Energy-based constrained text generation with Langevin dynamics. Advances in Neural Information Processing Systems, pp. 9538-9551, 2022. URL https::/ppooceeennggs.... neurips cc/paper_ pdf.
fttpe//ppweeeeeeeeeeeeeeedeedeee (Cited on p. 2, 20)
16

---

Published as a conference paper at COLM 2025
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning, Stefano Er- mon, and Chelsea Finn. Direct preference optimization: Your language model is se- cretly reward model. Adounces in Neural Information Processing Systems, pp. 53728- 53741, 2023. URL 158565666647744450226666677---02
neur wwwpp.pprrrrr..ppppppppppppp..ep saaper_files, tttee//appr/222/fiille
.df. (Cited on p. p.
Ronald Rosenfeld, Stanley Chen, and Xiaojin Zhu. Whole-sentence exponential lan- guage models: A vehicle for linguistic-stattittiaal integration. Computer Speech & Lan- guage, 15, 01 2001. URL https://wwl www.secieeeeeectcccccco wtw.c//drreetttcccoccccccc//araa 508852308009015599 (Cited p. 20)
abs/pii/
Subhro Roy, Samuel Thomson, Tongfei Chen, Richard Shin, Adam Pauls, Jason Eisner, and Benjamin Van Durme. BenchCLAMP: A benchmark for evaluating language mod- els on syntactic and semantic parsing. In Advances in Neural Information Processing Systems, 2024. URL https://proceediin/ neur ips peurips.cc/paper... soarrrfilesppppe cctppppr_filee//prrreeeeeeeeeee ptteee//pppe//22//1/1/
9c1535aa2ffcce074433333333 4d91 1119910597-PP0 Paweeesaee----aaaaeteeeeee Baaaaasttts_an__Benaaaaarreee Benchnarks......... pdf. (Cited on p. 7)
Lars Ruddigkeit, Ruud Van Deursen, Lorenz C. Blum, and Jean-Louis Reymond. Enu- meration of 166 billion organic small molecules in the chemical universe database GDB-17. Journal of chemical information and modeling, 52(11):28864 2875, 2012. URL https://pubs. http:////ubssaas....ooooo acs. org/ ort..o/////////////// 111110..1111111 1021/ci30041 5d. (Cited on p. 7)
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incre- mentally for constrained auto-regressive decoding from language models. In Proceed- ings of the Conference Empirical Methods in Natural Language Processing, 2021. URL emnlp-main. 39/. (Cited on p. 1,9)
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I. Wang. Natural language to code translation with execution. In Proceedings of the Conference on Empiri- cal Methods in Natural Language Processing, 2022. URL https: htttp://accaathoooggy www.llooo.ooogo/goeoe org/2022. emnlp-maiie 231/. (Cited on p. 6)
Andy Shih, Dorsa Sadigh, and Stefano Ermon. Long horizon temperature scaling, In Interna- tional Conference on Machine Learning, pp. 31422-31434, 2023. URL https://proceediingg mlr.press/
pdf. (Cited on p. 2)
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 https:
l/aclanthology. .arasy..orr. org/2022 www.naalllmmaa. maallmmmannnmmm 396/. (Cited on p. 1,
Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil An- tonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Con- strained language models yield few-shot semantic parsers. In Proceedings of the Conference Empirical Methods in Natural Language Processing, 2021. URL https://aclanttollo org/2021. emnnl- main. 608/ (Cited on p.
Felix Stahlberg and Bill Byrne. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLP- IJCNLP), pp. 3356-3362, 2019. URL htttps://aclantholll www.oogg//// 11311131111111111111111111111111 pdf.. (Cited on p. 4)
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, pp. 3008- 3021, 2020. URL https::/proceeedingg neurips. (1888555550999006556444488555-54 Paapee .df.. (Cited on p.1)
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Trina Higgins. Solving math word problems
17

---

Published as a conference paper at COLM 2025
with process-and outcome-based feedback. arXiv preprint arXio:2211.142773 2022. URL
https://arxiv.orgg 2211 14275. (Cited on 6)
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: //ri://///xivvvv/. wwciii.og///oee org/pdf/2403. 01632. (Cited on 1, 2,9)
Shubham Ugare, Rohan Gumaste, Tarun Suresh, Gagandeep Singh, and Sasa Misailovic. IterGen: lttrative structured LLM generation. In International Conference on Learning Representations, 2025. URL
(Cited on p. 9)
Tim 2014.
Gumbel-max trick and weighted reservoir sampling, URL http://timvieira.cc git..b.................. wwtblog/post////////////// post/2014/08//// Humbel-max-tricen htw.:a/eeo.ooo.ooiiiiieeeeeeeeer
Vieira.
(Cited on p. 42)
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. In Advances in Neural Information Processing Systems, 2024a. URL https: htttt::///penreview..tt net/ (Cited on 1)
dorum?id=B4tkwuzeen wttp:e/eewkkueeatetnccaaaa..... Yww.teeeddddaoooe122222
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-Shepherd: Verify and reinforce LLMs step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9426-9439, 2024b. URL acg/2024.acl112a 510. 510.pdf. (Cited on p.
David Weininger. SMILES, a chemical language and information system. 1. introduction to methodology and encoding rules. Journal of chemical information and computer sciences, 28 (1):31-36, 1988. (Cited on p.
Brandon T Willard and Rémi Louf. Efficient guided generation for large language models. arXiv preprint orXiv:2307.09703 2023. URL https: httptpps//arxxi.or///a////////// 09702. (Cited on p. 2, 9, 46)
Huajian Xin, Daya Guo, Zhihong Shao, Zhizhou Ren, Qihao Zhu, Bo Liu, Chong Ruan, Wenda Li, and Xiaodan Liang. "Deepseek-roove Advancing theorem proving in LLMs through large-scale synthetic data. arXiv preprint arXiv:2405.14333 2024. URL https: //arxiv. hatlv.org//pff.. hppd////5... 14333. (Cited on p. 6)
Kevin Yang and Dan Klein. FUDGE: Controlled text generation with future discrim-
inators. In Proceedings of the Conference of the North American Chapler of the Associ- ation for Computational Linguistics: Human Language Technologies, 2021. URL https: //aclanthology org/2021 naacl-main. 276/ (Cited on p. 2, 20)
Yi Yang and Jacob Eisenstein. A log-lineat model for unsupervised text normalization. In Proceedings of the Conference Empirical Methods in Natural Language Processing, 2013. URL
https://aclantthol// hww.t/hhooogooooo//111 org/ --
(Cited on p. 2, 20)
Haotian Ye, Himanshu Jain, Chong You, Ananda Theertha Suresh, Haowei Lin, James Zou, and Felix Yu. Efficient and asymptotically unbiased constrained decoding for large language models. Xiv preprint ar Xix::25504.09135 2025. URL https: //axxiv. wwwpxxvv..og/page org/pdf 2504. 09135. (Cited on onp.2. 2)
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 human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQI. task. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2018 URL https: / aclanthologyyy...oo www.hollgg.oggggDeeo.oe 11-DDD111111 1425. (Cited on p. 7)
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In International Conference on Machine Learning, pp. 40932-40944 2023.
h/tp://ed///occceeeeeeeee mlr. pwwss/
.ddf. w /ttp://////aan////g///
(Cited on p. 2, 20)
18

---

Lunjun Zhang, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. Generative verifiers: Reward modeling as next-token prediction. In The 4th Workshop on Mathematical Reasoning and AT NeurlPS 24, 2024b. URI. http:ttt////peereeeee htt/pddfid==CHHooTO Published as a conference paper at COLM 2025
Honghua Zhang, Po-Nien Kung, Masahiro Yoshida, Guy Van den Broeck, and Nanyun Peng. Adaptable logical control for large language models. Adounces in Neural Information Process- ing Systemss, pp. 115563-115587, 2024a. URL https::/procceedingg neurnngg...errriee neurips cc/paper- hatpa///aaaaaaaaffaaaaaaaaaaaaea
pdf.
(Cited on p- 2)
(Cited on p. 6)
Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse. Probabilistic inference in language models via twisted sequential Monte Carlo. In International Confer- 2024. URL http::://procceeddggg.nmt
Machine Learning, pp- 60704-60135 v235/zha024c. html. (Cited on p- 2, 2, 20)
wwwpinnss.......seeeee..e press/
Lianmin Zheng, Liangsheng Yin, Zhigiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph É. Gonzalez, Clark Barrett, and Ying Sheng. SGLang: Efficient execution of structured language model programs. In Advances in Neural Information Processing Systems, 2024. URL https: /opps/////eeeeeeee/eeee net/forum?id= VqkAKQibpq. (Cited on p.
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 pref- erences. arXiv preprint arXiv:1909.008 08593, 2019. URL https: //arxiv. org/pdf/ /1999 08593. (Cited on p. 1)
Max Zuo, Francisco Piedrahita Velez, Xiaochen Li, Michael L. Littman, and Stephen H. Bach. Planetarium: A rigorous benchmark for translating text to structured planning languages. ar Xiv preprint 2002::2200003311,,, 2024. URL https: / http///axvvvvv//// wwwrxivooor/ppdeo orggpdff /2477 03321. (Cited on p. 7)
19

---

Published as a conference paper at COLM 2025
A Conditional Language Modeling
Strings. An alphabet X' is a finite set of symbols. Let X' denote the set of all strings formed from the symbols in X. Let e denote the empty string. Let x denote the length of E X
We also define & X as special end-of-string marker.
Constraints. Let x + {0,1} be constraint function, encoding set of valid strings L X Let Z (x xx' EC, i.e. the of all valid prefixes of strings in L. We define the incremental constraint function:
{ IxEC
ifx'=
[e(x') x)
(3)
1 IxrEZ
otherwise
Language models. A language model Po a probability distribution over X The prefix probability (x) is the probability that a string drawn from Po has as prefix:
Px(x) del Σ Po(xx')
(4)
XEX
The conditional prefix probability is the probability that a string drawn from Po has the prefix xx' given that it already has the prefix for any strings x, X
Po(xx') and Po x) Po(x)/ Pb(x) Px(x)
Fo
x))
(5)
Then, the probability of x may be factorized as
Po(x) = [ x)
Po(x: |xx)
(6)
Global conditioning. We build recent work defining constrained generation proba- bilistic conditioning (e.g., Börschinger & Johnson, 2011; Dubbin & Blunsom, 2012; Yang & Eisenstein, 2013; Buys & Blunsom, 2015; Lin & Eisner, 2018; Miao et al., 2020; Krause al., 2021; Yang & Klein, 2021; Meng et al., 2022; Qin et al., 2022; Zhang et al., 2023; Amini et al., 2023; Hu et al., 2024; Lew al., 2023; Du et al., 2024; Zhao et al., 2024; Park et al., 2024; Ahmed et al., 2025; Loula et al., 2025). In particular, we define the posterior distribution P(x) of language model prior x Po subject to the condition 1 (x)x,, as
p(x) def
P(x) G
P(x) del Lo(x)
G def Σ P(x)
XEX
For to a well-defined probability distribution, we require G - Pry P [x)] > 0. In other words, there must be way to generate constraint-conforming string from Po, and G tells us the probability of this event. Note that
P(x)
X x X X-PP
Pr
(8)
Probabilistic conditioning is an enticing method for conditional generation as it is the only method that preserves the relative probabilities of all events that satisfy the condition.
Note that is a language model, so has conditional prefix probabilities P. Unfortunately, however, G and the conditional prefix probabilities are generally intractable to compute exactly as they involve intractable sums over all x E X' (Rosenfeld et al., 2001). This makes ancestral sampling, i.e., left-to-right sampling from the conditional prefix probability distri- bution, infeasible. In what follows, we will develop methods for (approximate) sampling from P.
20

---

Published as a conference paper at COLM 2025
(Sequence-level) Rejection sampling. The most straightforward algorithm for sampling from P is rejection sampling. Note that this the intention of sample-verify methods:
1 def rejection_samplingo>>>
while True:
3
x Po # sample complete string from the prior
if cx(xx: # only return the string if the condi tion is satisfied
5
return x
Rejection sampling has an expected runtime of ((1/G) per sample. So it is only practical in this setting when G = 1.
Locally constrained decoding. Locally constrained decoding (typically performed through token masking) defines a language model l that attempts to approximate P by approximat- ing P with E(x'
x) 2s P(x' x) where
xx) def Po(x' x)Tx(x') xx) and L(x) def L(x)
7(x'
Po(x' xx)[(xx) |x)
(9)
Prior work (e.g,, Lew et al., 2023; Park et al., 2024; Ahmed et al., 2025) has shown that this local approximation can be very different (i.e., biased) from in both theory and practice. Fortunately, it is possible to improve this approximation (i.e., overcome this bias) with additional computation using the techniques that we describe next.
Explanation for why locally constrained decoding is biased. Although é is an effective method for generating strings x ~ E that satisfy 1 (x), it has tendency to over-represent certain strings. We can quantify this through the string's relative probability
p(x) del P(x)
1 1o(x)
xx +1
L(xat)
(10)
((x)
G
((x)
E=
because
P(x) Po(x)1c(x) G
1 -1
and ((x)
(11)
x L(x²))
In other words, we compare samples from the local distribution to their relative proba- bility in the global distribution P, the string x will appear at rate of p(x) more if p(x) < 1 or less p(x) than should.
In this work, L(x)= < 1 for all x.
In the expression for pxx), we see the factor that actually depends on the string x independent of G, which is fortunate for us as we cannot efficiently compute G. Let w(x) Gp(x)
x|+1 L(xxr).
Clearly, 11 |x|+1
L(xx;) is an important diagnostic for sample quality. Operationally, when sampling from E, the cumulative product of local L's is a useful signal for detecting low-quality samples.
Interestingly, the average weight is equal to G, ie,, Ex-e [TI L(xxt) = G.
Although the expression for the bias does not care about the ordering, it's hard not to think about the operational view of ancestral sampling from E; in this view, the sample is created from left to right by sampling from the conditional token distributions. We say that our specific sample distorted by the product of its local normalization constants. This quantity measures how much the constraints affected the sample. the constraints only rule out very low (or even zero) probability tokens, then the distortion will be small as L will be x 1.
This operational view motivates the use of sequential Monte Carlo (SMC). In the case of SMC, we compare samples of complete and incomplete strings of length and resample
21

---

Published as a conference paper at COLM 2025
those that appear to be on track, ie., favoring those that have higher intermediate weight values. Thus, if a particle was favored initially by the proposal distribution, may be evicted later in favor of replica of higher-weight particle.
Below is a simple example illustrating global conditioning, which can be used illustrate the difference with respect to local conditioning.
Example 1. Suppose that X' {a, b), the language of valid strings is L {aa, ba), and the probability distribution is encoded in the following probability tree, which annotated with the valid and invalid strings:
a/0.01
aa /
a/0.9
b/0.99
b
by0.1
a/0.99
ba V
b/0.01
bb
Under the original distribution, we have
p(aa) = .01 .01 0.009
p(ab) = .99 0.891
p a) = 1 .99 0.099
pbb = 1 0.001
The globally conditioned distribution is
((a .083333
P(ba) -916667
This example illustrates a local reversal: under the original distribution Po. the first symbol is a in .9 of cases, and is the first symbol in .1 cases. However, after conditioning, the case that made a so common (i.e., ab) is disallowed. And, less importantly, a ninor case for b is disallowed. This makes the globally conditioned conditional prefix probability:
P(a E) 0.009 .099 .083333
0.009
P(b 0.009+009
0.099
-916667
which is dramatic reversal from .9 and 1, respectively.
Importance sampling. In our setting, importance sampling is a simple sampling-based approximate inference technique that can be used to extend locally constrained data with
a weight correction. The weight correction allows us to overcome the bias in 7 P with additional computation, i.e,, taking more samples. Given computational budget of M > samples, the importance sampling procedure works as follows:
1. Sample from the locally constrained distribution: x11), (MM) (M) iid. distribution such as 9 = l.
where & is a proposal
Compute weights for each m: (m)) Po(x(mi) g(xlm))
For the special case of 9 l, the weight
simplifies to (m) - [2/)|| [+1 L(x<()-
22

---

Published as a conference paper at COLM 2025
3. Define estimates:
G
del
M Σ IN
w())
P(x)
def 1
Σ 11
M
w(m)
I (m)
P(x) del
P(x)
M
M
&
4. Return a sample from the posterior estimate P.
Example 2 (Example 1, continued). Returning to the above example, in this case, importance sampling with the locally conditioned distribution as proposal generates
((aa) .9 with weight L(a)- L(aa) = 11.001 = =01
E(b a) .1 with weight L(b)- L(b a) 1- 199- =99
Thus, the importance-uwiighted distribution estimate is
P(aa) .01-9
01.99.1.99 .083333
P(ba)
9+.1 .916667
.0-99+1-999
which is precisely the global distribution.
SMC is an extension importance sampling, which effectively applies importance sampling to sequence of intermediate target distributions chosen to keep partial generations on track rather than once for the entire sequence.
Sequential Monte Carlo.
We define intermediate twist function (also referred to shaping function) :p: X R20, which is the key to providing partially generated strings intermediate feedback. Complete strings, on the other hand, will be judged by In this work, we use (xx) Px(x) [xx), but we will discuss alternatives shortly. In our incarnation of the SMC algorithm, both complete and incomplete strings will evolve through time-indexed state space where, at time f, the state contains two variables: string of length < f, a Boolean indicating if the string is active (incomplete). When the string is active, its length restricted to equal f. Once the string has been completed, it is never changed, i.e., no symbols can be appended to
We define the initial target as
xo del
La=Tx=E
(12a)
which says that initially, the only possible state is (T, i.e., active and equal to the empty string. We define the intermediate targets ni (for > 0) as
(a,x)) [x(x)
[incomplete]
(12b)
+ P((x) |
[complete; length < f]
Note that as t + 00, π. (T, converges to P.
In this work, we use (xx) T((x) as our shaping function as in (Loula et al., 2025). Under this choice of intermediate target, the constraint checker ensures that we always have at least one valid complete of the string prefix x. This feedback is useful for detecting rejection soon as the string guaranteed fail, and it is useful for detecting cases where a lot of the probability mass from the prior has been eliminated (i.e., we are likely to have low-weight particle in the sense of importance sampling). In relation to P, it provides
A complete string requires [x] 1 steps be generated due to the final event. This is why m has complete strings of length- < f, rather than (say) S
12 A guiding principle for designing & is approximate q P. However, any choice of き that satisfies the technical condition (xx) 0 P(x) 0 will converge (albeit with different rates). Note that + P, the SMC algorithm is exact sampler for P. Unfortunately, computing á exactly is typically intractable,
must approximate it.
23

---

Published as a conference paper at COLM 2025
sufficient condition for when ((x) O. It, however, does not provide much information beyond that. We define the shorthand
P(x) ((x) *(x))
=f
(x
x) def
(13)
((xxx))
otherwise
Importantly, this definition gives the following factorization of P, vx E X
P(x) (-))(()))))))))) x)
I (xx
xx()
(14)
straightforward to verify that the shaped weights of complete strings are equivalent to those used in importance sampling:
P(x)
(
x)
(x+x
x(t)
(({))
(15)
(xx)
7(m
x
(xt
xxct)
We provide pseudocode for the SMC procedure in Alg.
Algorithm Sequential Monte Carlo
procedure SMC(q, &,,M T, for 1... M
M number samples
3. (x(("), w(()), al!n)) <- (e, (e(), true)
while 3m E 1.. M: a (m))
5. for
M x(m);
>incomplete particles
x' q(: (())
7.
if x'
pComplete particle
(m) false
8.
9.
else
x (m) + (m)) o x
10
mlm) + (m)) ((x(x/
11.
(x((),, wol) a(1)) RESAMPLE(X!), (a))),)),))
G + M 2m=1 (m))
14. P(x) - 1
M IM (o(m)
( xx=
15. P(x) P(x)
G
return PG,
17. procedure RESAMPLE(x wo(),a))) T)
W + M m())
M + w IM (2)
EEffective sample size D-Resample if needed b Temporary copy
20. if MM- < <TM::
x < x(:); w-t-) +- n
21.
for = 1.. M:
R N~ Categorical( w (wo(1) w(M))) (x((m), zo(m)) amm)) (x(R), W/ W/M,a (R)
return (x()), wol)) al))
Note that it is ok from the perspective of the technical conditions for (x(x) to have false positives (i.e., strings that are considered ok, that not); however, false negatives are prohibited.
24

---

Published as a conference paper at COLM 2025
SMC extension for properly weighted token proposals. Our method uses extension of Alg. that allows for a properly weighted proposal distribution (See App. B for a more detailed discussion of proper weighting). More specifically, the token proposals will now be a pair of a token and a weight, i.e., (x',w)) g(- xx(")). The requirement that token proposal distribution is properly weighted with respect to the intermediate target:
(xx') x)))).. While still yielding sound inference, the use of approximate proposals does admit additional variance. We provide several methods for defining these kinds of proposal distributions ($3). Pseudocode for the extended method is provided in Alg. 2.
Algorithm 2 Sequential Monte Carlo with Properly Weighted Proposal
procedure SMC-PWP(Q, 6, M, r)
2. for = 1.. :::
b number of samples
3. (.(m),wllm) (a(n)) &- (e, (e)), true)
4. while 3m E 1.. M: (
5.
for m = 1... M s.t. alm)
Dincomplete particles
(x',w') w/) ~ 9( x!!!))
6.
2.
if = =0:
D-Complete particle
a (m)) + false
8.
else
x(m] (m)) ox
wllm) f (n). w
11.
(x()) (o 2) - RESAMPLE(x() (,,)), ,0))),a(),)
12.
G
M = (m())
M
13.
P(x)= + M Lm wo(m) (x==((1)
11.
P(x)= P(x)
return PG,P,P)
16.
25

---

Published as a conference paper at COLM 2025
B Recursive Auxiliary-Variable Inference (RAVI)
Importance sampling is an approach to approximate sampling from an unnormalized target distribution p, with normalizing constant Z, through a proposal distribution q whose support is at least that of p. We would like to design with favorable properties towards our downstream goal, e.g,, efficient runtime. Crucially, this design of strong proposal distribution is often mediated by auxiliary random choices such that sample (x, 9.
When this is the case, is necessary to calculate a weight (xx,r) to correct for r.
RAVI (Lew et al., 2022) gives of relatively arbitrary choices of 9. Within RAVI, we may work with any unnormalized target distribution p over any space X. Let (x, w) Q denote the process of sampling from a proposal and calculating its weight w. We are interested in developing Q with the following property:
generalized, flexible recipe for deriving the weights
Definition 3. The proposal distribution Q is properly weighted if:
E (x
[ f(x)]
Z E x~p [f(x]]
(16)
Note that by taking trivial f(x) = 1, this property implies (x Z. Leveraging this identity, each estimator 2 in the main text is approximated via the weight w of a properly weighted proposal distribution. For notational consistency with the literature on proper weighting, w will be used as opposed to 2 throughout the appendix.
B.1 The Proposal
RAVI proposal is a joint distribution q(,, x)) over a product space R x X, where R holds auxiliary random choices made by the proposal. Typically, proposals will be designed to make the marginal (x) good approximation to the target p(x).
In this work, consider exclusively exact proposals, where (x) p(x). This is achieved via various formulations of rejection sampling, where represents the auxiliary randomness generated by the rejection sampler. Because (xx) Ercr (1, ) is typically intractable to
evaluate exactly, the usual importance weight w p(x) cannot be computed directly. RAVI
q(x)
provides way to tractably compute a (noisy) importance weight that still satisfies proper weighting.
B.2 The Meta-Proposal
A RAVI meta-proposal h((;x)) is designed infer r given x. The optimal meta-proposal would be q(r]x) def (xxx), but this optimal choice is often not tractable. In practice, we select a family of probability distributions h(r;x) over R, indexed by X, with the
appropriate support, in order to define an 'extended' target (r,)(r, _ ((x)h(r;x) over the joint space. Formally, require that 5h << 14 For given x, this means that should, with probability 1, propose some r such that qr, > O.
B.3 Properly Weighted Sampling
Definition 4. We define 1-level RAVI sampling (cf. 2-level RAVI sampling in Def. 5) from a proposal 9 and meta- propppl h as follows:
1. Generate (r, ~ Evaluate w del h(rx)
q(xxx)
Return (x,w). w).
14For μ, two distributions the same domain, h is said to be absolutely continuous (AC) with respect to (written μ v) if and only μ zero anywhere that v is zero.
26

---

Published as a conference paper at COLM 2025
This can be seen standard importance sampling on the extended state space R x X. The weighted value (f,,x), w) is properly weighted for the extended target p(x) h(r;x), which means that the weighted value (x, is properly weighted for the re-marginalized target p(x). When h(r;x) performs "perfect meta-inference; i.e, when h((;;) = q(r)x),
then w p(x) k(rx) g(x) p(x)
(()xx)(()) q(x)" meaning we compute exact importance weights.
(((x)
Otherwise, the importance weights will be noisier but will still have the same expected p(x),
value (that is, E/w x] q(x) consequently we also have E E[w] (xx))~
p(xx Z).
((x)
Proposition 5. Given proposal x(),x) and meta-propoun h(r;x), such that ph < 9, Def. 4 is properly weighted for p.
Proof.
h(xx)((;x))
E QI-RAVI
[xx]]]
E
f(x)
[Def. 4]
(17a)
q(r,x)
(rx)ma
p(x) p(x)h((ix) f(x)
Σ E x(1xx)
Deef. of expeecaation]
(17b)
q(r,x)
TRRE
Σ E p(x) h((;)) f(x)
[Cancellation; AC]
(17c)
TERXEX
F(x) Σ h(r;))
[Rearranging]
(17d)
XCX
TR
Fxx))((x
[h(,;x) is distribution]
(17e)
XEX
E Z (xxxf((x)
(Def. of pl
(17f)
XEX
Z E f(x)
[Rearranging]
(17g)
xEX
Z xmp
[f(x)]
[Def. of expectation)
(17h)
B.4 Deeper Recursive Inference
If our meta-inference Ji itself introduces auxiliary variables s E S (so we have rx)), then can repeat this process, adding meta-meta- teta-mmta-proposal j(s; x) that aims to approximate htss 1;x). Our properly weighted algorithm then becomes:
Definition 5. We define 2-level RAVI sampling from a proposal 9, meta- h, and meta-mela- proposal as follows:
1. Generate (r,x) ~ q and s ~ f(rr,xx). Evaluate w del h(x)a()))a))
Return (x,
Intuitively, since h "overextended" the target distribution to include not just r but also s, must now extend the proposal with a distribution over s. In general, we can continue this process (e.g., if has auxiliary variables), alternately extending the model and proposal until we reach an extension that does not introduce new auxiliary variables.
Proposition& 6. Given a proposal q(,, x), meta prepa-proposal hiss, x), and meta-meta propposl j(s;r,)), such that ph < q.. Def. 5 is properly weighted for p.
27

---

Published as a conference paper at COLM 2025
Proof.
E (xra0)~Qaa -D-RAV
[w0 fx))
p(x) f(x)
IB (rx))-a--i(
IDef. 5]
(18a)
((r,,))((str))
p(x) h(,,,,)
ΣED E j((TT)
((;,,) f(x)
IDef. of expectation
(18b)
XERXEX
Σ
E
f(x)
[Cancellation; ACI
(18c)
XEX
E f(x) f(x)
E E h(,,
[Rearranging]
(18d)
XEX
rERSES
[xxx
E h(rxx)
[Marginalize over s]
(18e)
XEX
FER
F())
[h(;;) a distribution]
(18f)
NEY
= Σ Zp(x) f(x)
[Def. of pl
(18g)
NEA
Σ p(x)
[Rearranging]
(18h)
TEX
Z E [f())
Def. of expectation!
(18i)
x-p
B.5 RAVI Intuitions for Def. (WRS)
In the context of the RAVI framework, WRS be understood representing the rejected samples as auxiliary variables generated during the sampling process. The auxiliary space R = t' consists of finite lists of rejected samples. The proposal generates trace of rejection sampling, while the meta-proposal lt generates additional rejection loops to improve our inference of the auxiliary variables. Finally, meta-meta-propont accounts for the additional auxiliary variables introduced by ht
Intuitively, as L increases, we obtain better estimate of the acceptance probability Z, leading to lower variance in our importance weights. In the limit as -> co, meta-oooposal xr;;x) converges to its optimal distribution q x) and the meta-meta-proposal j(,;r,x) converges to its optimal distribution h[s x)x).
B.6 RAVI Intuitions for Def. 2 (AWRS)
In the context of the RAVI framework, AWRS represents modification where the sampling procedures in the proposal, meta-proposal, and meta-meta-propost all maintain memory of previously rejected samples. The sampling distributions are continually renormalized after each rejection to account for the removed probability mass. This adaptation requires a different weight calculation that accounts for the changing probability distributions throughout the sampling process.
28

---

Published as a conference paper at COLM 2025
C Proofs for $3.1 (WRS)
Proposition 1. For (x, 2.) ~ QwRs, x is distributed according to and [[|] = Z.
(App. C)
Recall Ž w, where w is the weight of a properly weighted proposal distribution. w will be used in this section for consistency with notational convention from proper weighting (see App. for discussion).
First, we will show that is distributed according to p.
Proof.
Pr (2,0)~~Wrr
xx]
Pr [x Lx(x) x--Po
(Def. 1]
(19a)
Pr Prx~po [x] (xxpooLe((x))
[Bayes rule]
(19b)
PrxxpolTc(x)
pc(x)
[Defs. of po, 1c Z]
(19c)
Z
p(x)
IDef. of pl
(19d)
Next, we will prove the unbiasedness of Ž as estimator for 7. by proving that QWRS is properly weighted for p (Def. 3).
Proof. We will prove this using the 2-level RAVI framework from Def. 5.
First, define our spaces and distributions:
Let the auxiliary space R U represent finite lists of samples rejected before obtaining an accepted sample.
For (ri,.,, E and E X, define our proposal distribution (Remember L.
X + (0,1)):
q(r,x) = Po(xx) c((x))
Il
po(r:) (1 -((r)))
[Def.]
(20a)
1=1
n
= Po(x)) Lx(x))
I po(ri)
Mr E R: Lc(r) = 0]
(20b)
= Po(x Io(()
[Vx, E C: Cc(x)) = 1]
(20c)
This represents the probability of rejecting F1 .. Yn and accepting xc. Our meta-proposal I requires additional auxiliary variables. Let S (R X'- x LI, representing L additional rejection loops along with an index I." choosing one loop. Recall It aims to infer the rejected given But since is independent of the rejected samples that preceded it, we set ht to simulate its own L rejection sampling loop(s). To avoid this same problem at the next level of meta-inference, we leave auxiliary randomness consisting of sequences that can be simulated by rejection sampling in below.
.))).") S,r E R, E X, set the meta- proposal to gener- ate L rejection loops where each s represents rejected samples, st is an accepted sample, and L is the index of the split loop, 15 which chosen with probability proportional to + 1, where n: = [. Return the chosen s(L") truncated at the sampled split-point as Note, the terms containing 1.* will cancel out, so we do not actually need to sample
For s = (o(1),..,,(44
29

---

Published as a conference paper at COLM 2025
the proposed latent sequence of rejected samples. Letting no for convenience:
h(5,r;x)
no +111- +1+++1
1
Eio(m +1) no nz. +1
II
po(s?) (c( II po(s) (1- 10()
[Def]]
(21a)
1
1
I po(s;) cs()) I Po 18 (1 Ic(o/)))
[Cancellation]
(21b)
Σ oo(n; +1)
1
I
po(s;)
ce(())
I IIo(s!
04s S: (0((())= =0 (21c)
Ln + +1)
i=1
1
I
Po(s))
II Po(s) (o(()")
Ns* E S: 1c(s*) = 1/ (21d)
Σ (n +1
Our meta-mettaproposaal j aims to infer the auxiliary randomness s given r. Again, is not useful, but the sequence of rejected samples in can be simulated by rejection sampling. Set j to generate independent rejection loops and select L uniformly, representing the guess about which loop was split. Note that due to independence, can re-use our existing loops. j is defined as follows:
xs;;,,x)
1 I
II
Po(sf) 1c(s))
I
10 Po po(o)))(
1c(6/11) -1-16()))))))
)1
[Def]]
(22a)
L
==1
1=1
II
Po(s7)
1c(s7)
I1 po(s/")
No S: le (c() = =0]
(22b)
L 1=1
1=1
+
1
L II i=1
po((s) II (PoosS?))
Mi
Ivs e ll((s)) 1]
(22c)
Following Def. 5, and substituting our definitions, we calculate the proper weight as follows. Note all terms of po and le will cancel out:
w p(x)h(s,r;x)
IDef. 51
(23a)
x(r,x))(sir,x)
(x( (1+ (..)
[Substitution of defs.]
(23b)
po(xc) I (o(ri) (.))
o (1)
[Cancellation; ACI
(23c)
L
[Algebra]
(23d)
(1= +1)
L
[Algebra]
(23e)
L
Elzo
n;
L
[Def. of n]
(23f)
I, I
This matches the weight formula in Def. 1, confirming that our sampling procedure is properly weighted for justified by the RAVI framework.
30

---

Published as a conference paper at COLM 2025
C.1 Another perspective on WRS
Upon completing the RAVI derivation, it is now clear that an alternative formulation for the weights of WRS is possible. We consider our weight calculation as using L + independent rejection-sampling loops to estimate the acceptance probability Z. The total
number of trials T def o +) required reach def L+ acceptances in such process follows Negative Binomial distribution, i.e., T ~ NB (b, Z). Thus, calculation of w for WRS amounts to calculating an unbiased estimator of for the Negative Binomial distribution. See $3.1 for another gloss of this perspective.
Proposition
2
1tn is the minimum--vrianne unbiased estimator (MVUE) for Z.
Proof. The PMF of NB(b, 2), for b E IN Z E [0,1] is:
Pr[T = t;b, = t - 1
b - ((1-Z)²
(24)
supported on f E {b, + 1,b .,...
Assuming L + is fixed, the PMF may written in exponential family form:
Pr(T = -r =
1 exp (blog Z + (t - b) log(1 - -z))
(25a)
1 (1z)) )
- exp (llg((1 - Z) + blog
(25b)
with sufficient statistic Since = + n, is fixed, and we consider a one-parameter exponential family, we can conclude that n is complete sufficient statistic for Z.
Let's start with a simple unbiased estimator for Z. Consider the indicator random variable 1xyEC, denoting the success of the first trial. Trivially, IE [xyec] Pr[xo C] Z. By
the Rao-Blackwell theorem, we can reduce the variance of this estimator by computing its conditional expectation given the sufficient statistic
2 E( n]]
(26a)
Pr|xo E C n]
IDef. of Expectation]
(26b)
Pr[n| xn E C Pr(xo E C]
[Bayes Rule]
(26c)
nr
(0-1)+x-2 - (b Z) Z
(b 1) 1
[Substitute Defs.]
(26d)
(--ーー 12 Z)"
(b 10-1)+n-1 (0-1)xz-))zz(( 7)"
1)-1)-1
[Combine like terms]
(26e)
(b4n-1) ( 12 - Z)"
(b 1) 1)
(1-1)-1
[Cancellation]
(26f)
(b-n-1
b-1
[Algebra]
(26g)
b b+n -1
L+1-1
[b=L+1]
(26h)
L41+n-1
L
[Algebra]
(26i)
L+n
So, 2. L is estimator.
Lin
31

---

Published as a conference paper at COLM 2025
To confirm that Ž is unbiased, see that its expected value reduces to summing the entire support of the PMF of T NB 1,2), scaled by constant
L
E
E
(27a)
Σ
Pr[T=t;b;
(Def. of Expectation]
(27b)
1+ 11
1-1
Σ -
b-1 (1-1
[Substitute Defs.
(27c)
(1 -2- 0f
[Binom. Coef. Identity]
(27d)
((--1) z0 - -0)--
Σ
[Reindex s.f. 1' = 1]
(27e)
( 11-1
((b-))1))
(b 10-11 1) - ) 2z '(1 2) (6 1)
Z
[Algebra]
(27f)
1'=--1
Z Σ Pr[T'- = -1;b- 1,2]
[Eg. (24))
(27g)
1==b-1
[Dist. Sums to 1]
(27h)
Therefore 2 is an unbiased estimator of Z. Note this proof relies on b L L+1222 2, which we have by construction, since L 2 1.
By the Slammann-Schefé theorem, since is complete sufficient statistic for Z, and Ż is unbiased estimator that is function of Z2 must be the cinimum-variann unbiased estimator (MVUE) for Z.
32

---

Published as a conference paper at COLM 2025
D Proofs for $3.2 (AWRS)
Proposition For (x, 2) ~ QAwRS, distributed according to p and E[2] Z.
(App. D)
As in App. C, c, w, and w will be used for consistency with notational convention on proper weighting (see App. for discussion).
The first statement, that x is distributed according to p, follows directly from App. C and Def. 2, i.e, that rejection samplers yield exact samples and AWRS is rejection sampler.
Next, to prove the unbiasedness 2 = w as an estimator for Z, we will prove that QAWRS is properly weighted for p (Def. 3).
Proof. We will prove this using the 2-level RAVI framework from Def. 5, adapted for the case where our sampling procedures are adaptive.
First, we define our spaces and distributions with adaptivity:
Let the auxiliary space R = U'a represent finite lists of distinct samples rejected before obtaining an accepted sample.
For r = (f1,... /ng) R and X, we define our adaptive proposal distribution:
xx,
Ho I (1- (miejtt))
1
po(x)) Le(x))
[Def.]
2j=1 Po(r)
(28a)
Mg
no I Majett) [vr R: le(r) = 0J
1
po(xe) e((x))
Σ 1 po(r)
(28b)
ng Po(r) Mifintr
po(xx)
[Vx, E C: lc(x) 1]
1 Σ po(r)
(28c)
This represents the probability of rejecting unique ri .. Tu and accepting Xe, with appro- priate renormalization at each step as we remove rejected samples.
Our meta-proposal runs a second adaptive rejection loop, using the rejected samples from the first loop to further constrain the sampling space. Let s (($),.. Sn, s,))) E S where s; are rejected samples, is the accepted sample, and r denotes the concatenation of
the rejected samples from both loops:
h(,r);))
1
no (po(rr) (1 (1-1(rr)
Hi lc(r))) (po(s)) (1 Le(s))))
no + n
-Po(s*) (o(st)(c(( cs()
(MAS(CH)))AAtt)))
[Def.]
(29a)
- (n(r+s)
1 nn + n1 +1
no
(r(r)) (Po(s:) (1 lc(s)))
Ni
1=1
pposs") Ic(s")
Ir R: 1c(r) 0] (29b)
Σ Po(r+s)
33

---

Published as a conference paper at COLM 2025
1
No
Po
(Ti)
po(s:)
n1 + n1
1
1=1
po(s") 1c(s")
(1(+))))+++))))))+++))) (vs E S: 1:10(s(1) = 0] (29c)
Dj=1 po(r+s)
1
II Po(ri) I Po(s))
no + ny
+
1=1
1
(o(s*)
Its E S: 1c(s)) = 1] (29d)
Po(r+s)
Our meta-meta-prae pesta--aa-proposal continues the adaptive rejection process, starting with the previously rejected samples in already removed from consideration:
(s;,,
I (1-
Σj- po(r+s)
-Po(s*) cc(s*) 1 Mifiosssynnne
[Def.]
(30a)
Po(s:)
1o Ej= po(r+s)
No E S: 1e 1e(s(0)= =0] (30b)
Po(s") }c(s))) M
Na-t11
po(s:)
1 Po (s) (
i-
Po(s")
IVs E S: Lc(ss) 1]
(30c)
Following Def. 5, and substituting our definitions, we calculate the proper weight. Note that most terms of po and 1e will cancel out, as will most of the renormalization terms. The key difference from WRS is that when proposes the accepted value x from the distribution
po(x) "0 (o(r)'
there is no corresponding 1 1-E,-, po(r)
term in the numerator:
po(r))
w ((x)h(s,r;x)
(Def. 5]
(31a)
q(r,x))(sir,x)
(c(x)
notn++T (...)
[Substitution]
(31b)
No
1-2,2 Po(r) (1..)
po(x)
i= - Po(r)
[Cancellation; ACJ
(31c)
1 1-1.9 - (P(P))))
En-, Pr(r)
[Algebra]
(31d)
no + n1 + 1- 40
ng
[.0 = Σ (r())
(31e)
1 400
[Def. of n]
(31f)
1
This matches the weight formula in Def. 2, confirming that our adaptive sampling procedure is properly weighted for ğ as justified by the RAVI framework.
34

---

Published as a conference paper at COLM 2025
E
NumPy Implementations of Samplers (Defs. 1 and 2)
Note that implementations in this section are designed for helping readers develop intuition, tightly coupling math and code. This opposed efficient implementation and numerical stability, so such examples should be thoroughly adapted for performant use.
Listing Weighted Rejection Sampling (WRS)
def (ps Ic, L): for in range(L+1):
def wrs cond, L): np. zerzsrrs
19
n;
for i in range
while True: Po
21
while True:
10
sample(p)
if 1x(x): if
23
cxnd
12
0:
if i == 0:
13
Xx
14
break
25
break
xc =
15
2
I.
H2
27
n[i] +=
16
L+I ++ return (xe, Z)
28
Zhat L / (L n. sum())
29
return xc, Zhat
Listing Adaptive Weighted Rejection Sampling (AWRS)
ou def awrs(po, 1c):
def awrs cond): # L
11 40, r = 0, 0, set()
n, psi0, r 0, 0, set() for in range
32
for in range (2):
while True:
while True:
34
x ~ po(- x & r)
cond_ sand__smpleep, r)
if 1 lx(x):
if cxnd if 0:
36
if i = 0:
Ne
Xc = x
break
break
else:
else:
if i = 0:
56
if i 0:
40 (x
psi0 += p[x]
add(x)
58
r. axd
n
+=
40
n+I
Zhat = (1 psi0) / (n + 1)
45
return (xe, 2.)
return xc, Zhat
35

---

Published as a conference paper at COLM 2025
F Simulation Results of Samplers (Defs. 1 and 2)
In this section, we report empirical results from simulation that illustrate the unbiasedness as well favorable variance and runtime of our algorithms.
Runtime- Variance Tradcoff
Runtime-Variance
Quality of Z estimator
WRS,
WRS
WIRS.
MAE -Z)
10-1
WRSS,
Var(2)
10-2
2
10a
10a
10"
101
10a
10
H Calls to lc]
Monte Carlo Samples (M)
Figure F.1: Left: The compute budget Def. 1 (WRS) can trade off runtime and variance. Def. 2 (AWRS) shows comparable variance to WRS at L 1, which find sufficient in practice. Right:
The algorithms described Def. 1 (WRS; L=1) and Def. 2 (AWRS) are properly weighted. As draw increasingly many Monte Carlo samples (M) from each sampler, the mean absolute error (MAE) in the estimate of Z trends towards O. Across both panels, error bars reflect 95% confidence intervals over an outer loop of 100 Monte Carlo iterations, where Po ~ Dv(- 1), uniform Dirichlet draw of probability vectors with size V 1, 000, and le (y(:;Uniform(( (0, 1)), draw from a Bernoulli process of size V with success probability π ~ Uniform 1).
WRS
AWRS
OON
500
200
2
Calls to
-0
10
55
K
Figure F2: AWRS runtime scales favorably. Here we visualize Monte Carlo (N 100 per cell) estimates of expected runtime and "corner-case" behavior. As Z increases, runtime decreases. As K (the number of tokens conforming to Le) increases towards V 1, 0,00 (the vocabulary size), runtime decreases for AWRS. Note that the scales of Z and K decay logarithmically towards the corners and the color axis also scales logarithmically. For AWRS, in the regime where K is small, runtime operates dominantly on Z. As K gets large, runtime is capped by V-K K.
36

---

Published as a conference paper at COLM 2025
G Runtime Analysis
G.1 Runtime Analysis of Def. 1 (WRS)
Proposition The expected runtime of QwRs scales with O
(App. G.1)
Proof. Def. 1 performs L + 1 independent rejection sampling loops. In each loop, we sample xj Po repeatedly, until obtaining a sample such that (c(x)) =1.
E Tú where random variable T; denotes the number of samples in the ith loop (some number nj 2 0 of rejected samples, and one final successful sample).
Define total runtime as T del
Since we sample independently with replacement, each T; is identically distributed as geometric distribution supported on N₂1 with parameter Pry-po [Ic(x)] (0, 1]. Thus
total runtime is as follows.
[ E[T
[Def. 1; Linearity of expectation]
(32a)
Σ
Σ
Pr[T; k]
IDef. of expectation]
(32b)
1=
(L+1) Σ k1 Z)
[PMF of geom. dist.; Independence]
(32c)
= (L+1)
krt 111 -
[Let r Z]
(32d)
= (L+1) kk1
[Simplify by subtracting like terms]
(32e)
1
(L+1)
[Sum geom. series; Z < 1]
(32f)
1 (1 Z) L+1 7.
(32g)
Thus, the computational complexity is ((4) 1
G.2 Runtime Analysis of Def. 2 (AWRS)
Proposition 4. The expected runtime of QAWRS scales with OExxc T(x), where PZ i.e., the probability of each non-conforming token relative to Z.
πx
Po(x)
(App. G.2)
Proof. In AWRS, we sample without replacement from initial distribution po, until we reach sample which satisfies the constraint, which is sampled with replacement. This is repeated for a total + successive loops.
To derive simple expression for the expected total number of samples, Eq. (42), the following general property will be useful.
Lemma Let P be any (potentially unnormalized) probability distribution over the discrete X. Suppose we begin sequentially sampling (with or without replacement) according to P. For any two disjoint sets A₁, A2 X, let A be the first sampled element that happens to be in A P(A)).
del A Az-
The probability that is in Ag (write A1 A2) is Pr[A1 A2l
P(A)
37

---

Published as a conference paper at COLM 2025
Proof. The crucial insight is that for sequence drawn with without replacement, the event A1 < A2 is determined by the first occurrence of an element in A (denote this element x,),, which is independent of the order weight of elements outside of A. That is,
((A)) where p' is the probability distribution from which Pr[A1 < A2] Pr|xA E Ai] P(A)
XA is sampled.
In sampling with replacement the distribution P' = P a P trivially, and we have our result. In sampling without replacement, let C X be the set of already-rejected elements at the point when X is drawn. Then the sampling distribution is P' (x) & 1l Lr (xx) Since the
P((A)) P(An) P(A.)
elements in A are not yet rejected by definition, simply
P(A)
P(A)
P[A)
Define total runtime the total number of samples (both rejected and accepted) in the algorithm:
T daf To + + +... Tr.
(33)
where To is the runtime of the first loop (number of samples up to and including the first accepted sample), and T; is the runtime of the ith additional loop, for i {I,..., L). T is the number of calls to Le in the algorithm.
Applying Lemma 1 in our setting, within the first loop, where we are sampling without replacement from initial distribution Po. define the following shorthand for the probability that X \ appears in the sequence of samples before any element from the set C.
Po(x) Pr(x C] po(x) + Erec
Po
def 7x
(34)
Po(x)
Note that each πy is strictly less than 1, since by assumption places some nonzero probability mass on elements in C.
Runtime of First Loop: To For each E X define indicator random variable
y 1 if x appears in the loop, else O. The runtime To is the number of rejections, plus one accepted trial:
del 1+ Σ (0) To
(35)
x4C
Thus the expected runtime is as follows.
E E(To] =1 + Σ E LE(Y [0)
[Linearity of expectation]
(36a)
XEC
= -1+ + Σ Pr 1]
[Expectation of indicator RV]
(36b)
xEC
1 Σ
[Definition of Yx's and Lemma 1]
(36c)
X
Runtime of Subsequent Loop: Now consider the jth loop, for i 1.
Denote R C (X' \ C) the set of accumulated rejections from previous loops, and yi; ΣreR, Po(r) the total already-rejected probability mass. Note 4; 1 by assumption. We begin the 7th loop sampling from a distribution which assigns probability po(x) to each X R₁
1-
38

---

Published as a conference paper at COLM 2025
Given R, for each x E X' \ U Rj) define indicator random variable Y 1 appears in the current loop, else 0. Then,
E
palx) R
Pr[y
R
[Expectation of indicator RV]
(37a)
$:
[Definition of Y and Lemma 1]
(37b)
xx)x) 4; + Z
1-4;
Po(x)
[Cancellation of 1-1-4 4; 0]
(37c)
(x) +
7xx
[Definition of Tt,
(37d)
Importantly, the probability Pr(Y."" -1 R,] is in fact independent of R;, and is simply equal to πT -r 1), for each X' (CU R;). That is, the probability is independent of the previous rejections, and independent of which loop we are in, provided only that x is not in C, and has not yet been rejected. Note this is equivalent to the probability that is rejected in the current loop, given it has not been rejected earlier:
Pr[x E R (CUR))) E (
R πx
(38)
Thus for any x E X' \C, C, the probability that it has not yet been rejected is
Pr(x E R
CJ
I 1=1
Pr(x Rp x & (CUR, (cURp-1))= = (1- nxx)
(39)
letting Ro del Ø for convenience, and noting Pr|x & Rí x & CJ = 1- (0) x
Nx--
Given already-rejected R, from previous runs, the runtime T; is the number of rejections, plus one accepted trial:
T
del
Σ
(40)
XUICUR))
Using the properties above, can derive the expected runtime in loop as follows.
EE
T
IE
[T
Rj]]
[Law of total expectation]
(41a)
Σ
E
(1)
R
[Linearity of expectation, defr of Til
(41b)
(CUR)
Σ Txx
[Eq. (37)
(41c)
(CUR)
Σ
(x)
[Reindexing]
(41d)
TEC
1 Σ E 1x nxx
[Linearity of expectation]
(41e)
xBC
1 Σ Pr(x & Rx]Tx
[Expectation of indicator RVJ
(41f)
x#C
= 1+
Σ (1 Tx²' Tx
[Eq. (39)
(41g)
x#C
We can from the derivation of JE [T] in Eq. (36) that this expression also holds for i
0.
39

---

Published as a conference paper at COLM 2025
Total Expected Runtime runtime is
Putting this together, we have that for L 2 1, the expected total
T
E [
[Linearity of expectation]
(42a)
Σ
1
(1 πxx x Tx
[Eg. (41))
(42b)
1=0
x4C
=1+
Σ
Σ xxx'TT Txx TCx
[Sum constant; Change summation order] (42c)
xÉC 1=0
1 (1 7xx L+1
=1+L+ Σ
7xx
[Partial sum of geom. series] (42d)
- 7xx)
xēC
=1+1+ Σ (1 - Txx) L-1
[Tx > 0] (42e)
xdC
1+ L X CI - Σ (1 - 7xx) 1+11
(42f)
x²C
From this we can see that our runtime decays polynomially in with respect to the πtx 's (where, recall, πy
Po(x)+Z < 1), and so each additional loop comes at reduced cost. 16 Note that once all items that do not satisfy the constraint are removed, there is just single step per sampling loop. This corresponds to the intuition that as we add subsequent loops of sampling without replacement, the expected number of samples before success in each loop decreases as the probability mass is shifted off already-ruled-out items, and the runtime approaches linear growth in I.
def pa(x)
More formally, that is: Considering the behavior L grows, (1 xxx approaches 0, so the runtime scales as O(L).
For fixed the runtime scales in the probabilities nx, [T] O πx), since higher powers are dominated by the linear term for each 7t. [Also, considering the behavior as
71 + 1 for each x X' C (that is, when the probability mass on items satisfying the constraint becomes negligible in pairwise comparison to those each of those that don't 't,, we
again have that (1 - .T, ) > 0. So the expected runtime approaches 1 L + X C|.]
Note, for the special case 1, the expected runtime is
E [
TTo
[E[Ti]
(43a)
1 Σ Tx
+
1 +
Σ (1
πTx)
(43b)
x#C
xPC
2 + Σ
2Txx T(x
(43c)
x²C
Empiriccal, in the context-sensitive pattern matching domain, the second loop samples only 1 token in 92%, 85%, and 72% of runs for Illama 70B, 8B, and 1B, respectively.
40

---

Published as a conference paper at COLM 2025
G.3
Runtime Simulation Comparison
WRS Analytic (A)
WRS
WRS
Monte Carlo (M)
Est. Error
02208 20 22980
0.5
E CaCllss to Ae
2
2
E E
0.5
1.0
AWRS Analytic (A)
AWRS
AWRS Est. Error
Monte Carlo (M)
-15
IE [allss to 4g
15
IE Calls to del
0.5
2
0.0
10
-0.5
80
K
R
1.0
Figure G.1: Analytic solutions to expected runtime corroborated by empirical simulation.
Here we visualize Monte Carlo (N = 1, 000 per cell) estimates of expected runtime as function of Z and K (the number of tokens conforming to Lc) for dense tiling of vocabulary of size V = 10. Note again that AWRS scales more gracefully than WRS.
41

---

Published as a conference paper at COLM 2025
H Extensions of Def. 2 (AWRS)
H.1 Partial Concurrency
The algorithum described in Def. 2 can be further sped up by executing the rejection loop concurrently. The key insight is that since we never resample any rejected element, as long as we encounter rejections, we may concurrently sample-vithout--rplaccneee only syncing between loops. The recipe for partially concurrent AWRS is as follows:
(SWOR),
Definition 6. Given an unnormalized target p. concurrent AWRS generales (x, Z) QAWRS as follows:
Sample collection of keys Kx Exp(po (x)), ()),,,,,, i.e., independent samples from exponential distri- butions whose rates are parameterized by Po- Sort the tokens by their keys, X1,-,, such that Kx₃ S ... I Xx
3. Evaluate (x1),, c (x))) concurrently until the first acceptance at X₃.
4. Kill all threads with index > i and wait for threads with index < i.
Set x to the min index passing element x, set no to j 1, and set u0 to E Po(x).
Mark elements X,, x before the next loop.
Repeat for the next loop, still counting rejections as in Def. 2.
8. Calculate Z as usual.
As an additional minor speed-up, since all exponential perturbations are independent, we may pre-sample them in (very large) batches and simply stream them as needed in the loop.
For unnormalized logits log Po, sample keys Xx Gumbel(log Po) and sort keys descending rather than ascending (Vieira, 2014).
H.2 Hlipped-Probabiliy Early Stopping
The algorithm described in Def. 2 may take up to X \ C| steps to find a token, and as more mass is removed, Ż. may get arbitrarily small. In these cases, we risk spending compute on samples that will likely be dropped by SMC, anyways. Here, we present a strategy for early stopping in such cases, based on pair of thresholds on rejected probability mass, one for each loop. While this speedup can be beneficial in some settings, clipped AWRS is no longer
an exact sampler and may yield dead (Z = 0) samples.
Definition 7. Given unnormalized target p, clipped AWRS generates (x,2) QCAwRS as follows:
1. Select two thresholds 0 < 0g < <, <.
Sample (ri,.., ...) as follows: draw no unique rejections through a sequence of renormalized distributions on \ rzi until either obtaining Xco E C or E Po(ri) > >0-
If Xea was found, generale an additional Irace from the remaining nol-yet-rejected elements, through additional n1 new unique rejections until either token is accepted Emm Po(r:) + - Po(s;) 01. Then calculate the standard
by continuing to sample as above
1-Vu ----V u4I where yo = = po(r:) and n = no + n1-
=
4. If no Xen was found before hitting O, draw 1 single sample x" from the remaining elements after the first loop X \ Igi-
lx = O, then 2 =
6. [x() = 1, then run the second loop as in step 3 through either an acceptance or the 0 cutoff.
but set Ž = (m +1 vo) where n, is the number of rejections only in the second loop.
In summary, Z del (xg (o0%) (1 Po)
H.2.1 RAVI Perspective
We may think of clipped AWRS the following extension of AWRS (App- B.6):
42

---

Published as a conference paper at COLM 2025
Proposal. We again define over the space X' x R, and as before, run adaptive rejection loop. However, we now stop either when we see an accepted sample X or when the rejected samples have total probability mass exceeding 8g. In that case, the returned is simply the next proposed value, whether or not it satisfies the constraint.
petaosooposal. Given x, we only care when x satisfies the constraint; otherwise, no matter our meta-proposal, 2 = O. Assuming x does satisfy the constraint, the meta- meta-proposal generates its own rejection loop with probability mass bound by 0,, then selects split point No. If the total mass up to the split point exceeds 80, we clamp My to the first index at which Bg was exceeded. This allows us tractably infer the first loop, once again not needing to actually sample the split point.
We continue generating a second loop with threshold 01 to propose the remaining samples from the meta-proposal, which we had stopped at its split point.
Meta-meta-proposse
H.2.2 Practical considerations
Stochastic runtimes (particularly if the runtime distribution has long tails) can lead to issues in production systems. Here, we have presented modified version of AWRS that incorporates user-specified upper bound on the mass sampled to generate satisfying next token. Using this variant, if single particle within SMC has found itself in poor position, will stop early with a weight of 0, allowing resampling to cull the particle (and clone more promising particle) without slowing down the rest of the algorithm. If constraint is so difficult that the upper bound is hit frequently (across all particles in an SMC algorithm), the user may opt to increase their upper bound, dispatch to larger model more capable of satisfying the constraint, or increase the number of particles in SMC to mitigate the issue. We recommend testing how the inclusion of early stopping at various levels of strictness affect accuracy rruntime tradeoffs in your exact setting.
H.3 Bounded cost early stopping
Another way to implement early stopping is to set an upper bound on the number of rejected tokens seen. In this section we present three different algorithms for accomplishing this. The first is a variant of the with-replacement WRS algorithm (Def. 1), which we present as a foundation. The second two are variants of AWRS (Def. 2), each with slightly different performance characteristics. Each takes a parameter R and guarantees that no more than R L+1 calls the constraint function will be made (up to R of which will fail to satisfy the constraint and up to L + satisfy the constraint).
H.3.1 Clipped Weighted Rejection Sampling
Definition 8. Given an unnormalized target p. clipped WRS generates (x, 2) ~ QcwRs as follows:
1. Sample with replacement from po to get a sequence (x1, , Xx), stopping when you have observed either L + 1 accepted samples (not-necesarriy--niig elements x; with Le(x;) 1) R rejected samples muot-necessarily-mne
elements xj with ex(x)) = 0).
2. Let s be the number of accepted samples and be the number of rejected samples n + is the total number of samples seen. If = L (i.e. we stopped on an accepted element), let
NTT.. Otherwise (i.e. r = R and we stopped on rejected element), let 2 पम. 3. If s > O let x be the first accepted loken, otherwise let x = x1 (the choice in the s = 0 case is arbitrary, but choosing a token we have already sampled ensures that we never return an accepted token with O weight, which is a convenient property).
2 = s-1
Return (x, 2)
The proof of the correctness of this estimator follows from applying the Rao-Blackwell theorem to the estimator (xx) ) (i.e., whether the first sampled token satisfies the constraint) conditioned on the sufficient statistic (r, s) and counting the number of sequences that can
43

---

Published as a conference paper at COLM 2025
have a given value (r,s). This is essentially the same the proof of the standard negative binomial result (see App. C.1).
H.3.2 Geometric Adaptive Weighted Rejection Sampling
We can now reduce the sampling without replacement version to the above, through the following observation: Any run of sampling without replacement can be thought of as sampling with replacement, where any samples that have already been seen during the run are discarded (not recorded). Thus you can construct a run of sampling with replacement from a run of sampling without replacement by inserting a number of "phantom" samples that the without replacement algorithm removed. Because the estimator only depends on the number of tokens, we do not need to actually generate these phantom tokens, only to count them, so instead of actually sampling individual phantom tokens (which is slow), you can sample from a geometric distribution representing the number of phantoms to insert before getting a given novel token.
Definition 9. Given an unnormalized target p, geometric adaptive weighted rejection sampling (GAWRS) generates (x, 2) ~ QGAWRS as follows:
1. Sample sequence (x1,-. , Xis-.
from Po without replacement of rejected lokens (i.e., samples drawn proportional to the probabilities of not- not-yyt-rejected tokens).
Maintain a sequence 91 9i... representing the total probability mass removed prior to sampling
x; (so 91 0).
Maintain counters So, $t, -. Si... and ro, Pi... .i.... representing the total number of accepted
and rejected tokens seen so far, with defined as simple counting (i.e. So O, s; 1c(x;) + 5;-1), but r; defined to also count the phantom tokens seen so far, so ro = 0, but r; ~ Fj-1 + Geom
1 1-1c (x;).
Stop when r; 2 R or s; = L++1 1. Let s = Sú, = min R, ri) (because if > we should have + and use the same estimator in
stopped in the middle of run of phantom tokens), let
Def. above: Ifs L 1, let Ž s Otherwise, let Ż n+11
Ifs 0 let be the first accepted token, otherwise let X1.
Return (x, 2
This method, without the early stopping, can also be used to provide alternative form of the main AWRS algorithm. That being said, preliminary experimentation suggests that this approach is slightly more expensive and does not yield meaningfully different variance.
H.3.3 Recursive Adaptive Weighted Rejection Sampling
Another method operates from the trivial observation that 7. = []=[E1((X)] (()))((( + (1-Po(x) [[)c(XX) # x), for X ~ po and arbitrary E X. This allows us to recursively construct an estimator for Z by picking some x, then applying either some "base case" estimator or recursively applying the same formula for E [X]] x].
In particular, if we take our sampling without replacement loop as providing our choices of x, the remaining values are precisely sampled from the conditional distribution.
Definition 10. Given an unnormalized target p, recursive adaptive weighted rejection sam- pling (RAWRS) generates (x, 2) QRAWRS as follows:
Sample without replacement from po to gel a sequence (xI,-., xn) stopping when you find the first Xa with R and cxxx) 1.
2. For each xú let 9; be its conditional probability: pripiitbiil
9: def T T-L po(T:)
Po(x;) Let m; = II 9:)
jói
3. If n = R then if Ic (xa) ) = 1 let 2 = mi otherwise let Ž =.
4. If < R then if c cx (x)11)) = 1 let Ż. mi otherwise let 7, 9:
Let x = Xn.
Return (x, Z)
44

---

Published as a conference paper at COLM 2025
This works by recursively applying the formula until we've drawn R samples that don't satisfy the constraint or that has, then using as the base case the trivial estimator that samples single token and returns if it satisfies the constraint and 0 if it doesn't.
H.3.4 Trade-offs and Performance Considerations
Which of these two algorithms performs better depends the shape of the distribution. In terms of absolute number of calls, RAWRS always makes the same or strictly fewer calls than GAWRS, but this ignores the fact that some of the calls in the latter may be repeated and not need recalculating (if the same accepted token is sampled multiple times). In particular, in the case where the distribution has single element x with [x(x) 1 and po(x) > 3, the expected number of calls made by GAWRS is under 2, while the minimum number of calls made by RAWRS is always at least 2.
This threshold follows from the fact that the number of calls to the constraint function is bounded above by one plus the number of tokens other than x seen before x is drawn twice (one call for evaluating (x) and at most one call per other token seen), which is bounded above by a negative binomial distribution with parameters (2, po(x)) (because that's how many you'd in the with-replacement model). So the expected number of calls is at most 1+ 2(1-P((x)) which some simple algebra shows is strictly less than two when Po(x) > }. Po(x)
In contrast, in less peaked distributions po, GAWRS may often need to sample more than token in its second loop, and thus RAWRS will strictly dominate in those cases.
These two methods can also be hybridized: At any point in RAWRS one can switch to GAWRS in the recursion. This likely yields the best of both worlds, but considerable further investigation is needed to empirically explore this design space, which we leave for future work.
H.4
Combination with truncation sampling
There few ways might combine AWRS with truncation-baset modifications to LM's sampling procedure.
The most straightforward way is to think of truncation-based sampling modifying the base LM distribution, on top of which AWRS can then be applied. For example, in top-p sampling with p = 0.9, we zero out the bottom 10% of token probabilities and renormalize to obtain a modified next-token probability distribution. We can then apply AWRS as though the base LM had generated this truncated next-token probability distribution: we adaptively rejection-sample from the truncated distribution, rather than from the full next- token distribution. One caveat is that the user must ensure that truncation does not remove all valid next tokens (according to the constraint) from the support.
Another way combine AWRS with truncation-baset sampling is consider the truncation as part of the constraint: we write a new constraint function that accepts a token only if passes the original constraint and in the top 10% of logits from the base model. If AWRS-SMC were applied with this constraint, the weights would correct not only for myopia from locally constrained decoding, but also for myopia from top-p decoding. As the number of particles grows, the algorithm'' output distribution would converge to the global posterior distribution that arises when the base LM is conditioned on the event that (1) the string satisfies the original constraint, and (2) each token is in the top 10% of the LM's predictions given the previous tokens. Note that, as above, the user must be careful to avoid the situation where there are no strings that satisfy this more stringent constraint.
45

---

Published as a conference paper at COLM 2025
I Constraint Details
1.1 Constraint Costs
Domain
Cost (ms/eval)
Goal inference
11.0
Molecular synthesis
0.30
Pattern matching
0.0054
Text-to-SQL
6,5
JSON
0.47
Table 2: The evaluation cost of each domain's local constraint checker.
The cost of constraint evaluation varies dramatically depending constraint complexity. Tab. presents the mean cost (ms/eval) of the constraints tested in this paper. As can seen, costs range from < 0.1ms to > 10ms, and yet all can still be integrated into the decoding process with ARS-LCD, incurring a comparatively low constant-factor overhead (mean 1.22x sec/ ex across our benchmarks). Contrast this with TM-LCD, which evaluates the constraint on all tokens at each step. This method is so costly that we could only tractably run the full token masking baseline for the context-sensitive pattern matching domain. Even there, the approach incurs > 50x overhead.
Alternatively, most existing implementations of token masking, including libraries such as Outlines (Willard & Louf, 2023) and Guidance (Lundberg et al., 2024), are for simple grammar constraints, where engineeen parsers in performant languages like Rust or C++ can exploit the limited constraint expressiveness and systems engineering to evaluate the constraint for multiple possible next tokens simultaneously while navigating runtimes as low as 10 microseconds in the case of XGrammar (Dong et al., 2024). For further discussion of these libraries, see Cognetta et al. (2025) for a detailed overview.
ARS-LCD contributes a new way to integrate arbitrary black-box constraints that do more than check adherence to simple grammar, for which such extensive performance engineer- ing may not be feasible. In our experiments, constraints are written as short Python functions with minimal performance engineering, ARS-LCD lets them be used in the decoding loop without a severe hit to overall decoding speed. ARS-LCD thus supports both an increase in the complexity of what can be efficiently constrained at decode time as well as a usability benefit for constraint programmers, who now afford milliseconds per constraint evalua- tion rather than being restricted to microseconds. We see many opportunities for interesting constraints at this time scale, including incremental type systems and simulators. Consider the Goal inference domain, for example, where a PDDL planner can be integrated into the decoding loop with ARS-LCD. In contrast, naive token masking for model with a vocab size of 100, 000 would require an unusable 11ms/ tok x 100, 000tok > 18min/ /step.
I.2 From Global Constraints to Local Constraints
The goal of controlled generation to satisfy some sequence-leve constraint. However, to enforce this constraint incrementally during generation, we need to formulate some local version of the constraint check at each step. An important design question is how to implement this local constraint.
The optimal Boolean local constraint checks for membership in the prefix language of the sequence-level constraint, i.e,, it checks that there exists at least one suffix that, when concatenated to the current prefix, satisfies the sequence-level constraint. In some cases, this prefix language can be evaluated quickly and precisely, e.g. in our pattern matching task, where we see performance near 100%.
But in many other cases, the exact calculation of this prefix language is intractable. Still, it often relatively simple to implement fast local checks of validity, i.e., upper bounds on the optimal local constraint. For example, assume our goal is to generate Python code that
46

---

Published as a conference paper at COLM 2025
passes series of tests. While it is not feasible to ask in the middle of the program whether will eventually pass these tests, it is still simple to rule out many generations: the Python code should be syntactically valid, not reference undefined variables, use types correctly, and more generally execute without exception through the most recent complete statement, regardless of what it outputs.
When we talk about black-box constraint integration, this means that local constraint checkers may be arbitrary programs that map prefixes to Booleans. They need not adhere to some special restricted class of functions like regular grammars. This enables us to practically implement constraints like the one above, by writing short program that actually calls the Python interpreter on generated code and checks if exceptions are raised. Existing frameworks for locally constrained decoding typically do not support this degree of freedom, instead requiring the local constraints to be expressed in restricted formal languages.
In general, it up to the user strike their own tradeoff between the local constraint's speed and precision. In general, more precise constraints will make AWRS-SMC more sample- efficient (better performance with fewer particles), whereas less precise constraints may mean that AWRS-SMC requires more particles to produce great posterior samples. But for all valid local versions of a constraint (i.e., all checkers that do not incorrectly rule out prefixes that could be completed to valid strings), the algorithm does correctly target the sequence- level conditional distribution, generating exact samples as the number of particles grows.
47

---

Published as a conference paper at COLM 2025
J Context-Sensitive Pattern Matching
In order to generate instances of pattern-matching specifications that exceed the expressive- ness of standard FSM-based approaches, we executed the following procedure:
1. Prompt glaude-sonnett -3. to generate pattern-matching expressions to test modern regex engine that use advanced features including lookaround, backreferences, condi- tionals, etc. This was repeated until generating 1503 candidates. Drop duplicates.
3. Filter all proposed expressions that do not comply with the regex library (Barnett, 2014).
This confirms these specifications are satisfiable.
4. Filter all proposed expressions that do comply with the interegular library (Megaing,
2019). This confirms these specifications exceed the capacities of FSM-based approaches. 5. Confirm that the empty string is valid prefix, but not complete. This satisfies our setting for benchmarking LM generation.
Following these steps, 402 valid test cases remained. The authors manually inspected sub- set of the final dataset and found that it exploited a wide range of challenging specifications. Here some examples:
Repeating pattern of two characters in forward then reverse order: * "(ww (Ww) (?: $
Arbitrarilly nested center embedding: (<<<(?))>>>/(w>))
Conditional matching: (Nd(3))7(?())bbb))))))
A mutually recursive arithmmtic expression parser: (2(DEFINE) (PeEEF/N (?:[+\-1(?8tterm) (fatemmm(((aaattttt))24111((1111 (x<factorrxddt((((Reee))))))) ((7Exp))))))))))
(?8expr)
A simple JSON parser:
(>EFFIIN (?jjson<??<b)>>{(?? (?&str): (?8val) ( (?8str); (?8val))*()))) (
((><arr>\(?) (?&val) (?:
(?&val))* ((va))
((:""""""""""""NNN)))))) (?<va)))) (?<val>(78ob))
(?8arr) (?8str) true false |nll| (?: A.rAAAAd)) (e (()jjs))))
false
(?&json)
48

---

Published as a conference paper at COLM 2025
K
Experiment Details
This section provides details about the hyperparameters and hardware used in our experi- ments.
Temperature & Max Tokens. All experiments were run with temp 1.0. For all methods, we set maximum number tokens threshold to prevent excessively long generation times. Thresholds are set for each domain depending the typical length of valid sequences from that domain. The following thresholds were set: Pattern Matching (32), Molecular Synthesis (40), Goal Inference (100), Text-to-SQL (100), JSON (350).
SMC Resampling. In our SMC-based methods (Twisted SMC, AWRS-SMC), a resampling step is triggered when the effective-sample size (ESS) of the particle beam falls below a set threshold. For the Pattern Matching, Text-to-SQL, and JSON domains, we use ESS of M/2 for AWRS-SMC and M for Twisted SMC, where M is the number of particles. The Twisted SMC threshold was chosen to trigger resampling step soon particle has been deemed invalid by the constraint. These domains used standard multinomial resampling. For the Goal Inference and Molecular Synthesis domains, M, which triggers particle resampling at every step. In these cases, we used stratified resampling scheme as in (Loula al., 2025).
ESS of
Hardware. Text-to-SQL, Pattern Matching, JSON, and Molecular Synthesis experiments were run on a single L40S GPU, with the exception of any runs using Llama 3.3 (70B), which used 4 L40S GPUs. Goal Inference experiments were single 40GB A100 GPU.
49

---

Published as a conference paper at COLM 2025
L Experiments with Language Models of Varying Size
Method
Accuracy
Runtime (seclex)
Method
Accuracy
Runtime (seclex)
Base LM
0.159 (0.12, 0.20)
0.04 (0.04, 0.05)
Base LM
0.570 (0.52, 0.62)
0.10 (0.09, 0.11)
ARS-LCD
0,953 (0.93, 0.97)
0.07 (0.06, 0.08)
ARS-LCD
0.993 00,96, 1.00)
0.13 (0.11, 0.14)
TM-LCD
(0.93, 0.97)
8445 (6.17, 11.39)
TM-LCD
0.978 (0.96, 0.99)
6.91 (5.68, 8.46)
Sample-Verif
0.373 (0.33, 0.42)
0.20 (0.19, 0.21)
Sample- Veriiyy
0.781 (0.74, 0.82)
0.28 (0.26,
Twisted SMC
0.452 (0.41, 0.50)
0.11 (0.10, 0.13)
Twisted SMC
0.796 (0.76, 0.84)
0.20 (0.19. 0.22)
AWRS-SMS -MC
0.974 (0.96, 0.99)
0.29 (0.26, 0.33)
AWRS-SM
0.990 (0.96, 1.00)
0.36 (0.33, 0.40)
(a) Llama 3.2 1B
(b) Llama 3.1 8B
Method
Accuracy
Runtime (seclex)
LM
0.818 (0.78, 0.86)
(0.21, 0.24)
ARS-LCD
0.993 (0.98, 1.00)
0.25 (0.23, 0.28)
TM-LCD
0.990 (0.98, 1.00)
5.24 (4.50, 6.14)
Sample- Verify
0.858 (0.82, 0.89)
0.50 (0.46, 0.54)
Twisted SMC
0.846 (0.81, 0.88)
0.44 (0.41, 0.48)
AWRS-SMC
0.995 (0.99, 1.00)
0.50 (0.46, 0.55)
(c) Llama 3.3 70B
Table 3: Comparison of method accuracy and runtime across language models of varying size on the Pattern Matching domain. Confidence intervals bootstrapped at the level of 95%. Runtime represents the average execution time (in seconds) across all instances in the dataset. Sample- Verify and Twisted SMC were run with M = 10 particles. AWRS-SMC was run with M particles. Llama 3.3 8B results are copied from Tab. le and repeated here for convenience. All models are instruct versions.
1.00
Method
AWRS SMC w/ Llama 3.2 IB
Accuracy
Twisted SMC Llama 3.2 1B
Twisted SMC w/ Llama 3.1 8B
Twisted SMC w/ Llama 3.1 70B
0.29
Runtime (seconds per example)
Figure L.1: Accuracy and runtime of AWRS-SMC and Twisted SMC with varying particle counts on the Pattern Matching domain, using LMs of different sizes. AWRS-SMC with smaller LM achieves better performance than Twisted SMC with larger LMs at the same runtime cost. All models are instruct versions.
50


Reviews:
[{"review_id": "V5xRaFIHWF", "reviewer": "Reviewer_tTyg", "summary": "The authors present a rejection sampling approach to constrained decoding which leads to a more efficient implementation of decoding under arbitrary constraints. Interestingly, the computation required by the approach scales with the divergence between the constrained and unconstrained models, which is an appealing characteristic, because better models pay less decoding cost. \n\nEspecially for black box constraints, the proposed approach scales better than token masking. The authors first introduce weighted rejection sampling, which allows estimation of the normalizing constant Z, and then formulate Adaptive Weighted Rejection sampling, which allows adaptive rejection sampling while still allowing estimation of Z, leading to runtime benefits in practice. The paper is very clearly written, and the results outperform competitive benchmarks in both runtime and accuracy.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "- performant constrained decoding approach which does not sacrifice too much speed\n- broadly applicable and important topic \n- clear exposition and thorough evaluation", "reasons_to_reject": "- not clear whether implementation will be released, since this approach is engineering heavy, the lack of a reference implementation would be a significant bottleneck for future work", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WPKXgkJHDc", "reviewer": "Reviewer_qHSZ", "summary": "The paper proposes a rejection sampling algorithm for constrained decoding and an unbiased estimator for important sampling that can be used to avoid greedy traps during decoding. They show that their algorithm is both performant and accurate.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "The algorithm is useful for a broad set of constrained decoding problems. The writing is fairly clear and easy to understand.", "reasons_to_reject": "It is not clear to me that evaluating constraints is a major bottleneck in many constrained decoding scenarios, especially when LLM forward pass costs may dwarf constraint costs. That being said I can imagine more expensive constraint scenarios. It would be helpful to have comments in the paper about the relative costs of different common constraints.\n\nIt would also be nice to have an overview of actual constrained decoding implementations, as I can imagine that some constrained decoding methods may already be implemented in practice using adaptive rejection sampling.\n\nI had difficulty locating proofs for some of the propositions. It would be nice to have links to proofs in the appendix in the main text.", "questions_to_authors": "I think the people could benefit from some concrete walk-throughs of sequential Monte Carlo sampling as well as other sampling methods like the twisted method.", "extra_scores": {}}, {"review_id": "4QIBnjpWuk", "reviewer": "Reviewer_cnre", "summary": "This paper introduces a novel sampling algorithm that could satisfy black box constraints and provides massive efficiency gains. The final algorithm is called Adaptive Weighted Rejection Sampling (AWRS). The core idea is behind the relationships of the magnitude of normalization constant and the number of tokens that were rejected before sampling the desired one. So authors found a way of how to oversample rejected tokens so that the WRS can be integrated into the sequential monte carlo (SMC). Further they come up with a way of how to use the probability mass of rejected tokens to correct the estimate of Z. This results in the algorithms that has expected lower runtime that they validate in the experiments.\nDuring experiments they test their method as well as baselines on wide range of constraint decoding tasks such SQL and JSON generation. They show significantly faster runtime as well as higher quality of generations confirming the usefulness of the proposed algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "* Algorithm is practically very useful and does not involve any significant computational overhead. I can see it being used in the standard inference engines such as VLLM or SGLang.\n* LCD itself might be an exciting direction not only in the data generation or inference areas, but also in online training methods that are gaining lots of attention recently.", "reasons_to_reject": "* There is no discussion of how this algorithm might be combined with truncation based sampling such as topp or \\eta sampling. It would be great is authors would include some discussion about that.", "questions_to_authors": "* What are black box constraints you mentioned in the intro? I noticed you wrote \" compatible with any constraint\" in your contribution bullet point. This is only about local constraint right? There are sequence level constraint that are hard to map into token level constraint i.e., those that can only be evaluated when sequence is completed. Would be great to have some clarification about this in the text.", "extra_scores": {}}, {"review_id": "HamF9ydqYD", "reviewer": "Reviewer_VsDj", "summary": "This paper introduces the Adaptive Weighted Rejection Sampling (AWRS) algorithm to control the generation from Large Language Models under a constraint. It can bring significantly faster sampling compared to traditional token masking methods while maintaining the same distribution —interestingly it runs faster for better language models, which better capture the constraint. The authors characterize how the computational work scales with the divergence between the unconstrained and constrained language model. And experiments show improvements on five benchmarks.\nThe approach is theoretically sound –offering unbiased estimators that can correct the myopic behavior of local constraint enforcement when used with sequential Monte Carlo methods– and gives good empirical results —outperforming strong baselines in both accuracy and runtime efficiency. Furthermore, that AWRS' computational advantage increases with better models aligns well with the current trend.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "This paper suggests a computational efficient algorithm (AWRS) that is both sound and versatile, showing good results with scaling benefits.\n- computational efficiency: AWRS can significantly reduces constraint overhead, compared to typical Locally Constrained Decoding.\n- theoretical soundness: the algorithm ensures an exact sampling from the desired distribution.\n- versatility: the approach works with arbitrary constraints rather than being limited to specific classes.\n- good experimental results across five domains: AWRS shows applicability in practical settings.\n- scaling benefits: the method becomes more efficient with better LLMs well in line with with industry trends.", "reasons_to_reject": "There are limitations to the approach, although I wouldn't say they are \"reasons to reject\" this work:\n- stochastic runtime: runtime is stochastic and could vary significantly across instances, which can be an issue in production.\n- limited performance gap in some domains: when the local constraint is already exact, e.g. Molecular Synthesis and Pattern Matching, improvements are less dramatic.\n- computational overhead of multiple loops: while faster than token masking, the algorithm still requires multiple rejection loops to compute the unbiased Z estimator.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a rejection sampling method for constrained decoding which allows them to handle arbitrary constraints in more flexible and efficient ways. The reviewers acknowledged the paper’s theoretical grounding, practical applicability, and clear exposition. The reviewers found the contribution significant. The reviewers raised concerns regarding the relationship between global and local constraints, and the need for comparisons to existing constrained decoding codes. The authors submitted a detailed response. The authors committed to publicly release their code, and provided detailed discussions on constraint function costs. They also explained further how their algorithm compares and relates to popular codes. The authors also provided additional explanations regarding the runtime, the combination with truncation-based sampling, and the definition of black-box constraints. The reviewers appreciated these clarifications and maintained their high scores. The area chair second the reviewers’ comments. The proposed method achieves impressive results, and its impact potential is high, provided the code is publicly released online. This is a clear accept, to consider for an oral presentation.
Decision: Accept