betaFeedback

WorksComputer Science

Free Lunch Uncertainty: Sequence-Level Rényi Entropy from Particle Decoding for Adaptive LLM Reasoning

Abstract

Quantifying uncertainty over an entire LLM completion is critical for selective prediction and adaptive compute. Zero-cost signals such as mean token entropy and log-probability are local to tokens or to one completion, and self-consistency needs many extra completions. We show that Sequential Monte Carlo (SMC) decoding for power sampling already estimates the normalizing constant of the power distribution, which gives the sequence-level R'enyi entropy (SRE) of the model's completion distribution at zero marginal cost, with a guarantee at every particle budget. A R'enyi chain rule extends this readout to a family of stepwise entropies of any order. We prove that orders above one are tied to the most likely token of each step, which explains why they track log-probability, while the order-1/2 member accumulates the log of per-step search effort. This member is the best zero-cost selective-prediction signal in 10 of 13 settings. On MATH500 its AUROC is 0.022 to 0.044 above log-probability with all four models and within length quartiles, and the same order is selected when each setting is held out. An 8-particle probe identifies the problems that benefit from more particles, and a two-pass policy matches 64-particle accuracy on MATH500 with 34.2% fewer particles over three seeds.

Introduction

Recent work suggests that reinforcement learning primarily surfaces capabilities already present in the base model’s distribution, raising the probability of correct answers rather than teaching new reasoning skills ([26]). This insight has motivated training-free alternatives that sharpen the model’s distribution ([17, 2, 13]). One such approach is power sampling: drawing completions yy for a prompt xx from a power distribution

Figure 1. Overview of adaptive particle allocation using SRE. SMC importance weights from an initial low-budget probe run are used to estimate the normalizing constant Zα(x)Z_\alpha(x) and from it the sequence-level Rényi entropy. High-SRE problems are re-run with a larger particle budget (N=64N = 64), while low-SRE problems keep the probe answer.

πα(y∣x)∝pθ(y∣x)α\pi_\alpha(y|x) \propto p_\theta(y|x)^\alpha, where pθp_\theta is the language model and the sharpening exponent α>1\alpha> 1 concentrates probability mass on higher-likelihood completions.

Power-SMC ([2]) and related methods ([21]) implement power sampling with Sequential Monte Carlo (SMC), maintaining NN parallel candidate completions (called particles in the SMC literature) that are extended token by token, reweighted by importance weights, and resampled. These methods perform well on reasoning tasks but use a fixed particle budget NN for every problem, regardless of difficulty.

A complementary challenge is uncertainty quantification: knowing when the model’s answer should be trusted.

Uncertainty matters for selective prediction, calibration-aware deployment, adaptive compute allocation, and routing hard problems to stronger systems ([15]). For reasoning tasks, uncertainty is naturally a property of the full completion distribution. A model may be locally uncertain at a few tokens but follow one stable reasoning plan, or it may assign comparable probability to several incompatible solutions.

Existing uncertainty signals miss part of this structure. Mean token entropy is zero-cost but measures local next-token ambiguity rather than uncertainty over whole completions [18]. Sequence log-probability scores only the returned completion and cannot distinguish a single dominant completion from one high-probability completion among several competing alternatives. Self-consistency [24] and semantic entropy [18, 9] capture answer-level disagreement but require KK independent completions.

We make a simple observation: the SMC importance weights already give an estimate of the normalizing constant Zα(x)=∑ypθ(y∣x)αZ_\alpha(x) = \sum_y p_\theta(y|x)^\alpha, which defines the sequence-level Rényi entropy of the completion distribution (Rényi entropy generalizes Shannon entropy). We call the resulting entropy estimate SRE. When an SMC sampler is already running, this estimate gives a zero-marginal-cost uncertainty signal with no extra completions, classifiers, reward models, or model calls.

Beyond uncertainty quantification, SRESRE enables adaptive particle allocation. A cheap probe run with N=8N=8 particles estimates SRESRE per problem and predicts whether more particles will improve the answer. The probe supplies both the signal and a candidate answer, so the allocation decision requires no additional model call. Figure 1 gives an overview.

Our contributions.

  1. We identify the SMC normalizing-constant estimate as a sequence-level Rényi entropy signal for LLM reasoning, with an upward-bias and finite-NN guarantee that covers the sampler as run (Lemma 1). The readout costs one scalar accumulation per decoding step, leaves the sampler unchanged, and applies to every SMC sampler whose final target is πα\pi_\alpha (§4).

  1. We use the Rényi chain rule (Proposition 1) to extend the readout to a family of stepwise entropies of any order and characterize the family (Proposition 3). Each member accumulates the negative log of a power mean of the probability that the model gives to its own next token; members of order β\beta above one are tied to the top token within a factor β/(β−1)\beta/(\beta- 1); and the order-1/2 member accumulates the log of the per-step search effort of Proposition 2.

  1. We show that the order-1/2 member alone is the best zero-cost selective-prediction signal in 10 of 13 settings spanning four models, two benchmarks, and six sharpening exponents (§5.2, §5.5). Its area under the ROC curve (AUROC) is 0.022 to 0.044 above that of log-probability on MATH500 with all four models (p≤0.029p \le0.029 after Holm correction). The margin holds within length quartiles and with the order selected on held-out settings, and the order-1/2 member is also above a generation-length baseline (§5.4, §5.7).

  1. We show that SRESRE from a cheap N=8N=8 probe predicts the gain from additional particles (§5.3). Across three seeds and two models, the low-SRESRE tercile gains at most 0.6 points from N=64N=64 while the upper two terciles together gain 1.2 to 4.8 points, a pattern that an independent N=8N=8 re-draw does not reproduce. With Qwen2.5-Math-7B a two-pass policy matches uniform N=64N=64 accuracy on MATH500 with 34.2% fewer particles on average over three seeds (§5.6).

Background

Power-SMC

Given a prompt xx, an autoregressive language model defines pθ(y∣x)=∏t=1Tpθ(yt∣x,y<t)p_\theta(y|x) = \prod_{t=1}^{T} p_\theta(y_t \mid x,y_{<t}) over completions yy of length TT that end with the end-of-sequence (EOS) token. Power sampling draws completions from the power distribution

πα(y∣x)=pθ(y∣x)αZα(x),Zα(x)=∑ypθ(y∣x)α,(1)\pi_\alpha(y|x) = \frac{p_\theta(y|x)^\alpha}{Z_\alpha(x)}, \qquad Z_\alpha(x) = \sum_y p_\theta(y|x)^\alpha, \tag*{(1)}

where α>1\alpha> 1 is the sharpening exponent.

Power-SMC [2] maintains NN particles and samples each token from a proposal distribution: the locally optimal choice qt∗(v)∝pθ(v∣x,y<t(i))αq_t^*(v) \propto p_\theta(v|x,y_{<t}^{(i)})^\alpha, which corresponds to sampling at temperature τ=1/α\tau=1/\alpha and minimizes the variance of the incremental weight below. Under this proposal, the incremental importance weight (incremental weight for short) for particle ii at step tt is

ωt(i)=∑vpθ(v∣x,y<t(i))α,(2)\omega_t^{(i)} = \sum_v p_\theta(v|x,y_{<t}^{(i)})^\alpha, \tag*{(2)}

which is deterministic given the prefix [2]. When the effective sample size (ESS, a measure of how many particles carry non-negligible weight) drops below a threshold, Power-SMC performs systematic resampling: duplicating highweight particles and discarding low-weight ones to prevent weight collapse onto a few particles.

Rényi entropy

The Rényi entropy of order α\alpha of the full completion distribution pθ(⋅∣x)p_\theta(\cdot|x) is

Hα(pθ(⋅∣x))=11−αlog⁡∑ypθ(y∣x)α⏟Zα(x).(3)H_\alpha(p_\theta(\cdot|x)) = \frac{1}{1-\alpha}\log\underbrace{\sum_y p_\theta(y|x)^\alpha}_{Z_\alpha(x)}. \tag*{(3)}

For α>1\alpha> 1, HαH_\alpha is low when probability mass concentrates on a few completions and high when mass spreads across many. As α→1\alpha\to1, HαH_\alpha converges to the Shannon entropy.

Motivating Analysis

Analysis 1: Sequence-level entropy is a sum, not a mean

Mean token entropy, 1T∑tH(Yt∣Y<t,x)\frac{1}{T}\sum_t H(Y_t \mid Y_{<t},x) along a generated completion, is a common zero-cost signal of predictive uncertainty in language models ([20]). The entropy of the completion distribution is not an average of next-token entropies. For Shannon entropy the chain rule gives H(Y1:T∣x)=∑t=1TEy<t∼pθ[H(Yt∣y<t,x)]H(Y_{1:T} \mid x) = \sum_{t=1}^{T}\mathbb{E}_{y_{<t}\sim p_\theta}[H(Y_t\mid y_{<t},x)], a sum over steps ([5, 20]). Rényi entropy obeys an analogous rule ([14]). Let πβ(t)(y1:t)∝pθ(y1:t∣x)β\pi_\beta^{(t)}(y_{1:t}) \propto p_\theta(y_{1:t}|x)^\beta be the order-β\beta power distribution over length-tt prefixes and hβ(y<t)=11−βlog⁡∑vpθ(v∣x,y<t)βh_\beta(y_{<t}) = \frac{1}{1-\beta}\log\sum_v p_\theta(v|x,y_{<t})^\beta the Rényi entropy of the next-token distribution.

Proposition 1 (Rényi chain rule). For β>0\beta> 0, β≠1\beta\ne1, and prefixes Y<t∼πβ(t−1)Y_{<t}\sim\pi_\beta^{(t-1)},

Hβ(pθ)=∑t=1T11−βlog⁡E[e(1−β)hβ(Y<t)],H_\beta(p_\theta)=\sum_{t=1}^{T}\frac{1}{1-\beta}\log\mathbb{E}\left[e^{(1-\beta)h_\beta(Y_{<t})}\right],

where Hβ(pθ)H_\beta(p_\theta) abbreviates Hβ(pθ(⋅∣x))H_\beta(p_\theta(\cdot|x)), and the right-hand side converges to the right-hand side of the Shannon chain rule as β→1\beta\to1.

The proof is in Appendix § 20. Sequence-level entropy is therefore a sum of per-step increments, each an aggregate of next-token entropies over prefixes. Dividing by the length, as mean token entropy does, removes the accumulation that separates a long uncertain completion from a short one, and following a single completion ignores the expectation over prefixes.

Analysis 2: SMC importance weights already contain distributional information

Analysis. Classical SMC theory provides an unbiased estimator Z^α\widehat{Z}_\alpha of the normalizing constant, E[Z^α]=Zα\mathbb{E}[\widehat{Z}_\alpha] = Z_\alpha ([7, 3]). We call it the standard estimator:

log⁡Z^α=∑t=1Tlog⁡[∑i=1NWt−1(i)ωt(i)],(4)\log\widehat{Z}_\alpha= \sum_{t=1}^{T}\log\left[\sum_{i=1}^{N}W_{t-1}^{(i)}\omega_t^{(i)}\right], \tag*{(4)}

where Wt−1(i)W_{t-1}^{(i)} are the normalized weights before step tt, equal to 1/N1/N at the start and after every resampling step. Power-SMC already computes every ωt(i)\omega_t^{(i)}, which follows Eq. (2) once an initial ramp of the exponent has ended, and every Wt−1(i)W_{t-1}^{(i)} as part of its usual importance-weight computation. The SMC sampler therefore already computes an estimate of ZαZ_\alpha, one step at a time, but it discards this information.

Methodology

Extracting SRE from Power-SMC

Because the logarithm is nonlinear, log⁡Z^α\log\widehat{Z}_\alpha is a plug-in estimate of log⁡Zα\log Z_\alpha rather than an unbiased estimator of it.

