Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities
Authors: Alexander V Nikitin
Jannik Kossen
Yarin Gal
Pekka Marttinen
Venue: NeurIPS 2024 poster (2024)
Keywords: uncertainty quantification
LLMs
Primary area: safety_in_machine_learning
TL;DR: Kernel Language Entropy is a novel method for uncertainty quantification that utilizes semantic similarities in the form of kernels over the space of outputs.

Abstract: Uncertainty quantification in Large Language Models (LLMs) is crucial for applications where safety and reliability are important. In particular, uncertainty can be used to improve the trustworthiness of LLMs by detecting factually incorrect model responses, commonly called hallucinations. Critically, one should seek to capture the model's semantic uncertainty, i.e., the uncertainty over the meanings of LLM outputs, rather than uncertainty over lexical or syntactic variations that do not affect answer correctness.
To address this problem, we propose Kernel Language Entropy (KLE), a novel method for uncertainty estimation in white- and black-box LLMs. KLE defines positive semidefinite unit trace kernels to encode the semantic similarities of LLM outputs and quantifies uncertainty using the von Neumann entropy. It considers pairwise semantic dependencies between answers (or semantic clusters), providing more fine-grained uncertainty estimates than previous methods based on hard clustering of answers. We theoretically prove that KLE generalizes the previous state-of-the-art method called semantic entropy and empirically demonstrate that it improves uncertainty quantification performance across multiple natural language generation datasets and LLM architectures.

Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities
Alexander Nikitin
Jannik Kossen
Yarin Gal?
Pekka Marttinen
Department of Computer Science, Aalto University
OATML,, Department of Computer Science, University of Oxford alexander. nikitin@aalto..f
Abstract
Uncertainty quantification Large Language Models (LLLMs) is erucial for appli- cations where safety and reliability are important. In particular, uncertainty can be used to improve the trustworthiness of L.LMs by detecting factually incorrect model responses, commonly called hallucinations. Critically, one should seek to capture the model's semantic uncertainty, i.e., the uncertainty over the meanings of LLM outputs, rather than uncertainty over lexical or syntactic variations that do not affect answer correctness. To address this problem, we propose Kernel Language Entropy (KLE), novel method for uncertainty estimation in white- and black-box LLMs. KLE defines positive semidefinite unit trace kernels to encode the semantic similarities of LLM outputs and quantifies uncertainty using the von Neumann entropy. It considers pairwise semantic dependencies between answers (or semantic clusters), providing more fine- fine-grained uncertainty estimates than pre- vious methods based on hard clustering of answers. We theoretically prove that KLE generalizes the previous state-of-the-art method called semantic entropy and empirically demonstrate that it improves uncertainty quantification performance across multiple natural language generation datasets and LLM architectures.
Introduction
Large Language Models (LLMs) have demonstrated exceptional capabilities across wide array of natural language processing tasks [58, 66, 69]. This has led to their application many domains, including medicine [11], education [32], and software development [40]. Unfortunately. LLM genera- tions suffer from so-called hallucinations, commonly defined as responses that are "nonsensical or un- faithful to the provided source content" [26, 18, 52]. Hallucinations pose significant risks when LLMs are deployed to high-stakes applications, and methods that reliably detect them are sorely needed.
A promising direction to improve the reliability of LLMS is estimating the uncertainty of model generations [36, 13, 51, 44, 23]. For instance, high predictive uncertainty indicative of model errors or hallucinations in settings such as answering multiple-choice questions [30]. This allows us to prevent harmful outcomes by abstaining from prediction or by consulting human experts. However, the best means of estimating uncertainty for free-form natural language generation remains active research question. The unique properties of LLMs and natural language preclude the application of established methods for uncertainty quantification [20, 39, 45, 59, 55].
particular challenge is that language outputs can contain multiple types of uncertainty, including lexical (which word is used), syntactic (how the words are ordered), and semantic (what a text means). For many problems, semantic uncertainty the desired quantity, as it pertains directly to the accuracy of the meaning of the generated response. However, measuring the uncertainty of the generation via token likelihoods conflates all types of uncertainty. To address this, Kuhn et al. [36] have recently introduced semantic entropy (SE), which estimates uncertainty as the predictive entropy of generated texts with respect to clusters of identical semantic meaning (we discuss this more detail in Sec. 2).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Laplace
LLM, imp)
Semantic Entropy (SE)
Kernel Language Entropy (KLE)
LLM,
Einstein
Entropy
[inp] Which scientists contributed probability theary?
CF McCartncy
Semantic Kernels
A SE
A KLB
Laplace
(LMo(iop)
LLM,
Semantic Similarity
Cj: Kohmogorov and Laplace
CJ: Kolmogorov, Buler, and Laplace
Figure I: Illustration of Kernel Language Entropy (KLE). We here show a version of KLE called KT.F-c, which operates on semantic clusters. Given an input query and two different L.Mss, sample 10 answers from each model 01, 01,-.-- 010 and ai....,, 411 and cluster them by semantic equivalence into clusters Ci...., , C3 and Ci.... ................................ Ci.. For the sake of the example, the numbers and sizes of clusters, as well as individual cluster probabilities, are all equal p [C:]jnp)) p(C])inp) for all i. Then, semantic entropy would yield identical uncertainties for both LLMs. How- ever, uncertainty should be lower for LLM, because semantic "similarity" between the generations is much higher; i.e., the model fairly confident that "Kolmogorov" and "Laplace" are good answers. KLE, explicitly accounts for the semantic similarity between texts using a kernel-basee approach. Se- mantic kernels provide an effective way to encode the semantic similarity between answers, enabling the method to correctly identify that LLM2 's outputs should be assigned lower uncertainty (see right).
assume that
critical limitation of SE is that it captures semantic relations between the generated texts only through equivalence relations. This does not capture distance metric in the semantic space, which would allow one to account for more nuanced semantic similarity between generations. For instance, it separates "apple" as equally strongly from "house" as it will "apple" from "granny smith" even though the latter pair is more closely related. this paper, we address this problem by incorporating distance in the semantic space of generated answers into the uncertainty estimation.
We propose Kernel Language Entropy (KLE). KLE leverages semantic similarities by using a distance measure in the space of the generated answers, encoded by unit trace positive semidefinite kernels. We quantify uncertainty by measuring the von Neumann entropy of these kernels. This approach allows us to incorporate metric between generated answers or, alternatively, semantic clusters into the uncertainty estimation. Our approach uses kernels to describe semantic spaces, making KLE more general and better at capturing the semantics of generated texts than the previous methods. We theoretically prove that our method is more expressive than semantic entropy, meaning there cases where KLE, but not SE, can distinguish the uncertainty of generations. Importantly, our approach does not rely on token likelihood and works for both white-box and black-box LLMs.
Our work makes the following contributions towards better uncertainty quantification in LLMs:
We propose Kernel Language Entropy, novel method for uncertainty quantification in natural language generation (Sec. 3),
We propose concrete design choices for our method that are effective in practice, for instance, graph kernels and weight functions (Sec. 3.2).
We prove that our method is a generalization of semantic entropy (Thm. 3.5),
We empirically compare our approach against baselines methods across several tasks and LLMs with up 70B parameters (60 scenarios total), achieving SoTA results (Sec. 5).
We release the code and instructions for reproducing our results at https: com/ MlexanderWiikttiikkeen www.eeereee-nngggeeeeeeeee language-entrope
2 Background
Uncertainty Estimation. Information theory [49] offers principled framework for quantifying the uncertainty of predictions the predictive entropy of the output distribution:
PE(z) H(Y x)) f ply x) log ply x)dy.
(I)

---

where Y is the output random variable, is the input, and H (z)) is conditional entropy which represents average uncertainty about Y when is given. Uncertainty is often categorized into aleatoric (data) and epistemic (knowledge) uncertainty. Following previous work on uncertainty quantification in L.LMs, we assume that L.MMs capture both types of uncertainty [30] and do not attempt to disambiguate them, as both epistemic and aleatoric uncertainty contribute to model errors.
UQ in sequential models. Let S T be a sequence of length N, consisting of tokens, 8; T, where the set T denotes a vocabulary of tokens. The probability of S is then the joint probability of the tokens, obtained as the product of conditional token probabilities:
p( x)) = II, p(s)
(2)
Instead of Eq. (2), the geometric mean of token probabilities has proven to be successful in practice
[50]. Using Eq. (1) and (2), we can define the predictive entropy of sequential model. Definition 2.1. The predictive entropy for random output sequence S and input is
U U(x) H( 2) = =, p(s x) log(p(s x)),
where the sum is taken over all possible output sequences s.
A downside of naive predictive entropy for Natural Language Generation (NLG) is that it measures uncertainty in the space of tokens while the uncertainty of interest lies in semantic space. As an illustrative example, consider two sets of n answers, S; and S sampled from two LLMs with equiva- lent token likelihood p(Sa(z) [z) = p(S (r) as a response to the question "What is the capital of France?" [36]. Suppose the answers from the first LLM are various random cities ("Paris"" "Rome", etc.), and those from the second L.M are paraphrases of the correct answer "It is Paris". Naive predictive entropy computation can give similar values, even though the second L.IM is not uncertain about the meaning of its answer. Kuhn et al. [36] have proposed semantic entropy to address this problem.
We first define the concept of semantic clustering, Semantic clusters equivalence classes obtained using& a semantic equivalence relation, E(:-), which is reflexive, symmetric, and transitive and should capture semantic equivalence between input texts. In practice, E is computed using bi- directional entailment predictions from a Natural Language Inference (NLI) model, such as DeBERTa [22] or a prompted LLM, that classifies relations between pairs of texts as "entailment," "neutral," or "contradiction" " Two texts are semantically equivalent if they entail each other bi-directionally. Semantic clusters are obtained by greedily aggregating generations into clusters of equivalent meaning. We can now define semantic entropy.
Definition 2.2. For an input x and semantic clusters C E 2 where Q is a set of all semantic clusters, Semantic Entropy (SF.) is defined as
Σn(s p(s) x)) 1)
SE(x)=
Σ PCC 1x) CEO
x)= =
Σ p(s x)) SEC
log
(4)
CEn
SEC
In practice, is not possible to calculate Ee p(C x) logp((C x)) because of the intractable number of semantic clusters. Instead, SE uses Rao-Blackwellizeed Monte Carlo estimator
SE(x) ~ Σ p' ((((//
(5)
where C, are M clusters extracted from the generations and pC(C, 2)) is a normalized semantic probability, p', | z) A(Cla))/E, which refer to as p(C,|z) in the following for simplicity. SE can be extended to cases where token likelihoods are not available by approximating p(( (C,lz) with the fraction of generated texts in each cluster, p(C,(z) RJ Mm I(S. e C.)/N. We refer to this variant as Discrete Semantic Entropy [16].
3 Kernel Language Entropy
This section introduces Kernel Language Entropy (KLB), our novel approach to computing semantic uncertainty that accounts for fine-grained similarities between generations for better uncertainty quantification. We introduce two variants of KLE: the first, simply called KLF,, operates directly on the generated texts, and the second, KLE-c operates on the space of semantic clusters.
3

---

