Don't Throw Away Your Beams: Improving Consistency-based Uncertainties in LLMs via Beam Search
Authors: Ekaterina Fadeeva
Maiya Goloburda
Aleksandr Rubashevskii
Roman Vashurin
Artem Shelmanov
Preslav Nakov
Mrinmaya Sachan
Maxim Panov
Venue: ICLR 2026 Poster (2026)
Keywords: LLM
Large Language Model
Uncertainty Quantification
Beam Search
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: A new family of consistency-based uncertainty quantification methods for LLMs using beam search candidates

Abstract: Consistency-based methods have emerged as an effective approach to uncertainty quantification (UQ) in large language models. These methods typically rely on several generations obtained via multinomial sampling, measuring their agreement level. However, in short-form QA, multinomial sampling is prone to producing duplicates due to peaked distributions, and its stochasticity introduces considerable variance in uncertainty estimates across runs. We introduce a new family of methods that employ beam search to generate candidates for consistency-based UQ, yielding improved performance and reduced variance compared to multinomial sampling. We also provide a theoretical lower bound on the beam set probability mass under which beam search achieves a smaller error than multinomial sampling. We empirically evaluate our approach on six QA datasets and find that its consistent improvements over multinomial sampling lead to state-of-the-art UQ performance.

DON'T THROW AWAY YOUR BEAMS: IMPROVING CONSISTENCY-BASED UNCERTAINTIES IN LLMS VIA BEAM SEARCH
Ekaterina Fadeeva!
Maiya Goloburda²
Aleksandr Rubashevskii
Roman Vashurin²
Artem Shelmanov
Preslav Nakoy²
Mrinmaya Sachan'
Maxim Panoy
ETH Zurich
MBZUAI
ABSTRACT
Consistency-basee methods have emerged as an effective approach to uncertainty quantification (UQ) in large language models. These methods typically rely on several generations obtained via multinomial sampling, measuring their agree- ment level. However, in short-form QA, multinomial sampling is prone to produc- ing duplicates due peaked distributions, and its stochasticity introduces consid- erable variance in uncertainty estimates across runs. We introduce new family of methods that employ beam search to generate candidates for consistency- based UQ. yielding improved performance and reduced variance compared to multino- mial sampling. We also provide theoretical lower bound on the beam set prob- ability mass under which beam search achieves a smaller еггоr than multinomial sampling. We empirically evaluate our approach on six QA datasets and find that its consistent improvements over multinomial sampling lead to state-of-the-as UQ performance.
INTRODUCTION
Today, large language models (LLMs) are in-
Who sang the song "Thriller" 20th century?
creasingly being adapted in various safety- critical domains, including medicine (Busch
Michael Jackson
How confident this answer?
al. 2025). education (Xing al. 2025), and
law Shu et al., 2024). This rapid adoption has led to a growing body of work focused on
Multinomial Sampling:
Beam Decoding:
Prince Xx
Michael Jackson
V
p=0.39
the assessment of the quality and reliability of
jx
p=0.34
LLM outputs. An important research direction in this field is Uncertainty Quantification (UQ; Xiao & Wang 2019 Baan et al.) 2023 Xia al.) (022),, which measures the LLM's con- fidence in their responses.
Michael Jackson
V
M. Jackson v
p-0.19
Michaal Jackson
Bruno Mars x
p=0.05
|x
p=0.03
Confidence: 2
Confidence: 0.58
Figure 1: Beam Search Multinomial Sam- pling. Sampling produces multiple identical gen- erations resulting in noisy confidence estimate, while beam search covers top answers from LLM distribution resulting in a better confidence score.
UQ methods can be separated into several dis- tinct categories. These include information- based methods that rely token likelihoods produced by the L.LM (Fomicheva et al. 2000);;
verbalization approaches that prompt models to provide a confidence score (Tian et al. 2023);
2022); and last but not least, consistency- density- based methods that utilize embeddings (Yoo et based measures that evaluate agreement between sampled outputs (Lin et al. 2024).
Consistency- based UQ methods are of particular interest, due not only their strong performance but also their applicability to black-box settings (Vashurin et al., 2025a).
Correspondence efadeeva@ethz, ch, maxi
hww.:hcccccc.cc.ooaoogeeeee.eee ma.panov@mbuua ac.ae

---

Moreover, in white-box settings too, it was shown that combining information-basee and consistency-basee methods yields state-of-the-art performance for a variety of tasks (Kuhn et al, 2023 Duan al. 2024). A key component of these methods is sampling, which serves practi- cal means of approximating the full probability space of all potential model outputs.
Most existing UQ approaches rely multinomial sampling from the model's ' output distribution. However, in short-form QA, multinomial sampling is prone to producing similar or even identical generations, due to its bias towards higher-probability tokens during decoding; Figure] [ Fur- thermore, since each run produces a different set of candidate outputs, sample-based uncertainty estimates exhibit high variance, undermining their robustness. This limits their effectiveness representation of the full output space, especially since, for computational efficiency, studies typi- cally rely on a small number of samples.
To address this problem, we propose computing output consistency based samples generated using beam search. Beam search facilitates the exploration of alternative decoding paths, which in turn allows one to generate distinct candidate outputs that better capture the model's output space in short-form QA. Our approach includes weighting beam search outputs by their probabilities rather than uniformly, thereby preventing the overrepresentation of low-probability outputs. Particularly, when beam search is employed for decoding, uncertainty estimates are obtained at essentially no additional cost. We show that replacing multinomial sampled outputs with those generated via beam search improves the robustness and accuracy of existing consistency-based methods, as well hybrid methods relying both output consistency and token likelihoods.
Our main contributions are as follows.
We identify key limitations existing consistency-based uncertainty quantification meth- ods based on multinomial sampling; Section
We propose
family of UQ methods that employ importance eeportance-weiihtedd estimator consistency-basee uncertainty with beam search output candidates; see Section
We provide a distribution-fiet sufficient condition ensuring that the beam-weighted es- timator achieves lower enror than the expected error of the multinomial sampler; Section 3.2
We show that applying a beam search-based estimator to existing consistency-bast UQ approaches improves their performance on short-form QA tasks, achieving state-of-the-an results; see Section 4
2 BACKGROUND AND MOTIVATION
2.1 LANGUAGE MODEL DECODING
Autoregressive LLMs produce text sequentially, generating one token at time. At each step i, the model samples a token y: ~ p(- y<s, where y<ı denotes the sequence previously generated tokens. The probability of generating output sequence y is:
lyl II plus x).,)).
ply x)
At each step, the model outputs probability distribution over the entire vocabulary V conditioned on the prompt x and the partial sequence yii.
Decoding strategies. Since the model defines a probability distribution, a concrete output must be obtained at inference time by applying decoding strategy. Common decoding strategies include: (i) greedy decoding that selects maximum probability tokens at each step; (ii) multinomial sampling where tokens are drawn according to p(y: yei, x); and (iii) beam search, which maintains the top-k most likely partial sequences at each step. Several other variants of decoding approaches have been proposed, such top-p nucleus sampling temperature scaling (Holtzman et al.) 2020) Vijayakumar et al., 2018). Each decoding strategy offers different trade-offs between output quality and diversity.
2

---