We define the estimate of the sequence-level Rényi entropy, SRE, as

SRE=log⁡Z^α1−α.(5)SRE = \frac{\log\widehat{Z}_\alpha}{1-\alpha}. \tag*{(5)}

Computing Z^α\widehat{Z}_\alpha requires only accumulating one scalar per decoding step: the log of the weighted mean of the incremental weights across particles.

Stepwise accumulation. In all experiments we accumulate the log of the uniform mean of the incremental weights over particles at every step,

log⁡Z^αstep=∑t=1Tlog⁡[1N∑i=1Nωt(i)],(6)\log\widehat{Z}_\alpha^{\mathrm{step}} = \sum_{t=1}^{T}\log\left[\frac{1}{N}\sum_{i=1}^{N}\omega_t^{(i)}\right], \tag*{(6)}

which is Eq. (4) with Wt−1(i)=1/NW_{t-1}^{(i)}=1/N. It coincides with Eq. (4) when resampling occurs at every step. Under the blockwise resampling of Power-SMC (resampling at block boundaries when the ESS is low), the stepwise accumulation uses the next-token distributions of all NN particles at every step, rather than mainly those of the highest-weight particles. The two estimates have a Spearman rank correlation of at least 0.98 in every setting we test, and Appendix G compares them. Algorithm 1 in Appendix § 13 gives the implementation and the handling of resampling boundaries.

Stepwise family. Once the exponent ramp of Power-SMC has ended (Appendix § 13), ωt(i)=e(1−α)hα(y<t(i))\omega_t^{(i)} = e^{(1-\alpha)h_\alpha(y_{<t}^{(i)})} up to the nucleus truncation of the proposal, which drops the least likely tokens. Each term of Eq. (4) is therefore, up to a constant factor, the particle estimate of one increment of the order-α\alpha chain rule in Proposition 1. The weighted particles follow the intermediate target of the sampler, and Eq. (6) replaces the weighted mean by the uniform mean. The same per-step accumulation can be computed at any order β\beta from the next-token distributions that the sampler has already computed:

SREβ=∑t=1T11−βlog⁡[1∣At∣∑i∈Ate(1−β)hβ(y<t(i))],(7)SRE_\beta= \sum_{t=1}^{T} \frac{1}{1-\beta}\log\left[\frac{1}{|A_t|}\sum_{i\in A_t}e^{(1-\beta)h_\beta(y_{<t}^{(i)})}\right], \tag*{(7)}

where AtA_t is the set of particles still generating at step tt, with limit SRE1=∑t1∣At∣∑i∈AtH(pθ(⋅∣x,y<t(i)))SRE_1 = \sum_t \frac{1}{|A_t|}\sum_{i\in A_t} H(p_\theta(\cdot\mid x,y_{<t}^{(i)})) as β→1\beta\to1.

Whatever the order, the particles are drawn by the α\alpha-sharpened sampler, so SREβSRE_\beta measures order-β\beta entropy accumulated along the particles. At β=α\beta=\alpha this family member uses no ramp term and agrees with the stepwise accumulation of Eq. (6) at Spearman ρ≥0.94\rho\ge0.94 (Appendix § 14).

Choice of order. SREβSRE_\beta is the accumulated negative log of a power mean, of order β−1\beta-1, of the probability that the model gives to a token drawn from its own next-token distribution (Proposition 3, Appendix § 21). It is nonincreasing in β\beta and runs from a multiple of the length (β→0\beta\to0) to the summed negative log-probability, at each step, of the most likely top token among the particles (β→∞\beta\to\infty). For every β>1\beta> 1 each increment lies within a factor β/(β−1)\beta/(\beta-1) of the top-token term, so members of these orders are tied to the top token; members of order up to one also respond to how the remaining probability mass is spread. At β=1\beta=1 the family gives SRE1SRE_1, the chain-rule sum of Shannon entropies (Malinin and Gales, [20]) on the particle set, and the order-1/21/2 member accumulates the log of the per-step search effort defined next.

Proposition 2 (Search effort). Let Y∼pY \sim p be the completion to be found, and let a sampler draw completions independently from a proposal qq. The expected number of draws until YY is first drawn is at least eH1/2(p)e^{H_{1/2}(p)} for every qq, with equality for q∝pq \propto p.

The proof is in Appendix § 22; the same quantity governs guessing in order of decreasing probability (Arikan, [1]). Applied to the next-token distribution, eh1/2(y<t)e^{h_{1/2}(y_{<t})} is the least expected number of independent draws needed to hit the model’s next token, and SRE1/2SRE_{1/2} accumulates the log of this per-step search effort along the particles. The stepwise accumulation of order α\alpha has an analogous reading for the power distribution: Hα(pθ)=H1/α(πα)H_\alpha(p_\theta) = H_{1/\alpha}(\pi_\alpha), and eHα(pθ)e^{H_\alpha(p_\theta)} bounds the order-(α−1)(\alpha-1) guesswork of a completion drawn from πα\pi_\alpha within a factor 1+ln⁡M1+\ln M, where MM is the number of possible completions (Appendix § 22). We report three SRE signals: SRESRE, the stepwise accumulation of order α\alpha (Eq. (6)), which comes from the incremental weights with no further computation; SRE1SRE_1; and SRE1/2SRE_{1/2}.

Theoretical guarantee

Lemma 1 (SMC estimator of ZαZ_\alpha). Consider an SMC sampler with NN particles whose final target is πα\pi_\alpha, with any intermediate targets and proposals and with unbiased resampling at times that may depend on the current particle system. Let Z^α,N\widehat{Z}_{\alpha,N} be the standard estimator of Eq. (4) and SRE^α,N=11−αlog⁡Z^α,N\widehat{SRE}_{\alpha,N} = \frac{1}{1-\alpha}\log\widehat{Z}_{\alpha,N}. For every N≥1N \ge1, α>1\alpha> 1, and δ∈(0,1)\delta\in(0,1):

  1. E[Z^α,N]≤Zα\mathbb{E}[\widehat{Z}_{\alpha,N}] \le Z_\alpha, with equality for full-support proposals;

  2. E[SRE^α,N]≥Hα(pθ(⋅∣x))\mathbb{E}[\widehat{SRE}_{\alpha,N}] \ge H_\alpha(p_\theta(\cdot\mid x)); (upward bias)

  3. Pr⁡[SRE^α,N≥Hα(pθ(⋅∣x))−log⁡(1/δ)α−1]≥1−δ\Pr\left[\widehat{SRE}_{\alpha,N} \ge H_\alpha(p_\theta(\cdot\mid x))-\frac{\log(1/\delta)}{\alpha-1}\right] \ge1-\delta. (finite NN)

With full-support proposals and multinomial resampling at fixed times, SRE^α,N→Hα(pθ(⋅∣x))\widehat{SRE}_{\alpha,N} \to H_\alpha(p_\theta(\cdot\mid x)) in probability as N→∞N \to\infty.

The proof is in Appendix § 23. The bounds of the lemma cover Power-SMC as run, with its exponent ramp, its nucleus-truncated proposal, and its ESS-triggered resampling. The guarantee is non-asymptotic: at α=4\alpha=4 the estimate is more than one nat below the true sequence-level Rényi entropy in at most 5% of per-problem runs, for every particle budget including N=8N=8.

Generality. Lemma 1 holds for every SMC sampler whose final target is πα\pi_\alpha, whatever its positive intermediate targets and its unbiased resampling rule. The readout therefore applies, at the same zero marginal cost, to other SMC samplers for power sampling such as APPS (Nguyen et al., [21]) (Appendix § 24).

Adaptive particle allocation

Fixed particle budgets waste compute: easy problems are solved with a small NN, while hard problems may need many particles.

We use a two-pass policy with a threshold θ\theta: run Power-SMC with NprobeN_{\mathrm{probe}} particles (e.g., N=8N=8) and extract SRESRE and the candidate answer; if SRE>θSRE > \theta, escalate the problem by re-running it with NfullN_{\mathrm{full}} (e.g., N=64N=64), and otherwise accept the probe answer. The probe supplies the signal before committing to the expensive run, and its own answer serves as the fallback.

Experiments

Setup

We evaluate on MATH500 (Hendrycks et al., [11]; Lightman et al., [19]) and GSM8K (Cobbe et al., [4]) for mathematical reasoning. We test four models from two model families: Qwen2.5-Math-1.5B, Qwen2.5-Math-7B (math-specialized), Qwen2.5-7B (general-purpose) (Qwen Team et al., [22]), and Llama-3.1-8B-Instruct (Dubey et al., [8]). For each problem, we extract six uncertainty signals at zero marginal cost from the SMC run: (1) SRE1/2SRE_{1/2} and (2) SRE1SRE_1 from Eq. (7) (ours); (3) SREαSRE_{\alpha} from Eq. (6) (ours); (4) mean token entropy, which is SRE1SRE_1 divided by the number of decoding steps; (5) sequence log-probability, log⁡pθ(y∣x)\log p_{\theta}(y|x), of the returned completion; (6) particle agreement, the answer agreement across the NN SMC particles.1

None of them requires decoding beyond the Power-SMC run; generation length is reported as a reference. The SMC runs use Hugging Face Transformers with bfloat16 model parameters on NVIDIA RTX A6000 GPUs. The base performance of Power-SMC is reported in Appendix § 8. We will release the readout patch, the evaluation scripts, and per-problem logs.

Selective prediction

Experiment. We rank problems by each signal and report the AUROC for predicting the correctness of the returned answer in eight model–benchmark settings (Table 1); lower SRE, lower mean token entropy, higher log-probability, and higher answer agreement count as higher confidence.

SignalMATH500 M-1.5BMATH500 M-7BMATH500 Q-7BMATH500 LlamaGSM8K M-1.5BGSM8K M-7BGSM8K Q-7BGSM8K Llama
SRE1/2SRE_{1/2} (ours).836.850.834.884.776.782.658.743
SRE1SRE_1 (ours).825.821.824.866.760.779.686.733
SREαSRE_{\alpha} (ours).816.806.809.866.748.753.642.724
Seq log-prob.810.805.801.862.744.741.635.719
Self-cons.†.656.696.650.547.718.713.688.626
Mean token entropy.714.699.531.390.728.820.697.691
Generation length.690.678.722.852.592.479.493.626

Table 1. Selective prediction AUROC (N=32N=32, α=4\alpha=4, 500 problems per setting). M: Qwen2.5-Math, Q-7B: Qwen2.5-7B, Llama: Llama-3.1-8B-Instruct. SREαSRE_{\alpha}: stepwise accumulation of order α\alpha from the incremental weights (Eq. (6)); SRE1SRE_1 and SRE1/2SRE_{1/2}: order-1 and order-1/2 members (Eq. (7)). Best in bold, second best underlined. Bootstrap confidence intervals in Appendix § 16.

SRE1/2SRE_{1/2} is the best zero-cost signal in six of the eight settings. On MATH500, the SRE signals are the best for all four models, with SRE1/2SRE_{1/2} between 0.834 and 0.884. With the larger Qwen2.5-14B-Instruct the SRE signals reach 0.863 to 0.867, against 0.860 for log-probability, and with the newer Qwen3-4B (Yang et al., [25]), SRE1/2SRE_{1/2} reaches 0.864 against 0.837 (p<0.001p < 0.001; Appendix § 17).

On GSM8K, where generation length carries little information about correctness (AUROC 0.48 to 0.63, against 0.68 to 0.85 on MATH500), length normalization matters less: mean token entropy leads on Qwen2.5-Math-7B and Qwen2.5-7B, by margins over SRE1/2SRE_{1/2} that are not significant (p=0.19p=0.19 and 0.33). The order-1/2 member is the best signal on Qwen2.5-Math-1.5B and Llama-3.1-8B and the second best on Qwen2.5-Math-7B.

