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.
Speculative decoding (SD) accelerates language model inference by drafting tokens from a cheap proposal model and verifying them against an expensive target model via rejection sampling. Because rejection truncates the draft block at the first error, throughput degrades when draft and target diverge. Rather than rejecting draft tokens outright, we propose to reweight them. To this end, we introduce sequential Monte Carlo speculative decoding (SMC-SD), which replaces token-level rejection with importance-weighted resampling over a population of draft particles. SMC-SD is a principled approximate inference scheme that trades exactness for additional speed, while preserving theoretical bounds on its per-step approximation error. Because LLM inference is memory bandwidth-bound, the arithmetic needed to draft particles and to score them in parallel comes nearly for free -- SMC-SD uses idle compute to turn verification into a vectorized, fixed-size operation with no rollback. Empirically, SMC-SD achieves 2.36x speed-up over speculative decoding and a 5.2x speed-up over autoregressive decoding, while remaining within 3% of the target model's accuracy on reasoning, instruction-following, and coding benchmarks.
Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang +4
Inference-time sampling can elicit strong reasoning abilities from language models without additional training. Existing power-sampling methods do so by sharpening the distribution over full generated outputs, favoring completions that are individually likely under the model. We argue that this is the wrong object to target for reasoning: a completion entangles a reasoning trace with a final answer, whereas what matters is whether an answer is supported by many plausible reasoning paths. We therefore shift the target from the full-output distribution to the sharpened answer marginal, making self-consistency an inference-time objective rather than a post-hoc voting criterion. Surprisingly, this marginal target admits an efficient approximation: we propose a simple, purely autoregressive parallel sampling algorithm that approximately samples from the sharpened answer marginal, eliciting stronger performance than standard power sampling on mathematics and coding benchmarks while being orders of magnitude faster.
Aleksei Arzhantsev, Otmane Sakhi, Nicolas Chopin
Criteo AI Lab, CREST IP Paris · Criteo AI Lab · ENSAE, Institut Polytechnique de Paris
We study how to improve LLM reasoning at inference time without updating model weights or using external reward models. Recent reward-free power-sampling methods define the sequence-level power target πα(y∣x)∝p0(y∣x)α, where α>1, which increases the relative probability of completions that are already likely under the base model. Existing methods use Metropolis--Hastings or Sequential Monte Carlo (SMC) to approximately sample from this target. However, two challenges arise at different levels. At the target level, full-sequence sharpening can concentrate probability on a few exact reasoning--answer trajectories, suppressing alternative paths that support the same answer. At the sampler level, finite-particle SMC can suffer from path collapse when resampling repeatedly duplicates a few high-weight prefixes. To address these challenges, we propose Decoupled Marginal Sharpening (DMS), which separately controls how strongly the model favors particular reasoning paths and how strongly it favors final answers after aggregating support across those paths. At the target level, DMS first samples from a sharpened reasoning distribution, then marginalizes the model's answer probabilities over the resulting weighted reasoning population and sharpens the induced answer marginal. Separate exponents allow mild reasoning sharpening to encourage exploration of diverse paths, followed by stronger answer-marginal sharpening to concentrate probability on answers with greater aggregate support across those paths. At the sampler level, we develop Fully Adapted Annealed SMC, which combines an annealed sequence of power targets with locally fully adapted proposals and predictive ancestor resampling. Experiments on MATH500, GPQA-Diamond, HumanEval, and AIME24/25 across three base models show that DMS achieves the highest mean pass@1 among the compared methods in all tasks.