Free Lunch Uncertainty: Sequence-Level Rényi Entropy from Particle Decoding for Adaptive LLM Reasoning
Organizations: University of Southern California · 2Purdue University · 3Intel
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.
Figures & tables
| MATH500 | GSM8K | |||||||
| Signal | M-1.5B | M-7B | Q-7B | Llama | M-1.5B | M-7B | Q-7B | Llama |
| (ours) | .836 | .850 | .834 | .884 | .776 | .782 | .658 | .743 |
| (ours) | .825 | .821 | .824 | .866 | .760 | .779 | .686 | .733 |
| (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 |
| Tercile | Gain | ||||
|---|---|---|---|---|---|
| Low | 167 | 94.0 | 93.4 | 92.8 | 1.2 |
| Mid | 166 | 83.7 | 84.3 | 86.7 | 3.0 |
| High | 167 | 46.7 | 49.7 | 52.1 | 5.4 |
| All | 500 | 74.8 | 75.8 | 77.2 | 2.4 |
Appendix figures & tables20 assets
Supplementary material from the paper’s appendix.
Appendix
| Model | MATH500 | GSM8K |
|---|---|---|
| Qwen2.5-Math-1.5B | 69.0 | 80.8 |
| Qwen2.5-Math-7B | 75.8 | 86.2 |
| Qwen2.5-7B | 71.8 | 85.0 |
| Llama-3.1-8B-Instruct | 50.2 | 85.2 |
| Lvl | TokEnt | Acc | ||
|---|---|---|---|---|
| 1 | 43 | 12.8 | 0.088 | 0.91 |
| 2 | 90 | 16.4 | 0.077 | 0.87 |
| 3 | 105 | 20.8 | 0.089 | 0.87 |
| 4 | 128 | 24.2 | 0.085 | 0.73 |
| 5 | 134 | 32.6 | 0.090 | 0.57 |
| Signal | M-1.5B | M-7B | Q-7B | Llama |
|---|---|---|---|---|
| (ours) | +0.461 | +0.447 | +0.480 | +0.499 |
| (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 |
| Method | Level | Extra cost |
|---|---|---|
| Token ent. | Token | Free |
| Seq log-prob | Single path | Free |
| Self-Certainty | Token dist. | Free |
| Self-cons. | Answer | gens |
| Certaindex | Answer | gens |
| Sem. ent. | Ans. clust. | + clust. |
| Model, | LogP | Std. | Step. | Fam. | |||
|---|---|---|---|---|---|---|---|
| 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 |
| Transition | Mean probe | |
|---|---|---|
| Stayed correct | 358 | 19.3 |
| Flipped to correct | 28 | 34.2 |
| Flipped to wrong | 16 | 31.9 |
| Stayed wrong | 98 | 41.1 |
| Model | Signal | AUROC [95% CI] | vs. LogP |
|---|---|---|---|
| M-1.5B | .836 [.797, .871] | .002 ∗∗ | |
| .825 [.784, .862] | .007 ∗∗ | ||
| .816 [.774, .854] | .035 ∗ | ||
| Seq log-prob | .810 [.767, .848] | — | |
| Self-cons. † | .656 [.613, .699] | ||
| Token entropy | .714 [.663, .764] |
| Model | Signal | AUROC [95% CI] | vs. LogP |
|---|---|---|---|
| M-1.5B | .776 [.725, .823] | .020 ∗ | |
| .760 [.706, .811] | .049 ∗ | ||
| .748 [.693, .800] | .251 | ||
| Seq log-prob | .744 [.689, .795] | — | |
| Self-cons. † | .718 [.664, .770] | .575 | |
| Token entropy | .728 [.666, .788] | .519 |
| Signal | Q2.5-14B | Q3-4B |
|---|---|---|
| (ours) | .863 | .864 |
| (ours) | .867 | .856 |
| (ours) | .866 | .846 |
| Seq log-prob | .860 | .837 |
| Self-cons. † | .609 | .593 |
| Mean token entropy | .536 | .746 |
| MATH500 | GSM8K | |||||||
| Signal | M-1.5B | M-7B | Q-7B | Llama | M-1.5B | M-7B | Q-7B | Llama |
| (ours) | 11.9 | 8.0 | 10.2 | 23.3 | 7.7 | 5.2 | 9.1 | 7.4 |
| (ours) | 12.5 | 9.0 | 10.8 | 24.6 | 8.6 | 5.0 | 8.1 | 7.8 |
| (ours) | 12.9 | 9.5 | 11.6 | 24.8 | 8.9 | 5.6 | 10.3 | 8.6 |
| Seq log-prob | 13.0 | 9.3 | 12.2 | 25.0 | 8.8 | 5.9 | 10.5 | 9.0 |
| Self-cons. † | 23.6 | 16.3 | 21.6 | 47.3 | 11.9 | 8.4 | 9.6 | 11.0 |
| Mean CV | Median CV | Split-half | |
|---|---|---|---|
| 8 | 11.1% | 8.3% | 0.993 |
| 32 | 7.8% | 4.7% | 0.993 |
| MATH500 | GSM8K | |||
|---|---|---|---|---|
| Length quartile | Low | High | Low | High |
| Q1 (shortest) | 96.8 | 69.4 | 95.2 | 66.1 |
| Q2 | 95.2 | 77.4 | 100.0 | 82.3 |
| Q3 | 92.1 | 67.7 | 95.2 | 82.3 |
| Q4 (longest) | 73.0 | 33.9 | 92.1 | 75.8 |
| MATH500 | GSM8K | |||||||
|---|---|---|---|---|---|---|---|---|
| Signal | M-1.5B | M-7B | Q-7B | Llama | M-1.5B | M-7B | Q-7B | Llama |
| (ours) | .821 | .823 | .804 | .741 | .781 | .795 | .701 | .742 |
| (ours) | .813 | .789 | .789 | .708 | .757 | .811 | .731 | .721 |
| (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 |
| Math-7B | M-1.5B | ||||
|---|---|---|---|---|---|
| Gating signal | s42 | s43 | s44 | mean | s42 |
| (ours) | 77.01 | 76.26 | 75.68 | 76.31 | 69.39 |
| (ours) | 76.88 | 76.10 | 75.81 | 76.26 | 69.19 |
| (ours) | 76.84 | 76.17 | 75.76 | 76.26 | 69.27 |
| Seq log-prob | 76.76 | 76.11 | 75.75 | 76.21 | 69.25 |
| Answer entropy | 76.69 | 76.26 | 76.75 | 76.57 | 69.10 |
| Method | Acc (%) | Compute | Savings |
| Uniform | 74.8 | — | |
| Uniform | 75.8 | — | |
| Adaptive (Esc. 30%) | 76.4 | 57.5% | |
| Adaptive (Esc. 40%) | 77.2 | 47.5% | |
| Adaptive (Esc. 45%) | 77.8 | 42.5% | |
| Adaptive (Esc. 70%) | 77.8 | 17.5% |
| Accuracy | Gain by tercile | |||||
|---|---|---|---|---|---|---|
| Seed | Low | Mid | High | Savings | ||
| 42 | 74.8 | 77.2 | 1.2 | 3.0 | 5.4 | 47.5% |
| 43 | 75.8 | 76.4 | 0.6 | 3.0 | 0.6 | 22.5% |
| 44 | 74.8 | 76.2 | 0.0 | 1.2 | 3.0 | 32.5% |
| Mean | 75.1 | 76.6 | 0.6 | 2.4 | 2.6 | 34.2% |
| Esc. | Acc | Comp. | Esc. | Acc | Comp. |
|---|---|---|---|---|---|
| 0% | 74.8 | 55% | 77.6 | ||
| 5% | 74.6 | 60% | 77.4 | ||
| 10% | 75.2 | 65% | 77.6 | ||
| 15% | 75.4 | 70% | 77.8 | ||
| 20% | 76.4 | 75% | 77.6 | ||
| 25% | 76.6 | 80% | 77.6 |
| Accuracy at coverage | |||
|---|---|---|---|
| Policy | Compute | 80% | 60% |
| Probe only ( ) | 84.2 | 89.2 | |
| Three-way, | 84.5 | 90.0 | |
| Three-way, | 85.1 | 90.3 | |
| Uniform | 85.0 | 89.9 | |
LLM Uncertainty Estimation
Large language model uncertainty estimation measures when outputs may be wrong, ambiguous, or unreliable to guide safer decisions.
See all 416 papers