SRE1SRE_1 is above sequence log-probability in all eight settings, by 0.004 to 0.051 AUROC, and the difference is significant in six of them (paired permutation tests, p<0.05p < 0.05; Appendix § 16). SREαSRE_{\alpha}, which needs no computation beyond the incremental weights, is above log-probability in all eight as well, by up to 0.013. SRE1/2SRE_{1/2} is the strongest SRE signal in seven of the eight settings: on MATH500 it is 0.022 to 0.044 above log-probability (p≤0.006p \le0.006; p≤0.029p \le0.029 after Holm correction over the eight settings), and on GSM8K it is 0.023 to 0.041 above (§5.4).

Abstaining on the 20% highest-SRE1/2SRE_{1/2} problems raises accuracy on the rest from 75.8% to 86.0% (MATH500, Qwen2.5-Math-7B; Figure 2).

Figure 2. Selective prediction with Qwen2.5-Math-7B: accuracy vs. coverage on MATH500 (left) and GSM8K (right). AUROC in legend as [MATH500 / GSM8K].

Combining SRE1/2SRE_{1/2} with the three baselines in a logistic regression gives 0.878 cross-validated AUROC (Appendix § 11).

Does SRE predict the gain from more particles?

Experiment. We run Power-SMC at N∈{8,32,64}N \in\{8, 32, 64\} on MATH500 with Qwen2.5-Math-7B

†Correlated SMC-particle agreement (Appendix § 10).

and partition the problems into terciles of SREαSRE_{\alpha} from the N=8N=8 run (Table 2).

TercilennN=8N=8N=32N=32N=64N=64Gain
Low16794.093.492.8−1.2
Mid16683.784.386.7+3.0
High16746.749.752.1+5.4
All50074.875.877.2+2.4

Table 2. Accuracy (%) by SREαSRE_{\alpha} tercile from the N=8N=8 probe (500 problems, Qwen2.5-Math-7B, α=4\alpha=4). Gain = Acc(N=64N=64) − Acc(N=8N=8).

The gain from more particles grows with probe SREαSRE_{\alpha}: −1.2, +3.0, and +5.4 points from the low to the high tercile.

Replication. Averaged over three seeds, the gains are −0.6, +2.4, and +2.6 points, and on Qwen2.5-Math-1.5B they are +0.6, +3.6, and +6.0. In every run the low tercile gains at most 0.6 points, while the upper two terciles together gain 1.2 to 4.8 points (Appendix § 27). This rise across terciles is not a re-draw effect: over all pairings of the three seeds, an independent N=8N=8 run changes accuracy by −0.3, +0.4, and −0.1 points in the three terciles, against −0.5, +2.1, and +2.8 for N=64N=64, and in the upper two terciles N=64N=64 gains 2.3 points more than a re-draw (95% confidence interval 0.2 to 4.4).

Rank stability. The Spearman correlation between SREαSRE_{\alpha} estimated at N=8N=8 and N=64N=64 is 0.953 to 0.965 on the three seeds, and probe SRE1/2SRE_{1/2} identifies the problems that are correct at both particle budgets with AUROC 0.841 to 0.845, against 0.808 to 0.818 for log-probability (Appendix § 15).

Which entropy order?

Experiment. We log SREβSRE_{\beta} for orders from 1/41/4 to ∞\infty in the same runs and compare them on the same problems (Figure 3).

Figure 3. Selective prediction AUROC of SREβSRE_{\beta} (Eq. (7)) minus that of sequence log-probability, as a function of the order β\beta (N=32N=32, α=4\alpha=4).

On MATH500 the margin over sequence log-probability is largest at order 1/21/2 for every model: SRE1/2SRE_{1/2} reaches 0.836, 0.850, 0.834, and 0.884 with the four models, against 0.825, 0.821, 0.824, and 0.866 for SRE1SRE_1. On GSM8K the order-1/2 member is the best of the family with three of the four models (0.776, 0.782, and 0.743, against 0.760, 0.779, and 0.733); with Qwen2.5-7B, SRE1SRE_1 is higher (0.686 against 0.658). At β=∞\beta=\infty, where only the top token of each step counts, AUROC falls below that of log-probability (0.615 to 0.769 on MATH500). Below 1/21/2 the tail of the vocabulary dominates every increment and SREβSRE_{\beta} approaches a multiple of the completion length (Spearman ρ≥0.93\rho\ge0.93 at β=1/4\beta=1/4), so AUROC drops, to 0.743 on MATH500 with Qwen2.5-7B.

The choice of order is not tuned to a setting: selecting the order by mean AUROC on the other seven settings picks 1/2 for each held-out setting, and so do the four N=8N=8 probe runs and the N=64N=64 run of § 5.6 that log every order of the stepwise family (0.845, 0.824, and 0.827 for SRE1/2SRE_{1/2} on the three probe seeds, against 0.813, 0.792, and 0.792 for log-probability). SRE1/2SRE_{1/2} does not depend on the far tail of the vocabulary: computed over the 100 most likely tokens of each step, it is above log-probability in all seven settings where we log it, by 0.014 to 0.052, and over the 10 most likely tokens by 0.008 to 0.041.

Sensitivity to alpha

We sweep α∈{1.5,2,3,4,6,8}\alpha\in\{1.5, 2, 3, 4, 6, 8\} on MATH500 with Qwen2.5-Math-7B (Figure 6, Appendix § 25). SRE1/2SRE_{1/2} is the best of the logged orders at every α\alpha and the best of all signals from α=2\alpha=2 upward, 0.044 to 0.069 AUROC above sequence log-probability (p≤0.001p \le0.001); at α=1.5\alpha=1.5, where particle agreement leads (0.831), it is 0.079 above. SRE1SRE_1 stays between 0.802 and 0.822 and is above log-probability at every α\alpha (all p≤0.002p \le0.002), while particle agreement falls to 0.598 at α=8\alpha=8.

Figure 6. Selective prediction AUROC vs. α\alpha (MATH500, Qwen2.5-Math-7B, N=32N=32). †SC is particle agreement (correlated self-consistency).

Adaptive particle allocation: accuracy vs. compute

Experiment. We apply the two-pass policy of § 4.3 to MATH500 with Qwen2.5-Math-7B: the probe runs at N=8N=8 and problems with SREαSRE_{\alpha} above a threshold are re-run at N=64N=64 (every escalation rate in Appendix § 27).

Escalating the 40% highest-SREαSRE_{\alpha} problems matches uniform N=64N=64 accuracy (77.2%) with 47.5% fewer particles (Figure 4); on two further seeds the saving is 22.5% and 32.5%, for an average of 34.2%. With one escalation rate for all seeds, escalating 60% gives the three-seed mean accuracy of uniform N=64N=64 (76.6%) with 27.5% fewer particles, and random escalation saves nothing on average (−0.8%; Appendix § 27). With abstention added, a three-way policy (abstain, escalate, or keep the probe answer) matches uniform N=64N=64 on the 80% most confident problems (85.1% vs. 85.0%) with 4.2×4.2\times instead of 8×8\times the probe’s particle budget (Appendix § 28).

Figure 4. Adaptive particle allocation on MATH500 (Qwen2.5-Math-7B, α=4\alpha=4). (a) Accuracy gain from N=8→64N=8\to64 by SREαSRE_{\alpha} tercile. (b) Accuracy vs. compute: the two-pass policy reaches uniform N=64N=64 accuracy from 4.2×4.2\times onward and peaks at 77.8%.

Comparison of gating signals. Table 16 (Appendix § 27) compares SREαSRE_{\alpha} as a gating signal with other signals from the same probe run, including answer entropy over the probe’s particles (used by Fu et al. [10]) and Self-Certainty (Kang et al. [16]). Averaged over escalation rates

Gating signalMath-7B s42Math-7B s43Math-7B s44Math-7B meanM-1.5B s42
SRE1/2SRE_{1/2} (ours)77.0176.2675.6876.3169.39
SREαSRE_{\alpha} (ours)76.8876.1075.8176.2669.19
SRE1SRE_{1} (ours)76.8476.1775.7676.2669.27
Seq log-prob76.7676.1175.7576.2169.25
Answer entropy76.6976.2676.7576.5769.10
Self-Certainty76.5076.8676.0976.4870.06
Mean token entropy76.2976.0676.2376.1969.60
Random escalation76.0076.1075.5075.8768.90

Table 16. Gating signals for adaptive particle allocation, all computed from the same N=8N=8 probe (MATH500, 500 problems; s42 to s44: seeds). Entries are the accuracy (%) of the two-pass policy averaged over escalation rates from 0% to 100% in steps of 5%.

and three seeds, every signal beats random escalation. SRE1/2SRE_{1/2} is the best gating signal on the first seed, and SREαSRE_{\alpha} is within 0.94 points of the best gating signal in every run.

Analysis

Why the order matters. For every order above one, each increment lies between the negative log-probability of the top token and β/(β−1)\beta/(\beta-1) times it, and at the sequence level, with H∞H_{\infty} the negative log-probability of the most likely completion, H∞≤Hα≤αα−1H∞H_{\infty} \le H_{\alpha} \le\frac{\alpha}{\alpha-1}H_{\infty} (Proposition 3). Members of such orders are tied to the top token, which is also what the log-probability of a completion sampled at low temperature reflects. The data agree: at α=4\alpha=4 the standard estimator is within 0.004 AUROC of log-probability in all eight settings, and the order-4 increments sum to 1.25 times the top-token terms (median, inside the range [1,4/3][1, 4/3] of the proposition). Members of order up to one also respond to how the remaining probability mass is spread, and this is where the margin appears: 0.004 to 0.051 at order 1 and 0.022 to 0.044 at order 1/2.

The particle set. At order 1/2, aggregating over the particle set raises AUROC above that of the same sum along the returned completion at every α\alpha with Qwen2.5-Math-7B on MATH500: by 0.062, 0.030, 0.030, 0.012, 0.012, and 0.011 for α=1.5\alpha=1.5, 2, 3, 4, 6, and 8 (p<0.05p < 0.05 up to α=3\alpha=3). This advantage grows with the diversity of the particles (2.1, 1.6, 1.4, 1.3, 1.2, and 1.2 distinct answers per problem); at α=4\alpha=4 it is 0.020 with Qwen2.5-7B and 0.014 with Qwen3-4B (p≤0.020p \le0.020). At equal log-probability, higher SRE1/2SRE_{1/2} goes with more disagreement among the particles’ answers in all eight settings of Table 1 (partial Spearman correlation 0.06 to 0.34).

Sum, not mean. SRE1SRE_1 and mean token entropy are built from the same next-token entropies and differ only in the division by the length. On MATH500 that normalization costs 0.11 to 0.48 AUROC: dividing by the length removes the accumulated part. The accumulated part is more than length. Generation length alone reaches 0.68 to 0.85 AUROC on MATH500 and 0.48 to 0.63 on GSM8K, and SRE1/2SRE_{1/2} is 0.03 to 0.30 above it in all eight settings (p≤0.001p \le0.001 after Holm correction). The same normalization also hurts at order 1/21/2. Dividing SRE1/2SRE_{1/2} by the length gives a particle-set version of the average per-token Rényi score that Darrin et al. [6] use for out-of-distribution detection, and it lowers the AUROC from 0.850 to 0.708 (MATH500, Qwen2.5-Math-7B).

