On the Query Complexity of Verifier-Assisted Language Generation
Authors: Edoardo Botta
Yuchen Li
Aashay Mehta
Jordan T. Ash
Cyril Zhang
Andrej Risteski
Venue: ICML 2025 poster (2025)
Keywords: verifier-assisted language generation
query complexity
inference-time scaling
best-of-N sampling
constrained generation
theory
Primary area: deep_learning->theory

Abstract: Recently, a plethora of works have proposed
inference-time algorithms (e.g. best-of-n), which
incorporate verifiers to assist the generation process. Their quality-efficiency trade-offs have been
empirically benchmarked on a variety of constrained generation tasks, but the algorithmic design landscape is still largely poorly understood.
In this paper, we develop a mathematical framework for reasoning about constrained generation
using a pre-trained language model generator oracle and a process verifier—which can decide
whether a prefix can be extended to a string which
satisfies the constraints of choice. We show that
even in very simple settings, access to a verifier
can render an intractable problem (information-theoretically or computationally) to a tractable
one. In fact, we show even simple algorithms,
like tokenwise rejection sampling, can enjoy significant benefits from access to a verifier. Empirically, we show that a natural modification of
tokenwise rejection sampling, in which the sampler is allowed to "backtrack" (i.e., erase the final
few generated tokens) has robust and substantive
benefits over natural baselines (e.g. (blockwise)
rejection sampling, nucleus sampling)—both in
terms of computational efficiency, accuracy and
diversity.

On the Query Complexity of Verifier-Assisted Language Generation
Edoardo Botta Yuchen Li Aashay Mehta
Jordan T. Ash
Cyril Zhang? Andrej Risteski
Abstract
plest form, called best-of-N, the language model generates N candidate responses, which are then scored by the verifier, and the highest-scored candidate response is chosen as the output of the inference process (Cobbe et al., 2021; Nakano et al., 2022). If the verifier can score partial generations (sometimes called process reward), the space for inference- time algorithms gets much richer: e.g., the final answer can be generated incrementally, using the verifier to guide the process (e.g., by incremental (blockwise) best-of-N, or more complicated strategies like Monte-Carlo-Tree- (Browne et al.. 2012; Hao et al., 2023)), Importantly, though a flurry of recent papers consider "scaling laws" of natu- ral strategies, the algorithm design space of verifier-aided inference-tine algorithms still opaque. particular, the value of a verifier-and and the relationship it needs to have to the generator is not well understood.
Recently, a plethora of works have proposed inference-time algorithms (e.g. best-of-n), which incorporate verifiers to assist the generation pro- cess. Their quality-efficieney trade-offs have been empirically benchmarked on variety of con- strained generation tasks, but the algorithmic de- sign landscape is still largely poorly understood. In this paper, we develop a mathematical frame- work for reasoning about constrained generation using pre-trained language model generator or- acle and a process whicch can decide whether prefix can be extended to string which satisfies the constraints of choice. We show that even in very simple settings, access to verifier can render an intractable problem (information- theoretically or computationally) to a tractable one. In fact, we show even simple algorithms, like tokenwise rejection sampling, can enjoy sig- nificant benefits from access pirically, we show that a natural modification of tokenwise rejection sampling, in which the sam- pler is allowed to "backtrack" (i.e., erase the final few generated tokens) has robust and substantive benefits over natural baselines (c.g. (blockwise) rejection sampling, nucleus sampling) both in terms of computational efficiency, accuracy and diversity."
In this paper, we show that good verifier can substantially (both in theory and in practice) decrease the computational cost of natural generation tasks, using a pre-trained language model as an oracle. In particular, we show that:
verifier. Em-
Even simple constrained generation tasks-where we trying to generate string in the support of lan- guage oracle, subject to some structural constraint (e.g. describable as simple formal language. like a regular language) can be computationally intractable in the absence of a verifier.
can
Conversely, access to a good process verifier, one that can decide whether a prefix can be completed constraint-satisfying string, can remove these in- tractabilities. Moreover, even simple algorithms like tokenwise rejection campling-wheriii we generate the string one token at time, using the process verifier as a means to accept or reject-can have substantive computational benefits over the baseline of rejection sampling.
1. Introduction
The fast-evolving area of inference-time algorithms con- cerns itself with leveraging the already-impressive capabil- ities of language models (Raffel al., 2020; Brown al., 2020; Touvron al., 2023), together with verifier which can score generations of the language model. In the sim-
Equua contribution 'Camegie Mellon University "Microsoft Research NYC. Correspondence to: Yuchen Andrej Risteski <aris-
Finally, on natural constrained generation tasks namely, generating test cases for Python functions with a pretrained CodeLlama (Roziere et al., 2023) ver- ifter can be truined, such that simple, but natural generalization of tokenwise rejection sampling which is allowed to "backtrack" the last few generated to- kens, achieves substantial benefits in computational efficiency, accuracy, and diversity of the generations.
Li cruchenl-@cs.cmu.edd tesk@andres @a@dddde..cuu.ddu...
Proceedings of the 4rnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Our codes released https: http//ggttttbbbe// com/ MuchenLi01/IM_0r Lttp://MMuerr__ooppeeeeee

---

On the Query Complexity of Verifier-Assisted Language Generation
2. Setup and notation
be completed string 8 o s' E A. This is natural formalization of a "process reward", as it assigns belief to a partial generation. In the theoretical results (Section 3 and 4), we'll assume access to such an idealized verifier. In the empirical results (Section 5), such a verifier will be trained and will output a value between 0 and I, which can be naturally interpreted as a probability that the prefix s is completable string s s A.
Throughout, we let be a nonempty finite set, denoting the vocabulary. We denote as E' the set of strings of length and by 2 = the set of all finite strings on 2. Given string Σ" we denote as 8; its i-th element and as Siy the substring of 8 starting at its i-element and ending at its j-element, included. We use |s| to denote the length of string s and to denote the empty string. Finally, we let r oy denote the concatenation of string æ followed by string y.
Definition 3 (Process verifier). Given a constraint set A, verifier is a function V E + {0, such that Vs E E", V($) = if and only 3s' E X such that 8 o 8 E A.
Definition 1 (Autoregressive oracle). An autoregressive oracle O takes input a string E )¹ and returns sample from a next-token distribution ((s) E + R+
Designing algorithms given access to oracles which perform certain tasks, is classical tool in computer science (this is the basis of Turing reductions in computational complexity), as well as optimization (e.g., zero-order optimization as- sumes value oracle for a function, first-order optimization a gradient oracle, etc.) In the context of generative model- ing, analyses based on oracle complexity have been carried out the settings of diffusion models, where sampling algorithms rely on score oracles (Chen et al., 2022).
We will denote the corresponding joint distribution over strings & E E- as po : =-' + Rt. Correspondingly, Vs E E" let po( 8) denote the distribution over completions of predicted by O.
Definition 2 (Constrained generation). Constrained gener- ation with respect to an oracle O, a constraint set A, and vo- cabulary Σ is the task of producing an element s E A S E- such that ps) > O. If no such 8 exists, the algorithm needs to output FAIL.
We will consider several natural algorithms that use au- toregressive oracle and a (process) verifier:
When not clear from context, we will specify instances of this task by the triple (E, O). Under suitable choices of the vocabulary Σ and the target domain A, one recovers several language modeling tasks of theoretical and practical relevance as special cases of constrained generation. Specif- ically, our experiments consider the tasks of generating (i) valid strings under the Dyck grammar (Section 5.1) and (ii) valid test cases for a given Python functions (Section 5.2), where the oracles return samples from an appropriately pretrained language model. We recover these tasks from Definition 2 by setting:
Definition 4 (Rejection sampling). Rejection sampling works by repeatedly generating a string s according to po. then running a verifier V on the complete string- and accepting when the verifier outputs V(s)= =
Note, this algorithm only needs a verifier that decides the membership in A, rather than a process verifier. On the other hand, because the entire string needs to be generated first before being verified-the number of generations until the verifier accepts is likely very large.
Definition 5 (Tokenwise rejection sampling). Tokenwise rejection sampling works by generating a string one token at a time. To generate the next token t, given a prefix s, we sample ~ (s), and run the process verifier on V(s o t). We repeat this, until V(s o t) = 1, then proceed to the next token.
(i) Σ as the set of open and close parentheses, and A as the set of valid sequences of given length.
(ii) E as a set of characters from the Unicode standard (possibly after tokenization) and A as the set of strings that are valid test cases for an input function in the Python programming language.
This algorithm requires process verifier. However, since a partial string is accepted only if the process verifier accepts, the number of generations needed is likely to be smaller. In fact, we provide a very simple example in Section 4.
Note that this task is easier than the task of sampling accord- ing to the restricted distribution p(s) x 1(s E (s)) which asks that the relative weights of the strings & E A that are generated match the probabilities assigned by po. However, in many settings-e.a generating a proof of a mathematical problem, or code that performs some intended functionality- we merely care about producing one good sample.
Finally, we consider a "backtracking" strategy, in which the model is allowed to erase some of its generations. The rea- sons to consider such strategy is to allow the model to get "unstuck"; if the process verifier decides the current prefix cannot be completed to a valid string in A, it is possible that erasing the last few tokens will make it easier for the model to correct its mistake, compared to erasing just the last token. More formally, the framework of our algorithm
We will be considering "process verifiers" that take as input a prefix 8, and output whether or not such a prefix can
2

---

On the Query Complexity of Verifier-Assisted Language Generation
is given by Algorithm below.
seeks an assignment of the variables (a:) with at {0, vi E [D] such that c= Σ 0,X;
Algorithm 1 Tokenwise rejection sampling with backtrack-
ing
The problem is (weakly) NP-hard, even for some very spe- cial choices of c, X₁.
1: Input: Prompt z, generator O, verifier V, length D E
N_, backtrack quota Q E N, backtrack stride B E N+
2: 8 f+
3. Constrained generation is hard without a verifier
3: while |s] < D and 8|a| # <eos> do
4: Sample ~ (xxos)
5: s 2+ s
First, we show that the constrained generation task (Def- inition 2), without access to process verifier be intractable-even if the constraint set A is extremely simple (e.g. the parity of a binary string).
6: if Q > and V(x s) then
7:
81:|s|-B
8:
Q g Q 1
9:
for in 1.... B do
10:
Choose & E arg max O(r o
The source of intractability can be informatiio-thheoreiic namely, if the oracle does not have a succinct description, the algorithm may need to query prohibitively many times to identify what oracle it's interacting with. We view this as plausible obstruction in practice well: language mod- els frequently behave unpredictably "in-the-tails", which becomes increasingly more likely when generating long strings. Thus, to inspect the behavior of the model on long strings, many queries are needed.
11:
84800 808
12:
end for
13:
end if
14:
end while
When arguing about lower bounds, a natural lower bound on the complexity of an algorithm is the number of oracle calls needed', particularly so when this dominates the cost of the algorithm, as is frequently the case for language models:
The source of the intractability can also be computational: namely, even if the oracle is very simple (e.g., a uniform distribution), generating member of A can be NP-hard, even if checking membership in A can be done efficiently. Perhaps this should not come as a surprise: after all, easy verification of membership, but hard generation, is the hall- mark of NP-hard problems.
Definition 6 (Oracle complexity). Given (possibly ran- domized) algorithm A that solves the constrained gener- ation instance (E, O), the oracle complexity of A is defined as the expected number of calls to the oracle made by A to solve (E, A, O), namely:
C(A) calll O made by running A),
Proceeding to the first result, we show the following:
where the expectation is taken over the randomness of the oracle O and the randomness of the algorithm A.
Theorem 1.
There exists a constrained generation task (E, A, O) for which Σ = {0. 1), A C E.,, and O is an (un- known) member of a set 2- possible oracles, such that any (possibly randomized) algorithm A has an (expected) oracle complexity of at least 2D-1
Finally, we recall the classical knapsack problem, which will be used in a reduction to prove computational intractability results for the constrained generation task:
Definition 7 (Knapsack problem). Given a set of weights {X, E - E [D] and c E Zzo, the knapsack problem
Intuitively, the lower bound is shown by engineering a sce- nario such that the behavior of the oracle on long strings unknown to the algorithm but success of the generation task relies on "guessing" this behavior correctly.
"The algorithm is bit more involved, so we will describe it in pseudocode rather than text. Besides the notations in Section 2, Algorithm uses the following additional common conventions: <eos> denotes the
token; 8/4] # <eos> is understood as True when a = e; for any starting index i and ending index j. if >>> j. then 8tj erased positions using argmax: our results in Section 5.1.1 suggests that outtoo-ddistribation prefex a cause of generator mistakes. a remedy, redoing the erased positions using argmax is intended probability of the currently
In line 10, why redoing the
Proof. Consider the constrained generation task (E, A, Os), such that Σ = {0, 1}. A = {s Σ Σh 8; mod 2 = 0} for some fixed D E Z Moreover, the oracle O₂ is indexed by an (unknown to the algorithm) é E Dー1 and it specifies the autoregressive distribution defined s.t. Vs E [s < D - 1, we have po, (1|s) = Po, (0]s) =
to increase the generator-predie sampled prefix. We include an ablation study in Appendix B.3 verifying that this improves the accuracy.
"In our case, the number of calls is randomized quantity, so natural quantity to consider is the expected number of oracle calls. It is of course reasonable to consider finer-grained notions like tail bounds on the number of calls.
1/2; while for E Σ* E*,[s) = 1, it satisfies:
3

---

