A language model solving a math problem can be improved at test time by repeatedly revising its own solution. In one simple scheme, the model cuts its current solution at some point, regenerates everything after the cut, and then decides whether to keep the new version or revert to the old one. This is a Markov chain Monte Carlo (MCMC) sampler, meaning a random walk over candidate solutions that keeps or rejects each proposed move so that, in the long run, solutions are visited in proportion to a chosen target score. The sampler has a "step size": how much of the solution gets regenerated. Classical MCMC theory says step size should be tuned until a fixed fraction of proposals is accepted. That fraction is about 23.4% for random-walk samplers, about 65% for Hamiltonian samplers, and about 90% for microcanonical samplers. Nobody has asked what the right fraction is for chains over reasoning traces. Nobody has asked either whether such a rule can exist when the score used to accept moves comes from a model that is badly overconfident.
We propose to answer both questions together. Our hypothesis is that a stable optimal acceptance rate exists for reasoning-trace chains only when the acceptance score is calibrated. A calibrated score is a correctness estimate whose stated probability matches how often the solution is actually right. When the score is the model's own sequence likelihood, which is severely overconfident on wrong solutions, the acceptance rate carries little information and the chain locks onto confident errors. If the hypothesis holds, a single target acceptance rate can drive per-problem automatic tuning of how much to regenerate, the same way practitioners tune Hamiltonian samplers to roughly 65% without per-problem search. The tuning rule would be cheap and transferable. If the hypothesis fails, we will know precisely which assumption breaks.
Core Claim
Fix a base model $p$ and a calibrated correctness estimator $c(x)\in(0,1)$ computed from the model's hidden states on a complete trace $x$. The chain targets $\pi(x)\propto p(x)\,c(x)^{\beta}$, where $\beta$ controls how strongly correctness is favored. A move picks a cut position $k$, regenerates the suffix from $p$, and accepts with probability
$$\alpha(x\to x')=\min\left(1,\ \frac{c(x')^{\beta}\,|x|}{c(x)^{\beta}\,|x'|}\right),$$
where $|x|$ is the trace length. The length terms correct for choosing the cut uniformly over positions, and the base-model likelihood cancels because the suffix is drawn from $p$ itself. The step size is the regenerated suffix length. It is better measured in "fork points," the few tokens where the model's next-token distribution is genuinely uncertain, since overconfident models are nearly deterministic everywhere else.
Our hypothesis comes from a heuristic in the style of the diffusion-limit arguments. Suppose the change in $\beta\log c$ across a regenerated suffix of $m$ fork points behaves like a sum of $m$ weakly dependent increments. Then it is approximately Gaussian with variance $\sigma^2\propto m$ and mean $-\sigma^2/2$. That gives acceptance $2\Phi(-\sigma/2)$, where $\Phi$ is the standard normal distribution function, and expected fork-points-changed proportional to $\sigma^2\cdot 2\Phi(-\sigma/2)$. Maximizing this is the same calculation that produces the classical random-walk result, so the predicted optimum is roughly 0.23. The prediction is falsifiable. The product-form assumption is exactly what overconfidence should break. Raw log-likelihood ratios, or uncalibrated probe logits, are dominated by a handful of extreme forks, so their increments are heavy-tailed rather than Gaussian, and the optimum should then drift with model and difficulty.
Positioning
Three papers supply the motivation. Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective uses this prefix-cut-and-regenerate proposal with a Metropolis–Hastings acceptance test based on the model's own likelihood, for grammar-constrained generation. It does not study acceptance rates or calibration; we keep its proposal and change both the target and the tuning. Scalable Power Sampling targets the sharpened distribution $p^{\alpha}$ and abandons MCMC because it was over 10x slower than an autoregressive lookahead sampler. It never tunes the MCMC step size, and its target amplifies the model's own confidence, including confident errors. AERA documents that adding samples can break a correct majority: it reports 14 "collapse" and 42 "recovery" events on GPQA Diamond, and finds that majority ratio and entropy cannot separate the two cases. We read collapse as what happens when samples are scored by an overconfident energy, and we test whether a calibrated stationary target reduces it.
Several papers supply methods. Uncertainty Calibration for Tool-Using Language Agents shows that a small MLP probe on hidden activations predicts execution success well, cutting ECE from 0.690 to 0.035 on TabMWP. Our $c(x)$ is a probe of this kind, followed by post-hoc temperature fitting on held-out data. AutoStep gives a symmetric doubling/halving step-size selector that adapts step size per iteration while keeping the chain exact, and it recovers from initializations 14 orders of magnitude off. We port it to suffix length. Three papers (Diffusion limits of the random walk Metropolis algorithm in high dimensions, Optimal tuning of the hybrid Monte Carlo algorithm, Metropolis Adjusted Microcanonical Hamiltonian Monte Carlo) supply the template for the heuristic and the known targets of 23.4%, 65.1%, and about 90%. All three assume continuous spaces; our question is whether any analogue survives in a discrete, branching space.
Several papers constrain the design. Large Language Models Must Be Taught to Know What They Don't Know shows that verbalized confidence is unstable under rephrasing, which rules it out as the acceptance score. Calibrated Language Model Fine-Tuning shows that larger transformers are worse calibrated than shallow models, which is why raw likelihood is a poor energy. CarBoN is the nearest test-time competitor. It fits one logit shift and temperature after an exploration batch and then samples independently, with no chain, no acceptance test, and no adaptation after the fit.
Research Program
We first build the sampler on Qwen2.5-7B and Qwen2.5-Math-1.5B-Instruct. The probe $c$ is trained on final-answer correctness of sampled traces for MATH training problems, using the 7,500-problem split from Measuring Mathematical Problem Solving With the MATH Dataset, then temperature-calibrated on a held-out slice. Fork points are defined as tokens whose next-token entropy exceeds a threshold. Cut positions are sampled over fork points, with the corresponding correction applied in the acceptance ratio.
The second step is a sweep that measures the efficiency curve directly. For fixed suffix lengths we record the acceptance rate and accuracy per generated token, along with the expected number of distinct final answers visited per token. We do this under three energies: calibrated probe, uncalibrated probe logit, and raw power-likelihood. The measurement of interest is the acceptance rate at the efficiency peak, and how much that rate moves across difficulty levels 1 through 5, models, and datasets. We also test the Gaussian assumption directly by examining the distribution of log-acceptance ratios.
Third, if a stable band appears, we fix the target acceptance rate once on MATH and run AutoStep-style per-problem adaptation of suffix length. We then transfer that fixed rate unchanged to GSM8K and GPQA Diamond.
Baselines
The naive reference point is self-consistency majority voting over independent samples at the same total number of generated tokens. It represents doing nothing beyond spending compute. The same independent samples reranked by the calibrated probe, as Best-of-N, are a second baseline.
The strongest competitor for the chain is sampling-importance-resampling. We draw $N$ independent traces, weight each by $c^{\beta}$, and resample. This targets the identical distribution $\pi$ without any Markov chain, so it isolates whether the chain's reuse of correct prefixes actually helps. It is run with the same probe, the same $\beta$, and the same token budget.
The strongest published systems are two. The first is Scalable Power Sampling, which reports MATH500 accuracy of 70.8% for Qwen2.5-7B, up from 49.8% for the base model and close to GRPO at 74.0%. The second is CarBoN, which reports 77.2% on MATH-500 for Qwen2.5-Math-1.5B-Instruct at $N=64$. We reproduce both on the same models, prompts, and answer extraction, with matched completion tokens rather than matched sample counts. CarBoN's external process reward model is counted toward its cost. Beating these baselines means higher accuracy at equal tokens, or equal accuracy at fewer tokens, outside run-to-run variance across seeds. For MCMC power sampling there is no absolute MATH500 number on Lacuna; the file reports only that Scalable Power Sampling gives a 9.4% average improvement over it on Qwen2.5-32B. We therefore rerun it ourselves.
Two ablations isolate the key ingredients. The first keeps the chain and adaptive tuning but replaces the calibrated probe with its uncalibrated logits or with raw likelihood; this isolates calibration. The second keeps the calibrated probe but fixes the suffix length globally; this isolates acceptance-targeted adaptation. The tuning budget is equal for all methods: hyperparameters for every method are selected on the same MATH validation slice.
Why not just…?
Why not just rerank independent samples with the calibrated probe? This is the main threat. Sampling-importance-resampling reaches the same target, and if it matches the chain at equal tokens, the MCMC machinery adds nothing and the contribution reduces to probe reranking. The chain can only win where the base model rarely produces a correct trace, so that importance weights concentrate on very few samples. In that regime, keeping a correct prefix and regenerating only the part after an early error is far cheaper than rerolling. We will report the comparison stratified by MATH difficulty level and on GPQA Diamond, and we will accept a null result on easy problems.
Why not just temperature-scale the model or sharpen it with power sampling? Temperature acts on each next-token distribution separately. As Uncertainty Calibration for Tool-Using Language Agents argues, it cannot undo an early wrong commitment that is followed by confident tokens. Power sampling goes further and amplifies whatever the model is confident about. The energy ablation tests this directly: if a raw-likelihood chain matches the calibrated chain on accuracy and collapse counts, our explanation is wrong.
Why not just pick one suffix length by grid search and skip the theory? A tuned fixed suffix length may well be competitive on one dataset. The claim at stake is transfer. A target acceptance rate chosen once should adapt the step size to each problem's difficulty, whereas a fixed suffix length chosen on MATH should degrade on GSM8K and GPQA, where traces and fork density differ. The fixed-length ablation, evaluated on the transfer datasets without retuning, settles this.
Why not just fine-tune the model for calibration? The method of Large Language Models Must Be Taught to Know What They Don't Know reduces open-ended MMLU ECE from about 30% to 10%. It is complementary rather than competing: a fine-tuned calibrated head could serve as $c$. It does not by itself say how to allocate search, which is the question here.
Decisive Checks
The first check is whether the efficiency-maximizing acceptance rate under the calibrated energy falls in a narrow band across difficulty levels and both models, and whether the raw-likelihood optimum is visibly less stable. The near-0.23 prediction is secondary to stability. The second check is whether the calibrated chain beats sampling-importance-resampling at matched tokens on MATH level 5 and GPQA Diamond. The third check is whether, on GPQA Diamond, the calibrated chain produces fewer collapse events than self-consistency under AERA's definition, relative to AERA's reported 14. We will also measure ECE of the chain's answer-frequency confidence, because a sampler that converges to a calibrated target should yield answer frequencies whose stated confidence matches observed accuracy. If the first check fails under every energy, we will report that reasoning-trace chains admit no acceptance-rate tuning rule, which is itself a useful negative result for anyone reviving MCMC for reasoning.
References
- Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective
- Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening
- AERA: Adaptive Evidence Residual Allocation for Efficient Test-Time Reasoning
- Uncertainty Calibration for Tool-Using Language Agents
- AutoStep: Locally adaptive involutive MCMC
- Diffusion limits of the random walk Metropolis algorithm in high dimensions
- Optimal tuning of the hybrid Monte Carlo algorithm
- Metropolis Adjusted Microcanonical Hamiltonian Monte Carlo
- Large Language Models Must Be Taught to Know What They Don’t Know
- Calibrated Language Model Fine-Tuning for In- and Out-of-Distribution Data
- CarBoN: Calibrated Best-of-N Sampling Improves Test-time Reasoning
- Measuring Mathematical Problem Solving With the MATH Dataset