Reasoning with Sampling

Analysis

Why This Paper Matters

This paper tackles a central question in the era of large language models: is reinforcement learning (RL) post-training truly necessary for eliciting advanced reasoning, or can comparable capabilities be unlocked purely at inference time? The authors propose a surprisingly simple iterative sampling algorithm that sharpens the base model's own likelihood distribution, inspired by Markov chain Monte Carlo (MCMC) techniques. Their results show that this method can match or even outperform RL-based post-training on several single-shot reasoning benchmarks, including MATH500, HumanEval, and GPQA. This is significant because RL post-training requires curated datasets, verifiers, and substantial compute, limiting its applicability to domains where such resources are available. The paper's finding that inference-time sampling can achieve similar gains without any training suggests a paradigm shift: reasoning improvements may be more about how we query the model than how we train it.

Moreover, the paper highlights a critical drawback of RL post-training: it tends to collapse the diversity of outputs, producing fewer unique solutions across multiple samples. The proposed sampler avoids this collapse, preserving a richer set of reasoning paths. This has practical implications for tasks where multiple valid answers or exploratory reasoning are valuable, such as creative problem-solving or scientific discovery.

Technical Contributions

• Iterative Sampling Algorithm: The core innovation is a simple iterative procedure that repeatedly samples from the base model's likelihood, applying a sharpening transformation (inspired by MCMC) to concentrate probability mass on high-quality reasoning paths. No gradient updates, verifiers, or external data are used.
• Inference-Time Only: Unlike RL-based methods that modify model weights, this algorithm operates entirely at inference time, making it lightweight and easy to integrate into existing pipelines.
• Diversity Preservation: The method explicitly avoids the diversity collapse seen in RL post-training, as measured by the number of unique correct solutions across multiple samples. This is a key differentiator from prior work.
• Broad Applicability: Because it requires no verifier or curated dataset, the method can be applied to domains where defining a reward function is difficult, such as open-ended reasoning or creative tasks.

Results

• On MATH500, the sampling algorithm achieves accuracy comparable to RL-post-trained models, with some configurations slightly outperforming them.
• On HumanEval (code generation), the method matches RL-based performance, demonstrating its effectiveness across modalities.
• On GPQA (graduate-level Q&A), the sampler again shows competitive results, nearly matching RL post-training.
• Crucially, across all benchmarks, the sampler maintains higher diversity: the number of distinct correct solutions per sample is significantly larger than for RL-post-trained models, which tend to converge to a narrow set of outputs.
• The paper reports that the algorithm's performance scales with the number of sampling iterations, suggesting that more compute at inference time can substitute for training compute.

Significance

This paper has the potential to reshape how practitioners approach reasoning in LLMs. By demonstrating that inference-time sampling can rival RL post-training, it reduces the barrier to improving model reasoning: no need for expensive RL pipelines, verifiers, or curated data. This is especially impactful for small teams or domains where such resources are unavailable. The diversity preservation is also a practical advantage, enabling exploration of multiple solution strategies. However, the method's reliance on the base model's own likelihoods means it inherits any biases or weaknesses of the base model, and its effectiveness on very long or multi-step reasoning tasks remains to be tested. Overall, this work opens a new direction for reasoning enhancement that is simpler, more general, and more accessible than current RL-based approaches.