On the Query Complexity of Verifier-Assisted Language Generation
vs 8 ED-1, SD E [0, we have:
4. Constrained generation with process verifier gets easier
1, if - 8, + SD)
mod 2 = 1
(SD (8)
While pessimistic, the message of Section 3 agrees with re- cent developments in inference- time scaling: namely, many natural tasks of interest seem to require a verifier to be solved.
0, otherwise
(1)
For s = 3,8D E {0.1) 1}, we have:
First, we show that the simplest "natural" algorithm with a process verifier. tokenwise rejection sampling (Definition 5), can be much more efficient (exponentially so) in terms of or- acle complexity compared to the trivial baseline of rejection sampling (Definition 4).
1, if (E 8, + sD)
mod 2 =0 0
Po, 8)
0, otherwise
Proposition 1. Consider the constrained generation task (I, A, O), s.t. Σ = (0, A = {00) and O is uniform over Dd Then:
Suppose first that the algorithm is deterministic, and we choose the prefix & uniformly at random. Let us denote by I1, 22, ....... Zgg E ,n the queries to O generated by the algorithm. The claim is that expected number of queries q needed ensure at least one F2, [q] is in A is 2D-1 Indeed, the F2 s.t. |x,| D - 1 reveal no information about 3: the output of O is uniform Bernoulli random variable regardless of the value of &. On the other hand, if at some point the algorithm has queried a set S of x; of length D D- the probability over is uniform over y \. S. Hence, the expected number of queries (expectation being over the choice of 3) deterministic algorithm needs lower bounded by 2n-1
The expected oracle complexity of rejection sampling (Definition 4) is 2DD.
2. The expected oracle complexity of tokenwise rejection sampling (Definition 5) with a perfect process verifier is 2D.
Proof. Both claims are straightforward. (1) follows as gen- erating one guess for the string 8 takes D oracle calls. More- over, the probability of the full string matching the only string in A (i.e., 0D) 1/2". As the number of calls to generate 0 is geometric random variable, the expected number of full string generations is 2D.
By Yao's ss minimax lemma (Yao, 1977), this means that for any (even possibly randomized) algorithm A, there exists & on which the algorithm makes at least 2n-1 queries in expectation.
For (2), since O is uniform, at each token, the probability of drawing 0 is 1/2. Hence, the expected number of calls per coordinate needed is 2 - making the total number of expected calls for the entire string 2D.
Proceeding to the computational lower bound, the theorem we show is as follows:
This proposition underscores the power of a process verifier even in extremely simple settings, and even when used in conjunction with a very simple algorithm.
Theorem There exists a constrained generation task (E, A, O) for which Σ = 10.1), membership in A C Id can be checked in time polynomial in D, and O is such that Vs& E (0. 1) .po(s) > 0, the generation task is NP-hard.
In fact, one can easily see that with a perfect process verifier, one can easily solve the constrained generation task with [ D calls: each position, one queries the process verifier for each possible continuation of the string, and accepts only if the process verifier accepts. Of course, in practice, the verifier is not perfect, and its accuracy likely depends on how
Proof. We construct a reduction from the knapsack prob- lem (Definition 7). Let the set (X1,..., Xp) and the in- teger e specify an arbitrary instance of the knapsack prob- lem. Consider the constrained generation task specified by Σ == 10, A- : {s DD Vi E [D], s; E (0,1); Σh Σn 8,,, = c]. Membership in this A can be clearly verified in polynomial time. Suppose we have poly-time algorithm that generates solution to (E, A, O). Since Vs E " (s)) > 0, å provides a solution to the knapsack problem, as we needed.
the prefix it's queried on is (See Section 5. 5.5 and Appendix B.2.6)
We finally remark that a process verifier, as we defined is clearly useful to solve the generation task. If we instead wanted to sample from the restricted distribution p(s) x
1(s E A))o(s), it's not clear how useful the process verifier is. For instance, if we use the simple tokenwise rejection sampling (Definition 5), it's easy to see that the distribution we produce samples from is not the restricted distribution:
We discuss additional intuitions for understanding our proof Remark 2 Appendix A.3.

---

