Power-SMC: Low-Latency Sequence-Level Power Sampling for Training-Free LLM Reasoning

Seyedarmin Azizi; Erfan Baghaei Potraghloo; Minoo Ahmadi; Souvik Kundu; Massoud Pedram

Source-linked AI summary

Power-SMC: Low-Latency Sequence-Level Power Sampling for Training-Free LLM Reasoning

Seyedarmin Azizi, Erfan Baghaei Potraghloo, Minoo Ahmadi, Souvik Kundu, Massoud Pedram

arXiv:2602.10273v2Feb 10, 2026stat.MLcs.LG

TL;DR

Prior MH sampling from sequence-level power distributions improves reasoning but incurs substantial inference overhead. Power-SMC targets the same objective with batch-parallel particle sampling, matching or exceeding MH on MATH500 while reducing latency toward baseline decoding.

Problem
Metropolis–Hastings sampling from sequence-level power distributions can improve reasoning but incurs order-of-magnitude inference slowdowns.
Method
Power-SMC uses a Feynman–Kac prefix flow with token-level importance correction, ESS-triggered resampling, and exact exponent bridging to target the sequence-level power distribution.
Results
Power-SMC matches or exceeds MH power sampling on MATH500 while reducing latency from 16–28× to 1.4–3.3× relative to baseline decoding.
Takeaways & Limitations
Temperature τ = 1/α is the unique locally variance-minimizing prefix-only proposal, while residual weight dispersion reflects variation across sampled prefix paths.

Abstract

from arXiv · show

Many recent reasoning gains in large language models can be explained as distribution sharpening: biasing generation toward high-likelihood trajectories already supported by the pretrained model, rather than modifying its weights. A natural formalization is the sequence-level power distribution $π_α(y\mid x)\propto p_θ(y\mid x)^α$ ($α>1$), which concentrates mass on whole sequences instead of adjusting token-level temperature. Prior work shows that Metropolis--Hastings (MH) sampling from this distribution recovers strong reasoning performance, but at order-of-magnitude inference slowdowns. We introduce Power-SMC, a training-free Sequential Monte Carlo scheme that targets the same objective while remaining close to standard decoding latency. Power-SMC advances a small particle set in parallel, corrects importance weights token-by-token, and resamples when necessary, all within a single GPU-friendly batched decode. We prove that temperature $τ=1/α$ is the unique prefix-only proposal minimizing incremental weight variance, interpret residual instability via prefix-conditioned Rényi entropies, and introduce an exponent-bridging schedule that improves particle stability without altering the target. On MATH500, Power-SMC matches or exceeds MH power sampling while reducing latency from $16$--$28\times$ to $1.4$--$3.3\times$ over baseline decoding. The code is available at https://github.com/ArminAzizi98/Power-SMC.

1 INTRODUCTION

Power-SMC targets sequence-level power sampling with a batch-parallel particle method designed to avoid MH’s serial inference bottleneck. It combines exact sequential correction, adaptive resampling, theoretical proposal optimality, and latency gains over MH.

Motivation: MH power sampling faces serial accept/reject decisions and repeated suffix regeneration, creating a practical latency bottleneck for LLM inference.These costs can dominate wall-clock time despite standard Transformer KV caching.
Power-SMC algorithm: Power-SMC applies Sequential Monte Carlo to sequence-level power sampling, maintaining parallel candidate continuations with token-level weight updates and selective resampling.Particles with uneven weights are resampled by duplicating high-weight candidates and discarding low-weight ones.
Power-SMC algorithm: The method uses exact sequential importance corrections and ESS-triggered resampling, with cache-safe KV-cache reindexing and α-ramping that preserves the final target.The exponent-bridging schedule is intended to improve particle stability without changing the target distribution.
Theoretical analysis: τ = 1/α is the unique prefix-measurable proposal minimizing conditional variance of incremental importance weights.Residual path-wise dispersion is interpreted through prefix-conditioned Rényi entropies.
Empirical gains: 16–28× to 1.4–3.3×: on MATH500 across three models, Power-SMC matches or exceeds MH power sampling while reducing latency relative to baseline decoding.The comparison is reported as inference latency overhead over baseline decoding.

2 RELATED WORK

Prior power-sampling methods either incur sequential MH costs or approximate future-dependent conditionals with rollouts. Power-SMC instead uses prefix-only proposals, exact importance correction, and batch-parallel particle decoding.

