Reasoning with Sampling: Your Base Model is Smarter Than You Think β part 2/3
Cleaned-text code points [15823, 31789). Bibliography omitted here; source.md includes it.
We can observe this phenomenon with a simple example. Let us consider the token vocabulary π³ = { a , b } \mathcal{X}=\{a,b\} and restrict our attention to two-token sequences ( x 0 , x 1 ) (x_{0},x_{1}) : a β a , a β b , b β a , b β b aa,ab,ba,bb . Let p β‘ ( a β a ) = 0.00 , p β‘ ( a β b ) = 0.40 , p β‘ ( b β a ) = 0.25 , p β‘ ( b β b ) = 0.25 , p(aa)=0.00,\qquad p(ab)=0.40,\qquad p(ba)=0.25,\qquad p(bb)=0.25, so that p β‘ ( x 0 = a ) = 0.40 , p β‘ ( x 0 = b ) = 0.50 . p(x_{0}=a)=0.40,\qquad p(x_{0}=b)=0.50.\qquad Let Ξ± = 2.0 \alpha=2.0 . Under p Ξ± p^{\alpha} , we have p pow β ( x 0 = a ) β 0.00 2 + 0.40 2 = 0.160 , p pow β ( x 0 = b ) β 0.25 2 + 0.25 2 = 0.125 , p_{\text{pow}}(x_{0}=a)\propto 0.00^{2}+0.40^{2}=0.160,\qquad p_{\text{pow}}(x_{0}=b)\propto 0.25^{2}+0.25^{2}=0.125, so p Ξ± p^{\alpha} prefers sampling a a over b b . Under low-temperature sampling, p temp β ( x 0 = a ) β ( 0.00 + 0.40 ) 2 = 0.160 , p temp β ( x 0 = b ) β ( 0.25 + 0.25 ) 2 = 0.250 , p_{\text{temp}}(x_{0}=a)\propto(0.00+0.40)^{2}=0.160,\qquad p_{\text{temp}}(x_{0}=b)\propto(0.25+0.25)^{2}=0.250, preferring sampling b b over a a . If p Ξ± p^{\alpha} samples x 0 = a x_{0}=a , there is only one future path with likelihood 0.40 0.40 . If p temp p_{\text{temp}} samples x 0 = b x_{0}=b , there are two future paths b β a , b β b ba,bb , but either choice has likelihood 0.25 0.25 .
In other words, even though a a has lower conditional likelihood under both p p and p temp p_{\text{temp}} , p Ξ± p^{\alpha} upweights a a and samples the highest likelihood two-token sequence. b b has many future paths contributing to a higher likelihood under p p and p temp p_{\text{temp}} , but leads to low likelihood sequences. We provide a stronger formalization of this phenomenon in Appendix A.1 .
Thus, sampling from p Ξ± p^{\alpha} encourages sampling tokens which have fewer but higher likelihood βfuture pathsβ, as opposed to tokens with several lower likelihood completions. This type of behavior is immensely valuable for reasoning tasks. For example, choosing βwrongβ tokens that have high average likelihoods but trap outputs in low likelihood individual futures are examples of critical windows or pivotal tokens ( Li et al., 2025 ; Abdin et al., 2024 ) , a phenomenon where a few tokens are highly influential in the correctness of language model outputs. In fact, sharp critical windows have been shown to correlate strongly with reasoning failures ( Li et al., 2025 ) . Instead, embedded in sampling from the power distribution is an implicit bias towards planning for future high likelihood tokens.
### 4.2 The Metropolis-Hastings Algorithm
Now that we have seen how sampling from p Ξ± p^{\alpha} can in theory assist the underlying LLMβs ability to reason, our aim now turns towards proposing an algorithm to accurately sample from it. Given an LLM p p , we have access to the values p Ξ± p^{\alpha} over any sequence length; however, these values are unnormalized . Direct sampling from the true probabilities requires normalizing over all sequences ( x 0 , β¦ , x T ) β π³ T (x_{0},\dots,x_{T})\in\mathcal{X}^{T} , which is computationally intractable.
To get around this, we invoke a Markov Chain Monte Carlo (MCMC) algorithm known as Metropolis-Hastings (MH) ( Metropolis et al., 1953 ) , which targets exactly what we want: approximate sampling from an unnormalized probability distribution. The MH algorithm constructs a Markov chain of sample sequences ( π± 0 , π± 1 , β¦ , π± n ) (\mathbf{x}^{0},\mathbf{x}^{1},\dots,\mathbf{x}^{n}) using an arbitrary proposal distribution q β‘ ( π± | π± i ) q(\mathbf{x}|\mathbf{x}^{i}) to select the next candidate π± i + 1 \mathbf{x}^{i+1} . With probability A β‘ ( π± , π± i ) = min β { 1 , p Ξ± β ( π± ) β
q β‘ ( π± i | π± ) p Ξ± β ( π± i ) β
q β‘ ( π± | π± i ) } , A(\mathbf{x},\mathbf{x}^{i})=\text{min}\left\{1,\frac{p^{\alpha}(\mathbf{x})\cdot q(\mathbf{x}^{i}|\mathbf{x})}{p^{\alpha}(\mathbf{x}^{i})\cdot q(\mathbf{x}|\mathbf{x}^{i})}\right\}, (9)
candidate π± \mathbf{x} is accepted as π± i + 1 \mathbf{x}^{i+1} ; otherwise, MH sets π± i + 1 = π± i \mathbf{x}^{i+1}=\mathbf{x}^{i} . This algorithm is especially convenient as it only requires the relative weights given by p Ξ± p^{\alpha} (as the normalization weights in A A cancel) and works with any generic but tractable sampler q q with minimal restrictions. Remarkably, for large enough n n , this process converges to sampling from the target distribution p Ξ± p^{\alpha} under the following (quite minimal) conditions on the proposal distribution ( Neal, 1993 ) :
###### Definition 1 .
The proposal distribution q q is irreducible if for any set X X with nonzero mass under the target distribution p Ξ± p^{\alpha} , q q has nonzero probability of eventually sampling from X X . The proposal is aperiodic if the induced chain of samples does not return to the same sample after a fixed interval number of steps.
Thus, we must simply ensure that our proposal distribution satisfies irreducibility and aperiodicity, and Metropolis-Hastings takes care of the rest. On a practical level, we would also like both q β‘ ( π± | π± i ) q(\mathbf{x}|\mathbf{x}^{i}) and its reverse q β‘ ( π± i | π± ) q(\mathbf{x}^{i}|\mathbf{x}) to be easily computable.
Consider the following family of random resampling proposal distributions (see Figure 3 ). Let p prop p_{\text{prop}} be a proposal LLM. With uniform probability 1 T \frac{1}{T} , select a random t β [ 1 , T ] t\in[1,T] and resample the sequence starting at index t t using p prop p_{\text{prop}} . Then the transition likelihood q β‘ ( π± | π± i ) q(\mathbf{x}|\mathbf{x}^{i}) is simply the likelihood of the resampling. Note that at each candidate selection step, we have a nonzero probability of transitioning between any two sequences π± , π± β² β π³ \mathbf{x},\mathbf{x^{\prime}}\in\mathcal{X} , since with some probability we can always resample as early as the beginning of π± \mathbf{x} . This ensures our proposal distribution is both irreducible and aperiodic. Moreover, q β‘ ( π± i | π± ) q(\mathbf{x}^{i}|\mathbf{x}) is easy to calculate by symmetry, since we can treat π± i \mathbf{x}^{i} as a resampled version of π± \mathbf{x} .
With the flexibility endowed by Metropolis-Hastings, we can choose the proposal LLM p prop p_{\text{prop}} to be any LLM with any sampling strategy (e.g., low-temperature sampling).
### 4.3 Power Sampling with Autoregressive MCMC
A direct implementation of Metropolis-Hastings for LLMs would involve initializing with a sampled token sequence of length T T , subsequently generating new candidates of length T T with ( 9 ) over many, many iterations. This process is computationally expensive, however, due to the repeated, full sequence inference calls to the LLM.
In fact, the main downside to MCMC algorithms in practice is the potential for an exponential mixing time ( Gheissari et al., 2017 ) , where a poor choice of initialization or proposal distribution can result in an exponentially large number of samples required before convergence to the target distribution. This problem is exacerbated if the sample space has high dimensionality ( Bandeira et al., 2022 ; Schmidler and Woodard, 2013 ) , which is precisely exhibited by the sequence space of tokens π³ T \mathcal{X}^{T} , especially for long sequences/large values of T T .
To remedy this, we propose an algorithm that leverages the sequential structure of autoregressive sampling. We define a series of intermediate distributions which we progressively sample from, until converging to the target distribution p Ξ± p^{\alpha} . In particular, samples from one intermediate distribution initiate a Metropolis-Hastings process for the next, helping avoid pathological initializations.
Fix block size B B and proposal LLM p prop p_{\text{prop}} , and consider the sequence of (unnormalized) distributions β
βΆ p β ( x 0 , β¦ , x B ) Ξ± βΆ p β ( x 0 , β¦ , x 2 β B ) Ξ± βΆ β¦ βΆ p β ( x 0 , β¦ , x T ) Ξ± , \emptyset\longrightarrow p(x_{0},\dots,x_{B})^{\alpha}\longrightarrow p(x_{0},\dots,x_{2B})^{\alpha}\longrightarrow\dots\longrightarrow p(x_{0},\dots,x_{T})^{\alpha}, (10) where p β‘ ( x 0 , β¦ , x k β B ) p(x_{0},\dots,x_{kB}) denotes the joint distribution over token sequences of length k β B kB , for any k k . For convenience, let Ο k \pi_{k} denote the distribution given by Ο k ( x 0 : k β B ) β p ( x 0 : k β B ) Ξ± . \pi_{k}(x_{0:kB})\propto p(x_{0:kB})^{\alpha}. (11) Suppose we have a sample from Ο k \pi_{k} . To obtain a sample from Ο k + 1 \pi_{k+1} , we initialize a Metropolis-Hastings process by sampling the next B B tokens x k β B + 1 : ( k + 1 ) β B x_{kB+1:(k+1)B} with p prop p_{\text{prop}} . We subsequently run the MCMC sampling procedure for N MCMC N_{\text{MCMC}} steps, using the random resampling proposal distribution q q from the previous section. The full details are presented in Algorithm 1 .
Note that Algorithm 1 is single-shot : even though multiple inference calls are made, the decision to accept vs. reject new tokens is made purely by base model likelihoods to simulate sampling a single sequence from p Ξ± p^{\alpha} . We can interpret this as a new axis for inference-time scaling , as we expend additional compute during sampling to obtain a higher quality/likelihood sample.
To quantify the scaling, we can estimate the average number of tokens generated by Algorithm 1 . Note that each candidate generation step when sampling from Ο k ( x 0 : k β B \pi_{k}(x_{0:kB} resamples an average of k β B 2 \frac{kB}{2} tokens, N MCMC N_{\text{MCMC}} times. Summing over all k k , the expected number of tokens generated is πΌ tokens = N MCMC β β k = 1 β T / B β k β B 2 β N MCMC β T 2 4 β B . \mathbb{E}_{\text{tokens}}=N_{\text{MCMC}}\sum_{k=1}^{\lceil T/B\rceil}\frac{kB}{2}\approx\frac{N_{\text{MCMC}}T^{2}}{4B}. (12) The key tradeoff here is between the block size B B and number of MCMC steps N MCMC N_{\text{MCMC}} . A larger B B requires larger βjumpsβ between intermediate distributions, requiring a larger N MCMC N_{\text{MCMC}} to adequately transition. In Section 5 , we empirically find a value for B B that makes Algorithm 1 performant for relatively small values of N MCMC N_{\text{MCMC}} .
## 5 Experiments
### 5.1 Experimental Setup
#### Evaluation.
We use a standard suite of reasoning benchmarks ranging across mathematics, coding, and STEM (MATH500, HumanEval, GPQA), along with a non-verifiable benchmark (AlpacaEval 2.0) evaluating general helpfulness. We evaluate all of our methods and baselines single-shot ; i.e., on one final response string.
β’ MATH500 : The MATH dataset ( Lightman et al., 2024 ) consists of competition math problems spanning seven categories including geometry, number theory, and precalculus. There are 12500 problems total, with 7500 training problems and 5000 test problems. MATH500 is a specific randomly chosen subset of the test set standardized by OpenAI.
β’ HumanEval : HumanEval is a set of 164 handwritten programming problems covering algorihtms, reasoning, mathematics, and language comprehension ( Chen et al., 2021 ) . Each problem has an average of 7.7 associated unit tests, where solving the problem corresponds to passing all unit tests.
β’ GPQA : GPQA ( Rein et al., 2024 ) is a dataset of multiple-choice science questions (physics, chemistry, and biology) which require advanced reasoning skills to solve. We use subset GPQA Diamond for evaluation, which consists of 198 questions which represent the highest quality subset of the GPQA dataset.
β’ AlpacaEval 2.0 : The AlpacaEval dataset is a collection of 805 prompts ( Dubois et al., 2024 ) that gauge general helpfulness with questions asking e.g., for movie reviews, recommendations, and reading emails. The model responses are graded by an automated LLM judge (GPT-4-turbo), which determines a preference for the model responses over those from a baseline (also GPT-4-turbo). The resulting score is a win rate of model responses normalized for the length of the model response.
#### Models.
To demonstrate the efficacy of our sampling algorithm, we use the base models Qwen2.5-Math-7B, Qwen2.5-7B, and Phi-3.5-mini-instruct. For our RL baselines, we use the implementation of GRPO in Shao et al. (2025) , which posttrains these models on the MATH training split. For both the Qwen2.5 models, we use the default hyperparameters used to benchmark their performance in Shao et al. (2025) . For the Phi-3.5 model, we use a set of hyperparameters selected from Abdin et al. (2024) that avoids training instabilities and converges to improvement over the base model over a large number of epochs.
#### Sampling Algorithm.
For our implementation of power sampling (Algorithm 1 ), we set the maximum T T to be T max = 3072 T_{\text{max}}=3072 (termination can happen earlier with an EOS token) and block size B = 3072 / 16 = 192 B=3072/16=192 . Empirically, we find Ξ± = 4.0 \alpha=4.0 coupled with a proposal LLM p prop p_{\text{prop}} chosen as the base model with sampling temperature 1 / Ξ± 1/\alpha to be most performant for reasoning tasks. For AlpacaEval 2.0, we find that having a proposal distribution of higher temperature ( Ο = 0.5 \tau=0.5 ) improves performance.
### 5.2 Results
#### Main results.
We display our main results in Table 1 . Across base models of different families, our sampling algorithm achieves massive, near-universal boosts in single-shot accuracies and scores over different reasoning and evaluation tasks that reach, e.g., up to +51.9% on HumanEval with Phi-3.5-mini and +25.2% on MATH500 with Qwen2.5-Math. In particular, on MATH500, which is in-domain for RL-posttraining, power sampling achieves accuracies that are on par with those obtained by GRPO. Furthermore, on out-of-domain reasoning, our algorithm again matches GRPO on GPQA and actually outperforms on HumanEval by up to +59.8% . Similarly, power sampling consistently outperforms on the non-verifiable AlpacaEval 2.0, suggesting a generalizability of our boosts to domains beyond verifiability.
The surprising success of this fundamentally simple yet training-free sampling algorithm underscores the latent reasoning capabilities of existing base models.
### 5.3 Analysis
We analyze how the reasoning characteristics of power sampling relate to those of GRPO. We present an example in Table 2 , with further examples in Appendix A.3 .
#### Reasoning trace likelihoods and confidences.
By design, power sampling targets sampling higher likelihood sequences from the base model. In Figure 4 , the left graph plots a histogram of the output sequence log-likelihoods (averaged by length) of the base model, power sampling, and GRPO responses on MATH500, where likelihoods are taken relative to the Qwen2.5-Math-7B base model. Our method samples from higher likelihood regions of the base model, as intended, but still maintains noticeable spread. Meanwhile, GRPO samples are heavily concentrated at the highest likelihood peak.
We also plot the base model confidence of MATH500 responses, defined to be the average negative entropy ( uncertainty ) of the next-token distributions ( Prabhudesai et al., 2025 ) : Conf ( x 0 : T ) = 1 T + 1 β t = 0 T β x β π³ p ( x | x < t ) log p ( x | x < t ) . \text{Conf}(x_{0:T})=\frac{1}{T+1}\sum_{t=0}^{T}\sum_{x\in\mathcal{X}}p(x|x_{<t})\log{p(x|x_{<t}}). (13) The right plot of Figure 4 demonstrates that our methodβs and GRPO responses sample from similarly high confidence regions from the base model, which again correspond to regions of higher likelihood and correct reasoning.
#### Reasoning trace lengths.
Another defining characteristic of RL-posttraining is long-form reasoning ( Guo et al., 2025 ) , where samples tend to exhibit longer responses. On MATH500, Qwen2.5-Math-7B averages a response length of 600 tokens, while GRPO averages 671 tokens. Surprisingly, power sampling achieves a similar average length of 679 tokens, without explicitly being encouraged to favor longer generations. This emerges naturally from the sampling procedure.