Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo

Jelena Markovic-Voronov; Wenhui Zhu; Bo Long; Zhipeng Wang; Suyash Gupta; Kayhan Behdin; Bee-Chung Chen; Deepak Agarwal

cs.LGApr 7, 2026

Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo

Authors: Jelena Markovic-Voronov, Wenhui Zhu, Bo Long, Zhipeng Wang, Suyash Gupta, Kayhan Behdin, Bee-Chung Chen, Deepak Agarwal

Organizations: LinkedIn

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.

Figures & tables

\min\left\{1,\;\frac{\widehat{L}_{k}\left(x^{\prime}_{1:kB},q;\Pi_{\mathrm{II}}\right)}{\widehat{L}_{k}(x_{1:kB}^{(i)},q;\Pi_{\mathrm{II}})}\prod_{t=(k-1)B+1}^{kB}\frac{p(x_{t}^{\prime}\mid q,x^{\prime}_{<t})^{\alpha}\,}{p(x_{t}^{(i)}\mid q,x_{<t}^{(i)})^{\alpha}\,}\cdot\frac{\psi_{t}\left(x^{\prime}_{1:t},q\right)}{\psi_{t}(x_{1:t}^{(i)},q)}\cdot\frac{\tilde{p}^{(\alpha)}(x_{t}^{(i)}\mid q,x_{<t}^{(i)})}{\tilde{p}^{(\alpha)}\left(x_{t}^{\prime}\mid q,x^{\prime}_{<t}\right)}\right\}

Algorithm 1 General reward-guided block-wise resample–move SMC with selective MH rejuvenation

Figure 1: Pass@1 vs. total tokens per problem on a subset of 82 HumanEval tasks (Qwen2.5-7B). Best-of-N and SMC (reward) saturate early. Our method scales monotonically with compute.

Qwen2.5-7B
	MATH500	HumanEval	GPQA
Base	0.498	0.329	0.278
Low-temperature	0.628	0.524	0.303
Best-of-N	0.650	0.609	0.282
SMC (reward) ( Lew et al., 2023 )	0.710	0.787	0.323
MCMC Power Sampling ( Karan and Du, 2025 )	0.706	0.622	0.318

Table 1: Main results (pass@1) on MATH500, HumanEval, and GPQA (diamond split). Baseline numbers follow prior work Ji et al. (2026) ; we add our method as an extra row.

Explore similar work

Mar 19, 2026

Adaptive Decoding via Test-Time Policy Learning for Self-Improving Generation

Decoding strategies largely determine the quality of Large Language Model (LLM) outputs, yet widely used heuristics such as greedy or fixed temperature/top-p decoding are static and often task-agnostic, leading to suboptimal or inconsistent generation quality across domains that demand stylistic or structural flexibility. We introduce a reinforcement learning-based decoder sampler that treats decoding as sequential decision-making and learns a lightweight policy to adjust sampling parameters at test-time while keeping LLM weights frozen. We evaluated summarization datasets including BookSum, arXiv, and WikiHow using Granite-3.3-2B and Qwen-2.5-0.5B. Our policy sampler consistently outperforms greedy and static baselines, achieving relative gains of up to +88% (BookSum, Granite) and +79% (WikiHow, Qwen). Reward ablations show that overlap-only objectives underperform compared to composite rewards, while structured shaping terms (length, coverage, repetition, completeness) enable stable and sustained improvements. These findings highlight reinforcement learning as a practical mechanism for test-time adaptation in decoding, enabling domain-aware and user-controllable generation without retraining large models.

Asmita Bhardwaj, Yuya Jeremy Ong, Eelaaf Zahid +1

UC San Diego San Diego, CA · Plastic Labs San Jose, CA · IBM Research Cambridge, MA +1

Language Model Decoding Test-Time Adaptation RL for Language Models

Ask PDF

Mar 10, 2026

Learning Adaptive LLM Decoding

Decoding from large language models (LLMs) typically relies on fixed sampling hyperparameters (e.g., temperature, top-p), despite substantial variation in task difficulty and uncertainty across prompts and individual decoding steps. We propose to learn adaptive decoding policies that dynamically select sampling strategies at inference time, conditioned on available compute resources. Rather than fine-tuning the language model itself, we introduce lightweight decoding adapters trained with reinforcement learning and verifiable terminal rewards (e.g. correctness on math and coding tasks). At the sequence level, we frame decoding as a contextual bandit problem: a policy selects a decoding strategy (e.g. greedy, top-k, min-p) for each prompt, conditioned on the prompt embedding and a parallel sampling budget. At the token level, we model decoding as a partially observable Markov decision process (POMDP), where a policy selects sampling actions at each token step based on internal model features and the remaining token budget. Experiments on the MATH and CodeContests benchmarks show that the learned adapters improve the accuracy-budget tradeoff: on MATH, the token-level adapter improves Pass@1 accuracy by up to 10.2% over the best static baseline under a fixed token budget, while the sequence-level adapter yields 2-3% gains under fixed parallel sampling. Ablation analyses support the contribution of both sequence- and token-level adaptation.

Chloe H. Su, Zhe Ye, Samuel Tenka +3

Department of Computer Science, Harvard University, Boston, USA · Kempner Institute, Harvard University, Cambridge, MA, USA · UC Berkeley, CA, USA +1

Language Model Decoding RL for Language Models

Ask PDF

Jan 29, 2026

Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening

Reinforcement learning (RL) post-training is a dominant approach for improving the reasoning performance of large language models (LLMs), yet growing evidence suggests that its gains arise primarily from distribution sharpening rather than the acquisition of new capabilities. Recent work has shown that sampling from the power distribution of LLMs using Markov chain Monte Carlo (MCMC) can recover performance comparable to RL post-training without relying on external rewards; however, the high computational cost of MCMC makes such approaches impractical for widespread adoption. In this work, we propose a theoretically grounded alternative that eliminates the need for iterative MCMC. We derive a token-level decomposition of the autoregressive power distribution, showing that the global power distribution can be approximated by a token-level scaled low-temperature one, where the scaling factor captures future trajectory quality. Leveraging this insight, we introduce a training-free and verifier-free algorithm that sharpens the base model's generative distribution autoregressively. Empirically, we evaluate our method on math, QA, and code tasks, and show that our method matches or surpasses one-shot GRPO without relying on any external rewards, while reducing inference latency by over

10\times

compared to MCMC-based sampling.

Xiaotong Ji, Rasul Tutunov, Matthieu Zimmer +1

Huawei Noah’s Ark Lab · UCL Centre for Artificial Intelligence

Efficient Language Model Inference RL for Language Model Reasoning

Ask PDF