Reasoning with Sampling: Cutting at Decision Points

Sampling Instead of Post-Training

Frontier reasoning models are typically obtained by post-training base models with reinforcement learning. A growing body of evidence suggests that much of what RL adds is sharpening: the base model already assigns non-negligible probability to good reasoning traces, and post-training simply concentrates more mass on them. If that view is right, then sampling directly from the sharpened distribution should elicit reasoning at test time, with no additional training, datasets, or verifiers.

This is exactly what power sampling does. Given a base model p over complete traces, the power distribution

upweights traces that are already likely under p, with α > 1 controlling the sharpening. Power sampling is therefore training-free, dataset-free, and verifier-free, using only the base model's own probabilities.

The Sampling Bottleneck

For power sampling to be useful in practice, we need an efficient way to sample from Π_T. This turns out to be the main obstacle. The difficulty is that Π_T is defined over complete traces, not next-token choices. Exact sampling would require normalizing over an exponentially large sequence space. And simply lowering the per-token temperature does not recover Π_T either: sharpening at the trace level is not the same as sharpening token by token.

Karan and Du address this with a stagewise Metropolis-Hastings (MH) sampler. MH is an MCMC method that proposes candidate edits and accepts or rejects them under a rule that guarantees convergence to the target distribution. In the stagewise version, each step picks a cut position in the current trace, keeps the prefix, resamples the suffix from a proposal model, and applies the MH correction. This works, but its efficiency depends entirely on where the cut goes. With cuts placed uniformly over tokens, almost every proposal lands inside a stretch of routine continuation (mid-equation, mid-step, mid-implementation), and ends up rewriting local details rather than reopening the decisions that actually shaped the trace.

Decision Points in Reasoning Traces

To cut at decisions instead of cutting uniformly, we first need a way to identify where those decisions occur in a reasoning trace. Although a chain-of-thought may contain many tokens, only a small number of positions usually determine the subsequent reasoning path. For example, in a proof, the choice to proceed by induction rather than contradiction can determine the structure of nearly everything that follows. After that choice has been made, many later tokens are spent executing the chosen strategy. A sampler that treats every token as equally worth revising will therefore spend most of its proposals rewriting execution details rather than reopening the underlying decision.

Our key observation is that positive jumps in next-token entropy are a useful proxy for decision points. A jump in entropy means that the base model has suddenly become less certain about the next token, which often happens when several qualitatively different continuations are available. Once one continuation has been chosen, the entropy can drop again as the trace moves into the execution of that choice. We test this proxy directly by taking a chain-of-thought and resampling the suffix from two kinds of cut positions: positions in the top decile of entropy jumps and positions in the bottom decile. Cuts at high-jump positions produce 1.33× the normalized edit distance and 1.36× the fraction of distinct final answers. This indicates that entropy spikes mark positions where changing the suffix is more likely to change the downstream reasoning path.

However, a divergent suffix may differ only in wording or formatting. To look at the cut locations themselves, we run a blind audit. An LLM classifier (GPT-5.6 Sol) sees the current trace around each cut, but not the sampling method, the entropy values, the proposed continuation, or the outcome. It labels a cut a decision point if, at that position, the solution could take a different high-level strategy or make a different substantive intermediate choice, such as an equation, a subgoal, or a state update.

Entropy-Cut MH cuts at decision points more than three times as often as uniform-cut MH: 19.6% vs. 5.6% for Qwen2.5-Math-7B on MATH500, and 29.0% vs. 9.3% for Qwen3-8B-Base on HumanEval. The differences are 14.0 and 19.7 percentage points, respectively, with 95% confidence intervals of [10.8, 17.3] and [14.7, 24.5] from a bootstrap over problems. Two caveats apply. The labels come from a single LLM classifier, and most cuts of either method are still not labeled decision points. So entropy jumps make a cut at a decision point more likely, but they do not isolate decision points.

Our Algorithm: Cutting at Decision Points

The suffix-resampling experiment suggests that entropy jumps identify positions where the future reasoning path is especially sensitive to the cut. Entropy-Cut MH turns this observation into a proposal mechanism. It keeps the stagewise MH framework unchanged, but replaces the uniform cut distribution with a state-dependent distribution that gives more probability to large positive entropy jumps. At each step, given the current trace, we compute the next-token entropy profile, compute the values of positive entropy jumps Δ_t = max{0, h_t - h_t-1}, and sample a cut position with probability proportional to Δ_t^β. The exponent β ≥ 0 interpolates between uniform cuts (β = 0) and increasingly decision-aware cuts; we use β = 4 throughout.

Why the jump rather than the entropy itself? Because entropy often stays elevated for several tokens after a decision while its consequences are being worked out. The most informative place to cut is where uncertainty first rises.

