cs.LGNov 10, 2026

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

Authors: Erfan Baghaei Potraghloo, Milad Heidari Sorkhehdizaj, Shahab Rahimirad, Aliasghar Pourghani, Seyedarmin Azizi, Souvik Kundu, Abolfazl Hashemi, Joseph Campbell, 

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

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 10, 2026

Entropy-informed Decoding: Adaptive Information-Driven Branching

Large language models (LLMs) achieve remarkable generative performance, yet their output quality is dependent on the decoding strategy. While sampling-based methods (e.g., top-k, nucleus) and search-and-select based methods (e.g., beam search, best-of-n, majority voting) can improve upon greedy decoding, both approaches suffer from limitations: sampling generally commits to a single path, while search often expends excessive computation regardless of task complexity. To address these, we introduce Entropy-informed decoding (EDEN), a plug-and-play, model-agnostic decoding framework that adaptively allocates computation based on the model's own uncertainty, approximating higher-width beam search with fewer expansions. At each generation step, EDEN estimates the entropy of the output token distribution and adjusts the branching factor monotonically with the entropy, expanding more candidates in high-entropy regions and following a greedier path in low-entropy regions, improving token efficiency. Experiments across complex tasks, including mathematical reasoning, code generation, and scientific questions, demonstrate that EDEN consistently improves output quality over existing decoding strategies, achieving better accuracy-expansion trade-offs than fixed-width beam search. By treating next-token selection as a noisy maximisation problem, we prove that branching factors monotone in entropy are guaranteed to find better (i.e. more probable) continuations than any fixed branching factor within the same total expansion budget, and derive explicit regret rates characterising the benefit of the adaptive allocation.
May 20, 2026

When Should LLMs Reason? Adaptive Inference Routing via Entropy Dynamics

Chain-of-thought (CoT) reasoning can improve LLM performance, but its benefits vary across tasks, models, and individual queries. On some tasks, CoT provides marginal or negative accuracy gains while substantially increasing token consumption. We investigate whether early decoding dynamics can help identify when explicit reasoning is useful. Our analysis shows that tasks with larger CoT gains tend to exhibit decreasing early-stage entropy, while low-gain tasks more often show oscillatory or increasing trajectories. These patterns motivate an empirical regime interpretation of decoding behavior. We propose EDRM (Entropy Dynamics-based Reasoning Manifold), a lightweight routing framework whose default heuristic requires no router training. EDRM summarizes early entropy trajectories with a compact, interpretable representation and selects among Direct, Standard, and CoT decoding. Across 15 benchmarks and 7 LLMs, its global and instance-level variants offer 16--55% token savings at comparable accuracy. The Full instance-level configuration combines routing with a short Direct fallback branch; our heuristic-router ablation reports up to 4.9 percentage points of additional accuracy from oracle answer selection over routing without fallback. These results support selective reasoning based on early decoding signals and demonstrate the potential of entropy-based control for efficient LLM inference.
Aug 20, 2026

Forking Fast: Efficiently Estimating Uncertainty Dynamics in Text Generation

LLM reasoning is stochastic, and so understanding a model requires grappling with the distribution of reasoning chains that it might produce for a given question, i.e., its uncertainty. Resampling-based analyses characterize this distribution, revealing which steps of a rollout determine how the model arrives at its answer. However, a major limitation of these approaches is that resampling text sequences at every token or sentence in a reasoning chain is very costly. Our work strives to make resampling analysis more computationally efficient, while also shedding light on an important scientific question: what is the right statistical model for explaining uncertainty dynamics in text generation? We show that when resampling many reasoning chains, uncertainty dynamics converge to stable patterns, and noise is largely an artifact of sampling rather than an LLM's sensitivity to each individual token or reasoning step. We develop a statistical model for smoothing noisy low-sample rollout data to better approximate high-sample data, allowing us to significantly cut sampling costs.