acceptodds
Under review as a conference paper at ICLR 2027

The Surprising Effectiveness of Reasoning with Unsurprising Sampling

Abstract

Training language models to reason via reinforcement learning has led to dramatic improvements in their mathematical and coding abilities. Reasoning training leads to models that expend more inference time compute on their chain-of-thought in order to more effectively solve complex problems. Recently it has been shown that it is possible to obtain similar performance to RL training via sampling techniques which only make use of probabilities from the base LLM. In particular, forms of Markov chain Monte Carlo (MCMC) that converge to the annealed LLM distribution yield similar or better performance than RL training at the cost of scaling up inference time compute. In this paper we investigate the power of sampling for reasoning tasks, and discover that MCMC is not necessary to outperform RL. In fact, we show that best-of-N sampling, where the best sequence is determined by the minimum surprisal rate, matches the performance of MCMC sampling methods while being more token efficient and much simpler to implement. Our results demonstrate that the base LLM's level of surprise in its own generated sequences is a strong signal of correctness, allowing for more accurate sampling without any training, external correctness signals, or non-trivial modifications of standard LLM sampling pipelines.

Primary area:
foundation or frontier models, including LLMs
Keywords:
reasoning, best-of-N sampling, minimum surprisal rate

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_FcjHOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper evaluates a simple inference-time procedure, where they generate N candidate responses and select the one with the lowest average negative log-probability under the model. This minimum surprisal rate criterion is equivalent to selecting the candidate with minimum perplexity. Experiments use Qwen2.5-Math-7B, Qwen2.5-7B, and Phi-3.5-mini-instruct on MATH500 and HumanEval, comparing against low-temperature sampling, Power Sampling MCMC, and GRPO models trained on MATH. The empirical observation is potentially useful, but novelty, theoretical applicability, and efficiency claims are insufficiently established.

Critical strengths

S1: The method is simple, parallelizable, and requires neither training nor an external verifier.

S2: Results across three models and two benchmarks establish a useful baseline against more complex sampling methods.

S3: Prefix-based scoring suggests a potentially useful direction for adaptive stopping.

Critical weaknesses

W1: Minimum surprisal is equivalent to minimum perplexity, already evaluated as a Best-of-N selector in prior self-certainty work. Closely related baselines are missing.

W2: The lower bound permits probability queries, while the algorithm also requires samples. Its hard instance also has probability exactly beta, violating the stated strict >beta condition.

W3: Accuracy does not consistently exceed MCMC, and coding comparisons use GRPO trained on math.

W4: Temperature-dependent scoring and generation details are unclear, and prefix length is selected using evaluation results.

Questions for authors

Q1: How does the method compare with existing perplexity selection, self-certainty, and self-consistency using identical candidates?

Q2: Can the theorem be corrected under a common sampling-and-probability access model relevant to autoregressive inference?

Q3: Can you report matched-token and matched-time comparisons with uncertainty, clarify scoring probabilities, and validate prefix selection on separate data?

2 comments

We are truly glad to see that you found our method simple, parallelizable, and requiring neither training nor an external verifier while results across three models and two benchmarks establish a useful baseline against more complex sampling methods.

  1. "How does the method compare with existing perplexity selection, self-certainty, and self-consistency using identical candidates?"

The goal of our paper is to show that a very simple baseline, min-surprisal sampling, matches or outperforms much more complex MCMC methods [1] at a matched sampling budget, while also being much lower latency (MCMC require N sequential samples while min-surprisal can do N in parallel). We also provide a theoretical justification, that the number of samples required by min-surprisal is close to optimal in the worst-case for any such sampling method.

Min-surprisal sampling can be applied to literally any question asked to an LLM, all that is necessary is to keep track of cumulative log-probs. In contrast, methods like self-consistency are only applicable to questions where there is a unique correct solution e.g. math problems with a numerical answer. Thus, these methods cannot even be applied to coding problems, where multiple syntactically different coding solutions can all implement the same logical function.

[1] Karan, A. and Du, Y. Reasoning with sampling: Your base model is smarter than you think. ICLR 2026. Oral Presentation.

  1. "Can the theorem be corrected under a common sampling-and-probability access model relevant to autoregressive inference?"

There is no need to correct the theorem, because if you have access to computing probabilities then you immediately have access to sampling! In fact, this is precisely how autoregressive LLMs work: to sample the next token we use the model to compute the probability of each possible next token, and then we sample from that discrete distribution.

  1. "Its hard instance also has probability exactly beta, violating the stated strict >beta condition."

This is a typo. The condition in the definition should be ≥β\geq \beta rather than >β> \beta.

  1. “Can you report matched-token and matched-time comparisons with uncertainty, clarify scoring probabilities, and validate prefix selection on separate data?”

The results are already matched-token budgets: we use N=10 samples for min-surprisal and compare this to N=10 MCMC iterations for Power Sampling. The scoring probabilities are from the original LLM distribution.

For the prefix selection validation question, we took a random split of the MATH500 dataset into a train set and a test set of 250 problems each. The peak threshold for the train set was a t=1250 token prefix, with an accuracy of 78.8%. Using this same threshold t=1250 on the held-out test set gave accuracy 78.0%, which was also the peak accuracy for that set. Thus, the prefix threshold selection method generalizes to held-out problems.

Reviewer_FcjHOpenReview ↗

Thank you for the detailed rebuttal

Through their rebuttal, the authors have addressed most of my initial concerns, so I increased my score.

Reviewer_GqWsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates whether strong reasoning performance can be elicited from pretrained language models through simple inference-time sampling, without reinforcement learning or external reward signals. Motivated by recent findings that Power Sampling MCMC can achieve competitive reasoning performance by sharpening the base model's distribution, the authors propose a substantially simpler alternative: generating multiple candidate solutions independently and selecting the one with the minimum surprisal rate, defined as the average negative log-likelihood per token.

The main contributions are threefold. First, the paper demonstrates that minimum surprisal rate sampling can achieve performance comparable to Power Sampling MCMC and, in some settings, GRPO, while requiring fewer generated tokens and avoiding sequential MCMC operations. Second, it presents a no-free-lunch theorem showing that, for certain unstructured distributions, probability-query algorithms cannot substantially outperform independent sampling in identifying a high-probability mode. Third, the authors investigate surprisal rates along generated sequences and observe that selecting candidates based on intermediate prefixes can sometimes yield higher accuracy than using complete sequences.

Experiments are conducted on three language models, Qwen2.5-Math-7B, Qwen2.5-7B, and Phi-3.5-mini-instruct, using MATH500 and HumanEval. The results suggest that a simple likelihood-based selection mechanism can recover a substantial portion of the performance associated with more computationally involved inference-time reasoning methods.

Critical strengths
  1. A simple and practically useful alternative to computationally complex sampling methods.

The most compelling aspect of this paper is its demonstration that minimum surprisal rate sampling can provide competitive reasoning performance without MCMC, reinforcement learning, or external verification signals. Unlike Power Sampling MCMC, the proposed approach is straightforward to implement and naturally supports parallel generation through standard LLM inference pipelines.

This simplicity is consequential because it substantially reduces implementation complexity and potentially improves practical inference efficiency. The experimental results, particularly on Qwen2.5-Math-7B and Qwen2.5-7B, provide meaningful evidence that sophisticated sampling procedures are not always necessary to obtain strong reasoning performance.

  1. Interesting empirical evidence about the relationship between surprisal and reasoning correctness.

Beyond introducing a simple selection rule, the paper investigates how surprisal evolves throughout generated reasoning trajectories. The finding that intermediate-prefix surprisal can sometimes predict correctness more effectively than full-sequence surprisal is particularly interesting.

This observation suggests that sequence likelihood contains useful but temporally varying information about reasoning quality. It also motivates potentially more efficient inference procedures based on early candidate selection or pruning. These findings provide useful empirical insights beyond the immediate performance comparison.

