Grammar-Aligned Decoding
Authors: Kanghee Park
Jiayu Wang
Taylor Berg-Kirkpatrick
Nadia Polikarpova
Loris D'Antoni
Venue: NeurIPS 2024 poster (2024)
Keywords: Language Models
Decoding
Context-free Grammars
Primary area: natural_language_processing

Abstract: Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches a given constraint. Specifically, in grammar-constrained decoding (GCD), the LLM's output must follow a given grammar. In this paper we demonstrate that GCD techniques (and in general constrained decoding techniques) can distort the LLM's distribution, leading to outputs that are grammatical but appear with likelihoods that are not proportional to the ones given by the LLM, and so ultimately are low-quality. We call the problem of aligning sampling with a grammar constraint, grammar-aligned decoding (GAD), and propose adaptive sampling with approximate expected futures (ASAp), a decoding algorithm that guarantees the output to be grammatical while provably producing outputs that match the conditional probability of the LLM's distribution conditioned on the given grammar constraint. Our algorithm uses prior sample outputs to soundly overapproximate the future grammaticality of different output prefixes. Our evaluation on code generation and structured NLP tasks shows how ASAp often produces outputs with higher likelihood (according to the LLM's distribution) than existing GCD techniques, while still enforcing the desired grammatical constraints.

