Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
Authors: Dhruv Rohatgi
Abhishek Shetty
Donya Saless
Yuchen Li
Ankur Moitra
Andrej Risteski
Dylan J Foster
Venue: ICLR 2026 Poster (2026)
Keywords: theory
reinforcement learning
sampling
process verifier
process reward
language model
LLM
value function
markov chain
Primary area: learning theory
TL;DR: We give an algorithm for value-guided generation that provably avoids error amplification with an imperfect process verifier.

Abstract: Test-time algorithms that combine the *generative* power of language models with *process verifiers* that assess the quality of partial generations offer a promising lever for eliciting new reasoning capabilities, but the algorithmic design space and computational scaling properties of such approaches are still opaque, and their benefits are far from apparent when one accounts for the cost of learning a high-quality verifier. Our starting point is the observation that seemingly benign errors in a learned verifier can lead to catastrophic failures for standard decoding techniques due to *error amplification* during the course of generation. We then ask: can this be improved with more sophisticated decoding strategies?

We introduce a new process-guided test-time sampling algorithm, VGB, which uses theoretically grounded *backtracking* to achieve *provably* better robustness to verifier errors. VGB interprets autoregressive generation as a random walk on a tree of partial completions, with transition probabilities guided by the process verifier and base model; crucially, backtracking occurs probabilistically. This process generalizes the seminal *Sinclair-Jerrum random walk* (Sinclair & Jerrum, 1989) from the literature on approximate counting and sampling in theoretical computer science, and a conceptual contribution of our work is to highlight parallels with this literature. Empirically, we demonstrate on both synthetic and real language modeling tasks that VGB outperforms baselines on a variety of metrics.