Critical weaknesses
  1. The theoretical guarantees are only weakly connected to the proposed algorithm and the actual reasoning objective.

The theoretical analysis considers finding a high-probability mode in a distribution over fixed-length sequences, whereas the proposed practical method selects variable-length solutions according to their length-normalized negative log-likelihood. These objectives are fundamentally different: minimizing surprisal rate is not generally equivalent to identifying the highest-probability sequence.

More importantly, the no-free-lunch theorem establishes a worst-case limitation for identifying high-probability modes, rather than a guarantee about reasoning correctness. It does not establish that high-probability solutions are correct, nor does it demonstrate that minimum surprisal rate sampling is near-optimal for selecting correct reasoning trajectories.

There is also an apparent technical inconsistency in Theorem 4.1: the constructed distribution assigns probability exactly β\beta to its distinguished mode, while the defined distribution class and success criterion require probability strictly greater than β\beta. Although this may be fixable, it further weakens the precision of the current theoretical presentation.

Consequently, the theoretical contribution does not convincingly explain the empirical success of the proposed algorithm, which limits the strength of the paper's central justification.

  1. The experimental evaluation is insufficient to establish robustness, generality, and computational efficiency.

The experiments cover only three relatively small language models and two benchmarks, MATH500 and HumanEval. Given the paper's broad claims about inference-time reasoning, this evaluation is limited, particularly because the proposed method relies on an empirical correlation between sequence likelihood and correctness that may depend strongly on model architecture, training distribution, task difficulty, and sampling temperature.

The comparisons also require greater care. In Table 1, minimum surprisal sampling does not consistently outperform Power Sampling MCMC. For example, it underperforms on Qwen2.5-7B/MATH500 (0.698 vs. 0.706), Phi-3.5/MATH500 (0.496 vs. 0.508), and Phi-3.5/HumanEval (0.713 vs. 0.732). These differences may be small, but without uncertainty estimates or repeated experiments, it is difficult to determine whether the methods are statistically distinguishable.

Furthermore, the paper emphasizes token efficiency but does not provide a sufficiently detailed comparison of total generated tokens, wall-clock latency, and computational cost under matched inference budgets. A controlled comparison against low-temperature sampling across different temperatures, as well as other simple selection or aggregation baselines, would help isolate the benefit of surprisal-based ranking itself.

These limitations matter because the paper's main contribution is empirical. Stronger evidence is needed to establish that the observed advantages are robust rather than specific to the selected models, benchmarks, and inference configurations.

Questions for authors
  1. Theoretical formulation and applicability (clarification).

Theorem 4.1 studies mode identification under a probability-query oracle and a fixed-length sequence distribution. However, the proposed algorithm uses length-normalized surprisal over variable-length sequences, and its actual goal is to identify correct reasoning solutions.

Could the authors clarify how the theorem formally supports the proposed minimum surprisal rate algorithm? In particular, under what assumptions does selecting a high-probability mode, or a sequence with low surprisal rate, imply a higher probability of correctness?

Additionally, in Equation (6), pz(z)=βp_z(z)=\beta, whereas P(β)\mathcal{P}(\beta) requires p(x∗)>βp(x^*)>\beta. How should this apparent inconsistency be resolved?

  1. Sampling temperature and robustness (assessment-relevant experiment).

The experimental implementation generates candidate solutions using temperature 0.25, although Algorithm 1 describes sampling from p(x)p(x).

Are the surprisal rates computed using the original model probabilities or the temperature-adjusted sampling distribution? How sensitive are the results to the sampling temperature?

A comparison across several temperatures, including standard temperature-1 sampling, would help establish whether the reported improvements originate primarily from low-temperature generation or from the minimum-surprisal selection rule.

  1. Computational efficiency and statistical reliability (assessment-relevant experiment).

Could the authors report the average generated tokens, total inference FLOPs or GPU time, and wall-clock latency for minimum surprisal sampling and Power Sampling MCMC under comparable accuracy or computational budgets?

