Reasoning with Sampling: Cutting at Decision Points
2026-05-28 • Machine Learning
Machine LearningArtificial IntelligenceComputation and Language
AI summaryⓘ
The authors study how to make language models reason better by sampling their outputs in a smarter way without extra training. They explain that picking points to rethink during reasoning traces randomly can miss important decisions. To fix this, they use changes in the model's uncertainty (entropy) to find key decision points and focus on re-evaluating those parts. They show this approach helps the model explore better reasoning paths and performs well on several math and coding tasks compared to other methods.
language modelsreinforcement learningpower distributionreasoning tracesentropyMetropolis-Hastingssamplingmixing timedecision pointsMATH500
Authors
Felix Zhou, Anay Mehrotra, Quanquan C. Liu
Abstract
Frontier reasoning models are produced by posttraining base language models with reinforcement learning. Recent work has challenged this by showing that sampling from a sharpened version of the base model's distribution, a so-called power distribution, elicits comparable reasoning without additional training, curated datasets, or verifiers. However, making this method practical requires efficiently sampling from the power distribution. A sampler needs to "mix" to the power distribution, which necessitates moving between modes of the target distribution; intuitively, e.g., trying different reasoning strategies. The samplers proposed in prior works repeatedly select a "cut" position in the current reasoning trace uniformly at random and resample the suffix from that position onward. However, reasoning traces typically contain a few consequential decisions (e.g., the choice of proof strategy or algorithm), and we observe that a uniformly chosen cut tends to rewrite local details rather than revisit decision points. We introduce an algorithm (Entropy-Cut Metropolis-Hastings) that uses the base model's next-token entropy as a proxy to identify key decision points and resample from those positions. We empirically verify that entropy jumps are a useful proxy for decision points and, in a stylized model of reasoning, prove that our method's mixing time scales with the number of decisions in a trace rather than with the number of tokens, which can be much larger. Across MATH500, HumanEval, GPQA Diamond, and AIME26, our method consistently improves over baselines and RL-trained models.