On the Query Complexity of Verifier-Assisted Language Generation
Proposition 2. Consider the constrained generation task (E, A, s.t. Σ (0, 1), A = {s E EP 3i E [P] = 0f and O is uniform over DD. Then, tokenwise rejection sampling does not produce samples from p(s) x 1(s E (s))
in both natural and programming language syntax-and has been subject of interest in numerous theoretical studies on Transformers (Yao et al., 2021; Liu et al., 2022; 2023b; Wen et al., 2023). More formally:
Definition 8 (Dyck distribution). Dyckp denotes the Dyck language" of length D defined over the vocabulary ) = { () whose length-N prefix set is denoted as Proof. By Definition 5, until the last token is being gener- ated, the process verifier will always accept (as there exists string with at least one O coordinate in the coordinates that haven't I yet been sampled). Now, for the prefix 1 10-1, the only completion that is in A is 1 o 0. This means that 1011 o 0 is assigned probability mass z under the tokenwise rejection sampling schema. All other strings in D are assigned a probability z0. On the other hand, p(s) x 1(s E A)po(s) assigns uniform mass on all strings in A proving the claim of the proposition.
Dycky: VN E [D]. For a valid prefix WI.N E Dyckx the depth of WiNN is
d(wIN) # Oppn Brackets in WINN
# Close Brackets in Wi-N-
The distribution Dayek over Dycky, (parameterized by P.q E (0,1)) is defined such that VWI.N DyckN,
P(wi:)) x pl (.d(m))) (1 p)) (d((ma))1))
(3)
5. Backtracking: a surprisingly effective rejection sampling strategy
(pq) (in ((1 - p)g) [(l:::
(4)
The flexibility of the tokenwise rejection sampling with backtracking (Algorithm 1) makes it very natural strategy to use in conjunction with trained verifiers. We perform a thorough empirical investigation into the applicability of Tokenwise rejection sampling with backtracking in con- strained language generation, and benchmark it against com- mon baselines, including rejection sampling (Definition 4), nucleus sampling (Holtzman et al., 2020), temperature scal- ing, and "block best-of-N" (Appendix B.2.3) sampling, on both synthetic data (Section 5.1) and more realistic data (Section 5.2). We observe that across various settings, To- kenwise rejection sampling with backtracking reduces query complexity, improves accuracy, and does not hurt diversity.
(1 - (i-gglttlu.UUW))))eeemaa
Remark 1. Equation (3) defines an intuitive autoregressive generative process for Dyckp: :: if the current depth is 0, then sample the next token from [ and ( wwith probability p and
- p respectively; else if the current depth is D i + 1, implying that all the remaining positions have to be closing brackets, then deterministically close the last unmatched open bracket 5; else, sample the next token from open or close brackets with probability q and 1 q respectively. In other words, p controls the proportion of square vs. round brackets, while q controls the tendency to predict an open bracket when possible (a large q may result in a large depth at some position).
5.1. Language models trained on synthetic data
In our experiments, we pretrain autoregressive Transformer (Vaswani et al., 2017) Language models (6 layers, 8 heads per layer, hidden dimension 512) from scratch on data sam- pled from Dryck with D = -32, p 0.2, 4 = 0.5. We use batch size 32, weight decay 0.1, learning rate 3e-4 with 100 warmup steps, and follow Block et al. (2024) to use expo- nential moving average to stabilize training. We reached 100% training and (in-distribution) validation accuracy.
1. DYCK GRAMMAR AS A SANDBOX
Real-world LLM pretraining data (Li et al., 2024a) typically involves many diverse structures, so when an LLM algo- rithm outperforms baselines benchmark, it is generally challenging to precisely identify which component of the algorithm improved the handling of which structures of the data.
To search for stronger signals in benchmarking the accuracy of the trained model, we will prompt it using the following type of out-of- not--o-distribution prompts. Note that since p < 0.5, the training data contains less square brackets than round brackets, so long prefixes with many square brackets will be out-of-distributiio prompts for the trained model. We gen- erated set of such -itto---iitrbuttion prompts Dyckood
To have a quantitative control over the structure in the pre- training data distribution, and to derive fine-grained observa- tions about the effects of Tokenwise rejection sampling with backtracking, we synthetically generate the pretraining data based on the Dyck grammar (Schätzenbergeer, 1963), a clas- sic formal language (context-free grammar) consisting of balanced parentheses of multiple types (for example, "[O]" "" is valid but "()]" is not). Dyck serves as a useful sandbox, as it typifies features such as long-range dependencies and a hierarchical, tree- like structure characteristics often found
"We follow a simplified version of Wen et al. (2023) in defining probability distribution over strings in Dyck language. At any position, there is at most one valid closing bracket.
5

---

On the Query Complexity of Verifier-Assisted Language Generation
from Dycky with p 0.8 where the prefix length N is uni- formly randomly sampled from 25 v N 31. We let the trained language model complete these prompts and check whether the completed string is in Dyckp- Quantitatively: Definition 9 (Prompt completion accuracy). Given an au- toregressive oracle O (Definition 1) and a set of prefix prompts X, the accuracy of O in completing X is:
inducing prefixes" Xerrorinduccing to denote [-1: x Xenor.. Table 1 shows that prefixes in X emor inducing. if we backtrack only once for a small backtrack stride B, and continue the autoregressive sampling process, the error rate can be significantly reduced.
generation configuration
accuracy
baseline: nucleus sampling top-p= 0.9
0.331
Ac
1
Σ
1 DyccD
haseline: greedy argmax sampling
0.334
X
B L. then nucleus sampling top-p 0.9
0.366
B 2, then nucleus sampling top p
0.9
0.438
We construct the autoregressive oracle Onnclens which pre- dicts the next-token distribution based on our trained model
B = 4, then nucleus sampling top-p= 0.9
0.591
B = 8, then nucleus sampling top-p 0.9
0.790
with nucleus sampling (Holtzman et al., 2020) top-p set to 0.9. We observed that Acc Deemmntaeus, DyckooD) = 94.23%.
Table 1. At error-inducing prefixes, a larger backtrack stride B
We will show that Verifier hacktracking based on Algorithm can significantly reduce the remaining error rate.
significantly improves completion accuracy (Definition 9).
5.1.4. VERIFIER EFFECTIVELY REDUCES ERRORS
5.1.2. TRAINING THE VERIFIER
In Section 5.1.3, the sampling process forced a backtracking at error-inducing prefixes X emor inducing- Can the error reduc- tion effect be retained by trained lightweight single-layer verifier V in Section 5.1.2? Table 2 shows that Tokenwise rejection sampling with backtracking (Algorithm 1) using the trained verifier is remarkably effective. Moreover, in Appendix B. 1.2 we verify that the predicted backtracks were necessary.
We collect a set of 441 prompts in Dyckoon in which the trained model (denoted as LM) made mistakes when completing them. We implement a rule-based error parser according to the grammars of Dyck, which identifies the first position of error in each model completion. Applying this parser to the model mistakes, we obtain of model- generated strings Xemor C E' which contain errors. By contrast, we sample another set of 441 strings Xoorect Dyckood such that Xenor and Xcorret have the same length distribution. We train a lightweight neural network verifier to distinguish Xenor from Xeoneet-
Q
B
accuracy
2
0.421
0.500
6
0.604
Concretely, to maximally exploit the representations learned by LM, we train a l-linear-layer verifier V whose features the lastyer-lss--osiitiien
2
2
0.457
0.634
representations by LM of strings in Xemor U X uuoreet and labels are O for strings in Xemor and I for strings in Xeomeet Consequently, the train- able parameters of V are a single matrix of dimensionality 512 by 2. Among the 882 strings in Xenor U X Cooreet we use 792 samples for training, and 90 samples for validation. Despite being slightly over-parameterized, this minimal ver- ifier V achieved on average 93% (with standard error 3.9%) validation accuracy across 10 repetitions. Figure 1 in Ap- pendix 1. illustrates the intuition of why lightweight verifier may be surprisingly effective with a small number of labeled samples. We next verify that forcing a back- tracking at prefixes where the model made mistakes can effectively improve the completion accuracy (Section 5.1.)), and that the trained verifier in this section can mostly catch those mistakes and thus mostly retaining the accuracy gain (Section 5.1.4)
6
0.762
4
0.518
0.762
6
0.921
baseline: nucleus sampling top p 0.9
0.331
baseline: greedy argmax sampling
0.334
sampling
Table 2. When the prompts are error-inducing prefixes, single- layer trained verifier significantly improves completion accuracy using Tokenwise rejection sampling with backtracking (Algo- rithm 1). A larger backtrack quota Q and larger backtrack stride B are both helpful.
5.1.5. TOKENWISE REJECTION SAMPLING WITH BACKTRACKING REDUCES COMPLETION ERRORS ON UNSEEN OOD PREFIXES
Table 2 in Section 5.1.4 reported a significant improvement of accuracy by Tokenwise rejection sampling with back- tracking (Algorithm 1) when the prompts are X Xemor-inducing- for which the language model LM made mistakes during
5.1.3. BACKTRACKING EFFECTIVELY REDUCES ERRORS
The trained language model LM made a mistake at the last position of each string & E Xemor- We therefore use "error-
6

---

On the Query Complexity of Verifier-Assisted Language Generation
completion. Is the verifier V overfitted to these type of emrr- inducing prompts? Can the accuracy improvement general- ize to (average-case) out-of-distrrbution (OOD) prefixes, i.e. independently sampled strings of the same distribution as Dyckood (Section 5.1.1)?
5.2.1. TASK SETUP
A natural practical constrained generation task that requires both accuracy and diversity is generating test cases for target function specified by the prompt. To have an un- ambiguous notion of groundtruth regarding accuracy and diversity, we control the target function to be a simple imple- mentation of the append function for Python lists. Under this setting, we wrote an evaluator script which analyzes model generated completions, measuring the accuracy by checking whether a test case correctly tests list append, and measuring the diversity by checking how many distinct test cases are generated." 7
We independently sampled 10000 such out-of-distribution prompts DyckooD" and benchmark the accuracy of To- kenwise rejection sampling with backtracking (Algorithm I) against the baselines of nucleus sampling top-p= 0.9 (Holtz- man et al., 2020) and standard autoregressive sampling (cquivalent to top 1.0). Table 3 shows that Token- wise rejection sampling with backtracking (Algorithm 1) significantly reduces completion errors. Crucially, the im- provement does not diminish on top of the commonly used baseline of truncating the tail probabilities during sequence sampling. This verifies the desirable property that Token- wise rejection sampling with backtracking can be applied in combination with such baselines to further improve ac- curacy. We also verify that the accuracy improvement does not hurt diversity (Appendix B.1.
We write a program to systematically generate task prompts, randomizing over function names and demonstration ex- amples. Each prompt includes demonstration example specifying the intended output format, followed by a target function (implementing append), and finally requests 8 test cases be generated. Two examples of the prompt are provided in Table 7, and correspondingly, two examples of model completions of these prompts are provided in Table 8 in Appendix B.2.1.
Finally, provided with the verifier, why does the model still make mistakes? We include additional error analysis in Appendix B.1.3.
The test prompts include 10 different target function names that are unseen during training. Each target function name is independently tested 10 times. Since each prompt requests test cases, the total number of test cases requested for each run of a decoding algorithm is 8 10 10 800. We will measure the following metrics:
Evaluation metries
nucleus sampling top p
Q
B
#errors + std err
0.9
0
0
240.0 + 5.177
4
4
179.4 = 1.020
1.0
0 0
461.8 + 8.304
4 4 200.0 = 3.225
1. Ndistinet concer: the number of distinct correct test cases generated. This metric naturally incorporates both ac- curacy and diversity.
Table 3. Tokenwise rejection sampling with backtracking (Algo-
rithm 1) reduces completion errors on unseen out-of -fiiiiiibittininnn (OOD) prefixes. Crucially, the improvement does not diminish top of commonly used baselines, including nucleus sampling top-p 0.9. For each setting of top-p. we compare Tokenwise rejection sampling with backtracking (Algorithm 1) (using backtrack quota Q 1 and backtrack stride B = 1) with the baseline (using backtrack quota Q = 0 and backtrack stride B = 0). We report the number of completion errors that occur when completing an unseen set of 10000 independently sampled notto--distribution prompts Dyckood unseen The experiment was repeated times, and we report the standard errors.
2. ACCdistinet == N ddistiet correct/ 800.
3. C: the query complexity (analogous to Definition 6). We measure the total number of queries made to the generator LM when it completes the prompts. Each completion allows at most 384 tokens to be generated, so the max C is 384 x 10 x 10 38400 unless "block best-of-n" (Appendix B.2.3) used.
5.2. Generating test cases with pretrained CodeLlama
We use a pretrained CodeLlama (Roziere et al., 2023) as the generator language model LM, which we freeze during our experiments. We discuss common baselines in Ap- pendix B.2.2. We follow almost the same approach as Sec- tion 5.1.2 to train our verifier on this coding task. We next present technical details and ablation experiments regarding design choices of verifier training in Appendix B.2.3.
Motivated by our findings in Section 5.1, we apply essen- tially the same recipe of Tokenwise rejection sampling with backtracking (Algorithm 1) to real-data use case, and show that Algorithm clearly improves the quality vs. query com- plexity trade-off on top of commonly used basclines, such as nucleus sampling (Holtzman et al., 2020), temperature scaling, oe rejection sampling, and block best-of-n with process reward model.
Twoo test cases are different if and only if they test different lists or different appended items.
7

---

On the Query Complexity of Verifier-Assisted Language Generation
Q
top_p
T
block BoN
AcCaistinet + std err
parisons are visualized in Figure 3 and Figure 4 (in Ap- pendix B.2.5). Numerical values of C are reported in Ta- ble 13 in Appendix B.2.4.
4
0.95
1.0
0.714 + 0.011
0.95
1.0
2
0.684 + 0.038
0.95
1.0
0.660 + 0.042
0
0.95
1.0
4
0,623 + 0.036
0.95
1.0
8
0.559 + 0.038
6. Related work
1.0
1.0
0.639 +: 0.061
Inference-time scaling for language models Practical language generation tasks typically impose various task- specific constraints in addition to the general grammatical rules of language. One effective way to improve the chance of satisfying such constraints is to increase the inference- time compute through search and/or rejection sampling, There has been a long history of prior works that employ inference-time scaling in the language generation context, dating as far back as beam search (Lowerre & Reddy, 1976; Hayes-Roth al., 1976; Ow & Morton, 1988; Jurafsky & Martin, 2000; Graves, 2012). Much more recently, as re- searchers develop the techniques for language models to follow instructions (see the survey by Zhang et al. (2023b) and references therein), more creative designs for inference- time scaling algorithms have become viable (Wang et al., 2022; Yao et al., 2023; Zhang et al., 2023a; Zhou et al., 2023; Choi et al., 2023; Liu et al., 2024; Xie et al., 2024; Snell et al., 2024; Zhao al., 2024), and see Wu et al. (2024) for recent survey cost-performance tradeoff's of these approaches. Compared to these approaches in the litera- ture, our Tokenwise rejection sampling with backtracking (Algorithm 1) shares some features with lookahead search (Snell et al., 2024) (specifically, the rejection decision at the current position is based on the verifier decision at some future position). However, two main differences are: (1) To- kenwise rejection sampling with backtracking (Algorithm I) does not use a beam (i.e. does not need to generate mul- tiple candidates, thus reducing query complexity), and (2) Algorithm uses a different sampling approach (namely argmax) for the backtracked positions (we verify in Ap- pendix B.3 that in some settings this significantly improves the accuracy). It is natural future research direction to design inference algorithms that combine the advantages of the two.
10
1.0
1.0
0.622 = 0.046
0
1.0
1.0
0.504 + 0.025
4
1.0
1.2
0,440 1 0.026
1.0
1.2
0.269 + 0.025
0.0
1.0
0.013 + 0.000
Table 4. Tokenwise rejection sampling with backtracking (Algo-
rithm 1) improves accuracy and outperforms nucleus sampling top-p, temperature scaling T, and block best-of-n (BoN) (Ap- pendix B.2.3). In this table, we divide the rows into groups, sep- arated by double horizontal lines, such that each group uses the same top-p and lemperature. The backtrack quota Q = 0 means a haseline algorithm that does not use the verifier. Q > O means Tokenwise rejection sampling with backtracking with the corre- sponding Q and B. block BoN specifies the number of candidates generated for cach block; empty block BoN means not using block best-of-n. In all groups, Tokenwise rejection sampling with back- tracking leads higher AcCaisinct than all other methods. The last group corresponds to argmax greedy decoding, which has low AcCaisiner due to low diversity. The experiment was repeated 5 times, and we report the standard errors. The complete set of experiments are reported in larger Table 13 in Appendix B.2.4.
5.2.2. TOKENWISE REJECTION SAMPLING WITH BACKTRACKING IMPROVES ACCURACY
In this section, we show that Tokenwise rejection sampling with backtracking (Algorithm 1) achieves higher AcCaistinet than all the baselines described in Appendix B.2.2. Similar to our observations based on the synthetic Dyck grammar data (Section 5.1.5), the improvement does not diminish on top of commonly used baselines. This verifies the desir- able property that Tokenwise rejection sampling with back- tracking (Algorithm 1) can be applied in combination with commonly used baselines to further improve accuracy. The primary comparisons are reported in Table 4, and additional results are in Table 13 in Appendix B.2.4. Moreover, in Ap- pendix B.2.6, we show that analogous to our observations on the synthetic Dyck grammar (Section 5.1.5), Tokenwise rejection sampling with backtracking (Algorithm 1) gener- alizes better to out-of-distribution prompts than baselines.
Incorporating process reward model to assist language generation Among the vast design space for inference- time scaling, process reward modeling has been proven to be an important component common to many LLM systems (Polu & Sutskever, 2020; Uesato et al., 2022: Ma et al., 2023: Lightman et al., 2023; Wang et al., 2024). The pro- cess verifier which we study (Definition 3) is a special case of such process reward model if we restrict the output to be binary. However, there are still challenging open problems around process reward modeling, such as how to properly define the "blocks" (Guo et al., 2025) (see also our def- initions in the "Block verifier" part of Appendix B.2.3). Towards bringing more clarity to these open questions, our
5.2.3. TOKENWISE REJECTION SAMPLING WITH BACKTRACKING IS QUERY EFFICIENT
In this section, we show that Tokenwise rejection sampling with backtracking (Algorithm 1) achieves a better trade- off between Accaistinet and query efficiency C than all the baselines described in Appendix B.2.2. The primary com-
8

---

On the Query Complexity of Verifier-Assisted Language Generation
work develops theoretical framework for reasoning about the query complexity of process verifiers. Moreover, our experiments suggest the potentials of lightweight process verifier in improving the query complexity, accuracy, and diversity of constrained generation. In particular, our theory and experiments suggest (1) the "blocks" do not necessarily have to be carefully designed - setting each token as a block might potentially suffice, least in some more struc- tured domains such as codes; (2) backtracking (Algorithm I, Section 5) is robustly effective strategy that should be applied in combination with process verifiers. A possible extension of the type of verifier we study (Definition 3) is: instead of outputting binary acceptance/ / rejection decisions, the verifier could return a probability of accepting each prefix (Yang& & Klein, 2021). However, some tasks may re- quire that the output distribution should match some target distribution, and it may be challenging to ensure that the acceptance probability is well-calibrated in order to satisfy this requirement.
tributional calibration. Empirically, through fine-grained experiments on both synthetic and realistic data, we show that the Tokenwise rejection sampling algorithm, when com- bined with backtracking, is robustly effective recipe for reducing query complexity, improving accuracy, and main- taining diversity. For future works, we hope the theoretical framework and empirical observations can inspire system- atic characterization of the strengths and weaknesses of the diverse set of pieectio-sammllin-bbee -baeed inference-time al- gorithms. Concrete open problems at the intersection of theory and experiments include investigating the realistic and necessary conditions on the verifiers for the inference- time algorithm to achieve distributional calibration (e.g. it is unrealistic in some language generation setting to assume that verifier returns the calibrated acceptance probability in rejection sampling), and synergistically designing query- efficient verifier- assisted generation algorithms.
ACKNOWLEDGEMENT
We thank Bingbin Liu for insightful discussions.
Controlled synthetic data distribution as a sandbox for studying language models Our Dyck grammar distribu- tion most closely follows Wen et al. (2023) (though we switched to a sxxed-sequence-length setting, and used un- balanced bracket type probability, instead of length extrap- olation, to define the criteria for a prompt to be out-of- distribution). Dyck grammar was also used in other prior works (Hewitt et al., 2020; Ebrahimi et al., 2020; Yao et al., 2021; Liu et al., 2022; 2023b) to study language models. Dyck grammar can be seen as a special case of the task (specifically context-free grammar) considered in SynCode (Ugare et al., 2024). Other synthetic data distributions have been used to study various aspects of language models in prior works, including representational capability (Bhat- tamishra et al., 2020; Li & Risteski, 2021; Zhang et al., 2022; Zhao et al., 2023), statistical sample complexity (Edelman et al., 2022), optimization process (Lu et al., 2021; Jelassi et al., 2022; Li et al., 2023; Bietti et al., 2023), sampling (Li al., 2024b), and architectural limitations (Liu et al., 2023a), and see references cited therein.
AR and YL are supported in part by NSF awards IIS- 221 1907, CCF-2238523, IIS-2403275, an Amazon Re- search Award, a Google Research Scholar Award, an OpenAl Superalignment Fast Grant, and DoD Award N000142512124.
Part of this work was done when YL and AR were visit- ing the Simons Institute for the Theory of Computing. We thank the Simons Institute for hosting us. We also thank the Simons Foundation and Google for sponsoring compu- tational resources for us and other program visitors, and we thank Matus Telgarsky and NYU IT for managing these computational resources.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
7. Conclusion
References
We introduce a new theoretical framework for elucidating the design space of verifiers and correspondingly a simple inference algorithms.
Ackley, D. H., Hinton, G. E., and Sejnowski, J. A learning algorithm for boltzmann machines. Cognitive science, 9 (1):147-169, 1985.
family of perection-amplinn--aae In particular, our theory proves the computational benefits of incorporating a process verifier, measured by the query complexity of calling the generator. On the other hand, our theory also reveals the subtleties: straightforwardly applying a process verifier in a Tokenwise rejection sampling algo- rithm may unintentionally re- re-weigh the distribution among sequences that satisfy the constraints, which could be un- desirable for settings that require a strong notion of dis-
Bhattamishra, S., Ahuja, K., and Goyal, N. On the Abil- ity and Limitations of Transformers to Recognize For- mal Languages. In Proceedings of the 2020 Confer- ence on Empirical Methods in Natural Language Pro- cessing (EMNLP), pp. 7096-7116, Online, November 2020. Association for Computational Linguistics. doi: 1t..88553/1/2200 wtte200..mlpmmmme maanlp-main55.6..
URL https://

---

On the Query Complexity of Verifier-Assisted Language Generation
ac aclanthology www.ooog//o///..ooo emn commmmpmmma p-mmaimm maminn.............m... 6...
Ebrahimi, J., Gelda, D., and Zhang, W. How can self-attention networks recognize Dyck-n languages? In Findings of the Association for Computational Linguisties: EMNLP 2020, pp. 4301-4306, On- line, November 2020. Association for Computational Linguistics. doi:
Bietti, A., Cabannes, V., Bouchacourt, D., Jegou, H., and Bottou, L. Birth of a transformer: A memory viewpoint. Advances in Neural Information Processing Systems, 36, 2023.
384. URL https: /aclanthooooy org/20200 f Findings-emn11 384.
Block, A., Foster, D. J., Krishnamurthyy A.. Simchowitz, M., and Zhang, C. Butterfly effects of SGD noise: Error am- plification behavior cloning and autoregression. In The Twelfth International Conference on Learning Represen- tations, 2024. URL https: / /ttp//ppeeeeeeeereeee/e/e Forum?id-CgPsD4ee
Edelman, B. L., Goel, S., Kakade, S., and Zhang, C. In- ductive biases and variable creation in self-attention mechanisms. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Pro- ceedings of the 39th International Conference Ma- chine Learning, volume 162 of Proceedings of Machine Leurning Research, pp. 5793-5831. PMLR, 17-23 Jul 2022. URL / URLhttps: http::///occceeeeeeeeeee mlr press/ v162 eda.mm22mmm...... html.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan,
D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Weerbert-osss, A., Krueger, G. Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C.,, McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. URL https:/ neurips cc/ httprips.cccppppee/22//////////e https::/pprcceeaiiin 0777700fbfcc4499771188b8333 42 pdf.
Graves, A. Sequence transduction with recurrent neural networks. arXiv preprint arXiv: 2012...
Guo, D.,, Yang, D., Zhang. H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma. S., Wang, P., Bi, X., et al. Deepseek-rl: In- centivizing reasoning capability in llms via reinforcement learning, arXiv preprint arXiv:2501.12948, 2025.
Hao, S., Gu, Y., Ma, H., Hong. J. J., Wang, Z., Wang, D. Z and Hu, Z. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305. 14992 2023.
14992,
Browne, C., Powley, J. Whitchouse, D., Lucas, M.M.M. Cowling, P. I., Rohlfshagen, P., Tavener, S., Liebana, D. P., Samothrakis, S., and Colton, S. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4:1- 43, 2012. URL https: http://pap.....sssseeeeeeeeeeeee www.seitsaaiissoo........ org/Corpus Cpruss ID: 931 6331.
Hayes- Roth, P., Fox, M., Gill, G., Mostow, D., and Reddy, R. Speech understanding systems: Summary of results of the five-year research effort, 1976.
Hewitt, J., Hahn, M., Ganguli, S., Liang, P., and Manning, C. D. RNNs can generate bounded hi- erarchical languages with optimal memory. In Pro- ceedings of the 2020 Conference on Empirical Meth- ods in Natural Language Processing (EMNLP), pp. 1978-2010, Online, November 2020. Association for Computational Linguistics. doi: 10. 10.18653/v1/2020. emnlp-main. 156. URL https://www. aclweb. azg/anthologyy / 22200.00.... emnlp-main.
Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint ar arXiv:2209.1 1215, 2022.
Choi, S., Fang, T., Wang. Z., and Song, Y. Kets: knowledge- constrained tree search decoding with token-level hal- lucination detection. arXiv preprint arXiv:2310.0900 10.0904, 2023.
Holtzman, A., Buys, J., Du, L., Forbes, M., and Choi, Y. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL https://///. httpp::://ppezeee /ttp///ppeeeeeeeeeeeeeee wwwpreeiiwww.eeeeeeeeeeeeeeeeeee forum? i id=rygGOyrFvH:
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems, 2021. URL org/ abs
Jelassi, S., Sander, M. E., and Li, Y. Vision transformers provably learn spatial structure. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https: / openrevi ew net/ fwrmmmrrumm///m
14.68.
Dehghani, M., Amab, A., Beyer, L., Vaswani, A., and Tay, Y. The efficiency misnomer. arXiv preprint 2 10. /2894, 2021.
10

---

On the Query Complexity of Verifier-Assistedd Language Generation
Jurafsky, D. and Martin, J. H. Speech and language pro- cessing: An introduction natural language processing. computational linguistics, and speech recognition, 2000.
Liu, B., Ash, Goel, S., Krishnamurthy, A., and Zhang, C. Exposing attention glitches with flip-flop language modeling. Advances in Neural Information Processing Systems, 36, 2023a.
Karp, R. Reducibility among combinatorial problems. In
Complexity of Computer Computations, volume 40, pp. doi: 10.
Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Represen- tations, 2023b. URL https: openrevieweeeeeeeeeeeeeeee o net/ -
85-103, 01 1972. ISBN 978-3-540-68274-5.
Kellerer, H., Pferschy, U., and Pisinger, D. Knapsack Prob- lems. Springer, 01 2004. ISBN 278-3-540-40286-2. doi:
Liu, H., Xie, M., Li, Z., and Ma, T. Same pre-training loss, better downstream: Implicit bias matters for language models. arXiv preprint arXiv:2210. 14/99, 2022.
Kovaleva, O., Romanov, A., Rogers, A., and Rumshisky, A. Revealing the dark secrets of BERT. In Proceed- ings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th Interna- tional Joint Conference on Natural Language Processing (EMNLP-IJCNLP)) pp. 4365-4374, Hong Kong, China, November 2019. Association for Computational Lin- URL https:
Liu, J., Cohen, A., Pasunuru, R., Choi, Y., Hajishirzi, H., and Celikyilmaz, A. Don't throw away your value model! generating preferable text with value- guided monte- carlo tree search decoding. In First Conference on Lan- guage Modeling, 2024.
guisties. doi: 10. (0.188533/1/D119-11 //aclanthology.orggr www.hhhoooooooooogggooeee
Liu, N. Linguistic knowledge and transferability of con- textual representations. arXiv preprint 2019.
J., Fang, A., Smymis, G., Ivgi, M., Jordan, M., Gadre, S., Bansal, H., Guha, E., Keh, S., Arora, K., et al. Datacomp- Im: In search of the next generation of training sets for lan- guage models. arXiv preprint arXiv:2406. 1794, 2024a.
Lowerre, B. P. and Reddy, B. R. Harpy, a connected speech recognition system. The Journal of the Acoustical Society of America, 59($1):897-S99) 1976.
Li, Y. and Risteski, A. The limitations of limited context for constituency parsing. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natu- ral Language Processing (Volume 1: Long Papers), pp- 2675-2687, Online, August 2021. Association for Com- putational Linguistics. doi: 10. 10.18653//122022.cc-oong 208. URL ht attpps:/ /alaaaaaaanttooooy.oooo.a 2ot.aaannooo....r/2222....... acl-long; 208.
Lu, H., Mao, Y., and Nayak, A. On the dynamics of training attention models. In International Conference Learning Representations, 2021. URL https: / openreview net Coorummid=10ctii
Ma, Q.. Zhou, H., Liu, T., Yuan, J., Liu, P., You, Y., and Yang, H. Let's reward step by step: Step-level reward model as the navigators for reasoning. arXiv preprint arXiv:2310. 10080, 2023.
Li, Y., Li, Y., and Risteski, A. How do transformers learn topic structure: Towards mechanistic understanding. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 19789- PMLR, 29 Jul 2023. URL https: // proceedings mlr press / w202 hwtp//11ppppppp. html.
Nair, V. and Hinton, G. E. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), pp. 807-814, 2010.
Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, L., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., Jiang, X., Cobbe, K., Eloundou, T., Krueger, G., Button, K., Knight, M., Chess, B., and Schulman, We- bgpt: Browscr-assisted question-answering with human feedback, 2022. URL https: httpp:://axxxv.orrs 2112.09332
Li, Y., Kirchmeyer, A., Mchta, A., Qin, Y., Dadachev, B., Pa- pineni, K., Kumar, S., and Risteski, Promises and pit- falls of generative masked language modeling: Theoreti- cal framework and practical guidelines. In Forty-first first In- ternational Conference on Machine Learning, ICML'24. JMLR.org 2024b.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. arXiv preprint arXiv:2305.20051 2023.
Odlyzko, A. M. The rise and fall of knapsack cryptosystems. Proceedings of Symposia in Applied Mathematics, 1998. URL https: ses.aisimittiiccclll.. isscholar. org/CorpussD::11599599
sewanti