SRE is not a length proxy. Within every quartile of generation length, the half of problems with above-median SREαSRE_\alpha is less accurate, by 18 to 39 points on MATH500 and 13 to 29 points on GSM8K (Table 14, Appendix § 26). Inside length quartiles SRE1/2SRE_{1/2} stays above sequence log-probability in all eight settings, by 0.030 to 0.050 AUROC on MATH500 and 0.020 to 0.052 on GSM8K (Table 15); the pooled margins are 0.022 to 0.044 and 0.023 to 0.041, so the advantage does not come from length.

Length quartileMATH500 LowMATH500 HighGSM8K LowGSM8K High
Q1 (shortest)96.869.495.266.1
Q295.277.4100.082.3
Q392.167.795.282.3
Q4 (longest)73.033.992.175.8

Table 14. Accuracy (%) of the below-median (Low) and above-median (High) SREαSRE_\alpha halves within each quartile of generation length (Qwen2.5-Math-7B, N=32N=32, α=4\alpha=4).

SignalMATH500 M-1.5BMATH500 M-7BMATH500 Q-7BMATH500 LlamaGSM8K M-1.5BGSM8K M-7BGSM8K Q-7BGSM8K Llama
SRE1/2SRE_{1/2} (ours).821.823.804.741.781.795.701.742
SRE1SRE_{1} (ours).813.789.789.708.757.811.731.721
SREαSRE_{\alpha} (ours).799.773.770.713.738.790.677.711
Seq log-prob.791.773.760.709.729.776.677.708
Mean token entropy.755.747.715.649.723.814.719.690

Table 15. Length-stratified selective prediction AUROC (N=32N=32, α=4\alpha=4, 500 problems per setting): correct–incorrect pairs are compared only inside the same quartile of generation length.

Related Work

LLM uncertainty quantification. Self-consistency (Wang et al. [24]) measures answer agreement across KK independent completions. Semantic entropy (Kuhn et al. [18]) clusters sampled completions by meaning. P(True) (Kadavath et al. [15]) asks the model in an extra query whether its answer is true. Malinin and Gales [20] estimate sequence-level Shannon entropy from independent completions with the chain rule; SRE1SRE_1 applies this chain-rule sum to the particle set of an SMC sampler, and Proposition 1 extends it to Rényi orders. Darrin et al. [6] average a per-token Rényi divergence from the uniform distribution along one completion; SRE accumulates instead of averaging and aggregates over the particle set. To our knowledge, SREαSRE_\alpha is the first sequence-level entropy signal for LLM generation built from the normalizing-constant estimate of an importance-weighted sampler. Appendix § 12 gives a detailed comparison.

Power sampling for LLM reasoning. Power sampling was introduced with a Metropolis–Hastings sampler (Karan and Du [17]) and made faster with SMC (Azizi et al. [2]), rollouts (sampled continuations) (Ji et al. [13]), and future-value potentials (Nguyen et al. [21]). None of these works use the normalizing-constant estimate as an uncertainty signal or for adaptive particle allocation.

Adaptive inference-time compute. Several works allocate compute based on problem difficulty (Snell et al. [23]), typically with trained difficulty predictors or reward models. Certainedex (Fu et al. [10]) tracks the stability of intermediate answers, such as answer entropy across sampled completions, to stop or reallocate compute. CaTS (Huang et al. [12]) distills self-consistency confidence into the model and uses it for early stopping in repeated sampling. Self-Certainty (Kang et al. [16]) scores each completion by the divergence of its next-token distributions from uniform for best-of-NN selection. SRE is complementary: it is read from the SMC sampler itself and gates the particle budget of that same sampler.

Conclusions

We showed that SMC decoding already estimates the sequence-level Rényi entropy of the model’s completion distribution at the cost of one scalar accumulation per decoding step, with a guarantee that holds at every particle budget. A Rényi chain rule turns this readout into a family of stepwise entropies whose order-1/2 member, which accumulates the log of per-step search effort, is the best zero-cost selective-prediction signal in 10 of 13 settings, with a margin over log-probability that holds within length quartiles and with the order chosen on held-out settings. A cheap N=8N=8 probe identifies which problems need expensive decoding, and the two-pass policy matches uniform N=64N=64 accuracy on MATH500 with 34.2% fewer particles on average over three seeds.

Limitations

SRE is computed from the particle set of an SMC run and has zero marginal cost relative to that run (Appendix § 10 reports the order-1/2 sum along the returned completion alone); decoding that draws a single completion from the start is not evaluated. Our evaluation covers mathematical reasoning with six open-weight models from 1.5B to 14B parameters; other task types, such as open-ended generation and multi-turn interaction, are left for future work. The two-pass policy studied here chooses between two particle budgets; routing across models or reasoning modes with the same signal is a natural extension that we do not evaluate.

Power-SMC Accuracy

Table 3 reports the accuracy of Power-SMC for the four models on MATH500 ([11]) and GSM8K ([4]). All models are decoded with Power-SMC (α=4\alpha=4, block size 64, ESS threshold 0.5, α\alpha-ramp over 400 tokens, top-pp 0.9 on the proposal, at most 2,048 new tokens) unless noted otherwise. The default particle budget is N=32N=32. Answers are graded with the Power-SMC repository’s exact-match grader.

ModelMATH500GSM8K
Qwen2.5-Math-1.5B69.080.8
Qwen2.5-Math-7B75.886.2
Qwen2.5-7B71.885.0
Llama-3.1-8B-Instruct50.285.2

Table 3. Model accuracy (%) with Power-SMC (N=32N=32, α=4\alpha=4, 500 problems).

Difficulty estimation. We ask whether uncertainty signals track externally annotated problem difficulty. MATH500 problems have ground-truth difficulty levels from 1 (easiest) to 5 (hardest) ([11]). We compute the Spearman rank correlation between each signal and the level over all 500 problems (Table 5).

SignalM-1.5BM-7BQ-7BLlama
SRE1SRE_1 (ours)+0.461+0.447+0.480+0.499
SREαSRE_{\alpha} (ours)+0.467+0.441+0.494+0.500
Neg. seq log-prob+0.473+0.436+0.502+0.505
Mean token entropy+0.164+0.094−0.120−0.120

Table 5. Spearman ρ\rho with MATH difficulty levels (all 500 problems, N=32N=32, α=4\alpha=4).

SRE1SRE_1 and SREαSRE_{\alpha} correlate with difficulty at ρ=0.44\rho=0.44 to 0.50 across the four models, on par with sequence log-probability, while mean token entropy reaches at most 0.16 and is negatively correlated for two models. Per-level means for Qwen2.5-Math-7B (Table 4) confirm the trend: SREαSRE_{\alpha} increases monotonically from 12.8 (Level 1) to 32.6

LvlnnSREαSRE_{\alpha}TokEntAcc
14312.80.0880.91
29016.40.0770.87
310520.80.0890.87
412824.20.0850.73
513432.60.0900.57

Table 4. Per-level mean uncertainty and accuracy (500 problems, Qwen2.5-Math-7B).

(Level 5), while accuracy decreases from 0.91 to 0.57. The same monotone increase holds for the other three models.

Correct vs. Incorrect Signal Distributions

Figure 5 shows the distributions of each uncertainty signal for correct and incorrect answers (MATH500, Qwen2.5-Math-7B). SREαSRE_{\alpha} separates the two groups (AUROC 0.806), with incorrect answers concentrating at high-uncertainty values; SRE1/2SRE_{1/2} reaches 0.850. Mean token entropy (AUROC 0.699) shows more overlap.

Figure 5. Confidence distributions for correct (green) and incorrect (red) answers under each signal.

Particle Agreement

Particle agreement (Self-cons. in Table 1) measures answer agreement across the N=32N=32 SMC particles. After resampling, particles share ancestors and are no longer independent, which suppresses the disagreements that signal incorrect answers. Weighting the particles’ answers by the normalized weights does not fix particle agreement: the weighted answer entropy reaches 0.60 to 0.72 AUROC in the eight N=8N=8 and N=64N=64 runs of § 5.6, below sequence log-probability (0.78 to 0.81) in each. Computed along the returned completion alone, the order-1/2 sum is above sequence log-probability in all seven settings where we log it, by 0.013 to 0.033 AUROC.

Signal Combination

A natural question is whether the four zero-cost signals capture complementary information. We train a logistic regression (5-fold cross-validated) on MATH500 with Qwen2.5-Math-7B to predict correctness from signal combinations. SRE1/2SRE_{1/2} alone reaches 0.844 cross-validated AUROC; adding all three other signals raises this to 0.878. Adding SRE1/2SRE_{1/2} to the three baseline signals raises the cross-validated AUROC in all eight settings of Table 1, by 0.001 to 0.023. The improvement indicates that the signals capture partially orthogonal aspects of uncertainty, and a simple learned combination outperforms any single signal. In practice, this combination remains zero-cost at inference: all four signals are already computed by the SMC run.

Positioning Against Prior Work

MethodLevelExtra cost
Token ent.TokenFree
Seq log-probSingle pathFree
Self-CertaintyToken dist.Free
Self-cons.AnswerKK gens
CertaindexAnswerKK gens
Sem. ent.Ans. clust.KK + clust.
P(True)Surface1 query
SRE (ours)Seq. dist.0 marg.

Table 6. Comparison with LLM uncertainty methods. Level: the object the signal is computed on. Extra cost: computation beyond the decoding run that produces the answer.

Handling Resampling in the Normalizing-Constant Estimate

Power-SMC resamples at block boundaries when the effective sample size falls below a threshold, so between resampling events the particles carry unequal normalized weights Wt−1(i)W_{t-1}^{(i)}. The standard estimator of Eq. (4) accumulates the log of the WW-weighted mean of the incremental weights at every step. Over a segment between two resampling events these terms telescope to log⁡1N∑iw~(i)\log\frac{1}{N}\sum_i \widetilde{w}^{(i)}, where w~(i)\widetilde{w}^{(i)} is the unnormalized weight that particle ii has accumulated since the last resampling event. When systematic resampling occurs, the weights are reset to 1/N1/N and the unbiasedness of Z^α\widehat{Z}_{\alpha} is preserved because systematic resampling is itself unbiased ([3]): E[1N∑if(y(Ai))]=∑iwif(y(i))\mathbb{E}\left[\frac{1}{N}\sum_i f(y^{(A_i)})\right] = \sum_i w_i f(y^{(i)}). The stepwise accumulation of Eq. (6) uses the uniform mean at every step, so it needs no bookkeeping at resampling boundaries: we continue accumulating log-mean incremental weights across them. Power-SMC raises the exponent linearly from 1 to α\alpha over the first 400 tokens (the exponent ramp), αt=1+(α−1)min⁡(t,400)/400\alpha_t = 1 + (\alpha- 1)\min(t,400)/400 with α0=1\alpha_0 = 1. The intermediate target after tt tokens is pθ(y1:t∣x)αtp_\theta(y_{1:t}|x)^{\alpha_t} and the incremental weight is

ωt=pθ(y<t∣x)αt−αt−1pθ(yt∣x,y<t)αt−α×∑v∈Vtpθ(v∣x,y<t)α\omega_t = p_\theta(y_{<t}|x)^{\alpha_t-\alpha_{t-1}}p_\theta(y_t|x,y_{<t})^{\alpha_t-\alpha}\times\sum_{v\in V_t}p_\theta(v|x,y_{<t})^\alpha

where VtV_t is the nucleus of the proposal (the tokens that nucleus truncation keeps). The product of the incremental weights along a completion equals pθ(y∣x)α/q(y)p_\theta(y|x)^\alpha/q(y) for every completion length, because a final correction raises the exponent to α\alpha when decoding ends before the ramp does. The final target is therefore πα\pi_\alpha and Eq. (4) estimates ZαZ_\alpha. Both accumulations use this incremental weight.

Algorithm 1 SRE extraction from Power-SMC

Figure 1 (PDF p. 12). SRE extraction from Power-SMC.

