Free Lunch Uncertainty: Sequence-Level R'enyi Entropy from Particle Decoding for Adaptive LLM Reasoning
cs.LG, cs.AI, cs.CL
Submitted: 2026-11-10
Updated: 2026-11-10
License: http://creativecommons.org/licenses/by/4.0/
The gist: Quantifying uncertainty over an entire LLM completion is critical for selective prediction and adaptive compute.
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.
Sources
- Power-SMC: Low-Latency Sequence-Level Power Sampling for Training-Free LLM Reasoning
- Training Verifiers to Solve Math Word Problems
- The Llama 3 Herd of Models
- Measuring Mathematical Problem Solving With the MATH Dataset
- Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening
- Language Models (Mostly) Know What They Know
- Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation
- Let's Verify Step by Step
- The Model Knows, the Decoder Finds: Future Value Guided Particle Power Sampling
- Qwen2.5 Technical Report
- Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
- Qwen3 Technical Report
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis