Reasoning with Sampling
Free while signed in. Answers cite the passages they came from.
Base language models achieve reasoning performance matching or exceeding RL-posttraining through inference-time power distribution sampling, using MCMC techniques that require no training, datasets, or verifiers. - **Core insight**: RL-posttraining sharpens base model distributions rather than learning fundamentally new behaviors. Power distribution (p^α) sampling explicitly targets this sharpening by exponentiating base model likelihoods, upweighting high-probability sequences while maintaining diversity unlike collapsed RL distributions. - **Power vs low-temperature sampling**: Low-temperature sampling exponentiates conditional next-token distributions (exponent of sums), while power sampling sums exponentiated future path likelihoods (sum of exponents). This crucial difference means power sampling accounts for future completions, upweighting tokens with few but high-likelihood paths over tokens with many low-likelihood completions. - **MCMC implementation**: Autoregressive algorithm progressively samples intermediate distributions using Metropolis-Hastings with random resampling. Uniformly selects index, resamples from that point using proposal LLM, accepts/rejects based on relative power distribution likelihoods. Block size B=192, α=4.0, inference cost ~8.84x standard sampling. - **Empirical results**: On Qwen2.5-Math-7B, achieves 74.8% on MATH500 (vs 78.5% GRPO), but outperforms on out-of-domain tasks - 57.3% HumanEval (vs 53.7% GRPO), 2.88 AlpacaEval score (vs 2.38 GRPO). Maintains generation diversity with superior pass@k performance at k>1, avoiding RL's mode collapse. - **Training-free advantage**: No hyperparameter sweeps, curated datasets, or reward verifiers required. Broadly applicable beyond verifiable domains. Samples from highest base model likelihood/confidence regions (similar to GRPO) while maintaining 679-token average response length, suggesting latent reasoning capabilities exist in base models.
Core insight: RL-posttraining sharpens base model distributions rather than learning fundamentally new behaviors. Power distribution (p^α) sampling explicitly targets this sharpening by exponentiating base model likelihoods, upweighting high-probability sequences while maintaining diversity, unlike collapsed RL distributions.
Power vs low-temperature sampling: Low-temperature sampling exponentiates conditional next-token distributions (exponent of sums), while power sampling sums exponentiated future path likelihoods (sum of exponents). This crucial difference means power sampling accounts for future completions, upweighting tokens with few but high-likelihood paths over tokens with many low-likelihood completions.
MCMC implementation: Autoregressive algorithm progressively samples intermediate distributions using Metropolis-Hastings with random resampling. Uniformly selects an index, resamples from that point using the proposal LLM, and accepts/rejects based on the relative power distribution likelihoods. Block size B=192, α=4.0, inference cost ~8.84x standard sampling.
Empirical results: On Qwen2.5-Math-7B, achieves 74.8% on MATH500 (vs 78.5% GRPO), but outperforms on out-of-domain tasks - 57.3% HumanEval (vs 53.7% GRPO), 2.88 AlpacaEval score (vs 2.38 GRPO). Maintains generation diversity with superior pass@k performance at k>1, avoiding RL’s mode collapse.
Training-free advantage: No hyperparameter sweeps, curated datasets, or reward verifiers required. Broadly applicable beyond verifiable domains. Samples from the highest base model likelihood/confidence regions (similar to GRPO) while maintaining 679-token average response length, suggesting latent reasoning capabilities exist in base models.
Abstract
Frontier reasoning models have exhibited incredible capabilities across a wide array of disciplines, driven by posttraining large language models (LLMs) with reinforcement learning (RL). However, despite the widespread success of this paradigm, much of the literature has been devoted to disentangling truly novel behaviors that emerge during RL but are not present in the base models. In our work, we approach this question from a different angle, instead asking whether comparable reasoning capabilites can be elicited from base models at inference time by pure sampling, without any additional training. Inspired by Markov chain Monte Carlo (MCMC) techniques for sampling from sharpened distributions, we propose a simple iterative sampling algorithm leveraging the base models' own likelihoods. Over different base models, we show that our algorithm offers substantial boosts in reasoning that nearly match and even outperform those from RL on a wide variety of single-shot tasks, including MATH500, HumanEval, and GPQA. Moreover, our sampler avoids the collapse in diversity over multiple samples that is characteristic of RL-posttraining. Crucially, our method does not require training, curated datasets, or a verifier, suggesting broad applicability beyond easily verifiable domains.
Get next week’s papers.
The same picks and the same summaries, in your inbox. Free, and 176 issues deep.
Subscribe on Substack