Published as a conference paper at ICLR 2026
TAMING IMPERFECT PROCESS VERIFIERS: A SAMPLING PERSPECTIVE ON BACKTRACKING
Dhruv Rohatgi
Abhishek Shetty MIT shettyemit...
Donya Saless TTIC
Yuchen Li
MIT
Google Research
drohatgièmite e..
donya@ttic.edu
yuchenl @iahenl4@almmeen cmu cdu
Ankur Moitra MIT moi tra@mitt.... edu
Andrej Risteski CMU ari aristesk@andrew. cmu. edu
Dylan J. Foster
Microsoft Research
dy..anfosteremiccrooofff
ABSTRACT
Test-time algorithms that combine the generative power of language models with process verifiers that assess the quality of partial generations offer a promising lever for eliciting new reasoning capabilities, but the algorithmic design space and computational scaling properties of such approaches are still opaque, and their benefits are far from apparent when one accounts for the cost of learning a high-quality verifier. Our starting point is the observation that seemingly benign errors learned verifier can lead to catastrophic failures for standard decoding techniques due to error amplification during the course of generation. We then ask: can this be improved with more sophisticated decoding strategies?
We introduce uses theoretically grounded backtracking to achieve provably better robustness to verifier errors. VGB interprets autoregressive generation as a random walk tree of partial generations, with transition probabilities guided by the process verifier and base model; crucially, backtracking occurs probabilistically. This process generalizes the seminal Sinclair- rundom walk (Sinclair & Jerrum, 1989) from the literature on approximate counting and sampling in theoretical computer science, and conceptual contribution of our work is to highlight parallels with this literature. Empirically, we demonstrate on both synthetic and real language modeling tasks that VGB outperforms baselines variety of metrics.
process-guided test-time sampling algorithm, VGB, which
INTRODUCTION
Test-time compute provides powerful lever for scaling and improving language models, driving substantial improvements in reasoning capabilities (Brown et al., 2024; Snell et al., 2024; Wu et al., 2024; OpenAL, 2024; DeepSeek-AI, 2025). At the heart of these advances lies a fundamental principle: combining the generative power of language models with verifiers that can evaluate and guide their outputs. Even simple approaches like best-of-N sampling, where a verifier selects the highest-scoring response from multiple candidates, can yield non-trivial performance gains (Brown et al., 2024). one has access to process verifier that can assess the quality partial generations, additional gains can be unlocked (Polu & Sutskever, 2020; Uesato et al., 2022; Lample et al., 2022; Lightman et al., 2024; Wang et al., 2024; a0d the space of possible algorithmic strategies becomes considerably broader and less well-understood.
Empirical generation methods that incorporate process verifiers range from simple token-wise reweighting (Yang Klein, 2021; Mudgal et al., 2024; Khanov et al., 2024; Rashid et al., 2024) to more complex strategies that expend additional parallel (Mudgal et al., 2024; Wang et al., 2025; Puri et al., 2025) or sequential (Botta et al., 2025) computation. Many of these strategies are implicitly trying to address the problem that process verifiers are imperfect; often, they are learned from data (Yang Klein, 2021: 1: Lightman et al., 2024; Wang et al., 2025), and therefore seem subject to the curse of horizon- folklore principle in many subcommunities of machine learning, including imitation learning (Ross& & Bagnell, 2010), model-based reinforcement learning (Janner et al., 2019), multi-hop reasoning (Jiang al., 2022), dynamical systems (Somalwar al., 2025), PDEs (Lippe

---

Published as a conference paper at ICLR 2026
et al., 2023; Molinaro et al., 2024), and language modelling (Bengio et al., 2015; Cundy & Ermon, 2024), that long horizons tend to amplify learning errors. Understanding the extent to which different strategies mitigate this issue- and designing better -eeeirrssss making this problem explicit: in what ways are learned process verifiers imperfect? And when-if ever-car can amplification of these imperfections during generation be algorithmically avoided?
In this paper, we propose a concrete model for imperfect process verifiers, in which we show error amplification can be algorithmically mitigated. To do so, we connect the above problem with the classical algorithmic toolkit for sampling-spedd (MCMC) technique from theoretical computer science that leverages opproximate counting oracles to do approximate sampling (Sinclair & Jerrum, 1989). This machinery lets us implement the empirical heuristic of backtracking (Botta al., 2025; Yang et al., 2025; von Rütte et al., 2025)-i.e. occasionally "erasing" generated tokens-an in a mathematically justified manner, and to establish rigorous guarantees for guiding generation with an imperfect process verifier. Broadly, we believe that perspectives from classical theory on design and analysis of Markov chains may bear additional fruits for language model reasoning, and we hope our paper will stimulate further work to connect these areas. See Appendix A for additional related work.
a Markov chain Monte Carlo
1.1 THE PROMISE: TEST-TIME TIME ALIGNMENT WITH VALUE FUNCTIONS
Let Teef X + (()) be a pre-trained language model (or base policy) that maps a prompt æ to a distribution over responses y = (./,...., WH) E y == A", where each is an action (either single token, or more generally, chunk of tokens). basic goal of both post-training and test-time interventions is to "align" Tref according to reward function r* X y + [0. Rnax), while maintaining the capabilities of the base policy. In post-training pipelines, this task is typically accomplished by learning the policy n² that maximizes KL-rreularized reward (Ziegler et al., 2019), which for a temperature parameter / >> 0 and fixed prompt æ is defined as
Ja(m; == E y~r((1 (x. B- DKL (T(- ax) || Wree(: [=))
Given prompt æ, the analogous test-time problem is to sample from (- I)) which has the form
n" (y x)) x Frer(y x)) Txx
where T(x,)) == cxp(8-'r"<x, y)) (Korbak et al., 2022; Geuter et al., 2025). For a general tilt function J X 3/ - R20. we call this problem test-time alignment: given sample access Tref- query access to т. and a fixed prompt x, how do we sample from the tilted distribution -² (- x) defined via Eq. (2)? This central algorithmic problem subsumes many natural tasks like constrained generation (Scholak et al., 2021), posterior inference (Zhao et al., 2024a; Puri et al., 2025), and test-time reinforcement learning (Foster al., 2025). Unfortunately, since the response space y is exponentially large, it can be computationally intractable without further information (see e.g. Proposition G.5 or Botta et (2025)).
True value functions mitigate computational intractability. While many formalizations of process verifiers have been explored in the literature (Lightman et al., 2024; Wang et al., 2024; 2025), arguably the most principled of these value functions. The (ground truth) value of partial response yı:A for prompt x is the conditional expectation!
Vinee (I,, V1:h) := EE [7(x, V1.H) Vrs1).
In the KL-regularized setting, Vin is closely related to the regularized value function Q (Zhou et al., 2025). In general, Vint enables exactly computing the next-action conditional probabilities of nt (Lemma F.5) and, thus, efficiently sampling from x* via autoregressive generation:
(yhh x. V1:h-1) x Tree(yn V1:-1) Vän (2, V1:h).
We call this method action-level rejection sampling with Vin see also Yang & Klein (2021).
We use the notation Vh: to avoid confusion with the optimal value function for the autoregressive MDP, which in this setting would be V (J(()))) max vh EAH & 7 (2z, V1:11)
2

---

Published as a conference paper at ICLR 2026
VGB Block Best-of-N
Block Rejection Sampling
140
Dietinct Correct
Distinet Corract
130-
V(a)
2.00
720
-20-
(ala(ala) Vi(aa
x Towr(bla
100-
.V(ab)
an
ab
VCB
VCB BlockitS Frantier
70-
02
D4
3.6
0.8
022 0.4
0.
3.0
Accuracy
Accuracy
Figure 1: Left/middle: Accuracy (x) and diversity (y) of VGB vs. Block Best-of-N and Block
Rejection Sampling on Dyck grammar task (Section 5.2) with pre-trained base model and trained value function. Each circle is baseline with specific hyperparameters (block length E {1, 2, 8, 16) and # of candidates E (2. 4, 8, 16, 32 darker red indicates larger block length. Right: Snippet of the generation tree on which VGB walks, with transition probabilities from "a" (self-loop not shown).
1.2 THE CHALLENGE: A TRUE VALUE FUNCTION IS HARD TO FIND
The preceding discussion paints an optimistic picture: given the value function Viite> test-time alignment be efficiently and exactly solved via action-level rejection sampling. But there is no free lunch: typically, the task of evaluating Vun is itself computationally intractable. In practice, it is more common to use some heuristic progress metrie (Khanov et al., 2024; Loula et al., 2025) to learn an approximation to Virt- A popular recent approach is to an approximate value function 4 through regression on Monte-Carlo rollouts (Yang & Klein, 2021; Mudgal et al., 2024; Chakraborty et al., 2024; Setlur et al., 2025; Wang et al., 2025), solving some variant of the program
V arg min E (V U1ah) (1r b1:H)) VEV
which theoretically converges Vün in the well-specified large-sample limit, but in practice will incur errors due to misspecification, optimization bottlenecks, and finite samples. How do we design algorithms that mitigate amplification of these errors across long horizons?
1.3 OUR CONTRIBUTIONS
Pitfalls of naive action-level sampling (Section 3). As starting point, we theoretically demon- strate that when all we have is an approximate value function, action-level rejection sampling is no longer the right alignment algorithm: even in the presence of evidently benign errors in the approxi- mate value function V. (Examples 3.1 and 3.2), action-level rejection sampling with V amplifies these errors, degrading catastrophically with long generations. Other common process-guides algorithms such as beam search (Wang et al., 2025) are also insufficient even without errors (Appendix C).
new value-guided alignment strategy: VGB (Section 4). We introduce VGB, simple one-line modification to action-level rejection sampling that provably mitigates error amplification for broad class of value function errors- entirely avoiding degradation in the generation length-through backtracking. VGB interprets the space of possible responses to a prompt as a tree (with internal nodes as partial responses) and casts generation as a random walk on the tree (Figure 1), which stochastically adds actions or backtracks, guided by the value function and base model-and is designed so that the stationary distribution of the random walk exactly proportional to x at the leaves of the tree, even with imperfect value estimates at internal nodes.
On a technical level, VGB can be viewed as a generalization of the seminal Sinclair-Jerrum random walk (Sinclair & Jerrum, 1989), tool originally developed in the approximate sampling community of theoretical computer science. core conceptual contribution of our work is to highlight parallels between test-time alignment and approximate sampling and counting, opening the door for further transfer of ideas. Beyond showing that the Sinclair-Jerrum walk adapts to test-time alignment, a key technical contribution of work is establish correctness of the algorithm in the presence of average-case errors more akin to standard assumptions from statistical learning ueoory-using modern techniques such local mixing (Liu al., 2024b).
Empirical results (Section 5). We evaluate VGB with a trained value function V' on Dyck grammar generation, Python test case generation, and several instructive synthetic tasks. We find that VGB
3

---

Published as a conference paper at ICLR 2026
outperforms naive sampling strategies variety of axes measuring distributional aceuracy. Also, in the classical constrained text generation setting where there is no trained value function, VGB produces more coherent generations than the predominant algorithm (Scholak al., 2021). Our empirical results corrohorate our theoretical thesis that VGB mitigates error amplification.
2 PRELIMINARIES
General framework: Test-time alignment. Fix sets X' and y == AA Let Teef X + A()) be base model. Let X' x y/ - Ryo be a tilt function, and let V XXx A" Ry0 be an approximate value function (in subsequent sections, we will make assumptions about how V relates to the true value function ViLie defined in Eq. (3)). We assume that, for any X, h E [H] and Fich E Ah, we can (1) sample from the conditional distribution Trer(- x; v1.--), (2) query the density (ver(Un x, 11) and (3) query VI.11.)). We discuss both the setting where is known (in which case we set (zz y1. == T (ax, v1.H)) )) and the setting where unknown. Given z E X,
our primary goal is to sample from a distribution close to T" 2:) as defined in Eq. (2).
Special case: -l.rregllarized optimization. Suppose T(I, y) x exp($-1r" y)) for some
reward function r- X' - [0, Rnax] and temperature parameter 0. Given X, the goal of KL-regularized optimization is to sample from a distribution T(- x) with low KL-regularized
regret ( x) (T; (see Eq. (I)). Since =x(= (g( 3D (TT(- |x) [e)[((( (- xx))
In this setting, we have that Vinee (2. 81:1) = exp(8 Qz(2, V1sk)) where Q3 is the regularized value function (see Appendix F.2).
(Lemma F.4), this goal is equivalent to approximate sampling.
Special case: Constrained sampling. In this particularly common setting, T(x, v) = rx v) for some binary-valued reward function r" X x y + {0, 1). so x is conditional distribution (Yang & Klein, 2021; Scholak et al., 2021; Lew et al., 2023; Wang et al., 2025).
2.1 BASELINE ALGORIHTM FOR TEST-TIME ALIGNMENT
Outcome-level rejection sampling with т. Given prompt z, the algorithm OutcomeLeveIRR repeatedly draws yı:H Tref(- x)) and accepts with probability proportional to 7(x, V1:H).
Action-level rejection sampling with V. Given prompt x, the algorithm Action autore- gressively samples y1, V/.-. , Vrr for each h [H], after sampling //1h- uses rejection sampling to sample yr. from the distribution defined by Mn (yn. x (yh 2, (1.h-1) )) V (z, V1..).
See Appendix G for formal pseudocode and analyses. Outcomel eve is an exact sampler for x² (and doesn't 't need 2 but its runtime scales with the sequence-level coverage coefficient Csea (I) maxyey ( (y #ryrrer(y r)) When V = Vilt ActionLeveRRS also exact, and has runtime H)) where (act(x)) == maxs.y1.. π (yr x, (1.hhhh1)) Tref (Vr, x, Wi:h-- is the action- level coverage coefficient.' We always have (x)t(x) S Cueq (x), but one can have (x)q 2 2 even (z))(z) < 2, so ActionLevelRS can be exponentially more efficient than OutcomeLevelRs..
Remark 2.1 (Sampling vs reward maximization), As discussed in Section eration as a sampling problem, not a pure search/reward maximization problem, and thus largely consider sampling baselines. This framing is motivated by similar considerations in post-training (Ziegler et al., 2019), applications to constrained sampling (Scholak et al., 2021; Yang & Klein, 2021; Botta al., 2025), and empirical evidence that sampling is a more robust formalism for exploiting imperfect process verifiers (Puri et al., 2025).
cast guided gen-
3 PITFALLS OF ACTION-LEVEL SAMPLING
Unfortunately, the computational benefits of ActionLeve may not be realized in the presence of estimation errors. Suppose that have access an approximate value function V that is accurate (i up to some multiplicative error + Ev: Vita (x.
E [1/(1 + Ev), + ev]. The following
2 Mooe precisely, it can achieve approximation error in time (llog(1/e) (ee))_see Appendix G. 'When [A] is small, one can explicitly sample from μ4 in time [A], for overall time complexity of O(IA) See Sctlur al. (2025); Botta et al. (2025) for similar observations.
4

---

Published as a conference paper at ICLR 2026
Algorithm VGB: Value-Guided Sampling with Stochastic Backtracking (illustration in Figure 21)
Input: base model Tref appx. value function V. prompt æ E X, horizon H E N, step count T e N.
1: If outcome-level reward/tilt is available, set (1x, VI.H) T (2, MI:H).
2: Initialize y := Ø.
3: for 0 t < T do
4: Set = |. and define pd* as the distribution over neighborhood (11 of Vich where
vinh if > 0, if h 0,
Backtracking probability
pd (winh1))
and for each yh+1 E A,,
p (Vish yh+1) Tret (Ter ar, with Vaz vith Mh+1) if H.
if H,
5: With probability 1/2, set yu1h nh else sample y pl0. 6: return y (Thm. 4.1) or y for Unif([T)) (Thm. 4.2).
See Remark 4.1. // For analysis only.
didactic example shows that even for small Ey o(1), ActionLevelRS can fail entirely (unless Ey is inverse-poff poryes-aplnooiill in the sequence length H). See Appendix H.1 for more details."
Example 3.1 (Failure of ActionLevelRS under perturbation). Fix Ev (0,1) and N. Ler X = {LL (henceforth omitted from notation) and action space A == {a. b, c). Let Uni 6, H) and T(y:-)) = I[c & y. Then V(ne(() = (2/3) H -- & minn). Let a} + (ine(Min)) # a). Then the output distribution रे of ActionL evelRS satisfies DTv(R, 2 ((min(evVH..1)
us define V (yI.)) = (1 + (inn)(nn
Example 3.1 shows seemingly benign perturbations to the estimated value function v can com- pound during the execution of pectionLevelle While it is tempting to imagine that this might be fundamental limitation (i.e., the approximate value simply doesn't i contain enough information meaningfully guide the sampling process), we will see in Section 4 that this is not the case.
We give second example in the language of the KL-regularized setting, which demonstrates that ectionLever can suffer ?(1) KL-regularized regret even when there are no "perturbations" in but but it is simply delayed step compared to the truth. See Appendix H.1 for more details.
Example 3.2 (Failure of ActionL under delay). Let = {T} (omitted from notation) and A: {0, 10, Let Tref == )ni", 3 = 1/H1 and r" (211 ))= = म E so that π +"(..)) x exp(Eii yn) and, via Eq. (3), Vin Vinx(1))) = ( H-h exp (E vk). We define V by delaying the true value function by one step: (yv:*k) Vūne (11:h-1), which satisfies Ey := 1. Since (yra) does not depend on yhu ActionLevelRS samples from the uniform distribution के Trefi which has JØ(T²) Jz( DKu x*) To
Example 3.2 is a negative result for ActionLevelRS, but also hints at an algorithmic intervention:
(xx v1sk) gives no guidance in selecting yh., but can help detect whether the previous action Vh-1 was good bad. Can we improve ActionLevelRS by propagating information backwards?
4 TAMING IMPERFECT PROCESS VERIFIERS: STOCHASTIC BACKTRACKING
We now present value- value-guided sampling algorithm, VGB, that provably mitigates amplification through a principled stochastic backtracking strategy. We first describe the algorithm and motivation (Section 4.1,, then provide theoretical guarantees (Sections 4.2 and 4.3).
5

---

Published as a conference paper at ICLR 2026
4.1 MAIN ALGORITHM: VGB
Our main algorithm, VGB, is displayed in Algorithm 1. To explain the algorithm, we view guided sampling algorithms as implicitly traversing the exponentially-large tree T with node set Uh=o-A, where 91:h-1 is the parent of y1:A- ActionLevelRS implements a random walk from the root Ø to a leaf M1.H. which only goes down the tree. As we saw in Example 3.2, such strategies seem limited in their ability to correct for systematic errors in the value function estimates.
VGB as a one-line change to ActionLeveIRS. VGB addresses the limitations of ActionLeveIRS by augmenting the random walk with the ability to backtrack up the tree. Formally, let NV (V1.h) denote the neighborhood of Vich in T. which contains its parent V1:h-1 and all its children [31:1+] (
VGB now proceeds as follows. At each step t, given the current node yi.h- we first (Line 4) define a probability distribution pl*) over the neighborhood N (yyh)) ). The probability of selecting child node (with 1h++1 is proportional Feee (1/++1 | 3r, vi.i (2r, with Mo+1)-just as in (0) Vish-1 is proportional to V(z, vile)-
the probability of selecting the parent The random walk proceeds by sampling a new node y from pd with probability 1/2, and staying at the current node otherwise (setting y(c +- - After T steps, in the version of VGB that analyze first, it returns the final node of the random walk.?
Act seriioneveelss-v
VGB as a generalization of the Sinclair-Jerrume walk. VGB can be interpreted as a generalization of the Sinclair-Jerrum walk (Sinclair & Jerrum, 1989), which corresponds to the special case where Tref is uniform and r is binary-valued." This walk was originally used to show that approximate sampling reduces to approximate counting in self-redueible problems such as SAT, without incurring the error amplification of prior reductions (Jerrum et al., 1986). Value functions are precisely the generalization of counting oracles to our setting.
Under Assumption 4.1 on V. stated below, VGB inherits three key properties from the Sinclair-Jerrum walk, formalized in Theorem 4.1: (1) the walk rapidly mixes stationary distribution 7; (2) puts (21/H) mass on the leaves of Ti; and (3) as long as exact outcome-level rewards are used (i.e. VIr, v1.H) = T (1r, )) ); see Remark 4.2), म. is proportional to " at the leaves.
Remark 4.1 (Efficient implementation for large action spaces). When the action space A small (e.g.. in token-level generation), the distribution p in Line 5 of VGB can be constructed explicitly by enumerating all actions. When the action space is large (e.g.. in block-level generation), this enumeration is compulationally infeasible, but we can still sample efficiently from pd) using rejection sampling (in time O(Cact (z))-ses Theorem 4.1). See Algorithm 8 for the detailed implementation.
4.2 THEORETICAL GUARANTEES: UNIFORM ERROR
We present the first of our theoretical guarantees for VGB-th the strongest and simplest-unde under the assumption that the learned value function V satisfics a uniform error bound with respect to the true value function Vi (as discussed in Section 3), and that have query access the outcome-level reward r; we will relax both assumptions in the sequel. The assumption is for a fixed prompt x E X':
Assumption 4.1 (Uniform bound on value errors). We assume that the exact outcome-level reward is available (i.e, (ax y1.H)) T(x, yr.H)), and for each S < H. for each yı:h E A
(Z,Vis) +5/(1+5v),11 [ (1,
(5)
Under this assumption, we show that VGB rapidly converges to the target distribution x². The proof closely follows the analysis of the Sinclair-Jerrum walk (Sinclair & Jerrum, 1989), which bounds the mixing time of the walk by analyzing its conductance. See Appendix for the full proof.
We remark that Example 3.1 also has analogue in the KL-regularized setting; see Example H. "This technique (staying at the current node with probability 1/2) is called laziness, and needed to ensure that the random walk has a stationary distribution. See e.g. Levin et al. (2009) for background on Markov chains.
The chosen node may not he a leaf, which case we re-run the algorithm; this can occur at most ((H)
times.
See Bakshi al. (2024) for related generalization, applied quantum Gibbs state preparation.

---

Published as a conference paper at ICLR 2026
Algorithm 2 Instantiation of VGB for KL-regularized reinforcement learning
1: Input: Base model Trefi approximate regularized value function Q prompt E &,, horizon E N,
regularization parameter / > 0, step count T E N.
2: If nutcome-level reward is available, set Q(2, v1.H) r" (2,
3: Initialize y ;= Ø.
4: for 0 < T
5: Set h == / and define pd as the distribution over neighborhood (V of yith where
n (wi Texp(x (x.,)))) if
Backtracking probability
if h O,
and for each 1h++1 A,
Tror(un+1 1 1r wish) exp(8 (10 With Vh+1))
if H, if H.
p ( 11++) x (0
With probability 1/2, set yuth := yd), clse sample ((t p()
See Remark 4. // For analysis only.
7: return n (Thm. 4.1) or yd for (nT]( (Thm. 4.2).
Theorem 4.1 (Main guarantee for VGB). For any prompt x E X and ó > 0, under Assumption 4.1, let के be the output distribution of VGB with step count
T = Ō( (v) (1+e))-.oo((0-))
and let Exeat be the event that ~ 7 is a leaf node. Then P(εret) 2 1/(8(1 + H)) and the error conditioned this event isDTu(Fleu) T²) S 8. The total runtime (including evaluations of V and queries/conditioall generations of Tref) ) bounded by -(IA)-T) in the small-action case and Ō(Cact(z)) -T' in the large-action case."
In the KL-regularized setting, achieve an analogous bound on regret-namely, Ja(T*; Ja (a S 35; see Corollary 1.1 for the full statement. While these guarantees are conditioned on the event Exeaf- we can ensure that this occurs with high probability by simply rerunning the algorithm Õ(H) times. Compared to ActionLevelRS, VGB avoids the error amplification demonstrated in Examples 3.1 and 3.2, because these examples satisfy gy O(1). Compared to LiccomeLevelRRe VGB is much more efficient: it avoids dependence on the sequence-level coverage coefficient Czea (æ), which should be thought of as potentially exponential in H.
To be clear, there is room for improvement, as the overall time required for VGB to output a leaf node is Ō(H)).
Remark 4.2 (Access to outcome-level tilt r). When VGB has exact access T, output distribution (conditioned on Eleat) converges to n² as + 0, evenfor fixed value error εy- Without such access, convergence x* is impossible, but VGB still provably avoids error amplification, as shown below.
4.3 GUARANTEES UNDER WEAKER AVERAGE- EVERAGE-CASE ERROR
Theorem 4.1 shows that VGB can significantly improve over naive sampling in the presence of value function errors, but the result requires the uniform error condition Assumption 4.1. Such worst-case bounds may not hold for value functions derived from standard learning techniques like Monte Carlo estimation. To address this, we present a more refined analysis of VGB under a weaker, average-case assumption. We also drop the assumption that is known.
Assumption 4.2 (Average-case bound on value errors). We assume that for each h E (H),
(1sh (x, V1:A)
(anl(,V1sh) Viskk)
E Biih - (-Ix)
$ <1+EV,
5 51 +1+ Ev.
(6)
BIANT (-1z)
Vaa, (1.h))
This case requires (approximate) knowledge of Cuce (x) and EV; Remark I.1.
7

---

Published as a conference paper at ICLR 2026
In the KL-regularized settiig this condition controls the moment generating function under 'T of the error (3 y1*h) (xr, Viss), where Q(2,, V1:A) := Blog Var, V1:s)- While still requiring control over tail behavior, this significantly relaxes Assumption 4.1, which corresponds to a uniform bound on that error. Similar conditions have been studied in Aminian et al. (2025); Yang & Wibisono (2022).
Under this weaker assumption, VGB still provides strong guarantees, though of different nature than Theorem 4.1. Instead of a direct bound on suboptimality, we show VGB provides good coverage (Huang et al.. 2025b; Foster al., 2025) of typical responses from the target policy n²:
Theorem 4.2. For any prompt E X and 5 >> O, under Assumption 4.2, the runtime of VGB with step count T == Õ(H² (1 + Ev)o 5-1) is O [A)), and the output distribution ft satisfies
x (v1.H x) #(11H)
48H(1 + + S 6.
Pr (
8
That is, with high probability over V1.H ~ (. [)), the policy ß induced by VGB assigns y1:H not much less probability than x". This guarantee does not directly imply low regularized regret in the KL-rregularized setting; however, it does enable achieving low unregularized regret against n", by composing VGB with standard Best-of-N sampling (Cobbe et al., 2021); see Appendix B. We remark that in Examples 3.1 and 3.2, ActionLevelRS does not achieve Eq. (7) (see Appendix H.1).
Overview of analysis. The analysis of VGB under the average-case error assumption in Assump- tion 4.2 is considerably more challenging than in the uniform error setting. Classical techniques such global conductance are longer applicable. Instead, our analysis leverages modern tools for analyzing slowly mixing Markov chains, particularly the notion of local stationarity (Liu et al., 2024b). We view this analysis key technical contribution, as it bridges the average-case guar- antees typical in statistical learning theory with the uniform guarantees traditionally required in the analysis of approximate counting and sampling algorithms. We defer the full proof to Appendix I.4.
Insufficiency of alternative assumptions. We show that several alternative assumptions (which a priori may seem more natural than Assumption 4.2) are insufficient for any efficient algorithm to achieve non-tri non-trivial sampling guarantees: average-case multiplicative error under Trer (Appendix D.1), additive error bounds on V (Appendix D.2), and MSE bounds on Q (Appendix D.3).
EMPIRICAL RESULTS
Our experiments focus on constrained -erpaing--eehaps the most common, concrete application of test-time alignment (Yang & Klein, 2021; Scholak et al., 2021; Lew et al., 2023; Wang et al., 2025) where T := r" is binary-valued reward function. We train value functions for tasks where rrer is analytic (Section 5.1) or pre-trained language model (Section 5.2), and demonstrate benefits of VGB on a variety of axes measuring distributional fidelity. We also show that constrained text generation (Scholak et al., 2021) can be interpreted as value-guided sampling with weak value function- and that VGB improves coherence compared to the standard baseline for this setting (Section 5.3). These benefits largely do come at added computational cost, but we view our findings as promising step towards understanding trade-offs between efficiency and error mitigation-an therefore a step towards reliable sonn-horizon reasoning. For all omitted experiment details, and additional results (e.g. improving the efficiency of VGB with momentum), see Appendix E.
Implementation details. The value functions are parametrized as MLPs-where the input features are either one-hot encodings of the input sequence (for tasks with small [AA) or pooled hidden states from the pre-trained language model (for tasks with large [A))-and and trained via regression onto Monte Carlo roll-outs (Eq. (4)). To improve wall-clock efficiency, the implementation of VGB differs two ways from Algorithm 1. First, instead of fixing a step count T' we simply stop the Markov chain as soon as it reaches leaf. Second, in settings where the alphabet is too large to efficiently enumerate, use heuristic version of rejection sampling implement each transition. In experiments where the true rewards are provided at the final position, we allow ActionLevelRS to restart if all actions have reward 0. See Appendix E for pseudocode and task-by-task implementationn/raiinng details.
8

---

Published as a conference paper at ICLR 2026
N 500
Error (KL-di (iL-eiivergenee
N
1000
Error (KL (iL-divergence)
10000
Error (KL- [KL-divergence
ActionLevel
0.8
ActionLevel
0.12
ActionLevel
VGB
VGB
VGB
0.6
0.10
0.4
0.08
0.06
10
10
10
Horizon length (H)
Horlzon length (H)
Horizon length (H)
Figure 2: Estimated Kl--divergence of VGB and Act ActionLeveIRS to n² in ABC task (Section 5.1) for
varied horizon length and # of value function training samples N. We repeat the experiment 10
times for each N) and report the mean and standard error. See Appendix E.2 for details.
Eval (normalizedd log-prob
3.2
VGB
Actionlevel
0.55
-3.3
Winrate
-3.4
-3.5
0.45
Levil
-3.6
VGB
-3.7
0.15 0.20 0.25 0.30 0.55 0.40 0.45
0.10
0.30 0.35 0.40 0.45
Backtracking weight for VGB (a)
Backtracking weight for VGB (a)
Figure 3: Comparison of VGB against ActionLevelRS for letter avoidance task (Section 5.3), with varied backtracking weight a for VGB. Left: Winrate of VGB against ActionLevelRR under pair- wise comparison of responses by GPT-4o-mini (judging for coherence). Right: Average horizon-
normalized log- bog-robaabilitiss evaluated by Qwen-2.5-1 5-1.5B See Appendix E.6 for details.
5.1 SYNTHETIC GENERATOR WITH TRAINED VALUE FUNCTION
Our first tasks are synthetic tasks that we use to stress-test the theory; the base distribution Tref is analytic rather than defined by a pre-trained language model, and the problem instances small enough that we can easily compute relevant metrics, but the value functions are trained via Eq. (4).
ABC task (Appendix E.2): distributional benefits. We follow the task defined in Example 3.1, where proved that errors in specific V compound with ActionLevelRS, whereas VGB provably avoids this error compounding. We show that the benefits of VGB persist when V trained. We implement VGB and Act inn innieoeeeess using the true rewards at the final position, so both algorithms produce only reward-1 responses, but may have biased distributions. As shown in Figure VGB incurs lower KL-divergence to x* than Act ActionLevsRRs, with increasing benefits for large H.
The following task provides a setting where systematic training errors arise (a Example 3.2) and induce an even starker separation between VGB and ActionLevelRS.
Parity task (Appendix E.3): wall-clock time benefits. This task instantiates common intuition that estimating values may often be much harder at some positions than at others (Li et al., 2024). Specifically, we design Fref and r" so that many positions h, (ita)) is parity function- which is notoriously challenging for gradient descent to learn (Barak et al., 2022)-but many other positions "reveal" the most recent parity. Intuitively, this effectuates delayed feedback the trained value function, in Example 3.2. Indeed, this task, VGB requires less wall-clock time than ActionLeveIRS to find reward-1 response, with superior scaling as H increases (Figure 6).
5.2 LANGUAGE MODEL GENERATOR WITH TRAINED VALUE FUNCTION
We now turn to tasks where Traf is Transformer- language model. In these tasks, while it infeasible to empirically estimate KL-divergence as before (due to larger response space), we demonstrate that VGB has benefits over baselines according to natural subjective metrics.
10We have not sought to optimize the polynomial dependence on H. Also, for this result, omit analysis of the large- [A] case; Remark 1.2 for discussion.

---

Published as a conference paper at ICLR 2026
Dyck grammar task (Appendix E.4). The Dyck grammar (Schüttzeberrger, 1963) is a classic context-free freextt-eeeeeeeeee grammar consisting of balanced parenthesis strings (e.g. [O] is valid but ([)] is not), and a common theoretical sandbox for language modeling (Hewitt et al., 2020; Yao et al., 2021; Liu et al., 2023b;a; Wen et al., 2023; Botta et al., 2025). Using code from Botta et al. (2025), we train (from seratch) Transformer language model ref Dyek grammar sequences of length 32 with two bracket types. The training data is sampled from a distribution where square brackets [ and occur with probability 0.8 whereas round brackets andd) ) occur with probability 0.2. While Tref has near-perfee pear-perfect accuracy at completing in-distribution prefixes, it has much worse accuracy at completing
(OOD) prefixes, i.e. prefixes with many round brackets.
First, we fix randomly- chosen length- 16 prefix consisting of only round brackets, and train a value function for 40 epochs on 10000 completions from Tref- We compare VGB on two accurryy two popular sampling algorithms: Block Best-of-
and diversity (i.e. # of correct responses)-agallle N (Mudgal et al., 2024) and Block Rejection Sampling (a generalization of ActionLevelRS) We sweep over block sizes and number of candidate blocks, allowing up to 32 candidate blocks-which equalizes the number of queries to Tref made by VGB and the baselines (Table 1). VGB achieves a robustly non-dominated point the Pareto frontier between accuracy and diversity (Figure 1).
Second, on 12 OOD prefixes, we measure how well VGB and ActionLeveRRS match x* in distribution, using tractable proxy for distributional error. True rewards are used at the final position, and the value function is trained for a varied number of epochs. After initial epochs, VGB achieves lower & error than ActionLevelRS while being more query-efficient than OutcomeLeveIRs (Figure 12).
Code generation task (Appendix E.5). In this task, the goal is to generate a valid test case for randomly-named Python function that implements append and given the prompt (Botta et al., 2025). With base model Qwen-2. 5-0. 5B, a trained value function V, and true rewards at the final position, we evaluate VGB and ActionLevelRS against x* on three distributional metrics: (1) the histogram of test case lengths, (2) the distribution of object types in the test cases, and (3) the number of distinct test cases generated. We find that VGB substantially improves upon ActionLevelRS for (1,, and is comparable for (2) and (3); see Table 3 for full results and discussion.
5.3 CONSTRAINED TEXT GENERATION
In our final experiment, we demonstrate that VGB can be gainfully applied even without training a value function. In many applications of constrained sampling, the reward function y* itself is used as a process verifier (Shin et al., 2021; Scholak et al., 2021; Poesia et al., 2022; Lipkin et al., 2025). The dominant algorithm is locally constrained decoding (Scholak al., 2021), which is precisely ActionLevelRS with V x r* Recent works have observed that this algorithm does not sample from r (Lew et al., 2023; Park et al., 2024), and correcting this bias is an active research area.
Letter avoidance task (Appendix E.6). In this task, the goal is to generate an English sentence with H 32 tokens that does not use the letter "e"., We use base model Qwen-2. 5B and approximate value function (H1+) == a (21:s)))))))) for varied a (0, 1). Intuitively, good choice of should roughly represent the "average probability that Tref errs at an average position"; the choice of effectively controls the backtracking probability of VGB, but irrelevant to ActionLevelRS (it is equivalent to locally constrained decoding regardless of a). We show that across a broad range of a, VGB achieves superior coherence and log-probasilities to ActionLevelRS (Figure 3).
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
We view our work as fundamental research guiding Large Language Models (LLMs). While LLMs have capacity for harm, we believe that guided generation will ultimately be an important part of the toolkit for aligning LLM behaviors towards societal interests-and, therefore, that the benefits of this research outweigh potential harms.
REPRODUCIBILITY STATEMENT
We provide full proofs for all theoretical results in the appendix. We also provide our code in the supplementary material, along with extensive implementation details for all experimental results in Appendix E.
REFERENCES
Kareem Ahmed, Kai- Chang, and Guy Van den Broeck. Controllable generation via locally constrained resampling. The Thirteenth International Conference on Learning Representations, 2025. URL http://pppeeeeeeeeeeeeoooor/r/me nett/ForrummdddBBBggCCCCC
Gholamali Aminian, Idan Shenfeld, Amir R Asadi, Ahmad Beirami, and Youssef Mroueh. Best-of-n through the smoothing lens: Kl divergence and regret analysis. arXiv preprint arXiv:2507.05113, 2025.
Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. High-temperature gibbs states are unentangled and efficiently preparable. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1027-1036. IEEE, 2024.
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards theory of non-log-concan concavee sampling: first-order stationarity guarantees for langevin monte carlo. In Conference on Learning Theory, pp. 2896-2923. PMLR, 2022.
Maria-Florina Balcan, Avrim Blum, Zhiyuan Li, and Dravyansh Sharma. On learning verifiers for chain-of-thought reasoning. arXiv preprint Frxiiv2505.226500 2025.
Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang, Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750-211 217644, 2022.
Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. Scheduled sampling for sequence prediction with recurrent neural networks. Advances in neural information processing systems, 28, 2015.
Edoardo Botta, Yuchen Li, Aashay Mehta, Jordan T. Ash, Cyril Zhang, and Andrej Risteski. On the query complexity verifier-assisted language generation. In Forty-second International Confer- ence on Machine Learning, 2025. URL https://openreve
net/ /tt.:/ormmiiddoIoiaaaaa
Bradley Brown, Jordan Juravsky. Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv:2407.21787 2024.
Joan Bruna and Jiequn Han. Posterior sampling with denoising oracles via tilted transport. arXiv preprint arXiv:2407.00745 2024.
Antoine Chaffin, Vincent Claveau, and Ewa Kijak. Ppl-mets: Constrained textual generation through discriminator-guide mets decoding. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2953-2967, 2022.
Souradip Chakraborty, Soumya Suvra Ghosal, Ming Yin, Dinesh Manocha, Mengdi Wang, Am- rit Singh Bedi, and Furong Huang. Transfer q q-star: Principled decoding for Ilm alignment. Advances in Neural Information Processing Systems, 37:101225-101766 2024.
11

---

Published as a conference paper at ICLR 2026
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchiro Nakano, et al. Training verifiers to solve math word problems. arXtv:2110.14168. 2021.
Chris Cundy and Stefano Ermon. Sequencematch: Imitation learning for autoregressive sequence modelling with backtracking. In The Twelfth International Conference Learning Representations, 2024. URL http://veeeerreee....o. www.e/reereeeeeeeeooouummu
DeepSeek-AL. DeepSeck-RI: Incentivizing Reasoning Capability in LLMs via Reinforcement Learn- httpa///ewebbbbbbb/ae//eeeeeeeee
ing. 2025. URL httpt::/ttthhhtht com/ pdf.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-877 8794, 2021.
Dylan Foster, Zakaria Mhammedi, and Dhruv Rohatgi. a good foundation necessary for efficient reinforcement learning? the computational role of the base model in exploration. Conference Learning Theory (COLT), 2025.
Jonathan Geuter, Youssef Mrouch, and David Alvarez-Melis. Guided speculative inference for efficient test-time alignment of llms. arXiv preprint arXiv:2506.04115 2025.
Emmanuel Anaya Gonzalez, Sairam Vaidya, Kanghee Park, Ruyi Ji, Taylor Berg- wing-Kirkpatrick, and Loris Antoni. Constrained sampling for language models should be easy: An meme perspective. arXiv preprint arXiv:2506.0577 2025.
Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong. Zhen Wang, Daisy Wang, and Zhiting Hu. Reasoning with language model is planning with world model. In Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing, pp. 8154-8173, 2023.
Thomas P Hayes and Alistair Sinclair. Liftings of tree-structured markov chains. In International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 602-616. Springer, 2010.
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. RNNs can generate bounded hierarchical languages with optimal memory. In Proceedings of the 2020
Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9978-2010, Online, November 2020. Association for Computational Linguistics. doi: emnlp-main. 156. URL https: /www. aclweb. org/ httgg/nhhlllgyyyee0 2020 emp.:mmmmml.mmm...mm 156.
Jonathan Ho and Tim Salimans. Classifier-free diffusion guidance. In NeuriPS 202/ Workshop Deep Generative Models and Downstream Applications, 2021. URL Forum?id=qwBAAxFYY0
Audrey Huang, Adam Block, Dylan Foster, Dhruv Rohatgi, Cyril Zhang, Max Simchowitz, Jor- dan T Ash, and Akshay Krishnamurthy. Self- seff-improvement in language models: The sharpening mechanism. International Conference on Learning Representations (ICLR), 2025a.
Audrey Huang, Adam Block, Qinghua Liu, Nan Jiang, Akshay Krishnamurthy, and Dylan J Foster. Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment. International Conference Machine Learning (ICML), 2025b.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32, 2019.
Mark Jerrum and Alistair Sinclair. Conductance and the rapid mixing property for markov chains: the approximation of permanent resolved. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 235-244, 1988.
Mark Jerrum, Leslie G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43(2-3):169 16:1691188 1986. doi: 10. 1016/ 0304-3975(86901724 X4-X.
12

---

Published as a conference paper at ICLR 2026
Zeyu Jia, Alexander Rakhlin, and Tengyang Xie. Do need to verify step by step? rethinking process supervision from a theoretical perspective. In Forty-second International Conference on Machine Learning, 2025. URL
Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. Understanding and improving zero-shot multi-hop -hop reasoning in generative question answering. In Proceedings of the 29th International Conference Computational Linguistics, pp. 1765-1775, 2022.
Maxim Khanov, Jirayu Burapacheep, and Yixuan Li. ARGS: Alignment as reward- reward-guided search. In The Twelfth International Conference on Learning Representations, 2024. URL https:// openreview
Tomasz Korbak, Ethan Perez, and Christopher L. Buckley. RI with kl penalties is better viewed as bayesian inference. In EMNLP (Findings), pp. 1083-1091, 2022. URL https:///oft /ttt::://do..or/////. 18653/v1 /2022. findininnnninnee
Guillaume Lample. Timothee Lacroix, Maric-Anne Lachaux, Aurelien Rodriguez, Amaury Hayat, Thibaut Lavril, Gabriel Ebner, and Xavier Martinet. Hypertree proof search for neural theorem proving. Advances in neural information processing systems, 35:26337-26344 2022.
David A Levin, Yuval Peres, and Elizabeth L Wilmer. Markov chains and mixing times, volume 107. American Mathematical Soc., 2009.
Alexander K. Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash Mansinghka. Sequential monte carlo steering of large language models using probabilistic programs. In ICML 2023 Workshop: Sampling and Optimization in Discrete Space, 2023. URL https::/ wttpi/wwwwe//oouurmn/.. id=x12Ke
Bolian Li, Yifan Wang, Anamika Lochab, Ananth Grama, and Ruqi Zhang. Cascade reward sampling for efficient decoding-time alignment. arXiv preprint arXiv:2406. 16306, 2024.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Proceedings of the 61st Annual Meeting the Association for Computational Linguistics (Volume Long Papers), pp. 5315-5333, 2023.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024. URI. http:: /oppse///eeeeeeee...oooo net/ dorum?id=v@L@@pNEO0L
Benjamin Lipkin, Benjamin LeBrun, Jacob Hoover Vigly, João Loula, David R. MacIver, Li Du, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Timothy O' Donnell, Alexander K. Lew, and Tim Vieira. Fast controlled generation from language models with adaptive weighted rejection sampling. CoRR, abs/2504.05410, April 2025. URL h/top: org/ 10. 48550 arvi 2504.054144
Phillip Lippe, Bas Veeling, Paris Perdikaris, Richard Turner, and Johannes Brandstetter. Pde- refiner: Achieving accurate long rollouts with neural pde solvers. Advances in Neural Information Processing Systems, 36:67398-6767 2023.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference Learning Representations, 2023a. URL httph::////ooo /ttp:::////pppeveeeeeee net hett/Forummidddee4Fffffuee
Hong Liu, Sang Michael Xie, Zhiyuan Li, and Tengyu Ma. Same pre-training loss, better downstream: Implicit bias matters for language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 22188-22214, PMLR, 23-29 Jul 2023b. URL https: : http///pooeeeeeeeee/ee/e/oo/.ese mlr. press/ v202/1iu23ao, html.
13

---

Published as a conference paper at ICLR 2026
Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannanch Hajishirzi, and Asli Celikyilmaz. Don't t throw away your value model! generating more preferable text with value- guided carlo tree search decoding. In First Conference Language Modeling, 2024a. URL https://openrevieer net:/orrumicckhh2222...
Kuikui Liu. 6.s891 lecture 4: Spectral methods. conductance, and canonical paths. 2023. URL pdf.
https://kuikuil wu..iiiiiggee www.giituub.... wtt.i//ee/au22/////35//3///
http://kkkiiiii..ttuub.....
Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, and David X Wu. Locally stationary distributions: A framework for analyzing slow-mixing markov chains. In 2024 IEEE 65th Annual Symposium Foundations of Computer Science (FOCS), pp- 203-215, IEEE, 2024b.
Zhenhua Liu, Lijun Li, Ruizhe Chen, Yuxian Jiang, Tong Zhu, Zhaochen Su, Wenliang Chen, and Jing Shao. Iterative value function optimization for guided decoding. arXiv preprint arXiv:2503.02366 2025.
Zhixuan Liu, Zhanhui Zhou, Yuanfu Wang, Chao Yang, and Yu Qiao. Inference-time language model alignment via integrated value guidance. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 4181 11954195, 2024c.
João Loula, Benjamin LeBrum, Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O' O'Donell.. Syntactic and semantic control of large language models via sequential monte carlo. In The Thirteenth International Conference on Learning Representations, 2025. URL https: http//pppevvveeeeeee
Jiff Matoušek and Jan Vondrák. The probabilistic method. Lecture Notes, Department of Applied Mathematics, Charles University, Prague, 2001.
Roberto Molinaro, Samuel Lanthaler, Bogdan Raonié, Tobias Rohner, Victor Armegioiu, Stephan Simonis, Dana Grund, Yannick Ramic, Zhong Yi Wan, Fei Sha, et al. Generative for fast and accurate statistical computation of fluids. arXiv preprini arXiv:2409. 18359, 2024.
Ravi Montenegro and Prasad Tetali. Mathematical aspects of mixing times markov chains. Found. Trends Theor. Comput. Sci., 1(3), 2005, doi: 10. 10.1561/040000000 URL https: /rg///////.... 1561 /0400900003.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang, Yanping Huang, Zhifeng Chen, Heng-Tze Cheng, Michael Collins, Trevor Strohman, Jilin Chen, Alex Beutel, and Ahmad Beirami. Controlled decoding from language models. In Forty-first International Conference on Machine Learning, 2024. URL httpr//.oooopotutua/e/////////en
OpenAl. Introducing openai ol. Blog, 2024. URL https:///ppeaai.com//////
Kanghee Park, Jiayu Wang. Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D' A'tooni. Hlammar-alignes decoding. Advances in Neural Information Processing Systems, 37:24547- 24568, 2024.
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference Learning Representations, 2022. URL htttps:///ppp //tptee///peeeviii.... net/ Forummiio=kntV097143e
Ashwini Pokle, Matthew J Muckley, Ricky TQ Chen, and Brian Karrer. Training-free linear image inverses via flows. arXiv preprint 2rXiv:2310.044: 2023.
Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03393 2020.
Isha Puri, Shivehander Sudalairaj, Guangxuan Xu, Kai Xu, and Akash Srivastava. A probabilistic inference approach to inference-time scaling Iims using particle-base monte carlo methods. arXiv preprint 011102250..01618, 2025.
14

---

Published as a conference paper at ICLR 2026
Tian Qin, David Alvarez-Melis, Samy Jelassi, and Eran Malach. To backtrack not to backtrack: When sequential search limits model reasoning. arXiv preprint arXiv:2504.07052, 2025.
Rafael Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From $r$ to $q^#5: Your language model is secretly q- fffnuction. In First Conference on Language Modeling, 2024. URL https: net wwt..e/orrumiiikkkeywt.t.... //tpenreview.net//
Ahmad Rashid, Ruotian Wu, Julia Grosse, Agustinus Kristiadi, and Pascal Poupart. A critical look at tokenwise reward-guides text generation. arXiv preprint arXiv:2406.07778 2024.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pp. 661-668 JMLR Workshop and Conference Proceedings, 2010.
Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transuctions Information Theory, 2016.
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. Picard: Parsing incrementally for con- strained auto-regressive decoding from language models. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 1895-9901,
M.P. Schütteenerreer. context- free languages and push-down automata. Information and Control, URL
6(3):246-264, 1963. ISSN 0019-9958. doi: https://ww..cieee wwwp::/wwwiiinceeecc......c. cotpeeeedrreettcooeeooooeeeeeeee htttr///eeeeeeeeeaaeaee/e///////
Thomas Scialom, Paul-Alexis Dray, Jacopo Staiano, Sylvain Lamprier, and Benjamin Piwowarski. To beam or not to beam: That is a question of cooperation for language gans. Advances in neural information processing systems, 14426585-265977 2021.
Amrith Setlur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Fisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. Rewarding progress: Scaling automated process verifiers for LLM reasoning. In The Thirteenth International Conference on Learning https://openreviiee www.p/nreevieeeettoorumimiiiieee
Representations, 2025. URL WRRLhttps:///
Richard Shin, Christopher Lin, Sam Thomson, Charles Chen Jr, Subhro Roy. Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language
models yield few-shot semantic parsers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 7699-7715 2021.
Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation, 82(1):93 133,, 1989.
Anikait Singh, Kushal Arora, Sedrick Keh, Jean Mereat, Tatsunori Hashimoto, Chelsea Finn, and Aviral Kumar. Improving test-time search for LLMs with backtracking against in-context value verifiers. Scaling Self-Improving Foundation Models without Human Supervision, 2025. URL net https://openrewee wwwp::/.ewwffwnnmem.e www.nttfoorum1d1177760fffff
Marta Skreta, Tara Akhound-Sadegh, Viktor Ohanesian, Roberto Bondesan, Alan Aspuru-Guzir Ar- naud Doucet, Rob Brekelmans, Alexander Tong, and Kirill Neklyudov. Feynman kac correctors in diffusion: Annealing, guidance, and product of experts. In Forty-second International Conference on Machine Learning, 2025. URL https://openrewe/ wtwpr/rewiiieeeeeeerurmummmmm hett/Forumiid--hcokrre
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. arXiv:2408.03:: 0331,, 2024.
Anne Somalwar, Bruce D Lee, George Pappas, and Nikolai Matni. Learning with imperfect models: When multi-step prediction mitigates compounding emoor arXiv preprint arXiv:2504.011 000.25660...66, 2025.
Yang Song, Jascha Sohl-Dickstein Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021. URL https:// /ttp///pwp///eeee///////e/ f ExTIG12RRHS.
15

---

Published as a conference paper at ICLR 2026
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXIv:2211.1225,.0 2022.
Dimitri von Rütte, Janis Fluri, Yuhui Ding, Antonio Orvieto, Bernhard Schölkopf, and Thomas Hofmann. Generalized interpolating discrete diffusion. In Forty-second International Conference on Machine Learning. 2025. URL http:////ppppeeeeeeeeeeeeeeeeett net//forrmm/uurw22//ss...
Martin Wainwright. digh-ddieesiooal statistics; non-asymptotic viewpoint, volume 48, Cam- bridge University Press, 2019.
Kaiwen Wang, Jin Peng Zhou, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kianté Brantley, and Wen Sun. guiue- search for efficient chain-of-thought reasoning. arXiv preprint arXiv:2505. 17373,, 2025.
Peiyi Wang. Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce lims step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computtational Linguistics (Volume 1: Long Papers), pp. 9426-9439, 2024.
Kaiyue Wen, Yuchen Li, Bingbin Liu, and Andrej Risteski. Transformers uninterpretable with myopic methods: a case study with bounded dyck grammars. In Thirty-seventh Conference Neural Information Processing Systems, 2023. URL h www.eeeiwwweeeeeouuiiiiidie Oi tmaxSAUu.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang, An empirical analysis of compute-optimal inference for mroblem-solvigg with language models. arXiv:2408.00724 2024.
Tengyang Xie, Dylan Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Hassan Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit qf-approximation for sample-efficient RLHF. In The Thirteenth International Conference on Learning Representations, wwwpteeeut/niieeee www.moiddoodaaooooo oo
2025. URL https:: /ttp::::///ppeeevviieeeee
net/
Kaiyu Yang, Jia Deng, and Danqi Chen. Generating natural language proofs with verifier-guided search. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.). Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 89-105, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.18655. 11/2022.emnll-mail URL https:://aaaaattollggee org/2022. wwn.p-mmmppppppm.mm emnlp-main.77 main.
Kaylee Yingxi Yang and Andre Wibisono. Convergence of the inexact langevin algorithm and score-based generative models in kl divergence. arXiv preprint arXiv:2211.01512. 2022.
Kevin Yang and Dan Klein. Fudge: Controlled text generation with future discriminators. In Proceed- ings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 3511 1-3555, 2021.
Xiao-Wor Wen Yang, Xuan Yi Zhu, Wen-Da Wei, Ding-Chi Chu Zhang, Jie-Jing Shao, Zhi Zhou, Lan-Zhe Guo, and Yu-Feng Li. Step back to leap forward: saff-backtrackingg for boosting reasoning of language models. arXiv preprint arXiv:2502.044 044444 2025.
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 1th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 3770-3785, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v 100653////2221111 acl-llogg.222. 1a0.://////22....oooo......0000
URL https:
//acl l/aclanthology . org. 202122211100 acl-long 292.
Fei Yu, Yingru Li, and Benyou Wang. Scaling flaws of verifier-guided search in mathematical reasoning. In Workshop on Reasoning and Planning for Large Language Models, 2025a. URL
https://openrevier net hett/Forummid::wF/BBwwwsss
Fei Yu. Yingru Li, and Benyou Wang. Uncertainty-wware search and value models: Mitigating search scaling flaws in llms. arxiv preprint arXivv2502.1/155, 2025b.
16

---

Published as a conference paper at ICLR 2026
Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse. Probabilistic inference in language models via twisted sequential monte carlo. International Conference on Machine Learning, 2024a.
Yixiu Zhao, Jiaxin Shi, Feng Chen, Shaul Druckmann, Lester Mackey, and Scott Linderman. Informed correctors for discrete diffusion models. arXiv preprint arXiv:2407.21243, 2024b.
Jin Peng Zhou, Kaiwen Wang, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kilian Q Weinberger, Kianté Brantley, and Wen Sun. Qt:: Provably optimal distributional for Ilm post-training. arXiv preprint arXiv:2502. 2025.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint Xiv: 1909 1909.08533, 2019.
17

---

Published as a conference paper at ICLR 2026
CONTENTS OF APPENDIX
I Additional Discussion and Results
19
Additional Related Work
19
A.1
Empirical Literature
19
A.2 Theoretical Literature
20
Approximate Coverage Enables Reward Maximization
22
C Pitfalls of Beam Search
23
D Insufficiency of Alternative Error Conditions
25
D.I Average-Case Multiplicative Error Bound under Traf
25
D.2
Additive Error Bound for V Mean-Squared Error Bound for Q
25
D.3
................................
E Further Experimental Details and Omitted Figures
29
E,
Implementation Details for Sampling Algorithms
................................
29
E.2
ABC Task
................................
30
E.3
Parity Task
32
E,4
Dyck Grammar Task
33
E,5
Python Test Case Generation Task
42
E.6
Letter Avoidance Task
43
E.7
Additional Exploratory Experimental Results
II
Proofs and Supporting Results
49
F
Preliminaries
49
F.1
Probability Theory
49
F.2
KL-Regularized Reinforcement Learning
F3
Value Functions
51
F.4
Approximate Rejection Sampling
G Omitted Results and Proofs from Section 2
54
G.I Pseudocode and Analyses for Baseline Sampling Algorithms
G.2 Action-Level Sampling for Consistent Value Functions
G.3 Lower Bound for Outcome-Level Algorithms
58
Omitted Results and Proofs from Section 3
60
H.1 Details for Examples 3.1 and 3.2
................................
H.2
KL-Regularized ABC Example
I
Omitted Results and Proofs from Section
62
1.1
Detailed Implementation of VGB for Friform-FEror Results
62
1.2
Proof of Theorem 4.1: Uniform Error Bounds
I.3 Proof of Theorem L1: Uniform Error Bounds
66
1.4
Proof of Theorem 4.2: Average Error Bounds
69
LLM Usage Statement
76
18

---

Published as a conference paper at ICLR 2026
Part I
A Additional Discussion and Results
A ADDITIONAL RELATED WORK
A.1 EMPIRICAL. LITERATURE
Early empirical investigations into benefits of process verification for language models (Polu & Sutskever, 2020; Cobbe et al., 2021; Lightman et al., 2024; Uesato et al., 2022) focused intuitive notions of intermediate progress, and explored various schemes for aggregating step-wise verification judgments into final outcome-level score, including taking products of probabilities, majority voting (Li et al., 2023), or minimums of scores (Wang et al., 2024). A recurring theme in this line of work is the question of how define the "steps" or "blocks" for verification, and what level of granularity process-level feedback is most effective.
Many of these carlier works learned process rewards merely as a building block to more effectively learn outcome rewards (and used the learned rewards with reinforcement learning rather than at test time), but many recent works on language model reasoning have also directly used process reward models at test time, with beam search or other tree search algorithms (Yang et al., 2022: Snell et al., 2024; Wu et al., 2024; Wang et al., 2025). Several works have demonstrated empirical shortcomings of greedy methods such as beam search with process rewards, and suggest introducing stochasticity (Yu et al., 2025a; Puri et al., 2025) or uncertainty-awarent
(Yu et al., 2025b) to robustify generation.
Value functions as process verifiers. A growing body of empirical work uses learned value functions as (a specific instantiation of) process verifiers to guide language model decoding. These works can roughly be categorized as employing either guided search-based methods (primarily for mathematical reasoning or similar reward maximization tasks) (Snell et al., 2024; Setlur et al., 2025; Wang et al., 2025) or guided sampling paaeed based methods (for alignment or constrained text generation) (Yang& & Klein, 2021; Mudgal et al., 2024: Chakraborty et al., 2024; Khanov et al., 2024; Rashid et al., 2024; Li et al., 2024; Liu et al., 2025). Both lines of work typically learn the value function through Monte Carlo rollouts (a method that has also been employed in reinforcement learning pipelines (Wang et al., 2024)) and then use it within scarch schemes such as beam search or (block-level) best-of-N, or sampling schemes such as token/action-level sampling or block-level sampling.
Our work is most closely related to the sampling literature, and provides a formal thcoretical model for analyzing different value- value-guided sampling methods, but we hope that it may provide insights for improving search as well. Empirically, we expect that VGB, by incorporating more deliberate search and backtracking while preserving the base model's diversity, could be beneficially combined with the value function learning schemes from this literature.
Backtracking and tree search with process verifiers. While many search-based approaches are based on greedy decoding or beam search, several empirical works have explored more advanced back- tracking or tree search schemes with process verifiers (Scialom et al., 2021; Chaffin et al., 2022; Liu al., 2024a; Hao al., 2023; Snell et al., 2024; Singh et al., 2025; Botta et al., 2025). These methods aim to overcome the limitations of purely left-to-right generation by allowing the model to revise car- lier decisions." 11 Compared VGB, these methods may not preserve the base model's diversity, as they are designed with pure reward maxinization in mind (cf. Remark 2. 2). Our work demonstrates that backtracking can be applied effectively (and in mathematically justified manner) even for sampling.
Controlled decoding without learned process verifiers. Our work connects to a long line of empirical and methodological work on constraineddcontrolled decoding that has developed largely in parallel with the literature discussed above, but that does not actually learn a process verifier (Shin et al., 2021; Scholak et al., 2021; Poesia et al., 2022; Lew et al., 2023; Ahmed et al., 2025; Gonzalez et al., 2025; Lipkin et al., 2025; Loula et al., 2025). This line of work primarily focuses on the setting where the goal is to condition a base model Kref on some sequence-level constraint r* (I, y) = 1 that can also be evaluated on partial generations. These works forgo training value function (which can be computationally expensive), and instead use the reward function r* (I, F1.A) itself as a process
We remark that other recent works explore training models backtrack, which is orthogonal to the focus of this work (Qin et al., 2025).
19

---

Published as a conference paper at ICLR 2026
verifier for partial generations. The dominant method in this literature is locally constrained decoding (Shin et al., 2021; Scholak et al., 2021) (see also Lipkin et al. (2025) for additional references), which- discuss in Section 5-is equivalent to ActionLevelRS for a natural approximate value function V.
Sequential Monte Carlo and particle filtering. Our work also connects to a body of literature on using Sequential Monte Carlo (SMC) and particle filtering methods for inference-time decoding under process-level guidance (Lew et al., 2023; Zhao et al., 2024a; Loula et al., 2025; Puri et al., 2025). 12 These algorithms bear some resemblance to VGB, in that they maintain a diverse set of candidate sequences, sampling successors based on importance weights. However, they typically do not incorporate backtracking, and lack finite-imm/coompee performance guarantees. It is an interesting open question whether these methods achieve comparable guarantees to VGB.
diffusion models. Our work broadly shares some high-level motivations with a few strands of work diffusion models. Since the earliest days of diffusion models, strategies like predictor-corrector (Song et al., 2021) were used at inference-time to tame the error accumulation inference time, accrued from simulating the reverse SDE. Variants of these strategies have been developed also for discrete diffusions (Zhao et al., 2024b). Moreover, for the most popular type of discrete diffusion model for language-absorbingg abborring noise diffusion models- the natural inference-time sampling strategies will not revise a token once it has been set to some value. This has naturally led to work on allowing the model to backtrack in principled manner (von Rütte et al., 2025), with promising gains in performance.
Additional context:
Another related area in diffusion models is sampling from tilted distributions of a distribution that we have trained a diffusion model for. Notable applications of this flavor are classifier guidance (Dhariwal & Nichol, 2021; Ho & Salimans, 2021) and inverse problems (Bruna & Han, 2024; Pokle al., 2023). However, the conceptual problem in this area is somewhat different: namely, we have access to the denoiser for the base distribution (at any level of noise), but not for the tilted distribution and these two cannot be easily related to each other.
A.2 THEORETICAL LITERATURE
Theoretical understanding of process verifiers. On the theoretical front, our work is most closely related Botta et al. (2025), who show provable benefits of access to an exact process verifier in a binary outcome setting without KL-regularization, a result analogous to our findings regarding action-level versus sequence-lever coverage in Section 3. However, their analysis restricted to perfect verifiers. Botta et al. (2025) also show empirical benefits of backtracking heuristic with a trained process verifier; one key obstacle that they face is deciding when and how often to backtrack, which their method addresses by introducing several ad-hoc hyperparameters.
Foster et al. (2025) give guarantees for KL-regularized reinforcement learning in a setting where (%, )1.A) = (0", oxx, 31:h)) is linear in a known feature map. They show that by using deliberate exploration, it is possible to provably learn high-quality value function, with runtime controlled by the action-level coverage coefficient Cact. Conceptually this result highlights that process verifiers can be learned end-to-end while maintaining the computational benefits we sketch in Section 3, but the algorithm and analysis are quite specialized the linear setting.
Other related works include Huang et al. (2025a;b), who provide algorithms and theoretical guarantees for imperfect outcome-level verifiers, and Balcan et al. (2025). who study the sample complexity of learning outcome-level verifiers for chain-of-thi of-thought reasoning. Finally, we mention in passing the work of Jia et al. (2025), which shows that for general MDPs, the sequence-level coverage coefficient we consider is controlled by a state-level coverage coefficient:" 13 we remark that these quantities are equivalent for language models, i.e. the state-level coverage coefficient will also typically be impractically large.
Approximate sampling in theoretical computer science. As discussed in Section 4, VGB can be interpreted as generalization of the Sinclair-Jerrum random walk (Sinclair & Jerrum, 1989) from
IMMC is also common method for tilting diffusion models at inference time; see e.g. Skreta et al. (2025). BJa et al. (2025) use this observation to show that for offline reinforcement learning in general MDPs where reward ra is available at every step, learning from the sum DH Th is no harder than learning from the individual rewards (ri,...,PH))
20

---

Published as a conference paper at ICLR 2026
theoretical computer science. Sinclair & Jerrum (1989) developed this walk show that for any self- reducible constraint problem such as SAT, there is an efficient complexity -theorett reduction from approximately sampling from the uniform distribution satisfying assignments approximately counting the number of satisfying assignments. Crucially, the error in the approximate counter is not amplified: to the contrary, the approximate sampler achieve arbitrary (inverse-polynomial) accuracy even when the approximate counter has polynomially-lare error.
At a technical level, Sinclair and Jerrum (in the above work and Jerrum Sinclair (1988)) developed the foundations of (now classical) theory on the mixing time of Markov chains: specifically, the method of using conductance bound the spectral gap, which implies fast mixing. Our proof of Theorem 4.1 follows the same method; however, our proof of Theorem 4.2 requires more modern techniques such local stationarity (Balasubramanian al., 2022; Liu al., 2024b), as discussed in Appendix 1.4.
21

---

Published as a conference paper at ICLR 2026
B APPROXIMATE COVERAGE ENABLES REWARD MAXIMIZATION
In Theorem 4.2, we showed that the law of the output of VGB approximately covers the optimal distribution under Assumption 4.2. As result, competitive with the optimal distribution in terms of diversity (i.e., under Eq. (7), drawing O(nH/ó) samples from VGB will tend to cover almost as many responses ((n) samples from T²') Approximate coverage also enables approximate (unregularized) reward maximization. This is achieved simply by applying the Best-of-N algorithm to multiple samples from VGB. this section, we provide a formal statement this implication for completeness.
Formally, for proposal distribution a E A()), reward function r y - R, and positive integer N, the Best-of-N algorithm draws N samples ......., y arg e r" (y/"). The following proposition shows that approximate coverage implies regret bounds for any binary-valued reward function; e.g. Huang et al. (2025b) for more general guarantees.
......
π and outputs you where
Proposition B.1 (Best-of-N N guarantee under approximate coverage). Let n. π² be two distributions over the set Y, and let r* y + {0, 1} be a binary-valued reward function. Suppose that n, n satisfy
x x²( (
you
F(E)
SE
(8)
for some function F R20 Ry Then for any E,8 > O, the output y of the Best-of-N algorithm with proposal distribution π. reward function r", and parameter == F(c) log satisfies
E (T) E (r' - -
Note that this is interesting in the context of Theorem 4.2 since the output of VGB satisfies the above guarantee with F(s) (8 Thus, by applying the Best-of-N algorithm to O(H) samples from VGB, we can compete with the optimal distribution x² in expected reward (for any r" that we can evaluate).
Proof.
Let & be the event that (y) = 1, and let &g be the event that π (y)//(y)) < F(s). By assumption, have x² x*²)) 1 - e, and thus x² (E n E2) E= [r*( - It follows that
TE N2 2 F(e)
(r)( E).
Now recall the definition of the Best-of-N algorithm; let y ..... (N) denote the candidates that draws from The algorithm's output 7 satisfies
Eir" (1) > P E [N] " E E
E( n E2) 2 1 - मं (B" (wil-s)
2 1 888 [r' (v)l-
2 ET [x)
by choice of N and the inequality - y" 2 for all x, E 1].
22

---

Published as a conference paper at ICLR 2026
C PITFALLS OF BEAM SEARCH
The main focus of our work is on the task of sampling, which is often used to balance reward maximization and diversity / general capability (Ziegler al., 2019). In practice, sometimes the only goal is reward maximization: given a base policy Tref X + y and query access to a reward function r* X' y > [0, R the goal given some prompt x E X --is to compute some y E y achieving maximal reward.
Given some process guidance function G: A R, two classical, widely-used algorithms for this task are greedy decoding and heam search (Khanov et al., 2024; Wang et al., 2025). For some width parameter W, beam search with guidance function G proceeds as follows. each E [H), maintains W beams Vith-1.--- Vik- E AA--1 of length h - 1. It then computes the W|A beams that are all possible one-token extensions (if [AA] is large, then instead the algorithm draws some number candidate tokens from Traf). Finally, from these A| extended beams, it selects the W extended beams (11 1/h)) with the maximal values of G - Wh). After step H. the output is selected again by maximizing G. Greedy decoding is simply beam search with width W 1.
No matter the choice of guidance function, it is clear that these algorithms are not sampling from the distribution n defined in Eq. (2), nor do they maintain diversity of generations any sense, as their goal is pure reward maximization. In certain settings, they provably effective reward maximization: in particular, it is straightforward to see that with guidance function
max r (I,)):H) G(r, m):h) II
beam search finds some Vi.H arg max r" (z, V1:H) ) for any W 2 1. This guidance funetion the classical (optimal, unregularized) value function in the autoregressive MDP defined by the deterministic dynamics (y1:h-1 1, yh) y1.h-
However, our setting studies the benefits of the guidance function
G( V1:k) (an: vich) E [r" U1.H) x. M.:l,
which is the value function for Tref in the autoregressive MDP. This "averaged" guidance function natural since it be directly estimated via regression onto Monte Carlo roll-outs, unlike the preceding function, and this is commonly done in practice (Yang & Klein, 2021: Wang et al., 2025). The following example demonstrates that with this value function, even in the absence of estimation errors, beam search is not the "right" algorithm for reward maximization: it can be substantially worse than algorithms that sample from (y x) x Fyef x)r* (Iz, y).
Example C.1 (Greedy decoding and beam search are suboptimal with Viite). Let X' == {T} (we omit dependencies on the prompt space henceforth) and y = {0, T for some even H. Define Tref == (D). Define r" y [0.1] 1] by
y ///2+ =0 =0
(yI.H) = 21 11-H/2
y =
0
otherwise
Then the distribution xt (z) x (y)r (v) satisfies
2112-112-1
1
ET 1r [v))
Σ (0 /2.H/2, 01/2)
2H/2-12-11 + +21-12 1-4-12-H21--1 H22-H/2
92:H/2
However, consider the execution of beam search for any W 2/2211 For every h S. H/2, we have
2 2-11/2 11/2
i1 = 0
Vine(yn-n)
21-
if =1
In particular, Vine (0, 32.h) < Vine (1, s/2nh) for all 12:1o V2. Thus, by step H/2, beam search will reject all beams with y1 So will find response with reward H1HH/2 which is (11)-suboptimal compared to x*.
"'ff course, in some instances it can be better, so the algorithms are incomparable when the goal is reward maximization.
23

---

Published as a conference paper at ICLR 2026
We prove analogous result in the KL-regularized optimization setting. In this setting, for fixed base policy and reward function, the regularized value function Q F1 = 3 log Vile (z, M2sh) ) converges to the classical unregularized value function as B - 0, so this limit beam search will succeed. However, the following example demonstrates that even for / O11/H), beam search can fail unless it uses width W 20(H).
Example C.2 (Greedy decoding and beam search fail with Q3y) Let X == {1} (we ignore the prompt space henceforth) and y == {0, 1) for some even H > 2. Define Tref == Unif()).. Ser
(H-2) log((2 that e 28/2-11 Define r : [0, by
if yl 1. =0
("(m))) =
if y1 =1
2
otherwise
similar the preceding example. Then the distribution T3(()) x neef (v) exp(3-1r*(y)) satisfies
2 + 1
2 o(1)
("r(("())) 2H/2-12- 8- -2H-12-He05111 (2 221/2-122-
3
However, for every h S H/2, we have
12H12-2 2211221
if =
(yra)) Ra (r [1:a)]
if =
Thus, as in the preceding example, beam search will reject all beams with y1 = unless the width exceeds 22 Therefore it will (deterministically) produce response with reward only 1/2.
24

---

Published as a conference paper at ICLR 2026
D INSUFFICIENCY OF ALTERNATIVE ERROR CONDITIONS
In this section, we discuss issues with three natural alternative егтоr conditions to Assumption 4.2: an average-case eтror bound under Fref rather than x* (Appendix D.I), an additive error bound rather than multiplicative (Appendix D.2), and mean-- error bound on = 3 log V rather than an exponential MGF bound on Q (Appendix D.3).
D.1 AVERAGE- CASE MULTIPLICATIVE ERROR BOUND UNDER Tref One plausible alternative to Assumption 4.2 is the following assumption, which is average-case over Tee rather than x²; for each position h I H,
VI, Mi:h)
Vine vra)) Visk) S +ey
S Sitev.
E (
91 T (-Ia)
(I, Vish))
This modification seems particularly natural if V is estimated via regression onto Monte Carlo roll-outs from Tref. since typical statistical learning guarantees will be average-case over Tref- Unfortunately, as the following example shows, test-time alignment is information-theeortiiaalyy impossible with only this assumption, unless ěy is exponentially small. The basic reason that distribution shift between Tree and x² earlier positions can lead to the error bound being essentially vacuous on the effective support π at later positions > h.
Example D.I. Let X' == {1) (we omit dependencies on prompt henceforth) and y == AH where H E N is even and A == 10. Let Fref == Unif()). We define family of test-time alignment instances I parametrized by a sequence = 9H/2+1:H1 E 13/2 Each instance has base policy Kref and tilt function Ty ; + {0. 1} defined by
Ty Ty(.H. 1/ 0 VH/2+1:H = + My = =],
for a parameter X > O to be determined. The optimal distribution Ti x Tret Ty satisfies 77(0,)) g) =
1+A 1424/1x and
22h 2h-"1IyLA 2h- 0*] 2h 2h-HH1p "Ily1-A (0. AI = 0//
hf H/2 otherwise
Vilt.g (V1:h)
We define
((naa) = Veite (Wi:n)
if S H/2 otherwise
(Allyt-H/2 = ///2
Then for any h. > H/2, we have V (ynitt) S Viit. (B1:t)) ). for all yı and
Vii Veln. (Ursh) (ITAA)
2h-H
(V = (0, = 2-H
E Wish Tref
S1+
Pr
X
Set À 2- Then Eq. (9) satisfied with Ey == 2-12 Moreover, V does not depend on g. so for any alignment algorithm, the law 7. of the output on instance Ig is independent of It follows that there is some such that 7 g) < 1/2H/2, But by choice of X, we have r2 (0, g) 2 for all Thus, there is some g such that
TT (V.u))
Pr Vi:st nas
2 HH/221
2 2'
*(vi:H)
i.e. there is a constant fraction of the mass of TH where ã exponentially undercovers the responses.
D.2 ADDITIVE ERROR BOUND FOR V
Typical statistical learning guarantees for regression give additive error bounds rather than multiplica- tive error bounds. Thus, it may seem natural to instead assume that for each position E [H]. for each Vich E A
(5, via) Vine (2,, v)t) s ev
(10)
25

---

Published as a conference paper at ICLR 2026
for parameter Ev 0 or analogous average- bound. For simplicity, let us consider the worst-case version; the same issues apply to the weaker average-case versions.
The basic issue is that Eq. (10) is not appropriately scale-invariant:
rescaling т, Väit+ and V by 1/2 does not change the problem, but halves the additive error. Moreover, the following simple example demonstrates that even in the constrained sampling setting, where r is binary-valued and therefore has natural scale, Eq. (10) insufficient unless Ev exponentially small.
Example D.2. Let X = } and y = A where H E N and A = {0, 10. Let Trer == Un) We define a family of test-time alignment instances Lg parametrized by a sequence g = 91.H E A
Each instance has base policy re and tilt function Tg y - {0, 13 defined by
Tg = Ily = g).
Thus, the optimal distribution Tig x Tree Ty satisfies (g(9) = 1, and tilt, (Wi:)) = 22h gr.k]. We define
(v1:t.) = 10
if S H/2 Viir. (yIA) otherwise
Then Eq. (10) is satisfied with ev == 2-H/2 However, it is evident that observing a non-zero value of V requires (0( queries, for any algorithm that makes (n( queries, there will be some instance Ig on which its output distribution R. will exponentially undercover v (in the sense of the previous example) with high probability. We omit formal details of the query lower bound as such arguments are standard.
A scale-invariant additive assumption? The failure mode of the above example is that Tref has extremely low average reward and it seems natural that the accuracy of the value function estimates in such a setting may necessarily have to be correspondingly more accurate. Motivated by this observation, we briefly discuss a scale-invariant version Eq. (10), which scales the error according to the inherent "difficulty" of the problem:
Assumption D.1. For each position h E for each yıth E Aa,
(v
Vi.)) S Ev (z).
The following proposition shows that Assumption D.1 actually implies Assumption 4.2, with a slight adjustment to the approximate value function-that can be tractably computed if Vūne(z) is known (i.e. we have some estimate of the "difficulty" of prompt x for Tref).
Proposition D.I. Lei > O. Under Assumption D.I with parameter ev, the (modified) approximate value function V' 31:hh) (x, VI:1) Ev (1) satisfies Assumption 4.2 with parameter 22y.
Proof. Since x² (yi:h x)) (al (y1 x)) Veine (x,, m).)) we have
V' V1:h) Vinee (2, v1:h)
V' v1.h) - Vine (z, B1sh)) Vitr (1:11:h)
E Vicke (-1a)
1
E Vich (-lw)
Vi V1.N) - Viste (2,, V11n)) Vinn(())
1 +
E
M (+1z)
Vxx M1:h)) - Vise (x, M1sh) Vūn (x)
+ Ev +
nh. -
< 1 + 28v
and, for every VisA Ah, (1. (x, V1:h) Ev (iine()) 2 Vine (2, V1.h), so that
V Vi va:h)
E Visoor (-Ix)
<1
V'(I,3IAN)
which suffices.
26

---

Published as a conference paper at ICLR 2026
This result provides additional motivation for Assumption 4.2, and suggests a potential algorithmic intervention to make an approximate value function more defuu-nnmmlyy adding some estimate of Viie(a) to the approximation. However, it remains unclear whether Assumption D.1 is sufficient also unclear whether an average-case variant of Assumption D.1 could suffice for efficient test-time alignment (in the proof of Proposition D.1, the first part goes through with an average-case error bound under Fref. but the second part does not)-and in what regimes of εv it would enable improving upon the error guarantees of ActionLevelRS, We leave these interesting open questions for future work.
when Viir(2)) (a) is unknown.
D.3 MEAN-SQUARED ERROR BOUND FOR Q As discussed in Section 4.3, in the KL-rreuularized setting, Assumption 4.2 corresponds an MGF bound on A (z. V1:h) == Q7 (x, V1:A) (zx, y1.h);;; it is implied by:
cxx (3 (1-8)11666 (1 )1a))) S Ev.
(11)
M (
While an average-case assumption, this is still stronger than typical statistical guarantees for regression (e.g., Wainwright (2019)). One may naturally ask whether mean- mean-squared error bound suffices for Theorem 4.2; we show that does not." 15 This result demonstrates distinction between the = setting (Huang al., 2025b) and our setting.
To state the formal result, we introduce the following oracle framework for KL-regularized optimiza- tion, in which the algorithm has sample access to the base model and query access to the approximate value function (but does not have access to the true outcome-level reward). Note that Theorem 4.2
applies in this setting. See Huang al. (2025b); Foster al. (2025) for similar models.
Definition D.1 (Oracle framework for KL-regularized optimization). Let Feet be a base model, let r* be a reward function, and let O. We consider algorithms that have access to the following oracles:
Value function oracle: Given a prompt X and partial completion Yich E A", returns ((x, yn:h) = B log Vxx y1.h).
Conditional density oracle: Given prompt E X and a partial completion Vi:h-1 E A returns Tref (yke 2, 11: for all yh A.
We show that if Eq. (11) is relaxed to an lp error bound for any constant then there is no algorithm in the above framework that achieves an analogous "approximate coverage" guarantee to Theorem 4.2.
Theorem D.1. Letp 2 2 and let H E N be given. Set X = (1) = (0.1) and y = AH For any algorithm the above orucle framework with 3 = 2(p+2)H log H' there exists base model Tref : X + A()), reward function r* :Xxxx Xxy- y- + [0, 1]. and approximate value function Q satisfying Exeer (Q(r, Vinh) (7((, S SE6 and Emg [Q(r, V.A)) (Z((.V11)) %
(12)
where EQ = 0(3), and yet the output distribution के of the algorithm satisfies
TT( (1)
24 1
p
4
In other words, there can be a constant-fraction of the mass 3 where क exponentially undercovers the responses. This result can be contrasted with Theorem 4.2 and Assumption 4.2.
Note that this result is agnostic the query complexity of the sampling algorithm in the above oracle framework; there is simply not enough information in Q to achieve approximate coverage. However, the result does not capture algorithms that have access to the true outcome-leve rewards. In that case, there is (existentially) enough information to sample from the true distribution since the above result shows that the process verifier Q can be completely uninformative, we expect that there is a query- coeelxxtmy lower bound in this stronger setting.
1t is also not evident whether there a statistical regression procedure that achieves an MSE bound on Q (rather than V), but this result shows such bound would still be insufficient.
27

---

Published as a conference paper at ICLR 2026
Remark D.1. Consider the case p 2. To interpret the result, note the value function Q has low mean-squared ervor (MSE) under two policies: x² and Ares. Low MSE under IT" is the MSE analogue of Assumption 4.2, which the above result shows is information taeaotionnteorrtcllllly insufficient to achieve a comparable coverage guarantee to Theorem 4.2; this is true even when action space is large).
1 (if the
The ahean-squared error condition with respect to ref is more subtle. In the case of H = Huang al. (2025b, Theorem 4.1) show that using an algorithm based on pessimism, one can achieve runtime that scales with Cact(r) using only the assumption of low MSE under Tref. Our lower bound demonstrates that when H is large, MSE no longer (even information information-therrttinnn theoretically) sufficient to achieve such a guarantee esseeniall since distribution shift between Tree and xt arises in multi-step settings.
Proof of Theorem D.1. Set E == 1/H Fix ref Ber(1 - e) @ Ber(1 (er(1/2)((H-1) and == 1/H log(1/s)), We define family of instances where the reward function r* and optimal policy Tá are indexed by a sequence g 92.H E A", Instance [(g) is defined by reward function
Blog (V1.H)
r" (y).n)
Tref (ye:()
where x A()) is defined as the law of the following process: sample y1 ~ Ber(1/2). If = 1, Otherwise, independently sample y2..... V/ so that Ply: gi] 1 - s. By definition of r", we have that (3(1I.H) xx (VIr)) exp(3-1r-*0
then sample y2:H ~ Ber(112)0
so r* and Rt define valid instance of the KL-regularized optimization problem. Moreover, it is straightforward to check that (3(..)) (te...n/TTee(VV.ii (V1.11) E [s s=""="" " for all yI.H. and therefore r" ("()).)) [0. 1] by choice of
We have
(3(:)))
(7(()))) = Blog EF (exp((6- y1:A] + , log
Trer (Vi=h)
Define the approximation Q by
(3(an)) (0,
if = otherwise
(vin))
Since r" (W1:H) e [0, 1] for all F1.8, we have (3(1) [0, 1] for all yich, and therefore similarly @(BEN) E [0, 1] for all y1.h. It follows that
Frer
< pdre (y/2 0]
E.
Similarly,
< P 1y1 = 0 Ve.h 92211
SeH.
Note that (eH) < (1/(22 log(1/e) 0(3) so long as 8 S 11/Hp+2 Thus, for each instance [(g), the approximate value function satisfies the required accuracy guarantees. However, we can observe that @ does not depend on g. Thus, the law म of the sampling algorithm's 's output on instance I(g) does not depend on g. For each g, in instance [(g) it holds that (0, 92:H) = (1-)) 2 1- However, there is some 92.H H such that मे #(,, 92.H) < 21-H H Thus, in instance (gg). it holds that
(T())
> 2H3 2
1
Aly)
claimed.
28

---

Published as a conference paper at ICLR 2026
E FURTHER EXPERIMENTAL DETAILS AND OMITTED FIGURES
Basic setting, Our experimental tasks are instantiations of the following basic setup, Let X' denote prompt space, and y' A denote response space. Let Tref X' + A()) be generative model from which we can draw autoregressive samples (and compute next-token conditional probabilities). Let r* X' x y + {0. 1} be binary reward function that we can query (we will make it available to the generation algorithms in tasks where wish to measure distributional accuracy, but not in tasks where we wish to measure pure reward maximization). Given a prompt I E X, our primary goal is to sample from the distribution x²(- x)) E A(?) defined as the conditional distribution of Trer(: a) on reward-1 responses:
(y z) (y a)) r (z, v).
In different tasks, we will measure performance at this goal in different ways. As discussed in Section 1, it can be checked that x satisfies
' (yh x. V1sh-1) Trer (3h xr V1:h-1) Veire (2, y1sh)
where
Vilt (1, D1sh)) = E" (x, Vr:Ht) yran]-
Value function estimation by Monte Carlo rollouts. For all but the last of our tasks, we will train an approximation of Vit via regression onto Monte Carlo rollouts. In particular, expanding on the discussion in Section 1.2, the above expression for Viit suggests the following natural way to train a value function, which approximates the common approach in prior work (Yang & Klein, 2021; Wang et al., 2025):
1. Draw samples (z'), viAr)) D where x19) p is from some prompt distribution and y Tr ).
2. For each i [N], evaluate the reward p()) r (2 viTH)
3. For each h E [H] solve the regression problem
N
V < arg min
(V -
VEV
In specific experiments, we may deviate slightly from this formula, and we will describe such details in the corresponding sections.
Organization of section. In Appendix E.I. discuss in detail how we implement VGB and baselines, focusing particularly on the differences from the theoretical versions of the algorithms (made for efficiency and avoidance of unnecessary hyperparameters) In Appendices E.2 to E.6 provide details on the task setup, value function training setup, and evaluation protocol for each of the ABC task, parity task, Dyck grammar task, Python test case generation task, and letter avoidance task respectively. In Appendix E.7 we provide additional exploratory results.
E.1 IMPLEMENTATION DETAILS FOR SAMPLING ALGORITHMS
Implementation details for VGB, Recall that the provable guarantees for VGB require repeatedly running the Markov Chain for fixed number of steps, until the resulting generation is leaf node of the autoregressive tree (Algorithm 1). For our practical implementation of VGB, we instead return the first leaf reached during the random walk. We also remove self-loop transitions, as these now have no effect. For tasks with small alphabet size (ABC, Parity, and Dyck grammar) these modifications are the only changes made for the implementation: see Algorithm 3.
For tasks with large alphabet size (Python test case generation and letter avoidance), we make one additional change. Enumerating the alphabet each step would be computationally infeasible. Instead, we implement the transitions using an implicit approximation of rejection sampling (that
One difference is that these works typically do not train separate value function for each position h [H]]: revisit this detail the Python test case generation task (Appendix F.5).
We enforce fixed generation length in all of our experiments (so all leaves of the tree are at the same height H), but expect that our methods can be adapted to settings where generation lengths vary. We treat EOS as normal token.
29

---

Published as a conference paper at ICLR 2026
avoids needing to estimate normalization constant, unlike Algorithm 5). At iteration t, sample
K = 32 candidate tokens from Frer (: x, v1.)) Append each of these to Vish and let the resulting K
sequences be denoted by 2(1)....., 2 [K]
(e) E A 4++1_ Also define z(0] == Vich -1 We define probability
distribution g over z(0),...,2 by
(=(0)) & K V(I,
and, for 1 isisk
(=(i)) x 2(])).
We then sample t(t+ ~ poo It can be checked that as K + co, this distribution approximates the ideal distribution over the entire neighborhood of v/1
Implementation details for IGB-Momentum. We implement a version of VGB with momentum, analogous to the modification made by Hayes & Sinclair (2010) the original Sinclair-Jerrum chain. This means that there are two copies of each node of the generation tree, and each transition of the original undirected Markov Chain is replaced by a directed cycle; the crossing flows are then cancelled out to decrease diffusive behavior. See Hayes & Sinclair (2010) for the details of the modification, which carries over readily to our setting. The only practical modification we make is to stop the Markov Chain as soon it reaches leaf (as with VGB). We only implement this algorithm for settings with small alphabets, but one can see that would readily extend to large alphabets by the technique described above.
Implementation details for ActionLevelRS. When the true rewards are used for leaf nodes of the generation tree, actionLevelRR may get "stuck", i.e. all continuation probabilities may be O. In this case, we simply restart the algorithm at the root node. See Algorithm 4 for the implementation of ActionLe e for small alphabets. The implementation for large alphabets is the same as described above for VGB (again with K 32) except that the transition distribution puts zero mass on the backtracking candidate =|0] Vi-h-1' We do not the choice of K for either algorithm.
Implementation details for OutcomeLeveIRs. This algorithm is particularly simple in the con- strained sampling setting: it simply repeatedly draws responses from Trer until we find response with reward 1.
Implementation details for Block Best-of-B B and Block Rejection Sampling. In both algorithms, we generate via an iterative procedure: sample B blocks of length L, from Tref conditioned on the current partial generation. Then choose one of the resulting continuations by either (a) choosing the continuation with the largest estimated value (Block Best-of-B),, or (b) sampling the continuations proportional to their values (Block Rejection Sampling).
step count. Besides various error, diversity, and accuracy metrics, we will often measure the efficiency of different algorithms. Our main efficiency metric is step count. For VGB, this is the number of transitions of the Markov chain until it reaches leaf node; for ActionLevelRS, this is exactly the horizon H (i.e. length of responses) unless it gets "stuck" and either restarts or (in the large-I.4 |A| setting of Appendix E.6) has to redraw and evaluate new candidate tokens. For Block Best-of-B B and Block Rejection Sampling, this is BH where B is the number of candidate blocks. For MntcomeLeeeeRRS this is nH where is the number of repetitions required find reward-1 response." 18
Efficiency metric:
E.2 ABC TASK
Task setup. Let E N be a fixed horizon length, and define alphabet := {a, b, c). Define X = {1} to be the trivial prompt space, and define the response space to be y = A Define Tref E (()) to be uniform over y. Define reward function r r"() == Пyy E fa. b/ E [H]]. Thus, Tt is uniform over (a, b) This task, following Example 3.1, is designed to measure the effect of benign training errors on the sampling algorithms; note that there should be no computational obstacles learning the true value function.
We do not argue that step count is the only efficiency metric one might care about: indeed, in practice there are numerous other factors that heavily influence wall-clock time, including but not limited the number of language model queries per step, number of value function queries per step, key-value caching. and ease of parallelization; some of these are the focus of entire bodies of research in guided generation (Lipkin et al., 2025). These considerations are largely orthogonal to the focus of our work, for which step count is a simple micoretically-aaignee metric. We do nevertheless demonstrate that VGB can outperform ActionLevelRS in striet wall-clock time, albeit in the synthetic setting of the Parity task (Appendix F.3).
30

---

Published as a conference paper at ICLR 2026
Algorithm 3 Practical implementation of VGB for small alphabets
1: imput: Reference model Frefi approximate value function V. prompt X, horizon H E N. // If outcome-level. reward is available, set (ix, yıa) r" (x, v1.1).
2: Initialize y := Ø and
3: while 1y < H do
4: Set h == |
5: Define pl as the distribution over neighborhood ( of Vith where
(1x. if 0, if h 0,
p (1
and for each yh+1 E A.
TTee (Un+1 xr II, (x, vi Uh+1)
if < H, if H.
(v U1+1)
6: Sample y((=)) ~ pl), and increment t.
7:
return y
Algorithm 4 Practical implementation of ActionLevelRS for small alphabets
1: input: Reference model Fraf approximate value function V. prompt æ X, horizon E // If outcome-level reward is available, set (I, x" (1.1)..))
2: Initialize y ;= Ø and =
3: while (y H do
4:
if En EA Tre (V x, v VZ, (1) M1+1) then 5: Set gittt < Ø and increment f.
6: Set h := ly
7:
Define (h the distribution over neighborhood A (y)()) of with where for each gh++1 A.
p ( 1h+1) x Tret (yn+1 xr, (. V (z, yit Mh+1)
if < H, if = H.
8: Sample ((1)) p(t,, and increment 4.
9: return "
31

---

Published as a conference paper at ICLR 2026
N
500
= 1000
N 10000
Average Steps
800
ActionLevel
Average Steps
ActionLevel
Average Steps
ActionLevel
VGB
VGB
100-
VGB
600
100
100
200
50-
10
10
10
Horizon length (H)
Horizon length (H)
Horizon length (H)
Figure 4: Average step counts for ABC task (Appendix E.2). Each experiment is repeated 10 times and we plot the and standard error.
Value function training setup. Let E N the number of training samples. We train separate value network for each generation length E [ - 1] (at length H we use the true rewards). Each network takes as input a one-hot encoding of the generation and has one hidden layer of width 128; the internal activation function is ReLU and the final activation function is sigmoid. Each network trained with 100 steps of Adam, and learning rate 0.01, on the binary cross-entropy loss from N Monte Carlo roll-outs.
Evaluation protocol and results. For fixed and N, we train the value functions as described above, and then draw 10 2 samples from VGB (Algorithm 3) and ActionLeve (Algorithm 4). For each sampling algorithm, we compute the KI. divergence the empirical distribution to n² We repeat this experiment for 10 seeds, and all combinations of N (500, 1000, 10000) and H {5, 6, 7, 8, 9, 10). We observe that VGB robustly achieves lower KL-divergence than ActionLevelRS, with particularly pronounced benefits for larger H (Figure 2). We also record the average steps used by each algorithm (Figure 4), and observe that the step count of VGB appears to grow roughly quadratically in for large N, as predicted by the theory, but may scale considerably worse for small N.
E.3 PARITY TASK
Task setup. Let K, M N. Let MK be the horizon length, and define alphabet : : {0, 1) Define X' = {1) } to be the trivial prompt space, and define the response space be y = A
Define Tref E (()) by
I[yn yh+1-K 1/2
+ Uh-1 mod
if (K, ..... MK) otherwise
(ye 11:A-1)
Define reward function r" (v) Ily:k O E [M]]
Theoretical intuition for task. Intuitively, this task is designed so that a decision has to be made each position h K mod K, but the correctness of this decision is only made obvious at position f + (a la Example 3.2). This is motivated by the common empirical observation that in language model generations there is often natural "segmentation" where a complete segment is easier to score than an incomplete segment (Li et al., 2024).
More precisely, with this setup, we observe that the true value function
yh 0]
if h K mod K if h K mod K otherwise
Vine())))) = -2
0 LA < [h/K]]
Σ D - =0 mod 2]
1/2
For any position = K mod K, learning the value function requires fitting parity of K variables (as well as an AND clause) task that is notoriously challenging for gradient descent (Barak al., 2022). In contrast, for any position h K mod K, learning the value function only requires learning AND clause. Thus, we hypothesize that there is broad training regime in which a value function trained via gradient descent will approximately have the following form:
1pn 0]
if K mod K
((Na)) Q2//K1-MI[ya 0 <
[h/K]
1/2
k mod K. (13)
1/2
otherwise
32

---

Published as a conference paper at ICLR 2026
If this is the case, then ActionLeveIRS will make mistake at each position h = K - mod K with probability 1/2, and will therefore be exponentially unlikely to find any reward-1 response- let alone sample from the distribution x¹ over reward-1 Whheees VGB may be able to automatically use the values at positions h = K mod K to correct earlier errors (this is not a priori obvious from the theory, since (v1:s)) / satisfied, but formal theoretical guarantee can likely be proven under Eq. (13)). This intuition is borne out by the experiment- where we train V as discussed below.
can be infinite, so Assumptions 4.1 and 4.2 are not technically
Value function training setup. We use the same network parametrization as in the ABC task, with a separate network for each generation length (and true rewards at length H). We train each network with Adam for single epoch, with 10a batches of size 128 and learning rate 0.001, on the MSE loss from the batch of Monte Carlo roll-outs. We checkpoint the value functions every 1000 batches.
Evaluation protocol and results. We set K
and vary M E (8, 9, 10). For each N E {1000, 2000, ..., .000), after training the value functions for N batches, we draw 100 samples each from VGB and Actionl onveeelRs and we record how long each algorithm takes on average (in wall clock time), and how many steps it used. If the algorithm takes longer than 1 minute to generate single sample, we call that sample a timeout, and we track the number of timeouts. We repeat the experiment for K Results are shown in Figs. 5 and 6.
(this time with N E {5000, 6000, .... 14000} for computational reasons).
We see that after early checkpoints, VGB robustly improves upon octionLevvelee in all metrics, with increased benefits for larger K and M (and therefore larger horizon H)). To illustrate the source of this improvement, for K = 5 and M = 8, we visualize the error in the trained value function each position h E [H] (Figure 7). As theoretically predicted, training is substantially more efficient at positions h = 0 mod K than at positions h = -1 mod K. VGB improves upon ActionL RS in the regime after the value function has been learned at positions h = 0 mod K but before the value function has been learned at positions h = -1 mod K.
E.4 DYCK GRAMMAR TASK
Task setup. The basic setup for this task follows Botta al. (2025). Define A := [,,, P, S}. Define prompt space X' == A and response space y == AT We de- fine reward function r* X x + {0, 1) where pair (x, y) E X x y has reward if and only if it has the form xy = B$1:32E where $1:32 E 3 lies in the Dyck grammar for {G),
We train a transformer-bee based language model Trer on a distribution of strings in X' y that have reward 1. This distribution is designed so that square brackets appear with probability 0.8 whereas round parentheses appear with probability 0.2. Following Botta al. (2025), tokens "P" and "S" are extraneous tokens that do not appear in the training data and are not present in reward-1 strings. 19
While Trer typically achieves high reward on in in-distribution prompts, as we will see subsequently, there are out-of-distribunt prompts on which it achieves low average reward. These are the prompts on which we will train value functions and use guided samplers.
Value function training setup. We train separate value network for each generation length E [H. The network parametrization is the same as in previous tasks except the hidden layer has width 64 (this was not tuned, but simply chosen to mitigate overparametrization since the input layer has much larger width than in previous tasks). Each network is trained for 40 epochs on 10, 000 Monte Carlo roll-outs, using the Adam optimizer with learning rate 0.003, weight decay 0.1, batch size 32, and the MSE loss. We checkpoint the value functions at the end of every epoch.
Accuracy/diversity tradeoff: protocol and results. First, we fix the length-17 17 prefix
= BBCO (C(CC(C)CC
which was randomly chosen subject to the constraint that Tref has low success at producing reward-1 completions, i.e. (- [r(rr'((]])) (Ir, 3)] is small. We train value functions, via the procedure described above, on Monte Carlo rollouts from this specific prompt. For e E {1, 3, 5, 10, 40), we draw 3000 completions of this prompt from VGB, using the learned value function checkpointed at e epochs of training. For this first experiment, we do not use the true rewards, so the algorithm may produce
19ts is consistent with practical I.IMs: the vocabulary typically includes few unused token IDs. Our results show that VGB robust unseen, irrelevant tokens in the vocabulary.
33

---

Published as a conference paper at ICLR 2026
K 4, M
8
K 4, M
K 4, M 10
VGB
VGB
VGB
ActionLevel
ActionLevel
ActionLevel
10a
10
10*
Wall-clock time (s)
10"
109
10a
10-1
10-1
10-1
2000
4000
6000
8000
2000
4000
6000
8000
2000
4000
6000
8000
10a
VGB
10a
VGB
10a
ActionLevel
ActionLevel
Step count
20
10
10
VGB
10a
10a
10a
ActionLevel
2000
4000
6000
8000
2000
4000
6000
8000
2000
4000
6000
8000
0.7
VGB
0.7
VGB
0.7
VGB
ActionLevel
ActionLevel
ActionLevel
Fraction of time-outs
0.6
0.5
0.5
0.5
0.3
0.3
0.3
0.1
0.1
0.1
2000
4000
6000
8000
2000
4000
6000
8000
2000
4000
6000
8000
Training batch
Training batch
Training batch
Figure Efficiency of VGB and ActionLevelRS at finding reward-1 response Parity task (Appendix E.3) with K 4 and M E {8, 9, 10) (so that H E {32, 36, 40}), across training checkpoints E {1000, 2000..... 9000} of the value function. We cap the time draw a single response at 60 seconds. Top row: wall-clock time (in seconds), conditioned on not timing out; middle row: step count, conditioned on not timing out; bottom row: fraction of time-outs. For each M and each training checkpoint, we report mean and standard error over 100 samples drawn from each algorithm. We plot wall-clock time and step count on a log scale to make evident that the multiplicative benefit of VGB over Act octionLevelRR increases with M.
34

---

Published as a conference paper at ICLR 2026
K = 5, M
K= M 9
== 5, M 10
ActionLevel
101
10
101
Wall-clock time (s)
10a.
10a.
VGB
10a
VGB
ActionLevel
Action
6000
8000
10000
12000
14000
6000
8000
10000
12000
14000
6000
8000
10000
12000
14000
VGB
ActionLevel
Step count
10a
10
10a
VGB
VGB
Levil
Letie
10a
10a
10a
6000
8000
10000
12000
14000
6000
8000
10000
12000
14000
6000
8000
10000
12000
14000
VGB
VGB
VGB
ActionLevel
ActionLevel
ActionLevel
Fraction time-outs
0.10
0.08
0.08
0.08
0.06
0.06
0.06
0.04
0.04
0.04
0.02
0.02
0.02
0.00
0.00
0.00
6080
8000
I0080
12000
14000
6000
8000
10000
12000
14000
6000
8000
10000
12000
14000
Training batch
Training batch
Training batch
Figure Efficiency of VGB and ActionLevelRe at finding reward-1 response Parity task (Appendix H.3) with K 5 and M (8, 9, 10} (so that H E {40, 45, 50]), across training checkpoints N E (5000, 6000. 14000] the value function. We cap the time to draw a single response at 60 seconds. Top row: wall-clock time (in seconds), conditioned on not timing out; middle row: step count, conditioned on not timing out; bottom row: fraction of time-outs. For each M and each training checkpoint, from each algorithm. We plot wall-clock time and step count on a log scale to make evident that the multiplicative benefit of VGB Act iinneveeee eveIRS increases with M.
report mean and standard error over 100 samples drawn
35

---

Published as a conference paper at ICLR 2026
0.5
h-5
h-10
Conditional training error
h-15
h-25
h=30
h-35
0.3
h=4
h=9
h=14
h=24
0.1
2=
h-34
2000
4000
6000
8000
10000
12000 14000
Training batch
Figure 7: Visualization of training error for value function at each position h [H] in Parity task (Appendix E.3) with K == and M 8, across training checkpoints of the value function. For each h [H] we compute the probability that ActionLeveIRS makes mistake at position h of generation, on average over 100 roll-ins 91-h-1 π Since ActionLevelRS would never make mistake with the true value function Vüne. this quantifies the effective training error each position (while producing more informative visualization than directly measuring MSE, as this metric is appropriately normalized across h). For clarity, we only plot positions -1,0 mod K.
incorrect completions. We do the same for VGB-Momentum, actionLeveIRS, the base model Tref- Block Best-of-N, and Block Rejection Sampling. For the latter two algorithms, we sweep over block lengths in {1, 2, 4, 8, 16} and of candidate blocks in {2, 4, 16, 32.
The results comparing VGB against the baselines summarized in Figs. 8 and We see that after the first few epochs, VGB achieves an accuracy/diversity tradeoff outside the Pareto frontier of Block Best-of-NV and Block Rejection Sampling. While we do plot ActionLevelRS on these plots, we remark that is comparable to Block Rejection Sampling with block length 1 and 32 candidate blocks. See Table for a breakdown of the results for all baselines, including ActionLevelle and Trer itself, when using the value function trained for 40 epochs. We observe from this table that the result "query-equalized", i.e. we are allowing the baselines as many (in fact, slightly more) queries than used by VGB.
The results comparing VGB-Momentum against the baselines summarized in Figs. 10 and 11. In these figures we only compare against baselines with # of candidate blocks in {2, 4, 8}, since these the baselines with competitive query efficiency VGB-Momentum
Distributional comparison: protocol and results. In this experiment, using the prompt as before, and varying the training epochs over {1, 5, 10, 40). we draw 1000 samples each from VGB, VGB-Momentum, and ActionLevelRS, this time using the true rewards at the last position so that each algorithm only produces reward-1 generations (as discussed previously, this requires restarting ActionLevelRS if it gets stuck). For each algorithm and epoch, we compute the empirical histogram of where open parentheses/brackets are located in the completion. To estimate the ground truth histogram, we draw 10000 samples from R² (i.e. from Tref conditioned on reward 1). We then compute the & error of each histogram compared to the estimated ground truth. For statistical power, we repeat the experiment for 11 other -fit----iittiittioon prompts. As shown in Figure 12, for all epochs > 5, VGB achieves robustly lower distributional error than however, VGB-Momeen 1--Mmmmtmummmmmm is comparable to Action evvels.. While OutcomeLeve (i.e. sequence- level rejection sampling from Trer) would yield exactly the correct distribution, see that this naive method is less query-efficient than VGB. See Table 2 for prompt-by proompt prompt breakdown the results training epoch 40.
36

---

Published as a conference paper at ICLR 2026
Pareto Frontier of Block Best-of-N
Epoch 1
Epoch
140
120
100
80
60
40
20
140
distinct correct
100
80
40
20
Epoch 10
Epech 40
140
120
80
60
20
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Accuracy
Figure 8: Accuracy (x) and diversity (y) of VGB vs. Block Best-of-N on Dyck grammar task (Appendix E.4) with pre-trained base model and value function trained for varied number of epochs. Each circle indicates performance of the baseline with specific hyperparameters (block length {1, 2, 4, 8, 16) and # of candidates {2, 16, 32}); darker red indicates larger block length.
37

---

Published as a conference paper at ICLR 2026
VGB
Pareto Frontier Block Rejection Sampling
Epoch 1
Epoch
140
120
100
80
60
40
20
140
distinct correct
100
80
40
20
Epoch 10
Epech 40
140
120
80
60
20
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Accuracy
Figure 9: Accuracy (x) and diversity (y) of VGB vs. Block Rejection Sampling on Dyck grammar task (Appendix E.4) with pre-trained base model and value function trained for varied number of epochs. Each circle indicates performance of the baseline with specific hyperparameters (block length {1, 2, 8, 16) and # of candidates (2, 16, 32}): darker red indicates larger block length.
38

---

Published as a conference paper at ICLR 2026
Pareto Frontier of Block Best-of-N
Epoch 1
Epoch
140
120
80
60
20
Epoch 3
Epoch
distinct correct
120
100
60
40
Epoch
140
120
100
80
40
20
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Accuracy
Figure 10: Accuracy (x) and diversity (y) of VGB-Momentum vs. Block Best-of-N Dyck grammar task (Appendix E.4) with pre-trained base model and value function trained for varied number of epochs. Each circle indicates performance of the baseline with specific hyperparameters (block length 21,2,4 4, 8, 16) and # of candidates {2, 4, 8). to equalize query complexity): ; darker red indicates larger block length.
39

---

Published as a conference paper at ICLR 2026
VGB WGB-Momentum
Pareto Frontier of Block Rejection Sampling
Epoch 1
Epoch
140
120
80
60
20
Epoch 3
Epoch
distinct correct
120
100
60
40
Epoch
Epoch
140
120
100
80
40
20
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Accuracy
Figure 11: Accuracy (x) and diversity (y) of VGB-Momentum vs. Block Rejection Sampling on Dyck grammar task (Appendix E.4) with pre-trained base model and value function trained for varied number of epochs. Each circle indicates performance of the baseline with specific hyperparameters (block length E {1, 2, 4, 8, 16] and candidates {2, 4, 8). to equalize query complexity); ) darker red indicates larger block length.
40

---

Published as a conference paper at ICLR 2026
Algorithm
# Candidates
Block Len.
Avg. Steps
Accuracy
# Distinct Correct
BlockLevelBoN
136.000
0.975
VGB MGB-Momentum
77.617
0,964
120
BlockLevelBoN
16
272.000
0.957
BlockLevelBaN
16
272.000
0.941
10
BleckLevelBBN
544.000
0.936
VGB
393.471
0,932
137
BlockLeve1BoN
32
544.000
0,926
BlockLevelBoN
544.000
0.924
25
BloNkLevelBoN
272.000
0,902
BlockLeve
32
544.000
0.899
BlockLevelBer
2
136.000
0,880
41
BlockLeve Bo
68.000
0.868
79
BlockLeve BoN
16
272.000
0.762
BlockLeve e
136.000
0.726
32
544.000
0.693
132
BlockLevellf
32
4
544.000
0.645
140
BlockLevelBer
68.000
0.644
78
BlockLeven e
544.000
0.596
lockLevelle
272.000
0.591
132
B BlockLeve MekkLeelBBN
32
16
544.000
0.584
130
BlockLever evelRR
32
16
544.000
0.580
137
Act ActionLevelRs
17.000
0.580
132
BlockLeveIRS
272.000
0.568
BlockLeveIRS
16
272.000
0.561
135
BlockLever e
16
272.000
0.552
131
BlockLeveIRS
32
544.000
0.546
129
BlockLeve e
136.000
0.527
lockLeeelne
136.000
0.498
BlockLever eveeeeell
8 136.000
0.492
114
BlockLever evelRS
4
136.000
0.451
124
BlockLeveIRS
68,000
0.430
125
BlockLe evellBN
68.000
0.407
BlockLeved BeolBeN
34,000
0.381
109
Bl lockeeee
8 136.000
0.377
112
BlockLewe B
16
16
272.000
0.355
116
BlockLeve evelRS
272.000
0.355
LockLevelP
68.000
0.339
68.000
0.257
107
BlockLeve
68.000
0.238
105
BlockLeve B
34,000
0,236
79
BlockLevelle
34.000
0.207
BlockLevelBe
16
136.000
0,206
106
RockLevelRR
8 68.000
0.199
102
B BlockLever evelRS
16
136.000
0.197
112
BlockLev evlelss
34.000
0.158
BlockLen eckeevellee evelBoM
34.000
0.153
BlockLeve1R?
34.000
0.114
85
BlockLeve
16 68.000
0.113
73
BlockLevelle
68.000
0.113
BlockLeve e
34.000
0.089
BlockLevelle
34,000
0.073
BlockLevelle
2
16
34.000
0.059
64
evelBNN
16
34.000
0.054
55
Wref
17.000
0.028
43
Table 1: Detailed results for accuracy/diversity tradeoff experiment in Dyck grammar task (Ap-
pendix E.4) with value function trained for 40 epochs. BlockLeveIBoN denotes Block Best-of-N and BlockLeveIRS denotes Block Rejection Sampling.
41

---

Published as a conference paper at ICLR 2026
Average Steps (L)
Distributional Error (J)
Prefix
Tref
VGB
ActionLevelRS
VGB
276.303
314.998
0.485
0.327
403.232
330.082
0.536
0.179
426.003
437.812
0.344
0.187
442.204
396.146
0.416
0.283
505,481
445.886
0.347
0.149
608.796
410.510
0.475
0.387
639.817
422.092
0.364
0.272
670.543
462.700
0,435
0.259
706.200
508.182
0,409
0.263
739.038
446.574
0.265
0.176
852.620
378.564
0.239
0.193
981.361
440.922
0.324
0.300
Table 2: Prefix-by by- preffix breakdown of distributional comparison experiment for Dyck grammar task (Appendix E.4) at epoch 40, sorted by the average steps used by Tref to produce correct generation. On each prefix, VGB achieves lower distributional error (compared to Wref) than ActionLevelRs. and on 10 of 12 prefixes uses fewer steps average than Tef-- See Figure 12 for the aggregated results for all epochs.
2500
Histogram error (t:)
0.45
ActionLevel
Leve
VGB VGB-Momentum
2000
Letien
Step count
VGB
1500
VGB-Momentum
0.35
1000
0.30
500
0
5
10
15
20
25
30
35
40
0
5
10
25 Training epoch
20
30
40
Training epoch
Figure 12: Distributional comparison between VGB, VGB-Momentum, and baselines in Dyck grammar task (Appendix E.4), across training epochs for value function, and using true rewards at final position. Left; Error of histogram of open-bracket positions (not distinguishing between square and round bracket types), using PetcomeLevel1R to estimate the ground truth. Right: Average step count. The experiment was independently repeated for 12 OOD prefixes (chosen randomly subject to the constraint that Tref has accuracy in [0.01, 0.1]). and we report mean and standard error-see Table for the prefix-by-rrefis results.
E.5 PYTHON TEST CASE GENERATION TASK
Task setup. Let meef be the pre-trained language model (wen2.550055 which has token space A of size roughly 150,00 000. We set = 32 and define the response space to be A so responses fixed-length (however, in this task the prompts may have varying lengths). Following Botta et al. (2025), we define a distribution over prompts as follows. Pick random three-letter function name (we draw from pool of 10 possible names). The prompt first gives an in-context example of test case generation: (1) the Python implementation of the addition function f(a b) a + b, (2) a text prompt to produce test case for f. and (3) a valid random test case for f. The prompt then gives the Python implementation of the list append function, but with the random function name, and asks for a test case for this function. define reward function that checks if the response is a valid Python test case (in the desired format), 20 See Figure 13 for an example prompt and correct response.
More precisely, the reward function parses each line the response and returns reward there exactly one valid response. Of course, there are many other reward functions that may be natural (e.g. at least one valid response) but we did not explore these possibilities. We used the parser developed by Botta et al. (2025) for this purpose.
42

---

Published as a conference paper at ICLR 2026
def f(a, b): return a
List test case of the above function f, in one line: assert f(7, 7) == 14
def (v, item):
assert (1) is list (item) return
10
11
12
List 1 test case of the above function in one line:
assert ovs ([3, ,2], "asd") [3 "asd")
Example prompt and reward-1 completion for Python test generation task (Ap- pendix E.5). See Botta et al. (2025) for additional details on prompt distribution.
Figure 13:
Value function training setup. Since this task has large alphabet size, training value networks on one-hot encodings of generations infeasible. Instead, we train a single value network that can be applied to generations of any length h E [f]] We generate dataset by drawing 50, 000 prompts from the distribution described above; for each prompt I, we sample a response from Tref and evaluate the reward. We then pick random index h ~ Unif ( 2, 2,.., lv }), and compute J. Ei= Φ(x, Vi:s), where p(x, 31:1) is the final-token hidden state at the penultimate layer of Qwen2. 5-0. 5B.
...
Since the hidden states of Qwen2. 0--0 896 as well. fully-connected with a single hidden layer with 8 neurons; first activation function is ReLU and the second activation function is sigmoid. We train the value network on the dataset described above for 100 epochs using the Adam optimizer with learning rate 10-4, weight decay 10-4, and batch size 100.
5- 5B have dimension 896, the value network has input dimension
Evaluation protocol and results. We draw 1000 fresh prompts and sample a completion for each prompt from VGB and ActionLevelRs, using the true rewards at the last layer. We also sample completion for each prompt from n². We compare the empirical distributions produced by VGB and ActionLevelly
that of x² using three metrics: (1) the histogram of lengths of the final Python list each generated test case, (2) the fraction of strings in the final lists the test cases (the most common object type an integer, and the second most common is a string; the remaining types have negligible occurrences, so this essentially tracks the histogram of object types), and (3) the fraction of distinct final lists in the generated each algorithm compared to n"; (3) is measure of diversity, and from examination we saw that " had greater diversity than both algorithms. We repeat the experiment for independent seeds (the dataset generation and value function training are independent as well), and in Table 3 we report the mean and standard error across seeds for each metric.
cases. For (1) and (2) we compute the error of
E.6 LETTER AVOIDANCE TASK
Task setup. Let Trer be the pre-trained language model Qwen2. meen2.5-0.. as in the preceding task. We set H 32 and define the response space be A where the token space for the language model. We fix a prompt, which asks the model to generate sentence without using the letter "e" (Figure 14), and we define a reward function that checks (1) the letter "e" was not used (in the response), and (2) the EOS token for the language model was not used. We find that Tree only produces reward-1 responses out 10, 000.
It has been previously observed by Botta al. (2025) that the final layer does not necessarily lead to the best performance. We did not tune the layer index, since our gnal is compare different guided sampling algorithms, optimize the end-to-end pipeline.
43

---

Published as a conference paper at ICLR 2026
Algorithm
Length hist. error (1)
Type hist. error ())
Frac. distinct generations (f)
VGB 69.7500 (7 (7.9782)
0.0172 (0.0018)
0.3741 (0.0033)
ActionLevelRS
92.2000 (6.6375)
0.0157 (0.0031)
0.3700 (0.0036)
Table 3: Distributional comparison of VGB and ActionLevelRS for Python test case generation task (Appendix E.5). For each metric, we evaluated based on 1000 reward-1 generations from each algorithm. We repeated the experiment with 20 independent seeds and report the mean and standard error (in parentheses). While ActionLeve IRS outperforms the discrepancy is within the standard error. We hypothesize that VGB achieves better distribution over test case lengths since there likely substantial hetcrogeneity in the difficulty of generating different lengths, leading ActionLeveIRS to have a biased distribution.
on the histogram of types, note that
Generate one sentence story without using the letter 'e':
Vicky is having party and wants to buy two hamburgars. A sub sandwich costs $1.00 and ravioli costs $3
Figure 14: Prompt for letter avoidance task (Appendix E.6), and an example generation from naive locally constrained decoding (i.e., ActionLeveIRS).
Value function. this task, we do not train a value function. Instead, for a E
0.3, 0.4, 0.5), define
Note that with eetionLevelRS, all of these value functions are equivalent, and induce standard algorithm for constrained generation called locally constrained decoding (Scholak al., 2021; Lipkin et al., 2025): each generation step (z, 91.h). the next token yh-1 is drawn from Trer(: xr, Mach) conditioned on the event (x, 91+++1) = 1. However, these value functions are not equivalent for VGB, as they essentially vary the probability that VGB will backtrack.
Evaluation protocol and results. With the prompt shown in Figure 14 and for each (0.1, 0.2, 0.3, 0.4, 0.5], we draw 1000 responses from VGB using V.. We also draw 1000 re- sponses from LnteelleeelRRS using Vo,1 (as we discussed above, the choice of a irrelevant for ActionLevelRS) Recall that in implementation of ActionLevelRS with large alphabets, draw K = 32 candidate tokens at each generation step, and sample proportional to their estimated values. Since in this setting the estimated value can be exactly 0, this be ill-posed. We implement two natural heuristics for dealing with this: the first is to simply draw K = 32 more candidate tokens, which increments the step count (we simply refer to this algorithm as ActionLeve roughly comparable to sending K + oo); the second is to restart the response from the beginning (we refer to this algorithm as ActionLever "stuck" if the base model, conditioned on some prefix, puts almost all mass on tokens containing the letter "c". This is why the step count of ActionLeveIRS has higher mean and standard error than LetioneevelRS-Resee (Figure 16).
since it is
We remark that the first method can get
We evaluate VGB against ActionLevelRS and ActionLevelRS-Rese using two metrics. The first metric is winrate according GPT-4o-mini: given 1000 completions from two algorithms, pair up the completions and ask GPT-4o-mini to judge which is more coherent, using the prompt template in Figure 17. We present the two completions in random order avoid (positive primacy bias. The second metric is the average horizon- normalized log- aeg-rrbbbbiltyy of the completions (conditioned on the prompt) as computed by Qwen2. 5-1 5B. See Figs. 3 and 15 for the comparisons with Action eveeeRR and average step count of each algorithm; see Figure 16.
negative)
respectively. For completeness, we also plot the
To quantify how the benefits scale in H. repeat the experiment for H {8, 16] (this time only evaluating against ActionLevelRS for computational reasons). As shown Figure 18, we broadly that VGB has larger benefits for larger H, particularly in the (horizzn-normalizeed)) log-
44

---

Published as a conference paper at ICLR 2026
Eval (norma lized) log propro
-3.2
VGB
ActionLevel-
-3.3
Winrate
0.50
-3.4
0.45
Action evel Reset
-3.6
VGB
0.10
0.15 0.20 0.25 0.30 0.35 0.40
0.45
0.50
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
Backtracking weight for VGB (a)
Backtracking weight for VGB (a)
Figure 15: Comparison of VGB against ActionLevellS-Reet for letter avoidance task (Ap- pendix E.6). with H 32 and varied backtracking weight a for VGB. Left: Winrate VGB against ActionLevelRS-Rese under pairwise comparison of 1000 responses from each algorithm, using GPT-4o-mini to judge writing quality. We report the 95% binomial confidence intervals. Right: Horizon-normalized log- bog-robbaiilities of generated responses, evaluated by Qwen- v.en-2.35 2-5-1. 5B; for each algorithm, we report the mean and standard error over 1000 responses.
300
250
ActionLevel
ActionLevel-Resst
200
150
100
0.10
0.15
0.20
0,25
0.30
0.35
0.40
0.45
0.50
Backtracking weight (a)
Figure 16: Step count comparison for VGB against ActionLevelRs and AetiioneeeeRR-Reeeeee for letter avoidance task (Appendix E.6), with H 32 and varied backtracking weight for VGB.
probabilitics the winrate increases from H/ = 8 to H 16 but seems roughly comparable between H 16 and H 32.
E.7 ADDITIONAL EXPLORATORY EXPERIMENTAL RESULTS
Value function parametrization matters. In the Dyck grammar task, we saw that the single-line change from ActionLevelRS VGB-adding a probability of backtracking-rohuee accuracy across training epochs. In this case, the value function was trained on the concatenation of one-hot encodings of the partial generation. In the code generation task, this parametrization is infeasible due to the large token space. Instead, the value function is trained on the mcan-pooling of the hidden states (in the base model) of each token in the partial generation. Again, VGB has robustly higher accuracy than Action ectionLevelRs But if the value function is trained on the hidden state of just the last token the partial generation, then this effect disappears (Figure 19). While in principle the last hidden state should encode all relevant information about the partial generation, this finding suggests that in practice may heavily attend to recent tokens thus, some benefits of backtracking-baat based algorithms can be contingent exactly what features they trained on.
improves
Momentum improves the query complexity of VGB. A classical method for accelerating Markov chains like VGB is to add momentum, which decreases the likelihood that the chain will "switch directions" (from going down the tree to going up, and vice versa) while preserving the stationary distribution. Hayes and Sinclair (Hayes & Sinclair, 2010) theoretically investigated the benefits of momentum specifically for the Sinclair-eerrum walk, and showed that it provably improves runtime the approximate counts are (1 + o(1))((cccuuaaae acccuraee (specifically, the accelerated chain mixes to क in time Ey H² under Assumption 4.1). We implement this Markov chain (with the practical tweak of stopping it as soon as reaches a leaf), and find that it improves the query complexity of VGB by nearly an order of magnitude, while achieving comparable (or higher) accuracy (Table 1).
45

---

Published as a conference paper at ICLR 2026
are a writing quality judge. You will be given pair text fragments. Say ONLY 'A' the first fragment is more coherent, or ONLY 'B' if the second fragment is more coherent.
Fragment A:
Fragment B:
Figure 17: Template of prompt fed to GPT-4o-mini for winrate computation in letter avoidance task (Appendix E.6).
However, it does not enjoy the same distributional benefits as VGB (Figure 12), suggesting potentially fundamental statistical-comes computatiionlll tradeoff.
Backtracking can help throughout generation. One might wonder whether e.g. backtracking only helps the last position, where the value function is likely most accurate (or even perfect, if the true rewards are being used). In Figure 20, we demonstrate that for the Dyck grammar task, for prefix where Actionl ActionLevel! early in the generation sequence: the most common eror indices are {4, 5, 6, 8) out of 17. Moreover, Figure shows that these errors can detected early: conditioned on particular index for see that the average estimated value at subsequent indices rapidly drops
achieves average reward roughly 0.5, often makes mistakes fairly
first error in a generation, off (compared to the average estimated value for sequences where ActionLevel makes no error). Thus, is (at least a population level) possible for backtracking be useful before reaching the leaves the generation tree.
46

---

Published as a conference paper at ICLR 2026
0.575
0.575
0.575
0.525
0.525
0.525
Winrate
0.475
0.475
D.475
0.450
ActionLevel
0.450
ActionLevel
0.450
ActionLevel VGB
0.425
0.425
0.425
0.3
0.4
0.2
0.3
0.4
Eval (normallieed) log-prob
-3.0
-3.0
-3.0
VGB
VGB
VGB
ActionLevel
ActionLevel
ActionLevel
3.4
3.4
3.4
-3.6
3..6
33.6
-3.8
-3.8
-3.8
-4.0
-4.0
-4.0
4.2
4.2
0.1
0.2
0.3
0.4
0.5
0,2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
300
VGB
ActionLevel
ActionLevel
ActionLeve!
200
25
20
150
15
10
50
0.1
0.2
0.3
0.4 0.5
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
Backtracking weight for VGB (a)
Backtracking weight (a)
Backtracking weight (al
Figure 18: Comparison of VGB against ActionLevelRS for letter avoidance task (Appendix E.6) with varied horizon H {8, 16, 32). Top row: Winrate of VGB against ActionLevelRs under pairwise comparison of 1000 responses from each algorithm, using GPT-4o-mini to judge writing quality. We report the 95% binomial confidence intervals. Middle row: Average horizon-normalized log-pre prebbabbailisies of generated responses, evaluated by Qwen-2. 5-1.5 5:B for each algorithm, we report the mean and standard error over 1000 responses. Bottom row: Step count comparison; we that the average step count for actionLevelle is higher at H 16 than H = 32 due to an outlier generation that required 148251 steps.
47

---

Published as a conference paper at ICLR 2026
0.800
0.775
Accuracy
0.725
ActionLevel
VGB
0.700
0.650
10
Window length for input features
Figure 19; Window length of mean-pooled input features for value function (x) against accuracy of VGB and ActionLevelRS (y) for Python test case generation task (Appendix E.5). We repeat the experiment for 3 independent seeds and report the mean and standard error. All algorithms generate at most 32 new tokens per prompt, so window length 32 corresponds to mean-pooling over all tokens generated so far (the method used for the main experiment in Appendix E.5). We never pool over the tokens in the prompt.
Position
Estimated value pesition
None
10-1
6 8 10
12
14
16
Position completion
Figure 20: Average estimated values (y) in the Dyck grammar task (Appendix E.4), by position of first error (hue) and position completion (x). We pick a single prefix and value function trained for 20 epochs. We generate 1000 completions using ActionLevelRS and record the estimated value each step of each generation, as well as the first position in the generation at which a mistake has been made (i.e. it becomes impossible complete record this as "None". For each of the most common error positions (4, 5, 6, 8, None). we plot the average estimated value each position of the completion. We see that errors early the completion can be witnessed (at least, at population level) well before the final position.
valid string); if the generation is correct,
48

---

Published as a conference paper at ICLR 2026
Part II
Proofs and Supporting Results
F PRELIMINARIES
In this section, we collect standard results that will be used in our proofs.
F.1 PROBABILITY THEORY
Definition F.1 (Probability divergences), Let p. q be distributions on common domain X, with & q. The -diierggne from p to is defined as
p(w) 27 g(w)
Dx- (1
wmy
The KL-divergence from p to q is defined as
log M(w) g(w)
DKL () == E
The total variation distance between p and q is defined as
p(w) ((w)
Drv(p. q) =sup p(A) {(A)) woog
A
Proposition F.1 (Divergence inequalities (Sason & Verdú, 2016)). For any two distributions p, a common domain, with p < 9, we have
2 DTv(p, a)² <
Lemma F.1 Let n E N and A (0, 1/2). Then
(Bi(Bin 1/2), Bin(n, 1/2 + A)) 2(AVn).
Proof. Let == Bin(n, 1/2) and := Bin n, 1/2+ A)) Then
1 ((X)
Drv(p. 2
E X~p
p(X)
E 1 (1 (1-
X~p
E 1 11-(1 11-11)1pp0 x3)x(1 -
X~p
2 E
[1 11 A) -)m-2 2X 1[X s n/2]
X~p
2 E 1-e- (n- 2 T[X < n/2]
X~p
E min((n 2X) 1)1[X s n/2] X~p
using the fact that 1- e $/ min(t, 1) for all > 0. follows that
Div(p.9) 3 X~p
mnn 1)[[X & n/2 vnl Z min(A/n,
where the final inequality is by standard anti-concentration bound for the central Binomial distribution (Matoušek & Vondrák, 2001, Proposition 7.3.2).
Lemma F2. Let p, q be distribations on a ffintte domain X and let & C X be an event. Then Drv(ple.gle) < DTv(p.g) ((E)
and
(p || 4)
Dx=(ple gle) 5 ((E) 2
49

---

Published as a conference paper at ICLR 2026
Proof. We have
p(x) ((x)
DDiv(ple.gle)
Σ ZEE
P(E) 9(
1
p - (())] +
1
1
Σ
p(a)
((E)
(1E) ((E)
DEE
=EE
1
Σ (p(x) ((0)
(v()) ((8)
((E)
((8)
((() - ((8)
Σ DEE
(p()) - [(0))
((E)
((E)
Σ
[p(x) - ((>))
+ 9(E)
Σ
ppxx) - ((x)
9(E)
3EE
xERE
2
Drv(p.9)
(E)
which proves the first claim. For the second claim, we note that
Dx² (ple (1
1
Σ (((x) (1- ((E) p(x)
Eq(x)
9(E) 3E
D(E) g(x)
(()) Σ q(x)) (1- p(x)
(1 -11-1166 9(E)
p(E)2
q(x)
P(E)
JEE
((E)
xx² (p 9).
p(E)2
Now observe that by the data processing inequality, (p(E)-g(E)) ((E)
I Dx= || q). and therefore
(p(E) ((8)) S Vo(E)D (p |l q). follows that p(8) 2 ((E) Vv((E) x || g), and so D2 || g)
(p
(pe gle) N (g(E) - (E(E) 1)) 7)22 ((E) 2
where the first inequality requires Dx= g) (E) (the final bound is vacuous if this is false, holds unconditionallyy.
Lemma F.3. Let T E N and E 8 > O. and let Zi....,
......... Zr be nonnegative random variables with
Pr|Za S for each E [T]. Then
T
T
2
Pr
74
<
81-
T
2
T 1=1
1=1
Proof. Define the random variable N := #(i 2,
<
8). Then E[N] < Σ Ei so
Pr[N 5 -T fi. Moreover, N T/2 then
T
Z: 2 8/2 as needed.
F.1.1 MARKOV CHAINS
We present several basic definitions and results from the theory of Markov chains. See Levin et al. (2009) or other standard references for additional background.
Definition F.2. A Markov chain P on state space X' is reversible with stationary distribution if. for all u, X, it holds that
P(e u)p(u)= = P(u w)p(t).
Definition F.3. A Markov chain P on state space X is irreducible if. for all u, E X. there exists t 2 such that Idt (u v) > O. The Markov chain is aperiodic if. for every u E X, the GCD of {t > 1: P(u u) 0} is 1. The Markov chain is ergodic if is both irreducible and aperiodic.
50

---

Published as a conference paper at ICLR 2026
Conductance is standard measure of the bottlenecks in Markov chain, and is formally defined as follows.
Definition F.4 (Conductance). The conductance of Markov chain IP with stationary distribution defined as
Φ> =
min
SCT.Dc((3SS1/3
where
Øg = EngS.vgs (())P(e) u)
Enes
We recall the following fundamental result that relates the conductance with the mixing time of the Markov chain. This result can be derived from Cheeger's incquality, which relates the conductance of Markov chain its spectral gap: see e.g. (Montenegro Tetali, 2005, Chapter 3) Theorem 2.1 and the proof of Theorem 1.2 in Liu (2023).
Theorem F.1 (Conductance implics mixing in x²). For any ergodic reversible Markov chain P with stationary distribution ii and conductance 4, for any initial state z and any t E M,, holds that
xx² (P' (.12) (I Se- 421/2 ((2)
(14)
F.2 KL-REGULARIZED REINFORCEMENT LEARNING
In the KL-regularized setting introduced in Section 2, the optimal KL-regularized value function Q (e.g., Rafailov al. (2024); Xie et al. (2025)) is often defined via the following inductive procedure. For step H, we set Q7 (z, y1:H) == r* (x, 31:H). Then, for
1....,1:
(1.x) = sup PEA(A)
E Uh+1ip
Q0((,, B11+1)] - B DKL (p Trer (vh+1 = (2,
(15)
= log
[exp( 3- (3,
(16)
Eq. (16) can be viewed soft Bellman update; as B - 0, this update recovers standard dynamic programming (over those actions for which Trer(Un44
x, (1:h))) > 0). The optimal policy satisfies (3 x. 11sh--) Trer x. 11:h-11 exp( ( Br.h)). and we further define Ag(x; y1:h) == Q3 y1:h)) - Q3 (x, (1:h-1 1 as the optimal advantuge function. can be checked that with the above definition, Q3 also satisfies
(2(2, V1sk) = 3 log
E yh+ (aan)
[exp(3 (00- (r.
(17)
The following standard fact relates KL-regularized regret to KL-divergence to the optimal policy.
Lemma F.4 (See (Foster et al., 2025, Lemma F.4)). Fix any E X and क X - A(V). It holds that
Js(m" Jo Jo(A;z)) ( x) || x=(( x)).
F.3 VALUE FUNCTIONS
The following lemma states the key property of the true value function Vin which relates it to the next-action conditional probabilities .² This identity has been observed previously by, e.g., Yang & Klein (2021). We will use this fact throughout the paper.
Lemma F.5. For any X, h E [H], and Uish E Ah, it holds that
(a, Vi (z. V1:h-1)
x *"hh (1:h-11)) = Frer(yh (1.hhsh))
51

---

Published as a conference paper at ICLR 2026
Proof. We have
x (yrah (x)= =
Σ
<"h:nn ())
W
Σ
(T)
Trer(Vish (x)
E (T v1:H) vial
Viile(2) (2)
(yech (x)
V
iin (2, V1s)).
(x)
It follows that
x (Y1::h x)) = Trer xx, V1sh-1
Visie (1, Vi:h)
π (8h 2, 21
TT" (1 xx)
Vilte (2t, (1hh-1)
as claimed.
F.4 APPROXIMATE REJECTION SAMPLING
We present a guarantee due to Foster et al. (2025) for (a slight variant of) rejection sampling, which used implement OuteomeLevelRS, and is used as subroutine ActionLeveIRS and the full (large-[AA) version of VGB.
The only difference between this algorithm and the standard rejection sampling algorithm is that automatically estimates the normalization constant for the target distribution so that the rejection threshold can be set purely as a function of the density ratio between the target and base.
The basic setting is that we have sample access base measure μ A(Z) and query access to a tilt function g : + R20. and we would like to sample from the distribution with density proportional to (2). The algorithm pseudocode is given in Algorithm and the guarantee is given in Proposition F.2. We remark that Foster et al. (2025) consider the case where g(z) > (=p(33f(22) for function f Z R and temperature parameter 3 > 0, motivated by KL-regularized optimization), but the algorithm and guarantee extend unchanged to the setting where s(=) 0.
(specifically, they write g(2)
Algorithm 5 Rejeecioonampliing variant of Sof toofteeeeeetctiomSmmmllll (Foster et al., 2025)
input: Function g : Z - R, base measure μ A (Z), rejection threshold M 0, failure probability (0, 1).
Let N 4M log( (..
/* Estimate normalization constant */
2: Sample .I, i.i.d.
3: Set 2 = N -
Rejection sampling */
4: for iteration i = 1,,. N do
5: Sample 2 ~ pl-) and Ber(min (s(=)/2M, 1)).
6: If = 1, return
7: return u(-).
// Failure event; occurs with low probability.
Proposition F.2 (Guarantee for Algorithm 5; see Foster et al. (2025)). Let g Z ++ R be given, and define
π (a(:))
(2) x p(z)) g(2), and C.a
(18)
Fix å E (0, 1), and fix any M 2 4Co.. Then there is event E that occurs with probability at least
1 - 6, such that the output z E Z of Algorithum with inputs (g. p. M, 8) satisfies
PP|= = 1 = x())
52

---

Published as a conference paper at ICLR 2026
As a consequence. the unconditional law of satisfies DTv( T) S 6. Moreover, if [1, G) all E 2, then DKL || T) I 45 (4MG log(4/6)) The total number of sampling queries y ~ p and function evaluations g-)) used by the algorithm is at most 8M log(46 +1.
Proof. See (Foster et al., 2025, Lemma E.1).
53

---

Published as a conference paper at ICLR 2026
Algorithm 6 OutcomeLevelRRS Outcome-Level Rejection Sampling
Input: base model ref: tilt function т, prompt x E X, threshold M > 0, error & > 0.
1: Sample yı.H ~ peejectiionSmmlinggrrr. Teor(- 2)), M).
>> Algorithm
2: return 1/:H-
Algorithm 7 ActionLevelRs Action-Level Rejection Sampling
Input: base model reer; appx. value function V, prompt E X' Additional input for large-[AA regime: threshold M 0, enror E 0.
2: for < h < H do
Small- | regime: explicitly compute μ4 E (AA) defined by
n4 (yn) x (ye xr, v1: (ar, vr.),
and sample 14h- Large-[A] regime: sample
Algorithm
yh ~ RejectionSampling(2 ()) Vi 1), M, M/H/).
3: return y1:H-
G OMITTED RESULTS AND PROOFS FROM SECTION
In Appendix G.I, we give formal pseudocode and analyses for the baseline alignment algorithms OutcomeLeveIRS (Proposition G.1) and ActionLevelRS (Propositions G.2 and G.3), which were informally introduced in Section In Appendix G.2, we show that if the approximate value function satisfies Bellman consistency, then ActionLevelRS avoids eπrо compounding (Proposition G.4). In Appendix G.3, we show that any algorithm that does not have access to a process verifier must incur similar time complexity OutcomeLevelRR (Proposition G.5).
G.1 PSEUDOCODE AND ANALYSES FOR BASELINE SAMPLING ALGORITHMS
We formally describe and analyze the baseline sampling algorithms OutcomeLevelRR and ActionLevelRS, in the general test-time aligument setting where Tref : X + y is the base model, T X' y R> is the tilt function, and given ø X' we would like sample from the model x² defined by π (y x) x Tyer(y T)((x, y). We also give specialized analyses for the KI.-regularized setting where (Ix, y) exp(3-11p 1 v))-
Formal pseudocode for baseline algorithms. See Algorithms 6 and 7 for pseudocode of the versions OutcomeLevelff and ActionLevelRS that we theoretically analyze below. We remark that the versions that we implement in experiments differ slightly Appendix E.
Analyses of baseline algorithms. Recall that we defined the sequence-level coverage coefficient and action-level coverage coefficient for prompt or
π x) x)²
T² (Uh
Ir, 1/1k-11)
(z = max yEy (r
and Coct = max max kE[H] Visk E. Tree (1/h I, (1:h-)))
Proposition G.1 provides a guarantee for OutcomeLevelRR. Proposition G.2 provides a guaran- tee for ActionLeveIRS in the large-|A| regime, and Proposition G.3 provides guarantee for ActionLeveIRS in the small-|AA regime.
Proposition G.1 (OutcomeL evell)). Given prompt x and parameter e > 0, let #(. ()) be the output distribution of OutcooeeLeelRS((Teee (Teet T, x, 4Csea(2), Then
Div(f(-) a)) <² x)) s.
(19)
Moreover, in the special case where T(x, v).)) = exp(3- (00(8-11*(a) (x vl.)) for some r* : X y [0, Raax) and B > 0, it holds that
Jo(x);²) (F( S (Rnax +
log (4/s))) e.
(20)
The algorithm uses (x)) log(e-1)) reward evaluations and generations y Fref(: (r).
54

---

Published as a conference paper at ICLR 2026
To interpret the second guarantee, which bounds the KL-regularized regret of the law of OutcomeLeveIRS, note that a natural parameter regime is Rnax = (e.g. binary rewards) and 3 I 1. In this case, it holds that ==(==:z) J x) I O (og(Can(x1)).. Note that (2e (z) can in practice he exponentially large in H; however, since the time complexity of OutcomeLeveIRS only depends logarithmically on e, in this regime one can achieve ;=(x";;) -#; while paying only a factor of (og(H/s) in the time complexity. In any case, the time complexity is dominated by (1))
Proof of Proposition G.I. The first inequality Eq. (19) and the efficiency guarantee both follow immediately from Proposition F.2, using the choice of M and 8. The second inequality Eq. (20) follows from Proposition F.2 together with the choice of M and the algebraic equality
(1()=;)) Ja (f: x) 3Dku(F) x²), which shown (Foster et al., 2025, Lemma F.4).
Proposition G.2 (ActionLeveIRS; lrre--AAl regime). Let V be an approximate value function with
((r,y1.)) Vine(a,
max
S
V(r, yi:k)
for all h E [H]. The output distribution 7(: x)) of ActionLeweIIRS(Ters V,x, 4Coct(x) in the
large-IAA regime satisfies
DTv(T(: x)), ( ()) S 2ogg(())
(21)
Moreover, in the special case where 7(z,y1.H exp( 'r (x. y1:H)) for some r* : X y + [0, Raax] and B >> 0, it holds that
J
J)( S (Reax + B (16Cct (x) log(4 & 2HH (22)
In either case, the algorithm uses (x) H log(HE= value function evaluations and generations yh Trer(- x. 11:
To interpret Eq. (22), we remark that if ((x, v1a) = 3 log V v1.k) satisfies 1Ō(z, v1a) - (2, V1:1)l EQ for all x, Yish. then the condition of Proposition G.2 is satisfied with exp(eq/8) (),, and if Ranx B, Cact (x) O(1) then Eq. (22) reduces
J=(m²; x:) - J2(R; x) & Õ + c H).
While the term can be efficiently reduced by increasing computation, the term Eq H. is inherent for this algorithm, as we will see later.
Proof. We have (by the fact that TV-distance is metric and satisfies the data processing inequality) that
H
DTv(2(- | x)), x x))
E (1--1~
[Dvv(Rn( | v. Vi:h 1)) (: 11:b
(23)
h=1
where :n( x. 1/1.hhhh1 1) is the marginal distribution on ya under 7(- x, 11: and similarly for .- Fix any h E [H] and condition on /1:h-1- We invoke Proposition F.2 with base measure p(yn)= = Fret (yr x. 11: and tilt function g(um)= = (ar,yaa Define E A(A) by (Jn) x ((, V..).. It holds that
VI, v1.h) EniEd ((1)) V (2t, Vi:h-1, 9%)
max EEEA
Vine (x, V1:h)
S n max EA
Σ EA u(3h ) Vine (x. 11
V (I, v1:h)
n² max
nn EEA Σ EgAEA EAA x *3(h/
x. 81:h V Vinne(a 11:h-1)
x" (3/
x, 11:h-111)
x² max
Un EAA Troe (yh
< 2 (x)
55

---

Published as a conference paper at ICLR 2026
where the inequality is by the assumption on V, the second and third equalities are by Lemma F.5, and the final inequality is by definition of (z). Thus, M 2 4 Drv(ax (-1 2, Mi:h 1), T) - 8 = H. Moreover, we have
so Proposition F.2 gives that
DTv(T, I (1,11:11))
(T ( I. v1:))))
T(hh)
max log V UEEA
nt ("
2, 111h-1)
(ee v. Vi:h (i:n- (z. vi:h)
Eneer Ed Trerlths 2, bi 11:1- v/1)
max log yn EA
Tre z, 11:.--1 vish) Egses Tree (Vh x, W. 11:h
$ logg
by Pinsker's inequality and the assumption on V. It follows that
S E + Vllg H
DTv(TA Vi 1), 7 vlib-1))
Substituting into Eq. (23) completes the proof of Eq. (21).
The proof of Eq. (22) proceeds via an analogous argument but starting with the chain rule for KL-divergence:
H
DKL(f(- (f(- 1I x))
Σ
E (()
[DKL 2, 1ish-1 ( (1)--1))) (24)
Fix h E [H] and condition on 91-A-1- As before, the conditions of Proposition F.2 are satisfied, but in this special case, the proposition also gives a bound on the error induced by Algorithm in terms of KL-divergence, instead of just TV-distance:
DKL (T Ir (1:h x) < 4 R + log(16Caet log(4H//)))
As before, we have
(wn)
max log nn. E.A
< 2 log
** x. 11:h-11
follows that
(KL( x. 91.h 1) T x. 11:h-1))
π T(U))
(
f1:h (1:1111111111
E log (1/n
ma ( ((awwhhs)))) 4 (Rnax + log (z)r² log(4H/2))) logg(::)
2. 11sh-1)
Substituting into Eq. (24) and applying the fact that [a(T=(z) Jo(F;a) 3Dku (f( x)) (+ x)) (see (Foster al., 2025, Lemma F.4)) gives Eq. (22).
In the small-|AA regime, we avoid the error incurred by approximate rejection sampling, but retain the main error term incurred by inaccuracy of the approximate value function (and incur time complexity scaling with [A).. We omit the proof as is a strict subset of the argument used to prove Proposition G.2.
Proposition G.3 (ActionLeveIRS; small- AAl regime). Let V be an approximate value function with
(a,
max
(1,
V(a, vinh)
SK
56

---

Published as a conference paper at ICLR 2026
for all h E [ The output distribution A(- x) of ActionLewe V,2) in the small-|
regime satisfies
DTv(f(- x), ( < 2
(25)
Moreover, in the special case where T(r, (1:11) = exp( 100033-~'(as vI:H)) for some r : X y [0, Rmax] and B >> 0, it holds that
Ja(m";a) - Jo( S 2H log(k).
(26)
In either case, the algorithm uses A() evaluations of V and conditional density queries to Rref-
G.2 ACTION-LEVEL SAMPLING FOR CONSISTENT VALUE FUNCTIONS
In order to better appreciate the advantage of VGB, it helps to consider the case when the approximate value function V used by ActionLeveIRS is in fact the (exact) value function for some policy f.. This condition equivalent to a Bellman consistency condition, which is the formulation we use below, and it can arise if V is an implicit value function: that is, if it is implicitly defined via
(yh v14h-1
Vx, MIa) V (xx V1-h-1) Traf (yh. x V1:h
for an explicity-learned policy मे (this is essentially rephrasing of the basic equality from Lemma F.5).
In this case, ActionLevelRS is simply sampling from the distribution म (up to the error due to rejection sampling), and the closeness of गे to x² depends only the multiplicative ratio between V and Vilte and not on H.
There is empirical evidence suggesting that implicit value functions may be more effective at fine- grained action-level guidance than explicit value functions (Liu et al., 2024c). The following result, contrasted with Proposition G.2 and the failures discussed in Section 3, provides theoretical explanation for this observation. Moreover, it provides another perspective on the advantage of VGB: it can achieve comparable results for explicit value functions as ActionLeveIRS achieves for implicit value functions.
Proposition G.4 (ActionLevelRS: Improved guarantees for consistent value functions). In the setting of Proposition G.2, suppose that the approximate value function V additionally satisfies Bellman consistency: for all E X, h (H), and y1:h-1 E An-1
= Σ
(ye 11.h-11) (a, v1:h).
ULEA
Then the output distribution R( x) of ActionLevelRS satisfies
DTv(f(: 1-), S / logg()).
Proof of Proposition G.4. From Bellman consistency, we have that
(I.h))))= B Soter (-x.gn m) V(. v1-H)),
E
so V is the value function for the tilted distribution
- A()) defined by #(ynH | x)) x Trer (Vi-H) x)) (x, H1.H). Then Lemma F.5 applied to के gives
#(n I. 91:h-1) Trer (3h, ( V1:1).
We now analyze actionLevelle using this fact. Fix any E [H]] and condition on 1/1h-1- We
invoke Proposition F.2 with base measure (1(a)) = Tree (3h. x., 11)h-1) and tilt function g(v))
Vx, )1 We define æ E ((A) by T(y) x (uyy)) ((., v1.)). ). As in the proof of Proposition G.2, get that ( x, V1-h-1), 1), T) S E/H. But I, 11.b-1). i.c. the conditional distribution of yh. under 7( x, 11.b-1). Therefore
observe that coincides with 7
H
Drv(7( x)) 7( (x) <
Drv((A(( x, Wi-h-1): (- x. Fi:h 11:h-11)) )) S E.
57

---

Published as a conference paper at ICLR 2026
We now observe that Drv(T(- x), x- (+1x))) - DKL x) TT( x))
[ xx)
max log
wi π (11.11 x))
Vi Y1.H)
Eviney Viite v(.H)
max log BIE
Vine V1:H)
Eviney Vi (iHH
S /2lg
by the assumption that the multiplicative ratio between V and Vün is bounded by x. (see the statement of Proposition G.2). The triangle inequality for TV-distance completes the proof.
G.3 LOWER BOUND FOR OUTCOME-LEVER ALGORIHTMS
The following result shows that time complexity dependence on the sequence-level coverage coeffi- cient Czea (z) is unavoidable when only outcome-leve rewards are available; the proof is standard but included for completeness.
Proposition G.5 (Lower bound for outcome-level algorithms), Consider the KL-regularized opti- mization setting, where the algorithm only has access to Tref, 8, and r* (but no value function). Let
X = { and y == {0. 1} H. and set ref == Unif For any C [1,2 2H, set B == log(C). Any algorithm that satisfies Ja( (+( S Flog(C) for all instances with (x) S C must
use least N (CC) reward evaluations. Similarly, any algorithm that satisfies Dry (x 7) S 1/4 for all instances with (zeq(z) < C. must use al least N = QCCC) reward evaluations. 22
Proof of Proposition G.5. Without loss of generality, assume that C' is a power of 2. Fix X and y = {0, 1)"; we ignore the dependence on henceforth. Let Tref = Unif())). We construct a random instance of the alignment problem as follows. Set 3 == 1/ log(C) and let C y be uniformly random set of size 10 2d /C. Define rv) = Ily E S), and let Tī' be the desired distribution, i.e. (y) x Tree (y) exp( (3 (2)). Then
Z = Σ (re e (v))
10
C+ 1- )) 1 [1].
c
NEY'
Therefore for any E ,,
n (g( (e)r
= exp(3-1r'(1)) SC
Z
and hence this instance satisfies the desired bound (zea I on the sequence-level coverage coefficient. Let ft.s (Q)) be the law of the algorithm for this instance.
Consider also the "null" instance in which r"() := 0 for all y E V. Let 7. E A(Y) be the law of the algorithm for this instance. The desired distribution for this instance is m Wref-
Suppose that the algorithm uses at most N S C/40 reward evaluations. Then on average over the choice of S, the probability that the algorithm observes any reward-1 generation is at most 1/4. Thus, there is some specific such that the probability that the algorithm observes reward-1 generation is most 1/4. For this S, it holds that Drv(ãs, * < 1/4.
We now consider the two cases of the lemma's assumption: either the algorithm is accurate in TVV- distance, or in KL-regularized regret. We show both are impossible under the preceding assumption that N < C/40.
1. If DTV Rss #3) < 1/4 and DTv( Fret) < 1/4, then DTv(TT Trot) 3/4. But Teer (J\)S) 1 - 10/C 2 0.9, whereas T3' S) S 1/Z < 0.1. Thus DTv( Trer) 2 0.8, which is contradiction.
Formally, this result holds in the "sample-and camplle-anderee and-e-uuutteeee model of computation (Huang et al., 2025a;b), where Trer and r* are initially unknown to the algorithm, and can only be accessed through black-box reward evaluation queries r" (xz, v) and generation queries y ~ Feef z))
58

---

Published as a conference paper at ICLR 2026
2. Similarly, suppose that J)( S) < 1/g C) and J I
1/(8 log C), where Jz(:; is the KL-regularized regret for the instance parametrized by S, and Ja(::o) is the KL-regularized regret for the null instance. It follows from (Foster et al., 2025, Lemma F.4) and choice of ,3 that ( || x3) S 1/8 and DKL (#. || m²) S 1/8. From Pinsker's inequality, get Drv (Tv(#s, 33) 1/4 and (TV mt) I 1/4. The proof concludes as in (1).
This completes the proof.
59

---

Published as a conference paper at ICLR 2026
H OMITTED RESULTS AND PROOFS FROM SECTION 3
In Appendix H.1 we provide computations omitted from Examples 3.1 and 3.2. formally proving that ActionLevelRS incurs S2(1) TV-error in Example 3.1 and Q2() KL-regularized regret in Example 3.2. We also demonstrate that NutcomeLevelRs requires exponential time in these examples, and that ActionLeveIRS achieves exponentially poor coverage over ' (in contrast with the guarantee of Theorem 4.2 for VGB).
In Appendix H.2 we demonstrate that Example 3.1 can be adapted to the KL-regularized setting.
H.1 DETAILS FOR EXAMPLES AND 3.2
Details for Example 3.1. The calculation of Vün is straightforward from the definition
(vne = ET* (T(1:)) vinn]
Moreover, by construction it clear that
E [1/(1 Ev), εv] for all yish-
Note that Unif( {a, 6)")) whereas the output distribution ß of ActionLevelRS is product distribution that puts mass (1 + ev)/(2 + ev) on a for each coordinate.
First, we lower bound Drv(#, m² By the data processing inequality and Lemma F.1, we have
Div(i, x²) 2
1/2), Bin ev) Ev)) 2 ((min((vvH,11)
as claimed.
Second, observe that (1er(y1 3 for all V1-H E V, whereas x² (a,a...., 2 Thus, Cseq 2 (3/2) so OutcomeLeveIRS requires H))( time in this example.
Third, in the regime Ev ((1), show that ãे does approximately cover n' (in the sense of Eq. (7) in Theorem 4.2). Suppose without loss of generality that H is even, and let & C y be the set of yI.H that contain at most H/2 occurrences of a. Defining A = Ev <v/(4 28v), we have for any
91.H E & that
(VI:H)
= (1 A) (hagn =a) (1 A)" --##(bp < (1-A3)) 12) = exp( πt (y111)
since A (evvv) = -()).. It follows that for some constant c= d(v)).
n (Wi.)) 7()r:))
> exp(ett) 2 2m = 2'
Pr y1: mot
i... has exponentially poor coverage of a constant fraction of the mass of x²*
Details for Example 3.2. We calculate that the optimal regularized reward is JØ(=*) = Q2((3)
log((1 + e) e)) For the distribution मे produced by ActionLeveIRS, clear that मे Tref
Un0 1), and hence
1
Ja(T') - - J=(=T) - ET... [r* (VI.H) = log((1 + e)/2)
=
2
(27)
2 10
claimed. Next, observe that T² Ber(1/2 + 0 for some A 2(1), whereas
= Frer = Ber(1/2) Thus, the fact that OutcomeLevelRS requires exp()((H) time follows by analogous argument in Example 3.1, does the fact that ActionLevelRS fails approximately
cover nr
H.2 KL-REGULARIZED ABC EXAMPLE
Example H.1 (Failure of ActionLevelRs with approximate Q7)- Consider the following construc-
tion for EQ E (0, 1] and H N. We have single prompt X' = (1) (henceforth we will omit the prompt from the notation) and action space A = {a, b, c). We define fref Unif(fa, b, cf H) and r* (yi:H) = Ifc & y..H}- Then it can be checked that
(o(mn)) = Bog (1 -h - 1)I[(c & vnaal)
60

---

Published as a conference paper at ICLR 2026
Let us define
Q(vnn) = Q3((an) + tEQ
yf
(2((1:)) otherwise
Then ActionLeveIRS with approximate value function ((yaa) = exp(8-1Q(1ns)) satisfies Ja(T²) - (+ 2 M(min(sq, B) H).23
Details for Example H.1. We first derive the expression for Qg- For any vn:h E A c y1ah. then
(yn:) 3 log E Ee*"[ (expp(8"r""((0
Vraal Bog
since r"(y""( (y1.1)) will almost surely 0. On the other hand, if & Vish, then
Q (vr.) = 3 log E E (oxp((( (y1:H)) ) yaal
3 log
exp( + (1 (2/3) (h)
log (1+ (cxp)= 1))
Thus, it holds for all yısh E AAh that
(v(1a) = 3 log (1 (2/3) (2/3)
1)1lic $ y1.1l)
as claimed. Next, we observe that by construction, @ (v)=:)) S Eq for all E [M] and Yich E AA, It remains to verify the lower bound on KL-regularized regret. By (Foster al., 2025, Lemma F.4) and the chain rule for KL-divergence, we have
J
Ja(
m.6 Σ Tis (Tx( (1:4-1) (
91a--1))]
(28)
Fix [H] and condition on V1:h-1- We consider two cases.
1. Suppose that c E V1-h-1. Then exp((B-((7(Lna)) = 1 for each yn E A. so 7.(( 11th-1) is uniform over A. However, exp(B e (v).))) = exp(sq 'Tyy = a)), so (a x. v1:h-11 = e5018/(2 + 2 1/3. It follows that
DKL 11 ( 11:h-1)) 1
6F0/ /(2 (2+ cFa/ +
log
2 (mmin(Eq//B.1) 1)). (29)
1/3
2. Suppose that c & 91-h-1 Then =++ (2/3) -1)l(y, # c). On the other hand, exp((-1Q((nal)) = exp(3 exppeen = a)). Therefore
DKL (. V1:h-1) T V1:h-1))
1
e= /(e Q2((mm-110)tt/8
.- (3(mmn11,)) + e 1 12 (v))sn)))))))
3 log
1/(e 8- (J + Q-1 + (133((1))
ezq/0 -1
log
1 eaqli +2
3
2 (mmin(s0/3.1)
where the penultimate inequality uses the fact that (3(m)n-1,a) (3 > (7())s-1..).
Substituting into Eq. (28) gives that Jz(x*) - ( 2 M(min(Eq, H) as claimed.
The sequence-leve coverage coefficient is also exponential in H, Csea 2 20(H), and hence OutcomeLeve eve IRS requires exponential computational budget.
61

---

Published as a conference paper at ICLR 2026
Neighborhood A (v)a))
y1:A-1
x (e, vrsh)
each step f, for y Vi:h:
1. With prob. 1/2, stay: y ((+l) yf)
V1sh
1/2
2. With prob. 1/2, move to a neighbor in ((y:=) with weights shown on the arrows
OC Teet V()
V1:h+1
Vi.hr t44
Figure 21: Illustration of execution of VGB each step L.
I OMITTED RESULTS AND PROOFS FROM SECTION 4
In this section we formally prove Theorems 4.1 and 4.2. Specifically, this section is organized as follows. Appendix 1.1 we formally discuss how is implemented in the large- |A regime (Algorithm 8). In Appendix I.2 show that Theorem 4.1 follows from the small-|Al regime, Theorem I.1, We also give a regret guarantce for VGB in the KL-regularized setting (Corollary I.1). In Appendix 1.3 we prove Theorem L.1. In Appendix 1.4 we prove Theorem 4.2.
general guarantee for
We also include a high-level illustration of VGB (Figure 21).
Notation.
Recall that we let denote the autoregressive tree of generations, which has node set U At. We also let (ghh.) denote the neighborhood node Vich in T. In the proofs in this h=0
H
section, we will typically omit dependence on the prompt x, therefore writing e.g. (11:H) instead of Trer (V1.H z). Moreover, autoregressive tree) as well as distributions over the entire tree T. To avoid confusion, we will notate the former Tref, n², H, etc. whereas will other characters for the latter. Thus, Trer (Va:s) refers to the marginal density of Tref E (AA on yı:k. whereas (y)).. refers to the single-point density of E A(T) yl.h.
will consider both distributions over the set A (leaves of the
1.I DETAILED IMPLEMENTATION OF VGB FOR UNIFORM-ERROR RESULTS
In this section we present Algorithm 8, which gives more detailed pseudocode for VGB (compared to Algorithm 1). In particular, Algorithm 8 shows how to efficiently implement the transitions of the random walk VGB via rejection sampling in the large-IAA case. For any node y1:h in the autoregressive tree T. it is convenient to define the following distribution geer( yıa) over the neighborhood ())..)
Definition 1.1 (Unweighted neighborhood distribution). Let v1:h T (so that 0 < S H). We define (ref(- (ia) E (NN(s)))) as follows:
If h 0, then gret (W1:4+1 yiah Tror(ync41 via)) for all 2h+1 A.
If h = H, then quet (Vi-k-1 V1sk) := 1.
I < < H, then giet V1.A) := 1/2 and grot (His441 Wisn) == Trre y1a) for all
Vh-1 E A.
In other words, gref represents a transition kernel on that transitions to the parent node with probability 1/2 (if possible), and transitions to random child node with probaiblity 1/2 (if possible,
62

---

Published as a conference paper at ICLR 2026
Algorithm 8 Detailed Implementation of VGB for Uniform-Error Results
1: Input: Reference model Tref estimated value function V. prompt I E X, horizon H E N,
step count 7 E N. sampling regime ("large- |A|" or (amall-[A|"")
2: Additional input for large-I.A| regime: rejection threshold M > 0, rejection error ôrej E (0. 1).
3: Initialize y ;= Ø.
4: for 0 S ( < do
5: Set := 1/()
6: Set gref Gret(- )))
Definition I.1
7: Let g No Rzo be defined by
(vinh- 1= = Vx,, vith)
and, for all 1h41 E A,
g (v +1+ = Va wish th+
8: With probability 1/2, set g(1 = y else:
Small- A) regime: explicitly compute pdd (V((1))) defined by
(z) x (2) . (z),
and sample ((++1) p(o) Large-|AA regime: sample
> Algorithm
nut + RejectionSamplinggg"" gie M, 8re)).
9: return T
and under the distribution induced by wreF). Notably, sampling from gre( Vy:s) is tractable with single conditional sampling query to Wref- To implement the transitions of VGB step in the l|| case, use RejectionSampling (Algorithm 5) with base distribution grer vio and tilt function defined using V. See Algorithm for details.
1.2 PROOF OF THEOREM 4.1: UNIFORM ERROR BOUNDS
In this section, we state Theorem I. our general guarantee under uniform error bounds-and and use it prove Theorem 4.1. Notably, Theorem I.1 does require exact access to the outcome-level reward r, and also implies regret bound in the KL-regularized setting (Corollary I.1). It requires the following assumption on the multiplicative error of V, which reduces to Assumption 4.1 in the special case that Kleaf = We assume that Kieaf S for convenience.
Assumption L. (Uniform bound on value errors; generalization of Assumption 4.1). Let K. 2 Kleaf 2 For all x E X, h [H], and Visk Ah, it holds that
V(n Vinela, (1,))) Vinela, vish) ((x
max
(30)
Moreover, for all x X and yıh e H it holds that
Vin )1.11) Viite (2t, VieH)" Va vi:H)
max
Kleaf
(31)
We remark that in general, Kleaf can be interpreted as capturing the quality of the estimated reward model, while captures the quality of the estimated value function. If the estimated reward model is perfect, we have that Nleaf = 1.
To state the formal guarantee of VGB under Assumption I.1, we must introduce the following model म, which is defined by tilting Fref by the estimated values at the leaves.
63

---

Published as a conference paper at ICLR 2026
Definition 1.2 (Ideal cotommattion-hhooeette sampling distribution). Let X A()) be defined by Trer H x)) (ax, 91.H)
#VIn x)) = Enin Trer a) (a,
(32)
While it is not generically possible to sample from a distribution arbitrarily close RT when Kieaf > (even
we will show that it is possible to sample from distribution arbitrarily close to (with time complexity of the sampling algorithm scaling logarithmically the sampling error). Moreover, it is straightforward to see that π is close to x² in the sense of coverage:
Fact I.1. Under Assumption I.I, the density ratio between x* and iI is bounded as
# (VI: [x) x² (UL. | xx)
max
(y1. [=) 7(y.: 2)) Kleaf
(33)
for all x E X and 91.H E AA
We will show that VGB can be used to sample from a distribution that is close to म. in x²-divergence (Definition F.1). Note that the output of VGB is node of T. which may or may not be leaf node, whereas T (and π²) are distributions over leaf nodes. However, the following result demonstrates that VGB produces leaf node with reasonable probability, and that conditioned on this event, the output distribution is close to т.
Theorem L. (Main accuracy guarantec under uniform errors). There an absolute constant C4.1 with the following property. In the general test-time alignment setting (Section 2), suppose that Assumption 1.1 holds with parameters Rieaf Z Fix x E X, T N, and & E (0, 1), and ler V E (T) be the distribution of the output y of Algorithm with inputs Tret, V, x. H, and T, in the small-|AA regime.
Let & be the event that |y- = H. IfT 2 C4.1 H log(kH/s), holds that
1
u(E)= 2
(34)
8kleef
and
(ule |1 (T) Se.
(35)
The proof of Theorem 4.1 from Theorem 1.1 is largely straightforward. The main technical detail is to extend the accuracy guarantees to the large-|AA regime, which we do by approximately coupling the execution of VGB in the large-I-A) regime to its execution in the small-[A] regime.
Remark 1.1 (Hyperparameters for rejection sampling in large-|A] regime). We remark that in the large-IA) regime, as shown in Algorithmm 8, VGB formally requires two additional hyperparameters (which were omitted from the statement of Theorem 4.1), in order to use Reject SnnnsnnnSnmmmnn (Algorithm 5) to implement transitions in the random walk: (1) a rejection threshold M and (2) an error tolerance drej- In the proof of Theorem 4.1 below, we assume that 5, Caet and εv are known, and moreover M == (Cact(x) + Ev)² and ôrej := (16((1 + ey
e HTT). In the practical
implementation of VGB, we use a heuristic approximation of RejectionSampling that only requires single hyperparameter see Appendix E.I.
Proof of Theorem 4.1. We observe that under Assumption 4.1, Assumption I.l is satisfied with : + EV and Kleaf := 1. Also, by Fact L.1, we have मे = π*
First, we consider the execution of VGB in the small-|A |AA] regime (as formally described in Algorithm 8). Invoking Theorem 1.1 with = 82/4 /4, we get Pr[Eteaf] 2 1/(8(1 + ev) and
DTv E T²) S Dya || m+) < 6/2
where the first inequality uses Proposition F.1. The time complexity bound of O(T [AA) is evident from the algorithm description.
We next extend the analysis to the large-|AA |AA regime where each transition is implemented using Rejeettionaamling ing (as described in Algorithm 8). Fix some step E [T]. To invoke the guarantee
64

---

Published as a conference paper at ICLR 2026
for RejectionSampling (Proposition F.2), we must bound |p=0) /p=0////2 / bo Suppose that h 1 satisfies 0 < h < H (the edge cases follow by analogous and simpler arguments). We have
pd (V 2p ( 2
ref (21hh22)
and, for any yh E A.
pd (Vishr W1++1)
Vxe Vichiihh 11++1)
Gref 1ihh vh++1)
(6)
1 (vr with) + Eve EA Teoe (vh+1 I. wiih V (2, V 9/-11
x²
VVVin tiu (15, yi 1h++1
(6) + Evhn EA Frre (Wi+1 2, Vish V (z, 1 2 Wiite (I, 11-h
R² V (I, Vi.h 31+11
2 Vine (I, with) + 2 Viiee(o vith)
= x² 'I' (1h++1
x., v1.h)
Tref (V/+1 x, ViAh)
S Cac
where the first inequality is by Assumption I.1, the second equality is by definition of V cilt (Eq. (3)), the third equality is by Lemma F.5, and the final inequality is by definition of Cact()), follows from Proposition F.2 (so long as the hyperparameters in Algorithm are set appropriately-sse Remark L.1) that in the event that Reject erectiin ionSampling is invoked at step f. the distribution g of its output satisfies (Tv ) S (16(11 + ev) Let से denote the distribution of the output y² and let small denote the distribution of the output in the small-]A| regime; then a standard coupling argument gives DTv(ft (ft #maall S 5/(16(1 + Ev H)), and therefore Drv(āle: @smalll ( S 8/2 by Lemma F.2. By the above analysis, we have DTv (fsallmllll x²) S 8/2, so we get DTv g, x*) < as needed. The time complexity bound claimed the theorem statement is evident from the choice of M (Remark I.1) and the pseudocode for RejectionSampling in (Algorithm 5).
D
Remark I.2 (Large- |Al regime with average-case error bound). A key step in the analysis of Theo- rem 4.1 for the large- [A] regime was to show that every transition can be efficiently implemented with rejection sampling. This required showing that every step I, the desired sampling distribution y²*) has bounded density ratio with respect to a tractable proposal distribution (to invoke Proposition F.2).
Since pld) is defined in terms of V. this in turn requires some uniform assumption on V. Above, we showed that Assumption 4.1 suffices to control the density ratio in terms of the action-level coverage coefficient (and the assumption parameter = 1 + E.).
However, with only the average-case bound Assumption 4.2, is unclear how to make a similar argument work. For this reason, only state Theorem 4.2 in the small- ||] regime. One could easily extend it to the large-)AAt regime by introducing an additional assumption that explicitly controls the density bounds in the above analysis. It may also be possible to avoid extra assumptions via more delicate average-case argument that allows the rejection sampling procedure to occasionally fail. We leave this question for future work.
In the KL-regularized setting, we get the following additional guarantee on the KL-regularized regret (Section 2). We only provide this guarantee in the small- |A] regime, but we believe may be possible to extend to the large-|AA] regime using similar argument as in the analysis of ActionLevelRS (Proposition G.2).
Corollary I.1 (Regret guarantee for VGB in KL-regularized setting). In the KL-regularized alignment setting (Section 2) with lemperature parameter 3 > 0 and reward function y* X x y + |0, Baxx) suppose that Assumption 4.1 holds with parameter Ey O. Fix prompt let A(T) be the distribution of the output y of Algorithm 8 with inputs Tref V. x, H.
X and T E N, and
and T, in the small-IA A regime. Let & be the event that [ = H. Then, for any 8 E (0, 1), if HH2 H² log(s11/8), it holds that T 2 C2 jk
Ja(m"; JI(ples)) B8.
(36)
65

---

Published as a conference paper at ICLR 2026
Proof. As above, Assumption 1.1 is satisfied with 1 Ev and K 1, and ह n². Invoking Theorem 1.1 with EV == 5, we have
==)= - Ja(ule;))
= 3- DKL (ule x²)
S 3 xx (ule x+)
where the equality is by Lemma F.4 and the first inequality is by Proposition F.I.
1.3 PROOF THEOREM I.1: UNIFORM ERROR BOUNDS
This proof largely follows the template originated Sinclair & Jerrum (1989), generalized appro- priately to the test-time alignment setting: we show that VGB implements a reversible Markov chain, compute its stationary distribution, and use conductance argument to bound its mixing time. See also Bakshi et al. (2024) for related but incomparable generalization (using a slightly different random walk).
Fix prompt a E X. Since we will be working with the same prompt throughout the proof, we will drop it from the notation in the remainder of the section, and define quantities that implicitly depend on z. In particular, we will write Vein((1::)) == Viiee (2, vi:h), (yy:a) = V(r v1sh), and Tref (Vi:A) == rref (31:h
zz) as shorthand.
Recall that T is the tree with node A U.... A H and with edge set defined by setting the parent of Vi.h to be /1.h-1. For w, v E T, we will write ~ v if w and are adjacent in the tree, i.e. if one the parent of the other as defined above.
In order to prove Theorem I.1, we will use standard notions from the theory of Markov chains, such as reversibility, stationary distributions, and conductance. For detailed introduction to Markoy chains, we refer the reader Levin et al. (2009).
Definition 1.3, For any Yı.h E T with O, define
11 (ynsh V1:h11 V (yrsth Tree(yy:hh Define Markov chain P on T where, for any u, T, the probability of transitioning from v to is
[(v.w)
if w if = otherwise
2 Ew flowor)
PP(w] () =
1/2
Note that this Markov chain exactly corresponds to step Algorithm (in the small-[A regime). Definition I.4. Define μa E A(T) by
p(u)= = Z₁ wET:wwe
Σ
f(u, w)
where Z₁ -EVET EWET f(u w) is the normalizing constant.
The next lemma shows that the Markov chain P is reversible with respect to (Definition F.2).
Lemma L.1 The Markov chain P is reversible with stationary distribution p.
Proof. Recall that for w, E T with w ~ v, the transition probability is
f(v, w)
P(w ()) 2 2ww'n f00 f()
Hence
1 1 f(v,w)) S(.
f(e,w) w) 2 2n f(v,w()
f(v, w) 22,
((v)P(w1) ( v)
Z w'ne
By the same calculation with and w swapped,
((w))P(v w) = [(w, v)
[(V, w)
22,
27,
66

---

Published as a conference paper at ICLR 2026
using f(u, f(w, v). Therefore ((t)P(W) b) = p(w)P(e) w) for all adjacent w. verifying detailed balance and hence reversibility with stationary distribution μa.
We begin by showing that the stationary distribution μ has sufficient mass on the leaves of the tree and the root of the tree. The first part a specific claim Theorem I.I; the second part is important in bounding the mixing time of the random walk in Algorithm 8, since it starts at the root node of the tree.
Lemma 1.2. Under Assumption 1.1, it holds that for
Σ
ply1:H)
2
(37)
2n H
and
m(0) 2 2x²H
(38)
Proof. We observe that
Σ Σ
[(, =
Σ
Tear (Vr
U= wET:oNe
FIR EAH
Σ
Trei ( (1ne))
Kleaf
MIN EAA"
V (2))
filef
where the final equality uses Eq. (3), and
Z
Σ Σ
f(e, w)
TET wETwow
H
Tre (
h= Bisk
H
2x
Traf Ve
b= Vith
2xHH (e)
again using Eq. (3). follows from Definition I.4 that
Σ p(yL.)
Σ Σ
f(e, 2 2x H
Z5 o= EA wET:wse
UI "
which proves Eq. (37). Similarly, Eq. (38) follows from the fact that
Σ ((0,a) Σ
Trer (a)
Σ
Tree (a)
(()
R
K6
BEA
aEA
aEA
together with the previously-derived upper bound on Zy.
In order to bound the mixing time of the Markov chain IP, will bound its conductance (Defini- tion F.4).
Lemma L.3. The conductance & of the Markov chain satisfies
1
(39)
4x2 H
67

---

Published as a conference paper at ICLR 2026
Proof. Let S _ T be any subgraph with 0 s(S) < 1/2. Suppose that Ø 8. We know that u(S) Σ μ(T 5), and thus &s 2 TrYs. We have Ø & A... Hence, it suffices to prove that Ø3 2 1/(8x2 H) for all S TT with 0 < (u() and 2 S.
Fix any 5 S with 0 < p(S) and Ø S. Let St, . Sy be the (maximal) connected components of S in T. Then
Tith
Σi= EuES (u))(u) u)
Σ EmEs u(u)P(u u)
2 min Ss. RE(R
E Eves, u(u)
E
n(u)
where the second equality uses the fact that if E S₁ and v E S for + j then u of and so P(v u) = 0. The above inequality implies that it suffices to prove 4g 2 1/ 1/88 H) for all connected subgraphs 5 T with y(S) and Ø & S.
Fix any connected subgraph S C T with 0 < ((S) and Ø & S. Let v :- Vith be the shallowest node in S. Then v + Ø, has a parent = y1.h-1- Moreover, since S is connected, every v' E 5 is descendant of v. Hence,
S m())P((
Here, we use the notation o' 3 to denote that is an ancestor of v. Using the definition u(w) 2, ET ow [w, w/) (Definition 1.4) and the definition of (Definition 1.3), get
f(e,u)
p(v)l(ul
24,
H(1))
Z, E
EVETES EweT: f(v', w)
((v
2 VVVET'' EweTiwne f('',
By Assumption I.I, we have
=r Trat (v) 2 Troe (ree(v)Vinee)))
To bound the denominator, note that f(v', w) (r'r V V deeper node among {v', w. Moreover, for every node u in the subtree rooted v. there are only two ordered pairs (v', w) E 2 with v' ~ w and u = o' V w: namely, (u, u') and (u', u) where u' is the parent of u. follows that
(v' V w) where e' V w E T is the
Σ Σ
f(o',w) 22
Σ
Trer Trer (o')((o' 2K
Σ To
Tree VV
VETW'Se
Combining the preceding displays yields
Tref (ref(u)Viine
ps 2
4x²
EVer Trer ( (V')Vine
Expanding the denominator using Eq. (3), and noting that the depth of the subtree rooted is at most H, we get
1
4s 2
4
It follows that d satisfies the same bound.
Let ( 2) denote the distribution of the Markov chain IP after t steps starting from state 2. We recall the standard result that lower bound on conductance implies that the x² divergence Dye (Pt z) || μ4) decays exponentially in t. (Theorem F. This lets us conclude the proof of Theorem I.1.
Proof of Theorem L.1. Let denote the distribution of the output of Algorithm 8. Then v = PT(
Ø). Note that the Markov chain P is aperiodic since it has self-loops. Since (yra.)) > 0 if and only
68

---

Published as a conference paper at ICLR 2026
if Vann (11:s) O, the chain has positive transition probability between any two nodes (31:A-1, V1-h with π (V1sk. > Moreover, (()1=)) > 0 implies that π (3/1A) > 0. Thus, irreducible on the
support of μ., and hence engodic the support of (Definition E.3). We can now invoke Theorem F.1 to get
Dx²(v 1) S 621/2
(40)
(
Since 1//(0) I 4x2H (Lemma 1.2) and + 2 1/ H) (Lemma I.3), we have for any g' > 0, if T 3 log(n ( H/e"), then
Di-(U p) Ss.
(41)
Set := e/ (8 H: the condition on I' is satisfied so long Ct.1 is sufficiently large constant. Let be the set of leaves of TT Since μ(L) 2 [2 (Lemma 1.2), we have that
1
v(L) 2 ((L) (Tv(U, (L) Ve
4KFiteaf H
using Proposition F.1, which proves the first claim of the theorem.
Next, by Lemma F.2, Eq. (41), and Lemma 1.2, we have
Dza(y ml)
Dxl l1 pls) M(E) 2 ((E)
2 SE.
(42)
2
Now note that for any leaf y y1:H ET,
uuv)= x f(y1.H111 )1:H) V (ye::))Terr(ln ( #(y1:H)
by Definitions 1.2 and I.4. Therefore pll = मं and so
( || [) S
(43)
which proves the second claim of the theorem.
I.4 PROOF THEOREM 4.2: AVERAGE ERROR BOUNDS
The proof of Theorem 4.2 analyzes the same Markov chain IP as the proof of Theorem 4.1 (modulo returning gd for random t E [T] rather than returning )) but the analysis requires substantially different techniques. In particular, under Assumption 4.2, it is longer true that the Markov chain mixes rapidly the "globally" stationary distribution, since there may be branches of the tree where V is extremely inaccurate. We instead proceed using the machinery of local stationarity / meta-stabillty (Balasubramanian al., 2022; Liu et al., 2024b), which is weakening of fast mixing, analogous to how, in optimization theory, local critical points are weakened solution concept compared to global optima.
For broad class of Markov chains, the sampling analogue of an approximate zero-gradient condition low Dirichlet form condition, which implies that the sampling law "locally" resembles stationary distribution (Liu et al., 2024b). To prove Theorem 4.2, we apply this idea to IP and use local stationarity to show that the marginal distribution of the Markov chain at a random timestep approximately covers the true stationary distribution (which, in turn, approximately covers T²).
As before, we will fix the prompt x E X' and drop it from the notation. Throughout, we will assume that Assumption 4.2 holds with parameter EV, and for notational convenience will write = 1 +++ Ev. Thus, for each h [A], we have the following bounds on V with respect Vinee
Venee (vna))
((n=s) (Vine(Brs))
1) S K.
E=
.E."
(44)
In this setting, it no longer true that every cut has large conductance (with respect to the Markov chain P). We define set of "bad" nodes at each layer of the autoregressive tree T, where "bad" roughly means that the subtree rooted at that node has small conductance, and formally is defined as follows:
69

---

Published as a conference paper at ICLR 2026
Definition 155. Let and h [H]. Define
172
Bl == f1.h E A (Be:
Σ
Teer(Vi ( (VL.))
4x²
Lemma 1.4. For any and [H] it holds that
x (B S 17.
Proof. We know that n' (V1:H) (e) rre (V1.H) Viile (V1:H), and so
1 (o) Arer(y1.k ViiiV (v1:))
. (11:s)
Trer Viite (V1:H)
Vinr (2)
IKILHEAR-
by definition of Vint (Eq. (3)). Thus, for any fixed Vish AA,
E EMALLNAA-n (yer())a)) (vn.m))
Em IT" (y1-H) Pignin) Vitte
(B1:)) (y11))
((yia) x (B/it)
Vinn(H
(WI.)
E" V(nin
Vole(ur:))
1ish
We conclude that
Vine( (B1Ln))
(I1.H) (1i.r)
4x² v7? ((n..) Vine(Mr.))
Pr
WIdA BA.nl
Pr
1x
Mith
Vine(yine)
2x
2x
Pr
Pr Minn
E
1ich
17
Vine(era)) V(naa)
V(n=.) Vine(1)
E=
E=
2%
2x
S
where the final two inequalities are by Markov's inequality and Eq. (44) respectively.
Recall the definition of Markov chain IP from Definition I.3. will often be convenient to interpret as T T matrix, i.e. with P2,, Pyy æ). We will denote by v0 the initial distribution which puts all the mass on the root node 2, i.e. vo (2) = Denote by v == MylP" the distribution of the Markov chain after t steps starting from Py- Recall, from Lemma I.1, that the Markov chain IP is reversible with stationary distribution μ defined by
p(v)= Z₁ WET:iN
Σ
f(u, w)
(45)
where Z5 ;= == Eo f(, w). Furthermore, we have the following lower bounds on (1) the
mass that 1s places on the root node 21, and (2) the mass that μ places on the of leaves A _ T.
Lemma 1.5 is the analogue of Lemma I.2 for the average-case setting.
Lemma 1.5. The stationary distribution μ satisfies u(Ø) 2 H/(2x² and u(AH) 2 1/(2x²11) Furthermore, it holds that Z, 2V (2).
Proof. First, we observe that
Z = Σ f(u,w)
Σ
Σ
TreF( ((r.a)
NET WET:WN
h= V1.n EAA
(
= = (Ø)
Σ
E
((
h=1
2VA (2)
70

---

Published as a conference paper at ICLR 2026
by Eq. (44). Next,
Σ
E
Traf (VI.H V ((na.)
Mi:M E.A
Viite
ET
(2)
E=
(2)
by Jensen's inequality (r ~> 1/r convex on (0, oo)) and Eq. (44). follows from this bound and the preceding bound on Z that
p(A E
1
Dz
2x²H
VINEAA
Similarly,
(y1)
V (@)
Σ ((,,n)
E Trof (y)) (e) E=
Vine
BIEA
VIEA
which, together with the bound on z,, implies that u(0) 2 1/k22
For the analysis, we will look at the action of the Markov chain on the space of functions g T IR. Specifically, we will work with the space 2 (1)), which has inner product defined as follows.
Definition L6 (Inner product with respect to the stationarity distribution). For any functions g, g T R we define the p-inner product (g, g') by (g. (.g'), = E2 l9g't 9 Dg' (where D) diag(n)).
Next, we recall the notion of the Dirichlet form corresponding to Markov chain, which can be seen as generalization the Laplacian. This a measure how function varies locally with respect to the transitions of the Markov chain.
Definition L.7 (Dirichlet form). For any functions J.g' T - R, we define the Dirichlet form of g. (with respect kernel P. and stationary distribution μ1) be
E(g.g)=
M())PPu u)(g())) g(v)) (d g((u)).
MUET
The following lemma gives standard expression for the Dirichlet form. The proof can be found in (Montenegro & Tetali, 2005, Section 1.1).
Lemma L.. For any function g : R it holds that
E(g.g) 2(g. (P)))
where I the identity operator.
Rather than directly working with IP as matrix, it is more convenient work with the following similar matrix which is symmetric and PSD due to the laziness of the random walk, as shown in Lemma 1.7.
Definition L.8. Define Q E RTXT by Qny == P(y x) pL()))/)()) so that Q D1/2PD-112 1/2
where = diag(u).
Lemma L.7. The matrix Q is symmetric and positive semi-defiitte.
71

---

Published as a conference paper at ICLR 2026
Proof. The first claim follows from reversibility of P (Lemma I.1):
Qxy PPy 2))(())
P( D)llo) p(x)p(y)
Q yx
u(z)xly)
Since Q is similar to P,, has the same eigenvalues as P (which are real-valued since Q is symmetric). By construction, we write IP = (T PP) where I is the identity matrix and P is the Markov kernel corresponding to the non-lazy random walk (that is, the Markov chain conditioned on moving neighboring state each step). All eigenvalues of any Markov kernel (and in particular, IP') have magnitude at most 1, so all cigenvalues of P lie in j0, 1]. Thus, Q is positive semi-definite.
The next lemma is a key technical ingredient in the proof of Theorem 4.2; it is a local stationarity / metastabillty-tyn bound. It shows that the Dirichlet energy EVv,/ ((vr/u,ur//) must small average timesteps by showing that this form measures the change in x² -i-divergence, See Balasubramanian al. (2022); Liu al. (2024b) for similar bounds and additional references."
Lemma 188. For any T E N, it holds that
T-1 Σ 3
Vr Vr
S 2
Proof. Since Q is positive semi-definite (Lemma 1.7), the square-root of Q is well-defined. Define matrix = D D-1/2Q1/2 11/2 and, for each 0 I S 27, define function St T - R by 9t. = A'
(i.e. for any node gi (v) e, A.) Then, by Lemma 1.6,
Ege, gt) (gt, (I P)
(gt, It) (Age Agd)
= (gt, (gt+1, 9(+1)
where the second equality the fact that o. DIPg: = d6. D2/2QD//22 = AT DAg. Therefore
1 Σ Elge 9:) (go. 90) (g2r, 92r) S (go. 90) Dy3 (vo ll 14)
by telescoping and the fact that
(g2: 921) (") T T
2 20 = (0)) 2p Up = -T. = =Dx2 I) +1
1
for any nonnegative integer t. The penultimate equality uses the fact that DP = PT D by reversibillty. Next, since E(g.,9) 9t) 2 0 for all t, it holds that
T-1 1
Σ
E(g2r 22, p).
Now observe that for any even 2r,
gt A Vo
A D D- vo = 11122 =D- 1o V/ 4
Here, again used the reversibility via Q YQ. Thus,
Σ
< 2D0 1)).
TTeese works use KL-divergence the potential rather than x2 diverrgene, and so they get that E(vr/p, og(v+/p)) is small on average rather than Elvr/u, For our purposes, it will he slightly convenient have hounds on the latter quantity.
72

---

Published as a conference paper at ICLR 2026
To complete the proof we observe that xx |l ()) S _1 v(Ø) S 4H by Lemma 1.5 and the fact that bg only puts mass the root node Ø.
We will use Lemma 1.8 to show that at a typical timestep f, the density ratio v is roughly constant on (most of) the autoregressive tree 7-namely, on the subgraph carved out around the root node by the "bad" sets Br..y The following lemma formally relates the deviations in the density ratios on this subgraph to the Dirichlet energy at a particular timestep.
Lemma 1.9, Let 1j > and fix any r E [T]. Then,
Σ Vi.a E
( (olora)) vx(2)
p(yn:t)) mx0)) 1 S yith & Brool
8HK² 112
E
1/4
1/4 1i
p
Proof. For any h E [H] and yi:h A" \ Brar write V1.h and u 11:h-11-
Then we have
( 1 V1sh)
f(1:s, Vith (1-t-1)((22)))
Σ EminEAR - (((1:H)
Σ EenLHNEA a fV1.H M1:H 11
(Vrr))) (WIn)
2 Σ un II (rer( (yI.H)
n/²
(46)
8n²
where the final inequality is by definition of Br., (Definition I.5). Thus,
2
Σ p(yi.))
1 S H Vish & B
M(YE.))
m())
BIHEAA
(x((11)))
Pr (+((1x-1)) 2 1/vi- & Bu.nl
S Σ p(BI.))
V
H
m(nnss))
(yra & BR.rl
m(vr:))
((vis-1))
S
((yn)) yrsk) (v((k))))
v.(orx-11)
2 1 182ck & Banl
Σ
Σ
112
M(y2=)) p(brak11)
1=1 MLLEAA
k
Vr Vr
{(
1/2
p
p
where the second inequality is by Eq, (46).
The preceding lemma shows that (at timesteps where the Dirichlet energy is small), the density ratios Pr/ p are near-constant on a certain subgraph of the tree (which, via Lemma I.4, we will show is wish to show that v,/n is
"most" of the tree, under the measure of x*). However, ultimately not too small on most of the tree (which we will use to lower bound v,/ / The following lemma
ensures this by lower bounding the density ratio at the root node 2.
Specifically, makes formal the intuition that if (1) the random walk starts at Ø, and (2) the stationary distribution puts reasonable mass on Ø, then the marginal law of the random walk at any particular timestep should put reasonable mass the root-even before the random walk mixes the stationary distribution. This, of course, requires the walk to be sufficiently lazy, which implicitly comes into the proof via the fact that P is similar PSD matrix Q (Lemma L.7).
Lemma L.1. For any non-negative integer t, it holds that (z) 1.
v(3)
73

---

Published as a conference paper at ICLR 2026
Proof. Define 9: T - by g(x) to (a(a)-u(a) Then since Q is positive semi-definite (Lemmal 1.7),
Vu(z)
we have that Q is positive semi-definite and hence
0 S 9 T Q'1
(vD 11) BTDD-1 D'
pp) (vD 11) TP' D (u0 1t)
Ve D Dー'm0 - 11 "TD 11 D- 1 + D-
I vo(u) 1 1 1/ v + 1
yours u(y)
vo(y)
E gm p(y)
where the third equality uses the fact that j PT p. Rearranging terms and observing that po(y)= = 1ly = Ø] completes the proof.
To formally compare distributions on T with nt (which is a distribution on the leaves of T), it is convenient zero-extend n² to
Definition 1.9 (Extension of π* to T). Let jC E (T) be the distribution on T that agrees with n* on the leaves and zero on the internal nodes.
We show that μ² is not too far from in divergeee,, which is equivalent to an average-case density ratio bound:
Lemma 1.1. It holds that
1 Dys(n' 1l s 2Hn².
Proof. We have
n² (V1.H)
1 + D22(1 11)=
p(
n (V1.H) Jyy1:n (1:H.
Zz
E
Yuu
n (" (1r: V(n..)
Z
E
Yiu
Z
Vine(
VAA Vtile (8)
((ham)
< 2H
where the fourth equality is by definition of Vin and the final inequality by Lemma I.5 and Eq. (44),
We can now formally conclude the proof of Theorem 4.2.
Proof of Theorem 4.2. Observe that the distribution td in Algorithm is precisely v for each
0 < f. < T, and moreover the distribution the output is v = E Vt. Set = 5/(6H) and = k Fix any E [T]. Define events F F² F3 A by
F = {ui. : 3h < H, 81th E Br.n
F (vi. v, (vi.H) (()1.)) 1/2].
33 = (yi. μ(y)a))/ (H1.)) < 48'}.
By Lemma 1.4 and union bound over h E [H), we have
Pr
F Hn.
(47)
74

---

Published as a conference paper at ICLR 2026
Next, for any 91:H E F²2 FF, observe that y1.H satisfies
VolUnn) P(VL.)
v.(0)) 1 S H Vish & BR
2-11
>
(((3))
2
4
by definition of the events F F and by Lemma 1.0. It follows from Lemma 1.9 that
Pr Drpe
[(0 = H) A A
F))
32HR²
Vr
Vr
(48)
n
#
Therefore
Pr WI: E E [=( Pi:re
Pr
[[|b] = H) ( F² Ft]
onpp
1=¹ (2)
||||= H HAVE [ F4]
E
emp
puv)
Dx²(1² 11) Pr
8HKR²
Pr V/ E
(49)
where the first inequality is by Eq. (48). Finally,
and the second inequality is by Lemma I.11 and
n (VI.H) m(II.))
1
Pr ME
[VT- E FF
Pr PI---
S
(50)
48'
by Lemma 1.11 and Markov's inequality. In the event that neither of F2, F3 occur, we have (y(.H) 2 28'x" (H)sH). Thus, by Eqs. (47), (49) and (50),
(v(.))
8Hk² n
Pr 31:8
28' (31:H)
$ Hn +
3
8H
11 p
Recall that r E [T]
was chosen arbitrarily. Since v
1
Er= Vr, follows from Lemma F.3,
T
applied to the random variables Ze := (/(.n)))/ (81.1) (for v1.1 x*), that
v(y1:))
<8
s 2H 16 16
16H
Vr
Vr
Pr Vi:HWWTT
(y1:H)
n/
< 22Hm+16HH's
16HR²
T
T
3
Vr P
1/I'
16H
4H
< 22Hm+
T
58
where the third inequality is by Lemma I.8, and the fourth incquality is by choice of and 8', and holds so long as 2 cH for sufficiently large constant C. Substituting of 8' == 5/(48Hk2) and our definition of к := + Ev into the left-hand side of the inequality completes the proof of Eq. (7). The claim that the runtime of VGB O(T |Al) is immediate from inspection of Algorithm 1.
the choice
75

---

Published as a conference paper at ICLR 2026
J LLM USAGE STATEMENT
We used LLMs to help us write and refine small fragments of code code-specificallyy, code for program- matically generating Matplotlib and TikZ figures-and and purprse aide for learning syntax for specific Python libraries.
76


Reviews:
[{"review_id": "r38RwP6VHj", "reviewer": "Reviewer_VY1h", "summary": "The authors study \"process verifiers\" for LLMs within a theoretical framework. The notion of value function is introduced. It is supposed to align LLM generation with a predetermined reward. The \"true\" value function is defined, as well as its approximate counterpart. The central question of the paper is: how can we sample from the LLM using signal from the approximate verifier so that the resulting distribution of responses remain close to the optimal one achieved with the \"true\" value function?\n\nA VGB sampling algorithm based on Sinclair-Jerrum random walk is proposed and its theoretical guarantees are proved under certain assumptions.\n\nAdditionally, some small-scale experiments are conducted showing the practical usefulness of the method.", "questions": "1. In your framework you fix the length of generation to be H. Can the framework be reformulated to assume variable length generation? \n2. In VGB the probability of staying in the current node is 1/2. Is this the only constant preserving the properties of VGB, or it can be different?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* I find the topic of the paper interesting and timely.\n* The authors put effort into introducing a formal framework of sampling from LLMs with verifiers and seem to prove significant theoretical results.\n* The presented VGB algorithm is conceptually simple.", "weaknesses": "1. My main objection is that it's really unclear to what extent the presented theoretical results are relevant in practice. The authors motivate the paper practically, mentioning LLM-based PRMs from recent literature. However, I'm not sure if the introduced theoretical framework captures these practical PRMs and their usage. More specifically, I'm not sure if Assumptions 4.1 or 4.2 will be satisfied in practice with real-life verifiers. \n2. The presentation in some places is not polished. Some symbols are not defined (for instance delta in l. 64, A^H in l. 65, D_TV and omega in l. 209), which sometimes makes reading / understanding more difficult than necessary. \n3. It is good that the authors include some number of experiments, but they are small-scale and targeting simple problems. I think they are not convincing of practical relevance of VGB and its theoretical properties.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6cQzuhywdi", "reviewer": "Reviewer_ZxSD", "summary": "This paper investigates the robustness of process-guided test-time alignment in generative language models, focusing on settings where imperfect value functions (verifiers) are used to steer generation. The authors identify error amplification pitfalls associated with standard action-level sampling when value-function estimates are used, and propose a new algorithm, Value-Guided Backtracking (VGB), grounded in Markov Chain Monte Carlo theory to counteract these weaknesses. They provide theoretical analyses and guarantees for VGB—even under average-case error regimes—as well as empirical validation across synthetic, code generation, and constrained text generation benchmarks.", "questions": "- Can the authors rigorously clarify the scalability of VGB for long-horizon, real-world LLM settings, both in terms of query count and wall-clock time, beyond what is presented in synthetic or small-scale experiments? For example, can VGB be realistically run for open-ended generation and complex code synthesis tasks at scale, or do computational bottlenecks dominate in these regimes?\n- Would the main conclusions regarding error amplification and backtracking hold if the value function $\\widehat{V}$ were implemented with more complex architectures (e.g., transformer-based verifiers) or noisy/biased sampling of partial completions? Are the present synthetic experiments sufficiently representative?\n- Is there a principled way to tune the backtracking parameter (probability or weight), especially in the absence of oracle rewards or in scenarios where the true error profile of $\\widehat{V}$ is unknown?\n- Do the authors have insight into failure modes for VGB in more diverse or adversarial settings (e.g., prompts specifically constructed to trip up process verifiers), and could VGB be made robust to such cases?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The authors provide an explicit theoretical understanding of how small, seemingly benign errors in learned process verifiers can catastrophically degrade the distributional fidelity of generation under standard action-level sampling. \n- VGB is a principled modification to existing sampling strategies, and the authors convincingly root its correctness and performance in established Markov chain (Sinclair-Jerrum walk) theory.\n- The paper benchmarks VGB against both sampling (Block Best-of-N, Block Rejection Sampling) and search-style (beam search, locally constrained decoding) baselines across multiple axes.", "weaknesses": "- While the theoretical grounding is new, its real-world applicability and improvement magnitude over clever heuristics or simple extensions (e.g., adding \"undo\" moves) is not novel, especially since the best practical variant of VGB may require hyperparameter tuning for the backtracking probability, which the authors acknowledge but do not fully explore.\n- The computational cost of VGB, especially for long horizons (scaling as $\\tilde{O}(H^3)$ for guaranteed leaf sampling under uniform error, and worse under average-case errors), could render it prohibitive for many realistic LLM tasks beyond toy or controlled environments.\n- Most evaluation focuses on (relatively) small-scale or synthetic tasks—such as the Dyck grammar and ABC tasks. Despite one code generation task, there are no results on multi-turn question answering, math and code, or agentic reasoning where process verifiers are essential and imperfect. This leaves open how VGB would fare in \"hard\" settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4eK1PV5py4", "reviewer": "Reviewer_HyCr", "summary": "The paper proposes a generalization of the Sinclair-Jerrum random walk to reward-guided generation of language models when the value function is not perfect.\nThe proposed method (VGB) has a strong theoretical motivation, and where possible, formula derivations are delegated to relevant work.", "questions": "Do authors have any intuition or results regarding more complex problems, especially those that have a value function that is much harder to learn/approximate?\nTo be more precise, the algorithm still requires a good, on average, value function for efficient sampling, and it is not clear whether, in more complex cases, it wouldn't be cheaper to tune the policy with GRPO instead.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ Solid theoretical foundation backed up by experimental results\n+ Simple examples that illustrate the problem of a more greedy approach (ActionLevelRS)\n+ Thought out collection of evaluation tasks (such as parity that is not in $\\mathrm{AC}^0$)\n+ Polynomial (in generation length, action space, value function error, and target $D_{\\mathrm{TV}}$) algorithm for sampling from an optimal policy for a KL regularized objective", "weaknesses": "+ Minor: Relatively simple generation tasks (Dyck grammar, Python test generation, and letter avoidance with output length 32 and  0.5B parameter model). To be more precise, inclusion of simple tasks benefits the work; however, inclusion of more complex tasks should further help to assess the practicality of the method.\n+ Minor: The paper delegates a lot of proofs to the Appendix. To be more precise, the Appendix consists of around 55 pages, and around 25 of them are proofs. This is a highly dense, in particular for a conference where \"Authors may use as many pages of appendices (after the bibliography) as they wish, but reviewers are not required to read the appendix.\". I must say I haven't managed to check all the proofs of the propositions and theorems. However, I noted that some of them seem to miss some (relatively obvious so this is a minor problem) assumptions or have some typos regarding the parentheses (see proof of proposition G.3).\n+ Minor: the algorithm requires a lot of sampling to achieve theoretical guarantees", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nT84R19bGh", "reviewer": "Reviewer_s7CV", "summary": "In test-time scaling, process verifiers guide generation towards high-reward outputs. However, process verifiers may be inaccurate. This paper shows that process verification errors can \"cascade\" in the sense of growing with the number of decoding steps. It then presents an alternative test-time scaling algorithm, VGB, which is shown to have positive theoretical properties with regard to multiplicative errors in the process reward: \n\n- Given a uniform bound on the multiplicative process reward error, VGB is guaranteed to sample from a distribution $\\hat{\\pi}$ with bounded total variation distance from the reward-optimal sampling distribution $\\pi^*$, and to output a \"leaf node\" (a complete generation) in time $\\tilde{O}(H^3)$.\n- Given a bound on the expected ratio of the estimated and true process rewards, the output distribution is similar to the reward-optimal sampling distribution with high probability. Specifically the ratio $\\pi*/\\hat{\\pi} < \\delta^{-1} 48H(1+\\epsilon_V)^2$, with $H$ indicating the decoding length and $(1+\\epsilon_V)$ the multiplicative bound on the expected ratio of estimated and true process rewards. The runtime in this setting grows as $\\tilde{O}(H^5)$.\n\nThe paper makes several other theoretical contributions, including showing that other error conditions are insufficient to achieve the desired guarantees (appendix D).\n\nThe empirical side focuses mainly on minimal synthetic language tasks, such as Dyck grammars.", "questions": "Please feel free to comment on the points raised above: (1) whether errors still increase with $H$ in VDB, and (2) whether and how the algorithm can be practical given the apparently poor polynomial scaling with $H$.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an important practical issue in test-time scaling. It introduces useful theoretical machinery, which to my knowledge is novel in this domain. The discussion of \"pitfalls\" of existing techniques is clear and convincing, as is the presentation of the theoretical guarantees offered by the approach.\n\nThe empirical results shown in the main paper mostly support the main claims, albeit in toy settings: fig 1 demonstrates that VGB dominates block best-of-N and block rejection sampling in the Dyck grammar task, and fig 2 shows that the KL-divergence error grows more slowly with $H$ in the ABC task.\n\nOverall, while I doubt that the specific algorithm here is likely to be of practical value, the paper seems like a significant theoretical advance that will catalyze more research that may ultimately make test-time scaling more effective and/or efficient.\n\nThe writing quality is excellent throughout the paper.", "weaknesses": "While the paper claims to address the problem of cascading errors, it seems like the bound in theorem 4.2 still grows in $H$. Similarly, the KL-divergence errors seem to grow with $H$ in Figure 2, although they do grow more slowly than with action reject sampling. Thus it seems more like the proposed approach *mitigates* this issue rather than solving it.\n\nI think the proposed algorithm is unlikely to be adopted due to the polynomial run-time scaling with $H$ (cubic with the uniform guarantee, and quintic with the expectation condition). But as noted above, that's not a deal-breaker to me because the paper may stimulate research that results in more efficient algorithms. The authors do acknowledge this issue in the paper.\n\nI am not a specialist in this area, and I found it pretty hard to understand how the algorithm actually works. In particular, the paper did a poor job explaining the search space explored by the backtracking algorithm, and would have benefited from a better figure than fig 1 (right).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)