Additionally, could the authors provide confidence intervals or statistical significance tests for the results in Table 1? Several reported improvements or degradations are relatively small, making it difficult to assess whether the proposed method consistently matches or outperforms the MCMC baseline.

1 comment

We are glad to see that you found that our approach substantially reduces complexity, is simple, practically useful, straightforward to implement and naturally supports parallel generation through standard LLM inference pipelines, while our experimental results provide meaningful evidence and improve practical inference efficiency.

  1. (a) “Could the authors clarify how the theorem formally supports the proposed minimum surprisal rate algorithm? In particular, under what assumptions does selecting a high-probability mode, or a sequence with low surprisal rate, imply a higher probability of correctness?”

As discussed on lines 331-341, the no-free lunch result from Theorem 4.1 gives a lower bound on the number of samples required in the worst case to identify a mode. Proposition 4.1 shows that minimum surprisal sampling uses a number of samples that matches this lower bound up to first order terms. Thus, for worst-case distributions, minimum surprisal is optimal for identifying a mode.

The connection between identifying a mode and correctness is the premise of all the existing unsupervised sampling methods including Power Sampling MCMC, minimum surprisal sampling, low temperature sampling, greedy decoding etc. The motivation is that we should attempt to sample a high-probability sequence (i.e. a mode of the LLM distribution), because such sequences are most likely to be correct. All these different algorithms provide different ways of attempting to accomplish this same goal, and we prove that min-surprisal sampling is the most sample efficient way to accomplish this goal.

  1. (b) “Additionally, in Equation (6), (p_z(z)=\beta), whereas (\mathcal{P}(\beta))$ requires (p(x^)>\beta). How should this apparent inconsistency be resolved?”*

This is a typo. P(β)\mathcal{P}(\beta) should be defined to be distributions with p(x∗)≥βp(x^*)\geq \beta, rather than p(x∗)>βp(x^*) > \beta.

  1. ”Are the surprisal rates computed using the original model probabilities or the temperature-adjusted sampling distribution? How sensitive are the results to the sampling temperature?”

The surprisal rates are computed using the original model probabilities, while the sequences are sampled with temperature 0.25. The choice of the sampling temperature 0.25 was made to match the sampling temperature used in the original Power Sampling MCMC paper. This value of the temperature was tuned in that original paper to maximize the performance of Power Sampling MCMC, and so it is likely that we could get even better performance for min-surprisal sampling with additional tuning.

However, the goal of our paper is not to optimize the hyperparameters of a particular sampling method, but instead to show that a simple Best-of-N approach can match and sometimes outperform the much more complex Power Sampling MCMC algorithm. Hence, we kept the same temperature, as well as other sampling hyperparameters exactly the same as the original Power Sampling MCMC.

  1. (a) ”Could the authors report the average generated tokens, total inference FLOPs or GPU time, and wall-clock latency for minimum surprisal sampling and Power Sampling MCMC under comparable accuracy or computational budgets?”

The average generated tokens are already matched for min-suprisal in our experiments in the paper: we chose N=10 as the number of samples for min-surprisal, because the original Power Sampling MCMC paper uses N=10 MCMC steps per iteration.

Min-surprisal sampling is also clearly much lower latency than Power Sampling MCMC, because all the N samples in min-surprisal can be done in parallel. In contrast, the MCMC sampling requires multiple iterations, each of which require N=10 samples running in series, because the seed for the k-th sample is the entire (k-1)-th sample. This is the essential feature of all Markov Chain Monte Carlo methods. Thus min-surprisal sampling is on the order of N times lower-latency than Power Sampling MCMC.

  1. (b) "Additionally, could the authors provide confidence intervals or statistical significance tests for the results in Table 1?"

We provide boot-strap standard errors for min-surprisal sampling below. These indeed demonstrate that this simple Best-of-N surprisal approach either matches or at times exceeds the much more complex Power Sampling MCMC.