2.2 UNCERTAINTY QUANTIFICATION FOR LLMS
The objective of uncertainty quantification is to measure the level of uncertainty introduced by LLM when generating output sequence Y. conditioned input sequence x, denoted by Uy. x). Existing approaches to UQ can be broadly categorized into three main groups.
Information-buss methods rely on single forward pass of the model and compute statistics over the token-level probability distributions quantify un- certainty. Examples include Sequence Probability,
Sample Redundancy by Length
50
Redundant Samplees Samples
Mean Token Entropy. Perplexity (Fomicheva al.) 2020). and CCP (Fadeeva al., 2024).
30-
Reflexive methods query the model directly about its confidence in a generated answer using spe- cially designed prompts. is P(True) (Kadavath et al. 2022), which measures the probability that the model outputs "True" when asked whether its generated answer y. is correct.
20
representative example
5.2
Length of Output Takens
Figure 2: Mean percentage of redundant samples (i.e., outputs already seen among earlier generations) as a function of greedy output length. Results were obtained from 2. 2,000 questions from the TriviaQA dataset using the Gemma 3 4B base model and 10 candidate generations. Redundancy is es- pecially high for short answers, leading to wasted computation.
Sampling- campling-based based methods draw multiple samples from the model's output distribution and evaluate their semantic or lexical similarity to assess uncer- tainty. Lexical Similarity (Fomicheva al., 2020) computes mean pairwise similarity between gener- ated texts; other examples include Semantic En-
tropy (Kuhn et al. (2023). SAR (Duan et al.) 2024).
and black-box uncertainty measures from (Lin al. 2024).
Consistency- UQ methods. A notable subset of sampling-basse methods is consistency- based UQ (Vashurin et al. 2025b). These methods estimate uncertainty with respect to particular generated output y, ~ pl. x). rather than the overall uncertainty of the model's predictive distribu- tion for the imput This distinction makes consistency-based UQ particularly suited for evaluating confidence in a specific prediction rather than overall model uncertainty, and Vashurin et al. (025b) empirically demonstrate that such methods outperform other sampling-basee approaches in practice.
Let us consider the most straightforward consistency-batt method for predictive uncertainty quan- tification: measuring how semantically different alternative generations from the produced an- swer y.. We refer to this score as Dissimilarity and formalize it as the expected semantic dissimi- larity between the produced answer y. and all potential alternatives drawn from the model:
Unly. x) = Ey-p(-1x) [1 s(y.y.))
Here, s(y',y" [0. 1] is function that measures semantic similarity between two generations y' and y". higher value of Up(y. x) indicates lower consistency between the chosen answer and alternative candidate outputs, and thus reflects greater predictive uncertainty.
The corresponding Monte Carlo estimator introduced by (Lin et al. 2024) draws M i.i.d. samples (1) (dd) p(- x) and computes uncertainty in the following way:
ÚMC (y.
1 M
(1-s(y
(3)
Challenges of consistency-based UQ methods. A natural intuition is that, for consistency-based methods, samples should be generated a distinct, high-probability, and stable manner. Most existing methods use multinomial sampling, which, especially for shorter generations and small sample sizes, does not satisfy these criteria.
Figure 2 shows the effect of multinomial sampling on the percentage of duplicates depending the length of generations. The resulting samples contain many duplicates, with the issue being particularly pronounced for shorter generations, where 30-50% of the outputs duplicates.
3

---

This not only contributes wasted computation, but also leads to high variance estimates, More- over, drawing M full generations solely for uncertainty estimation can be costly.
Thus, while multinomial sampling is widely used, it does not best serve the goals of consistency- based uncertainty estimation.
UNCERTAINTY QUANTIFICATION BASED ON CONSISTENCY OF BEAM SEARCH CANDIDATES
To address the problems outlined above, we propose to utilize alternative decoding strategy for generating candidate outputs: beam search. Beam search (i) guarantees distinct candidate outputs, (ii) reduces variance (see Section 3.2 and (iii) provides uncertainty estimates essentially "for free" as the beam already provides a distribution over candidate outputs.
3.1 REPLACING MULTINOMIAL SAMPLING
simple way to approximate dissimilarity from beam- geaa--gneeattd candidates would be to reuse equa- tion (3) treating the beam outputs as if they were drawn uniformly. While this offers a plausible alternative, treating the candidates produced by beam search in a uniform manner would overem- phasize swerr-prbabbiliyy outputs. To better reflect the model distribution while avoiding repeated multinomial draws, we form probability estimator over the beam set.
For this purpose, we use beam search with width M to obtain distinct candidates (x) (b(1)... ....., (.....,(()) "od))...,,(ae b(M)) and their sequence probabilities {p(b(t) x)) To perform an estimation of Un(y- x) in equation (2) with the help of samples b(9), one needs to perform importance weighting. Thus, we define the restricted (top-M) normalized masses wy as:
((b(9 ( x)
W/
Σ .M Lj=1 p(b() x)
1, M.
(4)
The resulting suportance-weightee estimator of equation 2 is
Üb x) Σ w. (1,(1 (1-s(1)),
(5)
This top-M truncation introduces small bias relative to full multinomial sampling but typically reduces variance and duplication on peaked distributions, yielding more stable estimates per unit budget. In the next section going to explore the benefits of beam search-based estimator U+ x) from a theoretical perspective.
3.2 THEORETICAL ANALYSIS
We compare the multinomial Monte Carlo estimator UMC T for the dissimilarity Up defined in equation (2).
3 with the beam-weighted estimator
Theorem (Comparison condition for beam- beighweighted and Monte Carlo estimators).
Let Bis (x) (b) ..... ((M) be the beam set, my - (b x) be its total probability mass, and define jæ and Fg as dissimilarity inside and outside the beam set BM correspondingly:
μB Ey-p(-tx) s(y
(x)(x)),
PB = Exxp(( [1 s(y,y.) y $ Bx(x))
Then the beig-weighted estimator Ü& achieves smaller mean-squann mean-squared error than the Monte Carlo estimator MC whenever
(1 1-mB)lup Hsl < <
(6)
where 0² = Vary (1 (11-s(y.3) s(y.y.))) The corresponding distribution-free sufficient condition is
mg > 2/M
4

---

Proof. The Monte Carlo estimator averages M i..d. samples y( p(- x). it is unbiased with E = Up x) and MSE(U Var (C) o² /M. By Popoviciu's inequality, any random variable supported on [o, 1] has variance at most 1 /4, hence 6² = 1/4.
By the law of total expectation, the true dissimilarity UD decomposes as:
Uy x) mBp8 (1-
06 PB. μBB
so squared error of the beam-weighter estimator 0 is deterministic:
SB( (0) Un)² (1 ms) (us MBB)
Beam-weighted estimation is therefore more accurate whenever
(1 - mmm) - PB) < 0² /M,
which yields the stated condition 6
A distribution-Fii bound 77) follows from |AB /' S 1 and
x² 1/4.
From Theorem beam-weighted estimator is more accurate than Monte Carlo estimator whenever total beam probability mass my ex- ceeds 1
Probability mass covered by beam-search
33.5%
2VM For M 10, the thresh- old is mg > 0.842. Thus, when the top-10 beam hypotheses capture at least ~ 84% of the model's probability mass, beam search pro- vides a lower-error estimator than multinomial sampling with the same sample budget.
30
Fercentage
22.7%
12 12.7%
5.1%
Output
Figure 3: Percentage of texts meeting the suffi- cient condition (Theorem Results are based on 2,000 TriviaQA questions, Gemma 3 4B base and M = 10. The green "All" bar shows the overall percentage across all lengths.
In practice, this condition is frequently satisfied. On the TriviaQA dataset, Figure 3 shows that 22.7% of examples meet the sufficient condi- tion overall, and up to 30-40% for very short generations (S 3 output tokens), where proba- bility mass is highly concentrated on the top beams.
When the inside-outside gap = |MB 14B-11 Pzl < 1,
the break-even requirement (6) relaxes to (1 mg) a a/VM, allowing beam search to outper- form even when my < 0.842. Although /og is not directly computable due to the combinatorial output space, our experiments consistently show beam search outperforming multinomial sampling, suggesting that is modest in practice and that the effective threshold is often lower than 0.842.
3.3 ADAPTING OTHER UQ METHODS TO BEAM SEARCH
In similar manner, other consistency- bbssd methods be adapted to utilize beam barch-based samples in their formulation.
Eccentricity. Eccentricity is method introduced Lin al. (2024). Unlike dissimilarity, which uses only the similarities between the produced answer y, and each alternative sample, Eccentricity aggregates the joint pairwise relationships among all samples.
In this method, we first construct a similarity matrix of size (M + 1) (M + 1) for the M samples and the produced answer y (M+1) y::
Wiy s(y yU)), 15 M
(8)
Then we compute the degree matrix D:
M+1 Σ
Wa. i= j. i i j
Dij
(9)
0.
and obtain the eigendecomposition of the Graph Laplacian - D-1//WD --1/2 yielding M+1
eigenpairs ()i, u.
5

---

Smaller eigenvalues (close to zero) capture meaningful semantic structure, whereas larger eigenval- ues tend to reflect noise. We therefore retain the eigenvectors whose eigenvalues satisfy X < a, yielding K vectors in total; K is thus determined by the threshold > 0.
Semantic embeddings are formed as Vj [Uij U2js Uky]. For 1 J S M, v, represents the embedding of y0), and v. VM++ corresponds to y.. The confidence score is the distance between the embedding of the produced answer and the embedding of the samples:
Be x) = V=
V
(10)
M
where higher values indicate higher uncertainty.
With beam-generated candidates, we weight embeddings by the normalized masses wy from equa- tion to better reflect the model distribution while avoiding duplicate generations:
M
Byc x)
w
(11)
CoCoA. A white-box approach CoCoA (Vashurin et al. based uncertainty with the sample-consistency signal:
2025b combines model probabilities-
ÜCoCol(y. x) u(y- |x) U (y. x) u(y x)
1 M
Σ ==1
(1-5(1()) (()(() (12)
where u(y x) is model-based uncertainty measure for the sequence (e.g., log ply xx))
For a beam-weighted estimator, we utilize (5 as sample-consistency signal:
CCoCoa(y, xx) = w(y, x) 0% |x).
(13)
Eigenvectors Dissimilarity. Both Dissimilarity and Eccentricity produce confidence scores for the generated answer ys. Dissimilarity compares y, to each sample using the base similarity function while Eccentricity measures the distance from y- to the centroid in the Laplacian embedding space; see equation (TOp. To bridge these views, we measure dissimilarity within the embedding space itself, averaging the distances from the embedding of y, to the embeddings of individual samples. This retains the joint-pairwise smoothing of Eccentricity and also reflects the variance among samples, rather than only the centroid. The sampling-base based estimate is
ÜEiyVeeD(y, xx)
M Σ v.
vill2
(14)
and the beam-guided, probability version is
ÜesgeeDD xx) Σ w. || v1
(15)
where the embeddings v; (and v are obtained from the Graph Laplacian as in Eccentricity, and w; are the normalized masses from equation 44) This estimator increases both when y. moves away from the bulk and when the samples themselves are more dispersed; by contrast, Eccentricity focuses the single distance the weighted centroid.
4 EXPERIMENTS
4.1
EXPERIMENTAL SETUP
Datasets. We evaluate our approach on six QA datasets total. Those include two closed-book
datasets: TriviaQA (Joshi et al., 2017) and Web Questions (Berant al. 2013). two open-book
datasets: CoQA (Reddy et al. 2019) and HotporQA (Yang et al., 2018 and two multiple-choice datasets: CommonsenceCA Talmor et al. 2019) and ARC- ARC-Challenge (Clark et al. 2018). For each dataset, we randomly sampled several questions from the test set. The statistics for those datasets available in Table T Prompt details and examples of questions provided in Appendix C

---

Table 1: Test dataset settings and statistics.
Closed-Book QA
Open-Book QA
Multiple Choice
Web Questions
Common
ARC- Challenge
TriviaQA
CoQA
HotpoiQA
senceQA
# Questions
2000
1490
2000
2000
1221
447
# few-shot examples
all preceding
2
Max tokens
20
20
10
20
Table 2: Summary of baseline UQ methods.
Category
Uncertainty Quantification Method
Sequence Probability (Prob)
Mean Token Entropy (MTE)
Information-hased
Perplexity
CCP Fadeeva et al
2024
Reflexive
P(True) (Kadavath et al
2022)
Semantic Entropy Kuhn et al.
2023
Shifting Attention to Relevance (SAR)
Duan et al.
2024
Sampling-based
Lexical Similarity (Fomicheva al.
2020
of Eigenvalues of Laplacian (Eig aaplaciin)))
2024
Number of Semantic Sets (NumSemSets) (Lin et al. 2024
Models. We use base and instruct versions models: Gemma 4B (Team 2025a Llama 3.1
8B (Dubey al. 2024), and Qwen 3 8B (Team 2025b).
2025a). we adopt the Prediction-Rejeccion Ratio (PRR) as our primary evaluation metrie. Consider test dataset D = {(x,, }t) where ty denotes target output. Then, we can obtain an output yÿ generated by an LLM for input X; and the associated uncertainty score U, Uy} xj).
Metrics. Following best uncertainty benchmarking practices (Vashurin et al.
Based on these we can build rejection curve that captures how the average quality Q ty) over all {(yj, ty): < J changes with the rejection threshold т. An oracle rejection curve can be defined by substituting " = -Qy ty). giving best possible rejection order where lowest-quality outputs are rejected first. A baseline for rejection can be obtained by rejecting outputs uniformly at random. PRR is then defined as the ratio of the area between UQ rejection curve and a random rejection baseline to the area between oracle rejection and the same random baseline:
AUC AUCrmd
PRR
(16)
AUCoraele AUCma
higher PRR indicates a more effective uncertainty score. Following Vashurin et al. (2025a), we AlignScore (Zha et al., 2023) the quality metric Q. While PRR serves our mai evaluation measure, we additionally report ROC-AÜC and PR-AUC in Appendix D.2
Baselines. We evaluate four main methods, Dissimilarity, Eccentricity, Eigenvectors Dissimilarity, and CoCoA, under multinomial sampling and their beam-guided, probabilityweiighed variants. For CoCoA, we consider both CocoaMSP based on unnormalized log-probability:
u(y, x) = log p(y,
x),
(17)
and CocoaPPL based on perplexity:
u(y. x) 1--1
log Poy. xx)
(18)
In addition, compare against several state-of-the-an ofr UQ baselines summarized in Table ing implementations from LM-Polygraph (Fadeeva et al.] (023). The simplest baseline, Sequence Probability, calculates log p(y. x). For detailed descriptions of other methods see Appendix
2 us-

---

Table 3: PRR ( is better) averaged over 6 datasets. For each model, the top-1 method is bold and the second-best is underlined. For beam-guided variants, we mark when the variant improves over its original naltinomial-sampline counterpart.
Llama 3.1 SB
Llama 3.1 SB
Gemma 3 3-B
Gemma 3-1B
Qwen 8B
Qwen 3 8B
Mathod
Baseline UQ Methodl
Prob
410
.344 101
.71
.92 m
.376
288 4:30
MTE Perplesity
.364
.766
317
4007
.27
.323
CCP SAR PrTrue)
.401 1:1
.364 101
492 km
1.
355 234
291 1:18
.32
.35 :
386 6M6
239 PM
363 4: FM
222
.05
072
(933
-19%
.110
-114 665
Semantic Entropy
.376
339
299
Similarity
.366
1:358
Eig EigValLaplacian NumSemSSts
.255 m03
.371 121
.437 =:10
233 825
.406 =0
265 1.22
396
.319 101
A18
238 825
365 4 F2
.23 4:00
Consisroncy bured UQ: untrinouiaa beamseurch
Disimilziity
.379
Dissimiluity beamsearch
.543 1s am
A17 1 aes
450 716
252 11 2
.78 f1 m0
355 f1 30
Eccenticity
.533 ass
368 /
563 821
251
396 DM
251 4.29
Eccenticity beamsearch
.055 1
603 11x
285 11
.10 10011.00
345
Fisiittissinilaiityy
.370
233 es
Fig BigsiiDiiiiaaartttyy heamsearch
510 /oi
A14 1a mm
598 T1a
301 1/a
450 (tt: m9
.376 11+ 35
CoeuMMS
.055
4044 1os
587
314 cM
461 c3
334
CocoaMSP beamsearch
.21
.615
345 11.405
347
CoosuPPt
mm
.397 1.10s
312
.66 tM
337 1.20
CrouuPt. beanssnrrh
.36 ta a7
412 Ta mr
642 1a: 6M
339 Taa
461 11t mM
337 fs 191
All experiments use M = 10 candidates for both multinomial sampling and beam search. We adopt the entailment probability from the DeBERTa-large model fine-tuned on the MNLI task (He al., 2021) for similarity function s, following Lin et al. (2024).
4.2 RESULTS AND DISCUSSION
Table 3 PRR results for six models, averaged over six datasets. Across all models, incorpo- rating beam search consistently improves the performance of caaiistency-baseee uncertainty scores. Moreover, in almost every case, beam search-based methods achieve either the best or second-best PRR compared to both baselines and the original consistency-
approaches. In particular, Dis-
similarity + Beam Search achieves the best PRR scores for all base models and the second-best scores for Llama 3.1 8B instruct and Qwen 3 8B instruct. Similarly. CocoaMSP + Beam Search achieves the best results for Llama 3.1 8B instruct and Gemma 4B instruct, while CocoaPPL Beam Search ranks second-best for Llama 3.1 8B base, Gemma 3 4B base, and Gemma 3 4B instruct. We further provide separate results for each dataset in Appendix
4.3 ABLATIONS
In this section, we study sensitivity (i) the number of candidates M, (ii) output length, and (iii) rejection rate in PRR curves.
4.3.1 EFFECT OF SAMPLE COUNT
We vary the sample count M E (1,..., 15) for Dissimilarity, Eccentricity, and Fig VecDisiimmillrtty under multinomial sampling and beam search. Figure Sjswos that beam search generally achieves higher PRR across all budgets AM 2 2. Notably, beam search reaches high PRR at small budgets (3- 5 samples) and saturates quickly, while multinomial sampling improves more gradually and remains below beam search throughout.
For M 1, beam search reduces to greedy decoding, causing Dissimilarity to be nearly zero because it compares two identical greedy outputs. In contrast, the sampling variant compares greedy decoding stochastic sample, yielding more informative value.
8

---

TriviaQA
CoQA
0.60
0.750
0.55
PWX
0.700
0.50
0.675
0.650
0.625
0.40
5.66 Sequence length range (l..r)
Sequence length range 0..r)
Mulinomiaa Sampling
Figure 4: PRR (t is better) for Dissimilarity under beam search (with probability weights) vs, multi- nomial sampling, for different output lengths. Each dataset (TriviaQA, CoQA) with Gemma 3 4B base is partitioned into five approximately equal-size bins token length of greedy output.
Dissimilarity
Eccentricity
EigVecDissimilarity
2
6 10
12
2
6
10 12 14
2
6
10
12
Number of samples M
Number of samples M
Number of samples M
Multinomial Sampling
Figure 5: PRR (t is better) function the number of candidates M on TriviaQA with Gemma 4B base. Each panel reports one estimator (Dissimilarity, Eccentricity, Digisiiiiiiillttttt). Curves compare multinomial sampling and beam search (with probability weights from equation
Dissimilarity
Eccentricity
BigVecDissimilarity
Mooon Afgrserre
Meenn AgyScoree
Meon Algsteare
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.0
Rejection rate
Rejeztion
Random
Figure 6: Prediction- Rejecctoon curves for Dissimilarity, Eccentricity, and Eig Viissiiiiiiiilrrr on TriviaQA with Llama 3.1 8B base, comparing multinomial sampling (blue) and beam search with weights (orange). Oracle (black) and random (gray dashed) baselines are shown. The vertical dashed line marks the maximum rejection rate used in AUC calculations.
4.3.2 EFFECT OF OUTPUT LENGTH
Beam-guided estimators outperform sampling-based ones most clearly when generations are short. As shown earlier in Figure 2 duplicate rates under multinomial sampling are high for 2-4 tokens (~ 50%) and drop to 17% for outputs of 8+ tokens. To quantify the impact, we compute PRR for Dissimilarity using beam search (with weights from equation (4) and multinomial sampling (no weights) across five length bins of approximately equal size on TriviaQA and CoQA with Gemma 3 4B base; see Figure Within each bin, beam search consistently beats multinomial sampling for short outputs; the gap narrows and becomes negligible for lengths about tokens and above, where duplication less pronounced.

---

4.3.3 PREDICTION-REJECTION CURVES
Figure compares full Prediction-Rejection curves for Dissimilarity, Eccentricity, and Vie similarity on TriviaQA with Llama 3.1 8B base. Across all estimators, beam search consistently dominates multinomial sampling for nearly the entire rejection range. The becomes increasingly pronounced as the rejection rate grows, where beam-guide estimates remain stable while multi- nomial ones flatten or even degrade. This indicates that beam search is especially beneficial in the high-rejection regime, where distinguishing between stronger and weaker candidates is most critical.
4.3.4 ADDITIONAL ABLATIONS
Additional ablations are deferred to the appendices: Appendix A.1 compares candidate- -enerattonn strategies including Diverse Beam Search, temperature sampling, and a hybrid multinomial-bess sampling. Appendix AA.2 investigates restricted-mass normalization and shows that introducing a small probability floor can stabilize the weighting of low-mass beams. Appendix A.3 evaluates other sampling-base -astn objectives (Semantic Entropy, Degree Matrix) under beam generation with probability- formulations. Appendix [.] examines top-1 beam decode as the produced answer y- (instead of greedy), natural choice when beam search has already been run.
5 RELATED WORK
Consistency-based uncertainty estimation. In a black-box setting, consistency-base methods especially relevant, as they do not require access to the model internals. [Lin et al.] (2024) in- troduce several methods that estimate confidence based on a similarity matrix, where each entry represents the similarity between pair of sampled generations. |Fomicheva et al. (2020) present Lexical Similarity, a metric that evaluates the average similarity of words or phrases between each pair of responses. In white-box setting, consistency signals can be combined with model token- probabilities- basedd confidence. These hybrid methods, such as Semantic Entropy (Kuhn et al.) 2023), CoCoA (Vashurin et al. (2025b) and SAR (Duan et al., 2024) explore different ways of com- bining these signals and achieve state-of-the-arr performance. However, these works are primarily concerned with the introduction of new methods for uncertainty quantification and use multinational sampling way to approximate variety of consistency-base based measures.
Uncertainty and decoding. There were some efforts focused on examining the interaction be- tween decoding strategies and uncertainty quantification. In particular, Hashimoto et al. (2025) explores the impact of decoding strategies on the performance of token probabilities- methods, namely Sequence Probability and Mean Token Entropy. The authors find that these scores produced with beam search can sometimes under perform compared to greedy or contrastive search. While this work offers interesting insights, no experiments with stochastic decoding strategies or non-likelihood based methods were conducted. Conversely, other research focused on making the decoding itself uncertainty- aware.. For example, (MBR) decoding, which incorporates model uncertainty into the MBR objective for improved gener- ation quality. [arces Arias et al. (2024) Lnd et al. 2025) incorporate uncertainty into contrastive search decoding. Lastly, Ding et al. (2025) combines global entropy trends and local deviations to guide a self-adaptive decoding. These works integrate uncertainty into the decoding process to im- prove the quality of the generation, rather than improving the performance of the uncertainty itself. Although some uncertainty-awarr decoding methods have also demonstrated improved uncertainty quantification performance, they are generally not evaluated with consistency- -bsed metries.
UQ
al. (2025) propose Minimum Bayes Risk
6 CONCLUSION
We present new family of uncertainty quantification methods for LLMs that employ beam- weighted estimator of consistency-based uncertainty. Compared to multinomial sampling, com- monly used in existing approaches, our method yields lower variance in dissimilarity and greater diversity of candidate answers. We also derive a theoretical lower bound on the beam set probability mass under which the error of the multinomial Monte Carlo estimator is guaranteed to be larger. Finally, we evaluate our approach on six QA datasets and six different models, demonstrating state- of-the-art performance.
10

---

LIMITATIONS
Although our method provides an improvement over existing consistency-base estimators, several important considerations remain. First, evaluated methods in white-box settings, they quire access to the model's probability distributions. Nonetheless, we argue that developing methods tailored for white-box settings continues to be of great importance given their continued relevance and usage. Moreover, the methods could be extended to the black-box settings using empirical probability estimates.
Second, our experiments are limited to short-form QA datasets, and the generalizability of our find- ings to longer-form generation remains an open question.
Lastly, our implementation and evaluation relies on existing neural metrics: AlignScore is used to score the quality of the generation, and pre-trained NLI model is utilized as a measure of consis- tency. Although widely used in previous work, certain more specialized tasks might require different sample similarity measures and quality metries.
REFERENCES
Joris Baan, Nico Daheim, Evgenia Ilia, Dennis Ulmer, Haau-Sing Li, R. Fernández, Barbara Plank, Rico Sennrich, Chrysoula Zerva, and Wilker Aziz. Uncertainty in natural language gen- eration:
From theory applications. ArXiv, abs/2307. 157003 2023. URL https://api. semant i cscho ar. org Crtp/oorrsst: 26:03111611
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. Semantic parsing on Freebase from question-answer pairs. In David Yarowsky, Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard (eds.), Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1533-1544, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL /tttps://aclaaeeeets ceeethooogy..oo ogy. wgt...gg/13-111000011
Felix Busch, Lena Hoffmann, Christopher Rueger, Elon HC van Dijk, Rawen Kader, Esteban Ortiz-Prado, Mareus R. Makowski, Luca Saba, Martin Hadamitzky, Jakob Nikolas Kather, Daniel Truhn, Renato Cuocolo, Lisa C. Adams, and Keno K. Bressem. Current applications and challenges in large language models for patient care: A systematic review. Communi- cations Medicine, 5(1), 2025. ISSN 2730-664X.
doi: 1011388443366--02-00777--- URL http://dxx doi. 100 1038 -4385-338668-8 0201//4436002440011-----
024-00717-2
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? Try ARC, the A12 reasoning chal- lenge. arXiv preprint arXh::1803005457 2018. URL http::///aaa.v..oo//bb//////////
05457
Nico Daheim, Clara Meister, Thomas Möllenhoff, and Iryna Gurevych. Uncertainty-aware decoding with minimum Bayes risk. In The Thirteenth International Conference on Learning Representa- tions, Singapore, 2025. URL https:
/p///epeeeviiieeee/eeeee /ttps://openreview.
Yuanhao Ding, Esteban Garces Arias, Meimingwei Li, Julian Rodemann, Matthias Aßenmacher, Danlu Chen, Gaojuan Fan, Christian Heumann, and Chongsheng Zhang. GUARD: Glocal uncertainty-aware robust decoding for effective and efficient open-ended text generation. In Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng (eds.), Find- ings of the Association for Computationnal Linguistics: EMNLP 2025, pp. 7202-7226, Suzhou, China, November 2025. Association for Computational Linguistics. ISBN 979-8-89176-335-7 doi: 10. 10653/2222/2 www.:iin0...iiinnnninaaaa Andings-emmll.385
URL
Sindings-emnli 380/]
Jinhao Duan, Hao Cheng. Shiqi Wang, Alex Zavalny, Chenan Wang, Renjing Xu, Bhavya Kailkhura, and Kaidi Xu. Shifting attention to relevance: Towards the predictive uncertainty quantifica- tion of free-form large language models. In Lun-Wei Ku, Andre Martins, and Vivek Sriku- mar (eds.). Proceedings of the 62nd Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pp. 5050-5063. Bangkok, Thailand, August 2024. Asso- ciation for Computational Linguistics. doi: 18.138v3/v 12224.acl-loog.222 URL https: htw.hholllo......///// .el.aacl--- long.

---

Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, and Angela Fan. The Llama herd of mod- cls. CoRR, abs/2407.21783, 2024. htttt:://dool/ http///.........00////. 4ttp///1...5//..11111.
21783
Ekaterina Fadeeva, Roman Vashurin, Akim Tsvigun, Artem Vazhentsev, Sergey Petrakov, Kirill Fedyanin, Daniil Vasilev, Elizaveta Goncharova, Alexander Panchenko, Maxim Panov, Timothy Baldwin, and Artem Shelmanov. LM-polygraph: Uncertainty estimation for language models. In Yansong Feng and Els Lefever (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 446-461, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 10.18653/v /2023.emmlp-dmmo.. URL, ptttps://aclantholooo http://w..rr//002..m.1---------.
20
emw.pddmmo.pp.m.mmmm 417
Ekaterina Fadeeva, Aleksandr Rubashevskii, Artem Shelmanov, Sergey Petrakov, Haonan Li, Hamdy Mubarak, Evgenii Tsymbalov, Gleb Kuzmin, Alexander Panchenko, Timothy Baldwin, Preslav Nakov, and Maxim Panov. Fact-checking the output of large language models via token- level uncertainty quantification. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Linguisties: ACL 2024, pp. 9367-9385, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 10.18653//12222. findings-acl.555 ac1.558. h
URL/:tpp:://ccaattoooooyo www.achloaacco.....aoa..ao .rg/ 2024. findings-acl 558/
https:
Marina Fomicheva, Shuo Sun, Lisa Yankovskaya, Frédéric Blain, Francisco Guzmán, Mark Fishel, Nikolaos Aletras, Vishrav Chaudhary, and Lucia Specia. Unsupervised quality estimation for neural machine translation. Transactions of the Association for Computational Linguistics, 8: doi: 10.1162/tacl tacl 3537
539-555, 2020,
URL httpss////caaaatoooooooooo
Esteban Garces Arias, Julian Rodemann, Meimingwei Li, Christian Heumann, and Matthias ABen- macher. Adaptive contrastive search: Uncertainty-guided decoding for open-ended text genera- tion. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 1 15060-15000 15080, Miami, Florida, USA, Novem- ber 2024. Association for Computational I. Linguistics. doi: 10. 16.1886//1/2024. /20.://///.....nnnnggsseeee finding-emmll.855 URL httpps:/aat laccho ogy org/ 2024. findi ngs emm emn 1p. 885/
Wataru Hashimoto, Hidetaka Kamigaito, and Taro Watanabe. Decoding uncertainty: The im- pact of decoding strategies for uncertainty estimation in large language models. Chris- tos Christodoolopoulls, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng (eds.), Findings of the Association for Computational Linguistics: EMNLP 2025, pp. 14601-14613, Suzhou, China, November 2025. Association for Computational Linguisties. ISBN 979-8-89176-335.1 URL httpt:tt/////...... //ccl//ccc/ antho hoo.llll........................ org/2025.
doi: 10. 18.18853/112200 1/ 1/202 http://2....niinngnmm........... Findings-emn 1p. 788/
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. DeBERTa: Decoding-enhanced BERT with disentangled attention. In Pruceedings of the International Conference on Learning Representations, 2021. URL https: wttp///wpeeeeeeeee/ee/pee. wwtp:/n.e/eeeee....ee wtt.tetormm..o--
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL https:
//openzeview. http://eeeomommmeooooooorrr
Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Regina Barzilay and Min- Yen Kan (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 1601-1611, Vancouver, Canada, July 2017. Association for Com- putational Linguistics. doi: 10. 10.11//5/1//1171111777 URL htteps://aclantholl.. .oggg
P17-1147/
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodde Nova DasSarma, Eli Tran-Johnson. Scott Johnston, Sheer El Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bow- man, Stanislav Fort, Deep Ganguli, Danny Hermandez. Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom
12

---

Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. Language models (mostly) know what they know. arXiv preprint arXiv:2207.05221, 2022. doi: 10.48550//2X1.22207.22222
http:////.................... 02221
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, 2023, URL https: 7/ //openreview. net met/pdffid=vD AYtP(dve.
Hakyung Lee, Subeen Park, Joowang Kim, Sungjun Lim, and Kyungwoo Song. Uncertainty- aware contrastive decoding. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mo- hammad Taher Pilehvar (eds.), Findings of the Association for Computational Linguistics: ACL 2025, pp. 26376-26391, Vienna, Austria, July 2025. Association for Computational Linguis- doi: 10.18653/v1/2025. h00.:33///22225..mimng--aaee findingss-cl. www.fiinnnnniin 3335 1352/
tics. ISBN 979---99176-256-5
URL https:
/aaclanthooogyyo
Zhen Lin. Shubhendu Trivedi, and Jimeng Sun. Generating with confidence: Uncertainty quantifi- cation for box large language models. Transactions on Machine Learning Research, 2024.
ISSN 2835-8856. httL:tttt////ppereeeee
net / 2oorummmi--WKJCSXX..
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pre- training approach. arXiv preprint arXiv: /907. / 1692, 2019. URL httpps://arxi...om
abs/ 1969. 11692
Siva Reddy, Danqi Chen, and Christopher D. Manning. CoQA: A conversational question answering challenge. Transactions of the Association for Computational Linguistics, 7:249-266, 2019. doi:
10. a a_02666. URL http///aaaaathhtccccoo woaetthooogy..... ogy. wwgg/ogggg--- 1016
Dong Shu, Haoran Zhao, Xukun Liu, David Demeter, Mengnan Du, and Yongfeng Zhang. LawLLM: Law large language model for the US legal system. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 4882 4889, Boise, Idaho, USA 2024. Association for Computing Machinery, doi: 10.1457762767333600000 URL
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQQA: A ques- tion answering challenge targeting commonsense knowledge. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long and Short Papers), pp. 4149 4158, Minneapolis, Minnesota, June 2019, Association for Com- putational Linguistics. doi: 10. 18151/v1//1191144/0 1421. URL ht htt.::::/accaaachooogy.ooo
N1 N19-14211
Gemma Team. Gemma 3 technical report, 2025a. URL http:::/aaxxlv.oo////////333333
19786
Qwen Team. Qwen3 technical report, 2025b. URL
Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher Manning. Just ask for calibration: Strategies for eliciting calibrated con- fidence scores from language models fine-tuned with human feedback. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Meth- ods in Natural Language Processing, pp. 5433-5442, Singapore, December 2023. Associa- tion for Computational Linguistics. doi: 10.18653/w1/023.ccoo 100655///22233..mmmmma...... mmnl-- //aclanthology.oo wwtpoooyyy..g//223.... emnlp caennnppmain...mm
URL https:
Roman Vashurin, Ekaterina Fadeeva, Artem Vazhentsev, Lyudmila Rvanova, Daniil Vasilev, Akim Tsvigun, Sergey Petrakov, Rui Xing. AbdeIrahman Sadallah, Kirill Grishchenkov, Alexander Panchenko, Timothy Baldwin, Preslav Nakov, Maxim Panov, and Artem Shelmanov. Benchmark- ing uncertainty quantification methods for large language models with LM-Polygraph. Trans- actions of the Association for Computational Linguistics, tacl 00737.
2025a. doi: 10.1162/
13

---

Roman Vashurin, Maiya Goloburda, Albina Ilina, Aleksandr Rubashevskii, Preslav Nakov, Artem Shelmanov, and Maxim Panov. CoCoA: A minimum Bayes risk framework bridging confidence and consistency for uncertainty quantification in llms. In The Thirty-ninth Anmual Conference Neural Information Processing Systems, 2025b. URLbttps: bhttps::/opennevi.t.e net. forum?
id=H1 LNaVC
Ashwin Vijayakumar, Michael Cogswell, Ramprasaath Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra. Diverse beam search for improved description of complex scenes.
Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: URL https::/ojss...... www.ssaaai..om .org///orr//// index. www..php/AAAa Chmp/AAAA/artiis.
1609/aaai.v32ii
view/12340
Zhiqiu Xia, Jinxuan Xu, Yuqian Zhang, and Hang Liu. A survey of uncertainty estimation meth- ods large language models. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Findings of the Association for Computational Linguistics:
ACL 2025, pp. 21381-21396, Vienna, Austria, July 2025. Association for Computational Lin- doi: 1118655/11/20255 http:////1222....nnnn-aaeeeee andingg-acll.101. URL https:
guistics. ISBN 979-8-89176-25555- //aclanthology.ooo wtw.oog...rrgg.o/. findingginnnnn acl 1101/
Yijun Xiao and William Yang Wang- Quantifying uncertainties in natural language processing tasks.
Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):7322-7329 2019. ISSN doi: aaai. v33101 33017322
2159-5399.
(3309//aaai.3331133333313333 URL http: //tp:://dx /xt. doi wwt..di..ogg/1.11100001
Wanli Xing, Nia Nixon, Scott Crossley, Paul Denny, Andrew Lan, John Stamper, and Zhou Yu.
The use of large language models in education. International Journal of Artificial Intelligence in Education, 35(2):439 February 2025. ISSN 1560-4306. doi: 10. 00.100777000333-22-000445x.4 wwwppx.oooo.o...... URL htt.:pp:/paa.a...oo//000110////0 00t 025-0045----3000
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: dataset for diverse, explainable multi-hop question answering. In Conference Empirical Methods in Natural Language Processing (EMNLP), org/D1e 1259/]
Brussels, Belgium, 2018. URL httts::: ////cclaanttt /tRL:ttts/////aaaatt/ll/oo
Yioo Yoo, Jangho Kim, Jiho Jang, and Nojun Kwak. Detection of adversarial examples in text classification: Benchmark and baseline via robust density estimation. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Findings of the Association for Computational Lin- guistics: ACL 2022, pp. 3656-3672, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 10.18663//1/20222.nmmll 12dd:222...nnnng--a.2.23233 ac1.29.. URL ht https: http::s://acaaathhoooooooooooooo orq/ 2022. findings-acclcisc acl. 289/
Yuheng Zha, Yichi Yang. Ruichen Li, and Zhiting Hu. AlignScore:
Evaluating factual consis- tency with unified alignment function. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 11328-11 113881 Toronto, Canada, July 2023, Asso- acl-long.....
ciation for Computational Linguistics. doi: 10.18653/v1/200 //acl hothhn ogy. acl.aaccll--o acw.:/2....111n1..oo...... long....11...4444
1/2022.acl-longg
URL https:
14

---

A ABLATION STUDIES
A.1 DIFFERENT SAMPLING STRATEGIES
This section studies how the proposed estimators behave under different sample generation strate- gies, In addition to multinomial sampling and beam search settings, we evaluate three additional families.
Diverse beam search. We generate M = 10 candidates using a diverse beam search (ijjayau- mar al. 2018) with group penalties (0.5, 1.0, 1.5, 2.0) and group counts that split the ten candidates into G E {2.5} groups. As in the main beam setup, we apply the same self-normalized probability weights Wi from equation
Temperature sampling with importance weights. For different temperatures T, we draw M 10 samples with temperature sampling [yr (6) M and re-weight them via ceff-normalized importance weights
p(yT) x) 1-1/T
w
Σ= ply |x) 1-/TT
(19)
Hybrid multinomial-bean search. We also consider a joint strategy: first draw B beam candi- dates, then draw the remaining M B candidates via multinomial sampling while excluding the beam results. Beam candidates use autoregressive probability weights, and the residual probability mass is distributed uniformly the multinomial samples. Let (b()) Ri=1 be the beam outputs and { J==B+1 the multinomial samples (with beam sequences masked out). We assign weights
1
ΣE P (b
x)
w."" rb(()) x), i= 1..., B.
w
j B
M,
M B
(20)
so that EM w." = 1. We test B {1....,9).
Evaluations use a subset of 500 examples from TriviaQA and CoQA with two base models, Gemma 3 4B base and Llama 3.1 8B base. Results are summarized in Table
Table 4: PRR (1 is better) under different sampling strategies. Columns list methods (Dissimilarity, Eccentricity, Eig VecDissimilarity) and four different model-dataset pairs; rows list strategies with their hyperparameters. Per column, top-1 1 is bold, second- best is underlined.
TrivisQA
CaQA
TrivinQA
CoQQ
Dissim
Foe
EigNec
Dissim
Eoc
EigVee
Dissim
Fec
Eig
Dissim
Fee
Eig
Beam search
.771
.732
.751
.561
.483
.488
.623
.811
.98
.502
.438
.454
.368
T 0.9
.734
.664
.710
.468
.417
.425
.588
.21
.188
.007
.400
Multinomial
T = 1.0
742
680
7155
.465
.424
.432
.39
.16
.377
.31
.166
.244
Sampling
T
T
.718
.685
.717
.406
.426
.436
515
.397
.431
.400
T- 1.7
680
.601
777
.372
.466
.433
.69
.544
.300
304
.522
.441
0.5
.753
6=2,A=
.753
366
7705
.51%
384
.432
.594
-138
539
.466
.285
.35
2.
.763
.522
.714
.537
.420
.618
..001
542
.462
.245
.317
2,
Beam Seurch
G G, 0.5
.588
.466
736
.493
.401
.455
.591
-026
569
.35
2622
353
5.
.768
.523
.716
.515
369
.123
.615
-086
563
.447
.274
.376
G = 5, 2.0
.770
.476
690
.515
.355
.415
661
-093
548
A53
132
.54
.315
.314
.765
.731
.745
.519
.470
.617
586
.415
.358
B =
781
.736
.754
.503
.461
.439
.220
553
598
.519
436
.444
Hyhrid
.784
.75
.667
.466
388
Multinonial-
B=
.757
.733
.749
.538
500
.470
.412
.199
Beam
B 13=00
.733
.733
.756
.28
.512
.488
.335
586
.613
.46
.411
.415
.711
.737
.754
.43
.668
.677
A83
.99
.277
.764
773
.55
.488
.044
.491
.434
9
.772
747
.65
551
509
.97
.616
.977
.618
.501
.427
.39
15

---

No single strategy dominates across datasets, models, estimators. Temperature sampling (with importance weights) and diverse beam search systematically yield to beam search and hybrid multinomial-beam. Hybrid multinomial-beam strategy reach top-1 for specific hyperparam- eter B, but gains are not systematic and are sensitive to tuning. Given this variability and tuning cost, plain beam search with probability weighting reasonable default.
A.2 RESTRICTED-MASS NORMALIZATION
Equation normalizes autoregressive sequence probabilities over the M beam candidates. This choice can sensitive to tail candidates whose probabilities are tiny and length-dependent To test robustness, introduce floor the per-candidate mass:
max (c. p(b(.) x))
(21)
Σラ max(E, p((()) x))
M
yields uniform weights W 1/M. Intermediate values trade off fidelity to the model distribution against robustness to noisy, length-biased tails.
The setting recovers equation
We evaluate beam-guided probability- methods for different on subset of 500 examples from TriviaQA and CoQA with two base models, Gemma 3 4B base and Llama 3.1 8B base. Results are summarized in Table
The results do not indicate a clear best choice of method and corresponding parameter. Determin- ing the optimal is case-dependent task.
Table PRR (1 better) under restricted-mass normalization ablation. Columns group dataset-model pairs with methods (Dissim, Ecc, Eig VecDsssmm Rows vary the mass floor in equation (2T): c recovers equation 4 c = yields uniform weights w; 1/M. For each
dataset-method the top-1 score is bold and the second-best is underlined.
Gemma 3 4B base
Llama 3.1 8B huse
TriviaQA
CoQA
TriviaQA
CoQA
Veg Dissim
Vee Dissim
Eee Dissim
Heg Dissim
Dissim
Ecc
Dissim
Ecc
Dissim
Ecc
Dissim
Eoe
.741
.744
.487
.668
.596
.410
0.1
.765
.727
.745
.556
.497
.483
.667
.612
.627
502
.477
.446
0.05
.764
.720
.744
.561
490
.877
.657
.006
.26
509
435
.451
.584
0.001
.771
.731
.751
.562
.484
.488
.624
.581
.598
501
.438
.453
O. 0.0000L
.771
732
751
.561
.48
488
.623
.811
.988
502
438
.454
732
751
.561
.483
.488
.502
.438
A.3 OTHER CAMPLING-BASER METHODS UNDER BEAM SEARCH
Beyond Dissimilarity, Eccentricity, and EigVecDissimilarity, this ablation evaluates other sampling-based methods under beam-generated candidates: Degree Matrix (Lin et al. 2024) and Semantic Entropy (Kuhn al.) 2023), We also provide probability-weighte beam formulations using the weights from equation
Degree Matrix. Given M multinomial samples MM Degree Matrix estimates the average pairwise dissimilarity:
M
M
DegMac(x))
Σ
Σ (1
(,y0)))
(22)
M
For beam candidates {b
( M Ti 1, our mass-aware variant averages with weights:
ÜbeMMa((x)
Ü
Σ w. Σ wy
(b,))(())b)))))
((b()) b()).
(23)
16

---

Table PR-AUC (1 better) on 6 datasets with Gemma 4B base. Each method is shown as a pair: its multinomial-samplin variant and its peam-search variant; 1 denotes an improvement of the beam variant over its multinomial counterpart. Along main methods, the table includes input- uppttuuncertaitty methods (Semantic Entropy. Lexical Similarity). For each dataset, the top-1 score is bold and the second- underlined. The rightmost column reports the mean PR-AUC across datasets.
Web Questions
Common senceQA
ARC-
UQ Method
TriviaQA
CoQA
HotpoiQA
Mean
Challenge
Semantic Entropy Semantic Entropy beamsearch
.622
.505
.301
.140
407
.411
.001
.851
.6441
3651
.2881
4361
4541
.421
Degree Matrix
.682
.605
.385
.311
.099
.419
.469
Degree Matrix + beamseurch
.63
.6211
.328
.244
4441
.431
.467
SAR
656
.571
.347
.296
.183
.264
.386
SAR + beamscarch
671
.5891
.329
.266
.2091
.2691
.372
Dissimilarity
.755
.715
.578
.626
.661
.545
.630
Dissimilarity beamsearch
7661
.7221
.6001
.611
.5951
.604
.650
Eccentricity
.744
.653
.459
.453
.549
.549
.563
Eccentricity beamsearch
7391
.633
.5051
.5441
.5001
.636'
.6031
Eig Vigeiiiiiimilarttyy
.738
.661
.443
.448
.512
.562
.561
Fig VecDissimilarity + beamsearch
753t
.668*
.4971
.4871
.5621
.211
.5987
CocuaMSP
.738
.666
.509
.430
.595
CocoaMSP beamscarch
.4771
.679*
.5881
-5231
.5861
.6061
.615t
CocoaPPL
.739
.678
.548
.625
.580
.595
CocuaPPL + beamsearch
.7481
.6947
.5771
.6811
.5821
.6007
Semantic Entropy. Multinomial samples are clustered into semantic equivalence classes C. For each class, we calculate its probability
M Σ
p(c) = M
1ty Ec]
for c
(24)
1=1
Then Semantic Entropy calculates
Ssm = C
Σ
log((c).
(25)
CEC
For beam candidates, use cluster masses aggregated by w::
(c)c)
Σ w. 1(b E c).
(se) = - (c)
(26)
GEC
Note that these objectives score LLM uncertainty about the input x as they are independent of particular y..
The results are summarized in Table Beam search yields significant gains for Semantic Entropy and little to no improvement for Degree Matrix. Even with the beam- adapted formulations above, both objectives show worse results terms of absolute PR-AUC compared other methods. The primary reason is the target mismatch: as noted, these scores quantify uncertainty of the input x and are independent of the produced answer y., whereas our main methods, Dissimilarity, Eccentricity and Eig VecDimiimillarty focuses ranking the correctness of itself.
To further assess performance under different numbers of samples M used for UQ we plot PRR as function of M for one selected baseline, Semantic Entropy, well as for Dissimilarity (both sampling and beam-search variants) for reference. Figure 7 presents the results, showing that for all M 1, Semantic Entropy underperforms both Dissimilarity variants. This occurs because Dissimilarity measures the targeted uncertainty of the specific generation y. rather than the overall uncertainty associated with measured by Semantic Entropy.
17

---

Dissimilarity
0.6
PRR
0.4
Number of samples M
Dissimilarity Dissimilarity beamsearch
Semantic Entropy
Figure 7: PRR is better) as a function of the number of candidates M on TriviaQA with Gemma 3 4B base for 3 UQ methods: Semantic Entropy, and sampling and beam search versions of Dissim- ilarity.
Table PRR (f is better) for Eccentricity and Eig VecDismimilarity under different Graph Laplacian embedding choices on four dataset- model pairs. Top block varies the eigenvalue threshold (re- taining all X < a); bottom block fixes the embedding dimension K. For each pair, the best score bold and the second-best is underlined.
Gemma 3 44B hase
Llama 3.1 8B hase
TriviaQA
CoQA
TriviaQA
CoQA
Eig Dissim
Eig Vec
Big Vec
Fig Vec
Fec
Fec
Fec
Fec
Dissim
Dissim
Dissim
a 0.3
.717
.710
.355
.601
.599
.408
.364
.752
.740
.460
.627
.626
.431
.420
0.7
.750
.749
.539
.498
.622
.643
.438
.441
a 0.8
.751
.757
.088
.475
.616
630
.444
.50
.732
.751
.488
.598
.438
.444
.725
755
.432
.454
.535
.561
.397
.409
K
.358
.346
.332
.444
.357
.304
.280
K
.100
.322
.333
.361
.474
.469
338
.338
K 3
.199
639
.434
.429
.388
.534
.351
.348
K
645
643
.418
.412
.519
.514
.359
.352
K
.352
.492
.316
K
.29
545
.244
.236
.363
.368
.110
.211
K =7
.110
.42
-,00
.076
.050
.062
200
2211
K
-65
-209
-210
-171
-,358
-349
-327
-308
K
-566
.414
-668
118
4462
-410
-339
-317
K 10
-659
.484
.28
.189
-467
-397
+330
.249
A.4 GRAPH LAPLACIAN EMBEDDING PARAMETERS
Both multinomial and beam- guided versions of Eccentricity and EigVecDissimilarity depend on the threshold parameter a, which selects eigenvectors of the Graph Laplacian 7. 7 D-11/2 1/1/2 used form semantic embeddings. Specifically, after computing the eigenpairs {A;, M+1 we retain those with A; < a, yielding K eigenvectors in total and embeddings v, = [uı5, U.j..... uki] of dimension All eigenvalues lie in [0, 1]: smaller values capture stronger semantic structure, whereas values closer to I tend to reflect noise (Lin et al. 2024). In the main experiments we follow the original Eccentricity setting and use a 0.9.
Here vary and also test fixed-K K strategy (i.c., keeping exactly K leading low-spectrum cigenvectors irrespective of the threshold).
Table reports the performance for Eccentricity and EigVeeDissimillrity across and K four dataset-model pairs. fixed embedding size performs poorly: the optimal number of informative directions varies between candidate sets, fixing K either underfits or includes noisy directions. Thresholding is more robust: a E [0.7, consistently yields strong results across methods and pairs, supporting our default choice 0.9.
18

---

A.5 CHOSS-ENCODER SIMILARITY
In the main text, we instantiate the similarity function a using an NLI score: the entailment proba- bility from DeBERTa model. CoCoA, however, originally used RoBERTa-large cross-encoder fine-tuned on the Semantic Textual Similarity benchmark (Liu et al. 2019). Table | reports PRR for Gemma 4B base when replacing the NLI-based with this cross encoder; all other settings are unchanged.
Table 8: PRR (1 is better) 6 datasets with Gemma 4B base using RoBERTa-lane -arge cross- encoder (STS) as the similarity function place NLI. For each dataset, the top- is bold and the second-best is underlined: marks improvement of beam variant over its multinomial counterpart.
Weh Questions
Common senceQA
ARC- Challenge
UQ Method
TriviaQA
CoQA
HotpoiQA
Mean
Dissimilarity
.725
.683
497
.597
.811
.421
.667
Dissimilarity bcamscarch
.7461
.693
.531
.6541
.051
.4791
.388
Eccentricity
.722
.647
.489
.544
.455
.500
.560
Eccentricity beamsearch
7341
.6471
.48
.6041
.32
.421
.542
FigVisDDissmmilarity
.737
.649
.433
.523
.489
.529
.563
Eig Vigeeiiiiiiillttttt beamscarch
7441
.6751
4841
.8211
.439
.496
.5701
CocoaMSP
.731
.642
.438
.397
.553
.577
.556
CocuaMSP beamsearch
7401
.6481
.4221
.4911
.5581
.5937
.5807
CocoaPPL
.728
.653
.607
.546
.567
.598
CocoaPPL beamsearch
.7371
.6581
.4981
.6501
.5481
.5861
.613*
A.6
NUMBER OF SAMPLES ACROSS DIFFERENT TASKS
TriviaQA, Gemma-4b-base
ArcChallenge, Gemma-4b-base
0.8
0.8
0.6
0.6
PRR
0.4
PRR
0.4
0.2
0.2
0.0
0.0
2
12
14
2
4
12
Number of samples
Number of samples
TriviaQA, Llama Baama-b-bard 8b-base
TriviaQA, Qwen-8b -b-bae
0.8
0.8
0.6
0.6
PRR
0.4
PRR
0.4
0.2
0.2
0.0
0.0
2
4
6
10
12
14
2
4
10
12
14
Number of samples
Number of samples
Dissimilarity
Dissimilarity + beamsearch
Figure 8: PRR (f better) as function of the number of candidates across different datasets and models.
19

---

To evaluate the performance of the proposed bearcsearch variations under different numbers of samples M across models, we computed PRR for both the sampling and beam-search versions of Dissimilarity on 200 random subsamples of TriviaQA for three LLMs: Gemma 3 4B base, Llama 3.1 8B base, and Qwen 8B base. To further assess performance across datasets, we additionally evaluated PRR for Gemma 4B base the 200 subsamples of ARC-Challenge dataset. All four resulting plots are shown in Figure
The results show that for all budgets M 1, beam search consistently outperforms sampling, yielding higher PRR. On the open-ended TriviaQA dataset, PRR increases steadily with M, with beam search reaching a plateau around M 5 for all 3 models tested. On the multiple-choice ARC-Challenge dataset, PRR plateaus at a considerably smaller budget (M = 2), likely due to the small output space (i.e., limited set of answer choices).
Overall, these results indicate that the beam-search variant of Dissimilarity remains effective even relatively small sample budgets: M for open-ended short-form generation tasks, and M for multiple-choice settings, where the constrained output space enables faster saturation.
20

---

B ANALYSIS AND EXAMPLES
B.1 PROBABILITY MASS COVERAGE
Mass Coverage by Length
Beam search probabilities per sample
Probabiltty Mass Covered (%S
80
Multinomial sampling
Beamn search
60
01691] x3
0.6
0.4
20
0.2
Length of Output Tokens
Sample index
Figure 9: Left: average probability mass covered by the candidate set (M=10) across output-length bins (averaged over examples the bin) on TriviaQA with Gemma 3 4B base. Right: for beam search, distribution of sequence probabilities p(b(*) (3) x) by beam rank highest-probability text).
Figure 9 summarizes two observations. First (left), beam search covers a larger share of the model's probability mass than multinomial sampling across length bins. Second (right), beam probabilities decay sharply with rank: the first few beams capture most of the mass, while lower-ranked beams contribute little. This motivates mass-aware weighting ws (see equation (4) and helps explain why probability-weighte beam variants are effecttve, especially at small candidate budgets.
B.2 EXAMPLES
We include qualitative examples for Gemma 4B base: two from TriviaQA, two from WebQues- tions, and one from CoQA. Each panel shows the question, the greedy answer, multinomial samples, and ten beam-search samples with autoregressive probabilities, together with the corre- sponding uncertainty scores (e.g., Dissimilarity and its beam-guided variant). The cases illustrate how beam search reduces duplication and enhances uncertainty.
Question: What claimed the life of singer Kathleen Ferrier?
Question: Which number Beethoven sym- phony is known as 'The Pastoral"? Greedy: 6
Greedy: breasts cancer
Multinomial
Beam-search samples
Multinomial samples
Beam-search samples
samples
cancer
cancer
p=0.228
six
sixth
0=0.314
breast
tuberculosis
p50.154
seventh
6 6th ninth seventh
p=0.169
pulmonary
breast cancer
p=0.089
p=0.104
breast cancer
lung cancer
p=0.041
sixth
p=0.061
cancer
pneumonia
p=0.039
sixth
p=0.037
breast cancer
leukaemia
p=0.034
9
p=0.027
myx
myel
p=0.023
seventh no
six
p=0.233
cancer
leuk
p=0.011
9th
p=0.021
cancer
pulmonary
p=0.011
sixtcenth n6
no.
p=0.013
pneumonia
lymphoma
p=0.010
7
p=0.008
Dissimilarity: 0.330
Dissimilarity: 0.634
Dissimilarity + beamscarch: 0.533
Dissimilarity beamsearch: 0.561
Two examples from Gemma 3 4B base on TriviaQA. Each panel shows the question, greedy answer, multinomial and beam-search samples with autoregressive probabilities, plus dis- similarity and beamsearch-guided dissimilarity.
Figure 10:
21

---

Question: who plays charlie the santa clause
Question: what currency does eyprus use? Greedy: Cyprus pound
movies?
Greedy: Tim Allen
Multinomial samples
Beam-scarch samples
Multinomial samples
Beam-scarch samples
Euro
Euro
p=0.439
Tim Allen
Tim Allen
p=0.318
Euro
p=0.201
Tim Allen
Jeff Daniels
p=0.017
Euro
Cyprus pound
p=0.091
Scott Calvin
Timothy Oly
p=0.012
Euro
Cypriot
p=0.072
Tim Allen
Ed Asner
p=0.010
curo
Cyprus Pound
p=0.016
Tim Allen
Scott Calvin
p=0.008
euro
Euros
p=0.014
Edward Arnold
Edward Asner
p=0.008
curo
EURO
p=0.007
Tim Allen
Tony Cox
p=0.007
euros
euros
p=0.007
Jeremy nault
Tim Allen
p=0.007
Euro cyprus
p=0.007
Tim Allen
Tim allen
p=0.005
Euro Cyprus
p=0.006
Tim Allen
Eric Lloyd
p=0.004
Dissimilarity: 0.976 Dissimilarity + beamsearch: 0.800
Dissimilarity: 0.427
Dissimilarity beamsearch: 0.313
Figure 11: Two examples from Gemma 4B base on WebQ. Each panel shows question, greedy answer, multinomial and beam-search samples with autoregressive probabilities, plus dissimilarity and beamsearch -uideed dissimilarity.
Story: A couple of weeks ago, my 12-year-old daughter, Ella threatened to take my phone and break it. "At night you'll Il always have your phone out and break you' just type," Ella says. "I'm ready to go bed, and try to get you to read stories for and you'r 're just standing there reading your texts and texting other people," she adds. came to realize that was ignoring her as father...
Question: She mentions lot of grown ups don't 't make what in their lifetime?
Greedy: Limits.
Multinomial
Beam-scarch samples
samples
Boundaries.
Boundaries.
p=0.185
Set limits.
Limits.
0=0.779
Boundaries.
They don't
0=0040
limits.
Rules.
p=0.332
Boundaries in their
Boundaries.
p=0.029
Charging station. Similar limitations. Boundaries. Boundaries.
Boundaries.
0=0.28
charging station.
0-0.1
Boundaries that protect
0.010
Limits in their own Boundaries
00000
Set up similar limits
0=0.077
Dissimilarity: 0.310 Dissimilarity + beamscarch: 0.190
Figure 12: One example from Gemma 3 4B base CoQA. Shown are the question, greedy an- swer, multinomial and beam-search samples with autoregressive probabilities, plus dissimilarity and beamscarch-guided dissimilarity.
22

---

C DATASETS
Table lists the prompts used to form inputs for each dataset (separately for base and instruct models). Table T0 reports mean accuracy for each model-datasee pair. We measure accuracy the fraction of predictions whose AlignScore with the gold answer exceeds 0.5.
Table Prompt templates used for each dataset and model type. Few-shot exemplars are shown as placeholders (e.g., <5 few-shot QA pairs>); run-time inputs are denoted by <question>,
<context>, <title 1>, etc.
Dataset
Base Prompt
Instruct Prompt
TriviaQA
<5 few-shot QA pairs> Question: <question> Answer:
Answer the following question briefly possible. <5 fex-shot QA pairs>
Now answer the following question:
Question: <question> Anawer:
Web
<5 Iew shot QA pairas Question: <question>
3elow questions with short factual
Questions
Retura enly the short answer (a name, phrase, number, or year!
<5 fex-shot QA pairs> answer
0: <quastion>
CoQA
Story: <xontext>>
Story: <context>
<all preceding QA pairs> Question: <question> Answer:
<all preceding QA pairs>
Answer the following question as briefly as possible.
Question: <question>
Answer:
HolpoiQA
ritler <title 1>
Instruction: Read the centext and answer with a factual apan
<paragraph 1>
words] copted from context. Reply with the short answer only,
Title: <title <paragraph 2>
Title: <title
sparagraph 1>
Question: <question> Short enswer:
Title:
<paragraph 2>
Question: <question>
Short
Common senceQA
<2. faw-shot paira> inestion: <question> Options: eptions> Answar:
Instruction: Choose the single from the options. Anawer with the option text only inot the letter).
<2 fex-shot DA pairs>
ansker
Question: <question>
Options:
<(A)
(D) options>
Answer:
ARC- Challenge
<2 few-shot DA peirs>
Choose the single best answer from the options.
Instruction:
Question: <question>
with option text only Inot. the
Optso
letter).
(IA) options>
fex-shot QA pairs>
Anawer:
Now answer this.
Question: <question>
Options:
<IA)
(D) options>
Anawer:
Table 10: Mean accuracy (%): proportion of predictions with AlignScore to the gold answer >> 0.5.
Closed- Book QA
Open-Book QA
Multiple Choice
Web Questions
Common senceQA
ARC-
TriviaQA
CoQA
HotpotQA
Challenge
Llama 3.1 base
63%
47%
74%
53%
74%
72%
Llama 3.1 8B instruct
69%
40%
80%
72%
77%
76%
Gemma 3 4B base
47%
33%
69%
41%
65%
70%
Gemma 3 4B instruct
51%
35%
76%
66%
76%
77%
Qwen 8B base
52%
48%
81%
47%
89%
91%
Qwen 8B instruct
54%
42%
76%
76%
84%
88%
23

---

D ADDITIONAL RESULTS
D.1 SCORING TOP-BEAM OUTPUT
In the main text score the greedy decode as the produced answer y.. Table complements these results by scoring the top-/ beam as y. natural choice when beam search is already used to obtain a higher-quality decode. The ream-weights family of approaches achieves higher PRR than the original methods and baselines in the majority of cases.
Table 11: PRR (f is better) averaged over 6 datasets, when scoring the top-1 beam produced answer (instead of greedy). For each dataset, the top-1 score is bold and the second-best underlined. For beam-guided variants, mark when the variant improves over its original multinomial -amplingg counterpart.
Llama 3.1 8B
Gemma 3 4B
Qwen 3 8B instruct
UQ Method
base
instruct
base
instruct
base
Baseline UQ methods
Prob
.39
.174
.400
.213
.30
.090
MTE
320
.164
.317
.228
.34
.255
Perplexity
.366
.111
.359
.185
.388
.009
CCP
.395
.155
.369
.243
.352
.226
SAR
.333
.211
.336
.348
.342
.246
P(True)
.019
-0075
.031
.090
.012
-0000
SemanticEntropy
.345
.286
.397
.320
.299
.250
LexicalSimilarity
.377
.221
.384
.291
.404
.210
Fig Laplaaann
.366
.209
.402
.307
.384
.223
NumSemSets
.349
.215
.365
.262
.344
.208
Consistency- UQ: multinomial vs. beansearch versions
Dissimilarity
.437
.229
.424
.333
.446
.222
Dissimilarity beamsearch
4551
.266
4661
.3901
.40
.3461
Eccentricity
.405
.238
.395
.310
.375
.208
Eccentricity + beamsearch
4441
3011
.450
.3481
.3801
.388
EigVec Digssiiiiiii
.402
.243
.412
.316
.403
Eig VecDissimillritt + beamsearch
4461
.3661
.457
.3661
.151
.344f
CocoaMSP
.47
.284
.450
.347
.54
.22
CocoaMSP beamsearch
.4111
.2901
.4781
.4071
.591
3451
CocoaPPL
.440
.251
.433
.340
.422
.261
CoccaPPL. + beamscarch
.5011
.2311
.4441
.3551
.410
.3181
D.2 ROC-AUC AND PR-AUC
In the main text report PRR. Tables 12 and 13 complements these results with ROC-AUC and PR-AUC on Gemma 3 4B base. We binarize by marking an answer as correct if its AlignScore to the gold answer exceeds 0.5, and incorrect otherwise (the positive class for PR-AUC the incorrect label). The pattern mirrors PRR: beam- beam-guided variants generally match or outperform multinomial sampling.
D.3 DETAILED RESULTS FOR EACH DATASET
Complementing the main-table results in Table Tables 14 report PRR for six datasets sep- arately for Gemma 3 4B base, Gemma 4B instruct, Llama 3.1 8B base, Llama 3.1 8B instruct, Qwen 3 8B base, and Qwen 3 8B instruct.
24

---

Table 12: ROC-AUCT for datasets with Gemma 4B base. For each dataset, the top-1 method is variants are marked
bold and the second-best is underlined. Beam-guu soannggideed--e and with 1 when they improve over their multnoomial-smpling baseline. The two rightmost columns report the mean ROC-AUC across datasets.
UQ Method
TriviaQA
Web
CoQA
HotpoiQA
Common senceQA
ARC- Challenge
Mean
Questions
Baseline UQ methods
Prob
863
.688
.698
.632
.796
.21
.763
MTE
867
.793
.710
.721
.737
.753
.763
Perplexity
.755
.729
.735
.800
CCP
.881
.781
.698
.660
.775
.793
.764
SAR
867
.776
.701
.713
.653
.696
.748
P(Truc)
.642
.473
-524
.513
.571
.545
.545
SemanticEntropy
849
.758
.690
.591
.755
.774
.736
LexicalSimilarity
842
.766
.713
.656
.739
.756
.745
EigValLaplacian
.677
.766
.701
.633
.739
.775
NumSemSets
.856
.754
.653
.639
.702
.757
Consistency-bused UQ: mudtinomial vv. beamsearch versions
Dissimilarity
.16
836
822
.099
.817
818
.36
Dissimilarity beamsearch
.931
.82
.261
8141
8311
8411
.848
Eccentricity
.897
808
.768
.737
.099
.21
.806
Eccentricity bcamsearch
911f
8161
.7901
.7711
.8311
8591
.830
FigVeeDDisimilarity
902
813
.761
.728
.798
.825
.055
Eig BigVee-Disiiuularitt- + beamsearch
9201
8271
.7711
.7631
8201
8561
8297
CocoaMSP
904
.823
.791
.726
8826
.839
.188
CocoaMSP heamsearch
910t
83667
811f
.7791
8271
.8711
.3551
CocoaPPL
.977
.832
.810
.799
.825
.837
.835
CocoaPPL beamsearch
9121
8451
8231
.8281
8251
.8447
8461
Table 13: PR-AUCT for 6 datasets with Gemma 4B base. For each dataset, the top-1 method is bold and the second-bes best is underlined. Beam-guidee and grobability-weighte variants are marked with t when they improve over their multinomial-samplin baseline. The two rightmost columns report the mean PR-AUC across datasets.
Web Questions
Common senceQA
ARC-
UQ Method
TriviaQA
CoQA
HotpotQA
Mean
Challenge
Baseline UQ methods
Prob
.855
838
A77
.678
.623
.628
.683
.755
874
.555
.799
.558
.540
.699
Perplexity
860
861
.539
814
.629
.632
.722
CCP
866
.833
.475
.715
.676
.641
.704
SAR
865
861
.484
.753
.437
.422
.646
P(True)
.657
.662
.326
.634
.410
.355
.077
SemanticEntropy
838
.233
.456
.649
.572
.511
.642
LexicalSimilarity
833
.488
.144
.711
.545
.509
.660
Eig Vallaaaalaa
.865
.855
.481
.682
.565
.532
NumSemSets
841
.855
.427
.685
.508
.497
.631
Consistency- UQ: mudtinomial vs. beamsearch versions
Dissimilarity Dissimilarity- beamsearch
.91 .991t
.904
.715 .660
.388
.722
.648
.789
.95*
.822
.7541
.931
.744
Eccentricity
888
887
.611
.758
.685
.625
.734
Eccentricity bcamscarch
9061
.84
.566
.7891
.7441
.717
.769
Fig Vigesimiimiylrttty
902
.899
.573
.766
.677
.651
.743
Eig Digssmatisimilarttty + beamsearch
9161
9001
.5881
.7841
.171
.6891
.766*
CocuaMSP
897
894
.605
.761
.711
.680
.758
CocoaMSP heamsearch
9071
.944*
.6321
.001
.715t
.6911
.775*
CocoaPPL
902
.902
.672
.611
.712
.686
.789
CocoaPPL beamsearch
909t
9107
6901
.8811
.718t
6951
.011
25

---

Table 14: PRR ( is better) for 6 datasets with Gemma 3 4B base. For each dataset, the top-1 method is bold and the second-best underlined. Beam-guided and probabilitywwiigheed variants are marked with f when they improve over their multinomial-samae sampling baseline.
Web
Common SenceQA
ARC- Challenge
Method
TriviaQA
CoQA
HotpotQA
Questions
Baseline UQ methods
Prob
.659 0008
.511 10m
.312 0064
.274 1014
.511 1 0.0s
.548 1: 1.0
MTE
2015
.83 1,00
1.
.444 100
.364 6,001
1: 1000
Perplexity
647
.553 1:00
.369
.527
.503
.547
CCP
686 = 0.211
.569 +.00
.326 0822
.337 0.25
.506 0.004
.527 + 0.02
SAR
.656 om
.571 2:ms
.347 0,83
.296 001s
.183 0,887
.264 4: 0.05
P(Truc)
.22
-004
.031
.075
.090
,090
SemanticEntropy
622 0:221
.505 0.222
.301 0.19
_140 + 0/22
.407 0.228
.431 + 0.51
Lexical Similarity
0:17
.40
.349
0.85
.286 0nts
.386 0,882
.392 :: 0.054
Fig apllaainn
666
.555
.320
.246
.386
.452
NumSemSets
656 0.17
.538 0.22
.257 0827
.268 om1
.338 0.00
.454 :: 0.022
Consistency based UQ masltinomial US. beamsearch versions
Dissimilurity Dissimilarity beamsearch
.755 0,19
.715 115=me 005
.578
626 oo0s
.561 0:004
.545 0.03
.766 n.m
.722 t= ncos
.600 timmme
.611 1:m1
.595 71
.604 f= a.se
Eccentricity
.714 0.012
.653 2.09
A59 om
453 onzs
549 0,54
.549 +: 0.54
Recentricity heamsearch
.739 f'1.00 0.0r
.633 1oms
oms
f= 0007
.90 omm
.636 t 0.066
Eig VeeDissimillarity
.738
.661 1000
.443
.488
.512
.562 0.05
Eig EigVeeDissimilarity beamseurch
.753 0u22
.668 8082
497 0m
.487 1= 0016
.522 0
.621 oos
CocoMMSP
.738 0003
.666 oies
.509
.430
.583
.595 0052
CocoaMSP + beamsearch
.747 1+= 0.00
.679 o.
.48 1=
.523 1- 0027
.586 " 0,029
.606 1 0.022
CocoaPPL
.739 o.0s
.688 omes
.488 0.19
.625 0m23
580 0.281
.595
#: 0.09
CocoaPPL beamsearch
.748 + 0.124
.694 1= 0004
0.244
.681 1= now
.582 * o.as
.610
f 0.48
Table 15: PRR (1 is better) for 6 datasets with Gemma 3 4B instruct. For each dataset, the top-1 method is bold and the second-best is underlined. Beam-guided and probability variants marked with f when they improve over their multnoomia--smpplngg baseline.
Web
Common senceQA
ARC- Challenge
UQ Method
TriviaQA
CoQA
HotpotQA
Questions
Baseline UQ methods
Prob
.442 + .08
.45 + .331
.162 .24
.220
.004
+
.252 007
MTE
.534
.465 +
.161 +
.232
.253 :
.256
Perplexity
.422
.419
.157
.223
.252 à
.256
CCP SAR
.533 .211
.478
.117
.303 .025
.264
.290
.533 + 02
.426 + 018
.176 mB
.214 =.018
.033 + 087
.050 055
P(True)
-076 i me
-115 = .34
-161 + .08
-090
:: A25
-046 :: mi
-047 = 048
SemannicFatropyy
.449 MI
1
.166
.223 .01
.254 1: 008
.252
Lexical Similarity
.527
.427
.176
.127
.052
.172
EigValLaplacian
.578 + .144
.422 à
.190
.134 .024
.014 1:
.010
NumSemSets
.556 007
.42 + 828
.123 027
.006 000
.046 0:
.153 042
Consistency-bused UQ: multinomiaa vs. beanseurch versions
Dissimilarity Dissimilarity beamsearch
.549
.415
.111
.068
.024
.070
.413 .033
.321
.204 ++ .016
.273 t+
.18 1++
.085 1 .022
Eecentricity Eccentricity beamsearch
.540
.429
.167
.175 .05
-020
.094
.441 000
.36
.235 +++ .05
.314 1+
.266 f++
.108 1 .065
DissimDtis
.61
.437
.169
.173
-017
.095
Eig EigVecDissimiturit- beamsearch
.478 .00
.416
.240 f o01
308 1+
.253 f++
.113 f
Coc
.531
.456
.183
.198
.252
.266
CocouMSP beamsearch
.335 1
.473 1+
.237 1 nz
.287 1+
.282 1
.258
CocoaPPL
.523
.454
.174
.201
.247 +
.271
CocoaPPL beamsearch
.522 .04
.67 1
.22 fth: .044
.285 T+
277 1
.264
26

---

Table 16: PRR (1 is better) for 6 datasets with Llama 3.1 8B base. For each dataset, the top-1 method is bold and the second-bes is underlined. Beam-guided and seerabiiitywwiihhee variants marked with f when they improve over their multnommial-sapplng baseline.
Web
Common senceQA
ARC- Challenge
LQ Method
TriviaQA
CoQA
HotporQA
Questions
Baseline UQ methods
Prob
.577 .09
+ m29
.310 .02
.213 024
.04
129
.505 143
MTE
.544
.420
.266
.327
448
.511
Perplexity
.507 .05
.44 mm
.366
.375
.501
.570
CCP
.555 .16
.420 i ml
.276 09
.247 029
.422 m0)
.446 0M
SAR
.488 .17
.452 1 m78
.331 + m
.263
4: 811
.189 = 121
.330 à: 06
P(True)
-055 :: nal
1: M25
-020 o18
-,223 1 M06
104
184
SemanticEntropy
.538
.409
.30
.199
.492
.514
Lexical Similarity
.67 003
.396
.366
.289
.43
.511
Eig EigValLaplaccan
569 a09
.418 022
.377
.247 025
.449 .85
.499 047
NumSemSets
.50 014
.409 + 038
.319 o09
.241 m38
.378 105
.477 044
Consistency-basee UQ: multinomial vs. beamsearch versions
Dissimilarity
.576
.45 n24
.473
446
449
.640
Dissimilarity beamseareh
.654 + A17
.504 1 023
.485 ++ A19
.424 A24
.10 + A23
.683 1
Eecentricity
.555 .066
.044 :: nz5
.405
.297 021
464
,591
Eccentricity beamscurch
.613 1++ A2ı
.488 1= .019
.429 f++ 017
.361 1
.122 1++ A25
.657 1
BigVeaDDssimilarity
.570 .15
.422 a: uza
.409
.289
.469
.587
Eig BigNecDDssimillaity beamsearch
.630 1++ .199
.492 1 022
.427 1 0m
.357 *+.00
.506
f++ A35
.650 f 002
CocoaMSP
.555
.458
.463
.366 A21
.10
.641
CocoaMSP bcamscarch
631 1+ n19
.477 1== 023
.465 1 027
.372 11+ 027
.532
1 022
.639 041
CocoaPPL
.587 .017
.44
.464
.465
.501
.660
CocoaPPL + beamscarch
.116 1+ .16
498 1= 029
.459 .044
.456 A18
.25 1't 028
.61 1 046
Table 17: PRR (f is better) for 6 datasets with Llama 3.1 8B instruct. For each dataset, the top- method is bold and the second-best is underlined. Beam-guided and probability-weighee variants marked with f when they improve over their multinomial-samphing baseline.
Web
Common
ARC- Challenge
UQ Method
TriviaQA
CoQA
HotporQA
Questions
senceQA
Baseline UQ methods
Prob
.524 103
à: 036
.213 /02
= 106
.363 644
MTE
.604
.424
.37
.253
.260
.339
Perplexity
.98 -005
.367 025
.662
.221
.255 =.025
.332
CCP
576 m:0
.406 : m28
.291 .18
.265 022
.288
.402 /48
SAR
.599 M0
.420 : 639
.338 004
.236 1: in
.301
= 005
.418 : 04
P(True)
.36
1: 011
.018
034
-011 004
.135
SemanticEntropy
591
388
.335
.231
301
.418
Lexical Similarity
566 .03
.395
.37
.232
.275
.380
EigValLaplacian
615 021
.389 + 826
.35 029
.238 023
.252
.377 051
NumSemSets
569 .01
+
.228 + A8
.180 023
.208 .88
.368 051
Consistency-based UQ: multinomial vs. beamsearch versions
Dissimilarity
616 a066
.382 a
.39
.270 021
.277
.378
Dissimilarity beamseurch
662 1+ .15
.11 1= 029
.358 1+ 029
.349 1+
.288 1+ 832
.34 1+ 054
Eecentricity
.988 .m
.379 a u3
.319
.248 mm
.273
.389
Eecentricity beamseurch
620 1+t m1
.396 t= 027
.330 1 o21
.281 1+ m
.306 1+ .51
451 1+t 047
BigVenDissimilartty
.611 =0009
.378
.325
.249 A29
.264
.390
Eig SigVeeDisiiiilaiity beamscarch
640 T+ A17
.455 1= 023
.37 t++ 027
.291 1++ n22
.318 f++: 034
.461 1 .48
CocoaMSP
629
.099 + ozs
366
.788
314
.426
CocoaMSP bcamscarch
.665 1++ n16
.288 1= 029
.378 T++ 017
344 1++
302
.439 1 .41
CucoaPPL
626 .02
410
.354
.288 024
.299
.413
CocoaPPL + beamscarch
653 1+ .18
427 1= 002
.356 T++ 021
.334 11+.01
.285 +.00
.419 1 056
27

