acceptodds
Under review as a conference paper at ICLR 2027

Explore Broadly, Reason Sharply: Push Small Models Toward the Frontier via Sampling

17 views

Abstract

Power-sharpened sampling is an inference-time alternative to reinforcement-learning (RL) post-training for enhancing reasoning in large language models (LLMs). High-probability sequences are amplified under the base model without parameter updates or external rewards, avoiding the costly optimization and jagged generalization of RL. However, this approach faces a fundamental exploration–exploitation trade-off, as strong sharpening restricts exploration, trapping samplers in plausible but incorrect reasoning trajectories, whereas weak sharpening leaves the answer distribution diffuse. To resolve this trade-off, we introduce **Parallel Power Tempering (PPT)**, instantiating power-sharpened LLM sampling via parallel tempering. Running multiple interacting replicas in parallel at different sharpening levels allows lower-power replicas to explore diverse reasoning trajectories and higher-power chains to further exploit higher-likelihood responses favored by the sharpened target. Specifically, we tailor PPT to inference-time sampling by mitigating a truncation bias, identified in prior power samplers, and investigate effective swap strategies under finite memory and compute budgets. Extensive experimentation shows that our PPT substantially improves single-chain power-sharpened sampling and outperforms RL-post-trained models, producing higher-quality reasoning traces and even achieving performance comparable to frontier models.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language models, Parallel Tempering, Reasoning, MCMC, Sampling, Inference-time compute

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_zi5qOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

Parallel Power Tempering applies interacting replicas at different powers to sequence-level sharpened language-model distributions. A fixed-horizon construction corrects one-way shortening in prior samplers, while reversible suffix proposals and replica swaps preserve the intended stationary target. Experiments compare reasoning accuracy, sampling controls, communication schedules, and runtime/memory costs.

Critical strengths
  1. The fixed-horizon correction is technically important. The paper identifies a specific reverse-support failure and constructs proposals on a common record space, making the target-preservation argument materially stronger than an informal tempering analogy.
  2. The fixed-horizon single-chain, uncoupled-ladder, and token-budget-matched comparisons isolate useful parts of the empirical gain. The explicit memory and local-update costs also make the resource trade-off assessable.
Critical weaknesses
  1. Stationary-target preservation does not establish that the few refinement steps used in practice produce an approximately equilibrated output. Block extensions initialize a different distribution, and the paper itself separates finite-budget error from invariance. Stronger practical mixing evidence is needed to attribute accuracy gains specifically to sampling the intended sharpened target.
  2. The frontier-model comparison uses reported external scores rather than a matched inference protocol, while the strongest small-model settings use very large completion horizons and multiple internal proposals. Frontier comparability is therefore a limited benchmark observation rather than demonstrated resource-matched reasoning parity.
Questions for authors
  1. How do output statistics and accuracy change with longer refinement, different initializations, and replica round-trip diagnostics at the reported settings?
  2. Does the small-model advantage persist against matched latency/token-budget baselines under identical prompts and completion limits?
2 comments
AuthorsOpenReview ↗

Author Response to Reviewer zi5q (Part 1/3)

We truly appreciate the encouraging comments of the reviewer, as well as their useful remarks. In the following, we address the points raised by the reviewer.

1. Finite-budget mixing evidence

We thank the reviewer for the comment. Preserving the stationary target ensures the theoretical correctness of our algorithm. We agree that it does not imply that finite-budget samples have reached equilibrium, and we state this explicitly in the revision. We highlight that the accuracy gains over a single fixed-horizon chain are attributable to the parallel tempering mechanism of PPT. The mixing benefits of replica exchange, including exponential speedups for certain classes of multimodal distributions, have been widely studied [1]. We support this with two pieces of evidence.

Exact computation in a toy model. First, we devise the following example to isolate the mechanism by which exchange reduces finite-budget error from a non-target initialization:

  • Model: vocabulary {A, B, EOS}, at most T=3T=3 generated tokens, stopping at EOS (15 valid records), with next-token probabilities at each prefix drawn i.i.d. from Dirichlet(2, 2, 1).
  • Target and ladder: output target πα⋆∝p02.5\pi_{\alpha^\star}\propto p_0^{2.5}, with powers {1.0, 1.5, 2.0, 2.5}.
  • Initialization: each replica is drawn from the tokenwise-powered proposal gαkg_{\alpha_k} used by block extension, so both arms start from the same output-rung distribution, which is not the target.
  • One round: one suffix-resampling MH update per replica, followed, when exchange is enabled, by one sweep of adjacent swaps.
  • Measurement: exact propagation of the joint distribution, then the total-variation distance between the output-rung marginal and πα⋆\pi_{\alpha^\star}, averaged over three random models.

Table A. TV distance to the target in the toy model.

Rounds05102050
Single chain (K=1K=1)0.32080.12810.07240.02800.0020
PPT (K=4K=4)0.32080.04880.01540.00194.1×10−64.1\times10^{-6}

