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

Erfan Baghaei Potraghloo, Milad Heidari Sorkhehdizaj, Shahab Rahimirad, Aliasghar Pourghani, Seyedarmin Azizi, Souvik Kundu, Abolfazl Hashemi, Joseph Campbell, Vijay GuptaarXiv 2026 · arXiv

TL;DR

This paper introduces Sequence-Level Rényi Entropy (SRE), a "zero-cost" uncertainty signal for LLMs that can be extracted directly from Sequential Monte Carlo (SMC) decoding. By using a cheap 8-particle probe to measure SRE, the authors implement an adaptive reasoning policy that matches the accuracy of expensive 64-particle decoding while saving over 34% of the total compute.

What Problem Does This Paper Address?

Quantifying how "sure" an LLM is about a long reasoning chain is notoriously difficult. Standard signals like token-level entropy or sequence log-probability are often insufficient. Token entropy is too local, and log-probability only looks at a single path, failing to distinguish between a clear winner and a "messy" distribution with many competing high-probability answers.

While methods like self-consistency (sampling many answers and checking for agreement) work well, they are computationally expensive. Furthermore, most LLM inference uses a fixed compute budget per problem, which is inefficient: easy problems get more compute than they need, while hard problems don't get enough. The authors sought a way to get a high-quality, sequence-level uncertainty signal without the overhead of extra model calls.

Methods

The researchers leverage Sequential Monte Carlo (SMC) decoding, a technique where $N$ parallel "particles" (candidate completions) are extended token-by-token and resampled based on importance weights.

The "aha" moment comes from the realization that the math for uncertainty is already happening inside the SMC sampler. Specifically:

  1. Normalizing Constant ($Z_\alpha$): SMC naturally estimates the normalizing constant of the distribution it samples from.
  2. SRE Extraction: The authors show that this constant can be transformed into Sequence-Level Rényi Entropy (SRE). Because the importance weights are already calculated during standard SMC decoding, extracting SRE costs essentially nothing—just one scalar accumulation per step.
  3. The Rényi Chain Rule: They derive a chain rule that allows them to calculate SRE at different "orders" ($\beta$). They find that order-1/2 (SRE$_{1/2}$) is particularly powerful because it mathematically represents the "search effort" required to find the correct completion.
Figure 1: Overview of adaptive particle allocation us- ing SRE. SMC importance weights from an initial low- budget probe run are used to estimate the normalizing constant Zα(x) and from it the sequence-level Rényi entropy. High-SRE problems are re-run with a larger particle budget (N = 64), while low-SRE problems keep the probe answer.

Datasets

The authors evaluated their approach on two primary mathematical reasoning benchmarks:

  • MATH500: A subset of the challenging MATH dataset.
  • GSM8K: Grade school math word problems.

They tested across several open-weight model families, including Qwen2.5-Math (1.5B and 7B), Qwen2.5-7B, and Llama-3.1-8B-Instruct.

Key Insights and Ideas

  • The "Free Lunch": If you are already using SMC for decoding (which is increasingly common for complex reasoning), the uncertainty signal is already there. You just have to stop throwing it away.
  • Sum, Not Mean: Most uncertainty signals average over tokens. The authors argue that sequence-level uncertainty should be a sum over steps. This ensures that longer, more complex reasoning chains—which have more "room" for error—naturally show higher uncertainty.
  • Search Effort as a Signal: SRE$_{1/2}$ is uniquely effective because it tracks how much the model's distribution is "spreading out" across different possible reasoning paths.
  • Adaptive Compute: A tiny 8-particle "probe" run is surprisingly good at predicting whether a problem is "hard" enough to justify a full 64-particle run.

Key Results

  • Superior Selective Prediction: SRE$_{1/2}$ was the best zero-cost signal for predicting answer correctness in 10 out of 13 experimental settings. On MATH500, it outperformed standard log-probability by a significant margin (0.022 to 0.044 AUROC).
  • Compute Savings: Using a two-pass adaptive policy (probe with $N=8$, escalate to $N=64$ only if SRE is high), they matched the accuracy of a uniform $N=64$ budget while using 34.2% fewer particles on average.
Figure 2: Selective prediction with Qwen2.5-Math-7B: accuracy vs. coverage on MATH500 (left) and GSM8K (right). AUROC in legend as [MATH500 / GSM8K].

As seen in Figure 4, the adaptive policy (blue line) reaches the accuracy of the uniform $N=64$ baseline much earlier on the compute axis, demonstrating significant efficiency gains.

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

Limitations and Future Work

  • Task Scope: The evaluation focused strictly on mathematical reasoning. It remains to be seen how SRE performs on open-ended creative writing or multi-turn dialogue where "correctness" is less binary.
  • Decoding Dependency: This specific "free lunch" requires using an SMC-based decoder. While powerful for reasoning, it is not yet the default for all LLM applications.
  • Future Directions: The authors suggest that SRE could be used for more than just particle allocation, such as routing difficult questions to larger, more capable models or deciding when to trigger external tools/verifiers.

Summary updated

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.
BibTeX
@misc{potraghloo2026free,
  author = {Erfan Baghaei Potraghloo and Milad Heidari Sorkhehdizaj and Shahab Rahimirad and Aliasghar Pourghani and Seyedarmin Azizi and Souvik Kundu and Abolfazl Hashemi and Joseph Campbell and Vijay Gupta},
  title = {{Free Lunch Uncertainty: Sequence-Level Rényi Entropy from Particle Decoding for Adaptive LLM Reasoning}},
  year = {2026},
  eprint = {2611.13414},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13414},
}
Figure