---

Table 18: PRR (1 is better) for 6 datasets with Qwen 3 8B base. For each dataset, the top-1 method is bold and the second- best underlined. Beam- doam-guided and probabilitywwiighhee variants are marked with 1 when they improve over their multinomial saaanooliil---mllnngggg baseline.
Web
Common senceQA
ARC- Challenge
UQ Method
TriviaQA
CoQA
HotpotQA
Questions
Baseline UQ methods
Prob
617 007
.49 m25
= 1
.111 = 003
.337 039
.475 + uss
MTE
.02
.409
.267
.279
.443
.44
Perplexity
.597
.426
.278
.256
.294 945
.381
CCP
644 018
.406 mm
.213 = ms
.153 005
.296 948
.421
SAR
617 1: 063
.57 1. uns
.323 4:
.243 Km8
.220 1942
.317 1: 166
P(True)
.322 021
.282 115
= 161
.168
-043 1 145
-074 069
Semantic Entropy
.549
.111
.247 =
.173
.230 036
.305 1:
Lexical Similarity
.595
.300
.338
.310
.367
.508
EigValLaplacian
602
.23 MZ7
.301
.284
.349 032
.455
NumSemSets
.533 016
403 a29
.268 122
.250 623
.311 039
.367 4: 869
Consistency- bused UQ: multinomiaal vs. beamsearch versions
Dissimilarity
.668
.462
.406 +
.531
.315
.476
Dissimilarity heamsearch
.680 t m19
.484 1 m0
.409 1
.504 01
.335 1 1144
.457 1: 088
Eccentricity
.615
.416
.320
.319
.266 .53
.40
Eccentricity beamsearch
.440 [++ .13
.437 1
.368 1
.407 1 A26
.243
.366
BigsiiiDissmmilarity
628
.454
.325
.314
.373
.456
Big BigVecDissimilurity beamsearch
.660 + uno
.460 1
.380 f
.944 1 uz5
.353 0945
.453
MSP
667
.492
.385 4:
.320
.378
.523
CocoaMSP beamsearch
678 + uns
.498 1
.391 1
.378 1 M29
385 1 107
.10
CocnaPPI.
665
.478
.388
.397
.353
.484
CocoaPPL beamsearch
.67 1 uno
.486 1
.387 1066
.437 t u26
.339 /944
.450
Table 19: PRR (f is better) for 6 datasets with Qwen 3 8B instruct. For each dataset, the top-1 method is bold and the second-best is underlined. Beam- gound and probability weiightd variants marked with f when they improve over their multinomial-samplinn baseline.
Web
Common
ARC-
UQ Method
TriviaQA
CoQA
HotporQA
Questions
senceQA
Chullenge
Baseline UQ methods
Prob
.54 = -001
: 032
.215 +
.250 026
.174 =
.181 078
MTE
.644
.345 : 038
.164
.251
.183
.272
Perplexity
.41
.31
.169
.250
.175
.229
CCP
563 1
.333 02M
.66
.258 029
.173
.202
SAR
.900 .015
.425 : 113
.146 C0s
.159 029
.201
.233 051
P(True)
-105 + .22
-222 .05
-.126 + 017
.018 A22
-088 +
-164 +
Semantic Entropy
.577
214
.231
.174
.176
Lexical Similarity
530
.425 :
.193
.101
.121
.053
FigVall aplacian apllaiann
626 005
A17
.196
.083 034
.134
.134 066
NumSemSets
608 001
.437 + 136
.110 o15
.096 024
.113 DMI
.154 /66
Consistency- based UQ: multinomial US. beamsearck versions
Dissimilarity Dissimilarity beamsearch
.588
.382
.165
.187 A25
.246
.394
637 1+ .18
.386 1= mss
.269 + 019
.264 1+ .os
.213 m8
.362 083
Eccentricity Eccentricity beamsearch
.665 =0099
.367
.167
.125 A23
.150
.132
.000 T+ .16
.392 f= 034
.888 ++ 029
.291 1++ 002
.211 f++: .35
.285 1+ 094
BigVenDiisiiilarity
.900 .004
.385
.169
.121
A22
.143
.131
Eig DigVeeDissimilaitty beamscarch
.645 f+ .16
.439 1= 032
.328 ++ Av9
.297 1++ .13
.242 1++ 029
.066 1+ 058
CocoaMSP
607 -00
.394
.204
.272 023
.230
.298
CocoaMSP bcamscarch
635 1++
.404 1= 024
.263 f++ 023
.282 1++ 025
.066 022
.290 0681
CucoaPPL
581 4
.389 +: 032
.179
.272 A22
.232
.309
CocoaPPL + beamscarch
.099 1+ m
.395 1= .001
.233 T++ 025
.282 1
.207 +.08
.299 084
28

---

E DETAILED DESCRIPTION OF UNCERTAINTY QUANTIFICATION METHODS
In this section, we describe the uncertainty quantification methods used in our experiments.
Sequence Probability (Prob) is the most straightforward approach to uncertainty quantification. We define it formally as the negative log-probability of the generating sequence:
Usp(y x) log P(y x)-
(27)
Mean Token Entropy (MTE) measures an average entropy of tokens in sequence:
1 UMTElY x)) L
Σ H(y y<,x),,
(28)
where H(j Yet, x P(n = y y<t,
log P(n = v y<t,)..
Perplexity computes negative average log- log-likel of tokens a sequence:
UPP x) L
log P(y xx,,
(29)
Claim Conditioned Probability (CCP), introduced in (Fadeeva et al. 2024), measures uncertainty on claim level by perturbing claim's 's tokens with alternative generations:
UCcr(C x) = =1 - II CCP(U, [,,., x).
(30)
jEC
Exsurot
uy)= ay)) P(u (x))))))))
Where CCP(U; x) Lesuef uy)elfe P(u)Tyeyaa)
Shifting Attention to Relevance (SAR) is a method combining TokenSAR and SentenceSAR, as introduced by Duan et al. (2024). SentenceSAR is defined follows:
1
Σ log (p((())) x) + Rs(s x)):
US USentSAR(()
(31)
M
To obtain SAR score, the generative proba- bility p(y x) is replaced with relevance-reweighte probability sequence level. TokenSAR is defined as:
Here, Rs(y()), x)= Exee s((b), (( ( (x) x).
UTokenSAR (x)
y,, log P(u yet,)),
(32)
where RT(-) denotes some token relevance function and relevance weight for token is given by Rr Rykk y,
Rr
Σ Ry (x))
P(True), introduced in (Kadavath et al. 2022). evaluates the confidence in generation by asking the model the original question and answer, then asking if is or false. We then use the negative log- bog-probability of the token "True" as an uncertainty score.
Lexical Similarity, introduced in (Fomicheva et al., 2020), measures average pairwise similarity between M sampled generations using some similarity function s(y.y'):
ULSRR.. (x)
2
s(x(10) y(()).
(33)
M(M 1)
Number of Semantic Sets, introduced in (Lin et al. 2024), estimates how many distinct meanings the model produces by clustering its outputs with NLI model. Two answers placed in the same cluster if they mutually entail each other more than they contradict and the final number of distinct clusters serves uncertainty score UummSeeSets
29

---

Sum of Eigenvalues of Laplacian, introduced in (Lin et al. 2024), constructs a similarity matrix among the sampled outputs and computes a uncertainty score from the eigenvalues of the Laplacian of that similarity matrix:
(xigv(x)=
max(0, (0, - (x)x).
(34)
F COMPUTATIONAL BUDGET
All experiments were rum on 2xNVIDIA A100 (80 GB). Evaluating a single model across all six datasets took approximately 2 wall-clock days this setup (4 GPU-days); with six models, this amounts to 12 wall-clock days (24 GPU--ays). Additional ablations (sampling strategies, top-1 beam scoring, and other objectives) required further 5 wall-clock days the same hardware (10 GPU-days). In total, the study used about 34 GPU-days.
G THE USAGE OF LLMS
In this study, large language models are examined primarily as the focus of analysis. For practical tasks such as programming and writing, we also make limited of LLM-based assistants (e.g., ChatGPT) to support grammar correction and code debugging, with all usage carefully monitored by humans.
30


Reviews:
[{"review_id": "wpiN8ZZk3w", "reviewer": "Reviewer_mkAX", "summary": "Uncertainty quantification is an important topic for LLMs. This paper focuses on the consistency-based methods that measure agreement among multiple generations. The authors argue that multinomial sampling often produces duplicate short answers and high run‑to‑run variance, especially in short‑form QA. They propose replacing samples with beam‑search candidates and computing importance‑weighted consistency scores over the beam set (top‑M). The goals were to reduce duplication, lower estimator variance and achieve efficiency and effectiveness with 'no extra cost', since beam search is already used for decoding.", "questions": "Further on the questions raised in Weakness, please also answer my following questions.\n\n1. Can you report per‑query latency/throughput comparisons for beam vs. multinomial sampling at the same MMM, both when (a) beam is not used for generation and when (b) it is used (to support the “free” claim)?\n\n2. Beyond the sufficient bound, can you measure mBm_BmB​ and provide scatter plots of PRR gain vs.  $m_B$​? Any proxy to estimate the truncation bias on real data?\n\n3. Do the gains persist for longer generations (e.g., multi‑sentence answers, summarization)? If not, why?\n\n4. Can you include exact‑match (or normalized string match) for TriviaQA/WebQ and choice accuracy for MC to corroborate PRR conclusions that rely on AlignScore?\n\n5. Given the sensitivity in Table 8, do you recommend NLI vs. STS depending on task type (factoid vs. conversational vs. MC)? How stable are results across different NLI models?\n\n7. One claimed benefit is reduced run‑to‑run variance. Can you report std/CI of PRR over multiple runs for sampling‑ vs. beam‑based estimators at fixed M?", "limitations": "", "rating": null, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**Interesting problem and good motivation**\n\n> The paper pinpoints a concrete weakness of consistency‑based UQ in short QA: duplicates and variance from multinomial sampling, with evidence (e.g., duplicate rates 30–50% for 2–4 token outputs in TriviaQA with 10 samples) and intuitive illustrations (Fig. 1 and Fig. 2). The proposed beam‑weighted estimator is simple and broadly applicable across prior consistency‑based methods. \n\n**Theoretical analysis**\n\n> The paper provided comparison analysis, covering the MSE of the multinomial MC estimator (unbiased, variance) against the deterministic beam‑weighted estimator (bias from top‑M truncation, but no sampling variance). The resulting condition, for example beam mass $m_B$​ above a threshold (e.g., >0.842 for M=10), is interpretable and aligns with short‑form QA, where top few beams often capture most probability mass. This work shows this condition holds for a sizable subset and more often for short outputs. \n\n**Empirical findings**\n\n> Six datasets spanning closed‑book, open‑book, and multiple‑choice QA, six popular LLMs (base and instruct), and comparisons to a large set of information‑based and consistency‑based baselines implemented via LM‑Polygraph. The principal metric PRR (normalized AURC with AlignScore quality) follows recent UQ benchmarking recommendations.", "weaknesses": "**Limitation in theory**\n\n> While the paper has provided comparison condition, it heavily rely on unknown “inside‑outside” gap and assumed similarity. The estimator is deterministic given a fixed beam set, but it still inherits the bias from top‑M truncation. \n\n**Limitation in scope**\n\n> Most gains are for short answers; the paper itself shows the advantage shrinks as outputs lengthen (Fig. 5). It is unclear whether the approach still helps long‑form generation (summarization, step‑by‑step reasoning), where beam search can become less diverse and costlier.\n\n**Further report on cost claims**\n\n> The paper states UQ is “essentially free” when beam search is already run; however, many UQ pipelines today do not decode with beam for generation (often nucleus/temperature sampling). The paper reports total GPU‑days, but not per‑query latency nor a direct throughput comparison between beam(M) and sampling(M) under matched compute.\n\n**Sensitivity analysis**\n\n> Although STS vs. NLI ablations are shown, results do shift on some datasets (Table 8). The paper also introduces a mass floor $\\epsilon$ for stability, but the “best $\\epsilon$” is case‑dependent (Table 5).\n\n**Baselines selection**\n\n> While diverse beam and temperature sampling are ablated, a natural question is how nucleus/temperature sampling with semantic deduplication (e.g., cluster‑then‑subsample) fares as a competing “low‑variance” sampler for short QA. The hybrid beam+sampling table suggests potential, but a semantic‑dedup sampling baseline would make the case stronger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "22D6t2yo46", "reviewer": "Reviewer_SuGS", "summary": "They propose a new family of UQ methods based on beam search, using importance-weighted estimators to produce distinct candidate outputs. The authors provide a theoretical analysis alongwith an empirical analysis across multiple datasets and models.", "questions": "- How does the method scale to tasks involving longer generations, where the probability mass may be less concentrated on a few beams?\n\n- How does it compare to multinomial sampling technique with averaging of confidence instead of just doing maximal voting?\n\n- How to set beam width for different tasks or LLMs?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is generally well written, well structured and easy to understand.\n\n- It proposes a new way of leveraging beam search for UQ, going beyond routine sampling or decoding tweaks.", "weaknesses": "- The focus is primarily on short QA tasks. It’s not clear how well the approach would generalize to long-form or structured generation, or to tasks with less peaked probability distributions.\n\n- An deeper study on beam width and similarity function for semantic entropy is missing.\n\n- A more intuitive summary and visualization of the main theorem’s impact would increase accessibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LG38gPmImC", "reviewer": "Reviewer_jkE6", "summary": "The paper presents a new uncertainty quantification scheme for LLMs that leverages the sequence probabilities of the multiple beams obtained during the generation phase of the response. This is in contrast to existing consistency-based approaches that typically rely on generating multiple sample responses from the distribution represented by the LLM. The basic idea behind the proposed uncertainty estimator is to weight the disimilarity measure of each sequence by it' s corresponding normalised probability. Furthermore, the paper also shows that several consistency based estimators such as those based on eccentricity or eigenvectors dissimilarity can be expressed in terms of the probabilities of the beams. The experimental evaluation is restricted to QA benchmark datasets and 3 open models from the Llama, Qwen and Gemma families. The results show indeed improved performance over the corresponding UQ schemes that rely on multinomial sampling.", "questions": "- I would be interested to get your perspective if I am to apply your method in summarisation tasks where sequences are longer. How would that affect the sequence probabilities?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Uncertainty quantification for LLM is currently a hot topic and therefore advances in this area are warranted.\n\n- The quality of the presentation is overall quite good and therefore the paper is relatively easy to follow even by readers outside this research area. Most of the technical details presented in the paper are discussed in a relatively clear manner.", "weaknesses": "- The experimental evaluation considers only one generative task, namely QA, where responses are typically fairly short. LLMs are applied to a much wider range of tasks, and therefore it would be very interesting to see how the proposed approach performs in other tasks, such as for example summarisation or text-to-SQL translation.\n\n- The performance improvements appear to be just marginal over the standard multinomial sampling e.g., 0.543 vs 0.505 in Table 3. Standard deviations appear to be missing from the table, and these need to be included to account for the noise. Also, for such mediocre performance bumps, statistical significance tests are mandatory.\n\n- The proposed method assumes access to sequence probabilities and therefore it is not applicable to closed models such as GPT or Gemini. I think this limitation should be made clearer in the presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ewyTnn3fOf", "reviewer": "Reviewer_1K6A", "summary": "The paper targets uncertainty quantification (UQ) for short-form QA where consistency-based methods aggregate multiple generations to estimate confidence. It argues that the standard practice to generate samples via multinomial sampling under a small budget produces many duplicates in peaky distributions. This results in high variance and unstable UQ. The authors propose to use beam-search with probability weighting to obtain samples for the consistency estimator. Experiments across several QA datasets report consistent gains in UQ metrics.", "questions": "* For what answer lengths and budget M does beam-weighted consistency cease to outperform sampling? Any failure cases? \n* Could you discuss whether there are use cases in which beam search produces suboptimal predictions which may lead to unreliable uncertainty estimates?\n* Figure 4 indicates that even for M=1, the PRR of the beam search is comparable with the multinomial sampling with up to M=15 (dissimilarity) and M=5 (eccentricity). Could you explain why the beam search with such small beam width is performing so well? \n* The related works section is relatively short. Work of Hashimoto et al. (2025) is mentioned where different decoding strategies are compared in terms of UQ for different tasks. How is the beam search approach performing in those evaluations? Is the main difference and gain in this paper the combination of beam search with weighted consistency scores?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper clearly motivates the problem and proposes a simple drop-in replacement for multinomial sampling in consistency-based UQ via probability-weighted beam search. It provides a bias–variance analysis with an interpretable beam-mass condition. Experiments on multiple short-form QA datasets show consistent gains, including extensive ablation studies. Moreover, the probability-weighted beams consistently improve other UQ baselines (e.g., semantic entropy), suggesting broader applicability.", "weaknesses": "The improvements appear strongest for short answers, the coverage of probability mass by top-M beams degrades with length (Fig. 3). It’s unclear whether the advantages vanish or even reverse for longer outputs. An additional discussion or experiments on benchmarks with longer outputs could help to clarify.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9BR3nfzVpU", "reviewer": "Reviewer_fdB8", "summary": "The authors propose replacing multinomial sampling with beam search sampling for consistency-based UQ methods. They show that it's even theoretically less erroneous in low-sampling regimes. They verify the proposed method's effectiveness on various datasets and various methods.", "questions": "- Do you have any results for when you combine your idea with other methods that do sampling but use probabilities, such as SE and SAR?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper focuses on an important topic with a neat, focused contribution. \n- The paper is well written.\n- The proposed replacement of multinomial sampling with beam search definitely makes sense.\n- The idea is supported by a clean, small, but necessary theory.\n- Very good ablations and additional experiments with different temperatures and sampling ideas.\n- Clear demonstration of the effectiveness of the idea on various consistency-based methods.", "weaknesses": "- I don't see any major weaknesses, but the impact of the work is probably limited to the UQ community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)