Power sampling and MCMC: MH power sampling targets the correct sequence-level stationary distribution but can be expensive because proposals regenerate long suffixes and the chain is inherently sequential.Its accept/reject loop creates serial dependencies during inference.
Token-level approximations: Scalable Power Sampling approximates future-dependent power conditionals with Monte Carlo rollouts and, in practice, restricts candidate tokens for efficiency.Its lookahead-based approximation introduces a different computational trade-off from prefix-only sampling.
Token-level approximations: Power-SMC restricts proposals to current-prefix information, proves τ = 1/α uniquely minimizes incremental-weight variance in that class, and corrects globally through sequential weighting and resampling.It avoids per-token lookahead estimation while retaining an exact sequential correction.
Sequential Monte Carlo: SMC adapts weighted-particle evolution and resampling to autoregressive Transformer decoding, requiring correct reordering of cached model states across particles.KV-cache handling is a practical systems requirement for particle resampling.
Decoding heuristics: Unlike local temperature, top-k, and nucleus rules, Power-SMC is designed to target a global sequence-level power objective.The paper positions temperature as part of a globally correcting algorithm rather than as a standalone exact sampler.

3 BACKGROUND

The background distinguishes sequence-level power distributions from token-level temperature sampling and motivates SMC as an incremental importance-sampling solution for long sequences.

Power distributions: The sequence-level power distribution sharpens the pretrained model by exponentiating whole-sequence probabilities for α ≥ 1.This concentrates probability on higher-likelihood sequences without changing model parameters.
Temperature versus sequence-level power: Token-level temperature sampling generally differs from the sequence-level power target because independently exponentiating conditionals is not equivalent to exponentiating the joint sequence probability.Power-SMC addresses this mismatch with token proposals plus exact sequential importance corrections.
Importance sampling: Importance sampling estimates target expectations by weighting samples from a proposal distribution, but its all-at-once application to long sequences produces highly variable weights.Sequential Monte Carlo applies the correction incrementally along the sequence.
Sequential Monte Carlo: SMC evolves N weighted particles token by token, multiplies weights by incremental corrections, and resamples when weights become too uneven.Effective sample size is the standard diagnostic for weight collapse.

4 POWER-SMC: SAMPLING πα WITH A SINGLE BATCHED DECODE

Power-SMC constructs a prefix-level Feynman–Kac flow for the sequence-level power target and uses arbitrary prefix-only token proposals with exact incremental corrections. Batched decoding and ESS-triggered resampling maintain a weighted particle approximation through completion.

Prefix flow for the power target: Power-SMC defines intermediate unnormalized and normalized targets over prefixes, forming a Feynman–Kac flow whose completed-sequence distribution matches the desired power target.EOS is treated as an ordinary token with an absorbing terminated state.
Token proposal and incremental correction: A prefix-only proposal q_t(· | x, y_<t) is corrected by an incremental importance weight that compensates for using it instead of the generally intractable power conditional.The correction is exact for the chosen proposal.
Batched particle decoding: The algorithm decodes N sequences in parallel, updates particle weights after each token, resamples at low effective sample size, and samples the output from the final weighted particle set.This procedure is compatible with batched Transformer decoding.

5 LOCAL OPTIMALITY OF τ = 1/α AND A R´ENYI-ENTROPY VIEW

For prefix-only proposals, τ = 1/α uniquely minimizes incremental-weight variance, but path-dependent prefix uncertainty still causes weight dispersion; exponent bridging addresses that residual instability without changing the target.

Particle stability: SMC resamples when effective sample size falls below a threshold, duplicating high-weight particles and discarding low-weight ones.This controls weight imbalance during parallel particle evolution.
Local optimality: τ = 1/α is the unique prefix-only proposal minimizing the conditional variance of incremental importance weights.It removes variance attributable to the sampled token, leaving prefix-path variation as the remaining source.
Local optimality: Under the locally optimal proposal, incremental weights depend on the current prefix but not on the sampled token.This makes the correction deterministic conditional on the prefix.
Rényi-entropy interpretation: Prefix-conditioned Rényi entropy explains residual dispersion: particles encountering higher next-token uncertainty accumulate lower weights.More confident prefix paths receive higher weights, consistent with the sharpening objective.
Exact exponent bridging: Exponent bridging transitions through increasing exponents from 1 to α while preserving the final target distribution.The schedule is introduced to mitigate path-level weight divergence, with locally optimal temperature τℓ = 1/α(ℓ) within each stage.

6 COMPUTE AND LATENCY COST ANALYSIS: MH VS. SMC/SIR

The cost model attributes MH’s latency to serial suffix regeneration, whereas Power-SMC advances all particles in parallel under KV caching; the resulting advantage depends on edit regime and batch throughput.