---

On the Query Complexity of Verifier-Assisted Language Generation
Ow, P. S. and Morton, T. E. Filtered beam search in schedul- ing. The International Journal Of Production Research, 26 26(1):35-62 1988.
Ugare, S., Suresh, T., Kang, H., Misailovic, S., and Singh, G. Syncode: Llm generation with grammar augmentation. arXiv preprint urXiv:2403.01633 2024.
Plantard, T., Susilo, W., and Zhang, Z. Lattice reduction for modular knapsack. In Selected Areas in Cryptography: 19th International Conference, SAC 2012, Windsor, ON, Canada, August 15-16, 2012, Revised Selected Pupers 19, pp. 275-286. Springer, 2013.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.,, Gomez, N., Kaiser, L.,, and Polosukhin, I. Attention is all you need. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vish- wanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL https::////// https::/proceednnnggg neurips.cc/ neupippa.cc/pppee///01//// 3 (55ee223337ddee111000033llllldd3 pdf.
Polu, S. and Sutskever, I. Generative language model- ing for automated theorem proving. arXiv preprint arXiv:2009.03393, 2020.
Paper.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M.. Zhou, Y.. Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-5551 202..
Wang. P., Li, L., Shao, Z., Xu, R., Dai, D., Li, Y., Chen, D., Wu, Y., and Sui, Z. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations. In Proceed- ings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 9426 9439, 2024.
Rogers, A., Kovaleva, O., and Rumshisky, A. A primer in bertology: What we know about how bert works. Trans- actions of the Association for Computational Linguistics, 8:842-866 866, 2021.
Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E.,, Narang, S. Chowdhery, A., and Zhou, D. Self-consistency im- proves chain of thought reasoning in language models. arXiv preprint 12.i:::200..11177 2022.
Rosenblatt, F. The perceptron: a probabilistic model for information storage and organization in the brain. Psy- chological review, 65(6):886 1958.
Wen, K., Li, Y., Liu, B., and Risteski, A. Transform- ers are uninterpretable with myopic methods: case study with bounded dyck grammars. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: http:///pppeeeeeeeeee net/ forum? id=0i tmaiitma
Roziere, B., Gehring, J., Gloeckle, F., Sootla, S., Gat, I., Tan, X. E., Adi, Y., Liu, J., Sauvestre, R., Remez, T., al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308. /2950, 2023.
Schützenberger, M. On context-free languages and Information and Control, ISSN 0019-9958. doi:
Wu, Y., Sun, Z., Li, S., Welleck, S., and Yang. Y. Infer- ence scaling laws: An empirical analysis of compute- optimal inference for problem-solving with language models. arXiv preprint arXiv:2408.00724 2024.
push-down automata.
6(3):246-266) 1963.
URL http:::/www.sccennces cccenee/arttceee/ii////999999999
Xie, Y., Kawaguchi, K., Zhao, Y., Zhao, J. X., Kan, M.- Y., He, J., and Xie, M. Self-evaluation guided heam search for reasoning. Advances in Neural Information Processing Systems, 36, 2024.
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling Ilm test- time compute optimally can be more effective than seal- ing model parameters. arXiv preprint arX33.2408.03314, 2024.
Yang, K. and Klein, D. FUDGE: Controlled text gen- eration with future discriminators. In Toutanova, K., Rumshisky, A., Zettlemoyer, L., Hakkani-Tur, D., Belt- agy, I., Bethard, S., Cotterell, R., Chakraborty, T., and Zhou, Y. (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolo- gies, pp. 3511-3533 Online, June 2021. Association for Computational Linguistics. doi: 10. 10.18653/v1/2021 naacl-main.276 URL https:/ /aa/ccaanttt /acaantooooooy..... org/2021 wta.221..aacll.. nww.c
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine- tuned chat models. arXiv preprint arXiv:2307.09288, 2023.
Uesato, J., Kushman, N., Kumar, R., Song, F., Siegel, N., Wang, L.,, Creswell, A., Irving, G., and Higgins, Solv- ing math word problems with process-an and outcome- based feedback. arXiv preprint arXiv:22 /4275, 14.275,,,, 2022.
12

---

On the Query Complexity of Verifier-Assistedd Language Generation
Yao, A. C.-C. Probabilistic computations: Toward unified
measure of complexity. In 18th Annual Symposium Foundations of Computer Science (sfcs 1977), pp. 222- 227. IEEE Computer Society, 1977.
Yao, S., Peng, B., Papadimitriou, C., and Narasimhan, K. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meet- ing of the Association for Computational Linguistics and the 1 1ith International Joint Conference on Natu- ral Language Processing (Volume Long Papers), pp- 3770-3785, Online, August 2021. Association for Com- putational Linguistics. doi: 10. 10.18663/112021.acllbbe 292. URL https: a/c////cla// annllanhhloogy. httpllggg.rggg.2....// acl sel-longe 292.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2023.
Zhang, S., Chen, Z., Shen, Y., Ding, M., Tenenbaum, J. B., and Gan, C. Planning with large language models for code generation. arXiv preprint arXiv:2303.05510 2023a.
Zhang, S., Dong, L., Li, X., Zhang, S., Sun, X., Wang, S., Li, J., Hu, R., Zhang, T., Wu, F., et al. Instruction tuning for large language models: A survey. arXiv preprint arXiv:2308. 10792, 2023b.
Zhang. Y., Backurs, A., Bubeck, S., Eldan, R., Gunasekar, S., and Wagner, T. Unveiling transformers with lego: a synthetic reasoning task, 2022. URL https:// org/abs/220
abs htt//bs/222000 2206. 04301.
Zhao, H., Panigrahi, A., Ge, R., and Arora, S. Do transformers parse while predicting the masked word? In Bouamor, H., Pino, J., and Bali, (eds.), Pro- ceedings of the 2023 Conference on Empirical Meth- ods in Natural Language Processing, pp. 16513-16542, Singapore, December 2023. Association for Computa- tional Linguistics. doi: 10. 10.18655/111222.emmmp...o 1029. URL https: httpttttt///claaleae //aaaaaannooooyyyoooooooo
Zhao, S., Brekelmans, R., Makhzani, A., and Grosse, R. Probabilistic inference in language models via twisted sequential monte carlo. arXiv preprint arXiv:2404117566, 2024.
Zhou, A., Yan, K., Shlapentokh-Rothmant M., Wang, H., and Wang, Y.X. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.044000 2023.
13

---

Supplementary Material
A. Discussions
A.1. Is query efficiency reasonable notion of efficiency?
There are many reasonable efficiency metrics, and they do not always positively correlate with each other (Dehghani et al., 2021).
Our paper focuses on query complexity (measured by the number of tokens generated by the language model to satisfactorily complete the task & ), and we do not claim that the same conclusions apply when we switch out query complexity for other metries of efficiency, such as wall-clock time.
We think query complexity is (but not necessarily the only, the most) important aspect of efficiency due to the following considerations:
Many existing large language model (LLM) providers charge service fees the users according the number of tokens generated by the language model for the user, i.e. query complexity.
In the single sequence generation setting, controlling all other conditions to be held the same, query complexity positively correlates with the size of computation (the number of decoder forward passes) and wall-clock time.
In the batched generation setting, admittelyy, the wall-clock time does not necessarily scale linearly with query complexity meaning that the naive best-of-n rejection sampling is not as slow as query complexity would indicate (if the LLM has sufficient bandwidth for it). However, in many realistic LLM inference settings, the LLM receives a large number of query requests per second, so there is no additional idle availability 10 for duplicating each sequence generation request by n..
Although, as mentioned above, query complexity is partially indicative of few practically important efficiency metrics (e.g. monetary cost or wall-clock time), there are aspects of these metrics that are not tracked by query complexity. For example, different types of hardware and cache may have different efficiency best practices. In particular, on GPUs and TPUs, algorithms that better exploit parallelization or tensorized computation tend be more efficient. Therefore, an important direction for future work is design and analyze hardware-awand aware algorithms that incorporate these important aspects of the inference setup.
*This definition is natural since generating one token involves one forward pass of the (decoder-only autoregressive) language model, i.c. one query.
"For example, the wall-clock time of generating n candidate responses (with batch size n) might he less than a multiplying the wall-clock time of generating I candidate response. Unless more GPUs/TPUs are allocated serve this I.L.M.

---

On the Query Complexity of Verifier-Assisted Language Generation
A.2. On the hardness of the knapsack problem
The hardness of the knapsack problem has been the subject of extensive study. Specifically, the decision version of this problem has found applications in the context of secure cryptosystems (Odlyzko, 1998). Under assumptions the input structure, the best known algorithm is based dynamic programming (Kellerer al., 2004) and runs in pscudo-polynomial time. This algorithm is also used to obtain an FPTAS and its runtime is effectively polynomial if one further assumes that the weights are polynomially bounded in D. More exact or approximate algorithms achieve polynomial runtime, under specific input structures. Specifically, when the weights form a superincreasing sequence, that is,
X, 2 Σ X, vi (2, nz,
==1
greedy algorithm solves the knapsack decision problem (Odlyzko, 1998) in linear time. On the other hand, when the density of the knapsack
D
log2 (max, [X.)
small enough, knapsack approximately solved polynomial time by lattice reduction algorithms (Plantard et al., 2013). Our argument considers the most general setting, in which no assumptions are made on the structure of the inputs {Xi))=1> and the decision problem is No-complete (Karp, 1972).
A.3. Proof intuition for Theorem
Remark 2.
To help readers parse our proof above, we provide informal intuition. The oracle Os can be thought of as hiding secret message which is binary sequence of length D - 1. Because of our construction in Equation (1), by querying the oracle with any string + 8, the outpul of the oracle will not reveal any information about 8. Therefore, to know anything about 8, the query needs to exactly match 8. For any deterministic order of searching for è over {0, D) the worst case is always that é is the last item in the search order, causing runtime 2-1
Moreover, Theorem generally applies to any algorithm A. In particular, A is even allowed to never query the generutor oracle at all. Intuitively, one candidate counter-example of our theory would be a simple algorithm A which always outputs 0 all positions (as this will obviously satisfy the counstraint A := {s Σ E 9; mod 2 0}). However, recall that Definition 2 requires that the output must have nonzero probability under the generator oracle Og. Note that 0 Vi E [D) will not have nonzero probability under Og thus violating the consiraints (unless 8; 0 vi E (T) - 1] J. The intuitive reason why the above counter-example does not work is that, it is necessary to use the oracle O2 to know the & that it hides. Therefore, any algorithm A is governed by the abooe-mentiones lower bound of searching for by querying
O g.
15

---

On the Query Complexity of Verifier-Assisted Language Generation
B. Additional experimental results
We complement Section 5 by providing additional technical details.
B.1. Additional results about language models trained on synthetic data
B.1.1. VISUALIZING THE LANGUAGE MODEL REPRESENTATIONS OF CORRECT VS. INCORRECT SEQUENCES
musthhin
30
10
Figure 1. TSNE plot for the LM bas-layer-last-positee representations of strings in Xama U Xeamen Red dots correspond to the representations of incorrect strings, whereas gray dots correspond to the representations of correct strings of comparable lengths. We can see that the representations of incorrect strings form just few clusters. This intuitively justifies using a lightweight verifier on top of these LM representations.
16

---

On the Query Complexity of Verifier-Assisted Language Generation
B.1.2. THE PREDICTED BACKTRACKS WERE NECESSARY
During the experiment Section 5.1.4, the trained verifier V predicted backtracks many positions. Were they really necessary? For each setting of backtrack quota Q and backtrack stride B, collect the set of prefixes Xpredicted hackrracks where V predicted backtracks. Then, we let the language model LM complete each string in Xprsdieted backtracks without any backtracks, using common decoding techniques such as nucleus sampling top-p- 0.9 (Holtzman et al., 2020) and argmax greedy decoding. Table 5 shows that without backtracking, the completion accuracy is much lower than the accuracy reported in Table 2. This implies that predicted backtracks were indeed challenging prefixes for the LM, which verifies that the backtracks predicted by verifier V were necessary.
#backtracks
accuracy without backtrack nucleus sampling top p = 0.9
argmax
163
0.313
0.344
163
0.337
0.319
163
0.331
0.288
2
311
0.347
0.328
297
0.357
0.349
286
0.374
0,373
4
600
0.371
0.353
532
0.419
0.404
489
0.509
0.523
Table Predicted backtracks were necessary. For each setting of backtrack quota Q and backtrack stride B, we report the number of times that Tokenwise rejection sampling with backtracking (Algorithm backtracked. Moreover, we report the completion accuracy letting the language model LM complete these backtracked prefixes without any backtrack. For each setting, the complction accuracy much lower than the accuracy reported Table This implies that these backtracked prefixes were indeed challenging prefixes the LM.
17

---

On the Query Complexity of Verifier-Assisted Language Generation
B.1.3. ERROR ANALYSIS ON THE REMAINING MISTAKES
Given the improvement of accuracy (Section 5.1.5) a result of our algorithm Tokenwise rejection sampling with backtracking (Algorithm 1), why did the model still make mistakes?
We conducted an error analysis which parses all mistakes into error types, and examine the generated token, the LM predicted most probable token, their predicted probabilities, and a few intermediate variables during the course of our algorithm Tokenwise rejection sampling with backtracking (Algorithm I).
In summary, the findings are:
1. Among 225 generated mistakes, 222 correspond to predicting an incorrect closing bracket, and 3 correspond to pre-maturely predicting the end-of-sequence <eos> token.
2. In all 225 cases, the final state of the algorithm has used up all the backtrack quota Q allocated to it, if the error predictor was perfect, the algorithm would not have been had a chance to correct these mistakes. This suggests that suitably increasing backtrack quota Q might be an effective approach in improving the accuracy (though there are trade-off's with query efficiency).
A snapshot of our error analysis result is included in Figure 2. We have released experimental codes, more error analyses.
which include
error
prefix generated_ token generated_toker toaee___oeeebbbbeeeebbe
sost_probabil token #ost_ satbbablle_toke_pped_
backtrack_
INCORRECT.CM CERRREET_CCLOINCC CLOSING BRACKET ВIИΕИЛIOЛЛЛ())0000)
0.906425
0.996425
INCORRCC_.OO BRACKET РЕИNИИОKOOONИ
0.901748
0.901748
ICCORECT_ CLOBING,
INCORREC__CM CLOSING, BRACKET ((000000010XXXX11)
0,889476
0.698475
INCORRECT_CO CLOSING BRACKET BN0IAIIIGOOOOOCXX00000
0,564808
0.934803
INCORRECT_CO ACOPRECT_CLDSING CLLSINGG BRACKET ВЛКЛΙОЛОККGЛЛXXXXXX
0.987031
0.887031
INCORRCC__OM COOORICT
NCORRECT, CLOBING, BRACKET 6(000000000X0)ИX)0)
0.762460
0.760460
INCORREC_ CLOSIINGBRACKETT :XXICT)ОИ
0.802167
0.802167
INCORRECT CLOSING BRACKET RI(00C0B((00XXXX0
0.941579
0.841579
10
NCOPRECT_CLOREE CLOSINGG BRACKET
0.987442
0,897442
BINCIX000000N0IXX11
0.966299
ICCORRCT_ CLOSING BRACKET
0,523672
0.523672
CLDBING-BRACKET 13 INCORRCC CLOBING BRACKET
0.838832
0.838892
14 INCORRECT CLOBING, BRACKET B0X0000000XXX0000XXXXX
0 0.905885
0.905665
15 INCORRCCT CLOSING, BRACKET X
0.528673
0,828873
NCORRECT CLOSING
00000000000000000000000000
17 INCORRCT_ CLOSING BRACKET РИ0АО0ОИM2АИXXX0000
0,804548
0.854548
18 INCORRCCT CLOBING, BRACKET ВпОО:ИМИИККОИЛККК
0,728838
0.722893
19
SCORRECT_CLDGING CLOSING BRACKET В0XXIXX0И0ООО/XXXXX0
0.968540
0.966640
INCORRCC CEORECN BRACKET BUD)CCU0TTЛИNN00N
0.902594
INCORRECT (00000000И(0ККXXX
0.975986
0.975085
22 INCORRCT CLOSING, BRACKET 6000000060000000
COORIECT.CLOSINGG.
0.975067
0,975087
Figure 2. Error analysis table for mistakes of language model trained on Dyck grammar and sampled using Tokenwise rejection sampling with backtracking (Algorithm 1). The last column records the remaining backtrack quota Q the time of generating the incorrect token.
"https://githinn thub. M1/IM000eMMCCMMMMM/M exi
18

---

On the Query Complexity of Verifier-Assisted Language Generation
B. 1.4. TOKENWISE REJECTION SAMPLING WITH BACKTRACKING MAINTAINS DIVERSITY
In this section, we show that the significant accuracy improvement is not at the cost of reducing diversity.
Our experiment freshly samples 100 prompts following the same distribution DycKOOD (Section 5.1.1). For each prompt, we let the trained LM independently sample 10 completions, using Tokenwise rejection sampling with backtracking (Algorithm 1) or the baseline algorithm, and will compare how many (out of 10) samples were different, and report the mean and standard error across the 100 prompts.
Table 6 shows that Tokenwise rejection sampling with backtracking (Algorithm 1) generates similarly diverse samples as the baselines of nucleus sampling with top-p = 0.9 or 1.0.
B
top.p
diversity = std err (out of 10)
4
1.0
5.52 + 3.28
0
0
0.9
5.47 3,06
1.0
5.84 3.29
Table Under the experiment setup described in Appendix B.1.4, Tokenwise rejection sampling with backtracking (Algorithm similarly diverse as the baselines of qucleus sampling with top-p 0.9 or 1.0.
19

---

On the Query Complexity of Verifler-Assisted Language Generation B.2. Additional results about generating test cases with prefrained CodeLLama
This section complements our results in Section 5.2.
B.2.1. EXAMPLES OF PROMPTS AND MODEL COMPLETIONS
def f(a, b):
return a +
List 8 test cases of the above function f, one in each line:
assert f(5, 5) == 10
assert f(1, 5) == 6
assert f(2, 8) == 10
assert f(6,, 2) == 8
f(6,
15
assert f(4, 5) == 9
assert f(9, 6) == 15
assert [(6, == 7
def knk(1, item):
assert type(() list
Lappend(item) return I
List 8 test cases the above function knk, one in each line:
def f(a, b):
return
List 8 test cases of the above function f. one in each line:
assert f(5, 8) == 13
assert f(1, 5) == 6
assert f(8,
12
assert f(6, 2) == 8
assert f(3, 9) == 12
assert [(1. 7) == 8
assert [(S,
14
assert [(1, 7) == 8
def ovs(1, item):
assert type(1) is list Lappend((tem) return
List 8 test cases of the above function ovs. one in each line:
Table Two example prompts for generating test for simple implementation of the append function for Python lists. In these examples, the following components are randomly generated and will be different for different prompts: (1) the numbers in the demonstrations (e.g. assert (5, 8) 13) as long as they are correct for addition; (2) the name of the target function (c.g. knk, ovs).
20

---

On the Query Complexity of Verifier-Assistedd Language Generation
assert
assert (11(
assert knk([1.3),)==111.3]]
assert knnk[1.3.3,2)=
assert
assert (1.
assert
def sum_list(i)
return sum(1)
List 8 test cases of the above function sum list, one in each line:
assert list([)) ==
assert sum sum_lis(([]))===
assert sum_list(1,, 3]) 3]]=44
assert sum sum_list([1, 3,5)) ==
assert 3,5 16
assert sum list([]] 7,
assert sum [int[]is(([11 5, 11]) 36
def sublist(l, sub):
assert type
assert ovs([), 1)== [1]
assert (2), (1.
assert 1)= 1,2
assert ovs([1, 21) = [1.2,3]
(v,([1,
1,2
assert ovs[[1, 2,3] == -1,,,,3,, 4]
assert (Vs 0) = [0]
assert ovs([1, 21, = [0. 1.
Table Two example generations by CodeLlama corresponding the prompts in Table 7. Note that both generations flawed: (1) the model only generated 7 test cases instead of 8, even though the prompt requested 8. Then, it generated irrelevant contents, starting from def sum_list (1)= (2) more than one generated test cases were wrong (c.g. assert ovs ([2), right-hand-side should be [2, 11). More generally, we implemented a rulc-based parser to analyze model generations and identify the error type (if any), locate the first position of error.
[1, 2], the correct
21

---

On the Query Complexity of Verifier-Assisted Language Generation
B.2.2. BASELINES
We extensively tuned the hyperparameters in common baseline decoding algorithms, including
nucleus sampling (Holtzman et al., 2020): we grid-searched top_p E 0,,,
argmax greedy decoding: equivalent to top-p 0.0.
standard autoregressive sampling: equivalent to top-p= 1.0.
temperature scaling (Ackley et al., 1985): we grid-searched temperature E (0,,,0,,004,0,,,,,,,,,., 1.0, (for each
(op.p).
Through the above grid search, we found that the best combination was top_p 0.95, temperature 1.0.
Besides, we consider baselines based on the block-best-of-n rejection sampling approach to incorporate process rewards. More details about this baseline are provided in the "Block verifier" part of Appendix B.2.3.
block-best-of-n: grid-searched [2, 2,,, fixing the best combination of top_p and temperature found by the grid search above.
will show that Tokenwise rejection sampling with backtracking (Algorithm 1) clearly outperforms all these baselines in terms of the quality vs. query complexity trade-off.
22

---

On the Query Complexity of Verifier-Assisted Language Generation
layer index
AcCaistintt +: std err
27
0.714 0.011
28
0.711 0.016
26
0.708 -00088
30
0.706 0.036
24
0.701 0.033
31
0.688 0.028
29
0.676 0.021
25
0.672 0.030
23
0.709 0.017
3
0.700 0.028
15
0.700 0.028
19
0.692 = 0.028
7
0.691 0.031
0.650 0.041
ablation: random verifier
0.663 0.027
baseline:
nucleus sampling temperature scaling
0.660 0.042
Table 9. Ablation: layer 27 representations of Lada outperform layer 31 (the last layer) in terms of the quality of the error predictor trained based on these features. We control all other setting to be the same as the top perfofforming settings of the baseline (nucleus sampling top-p= 0.95 (Holtzman et al., 2020) and temperature 1.0), whose performance is also included in the table. The other rows in this table (layer 27 and layer 31) refer to applying Tokenwise rejection sampling with backtracking (Algorithm 1) using backtrack quota Q = 4, backtrack stride B= = 4, and verifiers trained on layers 24, .... 31 of the generator (CodeLlamaa, respectively. The row ablation: random verifier refers to a verifier that returns Uniform[O, IJ. and uses the same Q. B as the above. The experiment was repeated 5 times, and we report the standard errors. The rows sorted by mean AcCaisines (Section 5.2.1).
B.2.3. TRAINING THE VERIFIER
We follow almost the same training approach as Section 5.1.2. The differences are described below. The generator language model LM is pretrained CodeLlama (Roziere et al., 2023) (7B parameters), which we freeze during our experiments.
An intermediate layer provides more informative representations for verifier training than the last layer. Instead of training the verifier V on top of the last layer (i.e. layer 31) representations of LM, we instead treat the layer index as a hyperparameter, and conducted grid search over layer index E [3, 7, 11, 15, 19, 23, 27, 31). Among these candidates, layer 27 representations resulted in the best accuracy. We therefore exclusively used layer 27 representations in subsequent experiments, and finally conducted an ablation study on the top-performing setting of the baseline back-test the impact of using other layers. Table 9 shows that layer 27 outperforms layer 31. We conjecture that the layer 31 representations may be too specific for the next-token prediction task, which is not necessarily the optimal for discriminating correct prefixes vs. incorrect ones. 12 We also include results for a few other layers near the final layer. Note that even with a sub-optimally chosen layer, the accuracy of Tokenwise rejection sampling with backtracking (Algorithm 1) still outperforms the tor-perforiing settings of the baseline found through grid search. 13
With limited backtrack quota, it is better to be conservative in its usage. The verifier V is trained with binary labels (1 if correct, 0 if wrong). Although there a roughly equal number of training samples whose labels are 0 or are 1, using 0.5 as the error prediction threshold turned out to be suboptimal. Since our Tokenwise rejection sampling with backtracking (Algorithm 1) only allows a small backtrack quota Q = 4, it makes sense to only use backtrack quota when the error predictor is very confident that the current intermediate generation is wrong. Moreover, compared with our synthetic Dyck grammar setting (target length = 32) (Section 5.1). our code generation setting allows much longer generations (up to 384), which further justifies conservatively spending the small backtrack quota Q. Consequently, we consider decreasing the error prediction threshold 0.1. Table 10 shows that 0.1 is a better error prediction threshold than the default 0.5 in all settings tried.
1his is in line with some prior works that also observed that the final layers of language models tend to he more task-specific than the intermediate layers (Liu, 2019; Kovaleva al., 2019; Rogers et al., 2021). See Appendix B.2.2 for details about baselines.
23

---

On the Query Complexity of Verifier-Assisted Language Generation
Q
B
top.p
temperature
error prediction threshold
ACCasstnnt
std err
0.95
1.0
0.1
0.714 0.011
4
4
0.95
1.0
0.5
0.676 = 0.019
4
4
1.0
1.0
0.1
0.639 + 0.061
4
4
1.0
1.0
0.5
0.604 0.047
4
1.0
1.2
0.1
0.440 0.026
1.0
1.2
0.5
0.334 0.013
10
1.0
1.0
0.1
0.622 0.046
4 10
1.0
1.0
0.1
0.604 = 0.030
Table 10. Ablation: 0.1 is a better error prediction threshold than the default 0.5 in all settings we tried, including various nucleus sampling (Holtzman al., 2020) top-p, temperature scaling, and backtrack stride B. In this table, we divide the rows into groups of 2, separated by double horizontal lines. such that within each group, the only difference is the error prediction threshold. In all groups, 0.1 leads to higher AcCaisiner than 0.5. The experiment was repeated 5 times, and we report standard errors.
verifier # MLP layers
verifier validation accuracy
AcCastia:t std
0.96
0.714 0.011
4
0.97
0.699 + 0.038
2
0.97
0.687 = 0.035
0.97
0.684 0.015
ablation: random veritier
0,50
0.663 + 0.027
baseline:
nucleus sampling temperature scaling
N/A
0.660 + 0.042
Table 11. Ablation: Deeper verifiers do not outperform the 1-linear-laye layer verifier even though they can be trained to similar error- predicting accuracies on held-old validation set. We control all other setring to be the same as the top-performing settings of the baseline (nucleus sampling top-p= 0.95 (Holtzman al., 2020) and temperature 1.0), whose performance is also included in the table. The other rows in this table refer to applying Tokenwise rejection sampling with backtracking (Algorithm 1) using backtrack quota Q = 4. backtrack stride B= 4, and verifiers with 1, 2, 4, layers, respectively. The row ablation: random veriferr refers verifier that returns Uniform[O, 1J, and uses the same Q, B as the above. The experiment was repeated 5 times, and we report the standard errors. The rows are sorted by mean Accasina (Section 5.2.1).
Block verifier. Our verifier applies to the token level, i.c. predicting an accept/reeect action after the generator LM generates each token. In many practical settings (including ours), it is natural divide the generated output into blocks (each block may contain multiple tokens), e.g. in writing math proofs, each block may correspond to one reasoning step; in writing codes, each block may correspond to one line of codes. Recent works achieved strong empirical performance by generating multiple candidates for each block of intermediate model generations, train process reward models that evaluate each candidate, and select the best-scoring candidate (see e.g. Wu et al. (2024) and references therein). We refer to this as the bblock-best-ofaae approach. To compare with such "block-best-of-n" baselines, we train "block verifiers" Voteck which scores prefixes that are full lines of model output for our task. We will show that this "block best-of-n" approach is helpful, but is outperformed by our Tokenwise rejection sampling with backtracking (Algorithm 1) in terms of accuracy-efficien trade-off.
Does a deeper verifier perform better? The above experiments follow Section 5.1.2 in training a single-linear- verifier. In this section, we test the effects of scaling up the verifier depth. Specifically, we test verifiers based on Multi- Layer Perceptrons (Rosenblatt, 1958) of depths 2, 4, 8, with ReLU activations (Nair & Hinton, 2010) between adjacent parameterized layers. Table 11 shows that more MI.P layers did not outperform the 1-linear-layer verifier even though they can be trained similar error-predicting accuracies, measured by their accuracy in predicting whether prefix is correct or incorrect held-old validation set of prompts for task (Section 5.2.1) followed by partial generations by CodeLlama. In other sections of this paper, unless otherwise noted, we always use a single-linear-laye verifier for Tokenwise rejection sampling with backtracking (Algorithm 1) (and of course, no verifier for baselines (Appendix B.2.2) ).
Where are the potentials for further improving AcCaistinet? ? How optimal are our verifiers, and what are some ways to further improve them? To probe these potentials, we wrote a rule-based groundtruth verifier for our task (Section 5.2.1) and used it as drop-in replacement of our trained verifier. Table 12 shows that the AcCaissint enabled by our trained verifier
24

---

On the Query Complexity of Verifier-Assisted Language Generation
almost reached the AcCdistinet enabled by the groundtruth verifier, showing that improving verifier training may not be the most fruitful direction for further improvement. Interestingly, using much larger Q B (increasing from 4 to 10) does not necessarily improve the accuracy (sometimes even decreasing the accuracy). We conjecture that in these experiments, the (imperfect) generator oracle (CodeLlama), not the verifier, was the bottleneck for AcCaistint- As result, unnecessarily backtracking and forcing the model to re-generate more tokens may increase the chance that the model makes mistakes.
verifier type
Q
Accassiact + std err
groundtruth
4
0.719 + 0.022
groundtruth
10
0.717 = 0.015
trained
4
0.714 = 0.011
trained
10
0.692 0.025
ablation: random verifier
0.663 0.027
baseline:
nucleus sampling + temperature scaling
0
0.660 + 0.042
trained
10 0.622 + 0.046
Table 12. Ablation: Our trained verifier approaches the accuracy of the groundtruth verifier, evaluated by their ability to assist CodeLlama in completing our
generation task (Section 5.2.1) using Tokenwise rejection sampling with backtracking (Algorithm 1). In these experiments, we control the nucleus sampling (Holtzman et al., 2020) top 0.95 and temperature scaling 1.0 which are the optimal setting for haseline, found by grid search (Appendix B.2.2). The rows sorted by AcCaistine- The row ablation: random verifier refers a verifier that returns (niform(O. 1J. Interestingly, using a much larger Q B does not necessarily improve the accuracy (sometimes even decreasing the accuracy). We conjecture that generator model, CodeLlama, imperfect, so unnecessarily backtracking and forcing the model to re-generate more tokens may increase the chance that the model makes mistakes. The experiment was repeated 5 times, and we report standard errors.
25

---

On the Query Complexity of Verifier-Assisted Language Generation
B.2.4. FULL RESULTS OF CODELLAMA EXPERIMENTS SECTION 5.2
Caption for Table 13 (on the next page). Tokenwise rejection sampling with backtracking (Algorithm 1) improves accuracy and outperforms commonly used baselines, including nucleus sampling top.p. p. temperature scaling (temp), and block best-of-n (BBoN) (Appendix B.2.3). Baselines extensively hyperparameter tuned (Appendix B.2.2). Backtrack quota Q = 0 means baseline without verifier. When Q > 0, the row denotes Algorithm 1 with the corresponding Q and B. The column layer idx denotes which layer of CodeLlama provided the representations for training the verifier, and err threshold denotes the cutoff below which the verifier output is interpreted as a rejection (both were experimented in Appendix B.2.3). When BBoN is specified, the row denotes the number of candidates generated for each block; otherwise, the row does not use block best-of-n. The rows are sorted by AcCaistnet- Controlling top-p and temperature, Algorithm leads to better tradeoff between AcCaistinet and query complexity (both defined in Section 5.2.1) than all other methods. The experiment was repeated 5 times, and we report the standard emros.
26

---

On the Query Complexity of Verifier-Assistedd Language Generation
Q
B
layer idx
err threshold
top_p
temp
BBoN
AcCaistint t std err
C
4
4
27
0.1
0.95
1.0
0.714 0.011
39443 1: 235
4
31
0.5
0.95
1.0
0.688 = 0.028
39629 - 135
0
27
0.95
1.0
2
0.684 + 0.038
39364 = 1252
4
4
31
0.1
0.95
1.0
0.677 + 0.033
39546 98
4
27
0.5
0.95
1.0
0.676 = 0.019
38555 - 140
0
0.95
1.0
0.660 + 0.042
38231 + 165
27
0.1
1.0
1.0
0.639 0.061
31274 = 1559
0.9
1.0
0.634 = 0.023
38393 14
0
0.9
1.2
0.630 1 0.028
38005 1 232
0.8
1.2
0.627 0.015
38343 90
27
0.95
1.0
4
0.623 1 0.036
65496 7638
4
10
27
0.1
1.0
1.0
0.622 = 0.046
32923
1772
27
0.5
1.0
1.0
0.604 0.047
31091 968
10
27
0.5
1.0
1.0
0.604 1 0.030
27287 7580
0
0.95
1.2
0.584 = 0.027
36601 535
1.0
0.8
0.562 1 0.021
36610
0
27
0.95
1.0
0.339 1 0.038
122933 1 3832
0
0.7
1.2
0.531 = 0.035
38400 =
0.95
0.8
0.523 0.029
38386
0
0.8
1.0
0,511 = 0.028
38400 =
0
1.0
1.0
0.504 1 0.025
30754 = 1272
0.9
0.8
0.466 1 0.032
38400 1
4
4
27
0.1
1.0
1.2
0.440 = 0,026
24916 = 954
1.0
0.6
0.399 1 0.070
38320 73
0.7
1.0
0.353 - 0.021
38400 +
0
0.8
0.8
0.351 = 0.039
38400 + 0
0
0.95
0.6
0.337 1 0.053
38400 1
27
0.5
1.0
1.2
0.334 = 0.013
24217 = 1214
0
0.9
0.6
0.284 1 0.044
38400 1
1.0
1.2
0.269 0.025
21906 = 1780
0.7
0.8
0.239 - 0.019
38400 +
0
0.8
0.6
0.212 1 0.011
38400 1 0
1.0
0.4
0.207 0.029
38400 +
0.95
0.4
0.176 1 0.013
38400 1 0
0
0.9
0.4
0.147 1 0.013
38400 1 0
0.6
0.101 0.028
38400 +
1.0
0.2
0.080 1 0.020
38400 1 0
0
0.8
0.4
0.074 = 0.027
38400 + 0
0.95
0.2
0.057 1 0.018
38400
0
0.9
0.2
0.029 1 0.015
38400 1 0
0
0.7
0.4
0.025 = 0.016
38400 + 0
0.2
0.021 1 0.014
38400 1
0
0.7
0.2
0.018 = 0.011
38400 + 0
0.0
1.0
0.013 1 0.000
38400 1 0
Table Tokenwise rejection sampling with backtracking (Algorithm I) improves accuracy commonly used baselines, including nucleus sampling top-p. temperature scaling (temp), and block best-of-n (BBoN) (Appendix B.2.3).
outperforms
space constraints. more detailed captions are the beginning of this section. To help readers parse these results, we included smaller tables, each analyzing single aspect: please refer to Table 4 in Section 5.2.2, Table 10 in Appendix B.2.3, Table in Appendix B.2.3, and Figure Section 5.2.3.
27

---

On the Query Complexity of Verifier-Assisted Language Generation
B.2.5. VISUALIZING THE QUERY EFFICIENCY OF TOKENWISE REJECTION SAMPLING WITH BACKTRACKING
This section complements the query efficiency visualization discussed in Section 5.2.3,
Verifier-Assisted Sampling with Backtrack is Query-Efficient
exp: Q=4, B=4, top_p=0.95, temperature=10
baseline: top_ top_p=0.95, temperature=1.00 best of
number of distinct correct test cases generated
baseline: top_p=0.95, temperature=1.0
exp: Q=4, 8=4, top_p=1.0,, temperature=110
500
baseline: top_p=0.9, temperature=1.0
baseline: top_p=0.9, temperature=1.2
baseline: top_p=0.8, temperature=1.2
baseline: @op_p=0.95, temperature=1.0, best of 4
exp: Q=4, B=10, top_p=1.0,, temperature=1.0
baseline: top_p=0.95, temperature=112
300
baseline: top_p=1.0, temperature=0.8
baseline: top 00995, temperature=110. best of
200
baseline: top top_p=0.7, temperature=11.2
baseline: top_p=0.95, tem
baseline: top_p=0.8, temperature=1.0
100
baseline: top_ -op_p=1.0, temperature=100
baseline: top_p=0.9, temperature=0.8
Q=4, 8=4, top_p=1.0, temperature=1122
baseline: top_ 11000 temperature=0.6
20000
40000
60000
80000
100000
120000
baseline: 007, temperature=100
number queries
baseline: top 000_, temperature=0.8
Figure 3. Tokenwise rejection sampling with backtracking (Algorithm 1) is query-efficient. The horizontal axis denotes query complexity C, and the vertical axis denotes the number of distinct correct test cases generated Nasuaett both defined in Section 5.2. Blue dashed lines correspond the baselines (described in Appendix B.2.2), whereas orange solid lines correspond to Tokenwise rejection sampling with backtracking with various Q and B, both defined in Algorithm 1. Since the slopes of the orange curves are visihly greater than the slopes of the blue curves, we conclude that Tokenwise rejection sampling with backtracking is more query-efficient than baselines. The experiment was repeated 5 times, and each dot is the average metric of these runs. The specific numbers and standard errors are reported Table A more zoomed-in version of this plot is in Figure 4.
"This visualization here in Figure 3 slightly favors the "block best-of-n sampling" baseline, because its implementation stops the decoding process once the requested number of test cases generated, whereas when running algorithm non-hest-of-n baselines, the model is allowed (and fact does indeed) generate irrelevant tokens afterwards, which hurts query complexity. Even under this disadvantage, Tokenwise rejection sampling with hacktracking still outperforms "block best-of-n sampling" baselines.
28

---

On the Query Complexity of Verifier-Assistedd Language Generation
Verifier-Assisted Sampling with Backtrack Query-Efficient
exp: Q=4, B=4, top_p=0.95, temperature=1.0
baseline: top_p=0.95, temperature=110
number of distinct correct test cases generated
exp: Q=4, B=4, top_p=1.0, temperature=1.0
500
baseline: top_p=0.9 temperature=1.0
baseline: top_p=0.9, temperature=1.22
baseline: top_p=0.8, temperature=11.2
exp: Q=4, B=10, top_p=1.0, temperature=1.0
baseline: _op_p=0.95, temperature=112
baseline: top_p=1.0, temperature=0.8
baseline: top_ 000_, temperature=1.2
baseline: top_p=0.99 temperature=0.8
baseline: top 000.8, temperature=1.0
200
baseline: top_p=1.0, temperature=1.0
baseline: top_ -p0.9.0....pp----0000000000000 temperature=0..8
exp: Q=4, B=4, top_p=1.0,, temperature=1.2
100
baseline: 100_p_1.0,,p temperature=0.6
baseline: top_p=0.7, temperature=1.0
0
baseline: top_ 00p_,=0.8, temperature=0.8
baseline: top_p= 00995, temperature=0.6
5000
10000
15000
20000
25000
30000
35000 40000
baseline: top_ 00.9, temperature=0.6
number queries
Figure 4. Similar Figure just more zoomed-in, excluding block best-of-n baselines (Appendix B.2.3).
29

---

On the Query Complexity of Verifier-Assisted Language Generation
B.2.6. TOKENWISE REJECTION SAMPLING WITH BACKTRACKING GENERALIZES BETTER TO OUT-OF-DISTRIRUTTON PROMPTS
In this section, show that Tokenwise rejection sampling with backtracking (Algorithm 1) generalizes better to out- of-distribution prompts than the best nucleus sampling and temperature scaling baseline in Appendix B.2.2. Unlike the synthetic Dyck grammar setting, on real-world LLMs we do not have precise quantitative control over how "out- of-distribution" prompt is for the LLM. We therefore assume that a sufficient condition for a prompt in our setup to be disttiitiiiiittioonn is that the name of the target function denotes some meaning which is different from the actual implemented functionality (i.e. list append) (recall the task setup in Section 5.2.1). Two examples of such out-of- distribution prompt are provided Table 14. We validate this assumption by observing that the aceuracy indeed degrades such "out-of-distribution" prompts, suggesting that the model is indeed confused by the inconsistency between the function names and the function implementations. However, analogous (Section 5.1.5). Tokenwise rejection sampling with backtracking (Algorithm 1) again suffers much less reduction in accuracy on these "out-of dfistiiibbuttioon' prompts. The detailed comparisons are reported in Table 15.
observations the synthetic Dyck grammar
def f(a, b): return
List 8 test cases the above function f, one in each line:
assert f(6, 5) = 11
assert I(3, 2) = 5
assert f(5, 4) = 9
assert f(1, 5)
assert f(5, 4) = 9
assert f(3, 5) = 8
assert f(5, 6) = 11
f(2,
8
def add(1, item):
assert type(l) is list lappend(item) return
List 8 test cases of the above function add, one in each line:
def f(a, b):
return a
List 8 test cases of the above function f, one in each line:
assert f(8, 7) 15
assert f(8,
assert f(4, 7) = 11
assert f(8, 4) = 12
assert f(7, 4) = 11
assert 1(8, 4) 12
assert [(1, = 2
assert 5) = 10
def exp(1, item):
assert type(1) list lappend((tem) return
List 8 test cases of the above function exp. one in each line:
Table 14. Two example out-of-distrriuttinn prompts for generating test cases simple implementation of the append function for
Python lists. Different from the prompts in Table 7, here the function names denote a clear meaning (c.g. add exp), which, however, different from what the function implements (i.c. append).
30

---

On the Query Complexity of Verifier-Assisted Language Generation
Q
err threshold
in-distribution ACCdistnct + std err
OOD ACCaisinet = std err
4
0.1
0.714 + 0.011
0.710 = 0.029 0.687 + 0.024
4
0.5
0.676 + 0.019
0.660 + 0.042
0.606 = 0.034
Table Tokenwise rejection sampling with backtracking (Algorithm generalizes better out-of-distribution prompts than best nucleus sampling and temperature scaling baseline in Appendix B.2.2, which identified by grid scarch (Table 13) to be top-p= 0.95, and temperature 1.0. We manually pick 10 target function names according to Appendix B.2.6 which were unseen when training the verifier (Appendix B.2.3). When backtrack quota Q 0, the denotes baseline algorithm that does not the verifier (and consequently the backtrack stride B will not matter). The column err threshold denotes the cutoff below which the error predictor output is interpreted (Algorithm 1) with the corresponding Q and B. Tokenwise rejection sampling with backtracking (Algorithm 1) suffered minor or no drop between in-distribution and OOD AcCaisinct, whereas the baseline suffered drop by more than one standard error. The experiment was repeated 5 times, and we report the standard errors.
rejection (Appendix B.2.3). When 0, the denotes Tokenwise rejection sampling with backtracking
31

---

On the Query Complexity of Verifier-Assisted Language Generation
B.3. Additional ablation experiments the Tokenwise rejection sampling with backtracking algorithm (Algorithm 1)
Besides the ablation experiments in Appendix B.2.3 which probe various aspects of verifier training, in this section, focus algorithmic component.
Concretely, line 10 of Tokenwise rejection sampling with backtracking (Algorithm 1) re-generates the erased positions using argmax. This was motivated by our results in Section 5.1.1 which suggest that out-of-distribuiie prefix is a cause of generator mistakes. As a remedy, redoing the crased positions using argmax intended to increase the generator- predicted probability of the partially sampled generation, which (concatenated with the prompt) will be the prefix for subsequent generation steps. We include an ablation study verifying that this improves the accuracy, significantly under the synthetic data setting (Table 16), and only slightly (without hurting diversity) under the real data setting (Table 17).
sampling algorithm
ferrors 1 std
Algorithm
179.4 = 1.020
ablation: no argmax
245.8 = 8.658
Table 16. Re-generating the erased positions using argmax in Tokenwise rejection sampling with backtracking (Algorithm 1) reduces completion errors on unseen distro--ist (OOD) prefixes in Dyck grammar. We fixed nucleus sampling (Holtzman al., 2020) 0.9,, backtrack quota Q 4, and backtrack stride B = 4 (the best settings in Table 3). The row "ablation: no argmax" refers to removing lines 9-12 in Algorithm
report the number completion errors occur when completing an unseen of 10000 independently sampled out-of-dlsttriutte prompts DyckooD The experiment was repeated times, and we report the standard emrors.
sampling algorithm
err threshold
Accassinet + std err
Algorithm I
0.1
0.714 1 0.011
ablation: no argmax
0.1
0.711 + 0.032
Algorithm I
0.5
0.676 1 0.019
ablation: argmax
0.5
0.663 1 0.023
Table 17. Re-generating the erased positions using argmax in Tokenwise rejection sampling with backtracking (Algorithm 1) slightly improves the -ivurayydivverstty tradeoff' (Section 5.2.1) in our test case generation task. We fixed nucleus sampling (Holtzman et al., 2020) top p 0.95, backtrack quota refers to removing lines 9-12 in Algorithm 1. The column err threshold denotes the cutoff helow which the error predictor output is interpreted as rejection (Appendix B.2.3). The experiment was repeated 5 times, and we report the standard errors.
and backtrack stride B 4 (the best settings in Table 13). The row "ahlation: argmax"
32


Reviews:
[{"review_id": "0q9Ny5QcV5", "reviewer": "Reviewer_BPwH", "summary": "This work studies the problem of constrained autoregressive language generation from the perspective of computational complexity, showing that for even very simple autoregressive oracles (i.e. autoregressive language models) and very simple constraints, the task of constrained generation can be computationally hard, while becoming tractable if given access to a process verifier. Instead of trying to propose some new constrained decoding algorithms, this paper aims to conduct an a systematic study (theoretical and empirical) covering three most commonly leveraged constrained decoding paradigms: (1) sequence-level (rejection) sampling w/ access to a sequence-level verifier (2) token-level rejection sampling with a process verifier (that works on partial sequences) (3) token-level rejection sampling + backtracking. The paper first (i) establishes the difficulty of constrained generation due to the oracle itself being complicated, then (ii) demonstrates the exponential separation between (1) and (2) when the oracle is simple, and lastly (iii) verifies the advantages of (3) over (2), i.e. the benefit of backtracking, as well as the advantages of (2) over (1) with well-controlled synthetic experiments. The theoretical results in this paper are not ground-breaking but the arguments and ideas behind are somewhat fundamental to the study of constrained autoregressive generation in general. In addition, Proposition 2 also makes a nice and clean argument uncovering the bias (in terms of approximate probabilistic inference) carried by some of the commonly adopted constrained generation approaches for structured output (i.e. JSON generation).", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! In the following, we respond to a few points raised in your review.\n\n**1. Additional references.**\n\nThank you for the recommendations! Methods like FUDGE [1] are indeed related to a slight extension to our framework. In particular, the attribute predictor in FUDGE can be thought of as training a process verifier (Definition 3 in our paper) which, instead of outputting binary acceptance / rejection decisions, returns a probability of accepting each prefix. We will cite [1] and references about controllable text generation literature therein, and include a discussion along these lines. \n\n[1] Yang, Kevin, and Dan Klein. FUDGE: Controlled text generation with future discriminators. 2021.\n\n**2. Studying this problem in the settings where proper conditioning is desired.**\n\nWe agree that this is an interesting and challenging setting! The main difficulty is understanding what are reasonable assumptions on the power of the process verifier. Proposition 2 suggests that a verifier that solely outputs a binary answer (whether there exists a completion of the prefix in the target domain) is not powerful enough. On the other hand, a simple modification of part 2 of Proposition 1 also shows that a “perfectly calibrated” process verifier (which outputs the conditional probability of the prefix according to the target distribution) can be trivially used to design a linear-time algorithm to sample from the target distribution. Finding reasonable assumptions would involve both theoretical reasoning and incorporating empirical evidence from trained verifiers.  \n\n**3. KL divergence between the ground-truth and the trained model in Dyck grammar models.**\n\nIn summary: this KL divergence is very small (meaning that the trained model is very well-calibrated against the groundtruth next-token distribution) when completing in-distribution prefixes. For out-of-distribution prefixes, the KL divergence is sometimes large (meaning that the calibration is worse).\n\nMore specifically: we define the out-of-distribution prefixes as Dyck_OOD (above Definition 9 in Section 5.1.1 of the paper). Under this setting, a visualization of the calibration results is included in this figure: https://ibb.co/ymSGGsv2. \n\nIt can be seen that in this figure, for both the (in-distribution) training set and eval set, the model-predicted log probability of a sequence is generally consistent with the groundtruth log probability. For most sequences generated by the model itself, this consistency also holds, though for some model-generated samples, the model predicts a finite log probability, but the groundtruth log probability should be negative infinite (visualized at -100), because these model-generated samples are not grammatical. For samples generated according to Dyck_OOD, the rightmost subplot of this figure shows that, in many cases, the model can be very miscalibrated. \n\nIn calibrated cases, for each prefix, it takes a relatively small number of samples to cover the support for valid next tokens (because vocabulary size is small, and the next token probability is either exactly zero or lower bounded away from zero). In miscalibrated settings, it may take a large number of samples to cover the support for valid next tokens (e.g. when the model predicts an extremely small probability for some correct continuations).", "claims_and_evidence": "The claims are well supported by either theoretical results or empirical evidences.", "methods_and_evaluation_criteria": "The synthetic empirical evaluation employed by this paper is very rigorous and immediately to-the-point.", "theoretical_claims": "Yes, I checked the (sketch) proofs of the theoretical results. They are sound and well-written.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "See summary.", "essential_references_not_discussed": "The authors should probably include references to some of the controllable text generation literature such as *Yang, Kevin, and Dan Klein. \"FUDGE: Controlled text generation with future discriminators.\" arXiv preprint arXiv:2104.05218 (2021).* and more.", "other_strengths_and_weaknesses": "See summary.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. It would be nice if the authors/other people can study this problem in the settings where proper conditioning, i.e. we want to sample from $p(s) \\propto \\mathbf{1}(s \\in A) p_{\\mathcal{O}}(s)$, is desired.\n2. For the models trained on Dyck grammar, as you sample from them, how many samples to do you need to cover the whole support of the constraints? More specifically, do they achieve near 0 KL divergence between the ground-truth and the trained model?", "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": "UVOxD7x9qr", "reviewer": "Reviewer_jJPP", "summary": "The paper presents several theoretical and experimental results on the query complexity of constrained decoding. First, in Section 3, it demonstrates theoretically that there exists tasks for which constrained decoding is difficult without a verifier. Then, in Section 4, it shows that for certain problems, the access to a process verifier significantly makes constrained decoding easier. Finally, in Section 5, the paper presents experimental results to validate their theoretical results in Sections 3 and 4.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! In the following, we respond to a few points raised in your review.\n\n**1. Scope of our theory, imperfect verifiers**\n\nWe see one of our main theoretical contributions as being a new formalism for theoretically reasoning about algorithms for verifier-assisted language generation. Moreover, our theoretical analyses already illustrate a few practically relevant claims: the importance and power of verifiers from information-theoretical (Theorem 1) and computational (Theorem 2) perspectives, and the challenge of maintaining calibration while incorporating a verifier (Proposition 2).\n\nWe agree with the reviewer that there are multiple ways in which our results should be extended in order to guide practical algorithm design—in particular, an important aspect is dealing with imperfect verifiers. The main challenge is mathematical modeling: namely, what are assumptions on the verifier that comport with empirical evidence (i.e. satisfied by trained verifiers in practice), but are also provably theoretically helpful, and conducive to designing better algorithms.  \n\nWe hope that our proposed theoretical framework and these initial results will motivate the community to tackle such questions. Finally, for some of these relaxations of the theoretical assumptions, our paper includes careful empirical analyses which will hopefully inspire future theory. \n\n**2. Adding experimental results with perfect verifiers**\n\nThank you for your suggestion! We ran experiments using perfect groundt-truth verifiers. We show the results for the Python test case generation task in this figure: https://ibb.co/pv5z26Wk. In particular, our trained verifier approaches the accuracy of the ground-truth verifier. \n\nIn addition to perfect verifiers, we also reported experimental results with imperfect, trained verifiers with an eye towards other realistic tasks (e.g. creative story writing), because in such settings it’s not straightforward to implement perfect verifiers. This is to illustrate that our approach of training neural network-based verifiers is applicable to more general tasks. \n\nOur Dyck grammar task can be seen as a special case of the task proposed in SynCode. We will cite this paper and discuss its relevance in our Related Works section. \n\n**3. Why not use larger Q, B; can larger Q, B decrease the accuracy?**\n\nWe first note a possible misunderstanding: Table 1 and Table 2 are not directly comparable because they test different settings. In Table 1, we use a ground-truth verifier to exactly locate the first position of error, and allow the generator to backtrack once. In Table 2, we use a trained verifier. \n\nIn particular, Table 2 shows that, when backtrack quota (Q) and stride (B) are small, increasing them always results in higher accuracy.\n\nWhen using much larger Q or B, our results in https://ibb.co/pv5z26Wk show that even with a perfect verifier, applying it too many times can decrease the accuracy. We conjecture that the generator model, CodeLlama, is imperfect, so unnecessarily backtracking and forcing the model to re-generate more tokens may increase the chance that the model makes mistakes.\n\n**4. Algorithm 1, i.e., Line 6**\n\nYes it should be V(x+s) = 0. Thank you for catching this typo!", "claims_and_evidence": "I feel that the theoretical results are very weak as they only show the existence of hard problems but do not touch the difficulty in general. Can the authors comment on this? Moreover, the results only consider cases where the members of the constraint set A have fixed length. In practical use cases, the target length can vary, e.g., for code syntax and JSON.\n\nThere is a discrepancy between the theoretical results and the experimental results. While the theoretical results assume a perfect verifier that outputs a boolean value, the experiments leverage imperfect, trained verifiers that output a probability. On a high level, the problems studied by the theoretical and the experimental sections can be interpreted differently: the former focuses on the generation of structured outputs that can be described by symbolic constraints, while the latter targets the generation of any outputs with a trained verifier. The accuracy of the imperfect verifiers is also low, e.g., ~70% as shown in Section B.2.3. I think it is possible to construct perfect verifiers for both experiments in Section 5, e.g., leveraging SynCode (https://arxiv.org/abs/2403.01632). Why train the verifiers instead?", "methods_and_evaluation_criteria": "The backtracking condition in Algorithm 1, i.e., Line 6, does not look correct to me. Shouldn’t it be V(x+s) = 0?", "theoretical_claims": "The correctness of the theoretical claims look good to me. As discussed in the “Claims And Evidence” section, they are just not strong enough in my opinion.", "experimental_designs_or_analyses": "The experiment results are not impressive either. If we compare the accuracy between Tables 1 and 2, the access to a verifier with Q=1 or Q=2 can even decrease the accuracy, for the same B value. I am not even sure if the results for Q=1 or Q=2 are interesting. Since we have access to the verifier, why do we only use it once or twice?", "relation_to_broader_scientific_literature": "I think the topic studied by this paper is very important, given LLMs’ tendency to hallucinate and the promise of using constrained decoding to address these hallucinations. However, I have various concerns about the paper’s results, as discussed in the other review sections.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "N/A.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "N/A.", "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": "BNH0G71Ngk", "reviewer": "Reviewer_LdiQ", "summary": "This paper introduces a mathematical framework for analyzing verifier-assisted language generation and shows that process verifiers can transform intractable generation problems into tractable ones.  Through theoretical analysis and experiments on synthetic grammar and code generation tasks, they demonstrate their approach significantly outperforms baselines in computational efficiency, accuracy, and generation diversity.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! In the following, we respond to a few points raised in your review.\n\n**1. When constraints are \"softer\" or probabilistic rather than binary.**\n\nThere could be multiple types of constrained generation tasks with non-binary constraints. In the following, we explain our thoughts on two common types:\n\n(1) Suppose the constraints are specified as a probabilistic distribution over responses, such that better responses are assigned higher probabilities, and the task is to sample according to this distribution. The main difficulty then is understanding what are reasonable assumptions on the power of the process verifier. Namely, Proposition 2 suggests that a verifier that solely outputs a binary answer (whether there exists a completion of the prefix in the target domain) is not powerful enough. On the other hand, a simple modification of part 2 of Proposition 1 also shows that a “perfectly calibrated” process verifier (which outputs the conditional probability of the prefix according to the target distribution) can be trivially used to design a linear-time algorithm to sample from the target distribution. Finding reasonable assumptions would involve both theoretical reasoning and incorporating empirical evidence from trained verifiers.  \n\n(2) Suppose the constraints are specified as scores over the responses, such that better responses are assigned higher scores, and the task is to sample responses with high scores. Under this setting, one approach to the verifier is known as reward modeling in the literature. (Our response to your second question below includes more discussion on reward modeling.) We surmise that our verifier-assisted approach can be applied to this setting as well, by either setting a cutoff for our verifier (reward model) predicted scores, or accepting a prefix according to a probability predicted by the verifier. These approaches can very likely improve the average reward of the final generated responses. Like case (1) above, one challenge is to maintain the calibration of the output distribution against some target distribution. \n\n**2. How do you expect the results to generalize to more complex programming tasks with deeper logical dependencies and constraints?**\n\nThank you for raising this important question! A key component of our approach is the verifier – the success of our token-wise rejection sampling with backtracking algorithm relies on the ability of the verifier to correctly reject partially decoded sequences that are wrong. Therefore, more complex programming tasks may require larger verifiers or more verifier training data. \n\nDespite these challenges, prior works have shown strong potentials for verifiers. For example, one approach to training verifiers is to “soften” them as reward models: train the verifier to predict a higher score for correct responses, and lower scores for incorrect ones. In the case of programming tasks, the RewardBench leaderboard [1] shows that researchers have developed accurate reward models that can distinguish between correct code vs. buggy codes in several common programming languages (with >95% accuracy). \n\nIt may be a more challenging task to train process verifiers (Definition 3 in our paper) that can check any partially generated codes at arbitrary positions. However, we believe that since code is highly structured, it is promising to incorporate existing tools such as compilers/interpreters to provide additional signals for verification, or to automatically break down the programming tasks in to logical steps (e.g. a simple baseline is to treat each full line as a step), and train the verifier to check at the end of each logical step. \n\n[1] Nathan Lambert et al, RewardBench: Evaluating Reward Models for Language Modeling, 2024.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "The methods and evaluation criteria in the paper are well-aligned with the problem of verifier-assisted language generation.", "theoretical_claims": "1. Theorem 1 shows that without a verifier, certain constrained generation tasks require at least $2^{D-1}$ oracle queries in expectation. The proof constructs a scenario where the algorithm must identify a specific prefix among all possible prefixes and uses Yao's minimax lemma to establish the lower bound for randomized algorithms.\n2. Theorem 2 establishes that even with simple constraints like those in the knapsack problem, constrained generation can be NP-hard without a verifier. The proof is a straightforward reduction from the knapsack problem.\n3. Proposition 1 demonstrates the computational benefits of tokenwise rejection sampling with a process verifier compared to standard rejection sampling. This proof calculates expected queries for both methods on a simple example.\n4. Proposition 2 shows that tokenwise rejection sampling doesn't sample from the restricted distribution. The proof provides a counterexample.", "experimental_designs_or_analyses": "1. The authors pretrain language models on synthetic data with controlled parameters, then test on out-of-distribution samples. They train lightweight verifiers on error cases and evaluate backtracking effectiveness. The design is sound, with proper controls and ablations on backtrack quota and stride length.\n2. The authors evaluate their method against multiple baselines across metrics of accuracy, diversity, and query complexity. They conduct comprehensive hyperparameter searches and ablation studies.", "relation_to_broader_scientific_literature": "1. Verifier-assisted generation relates to inference-time optimization methods like best-of-N sampling, and provides formal analysis of when and why verifiers help, moving beyond empirical scaling laws.\n2. The tokenwise rejection sampling with backtracking approach extends classical rejection sampling techniques with a process verifier, connecting to both statistical sampling methods and search algorithms like beam search", "essential_references_not_discussed": "The paper covers most essential related work.", "other_strengths_and_weaknesses": "Other Strengths:\n1. The paper bridges theoretical analysis and practical implementation, showing both mathematical proofs of complexity benefits and empirical evidence of performance gains.\n2. tokenwise rejection sampling with backtracking algorithm is relatively simple to implement, making it accessible for practical use while still providing significant benefits.\n3. The error analysis in Appendix B.1.3 offers valuable insights into why certain errors persist, which could guide future improvements.\n\nOther Weaknesses:\n\n1. The real-world experiments focus only on code generation (specifically test case generation), which may not fully demonstrate the method's applicability to other constrained generation tasks like mathematical reasoning or formal specification.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Have you explored how the approach performs when constraints are \"softer\" or probabilistic rather than binary?\n2. For the CodeLlama experiment, you focus on test case generation for simple list append functions. How do you expect the results to generalize to more complex programming tasks with deeper logical dependencies and constraints?", "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:

Meta-review: After reviewing the reviewers’ comments and the authors’ detailed rebuttal, I recommend the paper be accepted. The reviewers found the proposed theoretical framework for verifier-assisted language generation to be both rigorous and insightful, significantly advancing understanding of complexity considerations in constrained generation tasks. The paper compellingly demonstrates that verifier-assisted methods can transform computationally difficult problems into tractable ones, with clear and valuable theoretical results. Empirically, the use of tokenwise rejection sampling with backtracking offers strong support for the theoretical claims, showing notable improvements in accuracy, efficiency, and diversity over existing baselines. The authors were proactive in addressing reviewers’ concerns, providing additional experiments, clarifications, and references that strengthened both the theoretical and empirical aspects of the work. Minor concerns include the gap between theoretical assumptions—such as perfect verifiers—and practical implementations using trained, imperfect verifiers, though the authors adequately addressed these with further clarification and experiments. Reviewers also encouraged exploring extensions to probabilistic constraints and real-world tasks beyond structured code generation. Overall, the paper’s theoretical depth, empirical rigor, and thoughtful engagement with reviewer feedback clearly outweigh the minor concerns, and the contribution is recognized as a valuable advancement in the field of constrained language generation.
Decision: Accept (poster)