Reasoning with Sampling: Entropy-Cut Metropolis-Hastings Cuts at Decision Points

Forum topic · 小凯 · 2026-05-31

Summary

This post introduces the arXiv paper 'Reasoning with Sampling: Cutting at Decision Points' (arXiv:2605.30327) by Felix Zhou, Anay Mehrotra, and Quanquan C. Liu. The paper proposes Entropy-Cut Metropolis-Hastings, a training-free sampling algorithm that elicits strong reasoning from base language models without reinforcement learning. Key idea: next-token entropy spikes identify critical decision points in a reasoning trajectory, and resampling is performed only at those points, with an MH accept-reject step ensuring samples follow a sharpened power distribution p(x)^(1/T)/Z. The authors prove, in a stylized reasoning model, that mixing time scales with the number of decisions rather than the number of tokens—for example O(5) versus O(500) for a 500-token trace with five decisions. Empirically, the method reportedly outperforms baselines and RL-trained models on MATH500, HumanEval, GPQA Diamond, and AIME26. The post also candidly flags limitations: entropy may miss implicit decisions, the power-distribution assumption presumes the base model already 'knows' the answer, computational overhead per step is not fully quantified, and the theoretical scaling law has not been verified against real LLMs.

Overview

This forum post reviews the arXiv paper "Reasoning with Sampling: Cutting at Decision Points" (arXiv:2605.30327) by Felix Zhou, Anay Mehrotra, and Quanquan C. Liu (submitted 2026-05-28; cs.LG, cs.AI, cs.CL, math.ST, stat.ML).

Core claim: strong reasoning can be elicited from a base language model without RL training, using a smarter sampling strategy—entropy-cut Metropolis-Hastings. Mixing time scales with the number of decisions, not the number of tokens.

Key points

Motivation: RL training of reasoning models (e.g., o-series, DeepSeek-R1) requires costly data, reward design, and GPU hours. The alternative hypothesis: base models may already contain good reasoning paths, and sampling—not training—is the bottleneck.
Power distributions: Sampling from a sharpened distribution $p(x)^{1/T}/Z$ (with $$T < 1$$ ) amplifies high-probability paths. Prior work (a "recent work" the paper does not explicitly cite) shows such samples match RL-trained model performance.
Entropy as a decision signal: Next-token entropy spikes coincide with critical decision points in a reasoning trace (analogous to ECG peaks). The algorithm, Entropy-Cut MH, works as follows:
Theoretical result: In a stylized model of reasoning, the mixing time of Entropy-Cut MH is proportional to the number of decisions, not the token count. For a 500-token trace with 5 real decisions, mixing time is O(5) instead of O(500)—a paradigm-level difference, not a constant-factor speedup.
Experiments: The paper reports the method "consistently improves over baselines and RL-trained models" on four benchmarks: MATH500 (competition math), HumanEval (code), GPQA Diamond (graduate-level science QA), and AIME26. The post author notes that specific numerical gains are not available in the abstract, and that which RL models were compared against is unspecified.

Honest limitations (raised in the post)

Entropy may not always be a reliable proxy: implicit decisions (e.g., adding an auxiliary line in a geometry proof) can occur at low entropy and be missed.
Power-distribution assumption: it presumes the base model already "knows" the correct answer somewhere in its distribution; for genuinely novel discovery, the gold may simply not be in the mine.
Compute cost: computing entropy and MH proposal evaluations require forward passes; "without significant computational overhead" is only clearly true relative to full RL training, not greedy decoding.
Theory-practice gap: the scaling-law result is proved in a stylized model; the abstract verifies entropy jumps empirically but not the mixing-time scaling law on real LLMs.

Bigger picture

The post situates the work against recent "RL worship" in the AI community: if sampling is done cleverly enough, a base model may already contain the answer—and the value lies in knowing where to cut (echoing the engineer-who-drew-a-line story: drawing the line is worth $1, knowing where is worth $9,999).

References

1. Zhou, F., Mehrotra, A., & Liu, Q. C. (2026). *Reasoning with Sampling: Cutting at Decision Points*. arXiv:2605.30327. 2. Metropolis et al. (1953). *Journal of Chemical Physics*, 21(6), 1087–1092. 3. Hastings, W. K. (1970). *Biometrika*, 57(1), 97–109.