Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo
Jelena Markovic-Voronov, Wenhui Zhu, Bo Long, Suyash Gupta, Kayhan Behdin, Deepak Agarwal · 2026
Read Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo by Jelena Markovic-Voronov, Wenhui Zhu, Bo Long, Suyash Gupta, Kayhan Behdin, Deepak Agarwal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16453.txt.
Introduction
Markovic-Voronov and colleagues offer a training-free way to steer language models toward higher-quality full answers rather than likely next tokens. Their method defines a reward-weighted target over complete sequences and samples from it with sequential Monte Carlo, using a fast prefix-only variant and a lookahead variant that matches exact sequence marginals. Resampling with rejuvenation steps and block-wise generation fold in common sampling tricks. On code generation, gains reached about 55 percent over the base model, and the method also beat a leading reinforcement-learning approach.
Catalog record
| CREATOR | Jelena Markovic-Voronov, Wenhui Zhu, Bo Long, Suyash Gupta, Kayhan Behdin, Deepak Agarwal |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49499 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16453
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo Thanks: Corresponding author: [email protected], [email protected] Jelena Markovic-Voronov, Wenhui Zhu, Bo Long, Suyash Gupta, Kayhan Behdin, Deepak Agarwal Abstract We introduce a principled probabilistic framework for reward-guided decoding in large language models, addressing the limitations of standard decoding methods that optimize token-level likelihood rather than sequence-level quality. Our method defines a reward-augmented target distribution over complete sequences by combining model transition probabilities with prefix-dependent reward potentials. Importantly, the approach is training-free: it leaves model weights unchanged and instead modifies the inference distribution via reward potentials, with all gains arising purely from inference-time sampling. To sample from this distribution, we develop Sequential Monte Carlo algorithms, including a computationally efficient prefix-only variant and a lookahead variant whose intermediate targets match the exact marginals of the full sequence distribution. The framework also integrates resample–move updates with Metropolis–Hastings rejuvenation and supports block-wise generation, subsuming common decoding strategies such as temperature sampling and power-tempered objectives. Empirical results across three 7B models show significant gains. On code generation (HumanEval), our method improves base performance by up to 54.9% and surpasses the strongest sampling baselines by 9.1% – 15.3% . On mathematical reasoning (MATH500), it achieves gains of up to 8.8% . Notably, it reaches 87.8% on HumanEval and 78.4% on MATH500 with Qwen2.5-7B , consistently outperforming the reinforcement learning method GRPO. 1 Introduction Large language models (LLMs) are typically used through autoregressive decoding, where tokens are generated sequentially according to the model’s next-token distribution ( 31 ; 26 ) . Common decoding strategies such as beam search ( 32 ) , nucleus sampling ( 13 ) , and temperature sampling ( 33 ) are designed primarily to control diversity and fluency of generated text. However, these approaches optimize token-level likelihood rather than the quality of the full generated sequence. In many important applications, the quality of a response depends on properties of the entire sequence rather than individual tokens. This is particularly evident in reasoning, code generation, and mathematical problem solving, where correctness or logical consistency can only be evaluated at the sequence level. Several recent works therefore introduce additional scoring mechanisms, such as verifiers for complete responses ( 6 ) , process reward models ( 19 ; 30 ; 35 ) , or human feedback signals ( 24 ; 2 ) . These signals provide reward potentials that score partial or complete outputs and guide generation toward desirable solutions. Despite their widespread use, reward signals are typically incorporated only heuristically. Methods such as best-of- N sampling ( 3 ; 14 ; 5 ) and re-ranking with process reward models ( 28 ; 29 ) do not integrate rewards into the sampling distribution itself. As a result, generation is still largely driven by the base model likelihood, with rewards only applied after candidate generation. This can be suboptimal, particularly when reward signals are strong or misaligned with likelihood, and it prevents these methods from defining a coherent probabilistic target over full sequences. In this paper, we introduce a unified framework for sampling from reward-modified sequence distributions using Sequential Monte Carlo (SMC). We consider targets of the form \Pi(x_{1:T}\mid q)\propto\prod_{t=1}^{T}m_{t}(x_{t}\mid q,x_{<t})\prod_{t=1}^{T}\psi_{t}(x_{1:t},q), (1) where x_{1:T} is the generated sequence and q is the prompt. Here, m_{t} is a transition factor derived from the base language model, and \psi_{t} is a reward potential over prefixes. This defines a Feynman–Kac model, with the language model inducing the Markov process and the rewards acting as multiplicative potentials ( 22 ; 7 ) . A similar form of a reward-modified base distribution appears in Direct Preference Optimization ( 27 ) , where rewards are incorporated at the whole sequence level. Importantly, our method is training-free : it leaves the base model weights unchanged and instead modifies the inference distribution through reward potentials. All improvements arise purely from inference-time sampling, without any additional training or fine-tuning. Our framework unifies several decoding objectives, including (i) tempered next-token targets (temperature-based decoding) and (ii) power-tempered sequence targets , corresponding to posterior sampling under a power prior ( 15 ; 23 ) , which arise from different choices of m_{t} . Within this framework, we derive two types of intermediate sampling targets. The first is a prefix-only target based on prefix factors of the model; it is computationally efficient but does not, in general, match the true marginals of the full sequence-level target. The second is a lookahead target, which incorporates a correction for future tokens and yields intermediate distributions that exactly coincide with the marginals of the full target. The framework also supports extensions such as block-wise generation of multiple tokens and Metropolis–Hastings (MH) rejuvenation within SMC, enabling efficient sampling while preserving the desired target distribution. Contributions. The main contributions of this work are: • Reward-aware probabilistic decoding. We introduce a probabilistic framework that directly incorporates reward potentials into the target distribution for LLM sequence generation. • Unified formulation of decoding objectives. We show that temperature-based decoding and power-tempered sequence sampling emerge as special cases of a unified reward-modified target. • SMC algorithms for reward-guided generation. We develop Sequential Monte Carlo algorithms for sampling from these targets, including both prefix-only intermediate targets and lookahead targets that match the true marginals of the full sequence distribution. • Empirical validation. We demonstrate significantly improved performance across multiple LLMs (Qwen2.5-7B, Qwen2.5-Math-7B, DeepSeek-Math-7B) and benchmarks (MATH500, HumanEval, GPQA), outperforming best-of- N , prior SMC-based approaches, and the reinforcement learning method GRPO. 2 Related Work Sequential Monte Carlo methods approximate sequences of distributions using weighted particle systems and were originally developed as particle filters ( 12 ; 8 ) . They are naturally formulated in the Feynman–Kac framework, where a sequence of path-space distributions is defined by a Markov process and multiplicative potential functions ( 22 ; 7 ) . The general SMC sampler of 7 extends these ideas to broader targets, with theoretical guarantees ( 4 ) and practical design principles such as resampling and proposal adaptation ( 9 ) , making SMC a flexible tool for high-dimensional sequential inference. Recent work has applied Monte Carlo methods to control language model generation. In particular, SMC-based approaches have been used to steer generation under structural or semantic constraints ( 18 ; 21 ) , where 18 samples from intermediate targets akin to our prefix-only formulation, and 21 incorporates a limited one-step lookahead. Additionally, adaptive weighted rejection sampling has been proposed for efficient controlled generation under local constraints ( 20 ) . Most closely related, 36 use twisted SMC with learned twist functions, requiring additional neural networks to approximate target marginals, and focus on tasks such as toxic generation control, sentiment-conditioned review generation, and infilling. In contrast, our method is training-free : our lookahead term corresponds to the optimal twist, which we estimate online and integrate with block-wise resample–move SMC and MH rejuvenation. 25 focus on grammar-aligned decoding and introduce an expected future grammaticality term, analogous to our lookahead, estimated via adaptive sampling. Additionally, a line of research focuses on sampling from power-tempered variants of the base model distribution. Sampling from the power distribution p(x_{1:T}\mid q)^{\alpha} without reward potentials has been explored using both Metropolis–Hastings and SMC methods. 17 introduce an MH algorithm for this setting, while 1 develop a faster SMC