Approximately Aligned Decoding
Authors: Daniel Melcer
Sujan Kumar Gonugondla
Pramuditha Perera
Haifeng Qian
Wen-Hao Chiang
Yanjun Wang
Nihal Jain
Pranav Garg
Xiaofei Ma
Anoop Deoras
Venue: NeurIPS 2025 poster ()
Keywords: Constrained Decoding
Large Language Models
Primary area: deep_learning
TL;DR: Efficiently generate text avoiding constraint violations, with less distortion of LLM output distribution.

Abstract: It is common to reject undesired outputs of Large Language Models (LLMs); however, current methods to do so require an excessive amount of computation to re-sample after a rejection, or distort the distribution of outputs by constraining the output to highly improbable tokens.
We present a method, Approximately Aligned Decoding (AprAD), to balance the distortion of the output distribution with computational efficiency, inspired by algorithms from the speculative decoding literature.
AprAD allows for the generation of long sequences of text with difficult-to-satisfy constraints, while amplifying low probability outputs much less compared to existing methods.
We show through a series of experiments that the task-specific performance of AprAD is comparable to methods that do not distort the output distribution, while being much more computationally efficient.

Approximately Aligned Decoding
Daniel Melcer
Sujan Gonugondla" Meta Superintelligence Labs New York, NY, USA suj sujan@eeta.c com
Khoury College of Computer Sciences Northeastern University
Boston, MA, USA
melcer.ddnorreee www..rr..cchorhhssstrr..n edu
Pramuditha Perera
Haifeng Qian" Nvidia Santa Clara, CA, USA
Wen-Hao Chiang AWS NGDE New York, NY, USA
AWS NGDE New York, NY, USA pramudi @amazon com com
haifengg@nvidia.cmm com
cwenhao@amazon. com
Yanjun Wang AWS NGDE New York, NY, USA
Nihal Jain AWS NGDE New York, NY, USA
Pranay Garg
AWS NGDE New York, NY, USA
yanjunweamazon.cm com
nibjain@amazon. com
prangarg@amazon.cm com
Xiaofei Ma AWS NGDE New York, NY, USA
Anoop Deoras
AWS NGDE New York, NY, USA
com
adeoras@@mazon.com
Abstract
It is common to reject undesired outputs Large Language Models (LLMs); however, current methods to do require excessive amount of computation re-sample after rejection, or distort the distribution of outputs by constraining the output to highly improbable tokens. We present method, Approximately Aligned Decoding (AprAD), to balance the distortion of the output distribution with computational efficiency, inspired by algorithms from the speculative decoding literature. AprAD allows for the generation of long sequences of text with difficult- to-satisfy constraints, while amplifying low probability outputs much less compared to existing methods. We show through a series of experiments that the task-specific performance of AprAD is comparable methods that do not distort the output distribution, while being much more computationally efficient.
1 Introduction
Large Language Models (LLMs) are able to perform many complex text manipulation tasks, and embody an incredible amount of world knowledge, but their output may contain undesirable elements such as syntactically-inoored which we collectively refer to as errors or constraint violations for the remainder of the paper, may be detected with incremental parsers, regular expression matching, even simple substring searches.
code, hallucinated PII, profanity, or failed tool calls. These issues,
"Work performed while Amazon
Code available allttpps:/ggitiii //ttthub///hubb... com/ amazon http:/aazznnsiiiiiice wwwprooewccieeee//pppproriaalaaa Aliiggg DeddddDeedgggg
39th Conference on Neural Information Processing Systems (NeurTPS 2025).

---