Motivating Example. Figure 1 illustrates the advantages of KLE (to be precise, the KLE-c variant) over other methods such as SE. Imagine querying two LLMs such that the outputs of LLM, are all semantically different and those of LLM22 are semantically similar but not equivalent. For simplicity, we assume an equal amount of clusters between L.MMs and equal likelihoods of clusters (C,]linp) = p(C) inp). SE would not distinguish between those cases and, thus, would misleadingly predict equal uncertainty. KLE on the other hand, will correctly assign lower uncertainty to the outputs of LLM2, its kernels accounting for the fact that LLM2 produces semantically similar outputs.
Before introducing KLE, we recall the definition of a positive semidefinite (PSD) kemel.
Definition 3.1. For a set X' + 0, a symmetric fortmtetiiicfcciionnnn K X X all n > 0, E X, E IR
R. is called PSD kernel for
En
(2aKK(I1 E",E",a,,,K 2 0.
(6)
For a finite set X, a PSD kernel is PSD matrix of the size (X|
3.1 Semantic Kernels and KLE
Next, we define semantic kernels, denoted Ksem as unit trace' positive semidefinite kernels over the finite domain of generaled texts. Unit trace PSI) matrices also called density matrices. These kernels should, informally speaking, capture the semantic similarity" between the texts such that (si,tt)) > (s2, t2) if and only if texts $1 and t are more semantically related than texts $2 and 12. Analogously, we define semantic kernels over semantic clusters of texts, in which case the kernel should capture the semantic similarity between the clusters. practice, there are multiple ways to concretely specify proper semantic kernel, and some options are described in Section 3.2.
The von Neumann Entropy. We propose use the von Neumann entropy (VNE) to evaluate the uncertainty associated with a semantic kernel.
Definition 3.2 (Von Neumann Entropy). For a unit trace positive semidefinite matrix A E Ruxn, the von Neumann entropy (VNE; (72]) is defined
VNE(A) - Tr[AAlg A].
(7)
can be shown that VNE(A)= = Σ. -A, log d where Ao 1 S i < are the eigenvalues of A. Within this defimition, we assume 0 log 0 = O. This reformulation shows that VNE is, in fact, the Shannon entropy over the eigenvalues of kernel.
Kernel Language Entropy (KLE). We can now define Kernel Language Entropy, as the VNE of a semantic kernel.
Definition 3.3 (Kernel Language Entropy). Given set of LLM generations St...., SN. input and semantic kernel K5om over these generations and input, we define Kernel Language Entropy (KLE) as the von Neumann entropy of semantic kernel Ksom
KLE(2) VVE( semm).
(8)
The von Neumann entropy has the following properties, which are aligned with the overarching goal of measuring the uncertainty of set of generations.
Proposition 3.4 (Properties of the von Neumann Entropy [5]). The VNE of a unit trace positive semidefinite kernel has the following properties:
1. The VNE of a kernel with only one non-zero element is equal 0.
2. The VNE is invariant under changes of basis U: VNE(K) VNE(UKU")
3. The VNE is concave. For set of positive coefficients os, Σ ai 1, and density
matrices K,, it holds that VNE (Etn (Einoa az Et VNE(K,).
I Kerelss with Tr[K] = are called unit trace kernels. Or more broadly semantic relatedness, including antonymy, meronymy, well semantic similarity [7].

---

Let us briefly discuss the practical implications of these properties. Property 1 states that if an LLM outputs a single answer (for KLE) or a semantic cluster (for KLE-c), the VNE is zero, indicating high certainty. Property 2 is significant as it allows the VNE to be calculated in practice as the Shannon entropy of the diagonal elements of an orthogonalized kernel, which can be interpreted as a disentangled representation of semantic kernel. Property 3 states that entropy is concave, meaning that the entropy combined system is greater than or equal to the entropy of its individual parts, a common requirement for entropy metrics. The intuition behind our use of the VNE for LLMs also relates to its origins in quantum information theory.
The VNE in Quantum Information The- ory. In quantum information theory, the states of quantum system (or pure states) are defined as unit vectors in C.V. However, experiments often result in statistical mixtures of pure quantum states, represented as density matrices.
Algorithm 1 Kernel Language Entropy
Require: LLM, Input E T Number of sam- ples n, Boolean kle-c indicating variant, Se- mantic kemels K;
1: Initialize a multiset of answers O <
The VNE is used to evaluate the entropy of the mixed states. Analogously, we can think of KLE as considering each answer as mixture of pure "semantic meanings", measuring the entropy of this mixture. We refer the reader to Aaronson [1] for further background reading on the VNE and quantum information theory.
2: for k <- 1 do -Sampling n answers
3: Add LLM((x) to O
4: end for
5: if kle-c then
6: Update O + cluster(O)
in [36]
7: end if
8: Combine (,)O,0) in Ksem
see Sec. 3.2 b Eq. (8)
9: Return VNE(K
KLE-c. Instead of defining semantic kernels directly over individual model generations, we can also apply KLE to clusters of semantic equivalence. We call this variant of our method KLE-c, Although KLE is more general than KLE-c for non- con-trivial clusterings, KLE-c can provide practical value as it is cheaper to compute and more interpretable due to its smaller kernel sizes.
Algorithm. Algorithm 1 provides a generic description of the steps required to compute KLE. We describe the practical details for defining and combining semantic kernels later in Sec. 3.2.
Computational Complexity. The computational complexity of KLE is approximately identical to SE which requires sampling from LLM N times and running the entailment model O(N2) times. Additionally, KLE requires ( elementary operations for kernel and VNE calculation. The actual cost of this is negligible in comparison to the forward passes through the LLM entailment model.
3.2 Semantic Graph Kernels
This section describes a practical approach for constructing semantic kernels over LLM generations semantic clusters. Concretely, apply NLI models to construct semantic graphs over the LLM outputs and then borrow from graph kernel theory to construct kernels from these graphs. A similar notion of semantic graphs derived from NLI models was proposed by Lin et al. [44] for black-box LLM uncertainty quantification.
First, let us recall the basics of graph theory. A graph is pair of two sets G = E), where V {l..... . n) is set of n vertices and E C V x is a set of edges. A graph is called weighted when a weight is assigned to each edge, and the weight matrix Wi contains weights between nodes i and j. For unweighted graphs, we can use a binary adjacency matrix to encode edges between nodes. The degree matrix D is diagonal [V| x [V| matrix with Wiy. The graph Laplacian is defined as L = D W. is a positive semidefinite
Graph Theory Preliminaries.
D2 Σド= == matrix, and eigenvalues of L are often used to study the structure of graphs [10, 71].
Semantic Graph. We define semantic graphs as graphs over LLM generations (Guem or semantic clusters (G) For Gsem. edges can be defined as a function of NLI predictions in both directions: Wi = J(NT.T(S,, S₁), NL,(S,, St)), where NLT are the predicted probabilities for entailment, neutral, and contradiction for S, and SJ- For example, f could be the weighted sum over the predicted probabilities for entailment and neutral classes. For Gsemo-es the weights between the clusters are computed by summing the entailment predictions over the generations assigned to the clusters, Wij Σsec; Eiec, f(NLI(s, s, t), NLI(t, s)).
Graph Kernels. When a semantic graph is obtained, KIE calculates graph kernels over semantic graph nodes to compute a distance measure. Since graphs are discrete and finite, any positive
5

---

[V] = 10
[V| =
[V] = 30
[V =
1.0
0.8
0.50
0.6-
VNE
(1),1) large
0.41
00.25
0.2
0.0
K (1%, n] for a small
Number of Edges
Large VNE dense
collapse
Figure 2: Entropy Convergence Plots for heat kernlls. For graphs of various sizes V we grow the number of edges and examine the VNE. For large lengthscales t, corresponding darker colored curves, the VNE quickly converges to zero. We can use these plots to determine kernel hyperparameters without validation sets. The VNE is scaled to start for visualization purposes.
semidefinite matrix would be a kernel over the graph. However, we seek kernels that exploit knowledge about the graph structure. We, therefore, adopt Partial Differential Equation (PDE) and Stochastic Partial Differential Equation (SPDE) approaches to graph kernels [34, 6, 57]. R is a signal over the nodes of graph, the heat kernel solution to the partial differential equation fat + Lu = 0 and the Matérn kernel is a solution to the stochastic differential equation, (20//22 + L) u = w, where w is white noise over the graph nodes and is the graph Laplacian defined above. The corresponding solutions to these equations are:
(9) These kernels allow for the incorporation of a distance measure that reflects the graph's locality properties (right part of Fig. 2). For example, the Taylor series of the heat kernel can be shown to be equal to a sum of powers of random walk matrices. Both kernels have hyperparameters: lengthscales l in the heat kernel, in Matérn kernels, and in the Matérn kernel, often interpreted as smoothness. The scaled eigenvalues of the Matérn kernel converge to the eigenvalues of the heat kernel [6] when goes to infinity. Matérn kernels provide more flexibility the additional parameter. Note that any kernel can be normalized into a unit trace kernel via K ((x, y) K (z. y)( x) (y. 8)) -1/2/N, where N is the size of K. We refer [34, 57, for further background reading on graph kernels.
Ke=
[HEAT]
Kμx = (20/22+
[MATÉRN].
the cost of
Kernel Hyperparameters. We propose ways to select the hyperparameters of the heat and Matérn kernels: either by maximizing the validation set performance or by selecting parameters from what call Entropy Convergence Plots, illustrated in Fig. 2. We obtain these plots by defining set of progressively denser graphs G <... < GK. These can be obtained by starting from graph without edges and fixed number of vertices and adding new edges either randomly by filling in the adjacencies of each node sequentially. We then plot the VNE against the number of edges in the graphs G, We analyze the von Neumann entropy over these plots to avoid pathologies connected to the fact that for large lengthscales, the VNE converges rather quickly, and such behavior should generally be avoided. For all remaining values, we can either choose hyperparameters randomly from the range of non non-collapsing hyperparameters or rely on prior domain knowledge.
Kernel Combination. KLE offers the additional fiexibility of combining kernels from various methods (e.g., multiple NLI models, different graph kernels, or other methods). For example, we can combine multiple kernels using convex combinations, K Σi= Oi Kú, where E
04
3.3 Kernel Language Entropy Generalizes Semantic Entropy
The semantic kernels used in KLE are more informative than the semantic equivalence relations used in SE [36]. The next theorem shows that KLE can recover SE for any semantic clustering.
Theorem 3.5 (KLE and KLE-c generalize SE). For any semantic clustering, there exists a semantic kernel over texts Kaom (s, such that the VNE of this kernel is equal to semantic entropy (computed as Eq. (5)). Moreover, there exists a semantic kernel over clusters K Kem, c') such that the VNE of this kernel is equal to SE.

---

Proof Sketch. For any semantic clustering, we consider a kernel with a block diagonal structure. Each block corresponds the cluster, //C, This is valid semantic kernel and the KLE for this kernel equals the SE. Thm. B.1 and Thm. B.2 in the Appendix contain the detailed proofs.
semantic cluster, and cluster likelihoods are normalized by the size of
The proof of Thm. 3.5 shows that the block diagonal semantic kernels used with KLE can recover semantic entropy for any clustering. However, there other kernels available that allow KLE to be more expressive than SE. Comparing KLE and KLE-c, we find that KLE is more general than KLE-c for any non-trivial clustering.
4 Related Work
In the context of machine learning, the VNE has been studied theoretically(4), applied to GAN regularization [33], and the exponential of the VNE has been used for effective rank and sample diversity analysis [64, 19].
The first attempts at estimating the entropy of language date back to the 1950s [65], and today, techniques for uncertainty quantification are widely used in natural language processing. For instance, Desai and Durrett [15] and Jiang et al. [28] presented calibration techniques for classification tasks. Xiao and Wang [73] empirically showed that, for various tasks, including sentiment analysis and named entity recognition, measuring model uncertainty can be used to improve performance. Calibration techniques have also been applied in machine translation tasks improve accuracy [37].
Malinin and Gales [50] discussed the challenges of estimating uncertainty in sequential models. Several previous works have queried LLMs to elicit statements about uncertainty, either via fine- tuning or by directly including previous LLM generations in the prompt [30, 9, 54, 43, 53, 21, 63, 68, 12, 74, 36]. Zhang et al. [76] studied UQ for long text generation. Quach et al. [61] used conformal predictions to quantify LLM uncertainty, which is orthogonal to the approach we pursue here. Yang et al. [75] have shown that Bayesian modeling of LLMs using low-rank Laplace approximations improves calibration in small-scale multiple-choit settings. Lin et al. [44] extended the work of Kuhn et al. [36] semantic entropy by introducing the use of the Laplacian of semantic graphs and applying spectral graph analysis for UQ in black-box LLMs. Aichberger et al. [2] proposed a new method for sampling diverse answers from LLMs, and Liu et al. [47] proposed improving calibration by adding an extra linear layer; more diverse sampling strategies and better calibration could improve KLE as well.
There are a variety of ways besides model uncertainty to detect hallucinations in LLMs such as querying external knowledge bases [17, 42, 70], hidden state interventions [77, 24, 46), using probes [8, 41, 48], or applying fine-tuning [31, 67]. KLE is complementary many of these directions and focuses on estimating more fine- -ra-grdi semantic uncertainty. It can either be used to improve these approaches or be combined with them sequentially.
Experiments
Datasets and Models. Our experiments span over 60 dataset-model pairs. We evaluate our method on the following tasks covering different domains of natural language generation: general knowledge (TriviaQA [29] and SQuAD [62]), biology and medicine (BioASQ [35]), general domain questions from Google search (Natural Questions, NQ [38]), and natural language math problems (SVAMP [60]). We generally discard the context associated with each input for all datasets except SVAMP, as the tasks become too easy for the current generation of models when context is provided. We use the following LLMs: Llama-2 7B, 13B, and 70B [69], Falcon 7B and 40B [3], and Mistral 7B [27], using both standard and instruction-tune versions of these models. As the NLI model for defining semantic graphs or semantic clusters, we use DeBERTa--Large-MNN (22).
Baselines. As baseline methods, we compare KLE with semantic entropy [36], discrete semantic
entropy [16, 36), token predictive entropy [50], embedding regression [16], and P(True) [30]. For embedding regression, we train a logistic regression model on the last layer's hidden states to predict whether given LLM answer is correct.
KLE Kernels. We propose to use the following two semantic kernels with KLE: KHEAT and KYULL- Both are obtained from the weighted graph Wo w NLI SS,, + w (S, (S,,S,)) where (1, 0.5, 0) is weight vector. Here, assume that NLI' returns one-hot prediction over
7

---

Table I: Detailed experimental results for Llama 2 70B Chat and Falcon 40B Instruct.
Method
AUROC
BinASQ [25]
AUARC
AUROC
[Q
AUARC
AUROC
SQHAD
AUARC
AUROC
SVAMP [60]
AUARC
AUROC
Trivia
AUARC
[29]
SE (36)
0.74 2. D.04
0.90 2 0.00
0.71 4 0.03
0.47 2: 0.03
0.66 2: 0.03
0.65 2 0.05
0.62 2: 0.03
0.61 2: 0.03
0.77 2: 0.03
0.79 2 0.02
DSR [56]
0.75 : 0.04
0.90 : 0001
0.71 1: 1.003
0.46 : 0.03
0.66 6:03
0.65
+ 0.03
0.63 1-003
0.61 +0003
0.77 : 1-003
0.79 0.002
Falson 40B lostr Lhmma 7000
PE [50]
0.69
0.90
0.67 000
0.44 0003
0.65
0.65
003
0.59
1: 0003
0.58 a 000
0.61 ::
0.33 0003
|
0.86
0.92
0.78
0.50
0,09
0.24
1.000
0.68
0.26 0:003
1.002
FR
KLE(Kassr
0003
0.78
0.51
0.71 2003
0.68
0.76
KLE p
0.88
0.92
0.77
0.02
0.50
0.70 ::
0.68
0.03
0.70
0.65
0.80
0.81 0.02
SF [36]
0.85 0.02
0.90
001
0.78
003
0.43
003
0.66 003
0.63 003
0.66
003
0.63
0.3
0.79
001
0.72 0.3
DSE [36]
0.85
0.89
0.77
0.40
0.66
0.62 0.0
0.67
0,61
0.79
0.71 à 0.0
PE [50]
0.71
0003
0.87
0.71
0.7
0.66
0.61
0.73
0.67
0.22
0.09
FR
0.74
0,8
0.0
0.73
0.63
0.61
0.75
0.68
0.76
0.69 0.03
KLE(Kan (ana))
0.92
[101
0.91
2: 0100
0,76
0003
0.42
0003
0.70
2: 0103
0.66
0.03
0.77
0002
0.68
0003
0,80
000
0.74 2: 0103
KLE )
0.90
=: 0.02
0.91
2: 0.00
0.78 0.03
0.43
= 0.03
0.69
2: 0.03
0.65
2: 0.03
0.69
: 0.03
0.64
: 0.03
0.80
0.03
0.73 : 0.03
KLE(
KLE(K
Pttrel
P(1rms)
DSE
SE
DSE
0:20
0.27
0.77
0.78
0:90
0.88
KI. KI.
01:00
0.75
0.90
0.70
0.88
0:91
0.8
0.8
KLB((Kor)))
0.60
0.72
0.77
0.83
0:90
0.58
KIR (R(oe))))
0.00
0.70
0.93
775
0.92
0:90
SE
0.23
0.28
0:30
0.57
0
0.50
0.6
SE
0.25
0.30
0.55
0.58
0.87
0.89
0.6
DSE
0:23
0.23
0.70
60
0
0.55
DSE
0.10
0.07
0.15
0.53
0.77
0.
P(Tuee)
11222
0:17
0.43
0.40
0.55
0.70
0..
P[Tuee]
11.31
11:25
0.02
0.17
0.57
0.711
0.4
PE
1.10
0.10
0.18
0.13
0.45
0.87
PE-
0.32
1.088
0.13
0:27
0.43
0.68
0.2
0.2
ER
1.12
0.12
0.20
0.15
0.33
00.33
KR
0.30
1.10
0:18
0.23
0.30
01.32
(a) Win rate measured with AUROC
(b) Win rate measured with AUARC
Figure 3: Summary of 60 experimental scenarios. Each cell contains the fraction of experiments where method from a row outperforms method from a column. Our methods are labeled KLE(-). Values larger than or equal to 0.62 and less than or equal to 0.38 correspond to the significance level p < 0.05 according to the binomial statistical significance test.
(entailment, neutral class, contradiction). KHEAT is a heat kernel over this graph. We further propose KFULL- KHEAT + (1 Ksg. where a E [0, 1] and KSE is semantic entropy kernel. We ablate these kernel choices in our experiments below.
Evaluation metrics. Following previous work, we evaluate uncertainty methods by measuring their ability to predict the correctness of model responses, calculating the Area under the Receiver Operating Curve (AUROC). Further, uncertainty metries can be used to refuse answering when uncertainty is high, increasing model accuracy on the subset of questions with uncertainty below threshold. We measure this with the Area Under the Accuracy-Rejection Curve (AUARC, [56]). The rejection accuracy at a given uncertainty threshold is the accuracy of the model on the subset of inputs for which uncertainty is lower than the threshold; the AUARC score computes the area under the rejection accuracy curve for all possible thresholds.
Sampling. We sample 10 answers per input via top-K sampling with K = 50 and nucleus sampling with p 0.9 at temperature T 1. To assess model accuracy, we draw an additional low-temperature sample (T = 0.1) and ask an additional LLM (Llama 3 8B Instruct) to compare the model response to the ground truth answer provided by the datasets. We evaluated the accuracy-checking performance of Llama 3 8B Instruct by comparing its assessments with human raters, finding 90% agreement across 100 cases. We also compared its evaluations with GPT-4 evaluations on the TriviaQA dataset, using answers generated by Mama--2-70-chann and observed 95% agreement.
Statistical significance. We assess statistical significance in two ways. First, we run a large number of experimental scenarios (60 -dtasst pairs), and second, for each experimental scenario, we also obtain confidence intervals over 1000 bootstrap resamples. We note that standard errors each scenario are more representative of the L.M and the dataset rather than the method. Therefore, our main criterion for comparing the methods based on the fraction of experimental cases where our method outperforms baselines (assessed with a binomial statistical significance test).
8

---

KLE outperforms previous methods. We compare the performance of UQ methods over 60 scenarios (12 models, five datasets). Figure shows the heatmaps of pairwise win rates. We observe that both our methods, KTFF HHAT)) and KTFF (uuL),, are superior to the baselines. Furthermore, Table shows the detailed results for the two largest models from our experiments, Llama 2 70B Chat and Falcon 40B Instruct. The results show that for the largest models, our method consistently achieves best results compared to baselines. In Fig. D.3 and Fig. D.4, we show the experimental results for all considered models. Importantly, our best method, KLE(KmeAT). does not require token-level probabilities from a model and works in black-box scenarios.
KLE hyperparameters can be selected without validation sets. We compare the strategies of hyperparameter selection from Sec. 3.2: entropy convergence plots and validation sets (100 samples per dataset except for SVMMP, where we used default hyperparameters). We observe that default hyperparameters achieve similar results as selecting hyperparameters from validation sets and conclude that choosing default hyperparameters from entropy convergence plots is good way to select hyperparameters in practice. In Fig. 4, we compare the two strategies for selecting hyperparameters, and see that the ranking of the methods remains stable and the pairwise win-rates are similar for both methods.
Method Selection
Many design choices outperform existing methods, the best KLE((KEAF) Next, in Fig. 4, we compare several design choices for KLE: choosing kernel (heat or Matérn), using KLE-c, combining kernels via a weighted sum or product, and using the probabilities returned by DeBERTa for edge weights. The superscript indicates the type of a graph: no superscript indicates a weighted graph as described above, DB means weights are assigned using probabilities from DeBERTa, and C means weighted graph over clusters (KLE-c). The subscript indicates the semantic kernels: SE stands for diagonal kernel with semantic probabilities (KSE), HEAT and MATÉRN for the type of kernel (KhEAt and MATERN)) and for the best of Heat and Matérn kemelss. We observe that even though all design choices outperform SE, the heat kernel over a weighted semantic graph, KLE(KHeAT), was overall the best. Additionally, we notice that the methods based on token likelihoods are performing better for con-instruccion-tte -uned models, and we can practically recommend including semantic probabil- ities (e.g., use variations of K if KLE is used in non coon-intruuttonn-i tuned scenarios (see Fig. D.5).
KuzAr
Validation
Kaarda
Default
kin
Ky Ksu
Kyeu
KS KSE
KPULL
SE
0.2
0.4
0.6
Average pairwise win rate
Figure 4: Comparison of various design choices for semantic graph kernels. represents the best hyperparameters and defaults. Error bars twice the standard error. Summary of 48 experiments. KLE consistently outperformed SE across all the kernlss evaluated.
KLE is better in practice because it captures more fine-grained semantic relations than SE. The performance of KLE improves over SE because in complex free-form language generation scenarios, such as those studied here, LLMs can generate similar but not strictly equal answers. SE assigns these to separate clusters, predicting high entropy. By contrast, our method can account for semantic similarities using the kernel metric in the space of meanings over generated texts, and predict reduced uncertainty if necessary. We give a detailed illustrative example for which KLE provides better uncertainty estimates than SE from the NQ Open dataset in Fig. C.2.
6 Discussion
Measuring semantic uncertainty in LLMs is challenging and important problem. It requires nav- igating the semantic space of the answers, and we have suggested method, KLE, that encodes a similarity measure in this space via semantic kernels. KLE allows for fine fine-grained estimation of uncertainty and is an expressive generalization of semantic entropy. We provided several specific design choices by defining NI.I-based semantic graphs and kernels, and studying kernel hyperpa- rameters. We have evaluated KLE across various domains of natural language generation, and has demonstrated superior performance compared to the previous methods. Our method works both for

---

white- and black-box settings, enabling its application to a wide variety of practical scenarios. We hope inspire more work that moves from semantic equivalence to semantic similarity for estimating semantic uncertainty in LLMs.
Broader Impact. Our work advances the progress toward safer and more reliable of L.MMs. KLE can positively impact areas that involve using LLMs by providing more accurate uncertainty estimates, which can filter out proportion of erroneous outputs.
Limitations. One limitation of the proposed method that it requires multiple samples from an LLM, which generally increases the generation cost. However, in safety-critical tasks, the potential cost of hallucination should outweigh the cost of sampling multiple answers, so reliable uncertainty quantification via KLE should always be worthwhile. Additionally, we study semantic kernels derived from NI.I-based semantic graphs, but other semantic kernels warrant investigation, such as kernels on embeddings. Moreover, the NL. landscape is highly diverse, and the method should be carefully evaluated for other potential applications of LLMs,, such as code generation. Lastly, our method es- timates uncertainty using predictive entropy, as commonly done in Bayesian deep learning. However, in applications where confidence estimates are important, alternative methods should be considered.
Acknowledgments and Disclosure of Funding
This work was supported by the Research Council of Finland (Flagship programme: Finnish Center for Artificial Intelligence FCAI, and grants 352986, 358246) and EU (H2020 grant 101016775 and Nex(GenerationEU). We also acknowledge the computational resourees provided by the Aalto Science-IT Project from Computer Science IT. The authors wish to acknowledge CSC IT Center for Science, Finland, for computational resources.
provided
References
[1] S. Aaronson. Introduction to quantum information science II lecture notes, 2022.
[2] L. Aichberger, Schweighofer, M. lelanskyi, and S. Hochreiter. How many opinions does your Ilm have? improving uncertainty estimation nlg. ICLR 2024 Workshop on Secure and Trustworthy Large Language Models, 2024.
[3] E. Almazrouei. H. Alobeidli, A. Alshamsi, A. Cappelli, R. Cojocaru, M. Debbah, É. Goffinet, D. Hesslow, Launay. Q Malartic, al. The falcon series open language models. arXiv preprint arXIv:2311.16867. 2023.
[4] F. Bach. Information theory with kernel methods. IEEE Transactions on Information Theory, 69(2): 752-775, 2022.
[5] Bengtsson and K. Zyczkowski. Geometry of quantum states: an introduction to quantum entanglement. Cambridge university press, 2017.
[6] V. Borovitskiy, Azangulov, A. Terenin, P. Mostowsky, M. Deisenroth, and N. Durrande. Matérn Gaussian processes on graphs. In International Conference on Artificial Intelligence and Statistics, pages 2593-2601.
PMLR, 2021.
[7] A. Budanitsky and G. Hirst. Evaluating wordnet-basee measures of lexical semantic relatedness. Computa- tional linguistics, 32(1):13 47, 2006.
[8] C. Burns, H. Yc, D. Klein, and J. Steinhardt. Discovering latent knowledge in language models without supervision, 2022.
[9] Chen and Mueller. Quantifying uncertainty in answers from any language model via intrinsic and extrinsic confidence assessment. arXiv preprint arXiv:2308, /6/75, 2023.
[10] F. R. Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[11] Clusmann, R. Kolbinger, H. Muti, Z. Carrero, J.-N. Eckardt, N. G. Lalch, C. M. L. Löffler, S.-C. Schwarzkopf. M. Unger, G. P. Veldhuizen, et al. The future landscape of large language models in medicine. Communications medicine, 3(1):141, 2023,
[12] R. Cohen, M. Hamri, Geva, and A. Globerson. LM LM: Detecting factual errors cross examination.
arXiv preprint arXiv:2305.13: 13281, 2023.
[13] J. R. Cole, M. J. Zhang, D. Gillick, J. M. Eisenschlos, B. Dhingra, and Fisenstein. Selectively answering ambiguous questions. Conference Empirical Methods in Natural Language Processing, 2023.
[14] D. Crystal. The Cambridge encyclopedia of the English language. Cambridge university press, 2018.
[15] S. Desai and G. Durrett. Calibration of pre-trained transformers. arXiv preprint arXiv:2003.0789. 2020.
10

---

[16] S. Farquhar, J. Kossen. L. Kuhn, and Y. Gal. Detecting hallucinations in large language models using semantic entropy. Nature, 630(8017):225-630 2024.
[17] P. Feldman, J. R. Foulds, and S. Pan. Trapping LLM hallucinations using tagged context prompts. arXiv preprint ar0i 06085, 2023.
[18] K. Filippova, Controlled hallucinations: Learning to generate faithfully from noisy data, arXiv preprint arXiv:2010.05873. 2020.
[19] D. Friedman and A. B. Dieng. The Vendi score: A diversity evaluation metric for machine learning. Transactions on Machine Learning Research, 2023.
[20] Y. Gal and 7. Ghahramani. Dropout as Bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, pages 1050-1059. PMLR, 2016.
[21] D. Ganguli, A. Askell, N. Schiefer, T. L. Liao, K. Lukošiâté, A. Chen, A. Goldie, A. Mirhoseini, C. Olsson,
D. Hernandez, et al. The capacity for moral self-correction in large language models. arXiv preprint arXiv:2302.0 07049,, 2023.
[22] P. He, X. Liu, J. Gao, and W. Chen. Deberta: Decoding-enhanced enhanced bert with disentangled attention. arXiv preprint arXiv:2006.0366. 2020.
[23] D. Hendrycks, N. Carlini, J. Schulman, and J. Steinhardt. Unsolved problems in ML safety, arXiv preprint
arXiv:2109.139) 13916, 2021.
[24] E. Hernandez, Z. Li, and J. Andreas. Measuring and manipulating knowledge representations in language models. arXiv preprint 2304:3044000044 2023.
[25] R. A. Horn and C. R. Johnson. Matrix amalysis. Cambridge university press, 2012.
[26] Z. Ji, N. Lee, R. Frieske, T. Yu, Su, Xu, E. Ishii, Y. J. Bang, A. Madotto, and P. Fung. Survey of ballucination in natural language generation. ACM Computing Surveys, 55(12):1-38, 2023.
[27] A. Q. Jiang. A. Sablayrolles. A. Mensch, C. Bamford, D. S. Chaplot, D. d. Casas, F. Bressand, G. Lengyel,
G. Lample, I.. Saulnier, et al. Mistral 7b. arXiv preprint urXiv:2310.0682 2023.
[28] Z. Jiang. J. Araki, H. Ding, and G. Neubig. How can we know when language models know? on the calibration of language models for question answering. Transactions of the Association for Computational Linguistics, 9:962-977, 2021.
[29] M. Joshi, E. Choi, D. S. Weld, and L. Zettlemoyer. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. arXiv preprint SoxXvv1705.035535 2017.
[30] S. Kadavath, T. Conerly, A. Askell, T. Hemighan, Drain, E. Perez, N. Schicfer, Hatficl- Daddds N. DasSarma, E. -oon-Jo, et al. Language models (mostly) know what they know, arXiv preprint arXiv:2207.0522/ 2022.
[31] K. Kang, E. Wallace, C. Tomlin, A. Kumar, and S. Levine. Unfamiliar finetuning examples control how language models hallucinate. arXiv preprint arXiv:2403.05611 2024.
[32] E. Kasneci, K. SeBler, S. Kücheeann, M. Bannert, D. Dementieva, F. Fischer, U. Gasser, G. Groh, S. Günnemann, E. Hüllermeier, al. Chatgpt for good? on opportunities and challenges of large language models for education. Learning and individual differences, 103: 2023.
[33] J. Kim, S. Kang, D. Hwang. J. Shin, and W. Rhee. VNE: An effective method for improving deep representation by manipulating eigenvalue distribution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3799 3810, 2023.
[34] R. I. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete structures. In Proceedings of the 19th international conference on machine learning, volume 2002, pages 315-322, 2002.
[35] A. Krithara, A. Nentidis, K. Bougiatiotis, and G. Paliouras. BioASQ-QA: A manually curated corpus for biomedical question answering. Scientific Data, 10(I):170, 2023.
[36] I.. Kuhn, Y. Gal, and S. Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. arXiv preprint (rXXi:2302.09666 2023.
[37] A. Kumar and S. Sarawagi. Calibration of encoder decoder models for neural machine translation. arXiv preprint 1 00800, 2019.
[38] T. Kwiatkowski, J. Palomaki. O. Redfield, M. Collins, A. Parikh, C. Alberti, D. Epstein, L Polosukhin. Devlin, K. Lee, et al. Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453-466, 2019.
[39] B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
[40] H. Le, Y. Wang, A. D. Gotmare, S. Savarese, and S. C. H. Hoi. Coderl: Mastering code generation through pretrained models and deep reinforcement learning, Advances in Neural Information Processing Systems, 35:21314-21 2212211188111 2022.
11

---

[41] K. Li, O. Patel. F. Viégas. H. Pfister. and M. Wattenberg. Inference-tine intervention: Eliciting truthful answers from a language model. Advances in Neural Information Processing Systems, 36, 2024.
[42] X. Li, R. Zhao, Y. K. Chia, B. Ding, S. Joty, S. Poria, and L. Bing. Chain-of ofwwooledgee:::: Grounding large language models via dynamic knowledge adapting over heterogeneous sources. In The Twelfth International Conference on Learning Representations. 2023.
[43] S. Lin, J. Hilton, and O. Evans. Teaching models to express their uncertainty in words. arXiv preprint arXiv:2205.14334 2022.
[44] Z. Lin. S. Trivedi, and J. Sun. Generating with confidence: Uncertainty quantification for black-box large language models. arXiv preprint arXiv:2305. 19187, 2023.
[45] J. Liu, Z. Lin, S. Padhy, D. Tran, T. Bedrax Weiss, and B. Lakshminarayanan. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. Advances in neural information processing systems, 33:7498-7512, 2020.
[46] S. Liu, L. Xing, and J. Zou. In-context vectors: Making in context learning more effective and controllable through latent space steering. arXiv preprint arXiv:2311.06600 2023.
[47] X. I. Liu, M. Khalifa, and I.. Wang. Litcab: Lightweight calibration of language models on outputs of varied lengths, arXiv preprint arXiv:2310. 19208, 2023.
[48] M. MacDiarmid, T. Maxwell, N. Schiefer. J. Mu, J. Kaplan, D. Duvenaud, S. Bowman, A. Tamkin, E. Perez, M. Sharma, C. Denison, and E. Hubinger. Simple probes can catch sleeper agents, 2024. URL attps://wwet anthropic cwm/news patchs-catch-- seattch-sleeper-- sleeper- agents..
[49] D. J. MacKay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
[50] A. Malinin and M. Gales. Uncertainty estimation autoregressive structured prediction. arXiv preprint axXiv:200..07650 2020.
[51] P. Manakul, A. Liusie, and M. J. Gales. SelfCheckGPT: Zero-resource black-box hallucination detection for generative large language models. In Conference on Empirical Methods in Natural Language Processing, 2023.
[52] J. Maynez, S. Narayan, B. Bohnet, and R. McDonald, On faithfulness and factuality in abstractive summarization. arXiv preprint arXiv:2005.0066 2020.
[53] S. Mielke, A. Szlam, Y.-I. Boureau, and E. Dinan. Linguistic calibration through metacognition: aligning dialogue agent responses with expected correctness. arXiv preprint arXiv:2012. 1498:3, 11, 2020.
[54] S. J. Mielke, A. Szlam, Dinan, and Y.-L. Boureau. Reducing conversational agents' overconfidence through linguistic calibration. Transactions of the Association for Computational Linguistics, 10:857-872. 2022.
[55] J. Mukhoti, A. Kirsch, J. van Amersfoort, P. H. Torr, and Y. Gal. Deep deterministic uncertainty: A new simple baseline. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 24384-24394, 2023.
[56] M. S. A. Nadeem, J.-D. Zucker, and B. Hanczar. Accuracy-rejection curves (ARCs) for comparing classification methods with reject option. In Machine Learning in Systems Biology. pages 65 81. PMLR, 2009.
[57] A. V. Nikitin, S. John, A. Solin, and S. Kaski. Non-separable spatio-temporal graph kernels via SPDEs. In International Conference on Artificial Intelligence and Statistics, pages 106440-10660, PMLR, 2022.
[58] OpenAI. GPT-4 technical report. 2023.
[59] Y. Ovadia, E. Fertig, J. Ren, Nado, D. Sculley, Nowozin, J. Dillon, Lakshminarayanan, and
J. Snock. Can you trust your model's uncertainty? evaluating predictive uncertainty under datasct shift. Advances in neural information processing systems, 32, 2019.
[60] A. Patel, S. Bhattamishra, and N. Goyal. Are NLP models really able to solve simple math word problems? In Proceedings of the 202/ Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pages 2080-2094, Online, June 2021. Association for Computational Linguisties. doi: 10.18653/v1/0021 haacl-main
URL https://
aclanthology- . org/2021 wwtg///1..aaclllaaeeeeeee manl..mmnin.... 168.
[61] V. Quach, A. Fisch, T. Schuster, A. Yala, J. H. Sohn, T. S. Jaakkola, and R. Barzilay. Conformal language modeling, arXiv preprint arXiv:2306. 10193, 2023.
[62] P. Rajpurkar, R. Jia, and P. Liang. Know what you don't 't know: Unanswerable questions for SQuAD. arXiv preprint arXiv: 806.006000 03822, 2018.
[63] J. Ren, Y. Zhao, T. Vu, P. J. Liu, and B. Lakshminarayanan. Self-evaluatiin improves selective generation in large language models. arXiv preprint arXiv:2312.09300 2023.
12

---

[64] O. Roy and M. Vettelli. The effective rank: A measure of effective dimensionality. In 2007 15th European signal processing conference, pages 606-610. IEEE, 2007.
[65] C. E. Shannon. Prediction and entropy of printed english. Bell system technical journal, 30(1):50-64, 1951.
[66] G. Team, R. Anil, S. Borgeaud, Wu, J.-., Alayrac, J. Yu. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, et al. Gemini: a family of highly capable multimodal models. 2023.
[67] K. Tian, E. Mitchell, H. Yao, C. D. Manning, and C. Finn. Fine-tuning language models for factuality, arXiv, 2023.
[68] K. Tian, E. Mitchell, A. Zhou, A. Sharma, R. Rafailov, H. Yao, C. Finn, and C. D. Manning. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. arXiv preprint 2305. 14975, 2023.
[69] H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaci, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint ar arXiv:2307.00288. 2023.
[70] N. Varshney, W. Yao, H. Zhang, J. Chen, and D. Yu. A stitch in time saves nine: Detecting and mitigating hallucinations of Iims by validating low-confidence generation. arXiv preprint arXiv:2307.0398. 2023.
[71] Von Luxburg. tutorial on spectral clustering. Statistics and computing, 17:395-416, 2007.
[72] J. Von Neumann. Mathematical foundations of quamtum mechanics: New edition, volume 53. Princeton university press, 2018
[73] Y. Xiao and W. Y. Wang- Quantifying uncertainties in natural language processing tasks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7322-7329 2019.
[74] Y. Xiao W. Wang. On hallucination and predictive uncertainty in conditional language generation. arXiv preprint arXiv:2103.1502: 2021.
[75] A. X. Yang, M. Robeyns, X. Wang, and L. Aitchison. Bayesian low-rank adaptation for large language models. arXiv preprint arXiv:2308. 13111, 2023.
[76] C. Zhang, F. Liu, M. Basaldella, and N. Collier. Luq: Long-text uncertainty quantification for llms. arXiv preprint arXiv:2403.20277 2024.
[77] A. Zou, L. Phan, S. Chen, J. Campbell, P. Guo, R. Ren, A. Pan, X. Yin, M. Mazcika, A.-K. Dom- browski, et al. Representation engineering: A top-down approach to ai transparency. arXiv preprint axXiv:3110014055, 2023.
13

---

Supplementary Material:
Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities
A Background
A.1 Linear Algebra
Definition A.1. For set X + 0. symmetric function K X x X + R. is called positive-
semidefinite kernel if for all n > 0, x; E N,, E
ΣΣ (Z,,K) =1
(A.1)
For a finite set X, a positive semidefinite kernel is a positive semidefinite matrix of the size |
Lemma A.2. For a block diagonal matrix
A 11
0
A22
0
0
A33
0
Ann
eigenvalues are all eigenvalues of the blocks Au combined, or equivalently det (A X1)
Il (At Al) =0
(=1
Proof. Notice, that block diagonal matrix can be decomposed into the following product:
A
0
I11
0
Iu
0
122
0
0
A22
0
0
In2
A
Tnn
Inn
Ann
where iú are the identity matrices of the same size as Asi-
By using the product rule for determinants, we obtain det (A - Al) = 0 + πI (et(AA - Al)
Lemma A.3 (Horn and Johnson [25]). An all-ones matrix J of size has eigenvalues (n, O O,...-
A.2 Discrete Mathematics
Throughout the text, we often refer to the notion equivalence relation. We remind readers of the definition of equivalence relation here. Definition A.4. Equivalence relation is binary relation E(:,)) on a set X, that is for any x. y, X, this relation is
1. reflexive E(x,2).
2. symmetric E(x, v) = E(y,x),
3. transitive if Elx, y) and Ely, 2) then E(x, 2).

---

B Theoretical Results and Proofs
In this section, we prove Thm. 3.5, for convenience we separate into two theorems for KLE and KLE-c.
Theorem B.1 (KLE is generalization of SE). For any semantic clustering, there exists a semantic kernel over texts K (s, s') such that the VNE of this kernel is equal to semantic entropy (computed as Eq. (5)).
Proof. Let fix arbitrary semantic clustering over M clusters C [CI,...... Cm with the size of each cluster my Now, we will construct a kernel K for an input such that the von Neumann entropy with this kernel will be equal to the semantic entropy of the texts VNE(K) SE(x, C). Let us consider block-diagonal kernel K. We will denote blocks K as K Kj...., KM:
Ki
0
0
K2
K
0
0
Kg
0
(B.1)
KM/
where M corresponds to the number of semantic clusters. The size of each block K₁ is m, m, Note that because K is block-diagonal. it follows that VNE(K) E VNE(K,). Consequently,
1. VNE(K;) -p(C,/=) log ((;(())
2. the sum of eigenvalues of K; equal to p(C])
3. K is positive semidefinite and unit trace,
then VNE(K) SE(skr).
Let define each block as K; p(C, (x)) Jm, where Jm; is all-ones matrix of size my mi- m.
Next, we prove that the desired properties from the list above hold. Indeed, the eigenvalues of K; are p( (C(r))) with multiplicity one and with multiplicity m, 1. So, VNE(K,) -p(C. (x) log (C(la (recall that for calculating VN entropy, we assume 0 log 0 0), and Properties and are fulfilled. K also symmetric and has non-negative eigenvalues. Thus, Property 3 fulfilled as well.
Because K satisfies all properties, we have proven that VNE(K x)) = SE(s(z).
Theorem B.2 (KLE-c more general than SE). For any semantic clustering, there exists kernel over semantic clusters K,(c, e') such that the VNE of this kernel is equal to semantic entropy (computed as in Eq. (5)).
Proof. Analogously to Thm. B.1 but with the blocks of size one.
The theorems not only show that KLE generalizes SE but also provide an explicit form for a semantic kernel that can be used with KLE recover SE.
C Kernel Hyperparameters
Following the discussion about kernel hyperparameters selection from Sec. 3.2, we visualize entropy convergence plots for Heat kernels Fig. and visualize heat and Matémn kernels on 2-d grid in Fig. C.4. Next, we expand on the question of parameter sensitivity, in Fig. C.3, and whether it is necessary to use validation set for selecting kernel hyperparameters. We observe that both with reasonable default choices (l = 0.3, a 0.5, v 1, and к = 1) and by selecting hyperparameters on a separate set of answers, we outperform the existing methods. When choosing hyperparameters, also have included boolean flag whether the graph Laplacian should be normalized, generally

---

V 20
30
V 40
V 50
1.5
K
2.0
2.5
3.0
3.5
4.0
5.0
01
2000
Number of Edges
Figure C.I: Matérn Entropy Convergence Plots.
speaking, both the normalized and the standard graph Laplacians can be used with heat and Matérn kernels
L, (=+))""L(Dt))))
(C.1)
where D+ is the Moore-Penrose inverse of the degree matrix D. We observe similar results when analyzing other semantic kemels..
Prompts. We prompt the models to generate full sentences answers with the following prompt: Answer the following question in a single brief but complete sentence..
Also, we have used the following prompt check the accuracy of the responses:
We are assessing {question] An The expected answer is: answer {predicted_ (
quality of answers (oorrect_answerk In The proposed
following question:
Within the context the question, does
the proposed answer mean the same as the expected answer? An Respond only with yes or no. \n Response:
Here we mark placeholders with the orange color. Or, if several correct answers were provided, we have used the following prompt:

---

Quession
who resporeitle for introducing the principle of uniormilarsaiiem?
Weight matrix the semantic graph
Answer
introdutin principle mitartanis geology.
fuuton te coedlled introkusing prinople unformmbeteeam peotogy
Sczebenn gesiogat ilutonn credied Introdudig the priccppe of unformittttrae in 1785.
Jenree luston, oetorrr Seotlon grolog and
lamse Huttonn and tee with immo ssng the prrople geckogi dal and procanoss that opecite today, hie 1788 hook "The Theory Favth
aryscians clar, credilee iraoducing pricple
proceesse cbownved in possent are the came
procaesss boow staped Forth fhrougoot maneey.
Jumos hulton is prodiked with intodloing the prireptl peotogy.
Samees Hultr, Bootss gookog oi and phopicion antormmaannaeee
directions
Jumre kutten.
James Hu Holton Seetish geologet the 10th oentury
Theps tincple lombrrii introduced
Entallment in one and neutral the other
5 Ja nos Hutton anod with incoduuing the pinople of undorrstanan which somse gecing da have shaped the Eart thoughouu hiltor.
James tutton, Ithhoantury Sortien phyaadan pedioghtt unformiartaniin goologg.
are neutral or entillmmnt and contradiction
Figure C.2: Example from NQ.
KLE(NNea)
Nasel )
KLE(haal Numer)
PtTmel
KLE
PtTmel
DSE
PE
FRi
SE
DSE
PP
FR
KLE(Knul
0:43
0.53
U.57
0.73
0:93
0.88
KLB(K
0:40
0.77
0.77
0.78
0.90
0.88
0.8
0.8
KLB(Kkor))
0.77
0.90
0.88
0.50
0.6
0.6
13
0.23
P(True]
00.33
0.4
P.Tree]
0.4
0.2
0.2
0.15
0.33
0.33
(a) AUROC: Default hyperparameters
(b) AUROC: Validation set hyperparameters
KLE(Keull
KLE:Naaad
KLE/KNull
KLE Kamar!
P(Tre)
P[Tne]]
SE
DSS
S6
DSE
PP
KLE (.....)
0.42
0.78
0.97
0.65
0:92
0:90
KLE (K....))
0.50
0.75
0.90
0.70
0.88
0:90
KLE
0.58
0.62
0.68
77
0:92
0.88
0.8
KLE Karve)
0.00
0.70
0.93
75
0.92
0.90
0.8
SE
1:222
0.38
0.85
0.58
0.87
0.82
0.6
SE-
0:25
0.30
0.85
0.58
0.87
0.82
0.6
DSE
0.12
0.15
0.53
0.73
0.77
DSB
0.30
D:07
0.15
0.53
0.73
0.77
P[Time)
0.35
0:23
0.42
0.47
0.57
0.70
00.4
P[Tue]]
0.31
0:25
0.42
0.47
0.57
0.70
0.4
PE
0.08
0.08
0.13
0.27
0.43
0.68
0.2
PE
0.12
0.08
0.13
0.27
0.43
0.68
0.2
ER
0.
0.12
0.18
0.23
0.30
0.32
ER-
0.10
0.10
0.18
0.23
0.30
0.32
(c) AUARC: Default hyperparameters
(d) AUARC: Validation hyperparameters
Figure C.3: Summary of 60 experimental scenarios. Comparing hyperparameters selection strategies.
Our methods are labeled KTF((-).
We are assessing the quality of answers to the following question: {question) \n The following are expected answers to this question: ccorrect_ansvers] An The proposed ansver is: (predicted_annseel An Within

---

the context of the question, does the proposed answer mean the same as any of the expected answers? An Respond only with yes no. An Response:
Example. We visualize an example from the
Heat Kemel (t 1) Matérn Kerel (v = 5/2, A
NQ dataset in Fig. C.2; we have used Llama-2 70B Chat for this example. In order to analyze cases where SE and KLE are inconsistent, we ranked all the answers separately by KLE and SE and found those cases where the difference between indices the list ranked by KLE and ranked by SE is high. In Fig. C.2. model pro- vides the correct answer. However, SE estimates the uncertainty to be high because it can detect only two answers as equal and thus considers the majority of the answers semantically distinct. Instead, our method considers more fine-grat -rriggriiedd relations between the answers and provides bet-
Kimna 1g)
Figure C.4: Heat and Matérn kernels visualized on 2-d grid.
ter uncertainty estimates (i.e., orange and red cells in the weight matrix). It is an illustrative example of the cases analyzed. It indicates that the longer and more nuanced the answers are, the more KLE would outperform SE.
D Additional Experimental Details
In this section, we provide additional experimental results.
Hardware and Resources. We Llama 2 70B models and the rest of the models on a single NVIDIA A100 80GB. The generation process took from seven hours (depending additionally took roughly four hours per scenario which can be further optimized by reducing the number of hyperparameters. The project spent more resources due to other experiments. Our experimental pipeline first generates the answers for all the datasets and then computes various uncertainty measures. We did not recompute generations, but in each experimental we only evaluated uncertainty measures.
NVIDIA A100 80GB GPUs,
model) for each experimental scenario, and the evaluation
Licenses. We release code under clear BSD-3-Clausc-CA The datasets used in this paper released under CC BY 2.5 (BioASQ: [35]), Apache 2.0 (TriviaQA; [29]), CC BY-SA 4.0 (SQuAD; [62]), MIT (SVAMP: [60]), and CC BY-SA 3.0 (NQ: [38]).
D.1 Models and datasets
In Fig. D.I, we show samples from each dataset we used in the experimental evaluation of our method.
Trivia
SQUAD
Questoo:
Comrec Answer:
Question:
Correct Answer
Question:
Comrect Anowor
What city Chile's second largest, suffered an 8.8 earthquani
Conceptiónn
Who played garllla in the cadbury adver??
Garan Michael
oer lnnard méleos document about opucelion
1945
20107
BioASQ
Questlon:
Correst Answor.
Contect
Questoon:
Corroct
What is the purpose of Micropinocyyooo incylooss?
process, which invelves the engultment of extra colluaar content vesicles known as macmppnnsomes.
Mecropinocytoiis wndocylic
peaches
manty
Steven and than all
Figure D.I: Samples from datasets we use: Trivia QA, NQ. SQUAD, BioASQ, and SVAMP.
Additionally, we demonstrate the accuracy of the models used in the experiments on each dataset in Fig, D.2. As can be seen, evaluate our method on a diverse set of models with varying level of

---

Mone capud
Ideen Pa
Pa
Lamoa Chhel bod
Mome
Rabon
Limea Croe
Figure D.2: Accuracy of the models
accuracy across the tasks at hand. This is especially important for UQ, because UQ methods should perform well for all the models regardless of their downstream effectiveness.
Real-world applications often involve deploying models with varying degrees of performance, and robust UQ method should provide reliable uncertainty estimates for all of them. By demonstrating the efficacy of our method across wide variety models, we validate its applicability in diverse scenarios. This highlights that our approach be confidently used in practical settings where model performance can fluctuate.
D.2 Instruction-tuned and non-instruction-tuned models
Furthermore, we investigate the performance of UQ methods by splitting the set of experimental scenarios into instruction-tuned and non-instruction-ture models. We visualize the splits in Fig. D.5. Interestingly, our approach significantly outperforms the existing methods when evaluated with instruction-tuned models, and only marginally outperforms when evaluated non-instruction-tuned models. We can hypothesize that con-instruction- tuned models are better calibrated, and thus methods based token-likelihene likelihoods perform well whereas instruction-tuning worsens calibration. This hypothesis is also supported by comparison of SE and DSE (DSE significantly outperforms SE instruction-tuned split, when AUROC is measured).
D.3 Detailed results of UQ
We provide detailed comparison of our method with previous uncertainty quantification measures. In Fig. D.3 and Fig. D.4, we show the results for a wide range of models across five datasets for non-instruction-tunee and instruction-tuned models, respectively. We want to note that ER has failed for Llama 2 13B (non-instruction- tuned version) for all datasets except BioASQ because training datasets for ER contained samples of only one class, We have assigned zero scores to the failed cases.
D.4 NLI models accuracy
In Supplementary Note 2, Farquhar et al. [16] analyze the accuracy of various NLI models. They report that DeBERTa shows average agreement of 0.8 with human raters, compared agreement of 0.87 between human annotators. We hypothesize that using more advanced but computationally expensive NLI model, such as GPT-4, could improve the semantic kernel and, consequently, enhance uncertainty estimation using KLE.
E
Additional Notes
E.1
Lexical, semantic, and syntactic variability
resort to the 6-level model of structure for text analysis proposed in [14] to extensively describe aspects of language beyond semantics. This model distinguishes four basic notions for text analysis: medium of transmission, grammar, semantics, and pragmatics. Medium of transmission is irrelevant to the study of language model outputs (however, it becomes relevant for multimodal

---

Semantic entropy Discrete Semantic Entropy
P(True) Naive Entrapy
Embedding Regression
KLE(K
AUROC
ALARO
AUFOC
ALLAC Liama 138
AUROC
AUAAC
AUROC
ALARC
ALFOC
AJARC Falcon 408
AUROC
AUVRC
Liama 2 78
Liama 2 708
Falcon 78
Mistral 78
Figure D.3: Full results of hon-instruction-tmme tuned models
Table 2: Examples of semantic, syntactic, and lexical variability of a sentence "Paris is the capital of France."
Semantic Variability
Syntactic Variability
Lexical Variability
Rome capital of France the capital Italy.
France's capital is situated in Paris.
Paris capital France.
The capital France Paris.
capital city
foundation models that can, for instance, answer a request either with text or an image); grammar further divided into the syntax and morphology of the text and semantics into semanties and discourse. Another dimension is pragmatics, or how the text is used. In this work, we focus only on the semanties of the text. However, the method be extended other aspects of text analysis. For instance, one can design syntactic or pragmatic kernels. We leave the study of other kernel modalities future works.

---

Semantic entropy
P(True] Entropy
Embedding Regression
(K
Semantic Entropy
TriviQ
SQUAD
NO Open
SWAMP
BicASQ
AUFOC Liama Chat 7B
AJARD
AUROC Liama 2 Chat 13B
AJARO
AUROC Lama Chat
AUKFC
AUROC Falcon
AUARC Instruct
AUROC Falcon 40B Instruct
AUARC
AUROC Mistral 7B Instruct
AUARI
Figure D.4: Full results instruction tuned models

---

KLE(KGmLl
KLE )
KLEI
KLE (aaan)
P(The)
PtThed
SE
USE
PB
ER
SE
DSE
PE
ER
0:210
0.93
0.50
0.77
0:93
0.90
KLE (ECrra))
0.60
0.63
0.50
0.87
0.87
0.8
0.8
Kine)
0.80
0.93
0.50
0.54
0:97
0.93
KLE KLE Kinse
0.40
0.50
0.63
0.77
0.83
0.83
1:077
0.07
0.07
0.43
0.80
0.70
0.6
0.40
0.50
0.53
0.70
0.83
0:90
0.6
0.101
0.11
0.93
0.50
0.87
0.80
0.37
0.17
0.70
0.87
0:90
P[True
0.57
0.63
P(Tru))
0.4
0.03
0.50
0.2
0.13
0.83
0.2
0.07
0.30
0.20
0.50
(a) AUROC instruction-tuncl models
(b) AUROC: non-instrunction tuned models
KLE:Keal
KLEIKwall
Pt[mme)
D5E
DSE
1.0
KLE [
0.23
0.93
0.03
0:63
0:33
0.50
KLE (SS
00.37
0.57
0.87
0.77
0183
0:90
0.8
0.77
0.90
1.00
0.77
0:97
0.57
0..8
KL Kumel
0.43
0.50
0.57
0.75
0.87
0.83
0.6
88-
0.43
0.30
0,83
0.67
0.87
0:90
0.6
D3E
DXIT
0.00
0.13
0:47
0.80
0.67
D88
13
0.13
0.17
0.60
67
0.5
-04
P(True)
0.37
0.23
0.50
0.53
0.57
0.50
P[True]
0.23
0.27
0.33
0.40
0.47
0.80
0.4
FE
D.07
0.03
0.13
0:20
0:33
0.53
0.2
PE
0.
0:13
0.13
0.33
0.58
0.83
0.2
0.0
ER
0.10
D:17
0.10
0.13
(.20
0.17
(c) AUARC: instruction-tuned models
(d) AUARC: non-instrunction tuned models
Figure D.5: Summary of 60 experimental scenarios. Comparing the results on instruction-tur tunedd and non-instruction-turee models. Our methods are labeled KLE(-).

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We list our contributions at the end of Sec. 1, and link each of the contributions either the theorems the sections in the paper. The theoretical results are described in Thm. 3.5, KLE is described in Sec. 3 and the experimental results are listed in Sec. 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:[Yes
Justification:
We have a separate paragraph related to the limitations of our approach in
Sec. 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?

---

Answer:[Yee
Justification: The paper discusses the assumptions for the theoretical results. We prove the theoretical results the Appendix (Thm. B.1 and Thm. B.2) and provides proof sketch in the main text. Lemmas used in our proofs are also added to the appendix, and either proved or properly referenced.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper fully describes our experimental pipeline, and supplementary materials include source code for reproducing the results. The source code will published online under permissive license and the datasets are already available online.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibilitty In the case of closed-source models, it may be that access to the model is limited in

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, we attach the source code and instructions for reproducing the results in the supplementary materials. We will release the source code and instructions online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. "nips.cc/ppppp ptc/public/guu wwtp//bccc/gguuee//ee/////////ee geuudds/Cooeeiiee
ssionoliccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all the necessary details in Sec. 5 and additional details in App. D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We assess statistical significance on two levels. First, we run a large number of experimental scenarios (60 model-dataset pairs), and second, for each experimental scenario, we also obtain confidence intervals with 1000 resamples. We would like to additionally comment that standard errors each scenario are more representative the LLM and the dataset rather than the method. Therefore, our main criterion for evaluating the methods is the proportion of experimental cases where our method outperforms others (assessed with binomial statistical significance test). We discuss it in more detail in Sec. 5.

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have discussed it in App. and Sec. 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttpas:///uuurie /nwurips..../// cc
Answer: [Yes]
Justification: Our research conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have discussed broader impact in Sec. 6 and Sec. 1.

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We discuss the licenses in App. D.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We document our source code the README.md file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.


Reviews:
[{"review_id": "n3oXz9veau", "reviewer": "Reviewer_S5q9", "summary": "This paper is highly motivated by and heavily draws from Kuhn et al. (ICLR, 2023) “Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation.” In Kuhn’s original paper they propose an unsupervised way to calculate the semantic uncertainty of LLMs by (1) generating a set of outputs from an LLM, (2) clustering these outputs by semantic equivalence via an NLI model, and (3) plugging in these clusters to an equation for “semantic entropy.” \n\nThis paper proposes an extension of the strict clusters of Kuhn et al.~by creating a “semantic graph” and calculate the “graph kernel” for the uncertainty metric. Thus, the authors attempt to measure the semantic entropy *between* clusters rather than just *within* clusters (the latter which is the approach of the previous work, Kuhn et al. (2023)). \n\nThe authors provide a lot of math and theory trying to justify that their generalization from Kuhn et al. is meaningful. However, the empirical experiments show modest to no performance gains from their generalization on real-world QA datasets and LLMs.", "questions": "1. In the abstract, you motivate this work by saying “by detecting factually incorrect model responses, commonly called hallucinations.” Yet, you never actually show that you detect hallucinations (which require world knowledge that is external and more complex than the “semantic uncertainty” you’re actually targeting). How do you justify this disconnect? \n\n2. On line 25 you cite two works that you use to justify “As LLM predictions tend to be well-calibrated.” However there is an *enormous* body of literature that shows the opposite. I would recommend hedging on this statement or providing citations of the opposite (non-calibration) findings.  \n\n3. Figure 1 lacks some details and motivation. In this example, I would not expect the named entity outputs, (e.g., “Laplace” or “Kolmogorov and Laplace”) to have any other lexical variants that have similar semantic meaning because these are named entities. In this figure, what does the little boxes next to “Semantic Kernels” represent? I would recommend explaining this more (e.g., I think you’re implying that blue means more similarity between particular clusters?) \n\n4. In Figure 3’s caption, please explain why only “values larger than or equal to 0.62” correspond to a p-value less than 0.05. \n\n5. I would recommend explaining how you are calculating AUPRC and why it is important. I know Kuhn et al. also use this metric but you do not make clear what this metric is in your standalone work. From re-reading Kuhn et al., I took away that they calculated an “entropy score” to predict whether a model’s answer to a question is correct. They vary the threshold of the entropy score for correctness prediction to get AUROC.", "limitations": "Addressed.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors have crafted a very extensive empirical set-up with 12 different LLMs on five datasets. They also get 10 LLM outputs per input and also obtain confidence intervals over 1000 bootstrap resamples (line 286-287). They combine this with five different baseline models for comparison to their proposed methods. I commend the authors on this extensive and painstaking experimental set-up. \n\n2. The authors seem very well-versed in the previous literature and identify a clear gap in Kuhn et al.: that the “hard clustering” of Kuhn et al. misses what could be a softer clustering of semantic similar (which the authors tackle by constructing a semantic graph with weights between clusters).", "weaknesses": "1. **The claims are not backed by strong enough evidence.**  \n\nOn line 59, the authors claim their approach achieves SoTA results. However, the empirical results (Table 1) are little to modest gains over baselines. Additionally, the bolding in Table 1 is misleading. Results should only be bolded if the method’s confidence interval is non-overlapping the confidence intervals of other methods (which they are not). For example, in Table 1 for AUROC on BioASQ, $0.88 \\pm 0.03$ for KLE (K_FULL) is overlapping with P(True) at $0.86 \\pm 0.03$. Likewise for SVAMP AUROC with $0.77 \\pm 0.02$ for KLE (K Heat) and ER at $0.75 \\pm 0.02$. This also makes me skeptical of how the authors are calculating the “win rates” for the other figures as well. \n\n2. Additionally the authors do not investigate the **error/accuracy of intermediate models** that the experimental set-up relies upon.\n\nA key part of the authors pipeline is using DeBERTa-Large-MNLI to predict whether LLM outputs entail one another and create their semantic graph (line 262). However, DeBERTa-Large-MNLI is also an imperfect model. What was the accuracy of this model on the domains/datasets in the authors’ empirical pipeline? Are there ways to propagate uncertainty from this intermediate NLI model downstream to the final uncertainty calculations of other LLM’s outputs? \n\n3. Additionally, see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer S5q9,\n\nThank you for a thoughtful and constructive review. We are pleased to hear that you found the experimental setting and the research problem in our work interesting. We hope to address your concerns in our reply below.\n \n**Weaknesses**\n> […] the empirical results (Table 1) are little to modest gains\n\nIn Tab. 1, our method is the best or among the best for all datasets and both models, while the second-best method is different for different setups (ER, P(True), or SE). **Statistical significance is achieved primarily by repeating the experiment with many different models and datasets.** Tab. 1 shows results for only the two largest models out of 12. **See Fig. 3 for the summary of all experiments.** Statistical significance was calculated by the sign test [1] across the 60 experiments, and confirmed in Fig. 3 that the differences between our method and any other method are always statistically significant (LL: 285-290). To further explicitly demonstrate the size of the improvement, we show the relative gains in AUROC and AUARC in Tab. 1 in the rebuttal PDF.\n> the bolding in Table 1 is misleading\n\nIt is common to bold the results when the average is the best, e.g. https://arxiv.org/pdf/2106.10934 or https://arxiv.org/pdf/2011.13456, but we are happy to add a comment to avoid confusion.\n>[...] how the authors are calculating the “win rates” [...]\n\nWin-rates represent the fraction of cases where one method outperforms another, based on a better mean value of the corresponding metric (LL: 285-290).\n> authors do not investigate the error/accuracy of intermediate models [...]\n\n- Models for generating answers: We report their accuracy in Appendix D (Fig. D2).\n- NLI models: The performance of NLI models in the same setting is analyzed by [2]. We will add a reference and summarize their analysis.\n- Models for checking the answers: We compared the performance of Llama-3-8B and GPT-4 for TriviaQA by Llama-2-70B-chat and observed 95% agreement. We additionally measured the performance compared to humans and observed 90% agreement in 100 cases.\n\n> DeBERTa-Large-MNLI analysis and uncertainty propagation\n\nThe uncertainty from the NLI model can be propagated to the final KLE model. In our experiments, we have used kernels where NLI confidences directly form weights (shown in Fig. 4 under $K^{DB}_{*}$). Moreover, KLE can combine multiple NLI models via kernel composition. We leave this and other alternatives to constructing better semantic kernels for future work (LL: 354-356). The accuracy of NLI in this setting is assessed by [2], which we will comment on.\n\n**Questions**\n\n> you motivate this work by saying “by detecting factually incorrect model responses, commonly called hallucinations.” Yet, you never actually show that you detect hallucinations [...]\n\nWe use predicted uncertainty to detect factually incorrect responses in our experiments, following the evaluation method used in [3] and other studies. AUROC and AUARC measure the effectiveness of uncertainty in detecting hallucinations (see LL: 273-280 and [2]).\n> you cite two works that you use to justify “As LLM predictions tend to be well-calibrated.” [...] I would recommend hedging on this statement or providing citations of the opposite\n\nThanks! We will discuss these papers. We will further clarify the differences in observations regarding calibration of LLMs (e.g., base vs. instruction-tuned models).\nImportantly, note that KLE does not rely on calibration and performs well when an LLM is not well-calibrated (see Fig. D5).\n>Fig. 1 […] I would not expect the named entity outputs [...] to have any other lexical variants [...] what does the little boxes next to “Semantic Kernels” represent? [...]\n\nThank you for pointing this out! The 3x3 matrices represent kernels over clusters, where colors show kernel values. Non-diagonal elements indicate similarities, and diagonal elements represent $p(C_i | x)$, similar to theoretical proofs. We'll add a more detailed explanation.\nThe answer \"Laplace\" can appear in different forms, like \"Pierre-Simon Laplace\" or “Laplace, a French scholar.” Answers in each cluster may or may not vary lexically.\nFig. 1 shows that even with identical distributions over semantic clusters, the kernels differ. The KLE method offers better uncertainty quantification than SE (right side).\n>In Fig. 3 [...] why only “values larger than or equal to 0.62” correspond to a p-value less than 0.05.\n\nA sign test shows that method A outperforms method B if the value is ≥ 0.62, and method B outperforms method A if the value is ≤ 0.38, according to the sign test. Values between 0.38 and 0.62 are not statistically significant. We will clarify this in the next revision.\n>explain how you are calculating AUPRC and why it is important. […] they calculated an “entropy score” to predict whether a model’s answer to a question is correct\n\nSimilar to [2, 3], we use the entropy score to predict the correctness of the generated responses. The AUROC and AUARC measure the ability of uncertainty to detect hallucinations (LL: 273-280).\n\n**Concluding remarks**\n\nWe appreciate your comments on our empirical results. We hope our answers have fully addressed your concerns.\n\nWe would like to emphasize that our method is both empirically effective and theoretically sound. It holds methodological value and opens the potential for developing semantic kernels for other LLM outputs, such as structured data or mathematical proofs, thereby broadening the scope of uncertainty quantification.\n\nWe would be grateful if you could let us know whether our explanations have addressed your concerns. Please let us know if you have any other questions or concerns.\n\n**References**  \n[1] Dixon, et al. (1946). The Statistical Sign Test.  \n[2] Farquhar, et al. (2024). Detecting Hallucinations in Large Language Models Using Semantic Entropy.  \n[3] Kuhn, et al. (2023). Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation.", "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": "77cNQ2ogsR", "reviewer": "Reviewer_Raee", "summary": "In this work, the authors propose Kernel Language Entropy, which shares a similar concept to semantic uncertainty but additionally considers semantic similarity. Based on this proposed theory, they design graph kernels and weight functions to estimate LLM uncertainty. Furthermore, they demonstrate that their method generalizes semantic entropy. The empirical results confirm the effectiveness of the proposed method across various tasks and LLMs.", "questions": "1. Which sample do you choose as the final answer among multiple samples, the answer in the biggest cluster or just a random one? I did not find this detail (perhaps I missed it), but it is important.\n\n2. Since the answer correctness is determined by an 8b model, I am curious about how reliable the predicted label is. From my previous experience, even GPT-3.5 is not capable of reliably estimating the correctness of model responses, especially when the responses are phrases. Tian et al. [1] also noted a similar issue, as seen in their Appendix C.\n\n[1]. Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback.\n\n3. Can this method be applied to long-form responses? Considering that long-form responses typically consist of multiple claims.\n\n4. Missing the following related work:\n\nLanguage Models (Mostly) Know What They Know\n\nLitCab: Lightweight Language Model Calibration over Short- and Long-form Responses", "limitations": "The authors acknowledge the issue of computational cost. Investigating ways to elicit confidence from the LLM itself could be a possible direction for addressing this.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality: This paper extends semantic entropy to Kernel Language Entropy, which additionally takes into account the semantic similarity between clusters. The idea is well-motivated.\n\nQuality: This paper provides detailed theoretical analysis and designs several variants. The experimental results demonstrate the effectiveness of these designs. The experiments are extensive.\n\nClarity: This paper is well-structured.\n\nSignificance: This paper focuses on estimating LLM uncertainty, which is significant for LLM applications, as they often make mistakes in their responses. The techniques proposed in this work could be beneficial in addressing this issue.", "weaknesses": "1. KLE requires iterative sampling from the LLM, which is computationally costly. This leads to delayed responses and limits its applicability.\n\n2. It seems that this method can only estimate the confidence regarding whether the LM will correctly answer the query, but it cannot predict the confidence for a given answer. For example, in scenarios like ranking candidate answers, we can use P(True) or PE to estimate answer confidence, which KLE cannot do.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer Raee,  \n\nThank you for your positive evaluation of our work and for highlighting its originality, quality, clarity, and significance. We hope to address your concerns and questions in our response below.\n\n\n**Weaknesses**  \n>KLE requires iterative sampling from the LLM, which is computationally costly. This leads to delayed responses and limits its applicability.\n \n\nOur method, like other most effective methods such as semantic entropy (SE) and discrete semantic entropy (DSE), also requires sampling multiple answers. One way to overcome this is by generating responses in parallel, which helps to avoid the delay but uses more resources. In Fig. 1 in the rebuttal PDF, we include an ablation study on the number of samples for NQ and BioASQ. We briefly discuss this limitation in LL: 351-352.\n\n>It seems that this method can only estimate the confidence regarding whether the LM will correctly answer the query, but it cannot predict the confidence for a given answer. For example, in scenarios like ranking candidate answers, we can use P(True) or PE to estimate answer confidence, which KLE cannot do.\n\nYes, that is correct! Methods like SE and KLE estimate the predictive semantic entropy of a model, which is different from estimating the confidence. Estimating uncertainty as predictive entropy is also an important problem for many applications (e.g., classification with rejection), and was used extensively in Bayesian deep learning. We will discuss these considerations in the limitations section.\n\n>Which sample do you choose as the final answer among multiple samples, the answer in the biggest cluster or just a random one? I did not find this detail (perhaps I missed it), but it is important.\n\nFollowing prior literature [1], we select a low temperature sample (T=0.1) in our experiments to quantify accuracy (LL: 282-283).\n> Since the answer correctness is determined by an 8b model, I am curious about how reliable the predicted label is. From my previous experience, even GPT-3.5 is not capable of reliably estimating the correctness of model responses, especially when the responses are phrases. Tian et al. [1] also noted a similar issue, as seen in their Appendix C.\n\nWe evaluated the Llama-2-70B-chat results using GPT-4 on TriviaQA and found the accuracy assessment to be consistent with Llama-3-8B in 95% of cases. Additionally, we compared Llama-3-8B with human annotations of accuracy and found agreement in 90% of cases. The source code for the experiments is available, allowing users to re-run them with GPT-4 if their budget permits. However, we used an open-source model to support researchers with limited budgets. Overall, Llama-3-8B appears well-suited for this task, accessible, and easy to use even with limited GPU access.\n>Can this method be applied to long-form responses? Considering that long-form responses typically consist of multiple claims.\n\nYes! As a matter of fact, our method particularly excels when working with longer answers. In our experimental setup, as illustrated by the examples in Appendix (Fig. C.2), the generated responses include the main answer as well as additional contextual content. For example, instead of simply answering “Laplace,” our LLMs might respond with “Laplace, a French scientist who studied…” By building a semantic kernel, we capture these fine-grained similarities and estimate uncertainty more effectively. In contrast, SE aims to assess the equivalence between answers, and including additional information often leads to worse performance (each answer tends to have its cluster). This is demonstrated in Fig. C.2 and discussed in the last paragraph of Appendix C.\n> Missing the following related work …\n\nThank you! We will add these references.\n\n\n**Concluding remarks**  \nWe would be grateful if you could let us know whether our explanations have addressed your concerns. Please let us know if you have any other questions or concerns.\n\n**References**  \n[1] Kuhn, et al. (2023). Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation.", "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": "VT8Cwy3vva", "reviewer": "Reviewer_DkpB", "summary": "The paper introduces the method \"Kernel Language Entropy\", capturing semantic similarities of output sequences via semantic kernels and subsequently estimating uncertainty using the von Neumann entropy.", "questions": "- Is the rather small model Llama 3 8B Instruct capable of evaluating the correctness of an output sequence? Have you considered other (statistics-based) metrics to evaluate the correctness?\n- Have the authors considered utilizing a regression model that directly assigns a single value to the semantic similarity instead of unintuitively having to aggregate the three classes of the NLI model?", "limitations": "The authors adequately addressed limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper proposes a novel approach to estimate uncertainty in LLMs.\n- It presents a solid theoretical foundation by showing that Kernel Language Entropy generalizes Semantic Entropy.", "weaknesses": "The primary area for improvement is the paper's structure. The paper is quite difficult to follow due to definitions and expressions not being clearly contextualized, for instance:\n- **Sections and Headings**: Section 3 is inconsistent in its use of subsections and subheadings. It begins with a motivating example (subheading), followed by the formal definition of PSD kernels without a subheading. The definition of semantic kernels is embedded in the text without a subheading, making it less prominent than the practical approach for constructing semantic kernels, which has a dedicated subsection at the end of the section. Also, VNE is given more prominence than the main concept, KLE (starting with the definition of KLE (subheading) as the VNE, followed by deriving its properties, would improve coherence).\n- **Kernels**: In Section 3.1, two explicit kernels ($K_{heat}$ and $K_{Matérn}$) are introduced. In Section 5, the authors then propose to use $K_{heat}$ and $K_{full}$, with $K_{full}$ being a weighted sum of $K_{heat}$ and $K_{SE}$. The previously proposed $K_{Matérn}$ is no longer considered in the main experiments, while $K_{SE}$ has not been introduced before. It only becomes clear in Section B of the Appendix that $K_{SE}$ is equal to Semantic Entropy, which is referred to as $SE$ in Section 5. Also, the importance of the weighting factor for $K_{full}$ is not discussed. In general, the criteria for choosing between kernels are unclear (and not all kernels consistently outperform the baselines across datasets).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer DkpB,\n\nThank you for your positive assessment of novelty and theoretical motivation of our work. Please, let us address your questions and pointed weaknesses:\n\n**Weaknesses**\n>Section 3 is inconsistent in its use of subsections and subheadings. It begins with a motivating example (subheading), followed by the formal definition of PSD kernels without a subheading […]\n\nThank you for pointing this out! We will add subheading to the KLE definition and further add a subsection to highlight “Semantic Kernels and KLE” in order to improve the structure of Section 3.\n\n> In Section 3.1, two explicit kernels ($K_{Heat}$ and $K_{Matern}$) are introduced. In Section 5, the authors then propose to use $K_{Heat}$ and $K_{Full}$ , with being a weighted sum of $K_{Heat}$ and $K_{SE}$. The previously proposed $K_{Matern}$ is no longer considered in the main experiments, while has not been introduced before. It only becomes clear in Section B of the Appendix that is equal to Semantic Entropy, which is referred to as in Section 5. Also, the importance of the weighting factor for is not discussed. In general, the criteria for choosing between kernels are unclear (and not all kernels consistently outperform the baselines across datasets).\n\nThank you for bringing it to our attention! $K_{\\operatorname{Matern}}$ was considered in the main experiments and showed similar results to $K_{\\operatorname{heat}}$ (see Fig. 4). Thank you for pointing out the inconsistencies regarding  $K_{\\operatorname{SE}}$; we will include its definition in the main text. We chose a weight factor using the validation set, and since the results with the validation set versus the default parameters are not significantly different, it is reasonable to use the default value (0.5) in practice or choose it as a hyperparameter with a validation set. It appears that all kernels outperform SE, with the best results observed using the vanilla $K_{\\operatorname{heat}}$ (see Fig. 4). $K_{\\operatorname{heat}}$ consistently shows strong performance and can be chosen as a default choice. We will add more details on this to avoid any confusion.\n\n**Questions**\n>Is the rather small model Llama 3 8B Instruct capable of evaluating the correctness of an output sequence? Have you considered other (statistics-based) metrics to evaluate the correctness?\n\nWe evaluated the Llama-2-70B-chat results using GPT-4 on TriviaQA and found the accuracy assessment to be consistent with Llama-3-8B in 95% of cases. Additionally, we compared Llama-3-8B with human annotations of accuracy and found agreement in 90% of cases. The source code for the experiments is available, allowing users to re-run them with GPT-4 if their budget permits. However, we chose to use an open-source model to support researchers with limited budgets. Overall, Llama-3-8B appears well-suited for this task, accessible, and easy to use even with limited GPU access. We will expand on this in the next revision!\n\n> Have the authors considered utilizing a regression model that directly assigns a single value to the semantic similarity instead of unintuitively having to aggregate the three classes of the NLI model?\n\nWe considered several ideas on how semantic kernels can be enhanced, including utilizing a regression model. However, in this work, we chose to focus on building upon existing approaches, and previously, NLI model outputs were used directly. We also employed confidences from the NLI model as graph weights but did not observe the improvement ($K^{DB}_{*}$, Fig. 4). We leave the improvement of the similarity measures for future work and briefly discuss these potential improvements and their limitations in LL: 354-356. We will expand on this in the next revision!\n\n**Concluding remarks.**  \nWe would be grateful if you could let us know whether our explanations have addressed your concerns. Please let us know if you have any other questions or concerns.", "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": "H6CE2mvqIk", "reviewer": "Reviewer_tEe6", "summary": "The authors propose a novel Kernel Language Entropy (KLE) method for uncertainty estimation in white- and black-box LLMs. KLE defines positive semidefinite unit trace kernels to encode the semantic similarities of LLM outputs and quantifies uncertainty using the von Neumann entropy. It considers pairwise semantic dependencies between answers (or semantic clusters), providing more fine-grained uncertainty estimates than previous methods based on hard clustering of answers. We theoretically prove that KLE generalizes the previous state-of-the-art method called semantic entropy and empirically demonstrate that it improves uncertainty quantification performance across multiple natural language generation datasets and LLM architectures.", "questions": "1. How do I get the final answer based on 10 samplings? For example, in fig 1, what could be the final answer of LLM2, majority vote?", "limitations": "the authors adequately addressed the limitations", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The authors propose Kernel Language Entropy, a novel method for uncertainty quantification in natural language generation.\n\n2. The authors propose concrete design choices for our method that are effective in practice, for instance, graph kernels and weight functions.\n\n3. The authors empirically compare our approach against baselines methods across several tasks an LLMs with up to 70B parameters (60 scenarios total), achieving SoTA results.", "weaknesses": "1.  The motivation is clear in Fig 1, but why choose the kernel to solve the problem, this part is not very clear.\n\n2. The proposed method looks like it depends on the sampling times, which is expensive. How is the performance when we sample few times?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer tEe6, \n\nThank you for the positive assessment of the novelty, practical effectiveness, and empirical comparison of our work. We would like to address the concerns and questions you raised below:\n\n**Weaknesses**\n\n>The motivation is clear in Fig 1, but why choose the kernel to solve the problem, this part is not very clear.\n\nConsidering only semantic clusters, as done in semantic entropy [1], is severely limiting because it assigns responses to strictly separate equivalence clusters. In reality, the space of semantic meanings is more nuanced and fine-grained; some answers may be similar even though they are not exactly semantically equivalent. Therefore, introducing a metric to capture semantic similarity is essential, and assigning a kernel is a natural choice for this purpose. In the center of Figure 1, we visualize semantic kernels – those kernels characterize the distance in semantic space and thus are more expressive than simply considering a distribution over distinct semantic clusters. The von Neumann Entropy over the normalized kernel provides a convenient way to quantify entropy while accounting for the semantic similarity. We will clarify this in the next revision\n\n> The proposed method looks like it depends on the sampling times, which is expensive. How is the performance when we sample few times?\n\nFor the rebuttal, we conducted an ablation study to investigate the optimal number of samples. See Fig.1 in the attached PDF. We observed that the performance of KLE is better than that of SE for all sample sizes, with a significant increase when the number of samples goes from 2 to 6, but continuing to grow until 10 samples. In practice, we recommend selecting as many samples as feasible and parallelizing sampling if needed.\n\n**Questions**\n\n> How do I get the final answer based on 10 samplings? For example, in fig 1, what could be the final answer of LLM2, majority vote?\n\nFollowing previous works [1, 2], we chose an answer sampled with a low temperature (T=0.1) as a final answer of an LLM, LL: 282-283. The majority vote is another viable option for short generations, however, in long-form generation answers become more diverse, which means that each semantic cluster is small and the majority vote becomes unreliable.\n\n**Concluding remarks**  \nWe would be grateful if you could let us know whether our explanations have addressed your concerns. Please let us know if you have any other questions or concerns.\n\n**References**  \n[1] Farquhar, et al. (2024). Detecting Hallucinations in Large Language Models Using Semantic Entropy.  \n[2] Kuhn, et al. (2023). Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation.", "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:
We thank all reviewers for their thoughtful reviews, valuable suggestions, and for taking the time to read our paper!

We particularly appreciate the positive recognition of many aspects of our work, including its novelty (tEe6, DkpB, Raee), significance (tEe6, Raee), empirical comparison and experimental setup (tEe6, S5q9), and theoretical results and research problem (DkpB, S5q9).   
We hope we have addressed all questions and concerns raised by the reviewers and are happy to discuss any remaining concerns or questions during the rebuttal.

**Main Changes:**
- Improving the clarity of the text with minor fixes and additional explanations.
- Including additional results that explicitly show the relative improvement in AUROC and AUARC compared to other models across 60 experimental scenarios setups (see Tab. 1 in the attached PDF). (S5q9)
- Investigating the impact of the sample size with a new ablation study (see Fig. 1 in the attached PDF). (tEe6, DkpB)
- Confirming the validity of using Llama-3-8B for accuracy checking by comparing it with human evaluation and GPT-4. (Raee, tEe6, DkpB, S5q9)

Please, take a look at the attached PDF for visualizations and tables.

We would be grateful if you could let us know whether our explanations have satisfactorily addressed your concerns. We are also open to discussing any other questions you may have.

Meta-review: This paper provides an improvement over Kuhn et al. (ICLR, 2023) "Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation", which performs hard clustering of the generated answers and computes the entropy of the clusters, by modifying the notion of semantic entropy to consider inter-cluster interactions. This is done by considering instead the von Neumann entropy (VNE) with respect to a graph kernel, where the graph edge weights encodes the similarity between the clusters. 

Most reviewers agree that this is a simple but well motivated and theoretically sound approach, pointing out as weaknesses the modest empirical improvements, the requirement of multiple samples to compute uncertainty, and the need to improve the structure of the paper. While this seems a relatively small contribution on top of Kuhn et al. and it has its limitations, the proposed approach seems solid and addresses an important problem with the original definition of semantic entropy by Kuhn et al. The rebuttal is convincing and provides additional results which will improve the paper. I am leaning to recommend acceptance.
Decision: Accept (poster)