Estimator Variants

Table 7 compares the stepwise accumulation of Eq. (6), reported as SREαSRE_\alpha throughout the paper, with the standard estimator of Eq. (4) and with SRE1SRE_1, all computed in the same runs. The stepwise and standard estimators rank problems almost identically (Spearman ρ>0.98\rho> 0.98 in every row). The standard estimator stays within 0.004 AUROC of sequence log-probability at α=4\alpha=4, while the stepwise accumulation is above log-probability in all 13 rows. The order-α\alpha member of Eq. (7) (Fam.), which uses no ramp term and averages over the particles still generating, agrees with the stepwise accumulation at Spearman ρ≥0.94\rho\ge0.94. As a gating signal for adaptive particle allocation (§ 5.6), the stepwise accumulation reaches uniform N=64N=64 accuracy with 47.5% fewer particles on the first seed and the standard estimator with 42.5%.

Model, α\alphaLogPStd.Step.Fam.SRE1SRE_1SRE1/2SRE_{1/2}
MATH M-1.5B, 4.810.810.816.818.825.836
MATH M-7B, 4.805.805.806.816.821.850
MATH Q-7B, 4.801.804.809.816.824.834
MATH Llama, 4.862.862.866.858.866.884
GSM M-1.5B, 4.744.745.748.749.760.776
GSM M-7B, 4.741.745.753.771.779.782
GSM Q-7B, 4.635.636.642.685.686.658
GSM Llama, 4.719.723.724.735.733.743
MATH M-7B, 1.5.730.740.772.800.802.808
MATH M-7B, 2.772.772.790.810.814.841
MATH M-7B, 3.782.782.796.810.813.828
MATH M-7B, 6.786.787.798.801.807.841
MATH M-7B, 8.803.803.810.807.822.849

Table 7. Selective prediction AUROC (N=32N=32) of sequence log-probability (LogP), the standard estimator (Std., Eq. (4)), the stepwise accumulation of order α\alpha (Step., Eq. (6)), and the members of Eq. (7) of order α\alpha, 1, and 1/2.

Problem Transitions Under Particle Scaling

Table 8 characterizes how individual problems change when scaling from N=8N=8 to N=64N=64 (500 problems). The stepwise accumulation from the probe separates the problems that are answered correctly at both particle budgets (mean SREαSRE_\alpha 19.3) from the 44 whose correctness changes (33.4) and the 98 that stay wrong (41.1). Probe SRE1/2SRE_{1/2} identifies the problems that stay correct with AUROC 0.841, 0.845, and 0.845 on the three seeds, against 0.809, 0.818, and 0.808 for log-probability.

TransitionnnMean probe SREαSRE_\alpha
Stayed correct35819.3
Flipped to correct2834.2
Flipped to wrong1631.9
Stayed wrong9841.1

Table 8. Problem transitions N=8→N=64N=8 \to N=64 (500 problems, Qwen2.5-Math-7B).

Bootstrap Confidence Intervals

Tables 9 and 10 report 95% bootstrap confidence intervals (10,000 replicates) and paired permutation test pp-values against sequence log-probability (10,000 permutations; 200,000 for the one value within 0.005 of 0.05) for the eight settings of Table 1.

SRE1/2SRE_{1/2} is above sequence log-probability in all eight settings, significantly for all four models on MATH500 (p=0.002p=0.002, <0.001<0.001, 0.003, and 0.006) and for Qwen2.5-Math-1.5B on GSM8K (p=0.020p=0.020). With Holm correction over the eight settings it remains significant for all four MATH500 models (adjusted p≤0.029p \le0.029). It is significantly above SRE1SRE_1 for Qwen2.5-Math-7B and Llama on MATH500 (p<0.001p < 0.001), and significantly above generation length in all eight settings (p≤0.001p \le0.001 after Holm correction). SRE1SRE_1 is above sequence log-probability in all eight settings, significantly for the three Qwen models on both benchmarks, and SREαSRE_\alpha is above it in all eight, significantly in two. Mean token entropy and particle agreement are significantly below log-probability for all four models on MATH500 (p≤0.003p \le0.003).

ModelSignalAUROC (95% CI)pp vs. LogP
M-1.5BSRE1/2SRE_{1/2}.836 [.797, .871].002**
SRE1SRE_1.825 [.784, .862].007**
SREαSRE_\alpha.816 [.774, .854].035*
Seq log-prob.810 [.767, .848]—
Self-cons.†.656 [.613, .699]<.001***
Token entropy.714 [.663, .764]<.001***
M-7BSRE1/2SRE_{1/2}.850 [.808, .887]<.001***
SRE1SRE_1.821 [.776, .862].013*
SREαSRE_\alpha.806 [.759, .848].892
Seq log-prob.805 [.760, .848]—
Self-cons.†.696 [.647, .744].003**
Token entropy.699 [.643, .752]<.001***
Q-7BSRE1/2SRE_{1/2}.834 [.795, .872].003**
SRE1SRE_1.824 [.783, .863].005**
SREαSRE_\alpha.809 [.766, .851].121
Seq log-prob.801 [.756, .845]—
Self-cons.†.650 [.604, .695]<.001***
Token entropy.531 [.470, .590]<.001***
LlamaSRE1/2SRE_{1/2}.884 [.852, .913].006**
SRE1SRE_1.866 [.832, .897].461
SREαSRE_\alpha.866 [.832, .897].090
Seq log-prob.862 [.827, .893]—
Self-cons.†.547 [.511, .583]<.001***
Token entropy.390 [.341, .440]<.001***

Table 9. Bootstrap 95% confidence intervals and paired permutation tests on MATH500 (α=4\alpha=4, N=32N=32).

†Correlated SMC-particle agreement.

Larger and Newer Models

Table 11 repeats the selective-prediction experiment on MATH500 with Qwen2.5-14B-Instruct and with Qwen3-4B (Yang et al., [25]) in non-thinking mode, using the same Power-SMC hyperparameters as in Table 1. Power-SMC reaches 80.8% and 79.8% accuracy. All three SRE signals are above sequence log-probability with both models. With Qwen3-4B, SRE1/2SRE_{1/2} is the best signal, 0.026 above log-probability (p<0.001p < 0.001) and 0.014 above the same sum along the returned completion (p=0.005p=0.005).

SignalQ2.5-14BQ3-4B
SRE1/2SRE_{1/2} (ours).863.864
SRE1SRE_1 (ours).867.856
SREαSRE_{\alpha} (ours)<u>.866</u>.846
Seq log-prob.860.837
Self-cons.^†.609.593
Mean token entropy.536.746
Generation length.808.833

Table 11. †Correlated SMC-particle agreement. Table 11: Selective prediction AUROC on MATH500 with Qwen2.5-14B-Instruct and Qwen3-4B in non-thinking mode (N=32N=32, α=4\alpha=4, 500 problems).

Risk–Coverage Analysis

Table 12 reports the area under the risk–coverage curve (AURC), the error rate on the retained problems averaged over all coverage levels, for the settings of Table 1. The best signal by AURC is the best signal by AUROC in all eight settings: SRE1/2SRE_{1/2} has the lowest AURC in six, an SRE signal is the best or second best in all eight, and SRE1/2SRE_{1/2} and SRE1SRE_1 have a lower AURC than sequence log-probability in all eight.

SignalMATH500 M-1.5BMATH500 M-7BMATH500 Q-7BMATH500 LlamaGSM8K M-1.5BGSM8K M-7BGSM8K Q-7BGSM8K Llama
SRE1/2SRE_{1/2} (ours)11.98.010.223.37.75.29.17.4
SRE1SRE_{1} (ours)12.5<u>9.0</u><u>10.8</u>24.6<u>8.6</u>5.08.17.8
SREαSRE_{\alpha} (ours)12.99.511.624.88.95.610.38.6
Seq log-prob13.09.312.225.08.85.910.59.0
Self-cons.†23.616.321.647.311.98.49.611.0
Mean token entropy20.115.229.063.011.44.27.98.0

Table 12. Area under the risk–coverage curve (×100\times100, lower is better; N=32N=32, α=4\alpha=4, 500 problems per setting). Ties are broken at random and averaged over 200 orderings. Best in bold, second best underlined. †Correlated SMC-particle agreement.

ModelSignalAUROC [95% CI]pp vs. LogP
M-1.5BSRE1/2SRE_{1/2}.776 [.725, .823].020*
SRE1SRE_1.760 [.706, .811].049*
SREαSRE_{\alpha}.748 [.693, .800].251
Seq log-prob.744 [.689, .795]—
Self-cons.^†.718 [.664, .770].575
Token entropy.728 [.666, .788].519
M-7BSRE1/2SRE_{1/2}.782 [.723, .837].063
SRE1SRE_1.779 [.725, .830].002**
SREαSRE_{\alpha}.753 [.697, .806].014*
Seq log-prob.741 [.683, .795]—
Self-cons.^†.713 [.648, .776].500
Token entropy.820 [.766, .869].005**
Q-7BSRE1/2SRE_{1/2}.658 [.586, .726].213
SRE1SRE_1.686 [.619, .752]<.001***
SREαSRE_{\alpha}.642 [.566, .717].210
Seq log-prob.635 [.559, .710]—
Self-cons.^†.688 [.628, .746].325
Token entropy.697 [.631, .763].123
LlamaSRE1/2SRE_{1/2}.743 [.674, .806].129
SRE1SRE_1.733 [.662, .797].255
SREαSRE_{\alpha}.724 [.651, .791].419
Seq log-prob.719 [.646, .787]—
Self-cons.^†.626 [.558, .691].094
Token entropy.691 [.624, .756].346

Table 10. †Correlated SMC-particle agreement. Table 10: Bootstrap 95% confidence intervals and paired permutation tests on GSM8K (α=4\alpha=4, N=32N=32).

Estimator Variance Analysis

To characterize the reliability of the SREαSRE_{\alpha} estimator, we run each of 50 MATH500 problems R=10R=10 times with different random seeds at N=8N=8 and N=32N=32 (Qwen2.5-Math-7B, α=4\alpha=4). Table 13 summarizes the results.

NNMean CVMedian CVSplit-half ρ\rho
811.1%8.3%0.993
327.8%4.7%0.993

Table 13. Estimator variance of SREαSRE_{\alpha} across 10 repeated runs per problem (50 problems, Qwen2.5-Math-7B, α=4\alpha=4).

The coefficient of variation (CV) is small: the median CV is 8.3% at N=8N=8 and 4.7% at N=32N=32. The ranking of problems by SREαSRE_{\alpha} is almost perfectly stable: the Spearman rank correlation between the first and second halves of repeated runs is ρ=0.993\rho=0.993 at both NN values, and two single runs agree at ρ=0.964\rho=0.964 and 0.980 on average. This confirms that even a single N=8N=8 probe reliably identifies which problems are hard. On the 500 MATH500 problems the mean SRE from the standard estimator decreases with the particle budget (25.3, 23.2, and 22.6 at N=8N=8, 32, and 64), consistent with the upward bias of Lemma 1, which vanishes as NN grows; the stepwise accumulation follows the same trend (24.8, 23.3, and 22.9).

Proof of Proposition 1

Fix a prompt xx and a horizon TT, with EOS treated as absorbing after termination, so that the next-token distribution after EOS is a point mass with zero entropy. For t=0,…,Tt=0,\ldots,T let

Zβ(t)=∑y1:tpθ(y1:t∣x)β,Z_{\beta}^{(t)}=\sum_{y_{1:t}}p_{\theta}(y_{1:t}\mid x)^{\beta},