Power-SMC cost: Power-SMC with N particles and horizon T performs CSMC = N · T token-evals, with wall-clock time proportional to T · N/s(N).Weight updates and resampling remain O(N) per step and do not change the leading cost term.
MH cost regimes: Global-edit MH has E[Lk] ≈ kB/2 and E[CMH] ≈ T + MBK(K+1)/4, which is Θ(T^2/B) for fixed B.The expected regenerated suffix grows with the prefix length under uniform global edits.
MH cost regimes: Last-block MH has E[Lk] ≈ B/2 and E[CMH] ≈ T(1 + M/2).Restricting edits to the most recent block removes the global-edit growth with k but retains repeated suffix overhead.
Latency implications: MH’s overhead relative to baseline decoding satisfies ρMH ≳ 1 + M/2, giving ρMH ≳ 6 for M = 10 even under a perfect inference engine.This is an overhead floor for the last-block edit regime.
Latency implications: For N = 48, M = 10, and K = 16, global-edit MH has compute factor 43.5 and E[CMH]/CSMC ≈ 0.91.Power-SMC can nevertheless be wall-clock favorable when batch throughput s(48) is large because its additional compute is parallelized.

7 EXPERIMENTS

On MATH500, Power-SMC is evaluated against baseline, low-temperature, MH, and rollout-based sampling, achieving strong accuracy with latency close to baseline on the Qwen models.

Evaluation setup: Power-SMC is compared with baseline decoding, τ = 1/α decoding, MH power sampling, Scalable Power Sampling, and end-to-end latency on identical hardware.The evaluation uses the Hugging Face stack and reports accuracy–latency trade-offs.
Evaluation setup: Power-SMC uses N = 64 particles, α = 4, Tmax = 2048, and ESS-triggered resampling at κ = 0.5.An optional linear α-ramping schedule is applied over the first 100 tokens.
Results: Power-SMC achieves the best pass@1 among training-free samplers across all three models while remaining at 1.44–1.64× baseline latency on the two Qwen models.Latency is measured end-to-end under the stated evaluation stack and hardware.

8 CONCLUSION

Power-SMC is a low-latency particle sampler for sequence-level power distributions that combines theoretical guarantees with practical decoding mechanisms. On MATH500, it matches or exceeds MH power sampling while substantially reducing inference latency.

Power-SMC targets the sequence-level power distribution with a low-latency particle-sampling approach.
Power-SMC proves that τ = 1/α is the unique locally variance-minimizing prefix-only proposal and interprets residual weight dispersion through Rényi entropy.
Power-SMC combines exact α-ramping schedules, cache-safe Transformer resampling, and engine-independent compute and latency comparisons.
On MATH500, Power-SMC matches or exceeds MH power sampling while reducing inference latency from order-of-magnitude overheads to modest increases.

A PROOF OF THEOREM 1 AND COROLLARY 1

The proof minimizes the incremental importance-weight variance over valid prefix-only proposals. The optimizer is the powered token distribution, which corresponds exactly to temperature τ = 1/α and yields zero conditional variance.

For a sampled token v, the incremental importance weight is ω(v) = p(v)^α/q(v).
The conditional mean of the incremental weight is invariant to the proposal q, so minimizing variance reduces to minimizing its second moment.
The constrained optimization uses proposal probabilities summing to one and requiring q(v) > 0 wherever p(v) > 0.
The resulting optimizer is unique, and substituting it makes every incremental weight equal to Z(α; y<t).
The powered proposal q⋆_t(v) ∝ p_t(v)^α equals softmax(αℓ_t), which is temperature sampling with τ = 1/α.

B EXACT EXPONENT-BRIDGING (α-RAMPING)

Exact exponent-bridging introduces intermediate power exponents before reaching the final target. Its cumulative reweighting is algebraically identical to direct targeting while improving particle stability.

Exponent bridging uses a schedule from α(0) = 1 through increasing intermediate exponents to α(L) = α.
Within each stage, the incremental importance weight replaces the final exponent with the current α(ℓ).
At selected token boundaries, log weights are updated by (α(ℓ) − α(ℓ−1)) times the prefix log-likelihood.
The product of stage-wise corrections equals pθ(y | x)^(α−1), so α-ramping preserves the final target while improving particle stability.

C SYSTEMS: CACHE-SAFE RESAMPLING FOR TRANSFORMER DECODING

Power-SMC resampling must preserve particle ancestry by reindexing each particle’s Transformer state, especially its KV cache. The implementation uses systematic resampling and supports terminated particles through absorbing EOS states.

Resampling duplicates high-weight particles and therefore requires copying their model states through particle ancestry reindexing.
For autoregressive Transformers, the dominant particle state is the KV cache storing attention keys and values for each prefix.
EOS is treated as an absorbing state, with subsequent no-op transitions, forced EOS proposals, and skipped cache updates.
Systematic resampling is unbiased and typically lower-variance than multinomial resampling, while other unbiased schemes preserve the target distribution.