MATH500Qwen2.5-Math-7BQwen2.5-7BPhi3.5-mini-inst.
Power Sampling0.7480.7480.7060.7060.5080.508
Min Surprisal0.772±0.0180.772 \pm 0.0180.698±0.0200.698 \pm 0.0200.496±0.0220.496 \pm 0.022
HumanEvalQwen2.5-Math-7BQwen2.5-7BPhi3.5-mini-inst.
Power Sampling0.5730.5730.6220.622$0.732 $
Min Surprisal0.579±0.0350.579 \pm 0.0350.634±0.0350.634 \pm 0.0350.713±0.0350.713 \pm 0.035
Reviewer_qYqeOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors present a simple inference-time approach to sampling higher quality traces by using a best-of-N with surprisal (avg. per token likelihood). With a small N, this simple approach is competitive with GRPO and power sampling.

Critical strengths
  • Simple and effective inference time approach that achieves strong results.
Critical weaknesses
  • An analysis of pass@k performance of the surprisal sampling approach would be helpful in understanding how the distributional reach of generations compares to power sampling.
Questions for authors
  • What does it mean to stop sampling early using surprisal? Even if the surprisal is indicative early, doesn't the entire rollout need to be sampled still for correctness? If you mean reducing the size of candidates, maybe an adaptive filtering based on separation in surprisal in early tokens can differentiate between early vs. late separation in surprisal?

  • Could the authors provide pass@k comparisons between surprisal sampling and power sampling?

  • Is there a benefit obtained by using the surprisal to select between proposal candidate sequences during Metropolis-Hastings as an intermediate "process-reward"? I.e. for the next block sampled, instead of doing MCMC steps, sample N continuations of the block and choose the one with the least surprisal?

2 comments

We are truly glad to hear that you found our approach effective and simple that achieves strong results where our paper is sound, clear and easy to follow. We are sincerely glad to see your assessment of our paper from presentation to quality and soundness highly.

  1. ”What does it mean to stop sampling early using surprisal? Even if the surprisal is indicative early, doesn't the entire rollout need to be sampled still for correctness? If you mean reducing the size of candidates, maybe an adaptive filtering based on separation in surprisal in early tokens can differentiate between early vs. late separation in surprisal?”

By stopping early, we meant stopping sampling for all but the min-surprisal candidate after some threshold number of tokens. This would save on the total number of tokens required to identify and sample the final selected candidate. As you suggest, more sophisticated filtering schemes could potentially save more tokens, and further improve the efficiency.

  1. ”Is there a benefit obtained by using the surprisal to select between proposal candidate sequences during Metropolis-Hastings as an intermediate "process-reward"? I.e. for the next block sampled, instead of doing MCMC steps, sample N continuations of the block and choose the one with the least surprisal?”

This is definitely an interesting direction for future work, and our results on min-surprisal of prefixes indeed suggest that it could be helpful. Ultimately, as you also point out there could be many other potential ways to further leverage surprisal to guide sampling. One of the main points of our paper is that the simplest possible setup of Best-of-N with surprisal matches or exceeds the performance of much more complex MCMC methods.

Thanks for responding to my questions! I maintain my original positive assessment of the work!

Comments on the paper

1 comment

Dear Reviewers and Area Chair,

We sincerely thank you for dedicating your time to review our paper. We are truly glad that

Reviewer qYqe found our approach effective and simple, achieving strong results, and found our paper sound, clear and easy to follow. We are sincerely glad to see Reviewer qYqe’s high assessment of our paper across presentation, quality and soundness.

Reviewer GqWs found that our approach substantially reduces complexity, is simple, practically useful, straightforward to implement and naturally supports parallel generation through standard LLM inference pipelines, while our experimental results provide meaningful evidence and improve practical inference efficiency.

Reviewer FcjH found our method simple, parallelizable, and requiring neither training nor an external verifier, while results across models and benchmarks establish a useful baseline against more complex sampling methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.