Grammar-Aligned Decoding
Kanghee Park Jiayu Wang"" Nadia Polikarpova UUniversity of Wisconsin-Madison (kpark247, jwang2782, (eanton)@vvsc..cm edu, (tberg, npo ppolikarpovaaeee @oova)@@csd.
Taylor Berg-Kirkpatrick?
Loris D Antonni
University of California San Diego
Abstract
Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches given constraint. Specifically, in grammaar-constrainnd decoding (GCD), the LLM's output must follow a given grammar. In this paper we demonstrate that GCD techniques (and in general constrained decoding techniques) can distort the LLM's s distribution, leading to outputs that are grammatical but appear with likeli- hoods that are proportional to the ones given by the LLM, and ultimately are low-quality. We call the problem of aligning sampling with grammar constraint, grammar- aliignerr-- decoding (GAD), and propose adaptive sampling with approx- imate expected futures (ASAp), a decoding algorithm that guarantees the output be grammatical while provably producing outputs that match the conditional probability of the LLM's distribution conditioned on the given grammar constraint. Our algorithm uses prior sample outputs soundly overapproximate the future grammaticality of different output prefixes. Our evaluation on code generation and structured NLP tasks shows how ASAp often produces outputs with higher likelihood (according the LLM's distribution) than existing GCD techniques, while still enforcing the desired grammatical constraints.
Introduction
Despite their remarkable success, pre-trained Large Language Models (LLMs) often struggle with generating highly structured outputs, such as program code, configuration files, or mathematical formulas. A naïve approach to enforcing structure is rejection sampling, which repeatedly samples strings from the LLM and checks them against a validity oracle, typically the form of a context- free grammar (CFG). Rejection sampling is highly inefficient or simply intractable for restrictive grammars and long output sequences -ic., most generated strings will not be in the target grammar.
Constrained decoding addresses the inefficiency of rejection sampling by greedily "forcing" the LLM output to satisfy the given constraint. Specifically, when the constraint is given as a grammar, constar-cnnsrraine decoding (GCD) 7 27 28), can build automata that allow for on-the-fly masking tokens that will provably lead to outputs outside the grammar during decoding.
While GCD does not incur the overhead of rejection sampling-i.e, the generated output is always in the language of the grammar- show that GCD and in general all forms of structured decoding introduce a new problem: structured decoding distorts the LLM's learned language distribution, effectively hindering the LLM's capabilities.
* "qqual contribution
2 "Our code, datasets, and checkpoints are available at: http:s///aitttt...cc//mmmooooooo
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This paper introduces and formalizes grammar-aligned decoding (GAD), the problem of sampling from an LLM so that the outputs (1) are guaranteed to adhere a given grammar, and (2) are unbiased wrt. the LLM's distribution. Although exact GAD is intractable in general (similar to rejection sampling), we propose a new adaptive decoding algorithm for approximate GAD, which starts off as GCD and gradually converges to the LLM's 's distribution, and thus allows trading off between efficiency and accuracy. The algorithm, which we dub Adaptive Sampling with Approximate Expected Futures (ASAp), is built "on top" of existing constrained decoding algorithms. Whereas GCD approaches simply mask out tokens that lead to non- -nna-aammaaiaal sequences for a given prefix, ASAp remembers for all sampled prefixes the probability associated with masked-out tokens and uses it to upper bound the probability of grammaticality. By updating this bound when more samples are observed, the decoding algorithm converges to the desired probability distribution- i.... it samples outputs from the I.I M-innduueed probability conditioned on the outputs being accepted by the grammar. The idea works for any structured decoding approach and not just for GCD, but in this paper we focus our evaluation on constraints expressed via grammars.
We evaluate ASAp two structured prediction tasks: formal program synthesis and constituency parsing. Our experiments on program synthesis and NLP tasks show that GCD techniques generate outputs that are grammatical but unlikely according to the LLM, while with ASAp, the likelihood of the generated outputs improves over time, converging to the target constrained LLM- -.M-i.e. GAD better respects the LLM while still enforcing the constraints.
2 Grammar-Aligned Decoding
In this section, we formalize the problem of grammar- aligged decoding (GAD) as decoding from an autoregressive language model while enforcing the output sequence to be accepted by given context-free grammar. We also demonstrate the limitations of existing approaches to this problem.
Language Models the set of all strings w E E" over vocabulary of tokens E via product of left-to-right next-token conditional distributions P(w]... w.) = mT P(w; w1s--))
An (autoregressive) language model defines a probability distribution P on
Context-Free Grammars A context-free grammar (CFG) is a quadruple G = (E,N, R)). where Σ vocabulary of tokens (also called terminal symbols), M is a finite set of non-terminal symbols, E A is the start- ing tertenamla,, and R. is the set of production rules. An example CFG shown in Fig. I A grammar defines single-step derivation relation sequences of symbols a, 3,y E UU)): aAyy = a.3t if A - E R. The reflexive transitive closure of this relation is called derivation and written = A sequence of tokens w is a sentence if it is derivable from S: the set of all sentences is called the language of the grammar G. that is, L()) = (w E E S 3* w). The following example illustrates these definitions.
: 00000
1A2
A, 0A4,+1 1A for 2, 4 A5 ::=
Figure 1: CFG Gsk over tokens Σ {0, 1}, written in Backus-Naur form (BNF) notation. This grammar accepts the string 86908 and all length-5 strings that start with a
Example 1 (CFG Derivations). Given the CFG Gek shown in Fig. 1 the string 00000 belongs the language C(G.k) because it can be derived using the derivation + 00000. The string 10101 is also in (l and can be derived as follows:
S + 1A2- + 10As + 191A, = 1010A; + 10101
Each step replaces a nonterminal symbol using production rule in Gsk-e.g. in the string 10 Ag, the nonterminal Ag is rewritten 1A, by applying the rule Ag + 1As, resulting in the string 181A,-
In addition, we define the prefix language of as the set of all prefixes of sentences in L(G): Lpretii (9) = (w E Σx we E L())).
Grammar-Al Aligned Decoding Given a model distribution P and CFG G, granmar-aligned decoding (GAD) is the task of sampling from the distribution TC that is proportional to P but restricted to sentences in G:
1 1| L(G)) P(w)
r Enw 1| E L(9)) P(w")
2

---

When P and G are clear from context, we will write Q(w) instead of QP
Example 2 (GAD). Consider the distribution P that arises from prompting an LLM to "generate a binary string that ends with a 1". We expect P to assign high probability to strings of the form (0 (012)=1-iss those that satisfy the prompi (Mixtral-8x78) Baraaa--xx----nruttttt Instruct--ttt ve.. (temperature= 1) generates binary strings that end with a I around 90% of the time.) A snippet of a possible distribution P is depicted in Fig. 2)
Suppose we constrain the model's output the language of the grammar gsk in Fig. 1 which only accepts strings of length 5. Moreover, Osk only accepts one string that starts with 6, i.e. 60900, which does not end with 1. In Fig. 2 the grayed out parts of the trie are tokens that lead to sequences outside of the grammar gsk- According to the definition of GAD, the target sampling distribution QP.S.t should assign: (i) high probability to all eight strings of the form 1wwwwwal-wii both to the grammar and the prompt; (ū) low probability to the string 80000- which conforms to the grammar but not the prompt; and (iii) zero probability all other strings.
conform
Exact GAD Can one exactly sample from QP Rejection sampling, which repeatedly draws from P until a sample lands in L()), provably yields exact samples according to
0/0445)
(2-45)
(0:45)
(00455)
(1099)
3 (0:45)
QP. but if P assigns most of its mass outside of C(G). it is intractably slow, especially the prompt is not including information about the grammar (see (27)). For Ex. 2] rejection sam- pling would be highly inefficient because the model would generate many strings that are not
10.45
10.0
1
1
1.00.)
(0.33)
of length five.
(0.1)
(0:3)
In contrast, exact sampling from efficient because its joint distribution is represented by a product of easily computed left-to-right con- ditionals, enabling ancestral sampling (i.e., gen- erating tokens left to right, conditioned on al- ready generated tokens). Can we similarly fac- tor Q into a product of left-to-right conditionals QP' (ws(wissi), to enable ancestral sampling?
Figure 2: Fragment of the conditional model distribution P for Lx. 2 depicted as a trie. Each node corresponds to
prefix W 1, and each edge is annotated with the next token wy and its conditional probability P(w; w1-i-))- Filled nodes are complete strings. Grayed out parts of the trie are outside of the grammar Gak.
For simplicity, let us assume that a distribution over sequences of exactly length n (although, in practice, language models can produce 'stop' tokens which allow for a valid distribution on sequences of all lengths). The exact conditionals of QP are given by:
Q P.O (wel wis-1)
Em [I| E C()) HJ P(u; was- O] [w E C())
(I)
P(w: (1--1) Ep(rstaele...)
Thus, exact left-to-right sampling from QP.9 consists of sampling from model conditionals P(w: w1.-1), with an additional weighting term c(w1s) = (r(mssm((nss) [1 [w E CG)]] that considers the grammar.
We refer to c(wi.)) as expected future grammaticality (EFG), Lee the probability that a continuation of W1:: sampled from P lands in L(g). Using this notation, we can write the exact left-to-right sampling conditional explicitly as:
P(wa w1s-1) c(rix)) ( w1=-1)= = Ew: P( | w) cl c(Wis- w!)
(2)
To see why computing this conditional is intractable, consider using dynamic programming to compute c(w1:) by marginalizing over a product of potential functions: the set of model conditionals and an indicator potential for the grammar. While the indicator potential can be factorized across rules in the grammar, the model's contribution generally does not factorize: in practice, the final conditional probability P(w,, | w):n-1) is global potential function, defined by a non-linear neural network touching every variable. Thus, the main goal of this paper is to develop effective approximations to the EFG o(wia), which would enable us to compute the left-to-right conditionals of Q.
3

---

Limitations of constrained decoding (GCD) as a way to efficiently sample from an autoregressive language model subject to grammar constraints. Although the exact details of these techniques vary depending on class of grammars they support, the common thread is that they rely on an incremental parser, which can efficiently check whether given string is prefix of sentence in the grammar, i.e., w E pprettx (G). When given a sentence w1 GCD techniques use this parser during decoding to mask out any next token wi that results in a prefix wi: for which completion will produce sequence in the grammar. Using the trie in Fig. 2 as an example, one can think of GCD as sampling a path through the trie by selecting only among the black outgoing edges from every node, proportional to their conditional probabilities in the diagram (e.g. the first token is 0 or with equal probability).
Decoding Existing work 227 28 has proposed grammar-
In terms of the GAD problem, we can view GCD as approximating the exact left-to-right conditionals QP/ w1x-1) by the conditional distribution QGCD (wal W1:i-1), defined as follows:
P(w: W1:i-1) 1) 1 [wis E E (9)
QGcD(w: w1:-1) Em: P(w w1=-1) [W1:-11 w/ E (prefi(())
Though not originally formulated in this way, we can view recent work on GCD [27 28 as forming binary approximation 1 [wox E Lpreti to the EFG c(wis). In other words, while GCD considers the possibility of future grammaticality, it makes no attempt integrate the model's likelihood to estimate expected future grammaticality, which can lead to substantial bias in the sampling distribution-i.e. every EFG such that c(wi:) > will simply be approximated via the value 1.
Example 3 (GCD). Consider again the GAD problem from Ex. 2 where our target sampling distribution &* assigns high probability to strings that both start and end with a and a low probability to the string 00000. However, we observe that GCD (8) generates strings ending with 1 only 30% of the time-i.e.. GCD has effectively ruined the LLM's ability to follow the prompt by biasing sampling towards 00600, an incorrect output.
When generating the first token (9 or 1). the GCD algorithm does not know how many grammatical strings start with each character and, more importantly, how likely these strings are under P. Since both tokens 0 and I have the possibility of leading to a grammatical string, GCD will estimate their expected future grammaticality
I, and choose each of them roughly half of the time (since P(0)= R P(1)). Once GCD has chosen 0, however, it becomes "trapped" in the part of the search space where the only grammatical string is the low-probability sequence 00000.
Ex. 3 illlustrates how existing GCD approaches can hinder the language model's abilities to explore the space of possible outputs according to the learned distribution, thus highlighting the importance of designing a better approximation to the EFG o(w1s); this is addressed in the next section.
3 Adaptive Sampling with Approximate Expected Futures (ASAp)
In this section, we propose an adaptive sampling algorithm that iteratively builds better approximations of the future grammaticality of sequence. Our procedure operates by sampling repeatedly, each time bounding lost probability mass to provably ungrammatical areas of the search space in order to better guide the next sampling iteration. As result, our algorithm converges over many iterations to exact samples from the constrained LLM distribution, allowing for a flexible trade-off between efficiency and accuracy.
Overview of the Algorithm GCD approaches poorly approximate the desired distribution because they greedily sample prefixes without worrying about the EFG. When sampling the first token in Ex. 3 GCD simply uses the likelihood for tokens O and I assigned by the LLM without considering the probability that these next tokens would result in grammatical completions if sampling were unconstrained -i.e. without incorporating the critical EFG re- weighting terms that are necessary for unbiased sampling from the constrained LLM distribution. However, if GCD ends up sampling 0 as the first token for Ex. 3] it will necessarily sample the string 80000 since no other sequences starting with 0 are allowed by the grammar. We can "learn" from this result: the true probability mass assigned to all grammatical sequences starting with 9 is not 0.45 the LLM's next token probability would have us believe; instead, the total grammatical mass in this section of the search space is the joint probability of the single string 00000, which is the much lower value of 0.455 10-8

---

10.49-164
*0.45'100"
"0.45-00*
*30
01045110011 i yi (200)) (004es mnpeestt $150-9
*0 "0445 O (0-45)
(0:65)
(0:65)
(0-45)
(0.45)
0.0.3)
010.31
(8-45)
1(0445)
10.23
11.33
3
1,0033 10.3
.0.23+03
60.22-03
10.09
Figure 3: Illustration of the trie built by ASAp after sampling с6ese as the first string (left) and after sampling 11111 as the second string (right). EFG updates after each iteration are shown in red.
as depicted in Fig. 3
In other words, simply by sampling 0000e, we can better approximate (in this case, exactly) the EFG of tokens along this path.
The key insight behind our algorithm, which call ASAp, is that can iterate this process of discovering lost grammatical probability mass by repeatedly sampling and revising transition weights after each sample is produced. More formally, we can think of this procedure starting with GCD's over-approximation to each EFG ((w1:) term, and then, through repeated sampling and discovery of mass assigned to non-grammatical completions, reducing each overapproximation make it more accurate. In the limit, the approximations converge to exact EFG estimates and unbiased sampling.
Two possible first iterations of the ASAp algorithm are depicted in Fig. 3 In the first iteration (left of Fig. 3), after sampling the sequence 00000, the algorithm directly addresses the issue that arose in Ex. 3 by attempting better approximate the probability mass of potential grammatical completions of cach prefix of 00000 (red quantities). For example, the expected future grammaticality of the prefix 0008 it is now 0.45 i..._.... the algorithm effectively "looks ahead" to determine that only one valid (but low probability) string es that can follow 6eee. The ideas developed in GCD allow us to efficiently compute, for given string, the likelihood of the next tokens that will immediately result in non-grammaticality.
If we only sample one string from the LLM, we cannot hope to do better than GCD in terms of sampling faithfully in a grammar-alignen way. However, if we were to now sample once more, we could now better direct our sampling strategy. In the second iteration (right ofg. 3), the string 11111 is sampled and the expected future grammaticality is updated (red quantities). Note that at this point the probabilites assigned to the string 00000 from the carlier iteration have already been updated.
By repeating the above approach multiple times (i.e., by producing more samples), the ASAp algorithm produces precise approximations of the expected future grammaticalities and thus better samples from the constrained LLM.
The key quantity that the algorithm approximates based on past samples the expected future grammaticality (EFG) c(wi:)) = Eppwee tom wr [w E L(G)]). At iteration m 1. our algorithm uses the set of samples S {si..... Sm) observed so far compute an overapproximation ēs (w1::) of (s(w):) for every possible string wis. The overapproximation is inductively defined:
Algorithm Formalization
(s(w))) = (wi: E Epreffx(9) (s(W1s)) Em.. P(w++1 wiss) (s(Wi:
string in S starts with wi: otherwise
Intuitively, if no samples in 5 start with the prefix Wis, then (WW1:),, the overapproximation of EFG simply whether the string or is not a valid prefix in the grammar-icc the same overapproximation used by GCD. If, on the other hand, we have encountered the prefix win before in previous samples in S. the overapproximation uses the next token likelihoods that were computed during the previous sampling runs of the algorithm to compute a better estimate of EFG.
For example, in Fig. 3 once we have sampled the sequences 88000 and 11111, we have that čs (0000) 0.45 * 10 and Cs = (i.e., we have not seen a sample with the prefix 110 yet).
Theorem 1. Vwnx E Σ" (=,ū)((1:)) 2 c(w1=)-
Proof. To see that (swa))) is indeed an upperbound on c(wis), consider two cases: First, sup- pose wis not prefix of any string in S. this case, (s(wix) = [wii E (prefi(9)) and, like GCD, provides trivial upper bound. When [[Wid E Lpreax (G)] O, there is
5

---

no possibility of grammaticality along this path and the EFG is therefore also zero. When 1w1s E preffx (9)] = trivially bounds EFG, which is a probability. Second, we need to prove that Vun:
(S) (s(1::) 2 c(w1s). where prefix(S) is the set of (finitely many) prefixes of string in S. We proceed by induction, where the base case when Wis is in prefix(S) but no w1:++ is in prefix(S) for any possible next token W/+1- Consequently, every W1s+1 falls under the first case, leading us to the following incquality:
Eg (w(w)))
Σ P(W++1
w1:4) (5(111+11)
Σ P(we41 w1:+) c(w1s+1) = c(wix) (4) WE+1
01+1
Next, we move the inductive step where wi; is in pr) and for any W1+1, the string W1:++1 can either be a node that is not a prefix of S, which falls under the first case, or it can in prefix(S). for which the property holds by induction. Therefore, the reasoning used in Eq. 4 works for the inductive case as well.
The sampling procedure itself proceeds autoregressively like GCD, but using the iteratively updated EFG estimates we have just defined, čg. Specifically, the left-to-right sampling conditional for our procedure, (2:s[w]wss)) after having previously sampled the strings in S, is defined as follows:
P(w; w1=-1) (w1:))
(s(w)/wa:-)) = Emy P( wis-1) ös (wi--1, w
(5)
Our overall algorithm, which is presented in Algorithm I then proceeds iteratively, using past samples to improve subsequent samples. Whenever the sample set S is updated with a new sample Winn, the over- approximation is updated for the prefixes of Win. The update begins at the end of the sequence and proceeds backward to- ward the start, by the recursive definition in 3q.3] In the listing, we assume that we are only interested in the final sample, but our evaluation we will analyze whether the algorithm induces the desired distribution.
Algorithm 1 ASAp algorithm
Initialize == 0} ēs(+) :=
for S M do
Draw wi:n ~ Qs via ancestral sampling S = S=Sum (w1:n)
for in (n 1)... do
for w/ in {w' Wi: w' $ Eprefx do
?s(win w') :=
cs (w(:):) = Ew P(w' [wis)= čs (s(wis-u w²)
return Final sample Wi:n
Next we provide proof that this algorithm converges to exact estimates of EFG in the limit of infinite iterations, and therefore to exact samples from the constrained LLM distribution. The theorem assumes almost sure termination of ancestral sampling in the unconstrained LLM distribution P-i.e., the L.LM eventually terminates.
Theorem 2. Assume that as L - oc, the distribution assigns vanishingly small probability mass to sequences longer than length L. Now, let Sm = {s,,.... 8m} be the set of recorded samples up to the math iteration of ASAp. Then, Vwrs E Eproffix (9), ūs... (w)x) 23 c(wi.)) as m. + co.
Proof. Let Win be an arbitrary sequence in (g) The approximation gap after m iterations of sampling with ASAp, ém = čs. (Wis)) c(wi,)), is equal to the marginal probability under P of all ungrammatical continuations of wis that have not yet been encountered the first m samples, S.n- Now consider an arbitrarily small >> 0. By assumption, there exists an I. such that the probability mass P places on sequences longer than is less than e. Further, ASAp samples according to P, but re- re-weighted by an upper bound on the true EFG (Theorem 1). Thus, the probability of encountering a previously unseen ungrammatical continuation of wis no longer than L on any given iteration is at least as high as the probability of encountering the same continuation when sampling directly from P. Because the number of sequences no longer than L is finite, this implies that the probability mass under P of ungrammatical continuations of Wid that are no longer than L and that are not yer encountered in S, becomes vanishingly small as as m + oc. The remaining unencountered ungrammatical continuations of wi.i are longer than L, and thus their total mass bounded by e. Therefore P(em > e) + O as m + 0o.

