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.
Figures & tables
Figure 1: Performance of SMC (with N particles) vs. Best-of- N on Math500 problems; here we take N=32 . Each point is a different problem; thus, SMC with N particles improves performance over Best-of- N on most problems. See Section 4.5 for details.
Figure 2: Empirical validation for our theory on the prompt-switching task (see Section 4 ). (a) We vary the action-level coverage (as measured by a KL-divergence proxy) across many prompts while keeping 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 that DKL(πh⋆∥πh) predicts the sampling error of SMC.
Figure 3: Performance of SMC on the prompt-switching task ( Section 4.4 ). Each point represents SMC with some number of particles N∈{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.
Figure 4: Influence of PRM error (measured by Dχ2(πh⋆∥πh) ) on SMC accuracy for 10 Math500 problems. Different colors correspond to different values of the inverse temperature parameter λ parametrizing V(λ) . The plots show SMC accuracy with respect to a random particle (not the best one) selected at the end of SMC.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Performance of SMC vs. Best-of- N on AIME problems (each point is a different problem). Similar to Fig. 1 , the majority of points lie below the line y=x , indicating that SMC improves performance over Best-of- N on most problems.
Figure 6: Additional instantiations of the experiment shown in Fig. 2(a) , with different datasets (generated by GPT-5.2). Captions show Pearson correlation coefficients.
Figure 7: Additional instantiations of the experiment shown in Fig. 2(b) , with different datasets (generated by GPT-5.2). Captions show Pearson correlation coefficients.
Figure 8: Additional instantiations of the experiment shown with the 4 datasets in Figs. 2(b) and 7 , except with α=1 . Captions show Pearson correlation coefficients.