The target distribution stays the same. Entropy-Cut MH changes only how the sampler proposes a cut. The Metropolis-Hastings acceptance rule accounts for this by including the ratio of the cut probabilities under the proposed and current traces, so Π_T remains the stationary distribution.

we have x = 0 and y = 3.
Step 1: Calculate r
r = sqrt(x^3 + y^3)
  = sqrt(0^3 + 3^3 [CUT])

} = sqrt(27)

we have x = 0 and y = 3.
[CUT] Step 1: Calculate r
r = sqrt(x^3 + y^3)

Step 1: Calculate r
r = sqrt(x^2 + y^2)
  = sqrt(0^2 + 3^2) = 3

Mixing-Time Analysis

Empirical gains are one thing; we would also like to understand mathematically why entropy-cutting helps. To make this precise, we analyze a stylized model of reasoning: a depth-T token-labeled tree whose root-to-leaf paths are reasoning traces. Branch nodes correspond to decision points (positions with multiple plausible continuations), and chain nodes correspond to deterministic execution.

We analyze this tree under approximate symmetry, which means two things: entropy jumps are concentrated at branch nodes, and both Π_T and the proposal distribution are close to uniform over root-to-leaf paths.

In this setting, our main theorem gives a clean separation. Let k be the number of branch nodes on a root-to-leaf path (the semantic depth) and b₁ the depth of the first branch:

This separation is most meaningful when the first consequential decision appears early in the trace and only a small number of later positions are true decisions. In that regime, where b₁ = O(1) and k = o(T), Entropy-Cut MH mixes in o(T) steps, while Uniform-Cut MH still needs Ω(T) steps. The theorem says that entropy-cutting can make the sampler depend on the number of semantic decisions rather than the total number of tokens.

Empirical Results

We evaluate on MATH500, HumanEval, GPQA Diamond, and AIME26 with five base and instruction-tuned models from the Qwen and Phi families, comparing against standard sampling, low-temperature sampling, SMC, TMC, and uniform-cut MH. Entropy-Cut MH is competitive with and often improves over prior sampling methods across the four benchmarks. For instance, with Qwen2.5-7B, MATH500 accuracy rises from 35.9 under standard sampling to 71.9, and HumanEval accuracy rises from 33.0 to 68.9. Scores are averaged over eight runs (64 runs for AIME26).

To check which gains are statistically significant, we compare paired runs on MATH500, HumanEval, and AIME26 with Qwen2.5-Math-7B and Qwen3-8B-Base. We use a clustered McNemar test, which accounts for the dependence between runs on the same question, and we do not correct for multiple comparisons. At the 0.05 level, the improvements over standard and low-temperature sampling are significant on MATH500 and HumanEval for both models. Against uniform-cut MH, the improvements are significant for Qwen2.5-Math-7B on MATH500 and for Qwen3-8B-Base on HumanEval, but not in the other four comparisons. Scores in these paired runs can differ from the main benchmark results.

Comparison with Best-of-N

Entropy-Cut MH uses more computation than drawing a single standard sample. To account for this, we compare it with best-of-N under the same budget of sampled tokens, which serves as a proxy for compute and includes the tokens from rejected MH proposals. For each question, we draw standard or low-temperature samples until their total token count reaches this budget, keeping the sample that crosses it. We then return the response with the highest average log-likelihood under the base model, so the selection needs no verifier.

On MATH500 and HumanEval, Entropy-Cut MH significantly improves over standard best-of-N for both Qwen2.5-Math-7B and Qwen3-8B-Base. On AIME26, the differences are not significant. Entropy-Cut MH also significantly improves over low-temperature best-of-N in five of the six settings. The exception is Qwen2.5-Math-7B on HumanEval, where low-temperature best-of-N scores higher (61.0% vs. 58.9%), though the difference is not significant. These comparisons use a separate set of runs. Together, they show that the gains often persist when independent sampling receives a comparable token budget.

Likelihood and Diversity

Beyond accuracy, we measure two properties of the sampler. First, samples from Entropy-Cut MH sit in higher-likelihood regions of the base model than samples from standard, low-temperature, or uniform-cut sampling. This is consistent with the sharpening objective of power sampling. Second, despite improving single-sample accuracy, the method does not collapse pass@k (the chance of getting a correct answer in k tries). On Qwen2.5-Math-7B with MATH500, this suggests that the gain in single-sample accuracy does not come at the cost of multi-sample performance.

Citation

@inproceedings{zhou2026reasoning,
  title   = {Reasoning with Sampling: Cutting at Decision Points},
  author  = {Zhou, Felix and Mehrotra, Anay and Liu, Quanquan C.},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year    = {2026}
}

For questions, contact Felix Zhou or Anay Mehrotra.