Source-linked AI summary
Explore Broadly, Reason Sharply: Push Small Models toward the Frontier via Sampling
Panagiotis Theodoropoulos, Nan Jiang, Xintong Duan, Ali Hasan, Yuriy Nevmyvaka, Evangelos A. Theodorou, Wei Deng
TL;DR
Reward-guided post-training can require task-specific verifiers and costly parameter updates, while power-sharpened sampling must balance exploration with exploitation. This paper introduces Parallel Power Tempering (PPT), which couples replicas at different sharpening levels and corrects truncation bias. PPT is best or tied-best across 15 model–benchmark settings and performs comparably to frontier models with Qwen3.5-9B.
Problem
Power sharpening must balance exploring diverse reasoning trajectories against concentrating on high-likelihood responses, and reward-guided RL requires verifiers or reward models and costly parameter updates.
Source: §1 · p. 1, §3.1 · p. 4Method
PPT runs replicas at different sequence-level sharpening powers, couples them through swaps, and uses a fixed-horizon construction to preserve the sharpened target.
Source: §1 · p. 2, §3.2 · p. 5Results
PPT is best or tied-best in all 15 model–benchmark settings, outperforms GRPO without parameter updates or rewards, and performs comparably to frontier models with Qwen3.5-9B.
Source: §5 · p. 11Takeaways & Limitations
PPT's gains come from swaps rather than extra compute or chains, without requiring parameter updates or rewards.
Source: §5 · p. 11Naïve early-stopped suffix proposals can bias sampling toward shorter records; PPT addresses this with a fixed-horizon construction.
Source: §3.2 · p. 5
Abstract
from arXiv · showhide
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 \textbf{Parallel Power Tempering (PPT)}, instantiating power-sharpened LLM sampling via parallel tempering. Running multiple \emph{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 \method{} 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 \method{} 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.
1. Introduction
The introduction motivates inference-time reasoning improvements as an alternative to reward-guided post-training, then presents PPT as a way to balance exploration and exploitation. It reports broad benchmark gains, including performance comparable to frontier models with Qwen3.5-9B.
1. Introduction
- Reward-guided RL can improve reasoning on verifiable tasks, but requires a verifier or reward model and costly parameter updates.The introduction also notes that reliable rewards are often unavailable for open-ended inquiry, deliberation, and long-horizon planning.Source: §1 · pp. 1–2
- Existing selection and token-level reshaping methods do not generally sample from a prescribed sequence-level target.The introduction contrasts these approaches with sequence-level power sharpening.Source: §1 · p. 2
- Power sharpening creates an exploration–exploitation trade-off: strong sharpening can trap samplers in plausible but incorrect paths, while flatter distributions can produce noisy responses.The challenge is particularly consequential for multi-step reasoning, where an early mistake can yield a coherent but wrong solution.Source: §1 · p. 2
- PPT couples replicas at different sharpening levels so exploratory low-power chains can pass promising responses to exploitative high-power chains.The introduction describes adjacent swaps evaluated using cached base-model log-probabilities, requiring no additional model evaluations.Source: §1 · p. 2
- PPT outperforms sampling and RL baselines in nearly all settings and matches or exceeds frontier-model performance with Qwen3.5-9B.The paper reports these outcomes across mathematics, STEM, and code reasoning benchmarks.Source: Figure 1 · p. 1, §1 · p. 3
2. Preliminaries
The preliminaries define generated sequences and power-sharpened targets, then introduce Metropolis–Hastings and parallel tempering as sampling tools. Together, they set up sequence-level sampling and exchanges among replicas.
2.1. Notations
- At a fixed horizon, generated sequences include EOS-terminated records padded after termination, and the LLM assigns their probability autoregressively.Generation draws each token from the model conditioned on the prompt and preceding tokens.Source: §2.1 · p. 3
2.2. Power Sharpening for LLMs
- Power sharpening raises the base sequence distribution to α, suppressing low-likelihood continuations; MH sampling uses restart proposals to target this distribution.Direct autoregressive sampling is intractable because the target's normalizing constant sums over all possible future completions.Source: §2.2 · pp. 3–4
2.3. Parallel Tempering
- Parallel tempering runs replicas over auxiliary distributions and couples neighboring chains through proposed state swaps.The figure illustrates low-power exploration and high-power exploitation, with accepted swaps transferring a discovered high-probability state to the focused chain.Source: §2.3 · p. 4, Figure 2 · p. 4
3. Methodology
Parallel Power Tempering (PPT) addresses the exploration–exploitation trade-off by coupling replicas at different sharpening powers. A fixed-horizon construction also corrects one-way truncation bias in variable-length refinement.
3.1. Motivation: The Exploration Bottleneck
- Low-power replicas explore alternative reasoning paths, while swaps carry promising trajectories to sharper replicas that target higher-probability responses.The output rung retains its sharpened target marginal; its mixing advantage is conditional on auxiliary replicas having faster local kernels.Source: §3.1 · pp. 4–5, §3.3 · p. 6
3.2. Structural Truncation Bias and the Fixed-Horizon Correction
- Early-stopped suffix proposals can accept shortenings with no reverse move, creating one-way flow toward shorter records and preventing preservation of the true target.This truncation can also restrict exploration when shortened records move to lower-power rungs with less generation budget.Source: §3.2 · p. 5
- Fixed-horizon refinement pads post-EOS positions and regenerates suffixes through horizon T, removing structural truncation bias while preserving the sharpened target.The construction keeps early termination revisable; in the example, fixed-horizon refinement can return from a one-token record to a two-token record.Source: §3.2 · p. 5
3.3. Parallel Power Tempering
- PPT advances a shared horizon in blocks, extends open replicas, refines sampled suffixes, then exchanges adjacent records through sequential swaps.Local refinement and swaps preserve the stage target, and the ordered sweep can move a state across multiple rungs in one sweep.Source: §3.3 · p. 6
- Accepted swaps transport trajectories across the ladder, while cached sequence likelihoods let exchanges avoid additional model passes.The designated output rung has the sharpened target marginal; the mixing advantage depends on auxiliary local kernels being faster.Source: §3.3 · pp. 6–7
3.4. Ladder Design
- For fixed endpoint powers and replica count, an equi-accepting ladder equalizes adjacent swap acceptance, maximizing the weakest link.The authors initialize with a geometric ladder and empirically tune intermediate powers toward equal measured acceptances.Source: §3.4 · pp. 7–8
- Ordered ADJ needs half as many expected iterations as DEO, but its sequential communication favors few replicas; DEO scales better as replica count grows.ADJ’s sequential communication overhead grows quadratically with replica count, compared with DEO’s linear scaling.Source: §3.4 · p. 8
4. Experiments
PPT attains the best or tied-best accuracy in all 15 model–benchmark settings and remains ahead of compute-matched single-chain refinement and uncoupled replicas. Ablations show accuracy gains saturate around four to five replicas, while equi-accepting ladder spacing performs best among tested designs.
4.1. Main Results
- PPT achieves the best or tied-best accuracy in all 15 model–benchmark settings across mathematics, science, and code; its only tie is saturated GSM8K.The reported comparison also says PPT outperforms every sampling-based baseline and GRPO, without parameter updates or rewards.Source: §4.1 · p. 9, Table 2 · p. 9
- 1.03× and 1.72× single-chain local-update wall-clock time suffice for multi-replica Qwen3-8B and Qwen3.5-9B runs, while swaps take 0.1% of total time.Peak memory is approximately 3.73× and 2.47× the corresponding single-chain values.Source: §4.1 · p. 9, Table 3 · p. 9
4.2. Compute-matched Controls
- PPT remains more accurate than single-chain refinement at matched compute across four benchmarks, with LCB v5 at 58.4% versus 54.9% and AIME 24&25 at 78.3% versus 75.3%.The extended single chain matches PPT's total decode-token compute but does not close the performance gap.Source: §4.2 · pp. 9–10, Table 4 · p. 9
- Enabling swaps improves both Pass@1 and voting accuracy in every model–benchmark setting compared with an uncoupled ladder using the same number of chains.The reported gains are attributed to exchange, not merely running and aggregating more replicas.Source: §4.2 · p. 10, Table 5 · p. 10
4.3. Ablation Studies
- Accuracy saturates around four to five replicas: K=4 gains 2.7 and 3.9 percentage points, while K=5 peaks at +3.2 and +4.5 on MATH500 and HumanEval.With K=4, total cost is 2.1× and 1.2× single-chain cost on MATH500 and HumanEval, respectively.Source: §4.3 · p. 10, Figure 5 · p. 11
- Equi-accepting ladder spacing performs best on MATH500 and HumanEval among random, arithmetic, geometric, and equi-accepting designs.It approximately equalizes adjacent swap-acceptance rates to avoid a single communication bottleneck.Source: §4.3 · p. 10, Figure 5 · p. 11
5. Conclusion
The conclusion presents PPT as a way to address single-chain power sampling’s exploration–exploitation trade-off, with low-power replicas exploring and high-power replicas refining traces through swaps. The appendix formalizes fixed-horizon completion records and sequence-level power targets, which are distinct from tokenwise temperature decoding.
5. Conclusion
- PPT couples low-power exploration and high-power refinement through swaps, removes early-stopping truncation bias with a fixed-horizon construction, and is best or tied-best in all 15 model–benchmark settings.The conclusion reports performance comparable to frontier models with Qwen3.5-9B and gains attributed to swaps rather than extra compute or chains.Source: §5 · p. 11
A. Notation and Preliminaries
- The notation establishes prompt-conditioned completion records, a finite horizon, and the fixed-horizon representation used by the progressive sampler.Records terminate at the first configured terminal token and are padded through the horizon under the post-terminal convention.Source: A. Notation and Preliminaries · p. 17, §A.1 · p. 17
A.2. Sequence-level power target
- For sharpening power α≥1, the sequence-level power target is a probability distribution over fixed-horizon completions, with each replica assigned a target at its ladder power.The target is defined on a finite state space and has a finite, positive normalizer.Source: §A.2 · p. 18
A.3. Sequence-level powering is not tokenwise temperature decoding
- Sequence-level powering generally differs from tokenwise temperature decoding because its next-token conditional depends on possible continuations.The tractable tokenwise powered proposal omits the continuation factor and matches that conditional only when the factor is constant over supported next tokens.Source: §A.3 · pp. 18–19
B. Implementation Details
The implementation extends completion records blockwise, refines suffixes within each power rung, then swaps whole records between adjacent rungs. Batched execution and cached model state reduce per-round wall-clock costs without changing the local or swap kernels.
B. Implementation Details
- Joint batched block extensions and suffix resampling use continuous batching and KV-cache reuse to improve per-refinement-round wall-clock scaling until GPU saturation.Total generated tokens still grow with replica count; accepted swaps exchange records and caches without additional model evaluation.Source: B. Implementation Details · p. 19
B.1. Step 1: Block extension
- Blockwise extensions warm-start records at each enlarged horizon; subsequent finite refinement steps approximate the stage target.The terminal-stage target is the fixed-horizon target, and terminated records are extended deterministically through their post-terminal tails.Source: §B.1 · pp. 19–20
B.2. Step 2: Local refinement
- Local refinement retains a prefix and regenerates the suffix through the common horizon using a state-independent restart position.Applying the restart law over the full horizon avoids a state-dependent restart set and its additional acceptance-ratio factor; a restart after termination is a self-transition.Source: §B.2 · p. 20
B.3. Step 3: Swap exchange
- Adjacent-rung swaps exchange complete records, with the log acceptance ratio determined by the power gap and the records’ base-model log probabilities.An ordered sweep applies successive adjacent exchanges in increasing order, and accepted swaps move aligned caches with the records.Source: §B.3 · p. 21
B.4. Putting the implementation together
The implementation advances replicas through progressive horizons, applies local refinement and adjacent exchange sweeps, then returns a designated rung. The theoretical section identifies bias from one-way truncating updates and establishes target preservation for fixed-horizon updates, with convergence under supported full restarts.
B.4. Putting the implementation together
- After each stage extends records to its horizon, the sampler repeats local-update rounds and ordered adjacent exchange sweeps, then returns the predesignated rung.The returned completion ends at its first configured terminal token or at the horizon if no terminal occurs.Source: §B.4 · p. 21, §C.1 · p. 22
C. Theoretical Properties: Bias and Exactness of PPT
- One-way truncating local updates create structural bias in the ensemble and returned rung; fixed-horizon MH updates preserve the true target and converge asymptotically under supported full restarts.The section establishes these properties for kernels after the stage horizon is fixed.Source: C. Theoretical Properties: Bias and… · p. 21
C.1. Fixed-horizon targets and PPT kernels
- At a fixed horizon, local refinement retains a prefix and regenerates the suffix through the common endpoint, while adjacent replica-exchange kernels swap neighboring records.Restart probabilities are state-independent, and a synchronized local sweep updates the rungs conditionally independently.Source: §C.1 · pp. 21, 23
- An ordered adjacent sweep composes neighboring swap kernels sequentially, and a refinement round composes local sweeps with the configured exchange sweeps.The horizon, targets, restart probabilities, and schedule remain fixed during rounds; block extension initializes the state but is not part of the fixed-horizon transition kernel.Source: §C.1 · p. 23
C.2. Structural bias from one-way truncation in PPT
One-way truncation can break target preservation: accepted shortenings lose reverse proposal support, and swaps cannot restore the lost probability flow. Under a uniform accepted-entry condition, this bias yields asymptotic error floors for the ensemble and returned rungs.
C.2. Structural bias from one-way truncation in PPT
- Accepted shortening moves can have zero reverse-proposal probability, causing one-way probability leakage from longer records to shorter ones that swaps cannot undo.Under the intended target, positive shortening flow is sufficient to violate invariance; a uniform shortening probability is not required.Source: §C.2 · pp. 24–25
- Transient shortening crossings alone do not establish target bias; positive shortening flow under the target is sufficient to violate invariance.Crossings observed under a transient law estimate its own crossing probability, not the target flow.Source: §C.2 · p. 25
- Under a uniform accepted-entry probability δ, repeated shortening drives long records out, yielding asymptotic TV lower bounds for the ensemble and each rung.The bounds depend on excluded target masses b_k, while δ controls how quickly the floors are approached.Source: §C.2 · pp. 25–26
C.3. Target preservation and convergence of fixed-horizon PPT
Fixed-horizon refinement uses a common state space for proposals in both directions, preserving the intended target. Supported full restarts ensure convergence, although the guarantee is asymptotic and may not imply small error at practical budgets.
C.3. Target preservation and convergence of fixed-horizon PPT
- A common fixed horizon with deterministic padding lets proposals revise early termination and preserves the intended targets under Metropolis–Hastings acceptance.The fixed-position kernels, local sweep, swaps, and complete PPT kernel preserve the joint target Π.Source: §C.3 · p. 26
- Supported full restarts make Π the unique invariant law and guarantee convergence from any initializer.The full-restart component contracts total-variation error by at most a factor of 1−ε per local refinement step.Source: §C.3 · pp. 27–28
- The convergence guarantee is asymptotic, not a certificate of small error at practical refinement budgets.Its worst-case coefficient ε can be very small, including because uniform restart selection contributes a factor T−K.Source: §C.3 · p. 28
C.4. A finite illustration of target preservation and one-way truncation bias
A four-state example contrasts target-preserving fixed-horizon refinement with current-length truncation, then introduces thermodynamic distance as a local scale for swap acceptance. The ladder analysis assumes equilibrium draws and uses a Gaussian approximation only for finite-gap predictions.
C.4. A finite illustration of target preservation and one-way truncation bias
- The unbalanced TV error falls initially, reaches its minimum 37/128 at N=4, then rises toward 1/2; fixed refinement preserves π and its law converges to π.At N=2, the unbalanced TV error is 17/48, compared with 25/96 for the corrected error.Source: §C.4 · p. 29
D. Power-Ladder Design
- The power-ladder design studies expected swap acceptance at equilibrium with independent draws from adjacent sequence-level power targets.It fixes the number of replicas and endpoint powers; the sequence energy is U(x) := −log p0(x | x0).Source: D. Power-Ladder Design · p. 30
D.1. Thermodynamic coordinate and exact swap overlap
- For nearby powers, thermodynamic distance sets the local scale of the swap log ratio’s mean and variance, without implying a Gaussian shape.The expansions give E[G] = −d^2 + O(δ^3) and Var(G) = 2d^2 + O(δ^3); Gaussianity is an additional finite-gap approximation.Source: §D.1 · p. 31
D.2. Max–min design and the unique equi-accepting ladder
The design analysis chooses a unique equal-thermodynamic-gap ladder for a Gaussian max–min acceptance objective, while communication-schedule efficiency depends on timing. The remaining sections situate PPT among inference-time methods and specify experimental baselines and datasets.
D.2. Max–min design and the unique equi-accepting ladder
- For varying sequence energy, the Gaussian-surrogate max–min objective uniquely places rungs at equal thermodynamic gaps, equalizing predicted adjacent acceptance.When energy is constant, every power target is identical and every feasible ladder is optimal; arithmetic and geometric templates correspond to idealized variance curves.Source: §D.2 · pp. 31–32
E. Chain Communication Protocol
- Both ordered ADJ and deterministic even–odd swaps preserve the target; under the stated timing assumptions, DEO becomes preferable when d_ADJ > 2d_DEO.As K grows, the ordered sweep’s Θ(K^2(1 + R)) scaling dominates under those assumptions.Source: E. Chain Communication Protocol · pp. 32–33
F. Extended Related Work
- PPT adapts replica exchange to couple different sharpening powers over a common completion horizon, exchanging whole records using cached likelihoods without extra model evaluations.This contrasts with a prior LLM replica-exchange method that uses prefix-length-indexed targets and token-chunk exchanges.Source: F. Extended Related Work · p. 35
G.1. Choice of Baselines
- The baseline suite includes standard and low-temperature decoding, Power Sampling, PowerSMC, and GRPO, with comparator hyperparameters tuned independently by model.Power Sampling’s released implementation retains early stopping; GRPO is the training-based reference requiring a verifiable reward signal.Source: §G.1 · p. 35
G.2. Choice of Datasets
- Evaluation datasets span competition mathematics, coding, science questions, grade-school arithmetic, olympiad mathematics, and contamination-aware competitive programming.The listed sets are MATH500, HumanEval, GPQA Diamond, GSM8K, AIME 24&25, and LCB v5.Source: §G.2 · p. 36
G.3. Evaluation Metrics
The evaluation reports task-specific pass@1 scores and uses trace diagnostics to characterize likelihood and confidence. The configuration specifies the evaluated models, generation horizons, and sampler settings.
G.3. Evaluation Metrics
- Task accuracy is strict pass@1: each benchmark item receives one completion, scored by exact-answer matching or the specified equivalence grader.No method uses reward- or verifier-based reranking or oracle filtering.Source: §G.3 · p. 36
- HumanEval and LiveCodeBench v5 use execution-based pass@1, requiring successful execution and passage of every associated unit test.Invalid programs, runtime errors, and timeouts receive zero credit.Source: §G.3 · p. 36
- Trace diagnostics include average base-model token log-likelihood and mean negative next-token entropy, with values closer to zero indicating greater confidence.Scores are averaged over generated positions per completion, then across benchmark items.Source: §G.3 · p. 36
G.4. Configuration
- Evaluation covers 3.8B–9B base, instruction-tuned, and GRPO-trained checkpoints; no additional training is performed.For Qwen3, horizons range from T=3072 on GSM8K to T=32768 on AIME 24&25; Qwen3.5 uses T=131072 on GPQA and LCB v5 and T=65536 on AIME 24&25.Source: §G.4 · p. 37
- PowerSMC resamples systematically when effective sample size falls below 0.5N, then selects one final particle according to normalized weights.Particles are internal sampler states, not additional evaluation completions.Source: §G.4 · p. 37
- PPT returns replica K at target power α★ and performs one ordered adjacent sweep after each synchronized local-MH round.Local proposals restart uniformly within the block and regenerate the suffix using temperature τ_k=1/α_k.Source: §G.4 · p. 37
H.1. Extended Main Results
PPT attains the best or tied-best performance in most reported model-and-task settings, with its clearest advantages on difficult Qwen3 tasks. Its returned traces also concentrate in higher-plausibility regions, although those diagnostics do not establish correctness.
H.1. Extended Main Results
- PPT concentrates more trace scores near zero and suppresses the diffuse low-score tail seen most clearly under standard decoding.These internal-preference diagnostics support the concentration mechanism but do not establish correctness or calibration.Source: §H.1 · pp. 38, 40
- PPT is best or tied-best in the large majority of settings, with largest baseline margins of 5.0 points on AIME 24&25 for Qwen3-4B and 4.3 points on LCB v5 for Qwen3-8B.Results from other model families are more mixed, and PPT remains competitive on near-saturated tasks.Source: §H.1 · p. 38, Table 8 · p. 39
- Swap acceptance varies by model and task; Qwen3 accepts 0.18–0.37 of swaps versus 0.35–0.58 for other models.Both ranges fall within the passage’s cited classical recommendation of roughly 0.15–0.6; denser ladders could raise acceptance at the cost of more replicas.Source: §H.1 · p. 38, Table 9 · p. 40
H.2. Ablation Studies
The ablations examine refinement effort, compute-matched controls, termination handling, and swap schedules. They report benefits from interacting replicas and fixed-horizon refinement, with the ordered adjacent sweep outperforming the tested alternative under equal iteration budgets.
H.2. Ablation Studies
- At 4 refinement steps, accuracy gains are +3.0 on MATH500 and +4.1 on HumanEval; at 10 steps, the best gains are +4.4 and +6.6, respectively.Gains are not monotone in N_MCMC, and local updates dominate runtime, making refinement the main accuracy–cost trade-off.Source: §H.2 · p. 40
- Compute-matched comparisons cover a single chain with more refinement, uncoupled replicas, and independent base-model samples.Taken together, these controls report that PPT’s benefit holds across all three ways of spending matched compute.Source: §H.2 · pp. 40–41
- PPT’s single-trace records outperform uncoupled-ladder and Best-of-N traces at the same compute, and PPT is strongest in every reported setting.Against the uncoupled ladder, exchange improves single-trace and vote accuracy in every model–benchmark setting; compute-matched controls also favor PPT over deeper refinement of one chain.Source: §H.2 · pp. 40–41
- Fixed-horizon refinement improves accuracy over truncation with exchange disabled, and enabling exchange improves accuracy further.Fixed-horizon suffix moves can revise EOS earlier or later; the table reports Pass@1 accuracy and hit-capacity rate on MATH500.Source: §H.2 · p. 41, Table 12 · p. 42
- The fixed-horizon correction lowers hit-capacity rates from 9.2% to 8.0% on Qwen3-4B and from 12.2% to 9.5% on Qwen3-8B.Adding exchange leaves the hit-capacity rates essentially unchanged at 7.6% and 9.6%, respectively, while improving accuracy further.Source: §H.2 · p. 42
- ADJ achieves higher single-sample accuracy than DEO across all evaluated models and benchmarks under the same finite iteration budget.The comparison uses otherwise identical configurations.Source: §H.2 · p. 42, Table 13 · p. 42