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
Scaling inference compute, by generating many parallel attempts per problem, is a costly but reliable lever for improving language model capabilities. By default these attempts are generated independently, wasting inference compute on redundant solutions. This waste seems unavoidable. After all, independence is what makes parallel sampling trivial to scale. However, this tradeoff is not fundamental: there is a rich design space of samplers that generate correlated but exact samples entirely in parallel. We explore this design space as an avenue for improving sample efficiency in scaling inference compute and reinforcement learning (RL). Concretely, we introduce QuasiMoTTo, which uses correlated samples as a drop-in replacement for i.i.d. samples. To generate these samples, QuasiMoTTo uses a reparameterization of autoregressive sampling as inverse-CDF sampling and draws the underlying uniforms with quasi-Monte Carlo (QMC); because QMC spreads the uniforms out more evenly than i.i.d., the resulting samples cover the output space with far less redundancy. Even though the batch is correlated, each sample is marginally distributed according to the language model, so we can use the batch for policy-gradient training. Our empirical analysis focuses on understanding how efficiently QuasiMoTTo can turn compute into performance. To evaluate correlated samplers, whose dependence breaks standard pass@k estimators, we first develop an unbiased bootstrap estimator. Across four reasoning benchmarks, QuasiMoTTo matches i.i.d. pass@k accuracy with 25-47% fewer samples. Strikingly, QuasiMoTTo often saturates an upper bound on pass@k that holds for any marginal-preserving sampler. We also apply QuasiMoTTo to policy-gradient RL (GRPO) where it matches i.i.d. performance with 50% fewer training steps. These gains come from higher coverage, which yields a stronger learning signal per batch.