so that Zβ(0)=1Z_{\beta}^{(0)}=1 and Zβ(T)=Zβ(x)Z_{\beta}^{(T)}=Z_{\beta}(x). Factorizing pθ(y1:t∣x)=pθ(y<t∣x)pθ(yt∣x,y<t)p_{\theta}(y_{1:t}\mid x)=p_{\theta}(y_{<t}\mid x)p_{\theta}(y_t\mid x,y_{<t}) gives

Zβ(t)=∑y<tpθ(y<t∣x)β∑vpθ(v∣x,y<t)β=Zβ(t−1)Ey<t∼πβ(t−1)[∑vpθ(v∣x,y<t)β],\begin{aligned} Z_{\beta}^{(t)}=\sum_{y_{<t}}p_{\theta}(y_{<t}\mid x)^{\beta}\sum_v p_{\theta}(v\mid x,y_{<t})^{\beta} \\ &=Z_{\beta}^{(t-1)}\mathbb{E}_{y_{<t}\sim\pi_{\beta}^{(t-1)}}\left[\sum_v p_{\theta}(v\mid x,y_{<t})^{\beta}\right], \end{aligned}

and ∑vpθ(v∣x,y<t)β=e(1−β)hβ(y<t)\sum_v p_{\theta}(v\mid x,y_{<t})^{\beta}=e^{(1-\beta)h_{\beta}(y_{<t})} by the definition of hβh_{\beta}. Taking logarithms, summing the telescoping terms over tt, and dividing by 1−β1-\beta gives the statement, since Hβ(pθ(⋅∣x))=11−βlog⁡Zβ(T)H_{\beta}(p_{\theta}(\cdot\mid x))=\frac{1}{1-\beta}\log Z_{\beta}^{(T)}.

For the limit, πβ(t−1)→pθ(y<t∣x)\pi_{\beta}^{(t-1)}\to p_{\theta}(y_{<t}\mid x) and hβ→Hh_{\beta}\to H as β→1\beta\to1, and 11−βlog⁡E[e(1−β)hβ]=E[hβ]+O(1−β)\frac{1}{1-\beta}\log\mathbb{E}[e^{(1-\beta)h_{\beta}}]=\mathbb{E}[h_{\beta}]+O(1-\beta), so each increment converges to Ey<t∼pθ[H(Yt∣y<t,x)]\mathbb{E}_{y_{<t}\sim p_{\theta}}[H(Y_t\mid y_{<t},x)].

Order Spectrum of the Stepwise Family

Proposition 3 (Order spectrum). Fix a per-problem run and a step tt. Draw a particle II uniformly from AtA_t and a token V∼pθ(⋅∣x,y<t(I))V\sim p_{\theta}(\cdot\mid x,y_{<t}^{(I)}), and let Xt=pθ(V∣x,y<t(I))X_t=p_{\theta}(V\mid x,y_{<t}^{(I)}) be the probability the model gives to its own next token. Let Mr(X)=(E[Xr])1/rM_r(X)=(\mathbb{E}[X^r])^{1/r} be the power mean of order rr, with M0(X)=exp⁡E[log⁡X]M_0(X)=\exp\mathbb{E}[\log X], and let h∞=−log⁡max⁡vpθ(v)h_{\infty}=-\log\max_v p_{\theta}(v).

(a) The tt-th increment of Eq. (7) equals −log⁡Mβ−1(Xt)-\log M_{\beta-1}(X_t), so SREβ=∑t−log⁡Mβ−1(Xt)SRE_{\beta}=\sum_t-\log M_{\beta-1}(X_t).

(b) On every per-problem run SREβSRE_{\beta} is non-increasing in β\beta, with SREβ→Tlog⁡∣V∣SRE_{\beta}\to T\log|\mathcal{V}| as β→0\beta\to0 and SREβ→∑tmin⁡i∈Ath∞(yt(i))SRE_{\beta}\to\sum_t\min_{i\in A_t}h_{\infty}(y_t^{(i)}) as β→∞\beta\to\infty.

(c) For β>1\beta>1 every next-token distribution satisfies h∞≤hβ≤ββ−1h∞h_{\infty}\le h_{\beta}\le\frac{\beta}{\beta-1}h_{\infty}. Hence each increment of Eq. (7) is at least min⁡i∈Ath∞(yt(i))\min_{i\in A_t}h_{\infty}(y_t^{(i)}) and at most ββ−1\frac{\beta}{\beta-1} times the mean of h∞(y<t(i))h_{\infty}(y_{<t}^{(i)}) over AtA_t, and at the sequence level H∞(pθ)≤Hα(pθ)≤αα−1H∞(pθ)H_{\infty}(p_{\theta}) \le H_{\alpha}(p_{\theta}) \le\frac{\alpha}{\alpha-1}H_{\infty}(p_{\theta}) with H∞=−log⁡max⁡ypθ(y∣x)H_{\infty}=-\log\max_y p_{\theta}(y\mid x).

(d) For β<1\beta<1 and a next-token distribution with top probability 1−ε1-\varepsilon, (1−ε)β+εβ≤e(1−β)hβ≤(1−ε)β+εβ(∣V∣−1)1−β(1-\varepsilon)^{\beta}+\varepsilon^{\beta}\le e^{(1-\beta)h_{\beta}}\le(1-\varepsilon)^{\beta}+\varepsilon^{\beta}(|V|-1)^{1-\beta}. The upper end is attained when the remaining probability mass is uniform and the lower end, for ε≤1/2\varepsilon\le1/2, when it sits on one token. For β=1\beta=1 the range of h1h_1 is [hb(ε),hb(ε)+εlog⁡(∣V∣−1)][h_b(\varepsilon),h_b(\varepsilon)+\varepsilon\log(|V|-1)] with hbh_b the binary entropy.

Proof. (a) Write pi=pθ(⋅∣x,y<t(i))p_i=p_{\theta}(\cdot\mid x,y_{<t}^{(i)}). Then

E[Xtβ−1]=1∣At∣∑i∈At∑vpi(v)pi(v)β−1=1∣At∣∑i∈Ate(1−β)hβ(y<t(i)),\mathbb{E}[X_t^{\beta-1}]=\frac{1}{|A_t|}\sum_{i\in A_t}\sum_v p_i(v)p_i(v)^{\beta-1}=\frac{1}{|A_t|}\sum_{i\in A_t}e^{(1-\beta)h_{\beta}(y_{<t}^{(i)})},

so the tt-th increment of (7) is 11−βlog⁡E[Xtβ−1]=−log⁡Mβ−1(Xt)\frac{1}{1-\beta}\log\mathbb{E}[X_t^{\beta-1}]=-\log M_{\beta-1}(X_t). For β=1\beta=1 the increment is 1∣At∣∑iH(pi)=E[−log⁡Xt]=−log⁡M0(Xt)\frac{1}{|A_t|}\sum_i H(p_i)=\mathbb{E}[-\log X_t]=-\log M_0(X_t).

(b) The power mean Mr(X)M_r(X) of a positive random variable is nondecreasing in rr, so each increment is nonincreasing in β\beta and so is the sum. As r→∞r\to\infty, Mr(Xt)→max⁡i,vpi(v)M_r(X_t)\to\max_{i,v}p_i(v), which gives min⁡ih∞(y<t(i))\min_i h_{\infty}(y_{<t}^{(i)}). As β→0\beta\to0 the increment tends to log⁡1∣At∣∑i∣supp⁡pi∣=log⁡∣V∣\log\frac{1}{|A_t|}\sum_i|\operatorname{supp}p_i|=\log|V| for a full-support softmax.

(c) Let m=max⁡vp(v)m=\max_v p(v). Then mβ≤∑vp(v)β≤mβ−1∑vp(v)=mβ−1m^{\beta}\le\sum_v p(v)^{\beta}\le m^{\beta-1}\sum_v p(v)=m^{\beta-1}. Applying 11−βlog⁡\frac{1}{1-\beta}\log, which reverses inequalities for β>1\beta>1, gives −log⁡m≤hβ≤ββ−1(−log⁡m)-\log m\le h_{\beta}\le\frac{\beta}{\beta-1}(-\log m). For the particle aggregate, write hi=hβ(y<t(i))h_i=h_{\beta}(y_{<t}^{(i)}) and hˉ\bar h for their mean over AtA_t. Convexity of x↦e(1−β)xx\mapsto e^{(1-\beta)x} gives

1∣At∣∑ie(1−β)hi≥e(1−β)hˉ,\frac{1}{|A_t|}\sum_i e^{(1-\beta)h_i}\ge e^{(1-\beta)\bar h},

so the increment is at most hˉ\bar h, which is at most ββ−1\frac{\beta}{\beta-1} times the mean of h∞h_{\infty}. Also

1∣At∣∑ie(1−β)hi≤e(1−β)min⁡ihi,\frac{1}{|A_t|}\sum_i e^{(1-\beta)h_i}\le e^{(1-\beta)\min_i h_i},

so the increment is at least min⁡ihi≥min⁡ih∞(y<t(i))\min_i h_i\ge\min_i h_{\infty}(y_{<t}^{(i)}). The sequence-level statement is the first display applied to pθ(⋅∣x)p_{\theta}(\cdot\mid x) over completions.

(d) Let the other probabilities be q1,…,qKq_1,\ldots,q_K with K=∣V∣−1K=|V|-1 and ∑jqj=ε\sum_jq_j=\varepsilon. For 0<β<10<\beta<1, x↦xβx\mapsto x^{\beta} is concave with value 0 at 0 and hence subadditive, so ∑jqjβ≥εβ\sum_jq_j^{\beta}\ge\varepsilon^{\beta}; by Jensen’s inequality ∑jqjβ≤K(ε/K)β=εβK1−β\sum_jq_j^{\beta}\le K(\varepsilon/K)^{\beta}=\varepsilon^{\beta}K^{1-\beta}. Adding (1−ε)β(1-\varepsilon)^{\beta} gives the two bounds. The β=1\beta=1 range follows from H(p)=hb(ε)+εH(q/ε)H(p)=h_b(\varepsilon)+\varepsilon H(q/\varepsilon) and 0≤H(q/ε)≤log⁡K0\le H(q/\varepsilon)\le\log K. □

The logged per-problem runs agree with the proposition. Part (b) and the bounds of part (c) hold in every one of the 5,500 per-problem runs that log the order spectrum. The order-4 increments, averaged over particles, sum to 1.25 times the corresponding top-token terms (median per setting between 1.249 and 1.257), inside the range [1,4/3][1,4/3]. The Spearman correlation of SREβSRE_{\beta} with the number of decoding steps rises to at least 0.93 at order 1/41/4, the direction of the β→0\beta\to0 limit.

Proof of Proposition 2

Conditioned on Y=yY=y, the number of independent draws from qq until yy first appears is geometric with mean 1/q(y)1/q(y), so the expected number of draws is ∑yp(y)/q(y)\sum_y p(y)/q(y), which is infinite when q(y)=0q(y)=0 for some yy with p(y)>0p(y)>0. By the Cauchy–Schwarz inequality,

eH1/2(p)=(∑yp(y)1/2)2=(∑yp(y)q(y)q(y))2≤∑yp(y)q(y)∑yq(y)=∑yp(y)q(y)e^{H_{1/2}(p)} = \left(\sum_y p(y)^{1/2}\right)^2 = \left(\sum_y \sqrt{\frac{p(y)}{q(y)}}\sqrt{q(y)}\right)^2 \le\sum_y \frac{p(y)}{q(y)}\sum_y q(y) = \sum_y \frac{p(y)}{q(y)}

with equality if and only if p(y)/q(y)∝q(y)p(y)/q(y) \propto q(y), that is, q∝p1/2q \propto p^{1/2}. Arikan [1] shows that the expected number of guesses when candidates are tried in order of decreasing probability lies between eH1/2(p)/(1+ln⁡M)e^{H_{1/2}(p)}/(1+\ln M) and eH1/2(p)e^{H_{1/2}(p)} for MM outcomes, so the same quantity governs guesswork.

