Paper deep dive
Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference
Noah Golowich, Fan Chen, Dhruv Rohatgi, Raghav Singhal, Carles Domingo-Enrich, Dylan J. Foster, Akshay Krishnamurthy
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/13/2026, 12:37:40 AM
Summary
The paper provides a theoretical framework for analyzing inference-time interventions in large language models (LLMs) using particle filtering algorithms like Sequential Monte Carlo (SMC). It establishes non-asymptotic guarantees for SMC based on action-level coverage and process reward model (PRM) accuracy, identifies fundamental limits of particle filtering, and introduces an improved algorithm, SMC-RS, to achieve better convergence.
Entities (5)
Relation Signals (3)
Sequential Monte Carlo → implements → Aggregation and Pruning
confidence 95% · aggregation and pruning are naturally implemented by particle filtering algorithms, including the popular Sequential Monte Carlo (SMC) method
SMC-RS → improves → Sequential Monte Carlo
confidence 95% · we introduce Sequential Monte Carlo with Rejection Sampling (SMC-RS, Algorithm 2)—avoids this pathology, recovering Theorem 1.1 as well as the one-particle guarantee
Process Reward Model → guides → Large Language Models
confidence 90% · In this paradigm, aggregation and pruning are naturally implemented by particle filtering algorithms... which use the process reward model to adaptively prune and replicate multiple particles
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Inference-time methods that aggregate and prune multiple samples have emerged as a powerful paradigm for steering large language models, yet we lack any principled understanding of their accuracy-cost tradeoffs. In this paper, we introduce a route to rigorously study such approaches using the lens of *particle filtering* algorithms such as Sequential Monte Carlo (SMC). Given a base language model and a *process reward model* estimating expected terminal rewards, we ask: *how accurately can we sample from a target distribution given some number of process reward evaluations?* Theoretically, we identify (1) simple criteria enabling non-asymptotic guarantees for SMC; (2) algorithmic improvements to SMC; and (3) a fundamental limit faced by all particle filtering methods. Empirically, we demonstrate that our theoretical criteria effectively govern the *sampling error* of SMC, though not necessarily its final *accuracy*, suggesting that theoretical perspectives beyond sampling may be necessary.
Tags
Links
- Source: https://arxiv.org/abs/2603.07887v1
- Canonical: https://arxiv.org/abs/2603.07887v1
Trouble viewing inline? Open PDF directly →
Full Text
109,162 characters extracted from source content.
Expand or collapse full text
Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference Noah Golowich Microsoft Research nzg@cs.utexas.edu Fan Chen MIT fanchen@mit.edu Dhruv Rohatgi MIT drohatgi@mit.edu Raghav Singhal NYU singhal.raghav@gmail.com Carles Domingo-Enrich Microsoft Research carlesd@microsoft.com Dylan J. Foster Microsoft Research dylanfoster@microsoft.com Akshay Krishnamurthy Microsoft Research akshaykr@microsoft.com March 10, 2026 Abstract Inference-time methods that aggregate and prune multiple samples have emerged as a powerful paradigm for steering large language models, yet we lack any principled understanding of their accuracy– cost tradeoffs. In this paper, we introduce a route to rigorously study such approaches using the lens of particle filteringalgorithms such as Sequential Monte Carlo (SMC). Given a base language model and aprocess reward modelestimating expected terminal rewards, we ask:how accurately can we sample from a target distribution given some number of process reward evaluations?Theoretically, we identify (1) simple criteria enabling non-asymptotic guarantees for SMC; (2) algorithmic improvements to SMC; and (3) a fundamental limit faced by all particle filtering methods. Empirically, we demonstrate that our theoretical criteria effectively govern thesampling errorof SMC, though not necessarily its finalaccuracy, suggesting that theoretical perspectives beyond sampling may be necessary. 1 Introduction Recent work on large language models (LLMs) has demonstrated the value ofinference-time interventionsthat steermodels towards higher-quality outputs. For instance, existing work has experimented with a combination of usingparallelgenerations from LLMs (Madaan et al., 2025; Brown et al., 2024), techniques toaggregate such generations (Wang et al., 2023; Fu et al., 2025; Zhao et al., 2025), and ways toprune or compressthem to fit in the context window for subsequent model calls (Yang et al., 2024; Wu et al., 2025). Even withno additional training, such interventions can significantly improve performance on challenging tasks such as mathematical reasoning and question answering. However, these methods are largely ad hoc, since we lack a unifying theoretical framework that canexplainthe benefits of different inference-time interventions and guidealgorithm design towards the most effective ones. In this paper, we ask: Can we analyze inference-time interventions such as aggregation and pruning of parallel generations in a principled manner? To do so, we study the paradigm ofguided LLM generation with a process reward model(Wang et al., 2025a; Puri et al., 2025b), where the process reward model numerically scores partial generations. In this paradigm, aggregation and pruning are naturally implemented byparticle filteringalgorithms, including the popular Sequential Monte Carlo (SMC)method, which use the process reward model to adaptively prune and replicate multipleparticles(namely, partial generations from the base model), as tokens are generated. These strategies can have robust empirical benefits over simpler interventions such as Best-of-N; see e.g. Figure 1 or Puri et al. (2025b). 1 arXiv:2603.07887v1 [cs.LG] 9 Mar 2026 Figure 1: Performance of SMC (withNparticles) vs. Best-of-Non Math500 problems; here we takeN= 32. Each point is a different problem; thus, SMC withNparticles improves performance over Best-of-Non most problems. See Section 4.5 for details. While particle filtering methods have been extensively applied to tasks ranging from posterior inference (Pitt and Shephard, 1997) and robot localization (Montemerlo et al., 2002) to steering LLMs (Lipkin et al., 2025; Lew et al., 2023; Loula et al., 2025; Grand et al., 2025; Puri et al., 2025a; Zhao et al., 2024; Feng et al., 2024) and diffusion models (Skreta et al., 2025; Singhal et al., 2025), few non-asymptoticguaranteeshave been established for such methods. In this paper, we address this challenge, providing a user-friendly analysis of SMC and identifying benefits and limitations of more sophisticated particle filtering methods. Towards a theory of inference-time interventions.Increasingly, inference-time interventions utilize models not just for generation and scoring, but also more complex operations such as splicing (Fu et al., 2025) or summarizing (Yu et al., 2025) generations. While these operations are not directly captured by our setting, we believe that our work is a necessary first step towards developing a framework for understanding (and improving) such interventions. 1.1 Setting: Guided Generation with Imperfect Process Rewards For a fixed prompt, a language model defines a distributionπ ref ∈∆(A H )over sequences ofHactionsin some setA. 1 One can think ofAas the space oftokens, or more generally as blocks of tokens. Given a sequencea 1:h , we can efficiently sample fromπ ref (a h+1 =· |a 1:h ), which enables autoregressive sampling fromπ ref . We model the task ofsteeringthe language model towards some desired reward as asamplingproblem, in line with recent work on LLM inference and post-training (Rohatgi et al., 2025; Geuter et al., 2025; Foster et al., 2025; Xiong et al., 2024; Zhu and Lu, 2026). Given query access to a reward functionr ⋆ :A H →R ≥0 , we aim to sample from thetilted distributionπ ⋆ H (a 1:H )∝π ref (a 1:H )r ⋆ (a 1:H ). For instance, in the context of mathematical reasoning,r ⋆ (a 1:H )∈0,1measures whethera 1:H correctly solves the prompt. Imperfect process rewards.Following Rohatgi et al. (2025), we theoretically formalize a process reward model (PRM) as anapproximate value function. Given a sequencea 1:h of any length, the PRM provides an estimate b V(a 1:h )∈R ≥0 of theexpected rewardofa 1:h underπ ref , i.e.,V ⋆ (a 1:h ) :=E a ′ 1:H ∼π ref [r ⋆ (a ′ 1:H )| a ′ 1:h =a 1:h ]. In practice, there has been extensive effort to train transformers specifically to be PRMs (Lightman et al., 2023; Wang et al., 2024, 2025b; Zhang et al., 2025) for certain problems, such as math reasoning. If such a fine-tuned PRM adapted to a desired reward functionr ⋆ is not available, there are several other popular choices for b V—e.g. LLM-as-a-judge (Stephan et al., 2024) or LLM log-probabilities (Karan and Du, 2025; Lew et al., 2023); see also Section 4. 1 For simplicity, we assume that the language model produces generations of fixed length. 2 The key algorithmic challenge in this setting is that the PRM is imperfect. To address this challenge, numerous parallel and sequential approaches have been proposed, including SMC (Puri et al., 2025b), block rejection sampling (Mudgal et al., 2024), and backtracking (Botta et al., 2025). Thus far, provable guarantees are only known for backtracking (Rohatgi et al., 2025) — an inherently sequential approach. We ask:given access to π ref and b Vas above, what structural properties enable approximate sampling fromπ ⋆ H via efficient parallel methods such as particle filtering? 1.2 Theoretical Contributions: A Principled Analysis of Particle Filtering Meth- ods for LLM Inference Contribution I: Simple criteria for success of SMC.Our first result identifies twokey properties that enable the success of SMC. Forh∈[H], letπ ⋆ h ,bπ h ∈∆(A h )denote thetrueandapproximate intermediate target distributions, defined byπ ⋆ h (a 1:h )∝π ref (a 1:h )V ⋆ (a 1:h )andbπ h (a 1:h )∝π ref (a 1:h ) b V(a 1:h ). Then we show the following: Theorem 1.1(Corollary of Theorem 3.2).Suppose that the following hold. (1)Boundedaction-level coverage: for allh,a 1:h+1 ,π ⋆ (a h+1 |a 1:h )/π ref (a h+1 |a 1:h )≤C act . (2)Boundedχ 2 -divergences(these control the error of b Vvs.V ⋆ , per Fact A.2):D χ 2 (π ⋆ h ∥bπ h )≤C χ 2 for all h. Then SMC withNparticles samples from a distributionbμsatisfyingD TV (bμ,π ⋆ )≤ q H 2 C act (C χ 2 +1) N . This bound strengthens the guarantees for the backtracking-based algorithm VGB of Rohatgi et al. (2025). Moreover, the parallel runtime of SMC isO(H)whereas VGB uses timeΩ(H 2 )(and is inherently sequential). See Appendix A for additional discussion. Remark 1.2(Connection to literature on refinements of SMC).Interestingly, the twokey propertieslisted above map quite cleanly onto various efforts in prior work focused on refining SMC algorithms. The latter of the two conditions (that b VapproximatesV ⋆ ) is related to the line of work ontwisting targetsfor SMC. In particular, the distributionsbπ h introduced above are often referred to as (intermediate) target distributions, and prior work has explored how to choose (or learn) b V so as to bringbπ h as close as possible toπ ⋆ h for all h∈[H](Guarniero et al., 2017; Heng et al., 2017; Zhao et al., 2024; Lawson et al., 2022), which is a natural goal in light of Theorem 1.1. Moreover, the first condition (on action-level coverage) is related to the extensive literature on changing the proposal distributionπ ref,h to better approximate thelocally optimal proposal distribution(Naesseth et al., 2019; Doucet et al., 2000), which is defined as the distributionbπ h+1 (a h+1 =· |a 1:h ). In the event that bπ h+1 ≈π ⋆ h+1 , then the locally optimal proposal distribution has action-level coverage close to1, the smallest possible value. Thus, as long as b V is sufficiently accurate, modifyingπ ref,h so as to approximate the locally optimal proposal is a way to decrease action-level coverage. 2 Summarizing,our result helps to unify the existing literature on variants of SMC by showing that they are effectively minimizing the key quantities Theorem 1.1. Contribution I: Beyond Sequential Monte Carlo.Can particle filtering algorithms beyond SMC achieve stronger guarantees? First, we show that ifbπ h is close toπ ⋆ h in a strongerL ∞ sense, then it is possible to achieveexponential decayin sampling error (rather than polynomial decay, as in Theorem 1.1) by wrapping SMC in an outer rejection sampling loop (Theorem 3.6). Second, we observe that even when the PRM isperfect, and henceC χ 2 = 0, SMC requiresΩ( √ H)particles to achieve non-trivial sampling accuracy (Proposition C.8), even though there is a simple one-particle algorithm for this special case (Rohatgi et al., 2025). We show that a modified algorithm—Sequential Monte Carlo with Rejection Sampling (SMC-RS, Algorithm 2)—avoids this pathology, recovering Theorem 1.1 as well as the one-particle guarantee (Theorem 3.8). 2 Indeed, usingbπ h+1 as the proposal and appropriately modifying the weights in SMC yields a variant with improved convergence properties (see Section 3.3 and Appendix D.3). 3 0.00.20.40.60.81.01.21.4 Action-level coverage (KL proxy) 10 20 30 40 50 60 Error of SMC (a) Action-level coverage. 246810121416 Divergence btwn. * & (KL proxy) 15 20 25 30 35 40 45 50 55 Error of SMC (b)D KL (π ⋆ h ∥bπ h ). Figure 2: Empirical validation for our theory on theprompt-switching task(see Section 4). (a) We vary the action-level coverage (as measured by a KL-divergence proxy) across many prompts while keeping b V=V ⋆ fixed, and observe that action-level coverage predicts the sampling error of SMC. (b) We fixπ ref =π ⋆ (so that action-level coverage is fixed) and observe thatD KL (π ⋆ h ∥bπ h )predicts the sampling error of SMC. Contribution I: Limits of particle filtering.A key limitation of SMC (and our modifications) is that even whenπ ref has bounded action-level coverage (i.e.C act =O(1)) and the approximate value function b Vis within a constant factor of the truth (and henceC χ 2 =O(1)), our algorithm requires maintainingpoly(H) particles and hence requires superlinear work. In Theorem 3.9 we show that fully avoiding this lower bound would requirelookahead: anymyopicmethod needs at leastΩ(logH/log logH)particles (Theorem 3.9). Closing this gap is open. Addendum: backtracking as a form of particle filtering.In Appendix E, we show an interesting connection between particle filtering algorithms and the backtracking-based approach VGB (Rohatgi et al., 2025) — previously, the only algorithm for inference-time steering of LLMs that was known to be robust to PRM errors. VGB is a (one-particle) Markov chain method that generates tokens but sometimes alsodeletes the most recent token. We show that the execution of VGB can becoupledwith the execution of a certain particle filtering method, potentially providing a new perspective on the benefits of both methods. 1.3Empirical Contributions: Does the Theory Predict the Performance of SMC in LLMs? We investigate empirically whether the quantities identified by Theorem 1.1 indeed predict the performance of SMC on LLM sampling problems. First, we consider a simple “prompt switching” task in which the base modelπ ref corresponds to sampling from an LLM given some promptp ref , andπ ⋆ corresponds to sampling from that LLM given another promptp ⋆ (see Section 4 for details). By varyingp ref ,p ⋆ , and the PRM b V, we can control for each quantity in Theorem 1.1. First, in Figure 2a, we consider a dataset where b V=V ⋆ for all prompts in the dataset (soC χ 2 = 0) but the action level coverage varies, and observe a strong correlation between the action-level coverage (measured via a KL-divergence proxy) and the sampling error of SMC. Second, in Figure 2b, we consider a dataset where the action-level coverage is identical across all prompts but the degree of accuracy of b Vwith respect toV ⋆ varies, and again we observe a strong correlation between D KL (π ⋆ h ∥bπ h )and the sampling error of SMC. (We report the KL divergence instead of theχ 2 divergence since the latter requires prohibitively large sample complexity to estimate.) Evaluating SMC on math reasoning tasks.Finally, we consider the performance of SMC on challenging math reasoning benchmarks including AIME and Math500. In Figure 1, we plot, for each problem in Math500, the accuracy of SMC withNparticles against that of Best-of-N(withN= 32); each of these quantities was estimated by running the requisite algorithm 100 times per problem. As most points lie below the line 4 y=x, we see that SMC improves performance over Best-of-Nin auniform sense over all problems, which extends prior observations in Puri et al. (2025b); Chatziveroglou (2025) which observed that SMC improves upon Best-of-Nin anon-averagesense over such benchmarks. Despite this strong evidence for superiority of SMC, as we discuss further in Section 4.5, the quality of the PRM b V(as measured by an estimate of the chi-square divergence betweenbπ h andπ ⋆ h ) does not seem to positively correlate with performance, as often larger divergenceleads tohigher accuracy.We leave as an intriguing open question the development of a more refined framework that captures performance on such benchmarks. Roadmap.Section 2 introduces the formal setting for our theoretical results. Section 3 contains our main theoretical results, and Section 4 contains our experimental results. 2 Preliminaries Our theory applies to a setting that generalizes Section 1.1. It should capture settings such as guidance for diffusion models, though we do not investigate such settings concretely. LetX 0 ,X 1 ,...,X H be arbitrary sets, and letX:=X 0 ⊔X 1 ⊔·⊔X H be their disjoint union. Letπ ref = (π ref,h ) H−1 h=0 be a collection of transition kernelsπ ref,h :X h →∆(X h+1 ). Without loss of generality, assume thatX 0 =⊥is a single element. The transition kernels induces a Markov chainx 0 →x 1 →x 2 ·→x H , wherex h+1 ∼π ref,h (·|x h )for0≤h≤H−1; we drop the subscripthwhen clear from context. We write x 1:H ∼π ref to denote a sample from the Markov chain. Letπ h ∈∆(X h )be the induced marginal distribution ofx h . Remark 2.1(Special case: autoregressive generation).In the specialization to LLMs discussed in Section 1, we would haveX h =A h , andπ ref,h (· |a 1:h )is the transition kernel which samplesa h+1 (givena 1:h ) and appends it toa 1:h . As in the setup of Section 1, given a terminal reward functionr ⋆ :X H →R ≥0 , thevalue functionV ⋆ :X →R ≥0 is defined, forx∈X h , byV ⋆ (x) =E x 1:H ∼π ref [r ⋆ (x H )|x h =x]. Note thatV ⋆ (x H ) =r ⋆ (x H )forx H ∈X H . Forh∈[H], define the distributionπ ⋆ h ∈∆(X h )byπ ⋆ h (x)∝π h (x)·V ⋆ (x). One may check that the distributionsπ ⋆ h are induced by the Markov chain with kernel π ⋆ (x h+1 |x h ) := π ref,h (x h+1 |x h )V ⋆ (x h+1 ) V ⋆ h (x h ) ,(1) as P x h π ⋆ h (x h )π ⋆ (x h+1 |x h ) =π ⋆ h+1 (x h+1 ). 3 Partial Reward Model.We extend the definition of the PRM to our more general setting in the natural way: the PRM is denoted b V :X →R ≥0 , and satisfies b V (x H ) =r ⋆ (x H )forx H ∈ X H . We define b Z h :=E x∼π h [ b V(x)]forh∈[H], and letbπ h ∈∆(X h )be defined bybπ h (x) =π h (x)· b V(x)/ b Z h . 3 Theoretical Analysis of Particle Filtering Methods 3.1 Simple Criteria for Success of SMC The first criterion is boundedaction-level coverage: Assumption 3.1.There exists parameterC act ≥1such that for allh≥0,V ⋆ h+1 (x h+1 )≤C act V ⋆ h (x h )for anyx h+1 ∈supp(π ref (·|x h )). We call this conditionaction-level coveragebecause V ⋆ (x h+1 ) V ⋆ (x h ) = π ⋆ (x h+1 |x h ) π ref,h (x h+1 |x h ) is exactly the density ratio between the conditional distributionsπ ⋆ andπ ref,h . 4 3 We note the following slight abuse of notation: we useπ ⋆ with no subscript to denote the transition kernel in Eq. (1), and π ⋆ h with a subscript to denote the corresponding intermediatedistributions. 4 We remark that Assumption 3.1 can be relaxed to theaveragesense (cf. Theorem C.6). 5 Algorithm 1Sequential Monte Carlo Input:Transition kernelπ ref , value function b V. Parameter:Number of particlesN≥1. Initializebν 0 =δ ⊥ . forh= 1,·,Hdo SampleNparticles ̃x 1 h−1 ,..., ̃x N h−1 i.i.d. ∼bν h−1 (·). Generatex i h ∼π ref,h−1 (·| ̃x i h−1 )independently fori∈[N]. Define weightsw i h = b V(x i h ) b V( ̃x i h−1 ) . Define weighted empirical measurebν h : = 1 W h P N i=1 w i h δ x i h , whereW h = P N i=1 w i h . Define c W h := Q h i=1 W i N . Output Option 1:Outputx H ∼bν H . Output Option 2:With probabilitymin n c W H 2C ∞ b V(⊥) ,1 o , outputx∼bν H , and otherwise restart the algorithm. The second criterion is boundedχ 2 -divergences betweenπ ⋆ h andbπ h for allh. Quantitatively, the two criteria yield the following guarantee for SMC, which directly implies Theorem 1.1: Theorem 3.2.Under Assumption 3.1, SMC withNparticles achieves D TV (E[bν H ],π ⋆ H )≤ r C act N H+ H−1 X h=1 q D χ 2 (π ⋆ h ∥bπ h ) ! . We remark that boundingD χ 2 (π ⋆ h ∥bπ h )only requiresaverage-casecloseness between b VandV ⋆ (Fact A.2). Existing theory for SMC (Schweizer, 2012; Zhu and Lu, 2026) can recover an analogous bound that requires worst-casecloseness: Assumption 3.3.There exists parameterC ∞ ≥1such thatC −1 ∞ ≤ V ⋆ (x) b V(x) ≤C ∞ for anyx∈X. While the proof technique of Schweizer (2012) can relax this assumption to some extent, it cannot recover Theorem 3.2 (see Appendix C.3). Moreover, as we show below, we can strengthen Theorem 3.2 further to tolerateheavy-tailed errorsin b V. 3.1.1 Handling Tail Behavior While theχ 2 -divergences in Theorem 3.2 provide an easy-to-interpret upper bound,D χ 2 (π ⋆ h ∥bπ h )is sensitive to the tail behavior ofbπ h with respect toπ ⋆ h (equivalently, the tail behavior of b Vrelative toV ⋆ ); in the case of heavy-tailed errors, it can blow up and render Theorem 3.2 vacuous. However, the goal of SMC is to produce a sample from anapproximatelycorrect distribution, so the tail behavior should only appear as an error probability. This motivates the following notion of distributional closeness (Chen et al., 2025), which can be bounded in terms ofχ 2 -divergence but not vice versa—–in particular, it can be arbitrarily small even whenD χ 2 (π ⋆ h ∥bπ h ) =∞. Definition 3.4.For parameterM≥1,h∈[H], we define Cov M (π ⋆ h ∥bπ h ) =P x∼π ⋆ h π ⋆ h (x) bπ h (x) ≥M . Theorem 3.5.Under Assumption 3.1, SMC withNparticles achieves the following for anyM≥1: D TV (E[bν H ],π ⋆ H )≤H r MC act N + H−1 X h=1 Cov M (π ⋆ h ∥bπ h ). 6 Algorithm 2Sequential Monte Carlo with Rejection Sampling Input:Transition kernelπ ref , value function b V. Parameter:initial sample sizeN≥1, parameterη≥1. InitializeS 0 to beNcopies of⊥. forh= 1,·,Hdo Initialize a multi-setS h =. while|S h |< Ndo Samplex h−1 ∼Unif(S h−1 ). Samplex h ∼π ref,h−1 (·|x h−1 ). With probability b V(x h ) η b V(x h−1 ) , updateS h ←S h ∪x h . Output:x∼bν H =Unif(S H ). Let us compare the guarantee of Theorem 3.5 with that of Theorem 3.2: the coverage termsCov M (π ⋆ h ∥bπ h ) in Theorem 3.5 play the role of the chi-square divergencesD χ 2 (π ⋆ h ∥bπ h ) in Theorem 3.2, capturing the amount by whichbπ h deviates fromπ ⋆ h . A key difference, though, is that for any fixed value ofM, the TV error betweenE[bν H ]andπ ⋆ H in Theorem 3.5 does not approach0asN→ ∞, i.e., we pay for the mass Cov M (π ⋆ h ∥bπ h )additively. 3.2 Beyond SMC: Faster Convergence underL ∞ -condition Below, we show that a simple modification to SMC (Output Option 2 of Algorithm 1) yields exponential (rather than polynomial) convergence when b VandV ⋆ are close in a worst-case sense (Assumption 3.3). Theorem 3.6.Under Assumptions 3.1 and 3.3, Algorithm 1 withOutput Option 2samples from a distributionμthat satisfiesD TV (μ,π ⋆ H )≤δ , as long asN≥Ω(HC 4 ∞ C 2 act log (C ∞ H/δ)), using a number of outer loop steps that is bounded byO(C 2 ∞ log(1/δ)). The basic idea is to wrap SMC in an outer rejection sampling loop. This qualitatively matches the convergence rate of the backtracking-based method VGB of Rohatgi et al. (2025), which requires the same assumptions. 3.3 Beyond SMC: Near-perfect PRM Even when b V=V ⋆ (i.e. the PRM is perfect), the upper bound in Theorem 3.2 still scales as H √ N . In fact, this is a fundamental limitation of SMC, not an artifact of the analysis: even when b V=V ⋆ andC act = 2, SMC cannot achieveo(1)sampling error without at leastN≥Ω( √ H)particles (Proposition C.8). 5 Note that b V=V ⋆ , the one-particle algorithm which simply samplesx h ∼bπ(x h |x h−1 )succeeds in exactly sampling fromπ ⋆ , so there is indeed hope to improve the upper bound ofH/ √ N. To mitigate this issue, we introduce Sequential Monte Carlo with Rejection Sampling (SMC-RS, Algorithm 2). Intuitively, SMC-RS fixes the issue that, in order to sample new particles, SMCnormalizesthe weighted empirical measure, which introduces interference between particles. SMC-RS instead uses rejection sampling, so that regardless of the other particles, the conditional distributionx h |x h−1 is bπ(x h |x h−1 )∝π ref (x h |x h−1 ) b V(x h ). This can be regarded as a refinement of the base proposalπ ref (·|x h−1 )with the knowledge of b V. In particular, whenN= 1, SMC-RS reduces toaction-level rejection sampling(Yang and Klein, 2021), which, due to Eq. (1), is an exact sampler when b V =V ⋆ (see Appendix A for the definition). We analyze SMC-RS under the following action-level coverage condition, which we view as conceptually equivalent to Assumption 3.1 (and formally equivalent, up to a factor ofC 2 ∞ under theL ∞ condition of Assumption 3.3). In the event that we make the weaker assumption of controlling chi-square divergence betweenπ ⋆ andbπ(as in Theorem 3.8 below), Assumption 3.7 is needed in order to ensure that a bounded value of the parameterηin Algorithm 2 suffices. 5 We leave the problem of determining the optimalH-dependence as an open question. 7 Assumption 3.7.There exists parameter b C act ≥1such that for allh≥0, b V h+1 (x h+1 )≤ b C act b V h (x h )for anyx h+1 ∈supp(π ref (·|x h )). Theorem 3.8.Under Assumption 3.7, suppose that SMC-RS (Algorithm 2) is instantiated withη≥ b C act . Then SMC-RS withNparticles achieves D TV (E[bν H ],π ⋆ H )≤ 1 √ N H X h=1 q D χ 2 (π ⋆ h ∥bπ h ), and has time complexityO(NHη)in expectation. In particular, suppose b Vis near-accurate so thatD χ 2 (π ⋆ h ∥bπ h )≤ε 2 for allh∈[H]. Then SMC-RS achieves D TV (E[bν H ],π ⋆ H )≤ εH √ N . Ifε≤ 1 H , then SMC-RS achieves sampling erroro(1)with onlyN=O(1)particles. This is in sharp contrast to SMC, where by Proposition C.8,N≥Ω( √ H)particles are necessary even when b V=V ⋆ andC act =O(1) (note that in this setting b C act =C act =O(1)as well, so SMC-RS does indeed succeed). Finally, SMC-RS admits analogues of Theorem 3.5 (heavy-tailed errors) and Theorem 3.6 (fast-rate conver- gence); see Theorem D.3 and Theorem D.5, respectively. 3.4 Limits of Particle Filtering Methods A key downside of SMC (and the discussed variants) is that, when the PRM is imperfect, avoiding error amplification requires the number of particlesNto grow at least linearly in the horizonH. In this section, we show that some horizon dependence is necessary for allmyopicparticle filtering methods. Informally, a myopic particle filtering method is any algorithm that maintains a set of particlesS h at each steph, and does not use the PRM data from later stepsk > hto determine the setS h . SMC and SMC-RS are two examples of myopic methods; see Appendix F for a formal definition. We prove that even with mild (constant-factor) imperfections in the PRM, any myopic particle filtering algorithm requires nearlyΩ(logH)particles to even obtain non-trivialcoverageofπ ⋆ H : Theorem 3.9.LetN(H) :=log(H)/(4log log(H)). There isno myopic particle filtering algorithm Algwith the following guarantee for all sufficiently largeH:Alguses at mostN(H)particles, and under Assumptions 3.1 and 3.3 withC act = 2andC ∞ =e 3 , the output distributionνofAlgsatisfiesν(E)≥H −1/5 for all eventsE ⊂X H withπ ⋆ H (E)≥1/2. As an immediate corollary, no such algorithm can achieveD TV (ν,π ⋆ H )≤1/3. In contrast, with a perfect PRM (i.e.C ∞ = 1), a single particle achieves zero error (Rohatgi et al., 2025). Moreover, Theorem 3.9 is particularly striking since, under Assumption 3.3, every intermediate distributionbπ h has constant coverage of π ⋆ h (i.e.bπ h (x)/π ⋆ h (x)≥C −2 ∞ for allx∈X h ). Theorem 3.9 shows that it is impossible for myopic methods to inductively “maintain” this coverage without a super-constant number of particles — and raises the question of whether some form oflookaheadcan improve computational efficiency. 4 Experiments in Language Models Next, we investigate to what extent the quantities from Section 3.1 predict the performance of SMC on sampling problems involving LLMs. 4.1 Controlled Setting: Prompt-Switching Task A key challenge in evaluating SMC and understanding its performance as a function of the aforementioned quantities is the difficulty ofmeasuring them, as well as measuring the performance of SMC itself. Most notably, we need to measure quantities involving the target distributionπ ⋆ h , which is typically not readily available. While prior work (e.g., Zhao et al. (2024)) has studied how to evaluate the performance of 8 SMC using the algorithm’s estimate of the partition functionZ:=E π ref [V ⋆ (x H )], such techniques are only guaranteed to provide tight bounds if SMC is accurate. Moreover, these methods do not directly address the challenge of estimating other quantities such as action-level coverage. Thus, in this section, we consider an alternative approach, in a setting which will conveniently satisfy thatπ ref ,π ⋆ are both efficiently sampleable. In particular, we consider theprompt-switching task, whereπ ref andπ ⋆ correspond to the output distribution of a language model under different prompts. Formally, we fix a language modelM, and consider the setting of Section 1 whereAis the token space ofMandX h =A h . Each instance of the prompt-switching task is determined by 3 prompts,(p ref ,p ⋆ ,p), as follows. Given choices of these prompts, we letπ ref be the output distribution ofMfor the promptp ref , and we denote it asπ ref (·) =M(· |p ref ). We then choose the terminal reward function to ber ⋆ (a 1:H ) := M(a 1:H |p ⋆ ) M(a 1:H |p ref ) , which gives that, for any intermediate steph, V ⋆ (a 1:h ) =M(a 1:h |p ⋆ )/M(a 1:h |p ref ). It follows thatπ ⋆ h (a 1:h ) =M(a 1:h |p ⋆ ). Since it is tractable to sample fromMand compute sequence-level probabilities, sampling fromπ ref ,π ⋆ as well as computingV ⋆ is tractable. Finally, the promptpdetermines b V, in a way that will be discussed below. Evaluation.To evaluate SMC on the prompt-switching task, we consider the following metric, inspired by more complex “LLM-as-judge” techniques and also the use of log-probabilities to characterize the output distributions of LLMs (Golowich et al., 2025). Given two distributionsν,ν ′ over sequences of lengthH, and a set of promptsP, we define theP-logprob discrepancyLPD P (ν,ν ′ )betweenνandν ′ as the difference between the mean token-level log-probabilities assigned to sequences sampled fromνandν ′ under the prompts inP (summed over all positionsh). Formally, forν,ν ′ ∈∆(A H ), we have: LPD P (ν,ν ′ ) := X p∈P H X h=1 |E a 1:H ∼ν [logM(a h |p,a 1:h−1 )]−E a ′ 1:H ∼ν ′ logM(a ′ h |p,a ′ 1:h−1 ) . In words, theP-logprob discrepancy uses the prompts inPastest functionsto measure how different the two distributionsν,ν ′ are. It can be thought of as a very simple (albeit more stable) “LLM-as-judge” metric, where instead ofgeneratingfromMto evaluateν,ν ′ , we simply use the log-probabilities assigned by the modelM. In our evaluations, we chooseP=p ref ,p ⋆ , which is natural in light of the fact that the two most salient prompts in the prompt switching task arep ref andp ⋆ . 4.2 Evaluating Dependence on PRM Accuracy To evaluate the influence of PRM accuracy on SMC performance, we fix the action-level coverage between π ref andπ ⋆ (in particular, by fixingp ref =p ⋆ ) and vary the PRM b V. In particular, we consider a number k= 50of instances of the prompt-switching task as described above: each instancei∈[k]is specified by three prompts((p ref ) (i) ,(p ⋆ ) (i) ,p (i) ), as well as a scalarαused in Eq. (2) below. In this subsection, the reference (p ref ) (i) and target(p ⋆ ) (i) prompts are shared across all instances, so we denote them byp ref ,p ⋆ , respectively. Moreover, we in fact havep ref =p ⋆ — this prompt asks the model to write a short story (e.g., “Write a scene about a dragon negotiating peace with the last human kingdom.”). 6 Each instancei∈[k]has a different value of b V, denoted b V (i) , which is given as follows: we fixkpromptsp (1) ,...,p (k) , which are each identical top ref except they ask for the story inkdifferent styles (e.g., “...Tell it as a news article.”). For each such promptp (i) , we letπ (i) denote the distributionπ (i) (a 1:H ) =M(a 1:H |p (i) ), which should be interpreted as a “perturbed” version ofπ ⋆ . Then we define b V (i) (a 1:h ) := π ⋆ (a 1:h ) π ref (a 1:h ) · π (i) (a 1:h ) π ⋆ (a 1:h ) (1−h/H)·α ,(2) for some parameterα >0controlling the degree of accuracy of b V (i) . To get some intuition behind this definition, supposeα= 1for simplicity: for smallh, b V (i) (a 1:h )≈π (i) (a 1:h )/π ref,h (a 1:h ), while at the final step h=H, b V (i) (a 1:H ) =V ⋆ (a 1:H ). In particular, at early steps, b V (i) h looks the value function of the “perturbed” target distributionπ (i) , meaning that for smallh, b V (i) h is “misleading” in that it “points towards”π (i) instead 6 While in this setting it is trivial to sample fromp ⋆ , we emphasize that our main goal here is studying the performance of SMC in terms of PRM accuracy as opposed to solving a challenging sampling problem. 9 ofπ ⋆ . For largerh, we attenuate the noise so as to ensure that sampling fromV ⋆ H is information-theoretically possible (i.e., that b V (i) H =V ⋆ H ). Natural variation in the choice of the promptsp (i) (which were generated by GPT-5) leads the resulting functions b V (i) h to have varying levels of accuracy with respect toV ⋆ h . Definebπ (i) h ∈∆(A h )bybπ (i) h (a 1:h )∝ π ref (a 1:h )· b V (i) (a 1:h ). While estimatingD χ 2 π ⋆ h ∥bπ (i) h is in principle possible, we found that the ratios V ⋆ (a 1:h )/ b V (i) (a 1:h )needed to estimate theχ 2 divergence are prohibitively high in variance. Thus, we instead estimateD KL π ⋆ h ∥bπ (i) h to measure the divergence betweenπ ⋆ h andbπ (i) h , which is much more stable because KL divergence can be written as an expectation oflog-probabilities (see Appendix G.2 for further details). In our experiments, we use Qwen3-0.6B as the language modelMand set the horizon toH= 64tokens. For each choice ofi∈[k]we run SMC withN= 32particles given the PRM b V (i) , and sample from its output distributionbν (i) H . In Figure 2b, we plot the values ofD KL π ⋆ h ∥bπ (i) h against the sampling error of SMC, measured viaP-logprob discrepanciesLPD P (E[bν (i) H ],π ⋆ H )(estimated by running SMC for 200 trials). We observe a clear correlation between the two quantities, thus validating our theoretical findings that PRM accuracy (as measured by the divergence betweenbπ h andπ ⋆ h ) predicts SMC’s sampling error. In Appendix G.2 we repeat the experiment for additional choices ofp ref ,p ⋆ ,p (i) ,αand observe similar results. 4.3 Evaluating Dependence on Action-level Coverage We next evaluate the influence of action-level coverage on SMC performance. We consider the same setup as in the previous subsection, except for each instancei∈[k]we take the target distribution, denoted(π ⋆ ) (i) , to be the same asπ (i) . In particular, each instance is determined by the tuple(p ref ,p (i) ,p (i) ). Moreover, we takeα= 0, so that b V (i) = (V ⋆ ) (i) . In this setting, theaction-level coveragedepends oni. We again use Qwen3-0.6B, take the horizon to beH= 32tokens, and run SMC withN= 32particles. While the action-level coverage between(π ⋆ ) (i) andπ ref (in theL ∞ sense of Assumption 3.1) is extremely large and essentially impossible to compute, we note thatD KL (π ⋆ ) (i) ∥π ref can be viewed as an “average-case proxy” for action-level coverage in light of the chain rule, which gives D KL (π ⋆ ) (i) ∥π ref = H X h=1 E a 1:h ∼(π ⋆ ) (i) h " log (π ⋆ ) (i) h (a h |a 1:h−1 ) π ref,h (a h |a 1:h−1 ) # . Figure 2a plots 1 H D KL (π ⋆ ) (i) ∥π ref against theP-logprob discrepanciesLPD P (E[bν (i) H ],π ⋆ H ); we again observe a clear correlation between the two quantities, in line with our theory. 4.4 Dependence on the Number of Particles Finally, in Figure 3, we show the performance of SMC as a function of the number of particlesNfor the prompt switching task, using a setup similar to that of Section 4.2. In particular, we consider 50 different prompt tuples(p (i) ref ,(p ⋆ ) (i) ,p (i) ), and for each tuple we use a PRM b V (i) defined fromp (i) as in Eq. (2) with α= 1. In addition to SMC, we also plot the performance of (a) sequential importance sampling using b V (i) (Appendix A), and (b) the “best-of-N” algorithm which samplesNsequences fromπ ref and outputs the one with the highest value according to the terminal reward(V ⋆ ) (i) (a 1:H ). We observe that SMC consistently outperforms both baselines, and moreover that its performance improves asNincreases; the latter conclusion is in line with our theoretical results. 4.5 SMC on Math Problem-solving Tasks Finally, we study the use of SMC to improve the performance of LLMs on math problem-solving tasks, including AIME and MATH500. In this setting, the base distributionπ ref corresponds to the output distribution of a language model prompted to solve a math problem, and the terminal reward function r ⋆ (a 1:H )∈ 0,1is the indicator that the answera 1:H is correct. Thus,π ⋆ is simply the base model 10 10 1 10 2 Mean Wall Clock Time (seconds) 4 × 10 1 5 × 10 1 6 × 10 1 7 × 10 1 8 × 10 1 Sampling error 2 4 8 16 32 64 128 2 4 8 16 32 64 128 2 4 8 16 32 64 128 SIS BoN SMC Figure 3: Performance of SMC on the prompt-switching task (Section 4.4). Each point represents SMC with some number of particlesN∈2,4,8,...,128. We average the sampling error and wall-clock time over all data points and all trials per data point. SMC consistently outperforms both sequential importance sampling (SIS) and Best-of-N(BoN) baselines. distributionconditioned on producing a correct answer, andV ⋆ (a 1:h )is the probability thatπ ref produces a correct answer conditioned on the prefixa 1:h . There are several open-source process reward models fine-tuned for math problems, which purport to yield good estimates ofV ⋆ . In our experiments, we take the PRM b Vto be Qwen2.5-Math-PRM-7B, and the base modelπ ref to be Qwen2.5-1B-Instruct. In the application of SMC to math reasoning tasks, since the goal is simply to findsomecorrect answer, it is typical to combine SMC with Best-of-Nsampling in the following manner: at the end of SMC, we select the single particle with the highest value b V(a 1:H ). Note that this is distinct from the standard Best-of-Nsampling procedure, in whichNsamples are drawnindependentlyfrom π ref and the one with highest b V-value is selected. SMC improves performance on math.Many papers (Puri et al., 2025b; Chatziveroglou, 2025) have reported that SMC typically improves the performance over Best-of-N(as well as other baselines). However, such results are typically reportedon-averageover all problems in the dataset, which fails to account for the hetereogeneity between individual problems. For instance, it was not clear if SMC improves performance over Best-of-Nonallproblems, or if SMC can actually hurt performance (compared to Best-of-N) on a non-negligible fraction of the dataset. 7 Certainly such a distinction is salient for any theoretical explanation for SMC’s performance. In Figure 1, we estimate the performance of SMC and Best-of-Nfor each problem in Math500 (using 100 trials per problem), and plot the accuracy of SMC against that of Best-of-N. While there is variability in the relative performance of the two algorithms, we see that for the vast majority of problems, SMC’s accuracy is at least as large as that of Best-of-N. In Figure 5, we observe a similar conclusion for AIME24 and AIME25. SMC and PRM accuracy.Having established that SMC leads to a consistent increase in accuracy across most Math500 and AIME problems, we next turn to the question of what factors influence its performanceon a given problem. In light of the fact that significant effort has been spent designing better PRMs b V(Lightman et al., 2023; Wang et al., 2024, 2025b; Zhang et al., 2025), a natural follow-up question from our theory is whether the divergence betweenπ ⋆ h andbπ h (as measured by, e.g., theχ 2 -divergenceD χ 2 (π ⋆ h ∥bπ h )) predicts the performance of SMC. To address this question, we consider a range of PRMs b V (λ) by varying the inverse temperature parameter λused by the PRM to produce its final probabilities. In Figure 4, we select 10 Math500 problems, and for each value ofλ, we plot an empirical estimate ofD χ 2 (π ⋆ h ∥bπ h )against the accuracy of SMC given b V (λ) . 7 Indeed, much prior work has highlighted that SMC can suffer from pathologies such as mode collapse, which might decrease the diversity of responses from which Best-of-Ncan choose. 11 10 2 10 7 PRM error 0.0 0.2 0.4 0.6 0.8 SMC Accuracy Sample 14 10 1 10 5 PRM error 0.2 0.4 0.6 0.8 SMC Accuracy Sample 22 10 1 10 5 PRM error 0.0 0.2 0.4 0.6 0.8 SMC Accuracy Sample 82 10 1 10 4 PRM error 0.2 0.3 0.4 SMC Accuracy Sample 194 10 1 10 5 PRM error 0.0 0.2 0.4 0.6 0.8 SMC Accuracy Sample 197 10 2 10 7 PRM error 0.2 0.4 0.6 0.8 SMC Accuracy Sample 223 10 3 10 8 PRM error 0.15 0.20 0.25 0.30 SMC Accuracy Sample 228 10 1 10 5 10 9 PRM error 0.05 0.10 0.15 0.20 0.25 SMC Accuracy Sample 249 10 1 10 4 10 7 PRM error 0.1 0.2 0.3 0.4 SMC Accuracy Sample 317 10 0 10 3 10 6 PRM error 0.1 0.2 0.3 0.4 0.5 SMC Accuracy Sample 323 012345 Figure 4: Influence of PRM error (measured byD χ 2 (π ⋆ h ∥bπ h )) on SMC accuracy for 10 Math500 problems. Different colors correspond to different values of the inverse temperature parameterλparametrizing b V (λ) . The plots show SMC accuracy with respect to arandomparticle (not the best one) selected at the end of SMC. Interestingly, we observe that largerχ 2 -divergence often leads tohigheraccuracy, which is in contrast to our theoretical findings which predict the opposite. We suspect that larger values ofλ(lower temperature) lead to better performance since they more effectively weed out incorrect partial solutions; however, they will also potentially leadbπ h to miss some modes ofπ ⋆ h , which causes theχ 2 -divergence to blow up. Thus, in order to accurately capture the performance of SMC on such problems, we need a modification to our framework that aims to not approximateπ ⋆ H in a distributional sense but rather to simply cover some portion of its mass. 5 Discussion In this paper, we have established theoretical guarantees for particle filtering algorithms under varioues assumptions relating the reference distributionπ ref to the target distributionπ ⋆ and the PRM b V(via the induced distributionsbπ). We highlight below some intriguing directions for future work: •There are various polynomial gaps between our upper and lower bounds, including their the dependence on horizonH, as discussed in Section 1.2, as well as the decay of the total variation distance as a function ofN: whereas our upper bounds of Theorems 3.2 and 3.8 decay as1/ √ N, the lower bound of Proposition C.8 decays as only1/N. •Can we develop metrics for the performance of SMC (and other inference-time sampling algorithms) which are weaker than total variation distance but still meaningfully capture “usefulness” of outputs? For instance, for math problems, typically one only desires a correct answer, and the particular phrasing of the solution may not matter too much. •Can we develop provable guarantees for particle filtering algorithms or other types of inference-time sampling procedures which rely on weaker notions of discrepancy betweenπ ⋆ h andbπ h ? The values of D χ 2 (π ⋆ h ∥bπ h )seen in, e.g., the experiments in Sections 4.2 to 4.4 are extremely large (in particular, much larger than the values ofNseen in our experiments), yet particle filtering algorithms still are able to effectively make use of b V. References Edoardo Botta, Yuchen Li, Aashay Mehta, Jordan T. Ash, Cyril Zhang, and Andrej Risteski. On the query complexity of verifier-assisted language generation. InForty-second International Conference on Machine Learning, 2025. URLhttps://openreview.net/forum?id=9oIjvaDhoN. Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia 12 Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling.arXiv preprint arXiv:2407.21787, 2024. F Cérou, P Del Moral, and A Guyader. A nonasymptotic theorem for unnormalized feynman–kac particle models. InAnnales de l’IHP Probabilités et statistiques, volume 47, pages 629–649. Gauthier-Villars, 2011. Giannis Chatziveroglou. A*-decoding: Token-efficient inference scaling, 2025. URLhttps://arxiv.org/abs/ 2505.13672. Fan Chen, Audrey Huang, Noah Golowich, Sadhika Malladi, Adam Block, Jordan T Ash, Akshay Krish- namurthy, and Dylan J Foster. The coverage principle: How pre-training enables post-training.arXiv preprint arXiv:2510.15020, 2025. Pierre Del Moral. Feynman-kac formulae. InFeynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications, pages 47–93. Springer, 2004. Arnaud Doucet, Simon J. Godsill, and Christophe Andrieu. On sequential monte carlo sampling methods for bayesian filtering.Statistics and Computing, 10(3):197–208, 2000. Shengyu Feng, Xiang Kong, Shuang Ma, Aonan Zhang, Dong Yin, Chong Wang, Ruoming Pang, and Yiming Yang. Step-by-step reasoning for math problems via twisted sequential monte carlo.arXiv preprint arXiv:2410.01920, 2024. Dylan J. Foster, Zakaria Mhammedi, and Dhruv Rohatgi. Is a good foundation necessary for efficient reinforce- ment learning? the computational role of the base model in exploration.arXiv preprint arXiv:2503.07453, 2025. Yichao Fu, Xuewei Wang, Yuandong Tian, and Jiawei Zhao. Deep think with confidence. InNeurIPS 2025 Workshop on Efficient Reasoning, 2025. Jonathan Geuter, Youssef Mroueh, and David Alvarez-Melis. Guided speculative inference for efficient test-time alignment of LLMs.arXiv preprint arXiv:2506.04118, 2025. Noah Golowich, Allen Liu, and Abhishek Shetty. Sequences of logits reveal the low rank structure of language models, 2025. URLhttps://arxiv.org/abs/2510.24966. Gabriel Grand, Joshua B. Tenenbaum, Vikash K. Mansinghka, Alexander K. Lew, and Jacob Andreas. Self-steering language models. InConference on Language Modeling (COLM), 2025. arXiv:2504.07081. Peter Guarniero, Adam M. Johansen, and Anthony Lee. The iterated auxiliary particle filter.Journal of the American Statistical Association, 112(520):1636–1647, 2017. Jeremy Heng, Adrian Bishop, George Deligiannidis, and Arnaud Doucet. Controlled sequential monte carlo. arXiv preprint arXiv:1708.08396, 2017. Aayush Karan and Yilun Du. Reasoning with sampling: Your base model is smarter than you think, 2025. URLhttps://arxiv.org/abs/2510.14901. J. Lawson, L. Raventos, A. Warrington, and S. Linderman. Sixo: Smoothing inference with twisted objectives. CoRR, abs/2206.05952, 2022. Holden Lee and Matheau Santana-Gijzen. Convergence bounds for sequential monte carlo on multimodal distributions using soft decomposition.arXiv preprint arXiv:2405.19553, 2024. Alexander K. Lew, Zhi-Xuan Tan, Gabriel Grand, and Vikash K. Mansinghka. Sequential monte carlo steering of large language models using probabilistic programs.arXiv preprint arXiv:2306.03081, 2023. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step.arXiv preprint arXiv:2305.20050, 2023. Benjamin Lipkin, Benjamin LeBrun, Jacob Hoover Vigly, João Loula, David R. MacIver, Li Du, Jason Eisner, Ryan Cotterell, Vikash K. Mansinghka, Timothy J. O’Donnell, Alexander K. Lew, and Tim Vieira. Fast controlled generation from language models with adaptive weighted rejection sampling.arXiv preprint arXiv:2504.05410, 2025. 13 João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash K. Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O’Donnell. Syntactic and semantic control of large language models via sequential monte carlo. InInternational Conference on Learning Representations, 2025. arXiv:2504.13139. Lovish Madaan, Aniket Didolkar, Suchin Gururangan, John Quan, Ruan Silva, Ruslan Salakhutdinov, Manzil Zaheer, Sanjeev Arora, and Anirudh Goyal. Rethinking thinking tokens: Llms as improvement operators. arXiv preprint arXiv:2510.01123, 2025. Joseph Marion and Scott C Schmidler. Finite samplel_2bounds for sequential monte carlo and adaptive path selection.arXiv preprint arXiv:1807.01346, 2018. Michael Montemerlo, Sebastian Thrun, Daphne Koller, and Ben Wegbreit. Fastslam: A factored solution to the simultaneous localization and mapping problem. InProceedings of the AAAI Conference on Artificial Intelligence, 2002. 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. InForty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=bVIcZb7Qa0. C. A. Naesseth, F. Lindsten, and T. B. Schön. High-dimensional filtering using nested sequential monte carlo. IEEE Transactions on Signal Processing, 67(16):4177–4188, 2019. doi: 10.1109/TSP.2019.2926035. Michael K. Pitt and Neil Shephard. Filtering via simulation: Auxiliary particle filters. Technical Report W13, Nuffield College, University of Oxford, 1997. Isha Puri, Shivchander Sudalairaj, Guangxuan Xu, Kai Xu, and Akash Srivastava. A probabilistic inference approach to inference-time scaling of LLMs using particle-based monte carlo methods.arXiv preprint arXiv:2502.01618, 2025a. Isha Puri, Shivchander Sudalairaj, Guangxuan Xu, Kai Xu, and Akash Srivastava. A probabilistic inference approach to inference-time scaling of llms using particle-based monte carlo methods.arXiv preprint arXiv:2502.01618, 2025b. Dhruv Rohatgi, Abhishek Shetty, Donya Saless, Yuchen Li, Ankur Moitra, Andrej Risteski, and Dylan J Foster. Taming imperfect process verifiers: A sampling perspective on backtracking.arXiv preprint arXiv:2510.03149, 2025. Nikolaus Schweizer. Non-asymptotic error bounds for sequential mcmc methods in multimodal settings.arXiv preprint arXiv:1205.6733, 2012. Raghav Singhal, Zachary Horvitz, Ryan Teehan, Mengye Ren, Zhou Yu, Kathleen McKeown, and Rajesh Ranganath. A general framework for inference-time scaling and steering of diffusion models.arXiv preprint arXiv:2501.06848, 2025. Marta Skreta, Tara Akhound-Sadegh, Viktor Ohanesian, Roberto Bondesan, Alán Aspuru-Guzik, Arnaud Doucet, Rob Brekelmans, Alexander Tong, and Kirill Neklyudov. Feynman-kac correctors in diffusion: Annealing, guidance, and product of experts.arXiv preprint arXiv:2503.02819, 2025. Andreas Stephan, Dawei Zhu, Matthias Assenmacher, Xiaoyu Shen, and Benjamin Roth. From calculation to adjudication: Examining LLM judges on mathematical reasoning tasks.arXiv preprint arXiv:2409.04168, 2024. Kaiwen Wang, Jin Peng Zhou, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kianté Brantley, and Wen Sun. Value-guided search for efficient chain-of-thought reasoning.arXiv preprint arXiv:2505.17373, 2025a. Kaiwen Wang, Jin Peng Zhou, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kiante Brantley, and Wen Sun. Value-guided search for efficient chain-of-thought reasoning. InAdvances in Neural Information Processing Systems, 2025b. arXiv:2505.17373. Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y. Wu, and Zhifang Sui. 14 Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations.arXiv preprint arXiv:2312.08935, 2024. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. InThe Eleventh International Conference on Learning Representations, 2023. URLhttps://openreview.net/forum?id= 1PL1NIMMrw. Nick Whiteley, Nikolas Kantas, and Ajay Jasra. Linear variance bounds for particle approximations of time-homogeneous feynman–kac formulae.Stochastic Processes and their Applications, 122(4):1840–1865, 2012. Xixi Wu, Kuan Li, Yida Zhao, Liwen Zhang, Litu Ou, Huifeng Yin, Zhongwang Zhang, Xinmiao Yu, Dingchu Zhang, Yong Jiang, et al. Resum: Unlocking long-horizon search intelligence via context summarization. arXiv preprint arXiv:2509.13313, 2025. Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for RLHF under KL-constraint. arXiv preprint arXiv:2312.11456, 2024. Kevin Yang and Dan Klein. Fudge: Controlled text generation with future discriminators. InProceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 3511–3535, 2021. Ling Yang, Zhaochen Yu, Tianjun Zhang, Shiyi Cao, Minkai Xu, Wentao Zhang, Joseph E Gonzalez, and Bin Cui. Buffer of thoughts: Thought-augmented reasoning with large language models.Advances in Neural Information Processing Systems, 37:113519–113544, 2024. Yue Yu, Qiwei Di, Quanquan Gu, and Dongruo Zhou. On the limits of test-time compute: Sequential reward filtering for better inference.arXiv preprint arXiv:2512.04558, 2025. Zhenru Zhang, Chujie Zheng, Yangzhen Wu, Beichen Zhang, Runji Lin, Bowen Yu, Dayiheng Liu, Jingren Zhou, and Junyang Lin. The lessons of developing process reward models in mathematical reasoning.arXiv preprint arXiv:2501.07301, 2025. Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Grosse. Probabilistic inference in language models via twisted sequential monte carlo.arXiv preprint arXiv:2404.17546, 2024. Wenting Zhao, Pranjal Aggarwal, Swarnadeep Saha, Asli Celikyilmaz, Jason Weston, and Ilia Kulikov. The majority is not always right: Rl training for solution aggregation.arXiv preprint arXiv:2509.06870, 2025. Youheng Zhu and Yiping Lu. On the power of (approximate) reward models for inference-time scaling.arXiv preprint arXiv:2602.01381, 2026. 15 Contents of Appendix A Comparison with Prior Work17 B Technical Tools17 C Proofs for SMC18 C.1 Useful Lemmas for SMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 C.2 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 C.3 Insufficiency of Existing Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 C.4 Proof of Theorem 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 C.5 Proof of Theorem 3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 C.6 Lower Bound for SMC with Exact Value Function . . . . . . . . . . . . . . . . . . . . . . . . 24 D Proofs for SMC-RS25 D.1 Proof of Theorem 3.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 D.2 Analysis of SMC-RS with Heavy-tailed Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 D.3 Faster Convergence for SMC-RS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 E A Unified Perspective on Backtracking and Particle Filtering28 E.1 Background on VGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 E.2 Definition of SMC-IND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 E.3 Coupling VGB with SMC-IND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 F Proof of Theorem 3.931 F.1 Myopic Particle Filtering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 F.2 Specialized Setting and Formal Theorem Statement . . . . . . . . . . . . . . . . . . . . . . . . 31 F.3 Proof of Theorem F.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 G Additional Experimental Details37 G.1 Additional Evaluation Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 G.2 Details for Section 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 G.3 Details for Section 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 G.4 SMC vs. Best-of-Non AIME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 16 A Comparison with Prior Work In this section we discuss how our theoretical guarantees compare with prior work. We specify to the autoregressive generation setting, as the more general setting has not been theoretically studied in the past. Action-level rejection sampling / sequential importance sampling (Yang and Klein, 2021).This algorithm samplesa 1:H autoregressively via the conditional distributions bπ(a h+1 |a 1:h )∝π ref (a 1:h+1 |a 1:h ) b V(a 1:h+1 ). It can be implemented in expected timeO(H b C act )by rejection sampling / importance sampling Rohatgi et al. (2025), and by Eq. (1), it exactly samples fromπ ⋆ if b V=V ⋆ . However, even under assumption Assumption 3.3 withC ∞ = 1 +ε, it can incurΩ(ε √ H)sampling error Rohatgi et al. (2025), which is vacuous if e.g.ε= Θ(1). VGB (Rohatgi et al., 2025).This algorithm is defined by a random walk on thetree of autoregressive generations, which has state spaceA 0 ⊔·⊔A H and in which the parent ofa 1:h isa 1:h−1 . The first main result of Rohatgi et al. (2025) is that the random walk samples fromπ ⋆ , up to total variation errorδ, in time roughlyO(H 2 C act C 4 ∞ log(1/δ)). This guarantee is essentially matched by the guarantee of Theorem 3.6 for SMC, except the language model evaluations in SMC can be parallelized intoHrounds, whereas the language model evaluations in VGB are inherently sequential. 8 The second main result of Rohatgi et al. (2025) shows that under the following average-case closeness condition between b VandV ⋆ , as well as bounded action-level coverage, VGB samples from a distribution thatapproximately coversπ ⋆ . Assumption A.1(Average-case assumption of Rohatgi et al. (2025)). max ( E π ⋆ " b V(a 1:h ) V ⋆ (a 1:h ) # ,E π ⋆ " V ⋆ (a 1:h ) b V(a 1:h ) #) ≤C. We make the following observation: Fact A.2.For each0≤h≤H, it holds that D χ 2 (π ⋆ h ∥bπ h ) =E π ⋆ " b V(a 1:h ) V ⋆ (a 1:h ) # ·E π ⋆ " V ⋆ (a 1:h ) b V(a 1:h ) # −1. Thus, under Assumption A.1 as well as bounded action-level coverage, Theorem 3.2 shows that SMC with N≤(C+ 1) 2 H 2 /ε 2 particles samples from a distribution that isε-close in total variation distance toπ ⋆ . Note that closeness in total variation distance is a stronger guarantee than approximate coverage. B Technical Tools Proposition B.1.For anyR≥0, independent random variablesX 1 ,·,X n , it holds that E n X i=1 (X i −E[X i ]) ≤ q nRmax i E|X i |+ 2nmax i E[|X i |I|X i |≥R]. Proof.We defineY i = minmaxX i ,−R,RandZ i =X i −Y i . Then, we can bound E n X i=1 (X i −E[X i ]) ≤E n X i=1 (Y i −E[Y i ]) + n X i=1 E|Z i −E[Z i ]|. 8 The results of Appendix E suggest a potential approach to parallelizing VGB via particle filtering, but it is unclear in what generality such a simulation would be efficient. 17 Note thatE|Z i −E[Z i ]|≤2E|Z i |≤2E[|X i |I|X i |≥R]. Further, E n X i=1 (Y i −E[Y i ]) ! 2 ≤E n X i=1 (Y i −E[Y i ]) ! 2 = n X i=1 E(Y i −E[Y i ]) 2 ≤ n X i=1 EY 2 i ≤R n X i=1 E|X i |, where we use|Y i |≤min|X i |,R. The proof is then completed by combining the inequalities above. C Proofs for SMC Notation.We defineH h =( ̃x i ℓ ,x i ℓ ) ℓ∈[h],i∈[N] to be the full history of the execution of SMC (Algorithm 1) up to the end of iterationh. We writeE h [·]for the conditional distribution with respect toH h . We write Z:=E x 1:H ∼π ref [r ⋆ (x H )]and observe thatZ=E x∼π h [V ⋆ (x)]for allh. C.1 Useful Lemmas for SMC We first prove the following lemmas. Lemma C.1.For any stephand any functiong:X h →R, we have that E h−1 h c W h ·E bν h [g] i = c W h−1 ·E x h−1 ∼bν h−1 E x h ∼π ref (·|x h−1 ) h b V(x h )·g(x h ) i b V(x h−1 ) .(3) The next lemma follows from applying Lemma C.1 inductively. Lemma C.2.For anyg h :X h →R, it holds that E h c W h ·E bν h [g h ] i =E x h ∼π h h b V(x h )g h (x h ) i .(4) In particular,E[ c W h ] = b Z h =E[ b V(x h )]forh≥1and E h c W H bν H (x) i =Z·π ⋆ H (x),∀x∈X H .(5) Finally, we upper bound the TV error of Algorithm 1 by the deviation of c W H . Lemma C.3.For Algorithm 1, it holds that D TV (E[bν H ],π ⋆ H )≤ 1 2Z E| c W H −Z|. Proof of Lemma C.1 and Lemma C.2.To prove Eq. (3), observe that E h−1 h c W h ·E bν h [g] i = c W h−1 ·E h−1 " 1 N N X i=1 w i h g(x i h ) # = c W h−1 ·E h−1 " 1 N N X i=1 b V(x i h ) b V( ̃x i h−1 ) g(x i h ) # . Since ( ̃x i h−1 ,x i h ) are i.i.d. givenH h−1 , for eachi∈[N], we have E h−1 " b V(x i h ) b V( ̃x i h−1 ) g(x i h ) # =E ̃x h−1 ∼ˆν h−1 E x h ∼π ref (·| ̃x h−1 ) " b V(x h ) b V( ̃x h−1 ) g(x h ) # , 18 which establishes Eq. (3). Next, we argue that Eq. (4) holds inductively (noting that the base case is trivial since c W 0 = b V(⊥)andbν 0 =δ ⊥ ), using Eq. (3): E h c W h ·E bν H [g h ] i =E c W h−1 ·E x h−1 ∼bν h−1 E x h ∼π ref (·|x h−1 ) h b V(x h )·g h (x h ) i b V(x h−1 ) =E " b V(x h−1 )· E x h ∼π ref (·|x h−1 ) [ b V(x h )g h (x h )] b V(x h−1 ) # =E[ b V(x h )g h (x h )], as desired. We get thatE[ c W h ] =E[ b V (x h )]by usingg h ≡1. Finally, Eq. (5) follows by settingg H (x) = Ix H =xin Eq. (4) and using that b V(x H ) =V ⋆ (x H )forx H ∈X H . Proof of Lemma C.3.By Eq. (5), we can write 2ZD TV (E[bν H ],π ⋆ H ) = X x∈X H |ZE[bν H (x)]−Zπ ⋆ H (x)|= X x∈X H ZE[bν H (x)]−E[ c W H bν H (x)] ≤ X x∈X H E h c W H −Z bν H (x) i =E " c W H −Z · X x∈X H bν H (x) # =E c W H −Z . C.2 Proof of Theorem 3.2 We prove a slightly stronger upper bound. Proposition C.4.SMC (Algorithm 1) withNparticles achieves D TV (E[bν H ],π ⋆ H )≤ 1 √ N H X h=1 v u u t E π ref [ b V(x h−1 )]E π ref " V ⋆ (x h ) 2 b V(x h−1 ) # . Theorem 3.2 then follows from the fact thatV ⋆ (x h )≤C act V ⋆ (x h−1 )almost surely underx h ∼π ref (·|x h−1 ) and E π ref [ b V(x h−1 )]E π ref " V ⋆ (x h−1 ) 2 b V(x h−1 ) # = 1 +D χ 2 π ⋆ h−1 ∥bπ h−1 . Proof of Proposition C.4.We defineρ(x) = V ⋆ (x) b V(x) and M h = c W h ·E x h ∼bν h [ρ(x h )]. Then Eq. (3) withg(x) =ρ(x)implies(M h )is a martingale withM 0 =ZandM H = c W H . We can then decompose E| c W H −Z|≤ H X h=1 E|M h −M h−1 |. Next, we note that M h −M h−1 = c W h−1 1 N N X i=1 w i h ρ(x i h )−E x h−1 ∼bν h−1 [ρ(x h−1 )] ! = c W h−1 1 N N X i=1 V ⋆ (x i h ) b V( ̃x i h−1 ) −E x h−1 ∼bν h−1 [ρ(x h−1 )] ! . 19 Since the tuples( ̃x i h−1 ,x i h )are i.i.d. givenH h−1 , we can bound 1 c W 2 h−1 E h−1 (M h −M h−1 ) 2 ≤ 1 N Var x h−1 ∼bν h−1 ,x h ∼π ref (·|x h−1 ) " V ⋆ (x h ) b V(x h−1 ) # ≤ 1 N E x h−1 ∼bν h−1 " E x h ∼π ref (·|x h−1 ) [V ⋆ (x h ) 2 ] b V(x h−1 ) 2 # = : ∆ h−1 . Then, by Lemma C.2, it holds that E[ c W h−1 ]E[ c W h−1 ∆ h−1 ] = 1 N E π ref [ b V(x h−1 )]E π ref " V ⋆ (x h ) 2 b V(x h−1 ) # . Therefore, we can bound E| c W H −Z|≤ H X h=1 E[E h−1 |M h −M h−1 |] ≤ H X h=1 E h c W h−1 p ∆ h−1 i ≤ H X h=1 r E[ c W h−1 ]·E h c W h−1 ∆ h−1 i ≤ 1 √ N H X h=1 v u u t E π ref [ b V(x h−1 )]E π ref " V ⋆ (x h ) 2 b V(x h−1 ) # . Combining the inequalities above completes the proof. C.3 Insufficiency of Existing Analysis Most non-asymptotic analyses of SMC assume conditions at least as strong as theL ∞ closeness in Assump- tion 3.3 (Del Moral, 2004; Cérou et al., 2011; Whiteley et al., 2012). Another line of work (Marion and Schmidler, 2018; Lee and Santana-Gijzen, 2024) imposes assumptions on the transition kernel, which are therefore incomparable to those in this paper. We note that these approaches might fail to capture SMC convergence when we assume onlyχ 2 -closeness (Theorem 3.2). This is because many explicitly or implicitly control the variance(Var( c W h )) h∈[H] (Cérou et al., 2011; Whiteley et al., 2012; Schweizer, 2012, etc.). In contrast, our proof of Theorem 3.2 proceeds via the absolute deviationE|M H −Z|. The seemingly more natural attempt to study the varianceE(M H −Z) 2 must confront the fact thatM H = c W H = Q H h=1 1 N P N i=1 w i h is a sequential product. As the following lemma suggests,Var( c W h )need not be controlled when theχ 2 divergences(D χ 2 (π ⋆ h ∥bπ h )) h∈[H] are bounded. Lemma C.5.Suppose that b V(⊥) = 1. For anyh∈[H], it holds that Var( c W h ) =E( c W h − b Z h ) 2 ≥ Var x 1 ∼π 1 (E[ b V(x h )|x 1 ]) N . In particular, forH≥2, there exists a problem instance(V ⋆ , b V)such thatD χ 2 (π ⋆ h ∥bπ h )≤2, and both Assumption 3.1 and Assumption 3.7 holds withC act = 2, but SMC withNparticles incurs max h∈[H] Var( c W h )≥ 2 ⌊H/2⌋ −2 N . Therefore, if convergence of SMC is established via upper bounds onVar( c W h ), the rate can be vacuous unless we haveN≥exp(Ω(H))particles. For example, Schweizer (2012) study SMC through the following relation (cf. Lemma 2.1 therein) forf:X H →[0,1]: E E bν H [f]−E π ⋆ H [f] 2 ≤2Var( c W H ·E bν H [f]) + 2Var( c W H ). 20 Consequently, Schweizer (2012) establish upper bounds of the form N·Var( c W H ·E bν H [f])≤C 0 (f) +C 1 (f)·ε N , whereC 0 ,C 1 are two problem-dependent functionals, andε N is defined so that ε N ≥max h∈[H] Var( c W h ). This implies that the analysis in Schweizer (2012) cannot recover the upper bound of Theorem 3.2 (and Theorem 3.5). Proof of Lemma C.5.For anyh≤ℓ, we define e V ℓ (x h ) =E[ b V(x ℓ )|x h ]andρ ℓ (x h ) = e V ℓ (x h ) b V(x h ) , and we define M h,ℓ = c W h E bν h [ρ ℓ ]. Then it is straightforward to verify that(M h,ℓ ) h∈[ℓ] is a martingale withM 0,ℓ = b Z ℓ and M ℓ,ℓ = c W ℓ . Therefore, we can lower bound E( c W ℓ − b Z ℓ ) 2 ≥E(M 1,ℓ − b Z ℓ ) 2 =E 1 N N X i=1 e V ℓ (x i 1 ) b V( ̃x i 0 ) −E bν 0 [ρ ℓ ] ! 2 = 1 N E x 1 ∼π 1 [ e V ℓ (x 1 ) 2 ]− b Z 2 ℓ , where we note that ̃x i 0 =⊥fori∈[N]. Now, considern=⌊H/2⌋. Consider the following simple example: •For eachh∈[H],X h =(h,0),(h,1), andP((h+ 1,i)|(h,i)) = 1fori∈0,1. •The initial distribution is given byπ 1 ((1,0)) = 1 2 n =π 1 ((1,1)). •The reward function isr≡1, and henceV ⋆ (x) = 1for allx∈X. •For eachh∈[H], we set b V((h,1)) = 1and b V((h,0)) = 2 h forh≤n, and b V((h,0)) = 2 (2n−h) + for h≥n. Then, it is clear that both Assumption 3.1 and Assumption 3.7 hold withC act = 2, andbπ h is given by bπ((h,0)) = p b V((h,0)) p b V((h,0))+1−p , and hencebπ((h,0))∈[p, 1 2 ]. This immediately impliesD χ 2 (π ⋆ h ∥bπ h )≤2for any h∈[H]. However, we can then calculate e V n ((1,0)) = 2 n , and henceE[ e V n (x 1 ) 2 ]≥p·2 2n = 2 n . This gives the desired statement. C.4 Proof of Theorem 3.5 We prove the following general version of Theorem 3.5. Theorem C.6.SMC withNparticles achieves the following for anyM≥1,η≥1, D TV (E[bν H ],π ⋆ H )≤H r Mη N + H X h=1 Cov M (π ⋆ h ∥bπ h ) + Cov act η,h (π ⋆ ∥π ref ) , where we define Cov act η,h (π ⋆ ∥π ref ) : =P x h−1 ∼π ⋆ h−1 ,x h ∼π ⋆ (·|x h−1 ) π ⋆ (x h |x h−1 ) π ref (x h |x h−1 ) ≥η =P x h−1 ∼π ⋆ h−1 ,x h ∼π ⋆ (·|x h−1 ) V ⋆ (x h ) V ⋆ (x h−1 ) ≥η . 21 The quantityCov act η,h (π ⋆ ∥π ref )is the action-level analogue of Definition 3.4. Under Assumption 3.1, this additional term is0whenη≥C act , recovering Theorem 3.5. Proof.We follow the notation of the proof of Theorem 3.2 (Appendix C.2). Recall that M h −M h−1 = c W h−1 1 N N X i=1 V ⋆ (x i h ) b V( ̃x i h−1 ) −E x h−1 ∼bν h−1 [ρ(x h−1 )] ! , where the tuples( ̃x i h−1 ,x i h )are i.i.d. givenH h−1 . By Proposition B.1, for any fixed parameterR >0, we can bound 1 c W h−1 E h−1 |M h −M h−1 | ≤ v u u t R N E x h−1 ∼bν h−1 " V ⋆ (x h−1 ) b V(x h−1 ) # + 2E x h−1 ∼bν h−1 ,x h ∼π ref (·|x h−1 ) " V ⋆ (x h ) b V(x h−1 ) I ( V ⋆ (x h ) b V(x h−1 ) ≥R )# By Lemma C.2, we have E h c W h−1 q E x h−1 ∼bν h−1 [ρ(x h−1 )] i ≤ q E[ c W h−1 ]E[ c W h−1 E x h−1 ∼bν h−1 [ρ(x h−1 )]]≤ q b Z h−1 ·Z, and similarly, for anyη >0, E " c W h−1 E x h−1 ∼bν h−1 ,x h ∼π ref (·|x h−1 ) " V ⋆ (x h ) b V(x h−1 ) I ( V ⋆ (x h ) b V(x h−1 ) ≥R )## =E x h−1 ∼π h−1 ,x h ∼π ref (·|x h−1 ) " V ⋆ (x h )I ( V ⋆ (x h ) b V(x h−1 ) ≥R )# ≤E x h−1 ∼π h−1 ,x h ∼π ref (·|x h−1 ) " V ⋆ (x h )I ( V ⋆ (x h−1 ) b V(x h−1 ) ≥η −1 R ) +V ⋆ (x h )I V ⋆ (x h ) V ⋆ (x h−1 ) ≥η # =Z· " P x h−1 ∼π ⋆ h−1 V ⋆ (x h−1 ) b V(x h−1 ) ≥η −1 R ! +P x h−1 ∼π ⋆ h−1 ,x h ∼π ⋆ (·|x h−1 ) V ⋆ (x h ) V ⋆ (x h−1 ) ≥η # , where we useπ h−1 (x h−1 )·V ⋆ (x h−1 ) =π ⋆ h−1 (x h−1 )·Zforx h−1 ∈X h−1 andπ ref (x h |x h−1 )·V ⋆ (x h ) =π ⋆ (x h | x h−1 )·Z. Therefore, we can chooseR=Mη Z b Z h−1 to derive 1 Z E|M h −M h−1 |≤ r Mη N + 2P x h−1 ∼π ⋆ h−1 V ⋆ (x h−1 ) b V(x h−1 ) ≥M· Z b Z h−1 ! + 2P x h−1 ∼π ⋆ h−1 ,x h ∼π ⋆ (·|x h−1 ) V ⋆ (x h ) V ⋆ (x h−1 ) ≥η . Taking summation completes the proof. C.5 Proof of Theorem 3.6 We first prove the following lemma. Lemma C.7.Under Assumption 3.3 and Assumption 3.1, for anyδ∈(0,1), if we run SMC (Algorithm 1) withN= Ω(HC 4 ∞ C 2 act log(H/δ))particles, then with probability at least1−δ, it holds that| c W H −Z|≤Z/2. Proof.We follow the notation of the proof of Theorem 3.2 (Appendix C.2). Recall that M h −M h−1 = c W h−1 1 N N X i=1 V ⋆ (x i h ) b V( ̃x i h−1 ) −E x h−1 ∼bν h−1 [ρ(x h−1 )] ! , 22 where the tuples( ̃x i h−1 ,x i h )are i.i.d. givenH h−1 . Note that by Assumption 3.1, it holds that almost surely 0≤ V ⋆ (x i h ) b V( ̃x i h−1 ) = V ⋆ (x i h ) V ⋆ ( ̃x i h−1 ) · V ⋆ ( ̃x i h−1 ) b V( ̃x i h−1 ) ≤C act C ∞ . Using the fact that for a random variableY∈[0,A], we can boundE[e λ(Y−E[Y]) ]≤e λ 2 A 2 /8 , we have that for anyλ∈R, E h−1 [exp(λ(M h −M h−1 ))] =E h−1 " exp λ c W h−1 · 1 N N X i=1 V ⋆ (x i h ) b V( ̃x i h−1 ) −E bν h−1 [ρ(x h−1 )] !!# ≤exp 1 N λ 2 C 2 ∞ C 2 act c W 2 h−1 ≤exp 1 N λ 2 C 4 ∞ C 2 act M 2 h−1 . By Freedman’s inequality, for anyh∈[H], it follows that with probability1−δ, we have that |M h −Z|≤ h−1 X i=1 λC 4 ∞ C 2 act M 2 i N + log(2/δ) λ . Choosingλ= 4log(2H/δ)/Zand using the union bound, it follows that with probability1−δ, for allh∈[H], |M h −Z|≤ 4 log(2/δ)C 4 ∞ C 2 act N h−1 X i=0 M 2 i Z + Z 4 .(6) Since we have chosenN= Ω(Hlog(H/δ)C 4 ∞ C 2 act ), it follows from induction onhthat in the event that Eq. (6) holds, we have that|M h −Z|≤Z/2for allh∈[H]. In particular, this implies that| c W H −Z|≤Z/2with probability at least1−δ. Proof of Theorem 3.6.In any given round, letbpbe the distribution of the output of Algorithm 1 with Option 2 (when Algorithm 1 restarts we regard it as outputing the symbol “restart”). Then, the probability that the algorithm outputs anyx∈X H is given by bp(x) :=E " min ( 1, c W H 2C ∞ b Z 1 ) ·bν H (x) # ≤ Z·π ⋆ H (x) 2C ∞ b Z 1 , where we have used Lemma C.2. Moreover, using that2C ∞ b Z 1 ≥ 2Z≥ c W H with probability1− δ 2C 2 ∞ by Lemma C.7, for any subsetX⊂X H , bp(X) =E " min ( 1, c W H 2C ∞ b Z 1 ) ·bν H (X) # ≥ Z·π ⋆ H (x) 2C ∞ b Z 1 − δ 2C 2 ∞ . In particular, it holds that Z 2C ∞ b Z 1 − δ 4C 2 ∞ ≤bp (x̸=restart)≤ Z 2C ∞ b Z 1 , and hence using b Z 1 /Z≤C ∞ , we know that for anyX⊂X H π ⋆ H (X)−δ≤bp(X|not restart)≤(1 +δ)π ⋆ H (X), and henceD TV (π ⋆ H ,bp(·|not restart))≤δ . Finally, using the guarantee of rejection sampling, we know the number of outer loop steps is bounded byO(C 2 ∞ log(1/δ))by noting that b Z 1 /Z≤C ∞ . 23 C.6 Lower Bound for SMC with Exact Value Function In the following proposition, we show that the horizon dependence of SMC when b V=V ⋆ is not an artifact of our analysis. Proposition C.8.There exists a problem instance where b V=V ⋆ and Assumption 3.1 holds withC act = 2, however SMC withNparticles must incur D TV (E[bν H ],π ⋆ H )≥cmin ( 1, √ H N ) . Proof.We construct a problem instance as follows. Fixλ >0. We considerX h =0,1 h , and define the transition kernelPand value function b V=V ⋆ as follows: •For anyx, letπ ref (·|x) = unif((x,0),(x,1)). •Let b V=V ⋆ :X →Rbe defined recursively as V ⋆ (⊥) = 0, V ⋆ (x,0) =V ⋆ (x), V ⋆ (x,1) = (1 +λ)V ⋆ (x). •Then, it holds thatC act ≤1 +λ, andπ ⋆ H = Ber(p) ⊗H , wherep= 1+λ 2+λ . Under this construction, we can rewrite SMC as follows (wherebν 0 =δ ⊥ ). •Forh≥1, sampleNparticles ̃x 1 h−1 ,..., ̃x N h i.i.d. ∼bν h−1 (·)and generatesa i h ∼unif(0,1)independently. •Assign weightsw i h = 1 +λa i h to particlex i h = ( ̃x i h−1 ,a i h ). •Define weighted empirical measurebν h : = 1 W h P N i=1 w i h δ x i h , whereW h =N+λ P N i=1 a i h . We make the following claims, proven below. Claim C.9.It holds thatE[bν H ] = Ber(p N ) ⊗H , wherep N is defined in Eq. (7). Claim C.10.It holds thatp N ≤ 1+λ 2+λ − c λ N , wherec λ = 2λ(1+λ) (2+λ) 3 . Now, we can lower bound D TV (E[bν H ],π ⋆ H ) =D TV (Bin(H,p),Bin(H,p N ))≥cmin1, √ H|p−p N |, wherec >0is an absolute constant. Choosingλ= 1completes the proof of Proposition C.8. We prove the auxiliary claims: Proof of Claim C.9.By definition, for anyx∈X h−1 anda∈0,1, bν h (x,1) = 1 W h N X i=1 w i h I ̃x i h−1 =x,a i h =a. Note thata i h and ̃x i h−1 are independent, we can calculate E[bν h (x,1)] =E " 1 W h N X i=1 w i h Ia i h = 1·I ̃x i h−1 =x # =E " bν h−1 (x)· (1 +λ) P N i=1 a i h N+λ P N i=1 a i h # . Note thatA h = P N i=1 a i h ∼Bin(N, 1 2 )is independent ofbν h−1 . Then, we know E[bν h (x,1)] =p N E[bν h−1 (x)], p N = (1 +λ)E A∼Bin(N, 1 2 ) A N+λA .(7) 24 Applying this equation recursively gives the desired result. Proof of Claim C.10.We letY= 2A N −1so thatY h symmetrically distributed on[−1,1]. Then we can write N N+λA = 2 2 +λ(Y+ 1) = 2 2 +λ · 1 1 + λ 2+λ Y = 2 2 +λ X k≥0 (−1) k λY 2 +λ k . Note thatEY k = 0for odd integerkandEY 2 = 1 N , we can conclude E N N+λA ≥ 2 2 +λ 1 + λ 2 +λ 2 1 N ! . Reorganizing yields p N = (1 +λ)E A N+λA = 1 +λ λ 1−E N N+λA ≤ 1 +λ 2 +λ − 2λ(1 +λ) (2 +λ) 3 N . D Proofs for SMC-RS Analogously to Appendix C, we introduce the following quantity for Algorithm 2: W h : =E x h−1 ∼bν h−1 ,x h ∼π ref (·|x h−1 ) " b V(x h ) b V(x h−1 ) # , c W h : = h Y ℓ=1 W ℓ . We defineH h =S 1 ,·,S h to be the full history of the execution of SMC-RS (Algorithm 2) up to the end of iterationh. We writeE h [·]to be the conditional distribution with respect toH h . Lemma D.1.For steph∈[H]of SMC-RS (Algorithm 2), givenH h−1 , the setS h consists of i.i.d. samples from the distributionbμ h given by bμ h (x h ) = 1 W h E x h−1 ∼bν h−1 " π ref (x h |x h−1 ) b V(x h ) b V(x h−1 ) # ,∀x h ∈X h . Hence, for anyg h :X h →R, it holds that E h c W h ·E bν h [g h ] i =E h c W h ·E bμ h [g h ] i = 1 b Z 1 E x h ∼π h h b V(x h )g h (x h ) i .(8) Proof of Lemma D.1.The first claim follows immediately from the analysis of rejection sampling: For anyx h ∈X h , by Bayes’ rule, we have P(x h |accept)∝P(accept|x h )·P(x h )∝bμ h (x h ). To prove the second claim, we prove the following result, from which Eq. (8) follows inductively: E h−1 [W h ·E bν h [g h ]] =E h−1 [W h ·E bμ h [g h ]] =E x h−1 ∼bν h−1 ,x h ∼π ref (·|x h−1 ) " b V(x h )g h (x h ) b V(x h−1 ) # . 25 In particular,E[ c W h ] = b Z h / b Z 1 forh≥1and E h c W H bν H (x) i =Z·π ⋆ H (x)/ b Z 1 ,∀x∈X H . Further, we defineρ(x) = V ⋆ (x) b V(x) and M h = c W h ·E x h ∼bν h [ρ(x h )]. Then Lemma D.1 withg(x) =ρ(x)implies(M h )is a martingale withM 0 =ZandM H = c W H . Therefore, similar to Lemma C.3, we have the following upper bound. Lemma D.2.For Algorithm 2, it holds that D TV (E[bν H ],π ⋆ H )≤ 1 2Z E| c W H −Z|≤ 1 2Z H X h=1 E|M h −M h−1 |. D.1 Proof of Theorem 3.8 Note thatM h −M h−1 = c W h (E bν h [ρ]−E bμ h [ρ]) , andbν h =unif(S h ), whereS h consists of i.i.d samples frombμ h . Then, we can bound E h−1 |E bν h [ρ h ]−E bμ h [ρ h ]|≤ v u u t E h−1 1 N X x h ∈S h ρ(x h )−E bμ h [ρ] 2 = s E bμ h [ρ(x h ) 2 ]−(E bμ h [ρ(x h )]) 2 N , and hence √ NE|M h −M h−1 |≤E c W h q E bμ h [ρ(x h ) 2 ]−(E bμ h [ρ(x h )]) 2 ≤ r E[ c W h ] E h c W h E bμ h [ρ(x h ) 2 ] i −E h c W h (E bμ h [ρ(x h )]) 2 i ≤ v u u t b Z h E x h ∼π h " V ⋆ (x h ) 2 b V(x h ) # −Z 2 =Z s E x h ∼π ⋆ h π ⋆ (x h ) bπ(x h ) −1 =Z q D χ 2 (π ⋆ h ∥bπ h ), where the third line usesE[ c W h ]E h c W h (E bμ h [ρ(x h )]) 2 i ≥ E[ c W h E bμ h [ρ(x h )]] 2 =Z 2 (Cauchy inequality and Lemma D.1), and the last line follows from the definition ofπ ⋆ ,bπ, andχ 2 -divergence. Taking summation completes the proof. D.2 Analysis of SMC-RS with Heavy-tailed Errors Parallel to SMC, we show that SMC-RS also enjoys an upper bound that depends only on coverage (Definition 3.4). Theorem D.3.Under Assumption 3.7, suppose that SMC-RS (Algorithm 2) is instantiated withη≥ b C act . It holds that for anyM≥1, Algorithm 2 achieves D TV (E[bν H ],π ⋆ H )≤H r M N + H X h=1 Cov M (π ⋆ h ∥bπ h ). The convergence rate of Theorem D.3 improves upon that of SMC (Theorem 3.5) by a factor ofC act , though the same factor reappears in the time complexity. The expected time complexity bound matches Theorem 3.8. 26 Proof.We follow the proof of Theorem 3.8 (Appendix D.1). By Proposition B.1, it holds that E h−1 |E bν h [ρ h ]−E bμ h [ρ h ]|=E h−1 1 N X x h ∈S h ρ(x h )−E bμ h [ρ] ≤ r R N E x h ∼bμ h [ρ(x h )] + 2RE x h ∼bμ h [ρ(x h )Iρ(x h )≥R], where we useS h consists ofNi.i.d samples frombμ h . Therefore, we can bound E|M h −M h−1 |≤2 r R N E c W h q E x h ∼bμ h [ρ(x h )] + 2E h c W h E x h ∼bμ h [ρ(x h )Iρ(x h )≥R] i Further, by Lemma D.1, we have E c W h q E x h ∼bμ h [ρ(x h )] ≤ q E[ c W h ]E[ c W h E x h ∼bμ h [ρ(x h )]]≤ q b Z h ·Z, and E h c W h ·E x h ∼bμ h [ρ(x h )Iρ(x h )≥R] i =Z·P x∼π ⋆ h (ρ(x h )≥R). ChoosingR=M Z b Z h gives E|M h −M h−1 |≤2Z r M N + 2ZCov M (π ⋆ h ∥bπ h ). Taking summation completes the proof. D.3 Faster Convergence for SMC-RS In this section, we present and analyze a modification of SMC-RS, which we call SMC-RS with restart (Algorithm 3). Under the following assumption, we prove that Algorithm 3 achieves exponential convergence (analogous to Theorem 3.6 for SMC). Assumption D.4.There are at mostηvalues ofx h+1 for eachx h so thatπ ref (x h+1 |x h )>0, and these are efficiently enumerable. Algorithm 3Diffusion Monte Carlo Input:Transition kernelπ ref , value function b V. Parameter:initial sample sizeN≥1. InitializeS 0 to beNcopies of⊥. forh= 1,·,Hdo For eachx h−1 ∈S h−1 , compute e V(x h−1 ) =E π ref [ b V(x h )|x h−1 ]. DefineW h−1 = 1 N P x h−1 ∈S h−1 e V(x h−1 ) b V(x h−1 ) . Define the weighted empirical measureeμ h−1 = 1 NW h−1 P x h−1 ∈S h−1 e V(x h−1 ) b V(x h−1 ) δ x h−1 . Generates ̃x i h−1 ∼eμ h−1 ,x i h ∼bπ(·| ̃x i h−1 )independently fori∈[N]. DefineS h =x i h i∈[N] andbν h =Unif(S h ). Define c W H = Q H h=1 W h . Output:With probabilitymin n c W H e Z 1 ,1 o , outputx∼bν H , and otherwise restart the algorithm. We prove the following guarantee: 27 Theorem D.5.Suppose that Assumption 3.3 and Assumption D.4 hold, and we denoteε : =C ∞ −1. Further, suppose that we haveZ≤ e Z 1 ≤JZ. Then Algorithm 3 withOutput Option 2samples from a distribution μthat satisfies D TV (μ,π ⋆ H )≤δ, as long asN≥Ω(HC 2 ∞ ε 2 log(JH/δ)), using a number of outer loop steps that is bounded byO(J 2 log(1/δ)). Under Assumption D.4, we can always choose e Z 1 =C ∞ b Z 1 , so thatZ≤ e Z 1 ≤C 2 ∞ Z. Further, we can run Algorithm 3 1 time solely for estimatingZ, with choice e Z 1 = 2 c W H satisfiesZ≤ e Z≤4Zwith high probability. Similar to the proof of Theorem 3.6, we first state and prove the following lemma (as an analogue to Lemma C.7). Theorem D.5 then follows from the argument in Appendix C.5. Lemma D.6.Under the condition of Theorem D.5, for anyδ∈(0,1), if we run SMC-RS (Algorithm 3) withN= Ω(HC 2 ∞ ε 2 log(H/δ))particles, then with probability at least1−δ, it holds that| c W H −Z|≤Z/2. Proof of Lemma D.6.We follow the proof of Theorem 3.8 (Appendix D.1). Recall that M h −M h−1 c W h = 1 N N X i=1 ρ(x i h )−E bμ h [ρ] ! , wherex 1 h ,·,x N h areNi.i.d. samples frombμ h (givenH h−1 ). Note that by Assumption 3.3, it holds that ρ(x h )−1∈[−ε,ε]for anyx h ∈X h . This implies thatE x h ∼bμ h [e λ(ρ(x h )−E bμ h [ρ]) ]≤e λ 2 ε 2 /8 forλ∈R, and hence E h−1 [exp(λ(M h −M h−1 ))] =E h−1 " exp λ c W h · 1 N N X i=1 ρ(x i h )−E bμ h [ρ] !!!# ≤exp 1 N λ 2 ε 2 c W 2 h ≤exp 1 N λ 2 C 2 ∞ ε 2 M 2 h−1 , where we useM h−1 =E h−1 [M h ] = c W h E bμ h [ρ]≥C −1 ∞ c W h . By Freedman’s inequality, it follows that for anyh∈[H], with probability1−δ, we have that |M h −Z|≤ h−1 X i=1 λC 2 ∞ ε 2 M 2 i N + log(2/δ) λ . Choosingλ= 4log(2H/δ)/Zand using the union bound, it follows that with probability1−δ, for allh∈[H], |M h −Z|≤ 4 log(2/δ)C 2 ∞ ε 2 N h−1 X i=0 M 2 i Z + Z 4 . Since we have chosenN= Ω(Hlog(H/δ)C 2 ∞ ε 2 ), it follows from induction onhthat in the event that Eq. (6) holds, we have that|M h −Z|≤Z/2for allh∈[H]. In particular, this implies that| c W H −Z|≤Z/2with probability at least1−δ. E A Unified Perspective on Backtracking and Particle Filtering Our main theoretical results demonstrated that particle filtering methods like SMC can achieve strong guarantees under the same assumptions on b Vas the backtracking-based method VGB introduced by Rohatgi et al. (2025) — while improving parallel runtime from e O (H 2 )to e O (H). In this section, we show that the connection goes deeper: foranyproblem instance, the execution of VGB can becoupledwith the execution of SMC-IND, a variant of SMC in which the children of each particle are sampled independently. 28 We defer formal definitions until after stating the result (Theorem E.1), but we make several remarks for context. Henceforth, we specify to the autoregressive setting (Remark 2.1) in which VGB was defined Rohatgi et al. (2025). Recall that VGB implements a single-particle random walk in which the allowed transitions can not only add a token to the current particle (i.e.a 1:h 7→a 1:h+1 ) but also backtrack (i.e.a 1:h 7→a 1:h−1 ). For technical reasons, we augment the state space of the random walk with a statesthat is only adjacent to the empty string⊥. See Appendices E.1 and E.2 for the formal definitions ofSMC-INDand the VGB random walk. Theorem E.1.LetS DMC be the (random) multiset of particles visited bySMC-INDwithNinitial particles. LetS VGB be the (random) multiset of particles visited by VGB (initialized ats) before theN+ 1-st visit tos. Then there is a coupling so thatS DMC =S VGB \s(with multiplicity) almost surely. Intuitively, each particlea 1:h visited bySMC-INDcorresponds to an interval of time in which the VGB random walk started ata 1:h , ended ata 1:h , and never visited the parent nodea 1:h−1 (where we take the parent of⊥to bes). This demonstrates that the paradigm of backtracking to tame error amplification Rohatgi et al. (2025) is, in a sense, equivalent to a form of particle filtering. Outline of appendix.In Appendix E.1 we introduce the VGB random walk (slightly modified for technical reasons). In Appendix E.2 we introduce theSMC-INDstochastic process. In Appendix E.3 we prove Theorem E.1. E.1 Background on VGB The (non-lazy) VGB random walk Rohatgi et al. (2025) is defined on state spaceX=X 0 ⊔·⊔X H whereA is the token space andX h :=A h . For technical convenience (specifically, to avoid casework at step0when coupling VGB withSMC-IND), we introduce an auxiliary statesthat is not in the original definition. We define the transition kernelP VGB as follows. First,salways transitions to⊥: P VGB (⊥|s) = 1. Second, anya 1:h ∈A h with0≤h < Hcan transition to either a “child”a 1:h+1 or the “parent”a 1:h−1 : P VGB (a 1:h+1 |a 1:h ) = π ref (a h+1 |a 1:h ) b V(a 1:h+1 ) b V(a 1:h ) + P a ′ h+1 π ref (a ′ h+1 |a 1:h ) b V(a 1:h ,a ′ h+1 ) , P VGB (a 1:h−1 |a 1:h ) = b V(a 1:h ) b V(a 1:h ) + P a ′ h+1 π ref (a ′ h+1 |a 1:h ) b V(a 1:h ,a ′ h+1 ) , with the convention thata 1:0 =⊥(i.e. the empty string) anda 1:−1 =s. Third, anya 1:H ∈ A H must transition to its parent: P VGB (a 1:H−1 |a 1:H ) = 1. The transition kernel of the original VGB random walk Rohatgi et al. (2025) is identical conditioned on never visitings. Moreover, sincesis only reachable from⊥(and only transitions to⊥), our modification only affects the execution of VGB by stochastically inserting copies of the sequence(s,⊥)into VGB’s random trajectory. For notational convenience, it is useful to define a transition kernelP down as the VGB transition kernel conditioned on “downward” moves, i.e. P down (a 1:h+1 |a 1:h ) = π ref (a h+1 |a 1:h ) b V(a 1:h+1 ) P a ′ h+1 π ref (a ′ h+1 |a 1:h ) b V(a 1:h ,a ′ h+1 ) . E.2 Definition of SMC-IND In Algorithm 4, we describe howSMC-INDstochastically constructs multisets of particlesS 0 ,...,S H for a given problem instance. Note that there is no specified output mechanism, since the coupling between SMC-IND and VGB will apply to the entire multiset of particles. 29 Algorithm 4Sequential Monte Carlo with Independent Sampling (SMC-IND) Input:Autoregressive language modelπ ref , value function b V. Parameter:initial sample sizeN≥1. InitializeS 0 to beNcopies of⊥. forh= 1,·,Hdo Initialize a multi-setS h =. fora 1:h−1 ∈S h−1 do SampleD∼Geom(P VGB (a 1:h−2 |a 1:h−1 ))(with conventiona 1:−1 =s; see Appendix E.1) for1≤i≤Ddo Samplea 1:h ∼P down (·|a 1:h−1 ). UpdateS h ←S h ∪a 1:h . E.3 Coupling VGB with SMC-IND We interpret the executions ofSMC-INDand VGB as stochastically constructing forests of particles. We then show that these forests are actually the same (up to occurrences ofs) when the randomness is appropriately coupled. Infinite-particleSMC-INDprocess.The execution ofSMC-INDwithN=∞naturally defines a rooted forestF DMC where each node is labelled by a particle inS 0 ⊔·⊔S H . The roots are the particles inS 0 . For anyh >0, the parent of a particle inS h is the particle inS h−1 that birthed it. Note that there may be multiple (or even infinitely many) occurrences of any particlea 1:h inS h , soF DMC may contain multiple nodes with the same label. The parent of a node labelleda 1:h always has labela 1:h−1 . Infinite-time VGB process.We next show how an execution of VGB in the autoregressive treeTcan be interpreted as a rooted treeF VGB , similar to above. Fix an infinite trajectory(x 0 ,x 1 ,x 2 ,x 3 ,...)of VGB withx 0 =s. Suppose thatsoccurs infinitely often in the trajectory. The root node ofF VGB is indexed byN, and labeleds. Every other node is indexed by an interval[t,t ′ ]⊂Nwith the property thatx t−1 =x t ′ +1 is the parent ofx t =x t ′ inT, and this parent does not occur withinx t ,x t+1 ,...,x t ′ . This node is labeled withx t , and its parent inF VGB is the unique node with labelx t−1 whose interval contains[t,t ′ ]. Lemma E.2.Suppose that VGB almost surely visitssinfinitely often. There is a coupling of the randomness ofF DMC andF VGB such thatF DMC is almost surely equal to the forestF VGB \s. Proof.We construct the coupling layer by layer. By the lemma assumption, it is clear that the first layer of F DMC is almost surely identical to that ofF VGB . Now fixh≥1and condition on the forest structure and labelsx t (but not the indices[t,t ′ ]themselves) of the firsthlayers ofF VGB . Fix any nodeιwith labela 1:h−1 . Consider the law of the VGB random walk between these two visits toa 1:h−1 . The walk is restricted to the subtree rooted ata 1:h−1 , but since the walk is Markovian, its law is otherwise unchanged by the conditioning (and it is also independent of the children of other nodesι ′ ̸=ιat layerh). Letp=P(a 1:h−2 |a 1:h−1 )(with the conventiona 1:h−2 =sifh= 1). The number of childrenD ′ ofιis the number of times that the walk goes to a child ofa 1:h−1 inTbefore it returns toa 1:h−2 . Thus,P[D ′ =k] = (1−p) k p for anyk∈0,1,2,.... That is,D ′ is a geometric random variable with success probabilityp. Moreover, the label of each child of ιis independent and distributed according toP down (·|a 1:h−1 ). Thus, the coupling can be extended to the children ofι. Proof of Theorem E.1.The firstNtrees ofF DMC can be coupled to the forest induced bySMC-IND withNinitial particles. Similarly, the firstNtrees ofF VGB correspond exactly to the prefix of the trajectory of VGB beforesis visitedN+ 1times. The claim then follows from Lemma E.2. 30 F Proof of Theorem 3.9 In this appendix we formally state the requisite definitions for Theorem 3.9, and prove the theorem. In Appendix F.1, we formalize the definition of a myopic particle filtering algorithm. In Appendix F.2 we state Theorem F.5, which directly implies Theorem 3.9. In Appendix F.3, we provide intuition for and formally prove Theorem F.5. F.1 Myopic Particle Filtering Algorithms Definition F.1.Amyopic particle filtering algorithm withNparticlesis defined as follows. The algorithm computes a stochastic sequence of multisetsS 0 ,...,S H whereS h ⊂ A h for all0≤h≤H, satisfying the following properties: 1. It holds almost surely that for all1≤h≤H, for eachy 1:h ∈S h , we havey 1:h−1 ∈S h . 2.|S h |≤Nfor allhalmost surely. 3.The law of(S 0 ,...,S h )is determined by(π ref (a 1:h ) :a 1:h ∈ A h )and( b V(a 1:k ) :a 1:k ∈ A k ,k≤h)for allh. The algorithm then (stochastically) outputs any element ofS H . The first condition is a natural formalization of what it means to be a particle filtering method, i.e. a particle inS h cannot appear “out of nowhere”; rather, it must have a parent inS h−1 . The second condition asserts that the number of particles is always at mostN. The third condition is the “myopic” condition, which enforces that, at the level of distributions, the algorithm does not use information from later stepsk > hto determine the multisetS h . Remark F.2(Sequential Monte Carlo and variants).It is straightforward from Algorithm 1 to see that Sequential Monte Carlo is indeed a myopic particle filtering algorithm, as is Sequential Monte Carlo with Rejection Sampling (Algorithm 2). Remark F.3(Computational efficiency).We remark that Definition F.1 does not enforce any bound on computational efficiency or query complexity; in particular, a myopic particle filtering algorithm is allowed to examine b V(a 1:h )for alla 1:h ∈A h before deciding on the set of particlesS h ; it is not restricted to e.g. only querying the children of particles inS h−1 . This only makes our impossibility result stronger. That said, it is an interesting open question to prove an analogous result to Theorem 3.9 that applies toallalgorithms that makeo(H 2 )queries toπ ref and b V. Such a result would be formally incomparable to Theorem 3.9. F.2 Specialized Setting and Formal Theorem Statement Since we are proving a lower bound, it suffices to consider a special case of the general setting from Section 2. Thus, we restrict to the autoregressive generation setting (Remark 2.1) and moreover setπ ref :=Unif(A H ) whereA=0,1. We define a problem instance by specifying some distributionμ∈∆(A H )and functions(μ h ) h withμ h : A h →R ≥0 . These induceV ⋆ , b Vby V ⋆ (a 1:h ) := μ(a 1:h ) π ref (a 1:h ) and b V(a 1:h ) := bμ h (a 1:h ) π ref (a 1:h ) . Note that the goal distributionπ ⋆ is preciselyμ, and the third condition of Definition F.1 precisely enforces that the law of(S 0 ,...,S h )is determined by(bμ 0 ,...,bμ h ). For Assumption 3.1 to hold with parameterC act , it suffices to haveμ(a h+1 |a 1:h )≤C act /2for alla 1:h+1 ∈ A h+1 . Moreover, Assumption 3.3 holds with parameterC ∞ if and only ifbμisC ∞ -accurate forμin the following sense: Definition F.4.We say thatbμisκ-accurate forμ∈∆(A H )if it holds that bμ(a 1:h ) μ(a 1:h ) ∈[1/κ,κ] 31 for alla 1:h ∈A h , and moreoverbμ(a 1:H ) =μ(a 1:H )for alla 1:H ∈A H . We can now formally state the main result of this appendix, which directly implies Theorem 3.9. Theorem F.5.DefineN(H) :=log(H)/(4log log(H))for allH∈N. There is no myopic particle filtering algorithmAlgwith the following guarantee: fixHsufficiently large.Alguses at mostN(H)particles. For anyμ∈∆(A H ), for anye 3 -accuratebμ:A ≤H →R ≥0 , the execution ofAlgonbμhas outputo 1:H satisfying P o 1:H ∼Alg [o 1:H ∈E]≥H −1/5 for all eventsE ⊂A H withμ(E)≥1/2. Proof of Theorem 3.9.Immediate from Theorem F.5 and the preceding discussion on Assumptions 3.1 and 3.3. F.3 Proof of Theorem F.5 F.3.1 Intuition and Formal Construction To prove Theorem F.5, we construct a family of problem instances (each specified by a choice ofμand bμ 0 ,...,bμ H ) such that any myopic particle filtering algorithm with at mostNparticles must fail on at least one instance in the family. We do so recursively, by first constructing an instance forN= 1, thenN= 2, and so forth. The analysis will be similarly inductive. LetH:N→Nbe a function to be determined. Assume thatH(N)is a multiple ofH(N−1) + 2for allN >1. For eachN∈Nandy ⋆ ∈A H(N) , we defineμ N (·;y ⋆ )∈∆(A H(N) )andbμ N (·;y ⋆ ) :A ≤H(N) →R ≥0 recursively (inN) as follows. Intuition for construction.First, we provide intuition for theN= 1construction, which essentially follows Example 3.2 in Rohatgi et al. (2025). We will haveμ 1 (·;y ⋆ )be a product distribution where the marginalμ 1 (y h )is biased towardsy ⋆ h . We will then havebμ 1 (·;y ⋆ )be “delayed” compared toμ 1 (·;y ⋆ ), i.e. the marginal at stephis biased towardsy ⋆ h−1 instead ofy ⋆ h . Thus, the data ofbμ 1 1 (·;y ⋆ ),...,bμ 1 h (·;y ⋆ )is independent ofy ⋆ h , and so as formalized in Lemma F.9, any1-particle myopic particle filtering method must incur large sampling error. Next, we provide intuition for theN >1construction. The horizonH=H(N)is divided into blocks of sizeK=H(N−1) + 2. Againμ N (·;y ⋆ )is a product distribution where the marginal at stephis biased towardsy ⋆ h . In block[iK+ 1,(i+ 1)K], we definebμ N (·;y ⋆ )by “delaying” the dependence ony ⋆ iK+1 to step (i+ 1)K, and embedding a copy of the(N−1)-particle construction in the intervening steps. Intuitively, any N-particle myopic particle filtering algorithm has two choices at stepiK+ 1: either irrevocably guessy ⋆ iK+1 (i.e. all particlesy∈S iK+1 will have the same value ofy iK+1 ), or split up the particles so that some have different values ofy iK+1 . The basic idea, formalized in Lemma F.11, is that both choices lead to sampling error: the former because no data abouty ⋆ iK+1 is available at stepiK+ 1, and the latter by the inductive hypothesis on the(N−1)-particle construction. The multiple blocks are needed to amplify the error induced by the first choice. Making this argument precise requires a careful probabilistic analysis to ensure that the errors in the two cases cannot “cancel out”. Before proceeding to this analysis, we make the construction formal. Letγ 1 ,γ 2 ,·∈(0,1/2)be a sequence of parameters to be determined later. Formal construction: base case (N= 1).WriteH=H(1). We define μ 1 (y h |y 1:h−1 ;y ⋆ ) := (1/2−γ 1 ) I[y h ̸=y ⋆ h ] (1/2 +γ 1 ) I[y h =y ⋆ h ] and bμ 1 (y h |y 1:h−1 ;y ⋆ ) := 1/2ifh= 1 μ 1 (y h−1 |y 1:h−2 ;y ⋆ )if1< h < H 2μ 1 (y H−1:H |y 1:H−2 ;y ⋆ )ifh=H(1) . 32 Formal construction: recursive case (N >1).DefineK:=H(N−1) + 2. For any nonnegative integer iandh∈[H(N)]withiK < h≤(i+ 1)K, we define μ N (y h |y 1:h−1 ;y ⋆ ) := ( (1/2−γ N ) I[y h ̸=y ⋆ h ] (1/2 +γ N ) I[y h =y ⋆ h ] ifh=iK+ 1orh= (i+ 1)K μ N−1 (y h |y iK+2:h−1 ;y ⋆ iK+2:(i+1)K−1 )otherwise and bμ N (y h |y 1:h−1 ;y ⋆ ) := 1/2ifh=iK+ 1 bμ N−1 (y h |y iK+2:h−1 ;y ⋆ iK+2:(i+1)K−1 )ifiK+ 1< h <(i+ 1)K 2μ N (y iK+1 |y 1:iK ;y ⋆ )μ N (y (i+1)K |y 1:(i+1)K−1 ;y ⋆ )ifh= (i+ 1)K In the following lemma we check that the desired accuracy condition is satisfied for allNandy ⋆ . Lemma F.6.For anyN≥1andy ⋆ ∈A H(N) , it holds thatbμ N (·;y ⋆ )isexp(3 P N i=1 γ i )-accurate forμ N (·;y ⋆ ). Proof.We proceed by induction onN. FixN= 1. SetH=H(1). We observe thatbμ 1 (y 1:H ;y ⋆ ) =μ 1 (y 1:H ;y ⋆ ) and, for anyh < H, bμ 1 (y 1:h ;y ⋆ ) μ 1 (y 1:h ;y ⋆ ) = 1 2μ 1 (y h |y 1:h−1 ;y ⋆ ) ∈[1/(1 + 2γ 1 ),1/(1−2γ 1 )] ∈[e −3γ 1 ,e 3γ 1 ]. FixN >1and suppose that the claim holds forbμ N−1 . SetH=H(N)andK=H(N−1) + 2. For any h∈[H], ifh= (i+ 1)Kfor somei, then bμ N (y iK+1:(i+1)K |y 1:iK ;y ⋆ ) = 1 2 · (i+1)K−1 Y h ′ =iK+2 bμ N−1 (y h ′ |y iK+2:h ′ −1 ;y ⋆ iK+2:(i+1)K−1 ) ·2μ N (y iK+1 |y 1:iK ;y ⋆ )μ N (y (i+1)K |y 1:(i+1)K−1 ;y ⋆ ) =μ N−1 (y iK+2:(i+1)K−1 ;y ⋆ iK+2:(i+1)K−1 )·μ N (y iK+1 |y 1:iK ;y ⋆ )μ N (y (i+1)K |y 1:(i+1)K−1 ;y ⋆ ) =μ N (y iK+2:(i+1)K−1 |y 1:iK+1 ;y ⋆ )·μ N (y iK+1 |y 1:iK ;y ⋆ )μ N (y (i+1)K |y 1:(i+1)K−1 ;y ⋆ ) =μ N (y iK+1:(i+1)K |y 1:iK ;y ⋆ ). Thus, it holds thatbμ N (y 1:(i+1)K ;y ⋆ ) =μ N (y 1:(i+1)K ;y ⋆ ), and in particular,bμ N (y 1:H ;y ⋆ ) =μ N (y 1:H ;y ⋆ ). For anyiK+ 1≤h <(i+ 1)K, we have bμ N (y 1:h ;y ⋆ ) =μ N (y 1:iK ;y ⋆ )bμ N (y iK+1:h |y 1:iK ;y ⋆ ) =μ N (y 1:iK ;y ⋆ )· 1 2 ·bμ N−1 (y iK+2:h ;y ⋆ iK+2:(i+1)K−1 ) ∈[e −3 P N−1 n=1 γ n ,e 3 P N−1 n=1 γ n ]·μ N (y 1:iK ;y ⋆ )· 1 2 ·μ N−1 (y iK+2:h ;y ⋆ iK+2:(i+1)K−1 ) ∈[e −3 P N n=1 γ n ,e 3 P N n=1 γ n ]·μ N (y 1:iK ;y ⋆ )·μ N (y iK+1 |y 1:iK ;y ⋆ )·μ N−1 (y iK+2:h ;y ⋆ iK+2:(i+1)K−1 ) ∈[e −3 P N n=1 γ n ,e 3 P N n=1 γ n ]·μ N (y 1:h ;y ⋆ ) which completes the proof. To show that anyN-particle myopic particle filtering method fails to coverμ N (·;y ⋆ )(for some choice of y ⋆ ), we will show that there are eventsF N (y ⋆ )that are extremely likely underμ N (·;y ⋆ )(for anyy ⋆ ) but extremely unlikely under the execution of anyN-particle myopic particle filtering method (for a uniformly random choice ofy ⋆ ). Definition F.7 formally defines these events. Definition F.8 formalizes the claim about these events that we will prove inductively. 33 Definition F.7(Key events for analysis).FixN= 1andH=H(1). We define F 1 (y ⋆ ) :=o 1:H : #1< h < H:o h =y ⋆ h ≥(1/2 +γ 1 /2)(H−2). FixN >1and writeH:=H(N)andK:=H(N−1) + 2. We define setsF N (y ⋆ )as follows: F ◦ N (y ⋆ ) := \ i n o 1:H :o iK+2:(i+1)K−1 ∈F N−1 (y ⋆ iK+2:(i+1)K−1 ) o F □ N (y ⋆ ) :=o 1:H : #i:o iK+1 =y ⋆ iK+1 ≥1/2 +γ N /2 F N (y ⋆ ) :=F ◦ N (y ⋆ )∩F □ N (y ⋆ ). Definition F.8(Inductive hypothesis for analysis).FixN≥1. For parameterδ N,1 ,δ N,2 ∈(0,1), we let IH N (δ N,1 ,δ N,2 )denote the following hypothesis. There are setsF N (y ⋆ )⊆A H(N) with the following properties: •For ally ⋆ ∈A H(N) , it holds that μ N (F N (y ⋆ );y ⋆ )≥1−δ N,1 •For anyN-particle particle filtering algorithmAlg, it holds that E y ⋆ ∼Unif(A H(N) ) P o∼Alg [o∈F N (y ⋆ )]≤δ N,2 where the probability is over outputsoofAlgexecuted on instancebμ N (·;y ⋆ ). F.3.2 Base Case for Analysis Lemma F.9.For anyy ⋆ ∈A H(1) , it holds that μ 1 (F 1 (y ⋆ );y ⋆ )≥1−exp −γ 2 1 H(1)−2 16 . Moreover, for any1-particle particle filtering algorithmAlg, E y ⋆ ∼Unif(A H(1) ) P o∼Alg [o∈F 1 (y ⋆ )]≤exp −γ 2 1 H(1)−2 12 whereAlgis executed on instancebμ 1 (·;y ⋆ ). Proof.LetX∼μ 1 (·;y ⋆ ). ThenX 1 ,...,X H are independent withP[X h =y ⋆ h ] = 1/2 +γ 1 for eachh∈[H]. It follows from a Chernoff bound that μ 1 (F 1 (y ⋆ );y ⋆ ) =P[#1< h < H:X h =y ⋆ h >(1/2 +γ 1 /2)H] ≥1−exp(−γ 2 1 (H(1)−2)/16) which proves the first claim of the lemma. Next, fix any1-particle particle filtering algorithmAlg. Sample y ⋆ ∼Unif(A H(1) )and letS 0 ,...,S H be the stochastic sequence of multisets obtained by executingAlgon bμ 1 (·;y ⋆ ). Letobe the output ofAlg. ThenS h =o 1:h for all0≤h≤H. Since the law ofS 0:h is determined by(bμ 1 0 (·;y ⋆ ),...,bμ 1 h (·;y ⋆ )), it holds from the definition ofbμ 1 (·;y ⋆ )that(S 0:h ,y ⋆ 1:h−1 )is independent ofy ⋆ h for each1< h < H. Thus,y ⋆ h is independent ofS h conditioned on(S 0:h−1 ,y ⋆ 1:h−1 ), and so we have P[o h =y ⋆ h |S 0:h−1 ,y ⋆ 1:h−1 ] = 1 2 for all1< h < H. The second claim of the lemma then follows from Azuma’s inequality. 34 F.3.3 Inductive Step for Analysis Lemma F.10.FixN >1. Assume thatIH N−1 (δ N−1,1 ,δ N−1,2 )holds. SupposeH(N−1)≥2. For any y ⋆ ∈A H(N) , it holds that μ N (F N (y ⋆ );y ⋆ )≥1− H(N) H(N−1) δ N−1,1 −exp −γ 2 N H(N) 16·H(N−1) Proof.SetH:=H(N)andK:=H(N−1) + 2. Leto∼μ N (·;y ⋆ ). Then for eachi, the law ofo iK+2:(i+1)K−1 is preciselyμ N−1 (·;y ⋆ iK+2:(i+1)K−1 ). Thus, μ N (F ◦ N (y ⋆ );y ⋆ ) ≥1− X i μ N (o iK+2:(i+1)K−1 ̸∈F N−1 (y ⋆ iK+2:(i+1)K−1 )) = 1− H K 1−μ N−1 (F N−1 (y ⋆ iK+2:(i+1)K−1 );y ⋆ iK+2:(i+1)K−1 ) ≥1− H K δ N−1,1 ≥1− H(N) H(N−1) δ N−1,1 . Next, note that the random variables(o iK+1 ) i are independent andP[o iK+1 =y ⋆ iK+1 ] = 1/2 +γ N for eachi. Thus, μ N (F □ N (y ⋆ );y ⋆ )≥1−exp(−γ 2 N (H/K)/8)≥1−exp(−γ 2 N (H(N)/H(N−1))/16 by Hoeffding’s inequality, so long asH(N−1)≥2. The lemma follows from the union bound. Lemma F.11.FixN >1andδ N−1,1 ,δ N−1,2 ,δ N,2 ∈(0,1/2). Assume thatIH N−1 (δ N−1,1 ,δ N−1,2 )holds. Set H:=H(N)andK:=H(N−1) + 2. If γ N >4δ N−1,2 + r 8Klog(2/δ N,2 ) H + 8K H log(4/δ N,2 ), then for anyN-particle particle filtering algorithmAlg, it holds that E y ⋆ ∼Unif(A H(N) ) P o∼Alg [o∈F N (y ⋆ )]≤δ N,2 whereAlgis executed on instancebμ N (·;y ⋆ ). Proof.Consider the random process induced by samplingy ⋆ ∼Unif(A H(N) )and executingAlgonbμ N (·;y ⋆ ). Fixiand condition onS 0:iK . LetE i be the event thaty iK+1 ̸=y ′ iK+1 for somey,y ′ ∈S (i+1)K−1 . For each b∈0,1, define processT (0,b) ,...,T (K−2,b) whereT (0,b) =∅and, for eachh ′ >0,T (h ′ ,b) consists of the first≤N−1elements of y iK+2:h ′ +iK+1 :y 1:h ′ +iK+1 ∈S h ′ +iK+1 ∧y iK+1 =b∧y iK+2:h ′ +iK ∈T (h ′ −1,b) according to some arbitrary ordering ofA h ′ . Observe thatT (0,b) ,...,T (K−2,b) describes the execution of an(N−1)-particle myopic particle filtering algorithm onbμ N−1 (·;y ⋆ iK+2:(i+1)K−1 ). To see why, we check the conditions of Definition F.1. First, it holds almost surely that|T (h ′ ,b) | ≤N−1for allh ′ . Second, by construction, ify 1:h ′ ∈ T (h ′ ,b) theny 1:h ′ −1 ∈ T (h ′ −1,b) . Third, for any0≤h≤K−2, the law ofT (0,b) ,...,T (h ′ ,b) is determined by the law ofS 0:h ′ +iK+1 , which by definition ofAlgis determined by (bμ N h (·;y ⋆ ) :h≤h ′ +iK+ 1), which by definition ofbμ N is determined by(bμ N−1 k (·;y ⋆ iK+2:(i+1)K−1 ) : 0≤k≤h ′ ) (together with randomness independent ofy ⋆ iK+2:(i+1)K−1 ). It follows from the inductive hypothesis that P[∃y∈T (K−2,b) ∩F N−1 (y ⋆ iK+2:(i+1)K−1 )]≤δ N−1,2 . 35 In the eventE i , it holds almost surely that y iK+2:(i+1)K−1 :y 1:(i+1)K−1 ∈S (i+1)K−1 =T (K−2,0) ∪T (K−2,1) . Moreover, the outputo 1:H ofAlgsatisfieso 1:(i+1)K−1 ∈S (i+1)K−1 almost surely, so P[o iK+2:(i+1)K−1 ∈F N−1 (y ⋆ iK+2:(i+1)K−1 )|S 0:iK ] ≤P[∃y 1:(i+1)K−1 ∈S (i+1)K−1 :y iK+2:(i+1)K−1 ∈F N−1 (y ⋆ iK+2:(i+1)K−1 )|S 0:iK ] ≤P[ E i |S 0:iK ] +P[∃y∈T (K−2,0) ∪T (K−2,1) :y iK+2:(i+1)K−1 ∈F N−1 (y ⋆ iK+2:(i+1)K−1 )|S 0:iK ] ≤P[ E i |S 0:iK ] + 2δ N−1,2 . Next, observe that in the eventE i , it holds thato iK+1 =modey iK+1 :y∈ S (i+1)K−1 . Observe that S (i+1)K−1 is independent ofy ⋆ iK+1 , so that P[modey iK+1 :y∈S (i+1)K−1 =y ⋆ iK+1 |S 0:iK ] = 1 2 . Thus, we have P[o iK+1 =y ⋆ iK+1 |S 0:iK ]≤ 1 2 +P[E i |S 0:iK ]. It follows that P[o iK+1 =y ⋆ iK+1 |S 0:iK ] ≤ 1 2 +P[o iK+2:(i+1)K−1 ̸∈F N−1 (y ⋆ iK+2:(i+1)K−1 )|S 0:iK ] + 2δ N−1,2 . Define random variables W i :=I[o iK+1 =y ⋆ iK+1 ]−P[o iK+1 =y ⋆ iK+1 |S 0:iK ]. ThenW 0 ,...,W H/K is a martingale difference sequence under filtration induced by(S 0:iK ) H/K−1 i=0 , so for any δ∈(0,1), P H/K−1 X i=0 W i > p 8(H/K) log(1/δ) ≤δ. Thus, with probability at least1−δ, it holds that K H H/K−1 X i=0 I[o iK+1 =y ⋆ iK+1 ] ≤ 1 2 + 2δ N−1,2 + r 8Klog(1/δ) H + K H H/K−1 X i=0 P[o iK+2:(i+1)K−1 ̸∈F N−1 (y ⋆ iK+2:(i+1)K−1 )|S 0:iK ]. By Freedman’s inequality, it holds with probability at least1−δthat H/K−1 X i=0 P[o iK+2:(i+1)K−1 ̸∈F N−1 (y ⋆ iK+2:(i+1)K−1 )|S 0:iK ] ≤2 H/K−1 X i=0 I[o iK+2:(i+1)K−1 ̸∈F N−1 (y ⋆ iK+2:(i+1)K−1 )] + 8 log(2/δ). 36 We conclude that with probability at least1−2δ, K H H/K−1 X i=0 I[o iK+1 =y ⋆ iK+1 ] ≤ 1 2 + 2δ N−1,2 + r 8Klog(1/δ) H + 8K H log(2/δ) + 2K H H/K−1 X i=0 I[o iK+2:(i+1)K−1 ̸∈F N−1 (y ⋆ iK+2:(i+1)K−1 )]. Condition on this event. If we moreover haveo 1:H ∈F N (y ⋆ ), then we have both K H H/K−1 X i=0 I[o iK+1 =y ⋆ iK+1 ]≥ 1 2 + γ N 2 and K H H/K−1 X i=0 I[o iK+2:(i+1)K−1 ̸∈F N−1 (y ⋆ iK+2:(i+1)K−1 )] = 0. But then γ N 2 ≤2δ N−1,2 + r 8Klog(1/δ) H + 8K H log(2/δ). Setδ:=δ N,2 /2. Then this bound contradicts the lemma assumption, so in facto 1:H ̸∈F N (y ⋆ )almost surely (under the preceding condition). It follows thatP[o 1:H ∈F N (y ⋆ )]≤2δ=δ N,2 as claimed. F.3.4 Completing the Induction Fix someN. DefineH(n) :=N 4n for alln. Defineγ n := 1/Nfor alln. Lemma F.12.It holds that μ N (F N (y ⋆ );y ⋆ )≥1−exp(−Ω(N 2 )) for ally ⋆ , and E y ⋆ ∼Unif(A H(N) ) P o∼Alg [o∈F N (y ⋆ )]≤4 exp(−N). Proof.We have from Lemmas F.9 and F.10 that μ N (F N (y ⋆ );y ⋆ )≥1− N X n=1 H(N) H(n−1) exp(−γ 2 n ·Ω(H(n)/H(n−1)))≥1−N 4N+1 exp(−Ω(N 2 )). Next, observe that if we setδ n,2 := 4exp(−N)then the condition of Lemma F.11 is satisfied for eachn, so long asNexceeds a sufficiently large constant. Thus, applying Lemma F.11 together with induction onN (with Lemma F.9 providing the guarantee forN= 1) proves that E y ⋆ ∼Unif(A H(n) ) P o∼Alg [o∈F n (y ⋆ )]≤4 exp(−N) for eachn≤Nas needed. Proof of Theorem F.5.Immediate from Lemmas F.6 and F.12, together with the fact that theN-particle construction has horizonH=H(N) =N 4N , and henceN≥log(H)/(4 log log(H)). G Additional Experimental Details In this section, we provide further details regarding our experimental setup. 37 G.1 Additional Evaluation Approaches First, we give additional context and motivation for our choice of the evaluation metric of logprob-discrepancy introduced in Section 4.1. One approach to evaluate SMC, which has been used in prior work, is to use the fact that the value c W H computed in Algorithm 1 satisfiesE[ c W H ] =Zand moreover the differencelogZ−E[log c W H ]is an upper bound on the KL divergenceD KL (E[bν H ]∥π ⋆ H )between the output distribution of SMC,E[bν H ], and the target distributionπ ⋆ H (Proposition 5 of Zhao et al. (2024)). 9 However, there are several pitfalls with this approach: first, this is only anupper boundand is not guaranteed to be tight; further, it only applies to SMC and so does not allow us to compare the performance of SMC to other baselines. Finally, even for the relatively simple setting in which we operate, the numberNof particles is too small to get actualdistributionalcloseness betweenE[bν H ]and the targetπ ⋆ H (for instance, the action-level coverage is too large). Thus, we aimed to use a weaker notion of distributional closeness that we can both (a) measure efficiently and (b) hope to have some bearing on the quality of samples produced by SMC. TheP-logprob discrepancy certainly satisfies (a). Moreover, since its error is one-sided in nature (i.e.,LPD P (ν,ν) = 0) and it takes on a positive value in all of our experiments, we believe it is a good candidate in the context of the prompt switching task. G.2 Details for Section 4.2 For the prompt switching task in Section 4.2, the promptsp ref ,p (i) were all generated with GPT-5.2 (in particular, the gpt-5.2_2025-12-11 release). To estimateD KL π ⋆ h ∥bπ (i) h , we write D KL π ⋆ h ∥bπ (i) h =E a 1:h ∼π ⋆ h " log π ⋆ h (a 1:h ) bπ (i) h (a 1:h ) # =E a 1:h ∼π ⋆ h (1−h/H)·α·log π ⋆ (a 1:h ) π (i) (a 1:h ) + log b Z (i) h ,(9) where b Z (i) h :=E π ref [ b V (i) (a 1:h )] =E π ⋆ π (i) h (a 1:h ) π ⋆ h (a 1:h ) ! (1−h/H)·α .(10) We estimate the first term in Eq. (9) via Monte Carlo rollouts fromπ ⋆ h , and estimatelog b Z (i) h via Monte Carlo rollouts fromπ ⋆ , per Eq. (10) (each with 1000 samples). Notice that our estimate of of b Z (i) h is likely very noisy, since there is no logarithm inside the expectation. When we repeated the experiments without adding (our estimate of) the termlog b Z (i) h at all in Eq. (9), we observed similar results. Thus, the noise in our estimate of b Z (i) h seems unlikely to have affected our conclusions. Details for the figures.In Figure 2b, we use the PRM defined in Eq. (2) withα= 2. Moreover, the KL divergences are measured at steph= 32(recall thatH= 64); we observed similar results with other values ofh. The experiments were run on 32GB NVIDIA V100 GPUs. The Pearson correlation coefficient for the points plotted in Figure 2b is 0.81. In Figure 7, we plot additional runs of the same experiment as in Figure 2b, with 3 additional different choices of the dataset (i.e., different choices ofp ref andp (i) ). Finally, in Figure 8, we repeat the same experiment for all 4 datasets but withα= 1. 9 Further, in Lemma C.3 we show that the difference| c W H −Z|upper bounds thetotal variation distanceD TV E[bν H ],π ⋆ H . 38 G.3 Details for Section 4.3 In Figure 6, we repeat the experiment in Figure 2a with 4 additional choices for the dataset (i.e., choices of p ref andp (i) ,i∈[k]). The Pearson correlation coefficientsrare shown in the subcaptions of each subfigure. The experiments were run on 32GB NVIDIA V100 GPUs. G.4 SMC vs. Best-of-Non AIME In our experiments on math problems in Section 4.5, we used Qwen2.5-1B-Instruct as the base modelπ ref and Qwen2.5-Math-PRM-7B as the PRM b V. For both SMC and Best-of-N, we usedN= 32particles/samples. We sampled from the base model with temperature0.8, and used systematic resampling in the implementation of SMC. We generated for a maximum of 3072 tokens for AIME and a maximum of 2048 tokens for Math500. As opposed to implementing SMC withAbeing the space of tokens (as in our experiments on prompt switching), we tookAto be the space ofblocksof some numberBof tokens; doing so significantly improves the efficiency of SMC, as calls to the PRM are the main computational bottleneck. We setB= 64for Math500 andB= 128for AIME. Moreover, we observed that the reward model b V(a 1:h )often gave unreliable answers when passed as input a partial completiona 1:h which was truncated in the middle of a sentence or mathematical expression. Thus, we in fact truncated all blocks at the last instance of a delimiter character (e.g., new line, period). (a) AIME 2024(b) AIME 2025 Figure 5: Performance of SMC vs. Best-of-Non AIME problems (each point is a different problem). Similar to Figure 1, the majority of points lie below the liney=x, indicating that SMC improves performance over Best-of-Non most problems. 39 0.00.20.40.60.81.0 Action-level coverage (KL proxy) 10 20 30 40 50 60 Error of SMC (a)r= 0.83 0.00.20.40.60.81.0 Action-level coverage (KL proxy) 5 10 15 20 25 30 35 40 45 Error of SMC (b)r= 0.89 0.00.20.40.60.81.01.2 Action-level coverage (KL proxy) 10 20 30 40 50 Error of SMC (c)r= 0.88 0.00.20.40.60.81.0 Action-level coverage (KL proxy) 10 15 20 25 30 35 40 45 50 Error of SMC (d)r= 0.86 Figure 6: Additional instantiations of the experiment shown in Figure 2a, with different datasets (generated by GPT-5.2). Captions show Pearson correlation coefficients. 246810121416 Divergence btwn. * & (KL proxy) 20 30 40 50 60 Error of SMC (a)r= 0.70 2.55.07.510.012.515.017.520.0 Divergence btwn. * & (KL proxy) 20 30 40 50 60 70 Error of SMC (b)r= 0.79 246810121416 Divergence btwn. * & (KL proxy) 20 25 30 35 40 45 50 55 Error of SMC (c)r= 0.83 Figure 7: Additional instantiations of the experiment shown in Figure 2b, with different datasets (generated by GPT-5.2). Captions show Pearson correlation coefficients. 40 12345 Divergence btwn. * & (KL proxy) 15 20 25 30 35 Error of SMC (a)r= 0.78 12345 Divergence btwn. * & (KL proxy) 15 20 25 30 35 Error of SMC (b)r= 0.85 01234567 Divergence btwn. * & (KL proxy) 15 20 25 30 35 40 Error of SMC (c)r= 0.83 12345 Divergence btwn. * & (KL proxy) 15 20 25 30 35 40 Error of SMC (d)r= 0.82 Figure 8: Additional instantiations of the experiment shown with the 4 datasets in Figs. 2b and 7, except withα= 1. Captions show Pearson correlation coefficients. 41