---

Deternines what terns can appear (set-logic SLIA)
Determines what terms can appear (set-logic
The function to synthesize
; The function to synthesize (synth-fun inv
fsynth-fun f ((nane String)) String
The grammar for to be synthesized in ( ((Start String (S))
((s (BitVec 4)) (t (BitVec 4)))
(BitVec 4))
(5 String
; Helper functions
(name "_"
(define-fun min (BitVec 4)
(str.++ 5 S)
(bvnot (bvlshr (bvnot #x8) #x1)))
(str.at S I)
(define-fun max (BitVec 4) (bvnot min)) (define-fun
replace 5
(ubr. S I)))
((s (BitVec 4)) (t (BitVec 4))) Bool
(I Int
(bvsgt (bvnot (inv s t)) t))
(0 1 (+ I) (- I)
(define-fun SC
(str. len S) (str.indexof I)))))
((s (BitVec 4)) (t (BitVec 4))) Bool (distinct max))
Specifications to satisfy
; Specifications to satisfy
(constraint (- (f (rennyy_reetaferr) "N.F."))
with universally quantified variables (declare-var (BitVec 4))
(constraint (= (f "Andrew_ (eadrew_Cencici)) "A.C."))
(constraint (= (f "Jan Kotas") *J.K."))
(declare-var t (BitVec 4))
(constraint (= (f "Mariya, Sergienko") "M.S.") "))
(constraint (=> (SC $ t) (1 t)))
(a) SLTA/inttials-snal!
(b) INV www-Bv/fine BV/find inv_bvvlle www.srlllllhrreeeeeeeeee
Start 5
Start
S :
name " "!"
BV :== s
str.+t S $ str.at
#x7
str. replace $ S
bvneg BV bvnot BV bvadd bvsub BV
str.substr S I
I === 0 2 I| II
bvand BV BV bvlor BV BV bvlshl BV BV bulshr BV BV
str. len str. indexof 5
(c) Grammar for
(d) Grammar for inv
Figure 4: (a) A SLIA problem which grammar for the target function explicitly defined. (b) INV-BV problem which the grammar for the target function inv is implicitly defined. (c) The explicitly defined grammar for written in BNF notation. (d) The implicitly defined grammar for inv written in BNF notation. The grammar implicitly defined by primitives of BV logic and parameters of inv. The goal of each problem find an implementation for synth-fum fun functions that satisties all the constraints within a specified grammar ie.. to find implementation of in the grammar (c) and inv in the grammar (d).
4 Experiments
We implemented the ASAp algorithm as an extension of the Transformers-CFG implementation of GCD 8 When the LLM generates sequence Wi.n. the ASAp algorithm keeps track of the original LLM's probability P(w; w1s-1) for & S n and the set allowed next tokens {w, W1i--, w/ E L(G)} determined the incremental parser in the Transformers-CTF library. After the LLM finishes generating a sequence, our implementation of ASAp updates the overapproximation čs pookppropggating the quantity minus probability of the tokens that will for sure lead to non-grammatical sequences. The implementation of ASAp updates ēs (Wim-11 w,,) for all possible tokens w',, and then moves on update ēs (Wim-2, w/-1) ... (s wh), (s(w() using Equation 33.
from the end of sequence
Datasets and Models. We consider the benchmark from Example and three structured-decodingg tasks. Two of our tasks involve solving Syntax- -Gideed Synthesis Problems (SyGuS) 2 SyGuS standardized format where one provides a logical specification and a context free grammar of first-order terms and the goal is to synthesize term in the grammar that satisfies the specification. SyGuS natural for GAD and we consider two tasks from standard SyGuS benchmarks where grammars vary from benchmark to benchmark: strings with linear integer arithmetic (SLIA) and loop invariant generation with bit-vector arithmetic (INV-BV). In the former, the grammar used to restrict what constant strings one can when building string- sainnggmaipplattnng programs and in

---

50
23
100
100
1000
20
(a) Illustrative
Ex.
(b) SLIA/name wwwaane--ominnn combine long
(c) SLIA/Initiats--mal
Figure 5: KL(QAsApIIP) and K KL(QocD|P))
37-
(a) Illustrative Ex.
(b) SLIA/name- combine-4a lang
(c) SLTAinittaalss
Figure 6: Expectations of QAS QOO, and P
the latter the grammar is used to restrict constant bit-vectors and operations used to build invariants. Fig. provides examples of SLIA and INV-BV problems. For both families of benchmarks, our prompts consist of 3 in-context examples of the form (specification, solution) and the grammar is constraint for GAD. Our third task is the constituency parsing (CP) task already used in prior GCD work [ where the grammar is used to help the model produce well well-parenthesized parse trees for English sentences.
then provided
Due to constrained resources and needing to run inference multiple times to measure whether the distribution Q faithful to Q, we randomly select 15 SLIA problems, 15 INV-BV problems, and CP problems. We select the open-source Mistral-7B 112 for evaluation due to its superior reasoning and code generation capabilities.
Measures. We run both algorithms for 2,000 iterations/sample on each benchmark.
To assess converge to the target distribution, we measure the Kullback-Leibler (KL) divergence between the distributions of GCD and AS from the target distribution Q for given number of samples. Because the ideal GAD distribution QP.g is proportional to the original LLM's ' distribution P for sequences allowed by grammar G. we can use the LLM's distribution P on all observed samples estimate Qp..- The quantity KL(QIIP) only differs by constant from the KL divergence between empirical distributions and the ideal GAD distribution:
Q
Q QP.s)
KL(
log - -E
log
=
Eq
log
log (KKKQQQQ))))) log
C-QP.
where C' = E.. 1 E ((w). Thus, (L()))P) can be used to quantify the alignment between the empirical distributions of GCD and ASAp with the ideal GAD distribution.
For example. Fig. 5a shows convergence results for the first 75 iterations the illustrative the KL divergence for AA quickly converges whereas the one for QGCD doesn't.
i...
We also compare the empirical expectations of the variables QoCD. AASAn and P. For example,
Fig. 6a shows convergence results for the first iterations on the illustrative Ex. i... Q ASA converges to the right expectation.

---

17
63
14
42
(a) SLIA
(b) INV-BV4
(c) CP
Figure Scatter plots Ap (+) and Qaen (x) vs. expectations after 2,000 samples. Proximity to the diagonal indicates proximity to the actual expectation e.g., e. a at (0.45,0.4) indicates a benchmark where the empirical expectation of 0.45 and QASAD had converged expectation of 0.4 after 2,000 iterations.
Results. Fig. 5b and Fig. 6blillustrate benehmark which our ASAp algorithm quickly converges to the target distribution. Fig.. deppccs the KL divergence of a sliding window of size 500 (e.g.. the points at x=800 denote the KL divergence of the samples (00-1300), Fig. depicts all the samples from the experiment, as well as how the expectations converges (a point at x=i denotes the empirical expectation on the first samples. For this case the expecation for GCD stays very close to 0.
Similarly, Fig. 5c and Fig. 6c illustraaee a benchmark in which our ASAp algorithm converges slowly. In this case, bot ASAp and GCD are far from the target expectation (Fg. 6c), but because GCD happens to be biased towards the most likely outcome, it exhibits better KL divergence. The complete set of plots shown Sec. E.T.
To better understand how the algorithms respectively converge, Fig. 7 category the expectations for each benchmark computed by GCD and ASAp against the target expectation of after 2,000 iterations. The sum of least square difference between expectations computed by GCD and the expectations of P are 2.259 (SLIA), 1.852 (INV-BV4), and 0.1 (CP). The sum of least square difference between expectations computed by ASAp and the expectation and those of P are 1.242 (SLIA), 0.802 (INV-BV4), and 0.159 (CP). While we have too few points for CP to draw conclusions, the expectations computed by ASAp are much closer to the ones computed by GCD across our experiments.
plot for each benchmark
While our work is interested the theoretical convergence of the ASAp algorithm, we also report how the GCD and ASAp differ for solving the SLIA and INV-BV4 tasks-i.e., how many of the sampled programs are correct solutions to the given problem. GCD and ASAp solve approximately the same of problems (there is just SI.AA benchmark for which ASAp returns valid solution on one sample and GCD never does so). ASAp produces correct samples 38% more often than GCD (geomean), whereas for SLIA benchmarks that both tools can solve, ASAp produces correct samples 73% less often than GCD (geomean). Detailed results can be found in Sec. E.2 These results are in line with the fact ASAp shows faster convergence on INV-BV4 benchmarks. For example, for the benchmark illustrated in Fig. 5b) ASAp returns the correct solution for 1 1588 samples, whereas GCD only returns the correct solution 12 times, whereas for the benchmark in Fig. 5c ASAp returns the correct solution 69 times and GCD 363 times.
Discussion and Limitations. As predicted by our theorems, most benchmarks the ASAp algorithm converges to the desired distribution P whereas GCD does not improve over time (i.e., exhibits the bias described in this paper).
While ASAp has no strong effect on solving downstream tasks, we observe that on instances where the convergence is prominent, ASAp ends up sampling correct solutions more often than GCD, which what we expect when the L.LM
"learned" how to solve the given task.
The key limitation of our work is the current slow convergence the ASAp algorithm. In some benchmarks, even after 2,000 iterations the KL divergence barely improves and even though the expectation of Q AS is improving, it converges very slowly.
We highlight that the contributions of this paper are discovering and formalizing the bias of existing constrained decoding approaches and proposing the first converging algorithm to address this problem.

---

Now that we have identified the problem, there are many "low- howgingg fruits" to improve our sampling strategy, which are great targets for future work e.g. using forms of targeted beam search to bootstrap our sample set to better explore grammar paths and avoid sampling similar strings.
5 Related Work
Constrained Decoding Past work has extensively explored constrained decoding algorithms, which modify the original decoding process of LLMs to ensure the output adheres to user-specified
25 (26 in a discrete space. Other works enforce hard output constraints using dynamic monitoring and verification methods 15 27 or by modifying beam search techniques to impose lexical constraints, which require specific keywords to 17 20] At high level, these methods involve running the LLM decode in parallel with a monitoring scheme (e.g.. parsing algorithms for CFGs) to identify which next tokens or beams produce valid output sequences that meet the constraints. The decoder then masks out any tokens that would lead to invalid sequences, sampling only from the permissible ones.
regular [18 [8] or context-free language [5 6 19 23 24
appear in the generated text [4, 99 10 16
To incorporate sequence-level soft semantic or contextual constraints, Amini et al. [3], Kumar et al. [3], Li et al. [14], Qin et al. [21] have applied gradient-based sampling techniques that relax those constraints to differentiable ones, used them as classifiers to further guide the decoding process. While these works guarantee that the decoded output meets the specified constraints (whether in the form of grammar, monitoring schemes, or differentiable functions), they often operate greedily and introduce bias into the output distribution in the way that has been discussed in this paper. Depending on the application one considers, this problem may or may not affect downstream tasks, but as we have argued in this paper, the bias can be quite prominent and sometimes affect downstream performance. Our adaptive decoding algorithm improves decoding over time by analyzing how previous samples led to nongrammaticaility.
Constraint- Aligned Decoding This paper formally defines the problem of aligning the output distribution of an LLM in the presence of constraint. We focus our attention on constraints expressed as grammars, but our definitions and algorithm apply to any constraint for which possible satisfaction (in our case grammaticality) can be evaluated in a left-to-right manner.
In some settings, one is interested in generating multiple outcomes with an LLM to approximate a e.gg, to generate random number set of good test cases for a program. As we have shown, constrained decoding can heavily skew the LLMs distribution and result biasing the model towards certain constraint-matehhe matching sequences. While our work is at this point theoretical, now that the problem of aligning an LLM's distribution with constraints has been defined, we expect advances in how sampling is performed to quickly converge to better distributions faster (e.g., using beam search to quickly explore possible paths instead of just sampling).
distribution of interest [1] 22
6 Conclusion
We have introduced a new analysis of the ideal target for constrained sampling from an LLM using a grammar, which we call grammar-aligned decoding (GAD). We proposed a new algorithm for GAD which we call ASAp that iteratively builds better approximations to the critical re-weighting term required for GAD: the expected future grammaticality. We analyzed the convergence of our proposed algorithm and demonstrated its effectiveness in relation to existing techniques a set of benchmark code generation tasks. We analyzed and evaluated our approach using constraints enforced by a context-free grammar, however, extensions of our approach might be applied to more general classes of constraints for LLM decoding.
decoding
While the primary goals of this work are to formalize the likelihood misalignment problem of existing coummar-constringge decoding approaches and to provide an initial solution with provable asymptotic guarantees, future work may explore faster-converging approaches, such as sampling multiple tokens simultaneously, to improve efficiency further. We hope this work lays solid foundation for generating structured outputs from L.MMs without distorting the original distribution, advancing the field toward more efficient, trustworthy, and cesttrinn-alignee approaches in LLM-driven generation.
10

---

Acknowledgement
The authors would like to thank NeurIPS anonymous reviewers for their insightful feedback and helpful discussions. The authors thank Gurindar S. Sohi, Shivaram Venkataraman, Ming Liu, and Yixuan Li for the support of computing resources. This work is supported. in part, by NSF under grants CCF-1918211, CCF-1955457, CCF-2023222, CCF-2200333, CCF-221 1968, CCF-2402833, CCF-2422214, and CCF-2446711. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors, and do not necessarily reflect the views of the sponsoring entities.
References
[1] Lakshya A Agrawal. Aditya Kanade, Navin Goyal, Shuvendu K. Lahiri, and Sriram K. Raja- mani. 2023. Monitor-guided decoding of code lms with static analysis of repository context In Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023.
[2] Rajeev Alur, Dana Fisman, Saswat Padhi, Rishabh Singh, and Abhishek Udupa. 2019. Sygus comp 2018: Results and analysis
[3] Afra Amini, Li Du, and Ryan Cotterell. 2024. Structured voronoi sampling. Advances in Neural Information Processing Systems, 36.
[4] Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016. Guided open vocabulary image captioning with constrained beam search. arXiv preprint arXiv:1612.000.
[5] Luca Beeure-KKlllnet Mare Fischer, and Martin Vechev. 2023. Prompting is programming: A query language for large language models Proc. ACM Program. Lang.. 7(PLDI).
[6] Yihong Dong, Xue Jiang. Yuchen Liu, Ge Li, and Zhi Jin. 2022. Codepad: Sequence- code generation with pushdown automaton. arXiv preprint arXiv:2211.00818
[7] Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023. Grammar-constrained decoding for structured NLP tasks without finetuning, In Proceedings of 2023 Conference on Empirical Methods in Natural Language Processing, Singapore. Association for Computational
Linguistics.
[8] Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023. Transformers-CFG. https://github.cm httpstthu..com/ppeeee wtaarrlaaaabbrrrasforerrrssssss
[9] Chris Hokamp and Qun Liu. 2017. Lexically constrained decoding for sequence generation using grid beam search. arXiv preprint 17400:170..07138.
[10] J Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. 2019. Improved lexically constrained decoding for translation and monolingual rewriting. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 839-850.
[11] Linghan Huang, Peizhou Zhao, Huaming Chen, and Lei Ma. 2024. Large language models based fuzzing techniques: A survey
[12] Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023. Mistral 7b. arXiv preprint arXiv:2310.0683
[13] Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. 2022. Gradient-based constrained sampling from language models. Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages
[14] Xiang Li, John Thickstun, Ishaan Guirajani, Percy S Liang, and Tatsunori B Hashimoto. 2022. Diffusion-Im improves controllable text generation. Advances in Neural Information Processing Systems, 35:4328-433 -3343.

---

[15] Yixuan Li. Julian Parsert, and Elizabeth Polgreen. 2024. Guiding enumerative program synthesis with large language models. In International Conference on Computer Aided Verification, pages 280-301. Springer.
[16] Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan
Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. 2022. NeuroLogic a aeequu decoding: Constrained text generation with lookahead heuristics) In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 780-799, Seattle, United States. Association for Computational Linguistics.
[17] Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2021. Neurol decoding: (un)supervised neural text generation with predicate logic constraints, In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4288-4299 Online. Association for Computational Linguistics.
[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 preprint arXiv:2402. 17988.
[19] Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022. Synchromesh: Reliable code generation from pre-trained language models. arXiv preprint arXiv:2201.11227.
[20] Matt Post and David Vilar. 2018. Fast lexically constrained decoding with dynamic beam allocation for neural machine translation. arXiv preprint arXiv: /84.06990
[21] Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. 2022. Cold decoding: Energy- based constrained text generation with langevin dynamics. In Advances in Neural Information Processing Systems.
[22] Alex Renda, Aspen K. Hopkins, and Michael Carbin. 2023. Can LLMs generate random numbers? evaluating LLM sampling in controlled domains In ICML 2023 Workshop: Sampling and Optimization in Discrete Space.
[23] Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021. PICARD: Parsing incremen tally for constrained auto-regressive decoding from language models] In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 9895-9901, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
[24] Richard Shin, Christopher H Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Anto- nios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. 2021. Con- strained language models yield few-shot semantic parsers. arXiv preprint 104.022104.08768.
[25] Elias Stengel-Fskin, Kyle Rawlins, and Benjamin Van Durme. 2023. 7ero and few-shot semantic parsing with ambiguous inputs. arXiv preprint arXiv:2306. 00824.
[26] Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. 2024. Improving Ilm code generation with grammar augmentation. arXiv preprint 2231:24033.0133..
[27] Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. 2023, Grammar prompting for domain-specifee language generation with large language models
[28] Brandon T Willard and Rémi Louf. 2023, Efficient guided generation for large language models. arXiv e-prints, pages arxi--2307
12

---

Appendix
A Hardware and Software
Our experiments are conducted on 4 NVIDIA RTX A6000 GPUs and 4 NVIDIA A100 GPUs. Our implementation based on Python 3.10 and PyTorch 2.1.2.
B Hyperparameters
The hyperparameters discussed in this paper pertain to the decoding strategy of language models. As we aim to investigate the I.M's original distribution, we set Top-P at 1.0, Temperature at 1.0, and Top-K at ( to consider the complete token vocabulary.
C Model Checkpoint
We use the Mistral-7B model checkpoint provided by Hugging Face: https://hugginngaccecc mistralat/Mistral- Instruct-v8.2)
D Experimental Details
D.1 SLIA and INV-BV
Prompt Construction For both families of benchmarks, our prompts adopt standard in-context learning format which consist of in-context examples of the form (specification, solution) and ask the model to provide the solution for the last example. A concrete example would be
You expert in program synthesis.
You are tasked with solving a Syntax- Guided Synthesis (SyGuS) problem.
Your goal to output function that should produce outputs that satisfy series of constraints when given specific inputs.
Question: logi- BV)
(synth-fun inv ((s (BitVec 4)) (t (BitVec 4))) (BitVec 4))
vdeclare-var s (BitVec 4))
(declare-var (BitVec 4))
(define- fun udivtotal ((a (BitVec 4)) (b (Bitvec 4))) (BitVec 4)
(ite (= #x0) #xF (bvudiv b)))
(define-fun uremtotal ((a (BitVec 4)) (b (BitVec 4))) (BitVec 4)
(ite (= #x0) (bvurem b)))
(define-fum min () (BitVec 4)
(bvnot (bvlshr (bvnot #x0) #x1)))
(define-fun max () (BitVec 4)
(bvnot min))
(define-fun ((s (BitVec 4)) (t (BitVec 4))) Bool
(bvsle (bvlshr (inv s t)) t))
(define-fun SC ((s (BitVec 4)) (t (BitVec 4))) Bool (or (bvult t min) (bvsge s)))
(constraint (=> (SC t) (1 t)))
(check-synth)
Solution:
(define-fun inv ((s (BitVec 4)) (t (BitVec 4))) (BitVec 4) (bvnot (bvor #b6111)))
(2 more examples)
13

---

Question: (set- BV)
(synth-fun inv ((s (BitVec 4)) (t (BitVec 4))) (BitVec 4))
var (BitVec 4))
(declare-var t (BitVec 4))
(define-fun udivtotal ((a (BitVec 4)) (b (BitVec 4))) (BitVec 4)
(ite (= #x0) #xF (bvudiv a b)))
(define-fun uremtotal ((a (BitVec 4)) (b (Bitvec 4))) (BitVec 4)
(ite (= b #x0) (bvurem a b)))
(define-fun min () (BitVec 4)
(bvnot (bvlshr (bvnot #x0) #x1)))
(define-fun max () (BitVec 4)
(bvnot min))
(define-fun ((s (BitVec 4)) (BitVec 4))) Bool
(bvsgt (bvnot (inv t)) t))
(define-fun ((s (BitVec 4)) (t (BitVec 4))) Bool (distinct max))
(constraint (=>
(SC s t) t)))
(check-synth)
Solution:
Grammar Constraint While most SYGUS problems contain grammar constraints, problems have grammars implicitly defined by the theory. We explicitly converted the grammar constraint of the problem into EBNF format for constrained-decoding The example for the last example would be
root ::= (define- fun ((s (BitVec 4)) (t (BitVec 4))) (BitVec
Start ")"
Start ::= "s" "t" "#x0" | "#x8" "#x7"
"(" "bvneg" Start ")" "(" "bvnot" " Start ")"
"(" "bvadd" Start Start "}" | "(" "bvsub" Start Start ")"
"bvand" Start " Start "}" "(" "bvlshr" . Start Start ")"
(" "bvor" Start Start ")" "(" "bvshl" Start Start ")"
D.2 Constituency Parsing
For Constituency parsing task, our prompts consist of 8 in-context examples of the form. A concrete
example would
Perform constituency parsing on the provided sentences in accordance with the Penn TreeBank annotation guidelines. Fill in the last mapping.
Ad Notes
->
NP-HLN Ad ( NNS Notes ) ) ]
The market crumbled
->
S ( NP-SBJ ( The ) ( market VP VBD crumbled )
felt betrayed he later said
->
( S ( S-TPC-1 NP-SBJ PRP I ) ) ( VBD felt ) ADJP-PRI -RD ( VBN betrayed ) NP-SBJ PRP he ) ADVP-TMP RB later ) ) ( vP VBD said )
Friday October 13 1989
->
NP NNP Friday NNP October CD 13 ) ( CD 1989
14

---

Arabs had merely oil
( s ( NP-SBJ ( The ) ( NNPS Arabs ) ( VP ( VBD had
NP RB merely ) ( NN oil )
Energy ->
NP-HLN NN Energy
Some U.S. entrepreneurs operate smaller scale
->
( NP-SBJ Some NNP U.S. entrepreneurs
VP VBP operate
PP-MNR IN on ) ( NP ( DT [JR smaller NN scale ) }
Knowledgeware Inc.
->
( NP-HLN NNP Knowledgeware )
NNP Inc. ) )
They are more sophisticated this time
Grammar Constraint For the constituency parsing (CP) task we used the grammar provided in prior GCD work 7 The grammar is too large to attach, but it used to help the model produce well- parenthesized parse trees and ensure that all words in given English sentence appear in left-to-right order.
15

---

(a) KL divergence
(h) Expectations
(a) KI. divergences
(h) Expectations
Figure SLIA/dr-name name
Figure SLIA/firstname.. small
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure SLIA/firstname
Figure SLIA/initials small
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure 12: SLIA/initials- leriss---ng----eppee
Figure SLStamas
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure SLIA/name- combine short
Figure SLIA/name htw//aame-combineee... long repeat
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure 16: SLIA/name- conbiee--onnneeeeeee 4-sort
Figure 17: SLIA/name combine--beee.e long
E Detailed Experimental Results
We provide additional plots and experimental data.
E.1 Plots
Figures 8-22 provide the KI. divergene and expectation results for the SLIA benchmarks. Figures 23- 37 provide the KI. divergence and expectation results for the INV-BV benchmarks. Figures 38-43 provide the KL divergence and expectation results for the INV-BV benchmarks.
16

---

(a) KL divergences
(h) Expectations
(a) KL divergences
(h) Expectations
Figure SLIA/phone- L-nng
Figure wtw.//eeerreennee--ooee
(a) KL divergences
Expectations
KL divergences
(b) Expectations
Figure 20: SLIA/UnIv. 1 short
Figure 21: SLIA/univ.]
(a) KT. divergences
Expectations
KL divergences
(b) Expectations
Figure 22: 2..h/
Figure 23: IWVBV/find www.e.sge....m www.bvsge.bblshr1. bvlshr1. 4bit
(a) KL divergences
Expectations
KL divergences
(b) Expectations
Figure 24: INV-BV/find bnvee bvneg.4br 4bit
Figure 25: INV-BV/find. bvsge www.ge.bwoot..o. bbit
(a) KL divergences
Expectations
KL divergences
(b) Expectations
Figure 26: INV-BV/fime inv www.t.sstt.bbo. bbit
Figure 27: IW-BV/find. inv www.btugt..bb.. bvashr0
E.2 Correctness Results for SYGUS Tasks
Table [ shows how many samples (out of 2000) yielded correct solutions for each benchmark (bold better). The task initials Jong-repeat was only solved using ASAp
17

---

(a) KL divergences
(h) Expectations
(a) KI. divergences
(b) Expectations
Figure INV-BV/ NWV-BV/inn. www.bvugt..bvee. bvneg..4itt
Figure INV-BV/find bvule bwurend 4bit
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure 30: INV-BV Bwt.-///fiiiiieei www.bvute.bvvree...... bvurem1.4bi
Figure 31: INV-BV/find env blwdd_
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure 32: INV-VV BV/find lev__e__bbveeeeeeeeooeebbbbbrn bwl.hro_.bbbrt
Figure 33: INV-BVA ww--BV/find..i inv_ne__vvvnneeeeeeeeeeeeeeeeeee bwweg_veeeeeee 4bit
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure 34: INW BV/find inv_ne__i__eeeee vo bwudivo__4bl
Figure 35: INV-BV IWV-BV/fidd inv_ne__buddeeeeeeeeeeeee bvudivl_444 4bit
(a) KL divergences
(b) Expectations
(a) KI. divergences
(b) Expectations
Figure 36: WW--BV/ind..m wnwpiinddddddnnnnnnnee ne_ bwwremo. 4bit
Figure 37: INV-BVffind inv_ne ne. b
Will ASAp still be more aligned than GCD after fine-tuning?
F1
Experimental setup for fine-tuning
We adhere established QLoRA finetuning pipeline and create task-specific datasets of INV-BV4 and CP for instruction tuning. In line with paper's methodology, we incorporate in-context examples in the instruction tuning dataset to enhance the models' performance in in-context learning. For each task, we independently finetune Mistral-7B. resulting in two versions of the model (for
18

---

(a) KL divergene
(b) Expectations
(a) KI. divergences
(b) Expectations
Figure 38: CP/CP_ re. rtt 46b
Figure 39: CP/CP_ re.
Viel
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure 40: CP/CP_ re. Sett-_reeebbb.B_8_ 486
Figure 41: CP/CP_ rt.
(a) KL divergences
(b) Expectations
(a) KL divergences
(b) Expectations
Figure 42: ee/CP_re.ptb..14 1434
Figure 43: ptpp//.eeeepb.....
INV-BV4 and CP). We employ standard train-validation-tes. split of 70-10-20% Instruction tuning conducted on the training set, and model selection based on the lowest validation loss. Key hyperparameters include a learning rate of 2e-4, warmup ratio of 0.03, maximum sequence length of 2048, LoRA alpha 32, LoRA dropout of 0.05, and LoRA rank of 64. The best checkpoints were at 328 and 536 steps for INV-BV and CP, respectively.
F.2 Additional Results
No significant differences in convergence rates post fine-tuning. Section we evaluate ASAp and GCD on the base model Mistral-7B. A natural extension of this evaluation is determining whether ASAp retains advantages over GCD after fine-tuning the base model on sask-specific datasets, which optimizes the LLM for higher grammatical accuracy from the start.
In our fine-tuning step, want teach the L.M to assign higher probabilities to grammatical outputs for the specific task DSL. We randomly selected two INV-BV problems inind_ii_bbvgge.... -eiegee.bvneg_4ie 4bit and inw.iistsbbs.....mmo.. brortt_vor__bb_b_ for INV-BV) and four CP problems (CP_re_ptb_211 215_ cP_re_ptb_434, ce_re_t 1627 and CP re- pe_.tt______ 1643 for CP) from the test set, and instrction tuned input-output pairs of prompt and output programs in the training set for the base model Mistral-7B. We obtained two fine-tuned models, one for INV-BV and one for CP.
We tested GCD and ASAp the finetuned Mistral-7B the randomly left-out problems and checked the convergence rates of the KL-divergence. The results from finetuned Mistral-7B did not show significant differences in terms of convergence compared the base Mistral-7B. As done in Section 4 we computed the expectation for each benchmark obtained via GCD and ASAp after 2,000 iterations and compared it against the target expectation Q of GAD. The sum of least squares difference between expectations computed by GCD and the expectations of QPS are 0.677 (INV-BV4), 0.278 (CP), while ASAp achieved lower errors: 0.051 (INV-BV4), 0.201 (CP), indicating that ASAp more closely aligned with the exact GAD expectations. We did not include SLIA as we did have sufficient data for further fine-tuning
19

---

Table I: Correctness of solutions for different algorithms.
Benchmark
Correct ASAP
Correct GCD
phone-3-long
0
name-combine-2_.ke
171
319
name-combine-2-lon---eppp
0
name-combine-4-ae
20
11
name-combine-4-long
1588
12
lastname
285
1526
firstname
1960
1997
firstname firstname_small small
1754
1997
SLIA
reverse-name-long
1981
1859
univ
67
40
univ univ_I_short univ_2_short
605
1859
0
dr-name
357
1654
69
363
initials long initials_ Setials_long-repaat
540
1584
3
find und_inv__uu _nw_ee________ee bvudvvi I_iit find inv_ ____in__buuuu ____g__baaashrr find ind_inv_eed htw__e___bee__eeeeee _nt______blsshO___________ tir__e__vvand__ 4bit
0
bvashrO 4bit
83
49
bvlshrr 4bit
635
228
1599
1305
INV-BV
find inv_ jtd_jilv_buleeee bwwuebbm__maaeeeee 4bit
1813
1710
Bi__ivv_bvsgt_bve 4bit
11
10
84
36
find_inv_bve @erule_bvrrem__ee _bit
143
227
20

---

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]
The main claims are well-supported by the algorithm formalization and theoretical results in Section 3 and comprehensive experiments in Section and further results in the Appendix.
Justification:
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide detailed limitations in Section 4
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems are accompanied by formal proofs.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all the hyperparameters we use Appendix B model checkpoints in Appendix and experimental details in Appendix Do support the reproducibility of our experiments. The codebase and datasets with detailed instructions will also be released.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will attach datasets we covered in this paper during submission and the code will be released with detailed instructions.
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 to understand the results?
Answer: [Yes]
All experimental details are included in Appendix to to facilitate a better understanding of our setting.
Justification: Hyperparameters are included in Appendix B
7. Experiment Statistical Significance
Question: Does paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our experiments are run on 2,000 sampling iterations for which we show plots for convergence. Given the cost of the experiments we cannot run on multiple seeds, but high number of iterations mitigates the problem. Therefore, error bars not applicable.
8. Experiments Compute Resources
21

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide hardware and software details in Appendix A
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The authors have read the NeurIPS Code of Ethics and made sure the paper follows the NeurIPS Code of Ethics in every aspect.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper simply improves sampling. Existing LLM approaches will benefit from it, but the work will not directly lead to specific broader impacts.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
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: The paper properly cites the original paper sources whenever asset is used. URL the model checkpoint is included in Appendix C
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will attach the datasets as part of our submission and the code will be released with well-documented instructions.
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 to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects. 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: This paper does not involve crowdsourcing nor research with human subjects.
22


Reviews:
[{"review_id": "rB5NC3ODfT", "reviewer": "Reviewer_cHBv", "summary": "This paper points out that prior methods on grammar-constrained decoding (GCD) distorts the language model's learned distribution over sequences. At the heart of this exposition is the notion of _expected future grammaticality_ (EFG), where prior GCD methods can be cast an an upper-bound approximation to the EFG. To ameliorate this problem, the authors proposed the ASAp method: through many iterations, the EFG of a prefix can be better estimated.", "questions": "- L10: \"prorblem\" => \"problem\"\n - Missing related work: R Shin, et al (2021): Constrained language models yield few-shot semantic parsers. https://aclanthology.org/2021.emnlp-main.608/\n - Alg 1: What is \"ancestral sampling\"? Please explain.", "limitations": "The authors adequately discussed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is an important finding that conventional methods on grammar-constrained decoding distorts the language model's learned distribution. As far as I know, this important fact has not been pointed out before. The notion of expected future grammatically will be impactful in the area of sequence decoding.", "weaknesses": "The proposed method seems very slow to run, requiring many iterations. Additionally, it requires storing a table of all seen prefixes and their future grammatically, which would be very large if the grammar itself is large.\n\nIt seems to me that the ASAp method only depends on a grammar -- it does not specifically requires a training or test set to run. I wonder if it would be possible to first sample extensively and train the ASAp EFG estimates, then decode on a set. In this way ASAp can be cast as a preprocessing step of the grammar: if it is very slow, it wouldn't matter much since it'll only be processed once. \n\nFor example we are doing NL2SQL under many conditions. The target grammar stays the same: SQL. One can utilize a LM and generate massive amount of prefixes that has EFG > 0, then compute this estimation of $\\tilde c_S$ for all these distinct prefixes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The proposed method seems very slow to run, requiring many iterations. Additionally, it requires storing a table of all seen prefixes and their future grammatically, which would be very large if the grammar itself is large. It seems to me that the ASAp method only depends on a grammar -- it does not specifically require a training or test set to run. I wonder if it would be possible to first sample extensively and train the ASAp EFG estimates, then decode on a set.\n\nWe acknowledge that our proposed method can be slow to converge. However, the main focus of the paper is to formalize the likelihood misalignment problem in existing grammar-constrained decoding, and to provide an initial solution to address this problem together with a proof of convergence. The reviewer is right that there could be better decoding approaches, and we have started exploring several approaches as part of our future work (e.g., as hinted by the reviewer, sampling more heterogeneous sequences during preprocessing, and training a neural estimate of expected future grammaticality, offline, to use later during test-time sampling).\n\n> Missing related work: R Shin, et al (2021): Constrained language models yield few-shot semantic parsers.\n\nWe thank the reviewer for providing the missing early related work on grammar-constrained decoding. Semantic parsing is a very interesting application we plan to investigate in the future. We will include this paper in our revision.\n\n> Alg 1: What is \"ancestral sampling\"? Please explain.\n\nIn the literature, `ancestral sampling' is commonly used to describe the default process for sampling from a locally normalized generative model, that is, sample the variables in order of a topological sort of the graphical model. In left-to-right autoregressive models like LLMs, this is equivalent to just sampling tokens left-to-right. We will add this explanation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZqEwxHehCd", "reviewer": "Reviewer_CJH3", "summary": "This paper proposes adaptive sampling with approximate expected futures (ASAp) for grammar-aligned decoding for LLMs. The main objective of this method is to match the conditional probability of the LLM’s distribution conditioned on the given grammar. The evaluation is performed on code generation and structured NLP tasks showing a better likelihood for LLM’s outputs being grammar-constrained.", "questions": "I suggest maybe some improvement in Section 2. Restructuring it maybe and providing slightly more context on CFG (or giving a concrete example of how it works as a reminder, I found Fig 1 not illustrative enough), I'm sure I won't be the only reader who doesn't have recent experience with CFG.", "limitations": "Yes, limitations are discussed. What I liked in particular in this paper is that the limitations of ASAp are well exposed and discussed throughout the paper and not just in the limitations section.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The method is well-formalized and clear. The examples are very useful for faster understanding\n- The method is well-motivated (there isn’t an independent motivation section but each choice in the design of the method is appropriately justified)\n- The paper provides empirical validation that the method works and that it improves the benchmark scores", "weaknesses": "- Nothing in particular. Maybe I have found Section 2 of the paper somewhat difficult to read but it is probably because of my lack of recent readings on CFG.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I suggest maybe some improvement in Section 2. Restructuring it maybe and providing slightly more context on CFG (or giving a concrete example of how it works as a reminder, I found Fig 1 not illustrative enough), I'm sure I won't be the only reader who doesn't have recent experience with CFG.\n\nWe thank the reviewer for the suggested improvement. In the revision, we will include a formal definition of CFG and an example of how a string can be derived for the CFG in Fig 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XUsuKWgfxB", "reviewer": "Reviewer_gp9U", "summary": "This paper focuses on the constrained decoding scenario where LLMs are expected to produce high-quality and grammatically correct outputs. It presents the adaptive sampling with approximate expected futures (ASAp) method, which is designed to enhance the quality of the output by adjusting the conditional probability to align with the model’s original output distribution while ensuring grammaticality. Central to ASAp is the development of effective approximations to the expected future grammaticality (EFG). More specifically, ASAp involves an extra sampling process, where the estimates of EFG are iteratively refined after each sampling and will eventually converge to exact EFG in the limit of infinite iterations. Experimental results show that the output probability distribution of ASAp is closer to the original one than that of GCD methods.", "questions": "Given previous samples with the prefix $w_{1:i}$, there exist abundant future tokens beyond just the next token. However, ASAp only uses the next token likelihoods to facilitate a better estimate of EFG. Why not use other future tokens?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Advantages of ASAp include facilitating more accurate grammatical predictions. ASAp approximates the desired distribution by considering the potential future grammaticality of sequences, whereas GCD typically samples greedily based on current probabilities without considering the future development of the sequence. This approach allows ASAp to more accurately predict and generate text sequences that comply with grammatical rules.", "weaknesses": "The algorithm heavily relies on prior samples to estimate grammatical probabilities, which can be computationally expensive and difficult to manage, especially in cases where the dataset is large or the environment is dynamically changing. Moreover, a fair comparison of decoding speed between ASAp and GCD methods is required, as ASAp needs this sampling process to produce high-quality outputs, but conducting sampling on LLMs is very time-consuming.\n\nOnly evaluating the quality of the output by KL divergence and expectations is limited because the decoding sampling algorithm, except for the greedy search, does not always obey the probability distribution. For example, when the decoding temperature is set to 1, models may not output tokens with the highest probability. To conduct a more intuitive evaluation, one can choose some constrained decoding tasks with explicit quality scores, such as constrained translation [1] with BLEU and Exact Match, and code generation, which can be evaluated by the passing rate.\n\nSince the experiments in this paper are based on prompt-motivated LLMs, a natural step is to fine-tune LLMs and see if they can produce grammatically correct output with high quality. On the other hand, the authors can also try ASAp based on fine-tuned LLMs, which may further boost the performance of ASAp.\n\nTo enhance the readability of the article, the following suggestions can be considered.\n1. It’s more intuitive to give specific input and output examples for SLIA and INV-BV tasks.\n2. The names GCD and GAD are too similar to easily differentiate, even after reading the paper.\n3. Other typos: In line 289, the word “both” is typed as “bot”.\n\n[1] Wang, S., Li, P., Tan, Z., Tu, Z., Sun, M., & Liu, Y. (2022). A Template-based Method for Constrained Neural Machine Translation. arXiv preprint arXiv:2205.11255.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The algorithm heavily relies on prior samples to estimate grammatical probabilities, which can be computationally expensive and difficult to manage… a fair comparison of decoding speed between ASAp and GCD methods is required, as…conducting sampling on LLMs is very time-consuming.\n\nIndeed, ASAp requires building a large data structure to keep track of the sampled prefixes, but decoding **each sample takes the same time with GCD and ASAp**.\n\n> Only evaluating the quality of the output by KL divergence and expectations is limited because the decoding sampling algorithm, except for the greedy search, does not always obey the probability distribution.. one can choose some constrained decoding tasks with explicit quality scores..\n\nWe agree that downstream, extrinsic evaluations are of interest: e.g., how much does ASAp improve task performance metrics on specific tasks? (See next paragraph, we do include some of this information in our paper.) However, these results are task dependent, as the reviewer mentions -- in some cases, increasing likelihood may correspond to higher task accuracy and in some cases not. \nSince we focus on formalizing the problem of distribution misalignment in GCD, the primary objective of our experiments has been to evaluate **intrinsic** measures, i.e., to assess how closely the probability distributions from GCD and ASAp approximate the exact GAD in Equation 2 in practice. \n\nWe do present the downstream quality of the output in Table 1 in Appendix A.5.2. However, since the model we used for evaluation was not sufficiently well-trained for our task, the experimental results in Appendix A.5 show that the output with the highest probability does not necessarily indicate good quality on the downstream task.\n\n> a natural step is to fine-tune LLMs and see if they can produce grammatically correct output with high quality. On the other hand, the authors can also try ASAp based on fine-tuned LLMs\n\nWe thank the reviewer’s suggestions regarding the evaluation. Previous work on GCD has shown that grammar-constrained LMs outperform fine-tuned models in structured NLP tasks (citation [5]). But we agree it is interesting to find out whether ASAp still provides benefits over GCD when applied to an LLM distribution that has **already been fine-tuned** to achieve higher grammaticality from the outset.\n\nDue to limited time and data (139 INV-BV and 2416 CP problems), we conducted a small experiment to test the reviewer’s hypothesis. In our finetuning step, we want to teach the LLM to assign higher probabilities to grammatical outputs for the specific task DSL. We randomly selected 2 INV-BV problems (find_inv_bvsge_bvneg_4bit and find_inv_bvsgt_bvor_4bit for INV-BV) and 4 CP problems (CP_re_ptb_215, CP_re_ptb_434, CP_re_ptb_1627 and CP_re_ptb_1643 for CP) from the test set, and used all other input-output pairs of prompt and output programs to construct datasets for finetuning the base LLM.  We obtained 2 finetuned LLMs, one for INV-BV and one for CP. \n\nWe ran GCD and ASAp on the finetuned models on the randomly left-out problems and checked the convergence rates of the KL-divergence. The results from finetuned models did not show significant differences in terms of convergence compared to the original model. As done in our evaluation, we computed the expectation for each benchmark obtained via GCD and ASAp after 2,000 iterations and compared it against the target expectation $Q^{P,G}$ (line 76) of GAD. The sum of least squares difference between expectations computed by GCD and the expectations of $Q^{P,G}$ are 0.677 (INV-BV4), 0.278 (CP) (respectively. 0.051 (INV-BV4), 0.201 (CP) for ASAp). I.e., the expectations computed by ASAp were closer to the expectations of exact GAD than those computed by GCD. We didn’t include SLIA as we didn’t have sufficient data for further finetuning.\n\nWe acknowledge there are alternative ways to fine-tune the model for learning grammatically; this goal is beyond the scope of the paper.\n\n**Details on experimental setup**: We adhere to the established LoRA finetuning pipeline and create task-specific datasets for instruction tuning. In line with our paper's methodology, we incorporate in-context examples in the instruction tuning dataset to enhance the models' performance in in-context learning. For each task, we independently finetune Mistral-7B, resulting in two versions of the model (for INV-BV4 and CP). We employ a standard train-validation-test split of 70-10-20%. Instruction tuning is conducted on the training set, and model selection is based on the lowest validation loss. Learning rate: 2e-4, warmup ratio: 0.03, max sequence length: 2048, LoRA alpha: 32, LoRA dropout: 0.05, and LoRA r: 64. The best checkpoints for the finetuned models for INV-BV and CP are at 328 and 536 steps, respectively.\n\n> It’s more intuitive to give specific input and output examples for SLIA and INV-BV tasks.\n\nDue to the space constraint in the main paper, we have included concrete examples and the grammar used to constrain decoding for LLMs in Appendices A.4.1 and A.4.2. We will provide a detailed description of these problems in the supplementary materials.\n\n> The names GCD and GAD are too similar to easily differentiate, even after reading the paper.\n\nWe will use more readable macros.\n\n> Given previous samples with the prefix w_{1:i}, there exist abundant future tokens beyond just the next token. However, ASAp only uses the next token likelihoods to facilitate a better estimate of EFG. Why not use other future tokens?\n\nThe reviewer is right that there could be faster-converging decoding approaches, which we are exploring as future work (e.g., as hinted by the reviewer, sampling more tokens at once to accelerate convergence is one of them).\n\nThe main focus of the paper is to formalize the likelihood misalignment problem in existing grammar-constrained decoding, and to provide an initial solution with provable asymptotic guarantees.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their feedback, which will greatly improve the paper. 

We have addressed each reviewer’s comment in their corresponding answer.

We summarize the edits we plan to do to improve the paper based on the feedback we received:
Reviewers cHBv and gp9U proposed ways to potentially modify the ASAp algorithm to speed up convergence. 
1. We will clarify in introduction that the main focus of the paper is to formalize the likelihood misalignment problem in existing grammar-constrained decoding, and to provide an initial solution to address this problem together with a proof of convergence. We will explain in Section 3 that the ASAp algorithm is not necessarily optimal in terms of sample-efficiency and clarify in the conclusion that there are opportunities for improvement.
2. We will include a formal definition of CFG and an example of how a string can be derived for the CFG in Fig 1.
3. We will add the missing related work provided by the reviewer cHBv: R Shin, et al., Constrained language models yield few-shot semantic parsers (2021)
4. We will address all other comments raised by the reviewers and include all the technical and writing clarifications from each rebuttal.
5. We have performed the experiment proposed by reviewer gp9U on fine-tuned models for our tasks and did not observe any significant differences in terms of convergence rates for both GCD and ASAp compared to the original model. If the reviewers find it beneficial, we can add a paragraph about this finding.

Meta-review: This paper focuses on the constrained decoding scenario where LLMs are expected to produce high-quality and grammatically correct outputs. The authors point out that prior methods on grammar-constrained decoding (GCD) distorts the language model's learned distribution over sequences. As mitigation strategy, they present the adaptive sampling with approximate expected futures (ASAp) approach, which is designed to enhance the quality of the output by adjusting the conditional probability to align with the model’s original output distribution while ensuring grammaticality. The evaluation is performed on code generation and structured NLP tasks showing a better likelihood for LLM’s outputs being grammar-constrained.

The paper is well written and the method is well-formalized and clear. The paper provides empirical validation that the method works and that it improves the benchmark scores. The main focus of the paper is to formalize the likelihood misalignment problem in existing grammar-constrained decoding which is an important finding. The notion of expected future grammatically will be impactful in the area of sequence decoding.

Unfortunately, ASAp is computationally expensive, requires building a large data structure to keep track of the sampled prefixes and many iterations. Even though this may limit the adaptation of ASAp, the main contribution of the paper is the finding that conventional methods on grammar-constrained decoding distorts the language model's learned distribution.
Decision: Accept (poster)