Proposition 4 (Guesswork of the power distribution). For α>1\alpha> 1, Hα(pθ(⋅∣x))=H1/α(πα(⋅∣x))H_\alpha(p_\theta(\cdot|x)) = H_{1/\alpha}(\pi_\alpha(\cdot|x)). Consequently, if Y∼παY \sim\pi_\alpha takes MM values and G⋆(Y)G^\star(Y) is the number of guesses needed when completions are tried in order of decreasing probability,

eHα(pθ)1+ln⁡M≤(E[G⋆(Y)α−1])1α−1≤eHα(pθ).\frac{e^{H_\alpha(p_\theta)}}{1+\ln M} \le\left(\mathbb{E}[G^\star(Y)^{\alpha-1}]\right)^{\frac{1}{\alpha-1}} \le e^{H_\alpha(p_\theta)}.

Proof. ∑yπα(y)1/α=∑ypθ(y∣x)/Zα1/α=Zα−1/α\sum_y \pi_\alpha(y)^{1/\alpha} = \sum_y p_\theta(y|x)/Z_\alpha^{1/\alpha} = Z_\alpha^{-1/\alpha}, so H1/α(πα)=11−1/αlog⁡Zα−1/α=11−αlog⁡Zα=Hα(pθ)H_{1/\alpha}(\pi_\alpha) = \frac{1}{1-1/\alpha}\log Z_\alpha^{-1/\alpha} = \frac{1}{1-\alpha}\log Z_\alpha= H_\alpha(p_\theta). The inequality of Arikan [1], for any ρ>0\rho> 0 and any distribution PP on MM outcomes, reads (1+ln⁡M)−ρeρH1/(1+ρ)(P)≤E[G⋆(X)ρ]≤eρH1/(1+ρ)(P)(1+\ln M)^{-\rho}e^{\rho H_{1/(1+\rho)}(P)} \le\mathbb{E}[G^\star(X)^\rho] \le e^{\rho H_{1/(1+\rho)}(P)}. Take P=παP=\pi_\alpha and ρ=α−1\rho=\alpha-1, so that 1/(1+ρ)=1/α1/(1+\rho)=1/\alpha, substitute the identity, and take the power 1/ρ1/\rho.

Proof of Lemma 1

Let γt(y1:t)\gamma_t(y_{1:t}), t=0,…,Tt=0,\ldots,T, be the positive unnormalized intermediate targets of the sampler, with γ0=1\gamma_0=1 and γT(y)=pθ(y∣x)α\gamma_T(y)=p_\theta(y|x)^\alpha, let qt(⋅∣y<t)q_t(\cdot|y_{<t}) be the proposals, and let ωt=γt(y1:t)/[γt−1(y<t)qt(yt∣y<t)]\omega_t=\gamma_t(y_{1:t})/[\gamma_{t-1}(y_{<t})q_t(y_t|y_{<t})] be the incremental weights. Resampling is unbiased: the expected number of copies of particle jj is NN times its normalized weight. Power-SMC is the case γt=pθ(y1:t∣x)αt\gamma_t=p_\theta(y_{1:t}|x)^{\alpha_t} with the exponent ramp αt\alpha_t of Appendix § 13, a nucleus-truncated proposal, and systematic resampling at block boundaries when the effective sample size is below N/2N/2.

Proof. Write the particle system after step tt as (y1:t(i),wt(i))i≤N(y_{1:t}^{(i)},w_t^{(i)})_{i\le N}, where ww is the unnormalized weight accumulated since the last resampling event, and let CtC_t be the product of the averages taken at the resampling events so far,

Ct=1N∑kw(k)C_t = \frac{1}{N}\sum_k w^{(k)}

taken at the resampling events so far (C0=1C_0=1, w0(i)=1w_0^{(i)}=1). By the telescoping of Appendix § 13, Z^α,N=CT1N∑iwT(i)\widehat{Z}_{\alpha,N}=C_T\frac{1}{N}\sum_i w_T^{(i)}. For a function φ\varphi of length-tt prefixes put

Φt(φ)=Ct1N∑iwt(i)φ(y1:t(i)),γt(φ)=∑y1:t∈Stγt(y1:t)φ(y1:t),\Phi_t(\varphi)=C_t\frac{1}{N}\sum_i w_t^{(i)}\varphi(y_{1:t}^{(i)}), \qquad \gamma_t(\varphi)=\sum_{y_{1:t}\in S_t}\gamma_t(y_{1:t})\varphi(y_{1:t}),

where StS_t is the set of prefixes that the proposals can produce. We show E[Φt(φ)]=γt(φ)\mathbb{E}[\Phi_t(\varphi)]=\gamma_t(\varphi) for all tt and φ\varphi by induction; for t=0t=0 both sides equal φ(∅)\varphi(\emptyset).

Propagation. Given the system after step t−1t-1, whose history we denote Ft−1\mathcal{F}_{t-1}, particle ii draws yt(i)∼qt(⋅∣y<t(i))y_t^{(i)}\sim q_t(\cdot|y_{<t}^{(i)}) and wt(i)=wt−1(i)ωtw_t^{(i)}=w_{t-1}^{(i)}\omega_t, so E[wt(i)φ(y1:t(i))∣Ft−1]=wt−1(i)φ~(y<t(i))\mathbb{E}[w_t^{(i)}\varphi(y_{1:t}^{(i)})\mid\mathcal{F}_{t-1}]=w_{t-1}^{(i)}\widetilde{\varphi}(y_{<t}^{(i)}) with

φ~(y<t)=∑v:qt(v∣y<t)>0γt(y<t,v)γt−1(y<t)φ(y<t,v).\widetilde{\varphi}(y_{<t})=\sum_{v:q_t(v|y_{<t})>0}\frac{\gamma_t(y_{<t},v)}{\gamma_{t-1}(y_{<t})}\varphi(y_{<t},v).