The initializer places the output-rung marginal at TV 0.32 from the target, a concrete instance of the reviewer's point that block extension starts away from πα⋆\pi_{\alpha^\star}. Exchange lowers the error by 2.6× after 5 rounds and by 4.7× after 10, round counts comparable to those we deploy (6–20 per block). Both arms make the same local proposals, and swaps reuse cached likelihoods, so the arms are matched in proposals, though not exactly in tokens, since suffix lengths depend on the state.

Exchange moves high-likelihood records to the cold rung, where they are sharpened. Second, since the distance to πα⋆\pi_{\alpha^\star} cannot be computed for an LLM, we measure the effect of exchange within the actual refinement budget: how often the cold chain holds the highest-likelihood state among the KK replicas, with swaps enabled and disabled under matched compute and initialization. With swaps it does so in 89.2–97.5% of evaluations, compared with 29.0–54.8% without (Table B). Consistent with this, Figure 5 shows that PPT's returned traces concentrate at higher average log-likelihood than those of Power Sampling, GRPO and standard decoding (MATH500, Qwen3-8B). Concentrating on high-likelihood responses is how sharpening can improve final-answer accuracy.

Table B. Evaluations where the output rung holds the highest-likelihood record (%), Qwen3-8B.

MATH500GPQAAIME 24&25LCB v5HumanEval
PPT89.297.596.795.995.1
Swaps off29.037.442.354.841.3

2. Scope of the frontier-model comparison

We agree that the comparison should be described as an observation about reported benchmark scores. The frontier entries come from external evaluations, and we cannot establish comparable prompts, inference budgets, or latency. We will make this distinction clear in the caption of Figure 1 and in Section 4.1 of the revision.

The frontier entries in Figure 1 and Table 2 are scores reported by external evaluations. We did not re-run those models, so we cannot establish that their prompts, inference budgets, decoding settings, or latency match ours. Several reported configurations also do not disclose enough to align them. Therefore, the comparison is an observation about reported benchmark scores. It is not evidence of resource-matched reasoning parity, and we will state this explicitly. The point we want to make is that a 9B model, with no additional post-training, reward model, or verifier, and returning a single completion per problem, exceeds or comes within a few percentage points of the reported results of frontier models on GPQA-Diamond, AIME 24&25 and LiveCodeBench v5. We read this as evidence of how much reasoning capability is latent in a small model's distribution and how effectively PPT recovers it at inference time.

AuthorsOpenReview ↗

Author Response to Reviewer zi5q (Part 3/3)

4. Longer refinement, initialization and round trips

Longer refinement. Table C varies the number of refinement steps per block, NN, from 0 (the initial trace, before any refinement) to 50, with Qwen3-8B. Accuracy rises quickly and then saturates. On MATH500, the seed-averaged accuracy increases within the first ten steps and then stays at about 88 all the way to N=50N=50, with the fluctuations on the plateau within seed noise. HumanEval follows the same pattern. Intuitively, the first few steps do most of the work because they correct the errors that are cheap to correct: an initial trace that went wrong through an unlucky low-probability step is quickly replaced by one that the sharpened target prefers. Once the chain has reached the high-probability region of its target, further steps only move among traces of comparable quality. The errors that remain are those where the model itself favors a wrong answer, which additional sampling from the same target cannot be expected to repair.

We draw two main conclusions: (i) a small budget captures most of the benefit, so the method does not rely on long chains; and (ii) extending the budget well beyond that point neither helps nor hurts. The absence of late degradation is what one expects from a sampler with a fixed target distribution, as opposed to an optimizer that keeps sharpening its output and eventually over-commits.

Initialization. We also examine how strongly the output depends on the initial sequence. We re-ran both sweeps with every chain's initial state drawn at temperature 1.0 (more diffuse than any rung) or 0.2 (sharper than any rung), instead of the rung's own 1/α1/\alpha. The target, local moves and swaps are unchanged. Tables E and F show that even when the replicas begin from deliberately diffuse or sharp distributions, their likelihood trajectories rapidly draw together. Refinement removes roughly 90% of the initial separation, with half of the diffuse start's gap to the default disappearing within just 2–3 steps. Most of the initial separation therefore disappears within the reported budget, showing substantial forgetting of the starting conditions. The different starts also produce similar final accuracy. Together, these results support substantial forgetting of initialization and are consistent with convergence toward a common output distribution. We visualize these tables in the revision (App. H.3).

Table E. Accuracy (%) vs. NN for three initializations, Qwen3-8B. mean ± std over 5 seeds.

NNMATH500 defaultMATH500 diffuseMATH500 sharpHumanEval defaultHumanEval diffuseHumanEval sharp
083.4 ± 0.783.081.286.0 ± 1.183.878.6
183.6 ± 1.481.681.085.6 ± 0.682.379.2
284.4 ± 1.682.882.286.2 ± 0.485.984.7
486.6 ± 0.882.680.289.8 ± 0.989.087.8
587.3 ± 0.683.081.891.5 ± 0.790.290.2
686.8 ± 0.884.884.290.2 ± 0.691.490.2
1088.0 ± 0.686.484.692.2 ± 0.492.191.4
2087.9 ± 0.888.087.694.9 ± 1.591.492.1
3088.9 ± 0.687.887.293.7 ± 1.293.392.1
4088.4 ± 0.487.486.894.1 ± 0.992.793.3
5088.2 ± 0.688.086.894.3 ± 1.192.192.1

Table F. Per-token log-likelihood of the returned output vs. NN.

NNMATH500 defaultMATH500 diffuseMATH500 sharpHumanEval defaultHE diffuseHE sharp
0−0.1045−0.2038−0.0964−0.1644−0.2696−0.1264
1−0.1004−0.1690−0.0935−0.1535−0.2139−0.1201
2−0.0993−0.1509−0.0919−0.1466−0.1867−0.1154
4−0.0981−0.1401−0.0903−0.1439−0.1805−0.1153
5−0.0970−0.1281−0.0899−0.1402−0.1706−0.1159
10−0.0950−0.1149−0.0892−0.1372−0.1554−0.1168
20−0.0925−0.1065−0.0885−0.1312−0.1417−0.1158
30−0.0912−0.1030−0.0873−0.1286−0.1354−0.1147
40−0.0902−0.0996−0.0869−0.1256−0.1319−0.1140
50−0.0895−0.0975−0.0863−0.1241−0.1299−0.1123

Round trips. Table G gives the share of problems on which at least one replica completes a round trip on Qwen3-8B, with NN from 10 to 50 on every benchmark and all other settings as in Table 8. With 50 steps, almost all problems on every benchmark have a round trip.

Table G. Problems with at least one round trip (%), Qwen3-8B.

NNMATHAIMEGPQA-DLCB v5HumanEval
1017.432.127.036.954.5
2038.548.769.379.768.1
3073.583.077.292.686.6
4099.097.495.710098.3
50100100100100100

References

[1] Spectral Gap of Replica Exchange Langevin Diffusion on Mixture Distributions.

Reviewer_u8bFOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Parallel Power Tempering (PPT), which runs multiple replicas at different sharpening levels to address the exploration–exploitation trade-off in power sampling. In the main experiments, PPT improves over power sampling, and GRPO baselines, and is competitive with some reported frontier-model results.

Critical strengths
  1. The paper proposes a reasonable way to improve power sampling, with theoretical contributions on truncation bias, invariance of the target distribution, and convergence.
  2. The results show improvements over power sampling and GRPO, and also match with some reported frontier models. It also corrects the structural truncation bias identified in prior implementations of power sampling.
Critical weaknesses
  1. The authors report that PPT takes 1.03x and 1.72x the local-update time of single-chain MH for the two models in Table 3. However, PPT requires more KV-cache memory, therefore batching independent MH runs across different problems under the same KV-cache budget could achieve higher throughput. This is an expected trade-off for improved performance, but MH is already expensive, which may limit the broader applicability of the proposed method.
Questions for authors
  1. Could the authors clarify how the hyperparameters for PPT and the baselines were selected, and what validation setting was used?
  2. Figure 5 shows monotonically increasing accuracy for (K=1,...,5). Could the author explain the reason of choosing K=3, 4 and 6 across datasets for the main results in Table 6 instead of using K=5 with better performance? Also the minimum and maximum (\alpha) values selected for each dataset were quite different.
3 comments
AuthorsOpenReview ↗

Author Response to Reviewer u8bF (Part 1/2)

We would like to thank the reviewer for their positive comments, as well as their constructive criticism and further suggestions for improving our work. In the following, we address the points raised by the reviewer.

1. Cost, memory and compute-matched comparison

We agree that PPT is expensive in both time and memory, and that at a fixed KV-cache budget, independent single-chain runs batched across problems achieve higher throughput. Our aim is to show how far a small model can be pushed by balancing exploration and exploitation, so PPT targets settings where per-problem accuracy matters more than throughput. Further optimizing efficiency is left for future work, and recent advances in accelerating MH power sampling [1, 2] suggest PPT can be made substantially faster. Since PPT is more expensive, we conduct compute-matched comparisons on Qwen3-8B that give the baselines at least the same token budget as PPT.

We consider the following baselines: (i) Uncoupled ladder (no swaps): PPT's KK replicas at the same temperatures, with swaps turned off. This isolates the contribution of the swap move. (ii) Single chain (K=1K=1), more MH steps: the control of Table 14, one fixed-horizon MH chain that spends the extra budget on additional refinement steps. (iii) KK independent chains at the target temperature 1/αK1/\alpha_K, running the fixed-horizon kernel. (iv) Best-of-N: N independent samples from the base model, with N set by the budget.

The metrics are: (i) Pass@1: accuracy of the single trace a method returns. For PPT and the uncoupled ladder this is the cold (target-temperature) replica; for the KK independent chains, the first chain; for the single chain, its final state; for Best-of-N, which has no designated output, its highest-log-likelihood sample. (ii) Vote (AIME): majority vote over the final answers of all traces a method produces. (iii) Norm. ML (LCB v5): the trace with the highest length-normalized likelihood, since programming tasks have no single answer to vote on.

Table A. Compute-matched comparison on AIME 24&25, Qwen3-8B.

MethodTokensPass@1Vote
Single chain (K=1K=1), ≈4× MH steps215k75.3—
Uncoupled ladder151k76.780.0
K=4K=4 independent chains at αK\alpha_K151k74.376.7
Best-of-N (N=10)154k72.878.7
PPT (K=4K=4)151k78.381.7

Table B. Compute-matched comparison on LCB v5, Qwen3-8B.

MethodTokensPass@1Norm. ML
Single chain (K=1K=1), ≈4× MH steps213k54.9—
Uncoupled ladder211k55.057.2
K=4K=4 independent chains at αK\alpha_K211k56.157.9
Best-of-N (N=38)213k49.658.6
PPT (K=4K=4)210k58.460.1

The tables shows that PPT's advantage comes from replica exchange. We argue that PPT's performance gains are not an artifact of the cost, since at equal cost, neither more MH steps, nor more independent chains, nor more samples return a more accurate trace than parallel tempering.

2. Hyperparameter selection and validation

For each evaluation benchmark, hyperparameters were selected on a task-specific proxy set disjoint from the evaluation data. For MATH500, we used 100 problems sampled at random from the 5,000-problem MATH test set, excluding those in MATH500; for LiveCodeBench v5, 100 problems from LiveCodeBench v6 that do not appear in v5; and for GPQA-Diamond, 100 problems from GPQA-main that are not in the Diamond subset. The proxy sets for the other benchmarks are listed in App. G.5 of the revision. For PPT, we initialized each hyperparameter shared with Power Sampling to the value selected for that baseline, and then tuned four settings that we found to matter most for performance: (1) the number of MH updates, (2) the block size, (3) the horizon capacity and (4) the power ladder.

We varied one setting at a time while holding the other three fixed. For a given pair of ladder endpoints, we initialized the powers with geometric spacing and then automatically adjusted the intermediate powers so that the observed swap acceptance rates are approximately equal across adjacent pairs. Tables 8 and 9 of the manuscript report the final PPT configurations. For Power Sampling and PowerSMC, we used the official implementations and tuned method-specific hyperparameters separately for each model with a similar procedure. We tuned Power Sampling first, following the same protocol as for PPT, and reused its selected temperature for both PowerSMC and low-temperature decoding. Standard decoding used a temperature of 1. For GRPO, we evaluated existing trained checkpoints.

AuthorsOpenReview ↗

Author Response to Reviewer u8bF (Part 2/2)

3. Choice of K and ladder endpoints

Figure 6 (Figure 5 in the previous version) shows diminishing returns in KK. Going from K=3K=3 to K=4K=4 adds 1.61.6 % on MATH500 and 2.12.1 % on HumanEval, whereas K=4→5K=4\to5 adds only 0.5–0.60.5–0.6%. That last step costs about 25% more decode tokens and KV-cache memory, since both grow roughly linearly in KK (App. B, Table 3), and 13–27 % more wall-clock time (Figure 6, bottom). Therefore, we considered up to K=4K=4 for our reported results on all Qwen3 benchmarks except GSM8K. In particular, we use K=4K=4 on MATH500, AIME 24&25 and LiveCodeBench v5. We prefer K=3K=3 on GPQA-Diamond and HumanEval, as the gain from K=3K=3 to K=4K=4 on their proxy sets was found to be small. The Figure 6 sweep was run afterwards on the evaluation sets; it shows that K=4K=4 would add 2.12.1 % on HumanEval, so the K=3K=3 we report there is conservative.

The number of rungs KK was fixed per benchmark from the cost budget and the ladder range, not selected for test accuracy. Since accuracy increases with KK in Figure 6, this choice is conservative with respect to accuracy.

The two ladder endpoints serve different purposes. The upper endpoint, αmax⁡\alpha_{\max}, sets the power of the target distribution, while the lower endpoint, αmin⁡\alpha_{\min}, determines how broadly the lowest-power replica explores. Both are selected per benchmark on its proxy set (see above), which is why they differ across datasets. The one constraint we found to generalize is that the coldest rung should not be too sharp for long completion caps (see the fixed-ladder study in our response to Reviewer UgBW: 'Sensitivity to the ladder and tuning cost'). Given the endpoints, the intermediate powers follow the equi-accepting rule of Section 3.4, giving adjacent acceptance of 19–3719–37 % on Qwen3 (Table 12).

GSM8K is the exception. Its short completions (T=3072T=3072) keep extra replicas cheap, so we could afford K=6K=6. The additional rungs let the ladder extend well beyond the ranges used on the other benchmarks while adjacent replicas keep communicating. The selected range (2.0–4.0) is by far the widest, yet the gaps stay at 0.3–0.5 and adjacent acceptance at 27–3327–33 % (Table 12). The effect on accuracy is small, as GSM8K is near saturation for these models.


References

[1] PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling

[2] Reasoning with Sampling: Cutting at Decision Points

Thank you for the clarification and additional experiments. My main concerns have been addressed, and the hyperparameter selection procedure looks reasonable. I will maintain my original positive assessment

Reviewer_UgBWOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Building on sampling-based approaches to inference-time reasoning, the authors of this paper introduce parallel tempering MCMC approaches to LLM sampling as a means of attempting to go beyond simple distribution sharpening and explore at flatter temperatures while exploiting at higher temperatures. Parallel tempering involves maintaining MCMC style steps for power distributions at a range of temperatures, and then mixing trajectories between temperatures. The results demonstrate this style of reasoning outperforms GRPO and other power sampling baselines on a variety of benchmarks.

Critical strengths
  • Very very strong performance on AIME/LiveCodeBench, which are substantially difficult tasks that are matched to frontier model performance.

  • Well thought out compute-matched control experiments

Critical weaknesses
  • Minor weakness, but tuning the replica temperatures per task might not immediately simple, especially determining the spacing between the top and bottom temperature since that seems to vary quite a bit across tasks.
Questions for authors
  • Could the authors report the average token overhead in terms of sequence length and other block parameters to understand how it grows with sequence length?

  • How would you succinctly attribute the success of parallel tempering compared to power sampling? If I understand correctly, the individual replica chains are locally refined via power sampling, and the swaps execute tempering. Is the swap rate relatively high? Is parallel tempering enabling discovery of higher likelihood modes?

  • Figure 7 seems to show that parallel tempering sharpens even more strongly than GRPO and power sampling. How should we think of the exploration component at higher temperatures feeding into the exploitative sampling at lower temperatures?

  • In light of the prior question, could the authors report pass@k performance on a particular benchmark (AIME or LiveCodeBench) relative to some other baselines? In other words, would be interesting to see if this stronger sharpening does not come at a cost to generation diversity as in GRPO.

  • How sensitive is performance to replica temperatures? Is there a configuration that universally works well? How expensive is the tuning process?

  • The replica temperatures seem to be all greater than 1, so the "annealing" is all done on sharpened versions of the base model. Is there an advantage of using powers less than 1 for better exploration?

5 comments
AuthorsOpenReview ↗

Author Response to Reviewer UgBW (Part 1/4)

We truly appreciate the encouraging comments of the reviewer, as well as their useful remarks. In the following, we address the points raised by the reviewer.

1. Token overhead vs. sequence length and block parameters

We thank the reviewer for this question. Our analysis has three parts: (1) a token-cost approximation, (2) the measured overhead as a function of sequence length, and (3) parameter sweeps.

I. Token cost: approximation and bounds

Let TT be the completion cap, MM the number of equal-width blocks (width B=T/MB=T/M), KK the number of replicas, and NN the number of MH proposals per replica per block. At block mm, each replica extends to the horizon Tm=mT/MT_m=mT/M or to EOS, then makes NN proposals, each drawing r∼Unif{1,…,Tm}r\sim\mathrm{Unif}\{1,\dots,T_m\} and regenerating positions r,…,Tmr,\dots,T_m until EOS; a restart after the current EOS is a self-transition and decodes nothing. Let LkL_k be the final length of replica kk and ℓk,m=min⁡(Lk,Tm)\ell_{k,m}=\min(L_k,T_m). Ignoring length changes from accepted proposals and swaps, a fraction ℓk,m/Tm\ell_{k,m}/T_m of restarts is live and, taking the new suffix to be as long as the old one, each regenerates about (ℓk,m+1)/2(\ell_{k,m}+1)/2 tokens, so the expected cost per problem is

D^=∑k=1K[Lk+N∑m=1Mℓk,m(ℓk,m+1)2Tm].\hat D=\sum_{k=1}^K\Big[L_k+N\sum_{m=1}^M\frac{\ell_{k,m}(\ell_{k,m}+1)}{2T_m}\Big].

For M=1M=1 this is a per-replica factor 1+N(L+1)/(2T)1+N(L+1)/(2T) over one generation of length LL. The worst case, reached only if no chain terminates (Lk=TL_k=T), is D^≈KT(1+N(M+1)/4)\hat D\approx KT\big(1+N(M+1)/4\big).

II. Token overhead vs. sequence length

The MATH500 results in the paper use T=8192,K=4,M=2T=8192, K=4, M=2 and N=10N=10. Table 14 reports 89k decoded tokens per problem for this setting, about 21.7× standard decoding. To show the dependence on sequence length, Table A groups the 500 problems of this run by the mean final length Lˉ\bar L of their four chains. DD is the measured number of decoded tokens per problem and D^\hat D the estimate from the equation above. The last column is the overhead over standard decoding per chain, D/(KLˉ)D/(K\bar L): the tokens a chain decodes relative to a standard generation of the same length. The "At cap" column counts all four chains of each problem.

Table A. Token cost by mean final chain length, MATH500, Qwen3-8B.

Lˉ\bar L binProblemsMean final length of all the chains$\bar L$Chains at capMeasured decoded tokens per problem DDExpected token cost per problem D^\hat DD/D^D/\hat Doverhead over standard decoding per chain$D/(K\bar L)$
<1k159200%12.8k10.0k1.283.5
1–2k16615440%31.0k24.5k1.265.0
2–3k10025160%60.5k57.5k1.056.0
3–4k6235670%100.9k106.6k0.957.1
4–6k5748632%136.6k158.2k0.867.0
6–8k59717228%183.6k238.5k0.776.4
all at cap418192100%198.8k278.6k0.716.1
all500355812%88.8k102.2k0.876.2

The cost per output token grows with length while completions are shorter than one block and levels off or even declines slightly beyond it, so the total cost grows faster than linearly up to L≈BL\approx B and about linearly afterwards. D^\hat D follows the same trend but under-predicts short completions, whose proposals can run past the current EOS, and over-predicts those close to the cap, whose proposals can only be shorter. Only a few chains reach the cap, so most chains are no longer active in the second block, many of its proposals decode nothing, and a regenerated suffix tends to end early instead of running to the cap. This is also why D^\hat D, which assumes the new suffix is as long as the old one, over-predicts long completions (D/D^=0.71D/\hat D=0.71 at the cap), and why the average cost (88.8k) is about a third of the worst case (278.6k).

AuthorsOpenReview ↗

Author Response to Reviewer UgBW (Part 2/4)

1. Token overhead vs. sequence length and block parameters (Continuation)

III. Token cost parameter sweeps

We compare PPT with K=4K=4 replicas against standard decoding at the same budget TT and against a single MH chain (K=1K=1), using Qwen3-8B on MATH500. The fixed-horizon kernel uses MM blocks, KK replicas, and NN refinement proposals per replica per block. There are 3 sweeps, each with K=1K=1 and K=4K=4.

Horizon. We first vary TT from 2k to 32k with M=1M=1 and N=4N=4. Entries give the mean decoded tokens per problem; parentheses give the ratio to standard decoding on the same prompts and at the same cap. At T=8192T=8192, standard decoding averaged 4.1k tokens on MATH500. With a single block, every proposal restarts at a position drawn uniformly over the whole cap. When the cap is tight, completions fill it, almost every restart is live, and the overhead is close to its worst case. As the cap grows past the natural completion length, a growing share of restarts lands after EOS and costs nothing, so the overhead relative to standard decoding shrinks even though the budget is larger. The cost of PPT is therefore tied to how long the completions actually are.

Table B. Tokens per problem vs. cap TT.

KKTT=2k4k8k10k16k32k
15.4k (2.8×)7.6k (2.5×)8.9k (2.2×)9.3k (2.2×)9.1k (1.9×)6.7k (1.3×)
421.7k (11.3×)30.7k (10.2×)36.1k (8.8×)36.1k (8.4×)34.9k (7.3×)29.9k (6.0×)

Refinement. With M=1M=1 and T=8192T=8192, we vary N∈{1,2,4,8,10}N\in\{1,2,4,8,10\}. Token use grows approximately linearly with NN. This agrees with the expected cost D^\hat D, in which each additional proposal contributes E[L(L+1)]/(2T)\mathbb E[L(L+1)]/(2T) tokens per replica when the length distribution stays fixed. The cost decomposes into one ordinary generation per replica plus a constant price per proposal, so NN is a linear dial with no compounding. That price is only a fraction of a full generation, because restarts beyond EOS are free and live restarts regenerate only a suffix. Decoded tokens also grow about KK-fold, as noted in Appendix B, whereas replica-batching leads to more favorable wall-clock scaling.

Table C. Tokens per problem vs. proposals NN.

KKNN=124810
15.3k (1.3×)6.5k (1.6×)8.9k (2.2×)13.9k (3.4×)16.4k (4.0×)
421.1k (5.1×)26.0k (6.3×)36.1k (8.8×)56.3k (13.7×)66.4k (16.2×)

Blocks. We fix T=8192T=8192, make one proposal per replica per block, and vary M∈{1,2,4,8}M\in\{1,2,4,8\}. Splitting the same cap into more blocks does not change the final horizon, but it adds a round of proposals at every intermediate horizon, so the cost tracks the total number of proposals, roughly N×MN\times M per replica. Proposals at early horizons act on records that have not yet terminated, so they are mostly live but regenerate short suffixes; later ones are cheaper relative to their horizon because many restarts fall after EOS. The block width therefore acts on cost through the same quantity as NN, the total number of proposals per replica.

Table D. Tokens per problem vs. number of blocks MM.

KKMM=1248
15.3k (1.3×)6.3k (1.5×)8.4k (2.0×)12.2k (3.0×)
421.1k (5.1×)25.6k (6.2×)34.1k (8.3×)50.4k (12.3×)
AuthorsOpenReview ↗

Author Response to Reviewer UgBW (Part 3/4)

2. Role of swaps and higher-likelihood modes

The reviewer's reading is correct: each replica is refined locally by MH updates at its own temperature, and swaps between adjacent replicas perform the tempering.

Swaps. To capitalize on the benefit of parallel tempering, the distributions at adjacent temperatures must overlap sufficiently. Powers placed too far apart exchange rarely and can leave parts of the ladder effectively disconnected within the available update budget. Powers placed too close together make the replicas explore much the same set of trajectories. In our tuning, adjacent-swap acceptance rates of roughly 20–50%20–50\% worked well on most tasks. Below about 15%, trajectories rarely traveled far along the ladder. Above 60%60\%, frequent swaps often added little new exploration.

Higher-likelihood modes. PPT and Power Sampling target the same sharpened distribution, while GRPO sharpens by updating the model. Single-chain Power Sampling sharpens at the expense of exploration and often gets trapped in local modes. PPT addresses this by using swaps to couple high-temperature chains, which explore, with low-temperature chains, which exploit. High temperatures favor exploration but are weaker at exploitation, so a high-likelihood response found at a warm rung is a strong signal; it travels to a colder rung via the swaps, where the cold chain exploits and refines it. PPT's traces therefore reach higher likelihood not because its target is sharper, but because it escapes the local traps that confine a single Power Sampling chain.

Table E shows that the output rung of PPT holds the highest-likelihood record among the KK replicas in 89.2–97.5%89.2–97.5\% of evaluations with swaps enabled, against 29.0–54.8%29.0–54.8\% without. The per-rung histograms we include in the revision show the same division of labor: the warm rungs are broad and extend to the left, and the cold rung concentrates to the right, at higher likelihood than Power Sampling. As a result, PPT's returned traces achieve higher average log-likelihood than the baselines, as illustrated in Figure 5 of the manuscript (Figure 7 in the previous version).

Table E. Evaluations where the output rung holds the top-likelihood record (%), Qwen3-8B.

MATH500GPQAAIME 24&25LCB v5HumanEval
PPT89.297.596.795.995.1
Uncoupled29.037.442.354.841.3

3. Pass@k: PPT does not sacrifice diversity

We thank the reviewer for this question. By design, PPT does not obtain the sharpness of the output rung by collapsing the sampler onto a single mode, as GRPO does, but by exploring throughout the run via the lower-power replicas. Therefore, we do not observe any meaningful compromise in answer diversity with PPT. Below we report pass@k on AIME 24&25 and LiveCodeBench v5 with Qwen3-8B. All methods receive the same per-problem decode-token budget, counting refinement proposals for the MCMC-based samplers as in Table 14. Pass@k counts a problem as solved if any of the k final traces is correct: k=K=4 replicas for PPT, the uncoupled ladder and the KK independent chains at αK\alpha_K, and k=N samples for Best-of-N, with N=10 for AIME and N=38 for LCB v5.

Table F shows that, even at matched compute, the pass@k of PPT remains on par with Best-of-N: 86.7 vs. 85.3 on AIME (a difference of less than one of the 60 problems) and 63.2 vs. 63.9 on LiveCodeBench. Best-of-N is the natural reference for diversity, since it spends the entire budget on independent completions, each a fresh attempt at the problem. PPT also exceeds both the uncoupled ladder and the KK independent chains at αK\alpha_K in pass@k on both benchmarks, suggesting that the gains from exchange do not come at the cost of coverage.

Table F. pass@k at matched decode tokens, Qwen3-8B.

MethodAIMELCB v5
Best-of-N85.363.9
KK independent chains at αK\alpha_K82.762.5
Uncoupled ladder85.062.5
PPT (ours)86.763.2

Comments on the paper

3 comments
AuthorsOpenReview ↗

Author Response to Reviewer zi5q (Part 2/3)

3. Advantage in Compute-matched comparison

In our experiments, all methods on a given model share the same prompt, grader and benchmark-specific completion cap (Appendix G.4). Below, we show that PPT's advantage persists when the baselines receive at least its decode-token budget.

We compare PPT against the following baselines: (i) Uncoupled ladder (no swaps): PPT's KK replicas at the same temperatures, with swaps turned off. This isolates the contribution of the swap move. (ii) Single chain (K=1K=1), more MH steps: one fixed-horizon MH chain that spends the extra budget on additional refinement steps. (iii) KK independent MH chains running the fixed-horizon kernel at the target temperature 1/αK1/\alpha_K. (iv) Best-of-N: N independent samples from the base model, with N set by the budget.

The metrics are: (i) Pass@1: accuracy of the single trace a method outputs, with no selection across traces. For PPT and the uncoupled ladder this is the cold (target-temperature) replica; for the KK independent chains, the first chain; for Best-of-N, its highest-log-likelihood sample. (ii) Vote (AIME): majority vote over the final answers of all traces a method produces. (iii) Norm. ML (LCB v5): the trace with the highest length-normalized likelihood, since programming tasks have no single answer to vote on.

We give every baseline at least as many decode tokens per problem as PPT.

Table C. Compute-matched comparison on AIME 24&25, Qwen3-8B.

MethodTokensPass@1Vote
Single chain (K=1K=1), ≈4× MH steps215k75.3—
Uncoupled ladder151k76.780.0
K=4K=4 independent chains at αK\alpha_K151k74.376.7
Best-of-N (N=10)154k72.878.7
PPT (K=4K=4)151k78.381.7

Table D. Compute-matched comparison on LCB v5, Qwen3-8B.

MethodTokensPass@1Norm. ML
Single chain (K=1K=1), ≈4× MH steps213k54.9—
Uncoupled ladder211k55.057.2
K=4K=4 independent chains at αK\alpha_K211k56.157.9
Best-of-N (N=38)213k49.658.6
PPT (K=4K=4)210k58.460.1

Tables C and D show that PPT is the most accurate method in every column on both benchmarks, and each baseline falls short for a different reason. Extra refinement of a single chain saturates: it receives the largest token budget of any method and still does not reach PPT, because a sharpened chain that has committed to a coherent but incorrect line of reasoning rejects almost every proposal that leaves it, so more steps polish the current mode instead of finding a better one.

Exploration without exchange never reaches the output: the uncoupled ladder has PPT's replicas, temperatures and budget, and its hot replicas explore exactly as PPT's do, but nothing they find is passed to the cold replica that is read out. Swaps are the only difference between the two methods, so this gap is the contribution of replica exchange. Likewise, KK independent power-sampling chains cannot share what they find. Finally, PPT's single unselected trace is already comparable to what the baselines reach after selecting among all of theirs, since exchange delivers the best of the exploration to one known place.

Best-of-N provides coverage and breadth but not a reliable Pass@1 answer: it recovers some accuracy only when it selects among its samples, as good traces are often present but cannot be identified in advance. On AIME, its highest-likelihood sample reaches only 72.8, and a majority vote over all samples still falls below PPT.

Therefore, we argue that PPT's performance gains are not an artifact of the cost, since at equal cost, neither more MH steps, nor more independent chains, nor more samples return a more accurate trace than parallel tempering.

AuthorsOpenReview ↗

Author response to all reviewers

Response to All Reviewers

We thank the reviewers for their valuable insights. We are glad they acknowledge the importance of our problem to improve the reasoning of small models at inference time and appreciated our theoretical contributions (Reviewers u8bF, zi5q) and experimental setting (Reviewers UgBW, u8bF). The main questions were (i) whether the gains come from replica exchange and persist under matched compute (u8bF, zi5q), (ii) the cost and tuning burden: token overhead, memory, and the choice of ladder and hyperparameters (UgBW, u8bF), and (iii) how to explain the improved performance empirically (UgBW, zi5q). We have uploaded a revised manuscript, which adds:

  1. Replica-exchange diagnostics (Sec. 4.1, App. H.2): cold-chain likelihood rank with and without swaps, round trips and replica lineages. With swaps, the output rung holds the highest-likelihood record in 89–98% of evaluations on Qwen3-8B, against 29–55%29–55\% without.
  2. Ladder sensitivity (Sec. 4.3). Three fixed ladders, applied unchanged to five benchmarks and two models, differ by at most 4 points on four of the five benchmarks. The failure mode is a coldest rung too sharp for long completions (AIME).
  3. Token overhead versus sequence length (App. H.4): a cost model and measured sweeps over the horizon, the number of proposals and the number of blocks.
  4. Longer refinement (Sec. 4.3). The step ablation now runs to 50 steps per block over 5 seeds.

Furthermore, we carefully addressed the questions and concerns raised by all reviewers. The individual responses add three further results. First, we extend our cost-matched comparison, on AIME 24&25 and LiveCodeBench v5 with Qwen3-8B, every baseline receives at least PPT's decode tokens. PPT's cold trace stays ahead of the uncoupled ladder, a single chain with more MH steps, KK independent chains and Best-of-N (Reviewer u8bF, zi5q). Then, we show that the initialization sequence does not determine how the sequence will be updated and where it will end (Reviewer zi5q). Additionally, we investigated whether setting the warmest rung with power below 1 showed no clear benefit in an initial test. Lastly, we provided pass@k results on AIME and LCB, which show that PPT is on par with Best-of-N, demonstrating that the sharper outputs do not cost coverage (Reviewer UgBW).

We hope the responses below and the revision resolve the reviewers' concerns.

We thank the reviewer for acknowledging our theoretical analysis, toy/ empirical experiments, and clarifications. We offer three perspectives to alleviate concerns regarding the inference cost:

  1. Convergence vs. practical gains. We agree that global convergence is hard to achieve at context lengths up to 1M tokens, however, PPT already delivers substantial gains under finite budgets without requiring full convergence.

  2. Commercial vs. Sovereign Frontier Intelligence. As discussed in The Commanding Heights [1], unlike commercial AI, sovereign frontier AI prioritizes maximum capability over financial returns; this is a domain where PPT's advantages become particularly valuable.

  3. Declining inference costs. Epoch AI [2] reports a ~47% quarterly decline in the cost of achieving a similar AI performance. Advances in MH power sampling [3] also suggest the potential for over 2× acceleration of PPT in budget-sensitive (commercial) settings.

[1] The Commanding Heights. https://commanding-heights.com/commanding-heights.pdf

[2] The Plunging Price of Thought. Epoch AI.

[3] PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.