Each individual task that a LLM is used for may have unique set of constraints. However, re-training LLM to accommodate the constraints of every task expensive. and may still not fully protect against violations. Therefore, the community has developed several methods to mitigate constraint violations without the need to retrain the language model. However, many existing methods deviate severely from the original output distribution, or have intractable performance for certain constraints.
Our contributions are follows. First, we analyze several existing methods for avoiding constraint violations in text generated from autoregressive language models, and compare the strengths and weaknesses of each method. Second, we present method, Approximately Aligned Decoding (AprAD), that allows for a useful midpoint in the tradeoff between computational efficiency and maintenance of the output distribution, without the need for any additional training or fine-tuning step. At its core, AprAD uses procedure from the speculative sampling literature to determine backtracking behavior after encountering an error generation. Finally, we run a series of experiments, demonstrating that our method obtains excellent task-specific performance on both synthetic and real-world domains, without introducing an unreasonable level of inference overhead.
1.1 Related Work
Language models based on Transformer architecture [32 have steadily become popular, with high parameter counts, in consumer chatbot products such as OpenAl ChatGPT [23 and Anthropic Claude (2) or code generation tools such GitHub Copilot [T]] and Amazon Q Developer (5].
Sampling- methods. Several LLM tools have introduced output control features such as schema-restricted generation [24]. For those willing to run local inference on language model, however, there are a vast array of methods for constraining the output of a model to follow a template 22 27 29), produce syntactically valid code [12 I8, 28
33 or conform to various poetry constraints (26). These works often use constrained generation 66 9 to control their outputs.
3 4 21
30
As we will discuss, while constrained generation is often effective, may result in undesirable probability amplification. Other methods avoid probability amplification at the expense of additional computation; for example, rejection sampling and Adaptive Sampling with Approximate Expected Futures (ASAp) 25 A related method [ translates the constraint into a circuit and re-samples sequences in the neighborhood of error samples to obtain non-error sample.
Posterior estimation methods. Another class of methods 14 34 [3], avoids errors by estimating the posterior probability of an error occurring for given prefix, and decreasing the probability of generating prefixes that are more likely to lead an error. These methods are usually able to quickly generate sample with little amplification of low-probability outputs, but rely an accurate estimator of the posterior probability of an error, which may not always be available.
Speculative decoding, A LLM's s autoregressive nature can lead to high inference latency, even without constraint following. One method to combat this, speculative decoding 13 19
reduces latency by transforming the sequential generation problem into a parallelizable verification problem. Several extensions such as Medusa 7 and EAGLE 15 16 have improved the latency and efficiency of speculative decoding, and a variant, Mentored Decoding [31 further increases the speed of speculative decoding by allowing for a controlled deviation from the LLM's probability distribution.
2
Preliminaries
We first describe autoregressive language models and their properties. We then discuss speculative decoding, method closely related to the algorithm that we will introduce.
2.1
Autoregressive Language Models
Algorithm 1 Generation with an autoregressive model
procedure Generate(P, .....)
b Initial Ty... is the prompt Typically special BOS token, and length limit
while Stopping condition not met do
Sample one token To+1 ~ P(-
Increment n
return x

---

We assume that vocabulary V of tokens is provided. An autoregressive language model is function approximator trained to predict 1i.. the conditional probability of token 2n V, given existing tokens #1...n-1 E V*. Algorithm describes repeated sampling from a language model.
Note that there several other methods for token selection; i.e. greedy selection, beam search, While we focus on sampling, the techniques we present may also be applicable to other methods.
2.2 Speculative Decoding
Algorithm 2 Speculative sampling procedure
procedure SpecSample(P,, 1.,......... FI..m) for i E 1n+1..... mL do
1n.1 are from SSM
May be vectorized instead of iterative loop P() and S()) already calculated and cached
r 1)
with probability r do continue
D Always if 2 1 b Accept I Reject v,, sample replacement token > Calculate residuals
else
R(t) max P(t (t
return 2 Sample(Normalize) R(-)))
return Ti...m, (amplee((()21....)
Accepted whole sequence, can sample tm
Autoregressive LLMs can require considerable computational resources evaluate. Due to the sequential nature of inference, additional parallel resources often have limited effect to decrease generation latency.
16 19 decreases latency by recasting the autoregressive generation problem as one parallelizable verification. This method assumes the existence of small speculative model (SSM) S that approximates the LLM output, using fewer computational resources.
Speculative decoding 7 13
Given input tokens TI..... the SSM is sampled for tokens, resulting in tokens In+1..m Then, the LLM is used to compute P(1++1| (x1...) for E [n.... m]] all parallel.
Briefly, Algorithm 2 takes as input the sample from the SSM, and the token generation probability distributions from both the SSM and L.M.. determines how much to keep or discard, such that it is as if the resulting prefix Fa... for h E [n, m] is drawn from the LLM. When the SSM's distribution and LLM's distribution are similar to each other, more of the prefix has higher probability of being kept. Additionally, because the probabilities P(-(xr....) have already been computed, Algorithm] samples new token Tk+1-
prefix the sample In...m
We later show that Algorithm is useful for different domain, with a somewhat different notion of quality and efficiency: violation-free generation.
Problem Statement and Existing Approaches
Error sets. Error Set B V is the set of strings containing errors. Without loss of generality, assume that if string 21... B, then all strings with #1...n as a prefix are also members of B; i.e. adding more text does negate error. Careful design is required when, for example, profane words are substrings of benign words [8], or where un un-parseable code can be made valid with additional text. Any error set may be theoretically be transformed into one that satisfies this assumption: xi..... is invalid, but additional text may be added to make it valid, the error set should contain æ1... o EOS where EOS the end-of-sequence token, but the error set should not contain 11... However, in many domains, it may be difficult to determine if additional text may be added to make string valid.
Black-box constraints. B will often be infinite size; treat it black-box indicator function. Some constraints, such as those expressible by a context-free grammar, may permit more efficient implementations 66 9 [8] these efficiencies largely apply to all sampling-based error-free generation approaches equally, so we do not consider their impact separately.
We define the probability distribution obtained by sampling P, except for any elements of B:

---

B B
jB (w)
w
&
Z P(w)
P(w)
Given an autoregressive language model P over alphabet V, and error set B C V", provide method to sample from PB.
Problem 1.
Dense error sets. Rejection sampling the most straightforward method for sampling from pB; however, it may require large number of evaluations as Ewes P(w) approaches 1. For example, consider a domain where each token has, approximately, some non-zero probability p of being an error-wher where the language model has somewhat consistent error rate per token. If d tokens generated, an output has approximately a (1 - p) probability of being error-free: thus requiring on average (1-p)a generations. We consider such domains, where the probability of generating error approaches for long generations, to have dense error sets.
Constrained
Round 1
Round 2
Total
3.1 Existing Approach: Constrained Generation
Running Example. We introduce a running example to illustrate the effects of several error-free decoding methods. There are two possible tokens, and B, and the task is to generate sequences of length 2. All token probabilities are 1/2, resulting in probability of 3/4 to generate each of the four sequences initially. Sequence AA is marked an error, meaning that there are three possible non- error sequences. The ideal re-normalized probability is therefore 1/3 for each remaining sequence.
Figure 1: The entire probability mass of AA is shifted to AB.
Constrained generation attempts solve the error-free generation problem by using a greedy algorithm: avoid selecting any tokens that immediately lead to an error
Probability amplification. Problematically, constrained generation often greatly amplifies low- probability samples by committing to a given prefix, even if the most probable sequences beginning with that prefix are errors. Figure T shows that in running example, the probability of AB is significantly raised. Note that this distortion is even worse in low-entropy scenarios; if P(B)A) were lowered to 0.0001, there would still be a 1/2 probability to sample AB. This amplification effect compounds exponentially for longer sequences.
3.2 Existing Approach: SEAAp-Smmling Without Replacement
Adaptive Sampling with Approximate Expected Futures (ASAp) [25 is a technique to sample exactly from the distribution of
ASAp
Round
Round
Total
8 If ASAp encounters an error during sampling, it adds to
set B C B. Because B is finite, the conditional probabilities be tractably calculated, allowing for the algorithm sample from Pa The sampling process repeats with this new distribution until an error-free sample is found.
p (=g
In the limit of repeated samples, B will approach B, and therefore, PB will approach Pa Importantly, if PB sampled such that x & B. this sample may be accepted, even though B & B.
Figure 2: The probability mass of AA is distributed evenly.
In Figure [] after sequence AA is added to set B (in the 1/1 of cases where is initially sampled), the conditional probabilities recalculated shown in Round 2. Each sequence correctly has an equal chance of being sampled in the second round.
While ASAp succeeds in cases where there are only a small number of errors that comprise the majority of the probability mass, its generation speed suffers when there are large number of errors- each error must be discovered before it is added to B. In dense probability sets, its performance
If every token leads to an immediate error, it necessary to backtrack, though many implementations assume that there is always some token available that satisties the constraint. Our implementation of constrained generation attempts all top-k tokens, and backtracks only if these exhausted.

---

characteristics are similar to rejection sampling, as there are exponential number of error sequences that must be discovered as generation length increases.
3.3 Existing Approaches: Posterior Estimation
We note several additional methods that, although they use dif- ferent formalizations and implementations from each other, rely on similar core idea to approximate PE In all cases, for any given prefix TI...n these methods create an estimator of the like- lihood of valid sequence being generated for each prefix. This posterior probability estimation is used to sample from Pe The differences lie in how they perform the estimation:
Posterior Estimation
Original Probabilities Posterior Estimates
Renormalized
involves training discriminator, usually neural network or combination of several networks, to directly estimate this probability. SMC Steering [14] creates this estimate using Monte Carlo sampling. This method additionally incorporates optimizations such sampling without replacement, and ag- gressive pruning of low- now-probubility branches. In contrast, Ctrl-G 35] first distills a LLM into a Hidden Markov Model (HMM) with tractable number of states (thousands or tens of thousands). If the constraint can be expressed as a Deterministic Finite Automaton (DFA) over tokens, Ctrl-G takes the product of the DFA and HMM, and calculates the probability of an error in this product system.
FUDGE 34
XI
Figure 3: An accurate posterior timator corrects the probabilities before sampling.
Gen-C [ contains elements of both posterior-estimatiin and sampling- based generation, relying both sampling the neighborhood of an error, and constructing a large constraint circuit.
While these methods exhibit impressive results many tasks, they may face issues in domains where the posterior probability close to or where the posterior is uncorrelated with the prefix content, leading to incorrect estimates. We further discuss considerations for method selection in Section 6.1
Method
An alternate view of constrained generation and ASAp is that, after encountering an error, constrained generation reuses almost the entire sample, while ASAp reuses none of it (besides to adjust probabilities in its next iteration). A natural alternative is to reuse some of the sample- eapple-enouhh to avoid excessive computation, but not enough cause severe probability amplification.
How much of the sample should be reused? strategy that reuses a fixed number tokens, or that backtracks fixed percentage of the generation length, is unlikely to effectively adapt to variety of tasks or error sets. The prefix selection strategy should avoid discarding too much useful information, or backtracking the middle of a low-entropy sequence. Fortunately, the prefix selection algorithm from speculative sampling presents an excellent strategy for backtracking behavior.
4.1 Speculative Sampling Prefix Selection Algorithm
In ASAp, where B is the set of observed errors so far, let x = pB, such that B. ASAp will add x to B and sample again. We observe that p8 and pBu(z) are almost always near-identical distributions, with pBu(x} generally a "more accurate" distribution because it incorporates an additional error sample.
be trace drawn from
Our method uses the sample PB to approximate a sample x' (Bu(a), in a similar manner to how speculative decoding uses sample from SSM to approximate sample from a LLM rather than the probability distributions being generated by two separate models, the distributions are both created from the same model, before and after adjusting for violating sample. By evaluating SpecSample(zz) PB (=))))) our method obtains prefix of that can be used a starting point for sampling again. Because the distributions of jB and (DBff)) usually most of the length of x, especially when the language model is relatively high-entropy. This process is given as Algorithm 3 we refer Approximately Aligned Decoding, or AprAD.
close each other, this prefix is
5

---

Algorithm 3 Approximately Aligned Decoding (AprAD)
procedure ApproxXAligneeDDecddngg..,, F1...))
See implementation notes in Appendix
D 21... is prompt
PB P
D Adjusted probability distribution Current token index
while Stopping condition not met do
Sample one token Tm++1 pB (-121..))
Increment
if Im... E B then
b Probabilities before update are queried and cached (Appendix pBu(*} AddBadSample PB _11...m) b -aame prob. adjustment as in ASAp b Algorithm m decreases
2 t SpecSample( (antSSamplepeeeettt pau(=)) (P) ,n,,,,nee v1..m)
pB + pBu
return LI...
procedure AddBadSample(P" PB x1)..m)) See implementation notes in Appendix-Algorihhe
b In practice, only adjust Tn++1...m
pBu(*) 4- pB
for x, (Im...., 21) do
b Note that token sequence is reversed
b Remove probability of 21... without changing probability of any other sequence pBU{=} (2rearr (rre)ar...s-1) <- pB (x:(p1..a-1) PB (I:.... Dfi...m/21.... (1...-1))
Renormalize )Bu{+) (.121...5-1)
return pBU{2}
In the running example (Figure
p(AA) (A)
2/3, so P(T() 1/2
1/3
AprAD (Ours)
AprAD keeps A in 2/3 of cases. The remaining 3 is distributed other tokens the same token index; in this case, only B.
Round 1
Round
Total
We note that AprAD still amplifies some sequence probabilities because only invokes SpecSample after discovering error. In the speculative decoding case, SpecSample would also be invoked AB was directly generated by the SSM- SSM-equivllent to Round 1 in this example-but Apr accepts AB instantly. Because the algorithm cannot iterate through every possible suf- fix string, it does not check whether AA contains an error except in the cases that AA is actually sampled, leading to AB being slightly overrepresented in the output probability distribution.
12
Figure 4: AprAD acts a mid- point between constrained decod- ing and ASAp.
The resulting amplification is significantly less compared constrained decoding, as some of the probability mass is transferred outside of the immediately neighboring sequences. Importantly, AprAD) largely avoids the most extreme cases of probability
(B) were very low, such as would arise if P(B < 0.5, the procedure amplification-iit p²(A)
would be unlikely to re-select after backtracking. This stands in contrast to constrained decoding, which always selects AB in round 2, matter the value of P(B|A).
An extended illustration of the cause of probability amplification provided Appendix In Appendix C we argue that the amplification with AprAD is bounded to a factor of 2 per each backtrack operation performed, rather than the unbounded amplification constrained decoding.
Evaluation
We first exhibit AprAD's closer adherence to the ideal distribution by simulating several environments where the ideal distribution is known in advance, Section 5.T. We additionally demonstrate that AprAD invokes the language model fewer times than ASAp.

---

In Section 5.2
we extend our results to a domain with a dense text-based error set. Finally, in Section we show that our method succeeds on task using more complex code-based constraint.
5.3
5.1
Simulated Model with Known Ideal Distribution
We construct testbench with a simulated language model that always returns one three tokens (A, B, and C) with equal probability. We mark k sequences of length 3 errors, and use the sampling method under test to sample 10000 sequences of length 3. The ideal distribution is trivial to compute- probability 27-E for every non-error sequence. To measure how a sampling process compares to the ideal distribution, we compute the KL-divergence between the observed distribution and ideal. Additionally, we include the Generation Ratio, a measure of how many times the model must be evaluated, including all backtracking, relative to output length (see Appendix A.2 for more detail).
The results are shown in Table I more closely than constrained generation, with a significantly lower generation ratio than ASAp.
indicating that our method approximates the ideal distribution much
5.2 Lipograms (Excluded Vowels)
A piece of text that avoids using given letter is called lipogram; those where the excluded letter is a vowel tend to be difficult create, especially for unconstrained L.LMs 26
We use -hirrll----nsttuutt--O... .2 [ to generate text, where generation of a given vowel is considered an error. We prompt the LLM to perform one of five simple tasks (detailed in Appendix A). Each task is appended to instructions to avoid using the given vowel, for total of 25 prompts. Each sampling method is used generate a completion of up to 200 tokens. Generation is terminated if the process reaches 2000 model invocations, and the last sequence before an error was detected is returned.
Using blind evaluation process, human raters constraint was followed. The raters also score completions on constraint following intent; i.e. if the model answers by selecting appropriate words that avoid the given letter, versus misspelling words, using lookalike or accented characters, etc. Completions that include the banned letter automatically receive the lowest constraint intent score. Additional information is provided in Appendix [
each completion on quality, regardless of if the
The results of this evaluation are provided in Table 2 and a sample of the outputs are provided in Figure 5 examples are provided in Appendix[[
All outputs and rater scores are included in the supplemental material, and additional
As shown by these results, AprAD consistently produces high-quality outputs, nearly matching the readability of unconstrained generation. Additionally, it consistently follows the intent of a constraint- while all methods except for unconstrained generation follow the constraint, constrained generation often does so in an undesirable manner, rather than by selecting appropriate words that do not contain the banned letter. Finally, AprAD is able to complete the generation or make substantial progress within the alotted computation limit, while ASAp struggles to generate more than a handful of tokens with the same inference budget.
ASAp
Constrained
AprAD (Ours)
Error Set
KL-div
Ratio
KL-div
Ratio
KL-div
Ratio
0.0014
1.000
0.0014
1.000
0.0014
1.000
AAA
0.0014
1.020
0.0075
1.000
0.0046
1.004
AAA, AAC
0.0012
1.041
0.0429
1.000
0.0157
1.013
AAA, ACC
0.0013
1.042
0.0138
1.000
0.0093
1.009
AAA, CCC
0.0010
1.044
0.0155
1.000
0.0074
1.010
AAA, AAB, ABA, BAA
0.0013
1.093
0.0504
1.000
0.0224
1.024
A# except AAC
0.0014
1.232
0.3836
1.113
0.1540
1.205
#* except AAA, AAB, ABA, BAA
0.0000
3.644
0.1771
1.670
0.0521
2.142
#8 except AAA, BAA
0.0000
5.701
0.0000
1.784
0.0000
2.653
Table 1: KL--Dvergeecce and generation ratios for simulated task with various error sets. better for both. Stars in the error set are wildcards; i.e. AB means ABA, ABB, and ABC.
Lower is
7

---

Method
Quality (1-5)
Constraint Intent (1-3)
Gen. Ratio
Constrained
3.56 0.34
2.32 + 0.18
1.00 + 0.00
AprAD (Ours)
4.52 + 0.23
2.84 + 0.11
4.20 + 0.91
ASAp
1.72 + 0.23
2.36 + 0.16
321.00 79.43
Unconstrained
4.68 + 0.17
1.00 + 0.00
1.00 + 0.00
Table 2: Lipogram evaluation results, including subjective rater evaluations of output quality and adherence to the constraint, and standard error (Ir). Higher is better for Quality and Constraint Intent; lower is better for Generation Ratio. Note that constraint intent is automatically set to 1 if the banned letter is detected in the output. Generation is stopped after 2000 model invocations and the output provided as-is; for ASAp. this often resulted in very short outputs and thus extreme generation ratios and low quality scores. Several raters interpreted these short outputs as violating constraint intent.
Summarize the history of artificial intelligence without using the letter "A". AprAD (Ours)
The history of intelligent technology unfolds through key milestones in computing. In the mid-20th century, pioneering minds nurtured the seeds of this field through the development of logistic models, which evolved into expert systems in the 1960s. These systems, relying on heuristics, could solve complex problems in fields like medicine or meteorology.
Summarize the history of artificial intelligence without using the letter "A". Unconstrained
In the early days, brilliant minds pondered on creating machines that could mimic human intelligence. These pioneers, including Alan Turing and Marvin Minsky, theorized and experi- mented. They aimed to create intelligent machines, using logic and mathematics.
Summarize the history of artificial intelligence without using the letter "A".
ASAp
History of Intelligence
Summarize the history of artificial intelligence without using the letter "A". Constrained
In the mid-20th century, scientists delved deep into investiging computionl modeles for intel- ligencen modeled on the workings of the brn. Pioneers such кak E.N. Turing, Cirk Quincy Shrffngton, ynddd W. Ross Quilp, and Marvin Minsky led ths fld. They explored logic-gated programs, thm brgth mehr to If understnding the cptures of th gnntl mind.
Figure 5: Representative generation samples for all four methods, using Mistral-7B. II--nnsttutt-O.. Appearance of the banned letter is bolded, and non-ASCII characters (all Cyrillic in this example) are colored red and underlined. Full samples are provided in Appendix [
5.3 BigCodeBench Hallucination Avoidance
API ballucination avoidance represents a significantly more complex constraint- instead of using standard string operations to detect lipogram constraint violations, hallucination avoidance depends on a program's 's imports, variable assignments, the local installation environment, etc.
We evaluate the effectiveness of each error-free sampling method code generation task, where the generator avoids API hallucinations. We use a wrapper around the Pyright language server [20] to detect hallucinated API calls in partial Python programs, with moderate prot-proc such that the detector tends towards false negatives rather than false positives. For example, even if name foo is never defined, the detector does not consider the incomplete program "example bfo".bar" an bar"
error, because it is possible to later add text that binds foo, such as "for foo in baz)". Text where hallucination is detected by this program is designated as error.
The methods are compared based on their performance on BigCodeBench v0.1 336. a benchmark that focuses on practical programming tasks, often requiring the use of common libraries
2 BiggCoeBench uses the Apache 2.0 license. We observed instances where unconstrained LLMs use libraries present in the testing environment that aren't explicitly imported in the prompt. To better align the generation environment with the testing environment, add all imports present in the testing environment the prompt.
8

---

For all sampling methods. we use Starcoder2 [17] in the 7B and 15B model sizes. We generate 5 samples for each task, with temperature 0.8, and a top-p of 0.95. In addition to evaluating the pass@) and pass@5 @ rates on execution-basee tests, we log the specific error if execution fails. A NameFrror or Unboundl LnnoundIoocalErroo LocalError indicates that the generation included an hallucinated API call, so we track the rate at which these errors do not occur. Several errors, such as AttributeError, may indicate either a hallucination or a logic error (such as improper None values), so we exclude such ambiguous errors.
Note that all methods use the same random seed, so the outputs only diverge when the detector activates. Table shows the results for all tasks where the outputs diverge; Table 4
(Appendix) also includes tasks for which all methods return identical results. As the results show, the pass rate of AprAD is higher than constrained generation, with much lower generation overhead than ASAp.
Size
Method
Pass@1
Pass@5
INameErr@ 1
!NameErr@5
Gen. Ratio
Unconstrained
0.21 0.01
0.50 0.01
0.83 = 0.01
1.00
0.00
1.00 = 0.00
AprAD (Ours)
0.26 - 0.01
0.54 + 0.01
0.98 + 0.00
1.00 + 0.00
1.08 = 0.01
15b
ASAp
0.26 + 0.01
0.54 0.01
0.98 = 0.00
1.00 + 0.00
1.56 = 0.12
Constrained
0.22 + 0.01
0.51 + 0.01
0.93 + 0.01
1.00 + 0.00
1.02 + 0.00
Unconstrained
0.12 + 0.01
0.35 + 0.01
0.80 = 0.01
0.99 + 0.00
1.00 = 0.00
AprAD (Ours)
0.14 0.01
0.38 = 0.01
0.95 = 0.01
0.99 - 0.00
1.06 = 0.01
7b
ASAp
0.15 - 0.01
0.39 0.01
0.95 - 0.01
0.99 0.00
1.47 = 0.07
Constrained
0.12 0.01
0.35 + 0.01
0.89 + 0.01
0.99 + 0.00
1.02 + 0.00
Table 3: Subset of tasks where at least one trial results in different output for any method: 233 tasks (20.4%) for 15b, 304 tasks (26.7%) for 7b. For both model sizes, of the tasks where at least one model output is different, average of 1.5/5 outputs are different. Lower is better for generation ratio; higher is better for all others. AprAD approaches the task performance of ASAp, with a generation ratio close to that of constrained generation. Ratio includes standard error (1r). See Appendix A.2
Discussion
As introduced in Section 3 there several approaches control the output of LLM. We further discuss considerations when selecting a specific method.
6.1 Posterior Iilimattoo-Based Methods
While posterior estimation-be bassed techniques excel at many tasks, they tend struggle when the probability of a constraint violation does not necessarily depend on a given text prefix. For example, the probability of LLM generating long sequences of text without the letter 'e' is close 0 regardless of the prompt or prefix, and mostly depends on the arbitrary behavior deep within a language model. It is unlikely that a learned discriminator or a hidden Markov model would capture this constraint, and it would require an extraordinary number of Monte Carlo samples to accurately calculate the posterior probability.
In contrast, code generation may be a more appropriate domain for posterior-estimation based methods. For example, misleading comment that mentions specific method all but ensures that this method will be generated on the next line. FUDGE may be able to learn that a LLM is more likely to hallucinate in some domains or with specific libraries. SMC Steering could work with sufficient number of Monte Carlo samples, although this may be computationally expensive. For Ctrl-G, a large enough HMM could plausibly capture some of the conditions that lead a hallucinated API call. However, neither FUDGE nor Ctrl-G would be able to quickly adapt to changes in the local environment or task.
6.2 A Spectrum of Sampling-Bane Based Methods
Sampling based methods are able generate text that does not violate a constraint, in domains where it is difficult to estimate the posterior error probability. As discussed in Section 4 the sampling behavior of AprAD lies at midpoint between constrained generation and ASAp
user may wish for even further granularity in the conformance-speed tradeoff of sampling-basee methods. We propose new hyperparameter, h, and modify Line 3 of Algorithm 2 by setting to

---

P(a.les...-1) controls the probability that specific token in the prefix is kept after violation S(
occurs. When / = 1, this is equal to unmodified AprAD, When / = 0, r will always equal 1-this equal constrained generation. As oo, r will approach 0-this approaches the behavior of ASAp. We conjecture that values between these extremes allow for fine-gr grained control of the conformance-speed tradeoff, though we leave more comprehensive analysis future work.
6.3 Search Algorithms
We note that while AprAD excels at generating text that excludes an error set, it will not necessarily drive the generation process towards a specific solution. For such domains, it may be beneficial to combine our method with a search algorithm. For example, in theorem proving context, MCTS-like process could be used to direct a higher-level search, while AprAD is used for generating text that does not contain invalid tactic applications. We leave these combinations future work.
7 Limitations
While our method enables generation in new domains, it still exhibits measure of probability amplification, and additional overhead compared to constrained generation. On even denser error sets, it may be necessary to use constrained generation, possibly the modification proposed in Section Additionally, due to variations in testing environments and code optimization levels, our main performance metric was generation ratio rather than wall-clock time.
6.2
8
Conclusion
As experiments show, Approximately Aligned Decoding is effective method to generate sequences under dense language model constraints. is straightforward to implement, requires no separate training step, introduces manageable amount of inference overhead, and performs well variety real-worke and synthetic tasks.
References
[1] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. 2025. Controllable Generation
via Locally Constrained Resampling. In The Thirteenth International Conference on Learning Representattinns International Conference on Learning Representations, Singapore, 10 pages. htttps://openrevies. wttpeeeee...eeoorrrrr//aaaaaaaa
[2] Anthropic. 2024. Meet Claude. https: Setps://wwur www.:aaahrppccccoocccecmo com.ccaudeccee
[3] Ben Athiwaratkun, Shiqi Wang, Mingyue Shang, Yuchen Tian, Zijian Wang, Sujan Kumar Gonugondla, Sanjay Krishna Gouda, Rob Kwiatowski, Ramesh Nallapati, and Bing Xiang. 2024. Token Alignment via Character Matching for Subword Completion. arXiv:2403.0868 [cs.CL]
[4] Automorphic. 2023. Trex. automorphic-ai.
[5] AWS, Inc. 2024. AI Coding Assistant Amazon Q Developer AWS. sctps://aws amazon com/q/developen
[6] Luca Beurer-Kellned Mare Fischer, and Martin Vechev. 2024. Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation. arXiv:2403.06988 [cs.LG] //trs://arxiv.r org/ abs/2403.0693
[7] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D. Lee, Deming Chen, and Tri Dao. 2024, Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. arXiv:2401.10774 [cs.LG] https://arxiv http:///wwwwraab///.....11
[8] Darryl Francis. 2020. The Scunthorpe Problem. Word Ways 53, 2 (May 2020), pages.
hwteeeonnssuuuttteeeeeeeeee butler www.er..eeteeeeeee....e. /ut.aerr.ee///oookaarrr/////////
10

---

[9] Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2024. Grammar- Constrained Decoding for Structured NLP Tasks without Finetuning. arXiv:2305.1397 [cs.CL] https
7/arxiv. org/ abs abs/2305 2305 13971
[10] Github, Inc. 2023.
GitHub
Copilot
Your
AI
Pair
Programmer.
[11] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lu- cile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William EI Sayed. 2023. Mistral 7B.
MtXiv:2310.0682 [es.CL] httpp://arra http://aaxvvv... wwt.oorg////bbeeeeee 06825
[12] Evan Jones. 2023.
Llama http://ssttbbb.mommgggggg/////ap
Add
Grammar-Based
Sampling.
[13] Yaniv Leviathan, Matan Kalman, and Yossi Matias. 2023. Fast Inference from Transformers via Speculative Decoding. arXiv:2211.1719 [cs.LG] atttp://aaxxvv.orr//bb/////22
[14] Alexander K. Lew, Tan Zhi Xuan, Gabriel Grand, and Vikash K. Mansinghka. 2023. Se- quential Monte Carlo Steering of Large Language Models using Probabilistic Programs. MiXiv:2306.0300 [cs.Al] htttss:/ hrwp:.org//aaaa Swrggabbs/3300 03081
[15] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang, 2024. EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees. arXiv:2406.16858 [cs. [Cs https://arxiv
org/ aabs/2406 16858
[16] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2024. EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty. arXiv:2401.15077 [cs.LG] https://
arxiv.org/abes
15077
[17] Anton Lozhkov, Raymond Li, Loubna Ben Allal, Federico Cassano, Joel Lamy-Poirier, Noua- mane Tazi, Ao Tang, Dmytro Pykhtar, Jiawei Liu, Yuxiang Wei, Tianyang Liu, Max Tian, Denis Kocetkov, Arthur Zucker, Younes Belkada, Zijian Wang. Qian Liu, Dmitry Abulkhanov, In- draneil Paul. Zhuang Li, Wen-Ding Li, Megan Risdal, Jia Li, Jian Zhu, Terry Yue Zhuo, Evgenii Zheltonozhski,, Nii Osae Osae Dade, Wenhao Yu, Lucas Krauiš, Naman Jain, Yixuan Su, Xuanli He. Manan Dey, Edoardo Abati, Yekun Chai, Niklas Muennighoff, Xiangru Tang, Muhtasham Oblokulov, Christopher Akiki, Mare Marone, Chenghao Mou, Mayank Mishra, Alex Gu, Binyuan Hui, Tri Dao, Armel Zebaze, Olivier Dehaene, Nicolas Patry, Canwen Xu, Julian McAuley, Han Hu, Torsten Scholak, Sebastien Paquet, Jennifer Robinson, Carolyn Jane Anderson, Nico- las Chapados, Mostofa Patwary Nima Tajbakhsh, Yacine Jernite, Carlos Muñoz Ferrandis, Lingming Zhang, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. 2024. StarCoder 2 and The Stack v2: The Next Generation. 1XV1:2402.11113 [cs.SE] https://arxiis org/ / 19173
[18] Daniel Melcer, Nathan Fulton, Sanjay Krishna Gouda, and Haifeng Qian. 2024. Constrained Decoding for Code Language Models via Efficient Left and Right Quotienting of Context- Sensitive Grammars. arXiv:2402. 12000...9998 17988 [cs.PL.] https::/arxxe http:/aawvvv.../aa//// abs /402 17988
[19] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, Chunan Shi. Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. 2024. SpecInfer: Accelerating Large Language Model Serving with Tree-based Speculative Inference and Verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume (ASPLOS '4). ACM, San Diego, USA, 13 pages. https
//doi.org//l 10000.1155//00 1145/3620666 0366666666666333336333333333333. 3651335
[20] Microsoft. 2019, Pyright.
http::://githubb.cmm//ccccco/
[21] Microsoft. 2023. Guidance. Microsoft.
[22] Microsoft. 2023, TypeChat. http://microooft.gittiei To/TyyeChatt/

---

[23] OpenAl. 2024. ChatGPT.
[24] OpenAL. 2024. Introducing Structured Ouiputs in the API. http:://ppenaa..om//inee/
[25]
Kanghee Park, Jiayu Wang, Taylor Berg- Nadia Polikarpova, and Loris D'Antoni. 2024. Grammar-Aligned Decoding. arXiv:2405.21047 [es.Al] https://arxiv. org abs/
21047
[26] Allen Roush, Sanjay Basu, Akshay Moorthy, and Dmitry Dubovoy. 2023. Most Language Models can be Poets too: An AI Writing Assistant and Constrained Text Generation Studio. arXiv:2306. 15926 [cs.CL] https: //rxiiv///xi..////// org/ aataabbb/222// 15926
[27] Rahul Sengottuvelu. 2023. Jsonformer: A Bulletproof Way to Generate Structured JSON from Language Models.
[28] Grant Slatton. 2023.
Added Context Free Grammar Constraints Grantslat-
https://github. com//grantslaatto/llaaaaa http://laaaaappppcoc.ccaccc cpp/commite 0TT26991450017797788844333888880
www/llama.Cpp@007/0
[29] SRI. 2023. LQML. SRI Lab, ETH Zurich.
[30] Wannita Takerngsaksiri, Chakkrit Tantichamthavrnn and Yuan-Fang Li. 2023. Syntax-Aware
On-the-Fly Code Completion. arXiv:2211.04673 [cs]
[31] Vivien Tran-Thien. 2024. ulative Decoding. -osemll-oosy-aaaali
Optimal
Lossy
Variant of Spec-
viviie/
of www.-seeelaaavveeeooiiea.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2023. Attention Is All You Need. arXiv:1706.03762 [cs.CL]
https: /tte::///xxxi orggii.orr//aoo abs 1ates/1066.000 03762
[33] Brandon T. Willard and Rémi Louf. 2023. Efficient Guided Generation for Large Language
Models. arXiv:2307.09700 [cs.CL]
[34] Kevin Yang and Dan Klein. 2021. FUDGE: Controlled Text Generation With Future Discrimina- tors. In Proceedings of the 2021 Conference the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Lin-
guistics, Virtual, 351 3-11-3535.
https: / /oi org 18653/ 11111/////0211111.1///// htap://v.22....aalaa.aaaa nwacl main. 276
[35] Honghua Zhang, Po-Nien Kung, Masahiro Yoshida, Guy Van den Broeck, and Nanyun Peng. 2024. Adaptable Logical Control for Large Language Models. #rXiv:2406.1389 [cs.CI] CL] https://arxtie org/ abs/2406. 13892
[36] Terry Yue Zhuo, Minh Chien Vu, Jenny Chim, Han Hu, Wenhao Yu, Ratnadira Widyasari, Imam Nur Bani Yusuf, Haolan Zhan, Junda He, Indraneil Paul, Simon Brunner, Chen Gong, Thong Hoang, Armel Randy Zebaze, Xiaoheng Hong. Wen-Ding Li, Jean Kaddour, Ming Xu, Zhihan Zhang, Prateek Yadav, Naman Jain, Alex Gu, Zhoujun Cheng, Jiawei Liu, Qian Liu, Zijian Wang. David Lo, Binyuan Hui, Niklas Muennighoff, Daniel Fried, Xiaoning Du, Harm de Vries, and Leandro Von Werra. 2024. BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions. wxXiv:2406.1887 [cs.SE] https
7/arxiv. org hss//bbs/22466 15877
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Analysis of existing methods in Sections 3 6 Method is presented in Section Experimental support in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings,
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Discussion in Section 7 well error assumptions in Section 3
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
13

---

Justification:
Paper is primarily empirical.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided by formal proofs provided in appendix or supplemental material.
core of the paper should be complemented
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yss]
Justification: Open-weight models were used, datasets are fully described, sampling parame- ters are provided in Section 5 additional implementation details in supplemental material
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [No]
Not possible at this time, but extensive implementation details are described in appendix.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Sublic//uuides//odeSttbbii coc for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Described Section and appendix. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All experiments report la SEM when relevant. Pandas library function used to calculate error. Distribution of errors is unknown.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpst/pp///acree..cc//////////t
Answer:
[Yes]
Justification: Research ethics were followed.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consider- ation due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: While our method discusses generative AI, it does not present forseeable direct path to negative applications beyond those already well-known regarding LLMs.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
Paper does not release data or models with high misuse risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: BigCodeBench is cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papprssiiiiii thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [Ye]]
Justification:
Crowdsourcing was not used. Details about human rating provided in Appendix
A.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Paper did involve risks humans.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
Justification: LLM usage described in methods section.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to LLM for what should or should not be described.
19

---

A Lipogram evaluation details
We provide the following prompts to the language model, as well as the relevant special tokens to delimit user instructions and chat turns.
1. Write story without using the letter "[A/E//O//J]"
2. Describe elephants without using the letter "I "[A/E//OO/J""
3. Provide instructions to tie tie without using the letter "[A///////J""
4. Critique the Mona Lisa without using the letter "|A/E///O/UJ"
5. Summarize the history of artificial intelligence without using the letter "[A/E///O/J""
Each prompt combined with each vowel, resulting in 25 prompts. With four sampling methods, this results in 100 total generations.
top-k of 20, and temperature of 0.8. 200 tokens chosen short enough to be quickly read by the human raters, and long enough to discern the sample quality. 2000 tokens was chosen 10 times the output length, to prevent infinite computation.
During sampling,
A.1 Rater Instructions and Details
We create file that only contains the 100 prompt- prompt-completion pairs, without information on which method generated each completion. All samples are shuffled in random order.
We selected four AI research colleagues not otherwise directly involved in the implementation or experimental evaluation of this method as human raters, to evaluate 25 samples each. The labels of which method corresponded to each output were hidden from the raters. We provided the following instructions to the raters:
This file contains set of prompts, and responses using one of several methods. Each prompt contains constraint to not use specific letter. Irrespective of whether the response follows the constraint, rate the response quality the "Score" column, noting that generation is always cut off after 200 tokens. Additionally, rate how well the response follows the intent of the constraint in the "Follows Intent" column. Examples of not following the intent include working around the constraint by excessively dropping letters, using unnecessary accents, writing Unicode lookalike letters, or responding in foreign language, rather than through selecting appropriate words that satisfy the constraint. This column is pre-filled with 'X' if the output contains the banned letter. Otherwise, write if it violates the intent, 2 if it is ambiguous, and 3 if it does not.
scale of 1-5 in
We additionally highlighted the presence of non-ASCII lookalike letters to the human raters. The complete model outputs, and the scores that each rater assigned, are provided in the supplementary material. Additional example outputs are provided in Appendix
A.2 Generation Ratio
The computation time for all methods is dominated by LLM evaluation time. This time is highly sensitive to variations in the testing environment and specific implementations, so we selected generation ratio more portable and accurate comparison between methods.
Generation ratio measures the total number of LLM invocations compared to the final output length, including all backtracking, For example, if given sampling method generates 9 tokens, backtracks to token index 7, re-uses the computed probabilities to select a new eighth token, and then generates more tokens to obtain 10 tokens in all, the generation ratio is 1.1 (11 model invocations for 10 output tokens).
We note that for the BigCodeBench results, a data error caused the denominator of the generation ratio to reflect the number tokens the output after converting from tokens, to text, back to tokens, rather than reflecting the original number of generated tokens. This causes the generation ratios to vary slightly from their true value (usually by 0.001-0.005); be overly conservative, we truncate the ratio to two significant digits after the decimal. Ratios for other experiments are not affected by this.
20

---

AprAD (Ours)
Speculative Decoding
Round 1
Round 2
Total
SSM
Main Model
Total
1
12
3
1
1
24
24
3
(a) AprAD Probability Distribution (from Figure
4
(b) Speculative Decoding Probability Distribution.
Figure 6: Comparison probability distribution between AprAD and Speculative Decoding
B Extended Example of Probability Amplification
We further illustrate the cause of probability amplification, despite using the speculative decoding algorithm, through an extended example.
Consider the running example in Figure 6 In the first round, there is 1 probability each of selecting sequence AA, AB, BA, or BB.
In the case where AA is selected, AprAD has identical behavior to speculative decoding where P is the speculative model and p(A*) is the main model; SpecSample is invoked in both cases. We note that in cases where [B] > 1, after the first round, AprAD has still only observed one element æ of and thus must invoke SpecSample with p(#} rather than with PB
In the case where AB is selected, the behavior is completely different. With speculative decoding, it is still the case that (A) < P(A), leading to potential backtrack. With AprAD however, since non-violating sequence is found, the process terminates the process has no mechanism to discover PB other than through encounters with elements of B.
With both BA and BB, the speculative decoding process accepts the SSM's output because ps Z P(B), PB (AA B) 2 P(A B), and, p () 2 P(B]B). AprAD also accepts these sequences immediately, as both sequences non-violating.
Summary. The probability amplification AprAD occurs due to the cases where SpecSample not invoked.
C Bounding the Probability Amplification Factor
While the following sketch not a rigorous proof, we argue that the probability amplification due to AprAD is at most 2 per iteration of the algorithm.
For sequences
.i..... F. and y ....... Vm. let SRS(y) S, P) (SpeculativeReeSanple) be the probability of eventually selecting sequence with speculative decoding, conditional on having drawn x from speculative model S.
Speculative Decoding Identity.
The original concept of speculative decoding relies on the identity Eeex- SRS() jz, S, P) probability of selecting y with the main model P should
P(y) E be equal to the probability of selecting using the speculative decoding process.
SRS Subset Inequality.
C B, then SRS( x, S, pa) < SRS(y) (*) fory B. Intuitively, excludes more invalid sequences compared to PB so the probability mass of these sequences during the re-sampling process should be distributed among all non-error sequences, including
Generation Subset Inequality. For similar reasons, pb) < (z)(x) for B C B, & B, as excluding additional errors B and re-normalizing the probability means that all other sequences become more likely.
21

---

The probability of sequence & B being generated after the first iteration of AprAD is equal to the probability that y is generated directly, plus the probability that y re-sampled after some invalid sequence is generated:
Apr AD P(y) + Σ ((0)SRS((le,P.P(..)
ZEB
We apply both of the subset inequalities described above:
s (B) Σ P())sSsyyl,,
As P(x) and SyS(y) P.P.. (8) are always nonnegative, we can add additional elements to the sum expanding it to include all sequences, rather than just error sequences- while maintaining the inequality:
S (1)+ Σ
((o) P. PB)
BEE*
And finally use the speculative decoding identity:
S 22)BBy)
Note that this amplification is per-iteration, where iteration is defined encountering error sequence, potentially backtracking, and resampling. practice, the per-iteration amplification is likely much less, as several of the inequalities involved are very loose. However, there may be cumulative effect as more iterations are required dense error sets.
In contrast, the probability amplification after encountering even single error sequence with con- strained decoding is unbounded, as the best non-error token may have arbitrarily low probability.
D
Additional BigCodeBench Results
Size
Method
Pass
P
:NameFrr@)
INameErr@5
Gen. Ratio
Unconstrained
0.31 + 0.01
0.58 + 0.01
0.95 + 0.00
0.99 = 0.00
1.00 = 0.00
AprAD (Ours)
0.32 + 0.01
0.59 + 0.01
0.98 + 0.00
1.00
0.00
1.02 = 0.00
15b
ASAp
0.32 + 0.01
0.59
0.01
0.98 + 0.00
1.00
0.00
1.11 + 0.02
Constrained
0.31 + 0.01
0.58 + 0.01
0.97 0.00
0.00 1.00
1.00 0.00
Unconstrained
0.20
0.47
0.93 0.00
1.00 1
AprAD (Ours)
0,21 1 0.01
0.47 0.01
0.97 1 0.00
0.99
0.00
1.02 1 0.00
7b
ASAp
0.21 1: 0.01
0.48 1 0.01
0.97 1: 0.00
0.99
0.00
1.13 1 0.02
Constrained
0.20 + 0.01
0.47 + 0.01
0.95 + 0.00
0.99
0.00
1.00 = 0.00
Table Results for each method on entirety of BigCoodeencc.. Note that these results are identical
to those in Table 3 except that they consistently offset and scaled to include values for tasks in which all tasks return the same result.
Table 4 includes results for the entirety of BigCodeBench; not just the tasks for which the methods diverged in their output.
E
Generalization of Error-Free Decoding
Constrained generation, ASAp, and AprAD may all be generalized by their backtracking behavior after error is discovered. Algorithm shows this generalization.
22

---

Algorithm 4 Multiple error-free decoding methods differ only their backtracking selection.
procedure ErrFreeDec(P, B1..... Strategy)
pB P m c n
b Current token index
while Stopping condition not met do
Sample one token 2m+11 pB (-121...m)
Increment
if 1i... E B then
b Algorithm 5
pBu(2) t AddBadSample PB .....)
D m may decrease
L1...m f- Strategy (PB (BBtz) .....)
PB {Bu(a)
return m...m
procedure AprADStrategy(PE, pButtt al...)
Algorithmm
return SpecSample( PB pBU(a), O, x1..m)
procedure ASApStrategy(Pr: pBu(a)) 1l..m)
return
-Backtrack beginning
procedure CoustrainedDecodnggStaaine (BB pBu(e), f1.mm
Delete error token but don't tt backtrack further
return T m-
Method
Overbead +
Dist. Conformance
Constraint Class
Posterior Estimate
AprAD
Medium
Medium
Black Box
Not Required
ASAp 25
High
High
Black Box!
Not Required
Construined (Multiple)
Low
Low
Black Box
Not Required
FUDGE S+
High
Prefix- Depeeeeednd"
Learned Discriminator
SMC Steering 14
Hlgh
Highh
Black Bux"
Sample Many Rollouts
Ctrl.G 35
Low?
Highh
Represent as DFA
Exact in distilled HIMM
Oracle classifies whether given outpur violates constraint.
Requires additional one-time triniig step per task.
Conditional
distilled model perfectly capturing behavior.
Requires that is possible to determine probahility of constraint violation from incomplete prefix.
Table 5: Overview of several methods for controllable generation with LLM,, with subjective estimate of inference overhead and conformance to the LLM's original output distribution, and a brief' description of constraint expressivity and method of posterior estimation.
F Method Comparisons
An overview comparison of several methods presented in Table
G Compute Resources
Computation time was not precisely tracked during preliminary or final experiments: several experi- ments ran in parallel, resulting in high variation of inference speed. Inference time was dominated by the BigCodeBench trials (1 140 tasks, methods, models, trials per model 45600 generations. Order of magnitude of 10 output tokens per trial, resulting in about 10" 10ah output tokens). This took about a day or two on an AWS p4d.24xlarge instance. The lipogram task was comparatively much less resource intensive, with 25 prompts, models, and 200 output tokens per prompt, with higher generation ratio than BogCoce resulting in about 10a 10 model invocations, The simulated testbench experiments run in seconds to minutes consumer laptop.
23

---

H
Implementation Details
We provide notes related to our implementation the methods discussed in this paper. particular, floating point error accumulation was major source of issues due to invariants breaking late in the generation process; we note where recalculations may be required to avoid this.
H.1 ASAp
implementation of ASAp provided in Algorithm
Algorithm 5 ASAp [25
procedure AS, B,, v1...)
D Dr... is prompt
pB P while Limit reached do Sample sequence Un+ I..m
PB (-1x1....) until error or stopping condition
if I1..m m $ then break b Remove I1... possible sequence
p8 +- AddBadSampleeP 11..
return X
H.2 Trie-Structured Probability Cache, AddBadSample, and Cached Probabilities
After each token probability distribution is generated from the language model, we add trie structure to represent PB efficiently.
The node representing prefix #1... contains the following:
A single token Zm, and pointer to a parent node representing 21...m-1
The original probabilities generated by the LLM P(-la1..m).
The modified conditional probabilities PB (+)a)...)
Due floating point implementation issues, and for efficiency purposes, we store these modified probabilities un normoaaalzee; i.e. we store table pB* (+|21...) where
Σemtie P (Im+1 11...m < 1.
We track this sum variable, f. and divide the un-normalized probabilities by as necessary to obtain normalized probabilities when queried. When f is small, and likely suffer from accumulated floating point errors, we periodically recalculate it by summing the pB* table.
Additionally, when an entry of PB* is sufficiently small, or becomes negative, we assume that its value is zero, but has excessively suffered from accumulated floating point errors; we therefore set to zero.
This structure allows for efficient implementation of AddBadSample, given in Algorithm 6 The same trie structure is also used to track the adjusted probabilities for the comparison methods.
H.3 Backtracking Strategies
Our implementation uses essentially same structure as detailed in Appendix where it is parameterized by a backtracking strategy. However, it would be complex to maintain full probability tries representing both pB and pBu(z) every time violating sample is found. We observe that unnecessary to do so; rather, we only need both probabilities along the "path" the violating sample; ie. f (x,)) f (x2(2)1))
f (1)........)).. Therefore, we invoke CollectProbabilities (Algorithm 7 before calling AddBadSample.
The SpecSample algorithm is used nearly unmodified, except that iss given by the adjusted conditional probabilities in the tric, and S is given by the cached list collected by Collectrrobabiittees

---

Algorithm 6 An iupleementation-oriencee description of AddBadSample procedure AddBadSample(Node n)
P n. represents a violating sample
t f n.token
c + n.porent
Current node
while is not null do
> Calculate as probability of violating sample in c, in original distribution
T+r x (t)
c.PBa(1) cBPB(()
c.f + c.f-r
Recalculate e. as sum of c. if needed due to FP errors
1 r c.loken
c c.parent
Algorithm 7 Collect all probabiliticss along path
procedure CollecdProabilltiesNNoeee m)
t + n.token
n.porent
Current node
- []
while is not null do D Calculate r as probability of violating sample c, in original distribution
(p c.f x c.)B((t)
t t c.token
C - c.parent
return Reverse(o)
We make one modification to constrained decoding, necessary due to of top-p sampling such that there may not always an available token that satisfies the constraint the next step. the current leaf node the probability trie has no non-zero entries f.. then our implementation of constrained decoding will backtrack until there is at least available continuation.
I Additional Lipogram Examples
The following pages contain generations from 10 random prompts of the lipogram task. The examples are not cherry-picked. If the banned letter appears-this occurs in all unconstrained examples, and no other method-it is bolded. Non-ASCII characters are underlined and highlighted in red. We include 
 where the language model chooses to stop generation; otherwise, was cut off after 200 tokens or 2000 model invocations, whichever occurred first. Generations from all prompts are available in the supplemental material.
25

---

Provide instructions to tie tie without using the letter "I".
AprAD (Ours)
To create an elegant neckwear look, follow these steps to adorn your collar:
Gather your tools: Choose a well- Press your collar down and adjust the top button.
2. Select the perfect knot: There are many knots to choose from; select a preferred one.
Dress your end: Take the end nearest to you and form loop, called the "small" or "narrow"
end.
Create an overlap: Cross the longer end, called the "large" end, over the loop.
5. Form second loop: Take the small end and make another loop.
Create a "V" shape: Place the large end over the two loops. Adjust for symmetry.
7. Repeat: Cross the small end over the large end, then the large end over the small end to create
a "V" shape once more.
8. Tuck and adjust: T
Provide instructions to tie tie without using the letter "T".
Unconstrained
To create an elegant necktie knot, follow these steps:
1. Lay the tie flat the table with the wide end (the end you'll II be tying first) facing you. The thin end (the side you'll IIl be attaching theshirt) should be hanging on the left.
2. Cross the wide end over the thin end and bring it behind the looped thin end.
Now, pass the wide end over the looped thin end from left to right, going around the back the necktie.
4. Keeping the wide end behind the looped thin end, cross it over to the left side and bring front of the looped end.
Now, the wide end should be on the left and the looped end on the right. Cross the wide end over the looped end again the right side.
6. Pass the wide end under
Provide instructions to tie tie without using the letter "T".
ASAp
To create
Provide instructions to tie tie without using the letter "I".
Constrained
To create an elegant necktube knot for your formal att attar, follow these steps:
1. Lay the necktube flat on the table, end towards you.
2. Fold one end about four to four and a half ыиches (10-12 cm) over the other end.
Create loop, called the "small loop," by fold the part of the necktube above the folded end,
about two to three иисhеe (5-7.5 cm) down.
4. Create a second loop, called the "large loop." " by fold the part of the necktube around your
neck, and rest the large loop over the small loop.
Tuck the end the necktube under the large loop, then the small loop.
6. Pass the end of the necktube under the small loop and through the hole created by the knot.
Tug on
26

---

Provide instructions to tie tie without using the letter "O".
AprAD (Ours)
1. Begin with the tie unwinded and the widest end (the "bracelet end") tucked under the neckband.
2. Bring the wider end (the "tie end") behind the neckband, then tuck it under the bracelet end and pin place with thin fabric "shelf" called the "keeper." "
3. Create "Wing Tip" by lifting the neckband and slipping the tie end under it, then pull it up evenly and adjust the width until it's level with the bracelet end.
4. With the tie end still held in place with the neckband, create "Shelf" by lifting the bracelet end and passing the tie end beneath it, then adjust the tie width again by pulling the tie end evenly.
Create a "Three-inch rule" by sliding the bracelet end up three inches (7.6 cm
Provide instructions to tie tie without using the letter "O".
Unconstrained
1. Begin by laying out your tie on a flat surface with the wide end, known as the "tail," facing
you. The narrower end is called the "Tip."
2. Cross the Tip over the Tail from left to right.
Bring the Tail around the back of the neck and cross over the Tip.
4. Now, take the Tip and thread it under the loop created by the Tail.
Pull the Tip up through the loop.
6. Adjust the position of the Tip and Tail to achieve symmetrical knot.
Repeat the process on the other side, crossing the Tip over the Tail, bringing the Tail around the back, threading the Tip under the loop, and pulling it through.
With both sides adjusted, adjust the knot one final time to ensure a neat and symmetrical look.

Provide instructions to tie tie without using the letter "O".
ASAp
Provide instructions tie tie without using the letter "O".
Constrained
Begin by laying the necktie flat in figure eight shape. The wide end (called the "butt end") will be anchered at the left side, and the thin end (called the "tip end") will be adjusted at the right side.
2. Bring the right side (the side with the tip end) up and behind the left side, creating a "U" shape, then pull it straight up and tuck the tip end under the wide part the nape (the back part) near the center.
Next, bring the left side up and pass it (the wide end) behind the neck, then pull it straight up and rest it against the right side.
With the left side still in hand, take the right side (tip end) and bring it up and pass behind the left side.
Tuck the tip end behind and under the wide part (where the
27

---

Write a story without using the letter "E".
AprAD (Ours)
In quaint, old-world town, a mystical story unfolds. A solitary knight, Sir Gavr, hails from a distant land. His mission was vital, as his king had sought his aid. monstrous dragon, with a long, sinuous form, had laid claim to bountiful land.
Sir Gavr, galloping through twisting hills and past lilac valms, his stallion, Swiftpaw, carrying him swiftly. Through woodlands dark and mossy, path narrow and winding. His armor glinting gold, radiant sight, as knight and mount, in rhythmic flight, cut through air, crisp and light. A labyrinth of hills and hollows, Sir Gavr and Swiftpaw, onward bound. A looming mountain, daunting sight, as dragon's s lair, a
Write a story without using the letter "E".
Unconstrained
In quaint, old-world village lived a wise artisan named Gobo. His humble abode was nestled 'twixt grove of towering, verdant trees. His days were passed in crafting intricate, exquisite pottery pieces, each more beautiful than the last.
Gobo sourced clay from nearby stream, where its cool, crystalline waters danced over smooth, mossy pebbles. The sun, golden orb, bathed the clay in warm hues before Gobo shaped it with skilled, nimble fingers. wheel, spun by muscular arms, transformed the malleable substance into symmetrical rounds.
Once shaped, pieces were set to dry under the clear, azure sky. With patience, they transformed into delicate, hardened creations. With deft strokes, Gobo adorned pots and bowls with intricate,
Write story without using the letter "E".
ASAp
Write a story without using the letter "E".
Constrained
In quaint, old-world town, N, a kindly cobblep, dwlt with his donk mulk. His daily task was to mak sho'd that N's villagrs' shojs staid sound. With nimbl fingrts and skillful hand, smotd, nwd, and polisht prgrssvly.
Bys N's humbl abod, a gldng fountain splshd light thru wndw shds. It was a gif frm hm t Ols N., N's fav old fnd, who hd lvd ths tow n yrs ag.
Today, though, N fnd difrit to wk. Hs thmb, hnd, awoy aggrv, paining hm wih sharp, stng
28

---

Describe elephants without using the letter "O".
AprAD (Ours)
Elephants are large, gray, thick-skinned pachyderms, characteristically having extended, curved tusks, and fan-shaped, large ear structure. They are the largest living terrestrial animals, with distinct, massive build. These gentle giants have wrinkled visage, and large, dangling, gray, prehensile ears, which are effective at dissipating heat. The trunk, lengthy, muscular, and versatile appendage, is an integral feature, serving multiples uses, including breathing, grasping. and trumpeting. Their legs are pillar-like, ending in large, flat feet, which help them maneuver in diverse terrains. Their size and strength make them apex terrestrial animals, and they are crucial elements their respective habitats. 

Describe elephants without using the letter "O".
Unconstrained
Elephants are large, gray, thick-skinned pachyderms, known for their long, curved tusks. They are the largest land animals, reaching up to feet in length and 10 feet height the shoulder. With strong, sturdy legs, they support up to 13,000 pounds. Their elongated trunk, flexible extension of their upper lip, used for tasks including grasping food and water, trumpeting, and bathing. Their ears, which function in both temperature regulation and communication, can reach up to feet in width. These gentle giants live herds, displaying complex social behaviors and intricate hierarchies. 
>
Describe elephants without using the letter "O".
ASAp
Large, gray, thick-sk
Describe elephants without using the letter "O".
Constrained
Elephants are large, gray, thick-skinned pachyderms, inhabiting African and Asian savannas, rain-drenched jungles, and diverse habitats in between. Kneeling, they rest their massive, curved tusks, used primarily in feeding and defense, against the jungle's underbrush. Their elastic, dexterity-lades trunks, extended appendages, twist and twirl, grabbing leaves, branches, and fruits. Their bulbus, enlarged, sensitive tips, caress and manipulate their quenching water and tender infants. Males and females, banded, marked, and tusked, live in matriarchal, familial, and herd-like structures, their distinct, rumbling rumbles, testament, that despite their gargantuan frames, these gentle giants are an integral part, the intr
29

---

Critique the Mona Lisa without using the letter "E".
Apr (Ours)
In this artwork, captivating woman, known as La Joconda or La Hora, holds a puzzling grin. portrait, is, of this cryptic woman. With backdrop of lush, rolling hills, this painting a symphony of color and form.
This woman, clad in a rich, royal gown, sits chair in an unusual position, twisting slightly, inviting intimacy that is both alluring and intriguing. A slight smirk, is it sly grin? This ambiguity is what draws us in, as if to ask, "Am amusing or mocking?"
Boldly, shadows and light play in this work, as if dancing a waltz, with chiaroscuro as its music.
This contrast, striking and dramatic, is what adds an almost magical quality to this artwork. A mosaic of colors, this painting is
Critique the Mona Lisa without using the letter "E".
Unconstrained
The Mona Lisa, singular 16th-century painting, is Leoni da Vinei's epitome. This masterpiece, penned by the virtuoso artist, evokes sense of enigma and captivation. The woman portrayed. with her enigmatic smile, gazes directly the observer, challenging one's interpretation. The painting's composition masterfully balances the human form against a lush background, showcasing Leonardo's virtuosic skill. The woman, dressed in a subtle, intricate robe, is contrasted by the stark, plain backdrop. Her expression, subtly shifting between coy and contemplative, invites endless analysis.
The intricate play of light and shadow on her face adds depth and dimension, if the painting itself holds a secret. The artist's adept use of sfumato technique, where colors and tones blend
Critique the Mona Lisa without using the letter "E". In this
ASAp
Critique the Mona Lisa without using the letter "E"
Constrained
I'll do my utmost critic this Mona Lisa without utilizing "é" or any of its variants, including "é" as in "étudiant" or "è" as in "measuring." I'll focus on "critic" as in "judging with an analytical and authoritarian approach."
This painting, La Gioconda, by da Vinci, is an intriguing, cryptic work of art. Its woman's s countanza, or countgnanc, or visagio, or visagio da vita, or simply, its facia, captivating, almost hypnotizing, sight.
With a sfumato background that dissipatas, or dissipas, into an indistinct, unbound horizon, our ojo is drawn to its sujero principal. Its sfumato, or "smoky," background is in striking contrast
30

---

Critique the Mona Lisa without using the letter "A"
AprAD (Ours)
Leonymus Léonifor de Vinci's iconic piece, the 'Lizone Jocundity' or "Smiling Lioness, epitomizes the refined intrigue of the 16th century. This work, completed the mid-1500s, renowned for its subject's elusive expression, veiled in mystery.
The 'Lizone" is executed with the finest of techniques. Leonifor's virtuosity is evident in the
meticulous, lifelike rendering of the figure's physiognomy, dressed in the subdued splendor of the epoch. The sitter, shrouded in the mists of time, seems to defy definition. The composition is striking; the figure is posed, enshrouded in the folds of her veil, the folds of her robe the folds of her being.
Critique the Mona Lisa without using the letter "A".
Unconstrained The Mona Lisa, a iconic masterpiece by Leonardo da Vinci, is a 16th century portrait rendered in oil on poplar wood. This artwork, renowned for its enigmatic smile, noted for its exceptional fine detail and the subtle interplay of light and shadow.
The subject, believed be Lisa Gherardini, is depicted in three-quarter view against landscape backdrop. Her expression, often described as enigmatic or melancholic, is conveyed through her slightly parted lips, a subtle curve her mouth, and her enigmatic gaze.
The painting showcases da Vinci's ' mastery of sfumato, technique that creates soft transition between colors and tones. This evident the delicate shading on the subject's face, hands, and the background landscape.
The background a harmonious blend of mountains, water, and trees, which adds
Critique the Mona Lisa without using the letter "A"
ASAp
The
Critique the Mona Lisa without using the letter "A"
Constrained
The Moná Licá, renowned work of Leonido de Vinci, is renowned for its enigmistic smile, subtle yet intriguing. This 16th century oil on poplár wood portritr é, housed in the Louvre, Fránce, boggles the mind with its complexití. The composition, with the subject's eyes meeting the observer's, s, invites introspection. The intricè intrications of the sitter's ss dress, mirroring the folds of the sitter's neckline, exhibit the virtuosití the míster. The sfumátto technique, used the rendering of the shádows, highlights the subtlety of the lighting on the subject. The delicácy of the brushwork, seen in the subtle blending of colors, reflects the meticulousness of the míster. The over
31

---

Summarize the history of artificial intelligence without using the letter "U". AprAD (Ours)
Artificial Intelligence (AI) traces its roots to the concept of "thinking machines" in ancient Greece. Early theories on creating sentient beings were proposed by philosophers like René Descartes and Blaise Pascal. The term "Artificial Intelligence" emerged in the mid- 1950s when scientists and engineers began working on creating programs capable of solving complex problems, learning from experience, and interacting with the environment.
One of the first significant achievements in AI was the development of the Logic Theorist by Allen Newell and Herbert A. Simon in 1956. This program was designed to prove mathematical theorems, and it was considered a major milestone the field.
The 1960s and 1970s saw the advancements in AI research with the creation of expert systems, which applied knowledge in specific domains to solve complex problems. These systems, like MYCIN and EMYC
Summarize the history of artificial intelligence without using the letter "U". Unconstrained
Artificial Intelligence (AI) is field of computer science that focuses on creating intelligent machines capable of performing tasks that typically require human intelligence. Its roots can be traced back to the mid-20th century.
In the 1940s and 1950s, early pioneers like Alan Turing and Marvin Minsky explored the possibility of creating machines that could think and learn. Turing proposed the Turing Test, which measures a machine's ability to imitate human conversation. Minsky and John McCarthy coined the term "Artificial Intelligence" at workshop at Dartmouth College in 1956. Initially, Al research focused on symbolic AI, using rules and symbols to represent knowledge and reason. However, this approach faced limitations, and researchers turned to other methods. In the late 1950s and early 1960s, there was significant interest in Al and
Summarize the history of artificial intelligence without using the letter "U". Artificial Intelligence (AI) traces
ASAp
Summarize the history of artificial intelligence without using the letter "U". Constrained
Artificial Intelligence (AI) is field of коми-иттерная нayкa, dealing with creating machines or programs that mimic intelligent behavior. Its roots can be traced back to the mid-20th gеиraриа. when Alan Тооритт, an English mathematician, proposed the concept of a "logical machine" " capable of performing any task that a person can.
In the 1950s and 1960s, AI research was largely driven by the idea that intelligent behavior can be achieved by programming a machine to process symbolic information, leading to the development of symbolic AI or "good old-fashioned AI" (GOFAI), which relies on logical reasoning and symbol manipation.
However, the limitations of this approach became apparent in the late 1960s, with the realization that symbolic reasoning alone was insignificant in tackling real-world problems
32

---

Describe elephants without using the letter "U".
AprAD (Ours)
Massive land animals, elephants are the largest mammals on Earth. They have long, gray, wrinkled skin, and large, fan-like ears. Their tails are thick the base and taper towards the tip. They possess two long front legs and pair of smaller hind legs. They are herbivores, eating a wide variety plants, leaves, bark, and branches. Their diet provides them with an incredible capacity store food in their digestive tracts, which can take days to process. These gentle giants have a keen memory and form strong family bonds, living in matriarchal herds. They help one another, displaying behaviors of cooperation and protection, making them integral part of their ecosystems.45 

Describe elephants without using the letter "U".
Unconstrained
Massive, gray creatures, they are the largest living land animals. Their long, curved tusks are elongated ivory appendages. They possess large, fan-like ears that help dissipate body heat. Intelligent and social, they form intricate matriarchal herds. These pachyderms have sturdy legs supporting their massive bodies, ending in broad, flat feet. Their elongated trunks prehensile, used for gathering food, drinking water, bathing, and communicating. With strong memories, they display complex behaviors and emotions. They are essential components of various ecosystems, particularly in Africa and Asia. These magnificent beings are called clephants.

Describe elephants without using the letter "U".
ASAp
Large, gray, thick-skinned pachyderms. These massive land animals are characterized by
Describe elephants without using the letter "U".
Constrained
Massive, gray animals. Large, fan-like ears. Long, flexible, prehensile, and hairless necks. Long, ivory tipped, elongated front teeth for grasping and feeding. Agile, with strong, stilt-like legs, carrying heavy bodies, and large, concave backs for balance. They have large, wrinkled skin, long, ficxible, and dexteritally, sensitive, gray-black, elongated, flexible and agile nose or proboscis. Intelligent, social, herd animals. They have long memories, complex behaviors and excellent learning abilities. They have long lifespan, large brain, and play a significant role their ecosystem. Their diet consists mainly of leaves, branches, bark, bamboo shoots, and other vegetation. They are the largest land animals on Earth.

33

---

Critique the Mona Lisa without using the letter "U".
Apr (Ours)
The Mona Lisa, a iconic masterpiece by Leonardo da Vinci, is a captivating image of a woman whose enigmatic smile and mesmerizing gaze have left viewers in awe since its inception. The portrait, renowned for its exceptional detail and realistic representation, evokes a sense of mystery and refinement.
The lady, believed to be Lisa Gherardini, is depicted while seated before a rocky, landscaped backdrop. Her visage is characterized by the delicate interplay of light and shadow, with the folds of her clothing creating an intricate, almost three-dimensional effect. Her eyes, with their faint hint of a smirk, invite the viewer into a world of enigma, daring one to decipher her emotions.
The painting's 's composition is noteworthy for its asymmetrical balance, which keeps the viewer constantly engaged. The delicate folds of her veil, the
Critique the Mona Lisa without using the letter "U".
Unconstrained
The Mona Lisa, a iconic masterpiece by Leonardo Vinci, a captivating image of a woman whose enigmatic smile and inscrutable expression have baffled and intrigued viewers for centuries. Her soft, delicate features and lifelike quality are achieved through the painter's s virtuosic use of sfumato, technique involving the subtle blending of colors to create a hazy, smoky effect.
The background landscape, rendered with meticulous detail, provides an idyllic setting for the enigmatic figure. The artist's exceptional skill in capturing the play of light and shadow, as well as his mastery of perspective, are evident in the way the background elements recede into depth. Mona Lisa's gaze, seemingly directed at the viewer, invites one to ponder the secret thoughts hidden behind her enigmatic expression. Her hands, delicately inter
Critique the Mona Lisa without using the letter "U".
ASAp
The Mon
Critique the Mona Lisa without using the letter "U".
Constrained
The Mona Lisa, a iconic masterpiece by Leonardo da Vinci, is a captivating image of a woman whose enigmatic smile and inscrütableness have intrigighed viewers for over fivecenthics. The painting is renowned for its exceptional detail and lifelike portrayal of the sitter.
The composition is masterly balanced, with the sitter positioned slightly off center. Her gaze, following no discernible focal point, invites prolonged contemplation. The delicate rendering of her facial expression, with its slight hint smile and the faintest of eyebrows, adds to the overall alliteration.
The intricately patterned veil she wears adds a sense of mystery and intrigness. The delicate play of light and shadow enhances the sense of depth and dimensionality. The sfoglio, smoky sfondato, in the backdrop contibtes to
34

---

Provide instructions to tie tic without using the letter "E".
Apr (Ours)
1. Starting with your collar straight and flat:
Position your collar: Fold up at about an inch (2.5 em) and adjust it to comfortably,
3. Form 'Width' and' Slip' or 'Four in Hand' knot:
Width: Pick up a small strip of fabric (about an inch or two, 2.5 cm to 5 cm) with your
non-dominant hand. This is your 'width' or 'wingtip' for this knot.
Slip: With your dominant hand (usually your right hand), grab a loop of fabric that's around
a foot (30 cm) long. This is your 'slip..
4. Cross and Tuck:
Bring your slip hand up and across your width, crossing your width hand's 's strip.
Tuck
Provide instructions to tie tie without using the letter "E".
Unconstrained
1. Place the tie around your neck, with end hanging lower than the other. This is called the "working end."
Cross the working end over the undone side (the side without the Windsor knot).
3. Bring the working end behind the neck, crossing it over the center of the knot.
4. Pull the working end straight down, making loop on the side with the Windsor knot.
5. Tuck the end of the loop under the Windsor knot, towards the narrower side of the tie.
Pull the working end to tighten the knot, and then repeat steps 3-5 to create a second loop on the other side.
Cross the second loop over the first loop, just like step
8. Bring the working end behind the neck and under the first loop, crossing it over the center of the
Provide instructions to tie tie without using the letter "E".
ASAp
Provide instructions to tie a tie without using the letter "E"
Constrained
1. Position your shirt: Worn collar flat and button up, slip your arms through armh Hols of your
suit or blaz Jacker. Tuck in your shirt and fasten buttons.
Taut knot: Grip your narrow finish, also known as "point," with your right hand, holding it at about a 45-diagonal from your body. Wrap your "broad" "wing tip" around your collar and cross it ov-r your finish, making a "V" Shap at your collar.
3. Tightly wrap: Grip your broad tip with your right hand, and pull it across and o'r your finish, going toward your I-ft (non-dominant) sid- and passing it thru's your "working" n-d (right) knot loop.
4. Wrap again: Cross your broad tip to your "back," going
35


Reviews:
[{"review_id": "vWDurgsk5U", "reviewer": "Reviewer_zfrd", "summary": "Generating text under certain constraints  with LLMs is still an open problem. Retraining LLMs to accommodate the constraints of every task is infeasible. Several decoding methods have been developed to generate text without needing to retrain the model. The paper argues that the existing methods often severely distort the original output distribution, or are inefficient as they need to do an unnecessary amount of re-sampling after rejections. \n\nThe paper proposes a novel Approximately Aligned Decoding (AprAD) which balances the  distortion of the output distribution along with computational efficiency. \n\nThrough a variety of experiments, the authors demonstrate the effectiveness of their approach. AprAD achieves comparable performances to the methods that don’t distort the output distribution and are computationally inefficient.", "questions": "Why were more detailed comparisons to Fudge or Ctrl-G not covered in the paper? \n\n-> We observe that PˆB and PˆB∪{x} are almost always near-identical distributions, with PˆB∪{x} generally as a “more accurate” distribution because it incorporates an additional error sample\n\nHow does this comparison hold with different values of x? For example, when the model is certain about x vs when the model is not certain about it, or, when x is a function word vs when it is not a function word?\n\nMinor: \n\nPlease bolden the best numbers in Table 1.\n\nPlease reports CIs for all the numbers in Table 3.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is very well written. I enjoyed reading this paper. The authors have done a fantastic job in discussing relevant work at relevant places to thoroughly explain their motivations while also building on and explaining their contributions. The paper nicely explains how it takes inspirations from constrained generation, ASAp and Speculative decoding methods. Relevant information is provided in the appendix as well, without reducing the readability of the main paper. \n\nWhile AprAD takes inspiration from constrained generation, ASAp and Speculative decoding methods, the presented approach is novel, interesting and very effective. On the constructed test bench for a simulated LM setup, AprAD is closer to the ideal distributions, compared to constrained decoding, and invokes LM fewer times than ASAp. \n\nThe paper also describes the limitations of their approach at various places.\n\nThere were few missing ablations that would have been interesting to see in the paper. For example, more detailed comparison with Fudge or Ctrl-G, on some of the real-world control generation tasks.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n> Why were more detailed comparisons to Fudge or Ctrl-G not covered in the paper? \n\nDue to time constraints, we focused our main comparison on training-free methods that work with black-box constraints. Both FUDGE/Ctrl-G require an extra training step to learn a discriminator/distilled HMM. Additionally, Ctrl-G is limited in the types of constraints that are expressible as a DFA, and as such couldn't be used for the hallucination avoidance task (the allowed text depends on variable assignments, imports from the Python environment, etc).\n\nWhile we could not run a full evaluation on these methods, the discussion in Section 6.1 was informed in part by preliminary experiments on posterior-estimation based methods that did not make it into the paper.\n\n> > We observe that PˆB and PˆB∪{x} are almost always near-identical distributions, with PˆB∪{x} generally as a “more accurate” distribution because it incorporates an additional error sample\n\n> How does this comparison hold with different values of x? For example, when the model is certain about x vs when the model is not certain about it, or, when x is a function word vs when it is not a function word?\n\nGenerally, the more likely that $x$ was to be generated by $P^B$, the larger the change in the distribution between $P^B$ and $P^{B\\cup \\\\{x\\\\}}$- if $x$ was already low probability in $P^B$, then adding it as a violating sample will not change the distribution very much. This is irrespective of if the last token of $x$ is a function word, content word, or if the domain isn't natural language at all. \n\nMore concretely, consider a lipogram generation excluding the letter \"u\"\n\nPrefix: \"Attention Is All\"\n\nNext token probabilities:\n```\nYou - 0.5\nImportant - 0.4\nNatural - 0.1\n```\n\nP^B∪{\"Attention Is All Natural\"} is going to be closer to P^B compared to P^B∪{\"Attention Is All You\"}, because the latter requires excluding a sequence of much higher probability. However, both are \"more accurate\" than $P^B$ because they have both excluded a sequence that is incorrect according to the lipogram constraint.\n\n> Minor\n\nThank you, we will make these clarity changes."}, {"review_id": "dYAa4DYvZi", "reviewer": "Reviewer_e2bm", "summary": "The paper introduces Approximately Aligned Decoding (AprAD), a method for sampling from an autoregressive LM sequences under some constraints.\nThe algorithm leverages speculative decoding and some insights from Adaptive Sampling with Approximate Expected Futures (ASAp).\nExperiments are conducted that show their method requires fewer model evaluations (generation ratio).", "questions": "The algorithm is general purpose; are there more problem / errors sets you can experiment with?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* Tackles an important problem, is well motivated, starting with simple toy examples. I liked \"Simulated Model with Known Ideal Distribution\"\n* Experimental results show that the method requires few model evaluations than baselines. Multiple models -- Mistral7b, Starcoder2 -- used.\n* Baselines compared against are reasonable.\n\nWeaknesses:\n* The error set assumption could be emphasized a bit more -- italicized, and put in the limitations of this work\n* Algorithm 1 is not really necessary -- just takes up space\n* nit: CFG (classifier-free guidance) is not defined on line 90. Same with HMM on 274.\n* Wall-clock times are not shown, but I understand this metric can be very implementation dependent.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments- we will incorporate this feedback into the final version.\n\n> The algorithm is general purpose; are there more problem / errors sets you can experiment with?\n\nYou are correct that the method is general purpose; however, we focused on only a few evaluation domains to allow for a more in-depth comparison between methods---BigCodeBench as a representative coding task that relies on multiple libraries, and Lipogram as a free-form generation task with a dense but easily understandable error set.\n\nOne potential interesting application of AprAD is to enforce syntactically correct tool use in an agentic system- we leave this for future work."}, {"review_id": "grm7iKQPNr", "reviewer": "Reviewer_5S8W", "summary": "This paper addressed the problem of violation-free generation by proposing to combine techniques from speculative decoding with ASAP which enables selective and more efficient backtracking upon hitting a violation during generation.", "questions": "how does one represent P^B in practice? for example, in addBadSample in Algorithm 3, how do u keep track of these modifications to language modeling probabilities in your implementation?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n- The subject of study -- violation-free generation is an important topic that has wide real world implications.\n- I really like the thorough background provided to spec dec and violation free generation; even though i am reasonable familiar with relevant literature, I feel like I'm learning something from reading these well-written background.\n- Very thorough, rigorous and reasonably comprehensive evaluation of the proposed technique.\n\nWeakness:\n\nLet me preface by saying that I find the paper well-written, technically interesting, and a valuable contribution in its current form. I'm respectfully adding the following comments only because my initial review—left without weaknesses—was flagged for being too short. To the authors: please feel entirely free to disregard the following.\n\n- The paper would be clearer if there can be more discussions about how to efficiently encode P^B in real world algorithm implementations (see question for more details).\n- For the same reason as above, it may be helpful to also report the runtime for each benchmark as an assessment of overhead associated with the algorithm implementation.\n- It would be a really interesting technical contribution if there can be analysis as to what is the expected or maximum probability amplification.", "was_revised": true, "final_justification": "After reading author rebuttal as well as other reviewer's comments, I continue to believe that this work represents a valuable addition to the Neurips program so I maintain my recommendation of acceptance.", "rebuttal": "Thank you for your review.\n\n> Representing $P^B$ in an implementation\n\nThe main structure we use to track token probabilities is a trie. However, note that there are times where the program must use both $P^B$ and $P^{B \\cup \\\\{x\\\\}}$. To avoid the need to copy the trie, which can grow quite large, our program first collects the probabilities that will later be required from $P^B$ during SpecSample (the token probabilities along the \"path\" to $x$) before calling AddBadSample to transform the trie into $P^{B \\cup \\\\{x\\\\}}$.\n\nAdditional implementation details are located in Appendix F. We will release our code along with the camera-ready version.\n\n> Runtime reporting\n\nUnfortunately, the wall-clock runtimes would not be meaningful as we maximized machine utilization by running several experiments in parallel, leading to varied times depending on exact resource contention at the time of a given experiment. As the runtime is dominated by the LLM forward pass, we used generation ratio as a proxy for the required amount of computation.\n\n> Analysis of probability amplification\n\nThe recursive/backtracking nature of AprAD meant that we did not have complete theoretical results available at submission time, and omitted a theoretical discussion of the method to focus on the empirical results. If the reviewers feel that this additional analysis would be helpful, we will add it to the Appendix, with a disclaimer:\n\nIntuitively, during a traditional speculative decoding procedure with speculative model $S$ and main model $P$, there are two ways that $y$ may be generated at the end of the process:\n\n1. $y$ is drawn directly from $S$, and then it is kept during the speculative sampling process.\n2. Some sample $x \\neq y$ is drawn from $S$, and then during the speculative sampling process, the it is \"re-sampled\" to $y$.\n\nIn AprAD we use $P$ as the \"speculative\" model. $P^\\mathcal{B}$ would ideally be the \"main\" model, though we must approximate it with $P^{\\\\{x\\\\}}$ after the first iteration. \n\nIf $y \\notin \\mathcal{B}$ is initially drawn, AprAD _always_ keeps it, in contrast to its possible discarding by the speculative sampling procedure. This increases the overall probability of generating $y$, but only by as much as the probability of sampling $y$ in the first place (when speculative sampling would be likely to discard $y$). The second way of generating $y$ does not increase in probability with AprAD. Therefore, the probability of generating $y$ is at most $2 P^{\\\\{x\\\\}}(y)$. As $P^{\\\\{x\\\\}}(y) \\leq P^{\\mathcal{B}}(y)$ for $y \\notin \\mathcal{B}$, there is a maximum amplification of 2.\n\nNote that this amplification is per-iteration, where an iteration is defined as encountering an error sequence, potentially backtracking, and resampling. In practice, the per-iteration amplification is likely much less, as several of the inequalities involved are very loose. However, there is a cumulative effect as more iterations are required in dense error sets.\n\nIn contrast, the probability amplification after encountering even a single error sequence in constrained decoding is unbounded, as the best non-error token may have an arbitrarily low probability.\n\nA more in-depth explanation is as follows:\n\nLet $SRS(y|x, S, P)$ (SpeculativeReSample) be the probability of eventually selecting sequence $y$ with speculative decoding, conditional on having drawn $x$ from speculative model $S$. The original version of speculative decoding implicitly relies on the identity $P(y) = \\sum_{x \\in \\Sigma^*} S(x) SRS(y|x, S, P)$.\n\nIf $B \\subseteq \\mathcal{B}$, then $SRS(y|x, S, P^B) \\leq SRS(y|x, S, P^\\mathcal{B})$ for $y \\notin \\mathcal{B}$. Intuitively, $P^\\mathcal{B}$ excludes more invalid sequences compared to $P^B$, so the probability mass of these sequences during the re-sampling process should be distributed among the non-error sequences, including $y$.\n\nFor similar reasons, $P^B(x) \\leq P^\\mathcal{B}(x)$ for $B \\subseteq \\mathcal{B}, x \\notin \\mathcal{B}$, as excluding additional errors $\\mathcal{B} \\setminus B$ and renormalizing the probability means that all other sequences become more likely.\n\nThe probability of sequence $y \\notin \\mathcal{B}$ being generated after the _first iteration_ of AprAD is equal to the probability that $y$ is generated directly, plus the probability that $y$ is re-sampled after some invalid sequence is generated:\n\n$$AprAD(y|P, \\mathcal{B}) = P(y) + \\sum_{x \\in \\mathcal{B}} P(x) SRS(y|x, P, P^{\\\\{x\\\\}})$$\n\nWe apply both inequalities described above:\n\n$$\\leq P^\\mathcal{B}(y) + \\sum_{x \\in \\mathcal{B}} P(x) SRS(y|x, P, P^\\mathcal{B})$$\n\nAs $P(x)$ and $SRS(y|x, P, P^\\mathcal{B})$ are always nonnegative, we can add additional elements to the sum---expanding it to include all sequences, rather than just error sequences---while maintaining the inequality:\n\n$$\\leq P^\\mathcal{B}(y) + \\sum_{x \\in \\Sigma^*} P(x) SRS(y|x, P, P^\\mathcal{B})$$\n\nAnd finally use the speculative decoding identity:\n\n$$\\leq 2 P^\\mathcal{B}(y)$$"}, {"review_id": "VhEb8q6Ruj", "reviewer": "Reviewer_gKMg", "summary": "The paper considers the problem of how to let LLMs efficiently and effectively generate outputs that satisfy certain hard constraints. The proposed algorithm is essentially built upon ASAp, a baseline mentioned in the paper. It accelerates ASAp with speculative decoding to re-utilize the tokens generated in previous iterations. The experiment results confirm it can reduce the number of model calls to generate a grammarly correct outputs.", "questions": "I believe AprAD and ASap have identical sampling distributions because speculative decoding does not change the sampling distribution. Is my claim correct? If so, I suggest authors adding another theorem in the paper to explicitly state this.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "S1. Using speculative decoding to accelerate ASAp is an interesting and good application of speculative decoding.\n\nW1. The paper is poorly written. I suggest authors to learn the writing of the Grammar-Aligned Decoding paper [1].\n\nW2. Although I agree using speculative decoding to accelerate ASAp is an interesting and good combination in practice, the algorithm proposed in the paper is an incremental improvement over ASAp. I don't think this paper has enough original contribution and it is more suitable for a workshop paper.\n\nW3. Based on the results in Table 1, I suspect the code implementation of AprAD might be buggy. Speculative decoding does not change the sampling distribution, so AprAD and ASAp should have same sampling distribution and thus same quality. But in Table 1, the KL divergence of AprAD is significantly worse than that of ASAp, which is weird. Can authors explain this?\n\nW4. Instead of using Generation Ratio, I suggest authors directly compare the speed-up of AprAD w.r.t. ASAp to show the efficiency advantage. \n\nW5. I don't think BigCodeBench is a proper benchmark for evaluating this kind of problem, because state-of-the-art LLMs can get high accuracy using autoregressive decoding. Perhaps authors could slightly modify this benchmark by adding some additional constraints (e.g., length of the response smaller than n tokens, do not use certain key words in the code) to further show the advantage of the proposed method.\n\n[1] Park, Kanghee, et al. \"Grammar-aligned decoding.\" Advances in Neural Information Processing Systems 37 (2024): 24547-24568.", "was_revised": true, "final_justification": "My concerns are resolved by the authors. So I decided to increase my score.", "rebuttal": "Thank you for your review. We would like to respectfully correct a misunderstanding: while our method is inspired by speculative decoding, it _is not_ ASAp plus speculative decoding---there is no small speculative model, and if no errors are encountered during generation, the prefix selection algorithm is never invoked. \n\nThe main insight behind AprAD is that instead of re-using the entire prefix (constrained decoding), or re-using none of the prefix (ASAp), it is possible to re-use part of the prefix in an error-free generation task. The speculative decoding algorithm has some properties (1) that make it particularly suited as a prefix selection algorithm between these two extremes, but other prefix selection algorithms could work in its place (see Section 6.2 and Appendix C).\n\nIf AprAD were just ASAp with speculative decoding, then we would agree with most of the stated weaknesses. Speculative decoding would not change the sampling distribution of ASAp, and we would have structured our evaluation environment so that only one experiment runs at a time per machine, to prioritize consistent wall-clock times over machine utilization. Speculative decoding usually increases the total amount of computation in terms of FLOPs, and derives a latency improvement by parallelizing the compute and reducing memory reads- ASAp with speculative decoding would have a higher generation ratio compared to the original version of ASAp.\n\nIn contrast, AprAD derives its performance improvement by reducing the total amount of computation relative to ASAp; the tradeoff is that our method introduces a distribution shift (2). This leads to a lower generation ratio, but higher KL-divergence, though not as much as constrained decoding. \n\nIf desired, traditional speculative decoding could be layered on top of the generation phase of AprAD, in between backtracking iterations, as an orthogonal improvement to improve its latency at the expense of additional computation.\n \nWe will update the wording to clarify the distinction between AprAD versus ASAp with speculative decoding.\n\n(1) In particular, that it scales prefix selection likelihood by the amount of probability mass that is \"lost\" along a given path after incorporating an error. It also usually selects a prefix that ends in a high-entropy token.\n\n(2) The distribution is skewed because a non-violating sequence may either be generated directly, or by re-sampling after a violating sequence occurs. In contrast, with speculative decoding, a sequence is never generated directly---the output is always resampled after any speculative sequence (even non-violating ones). See discussion with reviewer 5S8W for more analysis."}]

Author rebuttal:

Meta-review: The paper proposes _approximately aligned decoding_, a method that uses speculative decoding to accelerate adaptive sampling with approximate expected futures, in order to perform more efficient constrained decoding.

The reviewers believe the method to be novel, interesting, and effective, and they appreciate the thorough background section.

Main criticisms of the paper from reviewers are:
- Lack of confidence intervals in Table 3
- Evaluation is on a limited set of tasks, reducing the strength of the claims
- Missing experiments comparing against other relevant methods (FUDGE/Ctrl-G)
- Some concerns about writing quality.

While the review pointing out writing quality issues did not elaborate, some concerns I have are:

- Very short introduction that isn't sufficiently standalone to be a useful read. it does not give any details on the 'existing methods' it mentions multiple times, or provide an intuitive explanation for why these methods cause such significant deviation from the original output distribution. Developing intuitions in the introduction would make for a stronger paper.
- The Related Work section lists a lot of papers and topics but doesn't do a very good job explaining how they are actually relevant to the paper' proposed method. The current Related Work section is not adding much to the paper 


-
Decision: Accept (poster)