Hence E[Φt(φ)∣Ft−1]=Φt−1(φ~)\mathbb{E}[\Phi_t(\varphi)\mid\mathcal{F}_{t-1}]=\Phi_{t-1}(\widetilde{\varphi}), whose expectation is γt−1(φ~)=γt(φ)\gamma_{t-1}(\widetilde{\varphi})=\gamma_t(\varphi) by the induction hypothesis. A finished particle is the special case of a deterministic extension, and the final exponent correction of the ramp is a reweighting by γ′(y)/γ(y)\gamma'(y)/\gamma(y) with no new token, for which E[Φ′(φ)]=γ(φγ′/γ)=γ′(φ)\mathbb{E}[\Phi'(\varphi)]=\gamma(\varphi\gamma'/\gamma)=\gamma'(\varphi).

Resampling. The decision to resample is a function of the system at time tt. If it is taken, the new particles are y^(i)=y(Ai)\widehat{y}^{(i)}=y^{(A_i)} with unit weights and C^=Ct1N∑kwt(k)\widehat{C}=C_t\frac{1}{N}\sum_k w_t^{(k)}. Since the expected number of copies of particle jj is Nwt(j)/∑kwt(k)Nw_t^{(j)}/\sum_k w_t^{(k)},

E[C^1N∑iφ(y^(i))|Ft]=Φt(φ),\mathbb{E}\left[\widehat{C}\frac{1}{N}\sum_i\varphi(\widehat{y}^{(i)})\middle|\mathcal{F}_t\right]=\Phi_t(\varphi),

so the claim is preserved.

Item 1. With φ≡1\varphi\equiv1 at t=Tt=T, E[Z^α,N]=γT(1)=∑y∈STpθ(y∣x)α≤Zα\mathbb{E}[\widehat{Z}_{\alpha,N}]=\gamma_T(1)=\sum_{y\in S_T}p_\theta(y|x)^\alpha\le Z_\alpha, with equality when the proposals have full support.

Item 2. By Jensen’s inequality E[log⁡Z^α,N]≤log⁡E[Z^α,N]≤log⁡Zα\mathbb{E}[\log\widehat{Z}_{\alpha,N}]\le\log\mathbb{E}[\widehat{Z}_{\alpha,N}]\le\log Z_\alpha; multiplying by 1/(1−α)<01/(1-\alpha)<0 reverses the inequality.

Item 3. By Markov’s inequality Pr⁡[Z^α,N≥Zα/δ]≤δE[Z^α,N]/Zα≤δ\Pr[\widehat{Z}_{\alpha,N}\ge Z_\alpha/\delta]\le\delta\mathbb{E}[\widehat{Z}_{\alpha,N}]/Z_\alpha\le\delta. On the complement log⁡Z^α,N<log⁡Zα+log⁡(1/δ)\log\widehat{Z}_{\alpha,N}<\log Z_\alpha+\log(1/\delta), and dividing by 1−α<01-\alpha<0 gives SRE^α,N>Hα(pθ)−log⁡(1/δ)/(α−1)\widehat{\mathrm{SRE}}_{\alpha,N}>H_\alpha(p_\theta)-\log(1/\delta)/(\alpha-1).

Consistency. With full-support proposals and multinomial resampling at fixed times, Z^α,N→Zα\widehat{Z}_{\alpha,N}\to Z_\alpha in probability for a fixed horizon (Del Moral, [7]; Chopin and Papaspiliopoulos, [3]), and the continuous mapping theorem applied to 11−αlog⁡\frac{1}{1-\alpha}\log gives the limit of SRE^α,N\widehat{\mathrm{SRE}}_{\alpha,N}. □\square

Generality Beyond Power-SMC

The estimator requires only the incremental weights wt(i)w_t^{(i)} of a sampler whose final target is the power distribution πα\pi_\alpha and whose resampling is unbiased. For any such sampler, Lemma 1 applies to the estimate of ZαZ_\alpha from the weights, from which SRE=log⁡Z^α/(1−α)SRE = \log\widehat{Z}_\alpha/(1-\alpha).

APPS. APPS [21] is a blockwise auxiliary-particle sampler. Its propagation step assigns each particle the proposal-corrected power weight

log⁡w(i)+=αlog⁡pθ(bj(i)∣xprev(i))−log⁡qj(bj(i)∣xprev(i))\log w^{(i)} \mathrel{+}= \alpha\log p_\theta\left(b_j^{(i)} \mid x_{\mathrm{prev}}^{(i)}\right) - \log q_j\left(b_j^{(i)} \mid x_{\mathrm{prev}}^{(i)}\right)

for block bj(i)b_j^{(i)} under proposal qjq_j. These are the incremental weights of an SMC sampler whose final target is pθαp_\theta^\alpha, so the estimator applies with no extra model calls. Lemma 1 holds for arbitrary positive intermediate targets, so the future-value potential that APPS uses at resampling boundaries changes the intermediate targets only. The estimator accumulates, at each resampling step, the average of the weights that the sampler resamples with, and the potentials cancel in the product because the final potential is 1. The estimand is ZαZ_\alpha.

Rollout-based power sampling. Scalable Power Sampling [13] samples autoregressively from pα(pow)(xt∣⋅)∝pθ(xt∣⋅)αζt(xt)p_\alpha^{(\mathrm{pow})}(x_t \mid\cdot) \propto p_\theta(x_t \mid\cdot)^\alpha\zeta_t(x_t) with a future-value factor ζt\zeta_t estimated by rollouts. Each per-token normalizer is Γt(y<t)=∑vpθ(v∣y<t)αζt(y≤t,v)\Gamma_t(y_{<t}) = \sum_v p_\theta(v \mid y_{<t})^\alpha\zeta_t(y_{\leq t}, v). With the exact future value ζt(y≤t)=∑y>tpθ(y>t∣y≤t)α\zeta_t(y_{\leq t}) = \sum_{y_{>t}} p_\theta(y_{>t} \mid y_{\leq t})^\alpha the first normalizer is the sequence-level normalizing constant, Γ1=∑vpθ(v)α∑y>1pθ(y>1∣v)α=Zα\Gamma_1 = \sum_v p_\theta(v)^\alpha\sum_{y_{>1}} p_\theta(y_{>1} \mid v)^\alpha= Z_\alpha, so SRE=11−αlog⁡Γ1SRE = \frac{1}{1-\alpha}\log\Gamma_1 is available after the rollouts of the first step. With estimated future values the sampler draws yy with probability q(y)=∏tpθ(yt∣y<t)αζt(y≤t)/Γt(y<t)q(y) = \prod_t p_\theta(y_t \mid y_{<t})^\alpha\zeta_t(y_{\leq t})/\Gamma_t(y_{<t}), and

Ey∼q[∏tΓt(y<t)ζt(y≤t)]=∑y∏tpθ(yt∣y<t)α=Zα,\mathbb{E}_{y\sim q}\left[\prod_t \frac{\Gamma_t(y_{<t})}{\zeta_t(y_{\leq t})}\right] = \sum_y \prod_t p_\theta(y_t \mid y_{<t})^\alpha= Z_\alpha,

so the mean of this weight over the sampled completions is an unbiased estimate of ZαZ_\alpha from quantities the method already computes.

Sensitivity to the Sharpening Exponent

Length Control

Table 15 applies the same length control to every signal: the AUROC is computed over correct–

incorrect pairs inside the same quartile of generation length. SRE1/2SRE_{1/2} is above sequence log-probability inside length quartiles in all eight settings, by 0.020 to 0.052, and SRE1SRE_1 in seven. SRE1/2SRE_{1/2} is usually less driven by length than log-probability: its Spearman correlation with the length of the returned completion is lower than that of log-probability in six of the eight settings. Removing the problems whose decoding reaches the 2,048-token limit (82 of 500 for Llama-3.1-8B on MATH500, at most 27 elsewhere) leaves SRE1/2SRE_{1/2} above sequence log-probability in all eight settings, by 0.015 to 0.048.

Full Adaptive Particle Allocation Sweep

Table 18 repeats the experiment with three seeds. Over the three seeds, the mid and high terciles gain more than the low tercile in 99.4% of 10,000 bootstrap replicates of the problems. On Qwen2.5-Math-1.5B (N=8N=8: 67.2%, N=64N=64: 70.6%) the tercile gains are +0.6, +3.6, and +6.0. The savings statistic of Table 18 is 34.2% for SREαSRE_\alpha and SRE1SRE_1, 32.5% for the standard estimator, sequence logprobability and Self-Certainty, 22.5% for SRE1/2SRE_{1/2}, 20.8% for answer entropy, 7.5% for mean token entropy, and −0.8% for random escalation (mean of 5,000 random orders); SREαSRE_{\alpha}, SRE1SRE_{1}, the standard estimator and log-probability are the only gating signals with a positive saving on all three seeds. With one escalation rate for all seeds, escalating the 60% highest-SREαSRE_{\alpha} problems gives the three-seed mean accuracy of uniform N=64N=64 (76.6%) with 27.5% fewer particles, and 50% gives 76.5% with 37.5% fewer.

Table 19 reports the full threshold sweep behind Table 17. Every escalation rate from 40% to 100% matches or exceeds uniform N=64N=64 accuracy (77.2%).

MethodAcc (%)ComputeSavings
Uniform N=8N=874.81.0×—
Uniform N=32N=3275.84.0×—
Adaptive (Esc. 30%)76.43.4×57.5%
Adaptive (Esc. 40%)77.24.2×47.5%
Adaptive (Esc. 45%)77.84.6×42.5%
Adaptive (Esc. 70%)77.86.6×17.5%
Uniform N=64N=6477.28.0×0%

Table 17. Adaptive particle allocation vs. uniform baselines on MATH500 (500 problems, Qwen2.5-Math-7B). Esc. X%X\%: escalate the X%X\% of problems with the highest SREαSRE_{\alpha} to N=64N=64. Compute is in N=8N=8 units and adaptive rows include the probe cost. Savings are relative to uniform N=64N=64.

Three-Way Policy: Answer, Escalate, or Abstain

The probe signal can drive a three-way decision. We rank problems by probe SREαSRE_{\alpha}, abstain on the most uncertain ones, escalate the next e%e\% of all problems to N=64N=64, and keep the probe answer for the rest. Table 20 reports the accuracy on the answered problems, averaged over three seeds, against uniform N=64N=64, which abstains by its own

PolicyComputeAccuracy at coverage
80%60%
Probe only (N=8N=8)1.0×84.289.2
Three-way, e=20e=202.6×84.590.0
Three-way, e=40e=404.2×85.190.3
Uniform N=64N=648.0×85.089.9

Table 20. Three-way policy on MATH500 (500 problems, Qwen2.5-Math-7B, α=4\alpha=4, mean over three seeds). Accuracy (%) on the answered problems when the policy abstains on the most uncertain 20% or 40%. Compute is in N=8N=8 units and includes the probe.

SeedAccuracy N=8N=8Accuracy N=64N=64Gain by tercile LowGain by tercile MidGain by tercile HighSavings
4274.877.2−1.2+3.0+5.447.5%
4375.876.4−0.6+3.0+0.622.5%
4474.876.2+0.0+1.2+3.032.5%
Mean75.176.6−0.6+2.4+2.634.2%

Table 18. Adaptive particle allocation with three seeds (MATH500, 500 problems, Qwen2.5-Math-7B, α=4\alpha=4). Gain: accuracy at N=64N=64 minus accuracy at N=8N=8 within each tercile of probe SREαSRE_{\alpha}. Savings: particles saved relative to uniform N=64N=64 at the smallest escalation rate from which the two-pass policy matches uniform N=64N=64 accuracy.

SREαSRE_{\alpha}. At 80% coverage the three-way policy with 40% escalation matches uniform N=64N=64 with 47.5% fewer particles, and at 60% coverage 20% escalation suffices.

Esc.AccComp.Esc.AccComp.
0%74.81.0×55%77.65.4×
5%74.61.4×60%77.45.8×
10%75.21.8×65%77.66.2×
15%75.42.2×70%77.86.6×
20%76.42.6×75%77.67.0×
25%76.63.0×80%77.67.4×
30%76.43.4×85%77.67.8×
35%77.03.8×90%77.48.2×
40%77.24.2×95%77.48.6×
45%77.84.6×100%77.29.0×
50%77.85.0×

Table 19. Accuracy (%) and average compute (in N=8N=8 units, probe included) as a function of the fraction of highest-SREαSRE_{\alpha} problems escalated to N=64N=64 (MATH500, 500 problems, Qwen2.5-Math-7B). Uniform N=64N=64: 77.2% at 8.0×.

References

  1. [1]Erdal Arıkan. 1996. An inequality on guessing and its application to sequential decoding. IEEE Transactions on Information Theory, 42(1):99–105.DOI
  2. [2]Seyedamin Azizi, Erfan Baghaei Potraghloo, Minoo Ahmadi, Souvik Kundu, and Massoud Pedram. 2026. Power-smc: Low-latency sequence-level power sampling for training-free llm reasoning. Preprint, arXiv:2602.10273.
  3. [3]N. Chopin and O. Papaspiliopoulos. 2020. An Introduction to Sequential Monte Carlo. Springer Series in Statistics. Springer International Publishing.DOI
  4. [4]Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. Preprint, arXiv:2110.14168.arxiv.org/abs/2110.14168
  5. [5]Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory, 2 edition. Wiley-Interscience, Hoboken, NJ.
  6. [6]Maxime Darrin, Pablo Piantanida, and Pierre Colombo. 2023. RainProof: An umbrella to shield text generator from out-of-distribution data. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 5831–5857.
  7. [7]Pierre Del Moral. 2004. Feynman-Kac Formulae: Genealogical and Interacting Particle Systems With Applications, volume 100.DOI
  8. [8]Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravanakumar, Artem Korneev, Arthur Hinsvark, Arun Rao, Aston Zhang, and 516 others. 2024. The llama 3 herd of models. Preprint, arXiv:2407.21783.arxiv.org/abs/2407.21783
  9. [9]Sebastian Farquhar, Jannik Kossen, Lorenz Kuhn, and Yarin Gal. 2024. Detecting hallucinations in large language models using semantic entropy. Nature, 630:625 – 630.DOI
  10. [10]Yichao Fu, Junda Chen, Siqi Zhu, Zheyu Fu, Zhongdongming Dai, Yonghao Zhuang, Yian Ma, Aurick Qiao, Tajana Rosing, Ion Stoica, and Hao Zhang. 2025. Efficiently scaling LLM reasoning programs with certindex. In Advances in Neural Information Processing Systems.DOI
  11. [11]Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874.
  12. [12]Chengsong Huang, Langlin Huang, Jixuan Leng, Jiacheng Liu, and Jiaxin Huang. 2026. CaTS: Calibrated test-time scaling for efficient LLM reasoning. In International Conference on Learning Representations.
  13. [13]Xiaotong Ji, Rasul Tutunov, Matthieu Zimmer, and Haitham Bou Ammar. 2026. Scalable power sampling: Unlocking efficient, training-free reasoning for llms via distribution sharpening. Preprint, arXiv:2601.21590.arxiv.org/abs/2601.21590
  14. [14]Petr Jizba and Toshihico Arimitsu. 2004. The world according to Rényi: thermodynamics of multifractal systems. Annals of Physics, 312(1):17–59.
  15. [15]Saurav Kadavath, Tom Conerly, Amanda Askell, Thomas Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zachary Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, and 17 others. 2022. Language models (mostly) know what they know. ArXiv, abs/2207.05221.arxiv.org/abs/2207.05221
  16. [16]Zhewei Kang, Xuandong Zhao, and Dawn Song. 2025. Scalable best-of-n selection for large language models via self-certainty. In Advances in Neural Information Processing Systems.arxiv.org/abs/2502.18581
  17. [17]Aayush Karan and Yilun Du. 2026. Reasoning with sampling: Your base model is smarter than you think. In The Fourteenth International Conference on Learning Representations.arxiv.org/abs/2510.14901
  18. [18]Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. 2023. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. Preprint, arXiv:2302.09664.arxiv.org/abs/2302.09664
  19. [19]Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. 2023. Let’s verify step by step. arXiv preprint arXiv:2305.20050.arxiv.org/abs/2305.20050
  20. [20]Andrey Malinin and Mark Gales. 2021. Uncertainty estimation in autoregressive structured prediction. In International Conference on Learning Representations.arxiv.org/abs/2002.07650
  21. [21]Tu Nguyen, Matthieu Zimmer, Rasul Tutunov, Xiaotong Ji, and Haitham Bou Ammar. 2026. The model knows, the decoder finds: Future value guided particle power sampling. Preprint, arXiv:2605.02427.
  22. [22]Qwen Team, Anyang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Daiyiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, and 24 others. 2025. Qwen2.5 technical report. Preprint, arXiv:2412.15115.
  23. [23]Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. 2024. Scaling llm test-time compute optimally can be more effective than scaling model parameters. Preprint, arXiv:2408.03314.arxiv.org/abs/2408.03314
  24. [24]Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations.arxiv.org/abs/2203.11171
  25. [25]An Yang and 1 others. 2025. Qwen3 technical report. Preprint, arXiv:2505.09388.arxiv.org/abs/2505.09388
  26. [26]Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Yang Yue, Shiji Song, and Gao Huang. 2025. Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model? In The Thirty-ninth Annual Conference on Neural Information Processing Systems.arxiv.org/abs/2504.13837

Paper details

vlnc:W_z5vmd6zg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents