To Believe or Not to Believe Your LLM: Iterative Prompting for Estimating Epistemic Uncertainty
Authors: Yasin Abbasi-Yadkori
Ilja Kuzborskij
András György
Csaba Szepesvari
Venue: NeurIPS 2024 poster (2024)
Keywords: uncertainty quantification
large language models
Primary area: probabilistic_methods

Abstract: We explore uncertainty quantification in large language models (LLMs), with the goal to identify when uncertainty in responses given a query is large. We simultaneously consider both epistemic and aleatoric uncertainties, where the former comes from the lack of knowledge about the ground truth (such as about facts or the language), and the latter comes from irreducible randomness (such as multiple possible answers). In particular, we derive an information-theoretic metric that allows to reliably detect when only epistemic uncertainty is large, in which case the output of the model is unreliable. This condition can be computed based solely on the output of the model obtained simply by some special iterative prompting based on the previous responses. Such quantification, for instance, allows to detect hallucinations (cases when epistemic uncertainty is high) in both single- and multi-answer responses. This is in contrast to many standard uncertainty quantification strategies (such as thresholding the log-likelihood of a response) where hallucinations in the multi-answer case cannot be detected. We conduct a series of experiments which demonstrate the advantage of our formulation. Further, our investigations shed some light on how the probabilities assigned to a given output by an LLM can be amplified by iterative prompting, which might be of independent interest.

To Believe or Not to Believe Your LLM: Iterative Prompting for Estimating Epistemic Uncertainty
Yasin Abbasi Yadkori Google DeepMind yadkori@google.co com
Ilja Kuzborskij Google DeepMind i1 iljak@google. e. com
András György Google DeepMind agyorgy@google.com com
Csaba Szepesvári Google DeepMind and University of Alberta szepi@google.com com
Abstract
We explore uncertainty quantification in large language models (LLMs), with the goal to identify when uncertainty in responses given query is large. We simultaneously consider both epistemic and aleatoric uncertainties, where the former comes from the lack of knowledge about the ground truth (such as about facts or the language), and the latter comes from irreducible randomness (such as multiple possible answers). metric that allows to reliably detect when only epistemic uncertainty is large, in which case the output of the model is unreliable. This condition can be computed based solely on the output of the model obtained simply by some special iterative prompting based on the previous responses. Such quantification, for instance, allows detect ballucinations (cases when epistemic uncertainty is high) in both single- and multi- anntti-nswerretee responses. This is in contrast to many standard uncertainty quantification strategies (such as thresholding the log-likelihood of response) where hallucinations in the multi-answer case cannot be detected. We conduct a series of experiments which demonstrate the advantage of our formulation. Further, our investigations shed some light on how the probabilities assigned to a given output by an LLM can be amplified by iterative prompting, which might be of independent interest.
particular, we derive an information-theoree
1 Introduction
Language models too occasionally suffer from hallucinations, or responses with low truthfulness, that do match our own common or textbook knowledge (Bubeck al., 2023; Gemini Team, Google, 2023). At the same time, since LLMs work by modeling probability distribution over texts, it is natural view the problem of truthfulness through the lens of statistical uncertainty. In this paper we explore uncertainty quantification in LLMs. We distinguish between two sources of uncertainty: epistemic and aleatoric (Wen al.. 2022: Osband al., 2023; Johnson et al., 2024). Epistemic uncertainty arises from the lack of knowledge about the ground truth (e.g., facts grammar in the language), stemming from various reasons such as insufficient amount training data or model capacity. Aleatoric uncertainty comes from irreducible randomness in the prediction problem, such as multiple valid answers the same query. Hence, truthfulness can be directly analyzed via looking at the epistemic uncertainty of model in the sense that when the epistemic uncertainty is low, the model predictions must be close to the ground truth.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Rigorously identifying when (either) uncertainty is small' is notoriously hard, especially in deep neural networks (Blundell et al., 2015; Antorán et al., 2020). This is because we generally lack guarantees about learning the ground truth (consistency), or even a weaker guarantee about how large the variance of a learning algorithm is. At the same time, there exist many heuristic approaches for uncertainty quantification based on simply looking at the log-likelihood of responses (Kadavath et al., 2022), estimating entropy (Kuhn et al., 2023), ensembling (Lakshminarayanan et al., 2017b; Dwaracherla et al., 2023; Osband et al., 2023), or sometimes even more principled formulations, such as conformal prediction (A (Angelopoulos et al., 2023; Ravfogel et al., 2023; Yadkori et al., 2024) (which however come with strong assumptions).
To the best of our knowledge, a common limitation of these approaches is that they are only meaningful in problems where there exists a single correct response (c.g. label) as they aim for detecting if one response is dominant (or multiple responses with the same meaning), that is, there is only little uncertainty in the prediction. On the other hand, when multiple responses are correct, that is, there is aleatoric uncertainty in the ground truth, simply estimating the amount of uncertainty in the LLM's output is insufficient, as the perfect (ground-truth) predictor may have large aleatoric uncertainty and no epistemic uncertainty, while a completely useless predictor may have large epistemic uncertainty only, but the total amount of uncertainty of the two predictors might be the same.
Contributions. In this paper address the above problem directly, and design methods to decou- ple epistemic and aleatoric uncertainty, allowing us to effectively deal with multi-response queries. Rather than trying to quantify how small epistemic uncertainty can be, we aim to identify when only the epistemic uncertainty is large, in which case we can suspect that the response is hallucinated."
As starting point we make a simple observation: If multiple responses are obtained to the same query from the ground truth (the language), they should be independent from each other, that is, in probabilistic interpretation, the joint distribution of these multiple responses, for fixed query, must be a product distribution.
This observation can be used to measure how far the language model can be from the ground truth. The sequential model implemented by a language model allows us to construct a joint distribution over multiple responses, which is done through iterative prompting of an LLM based on its previous responses and the application of the chain rule of probability: first the model asked to provide response given a query, then to provide another response given the query and the first response, contrast to some of
then third one given the query and the first two responses, an so on. This the earlier works that approached decoupling epistemic and aleatoric uncertainty for classification problems by training the model with label pairs (or tuples) (Wen et al., 2022; Johnson et al., 2024).
So, if the response to prompt containing the query and previous responses is insensitive to the previous responses, we have the desired independence and the LLM-derived joint distribution can be arbitrarily close to the ground truth. On the other hand, if the responses within the context heavily influence new responses from the model then, intuitively speaking, the LLM has low confidence about the knowledge stored in its parameters, and so the LLM-derived joint distribution cannot be close to the ground truth. As more responses are added to the prompt, this dependence can be made more apparent, allowing to detect epistemic uncertainty via our iterative prompting procedure.
Interestingly, as we will see in Section 3, can force LLM to provide a desired (possibly incorrect) response by adding this response repeatedly to the prompt. This phenomenon is then further investigated from the viewpoint of a transformer LLM architecture in Section 4.
The iterative prompting procedure then leads to the following main contributions:
(i) Based on the above iterative prompting procedure, we derive an information-theoretie metric of epistemic uncertainty in LLMs (Section 5), which quantifies the gap between the --d-eerieed distribution over responses and the ground truth. This gap is insensitive to aleatoric uncertainty. allowing to quantify epistemic uncertainty even in cases where there are multiple valid responses.
(ii) We derive a computable lower bound on this metric, which turns out to be a mutual information (MI) of an LLM--erived joint distribution over responses, and propose a fimite-sample estimator for it.
1 For instance, by saying that predictions live in confidence set with high probability. 'In technical terms this corresponds to giving lower bound, rather than an upper bound, on the quantity capturing the uncertainty.

---

We prove that this finite-sampi sample MI estimator sometimes suffers only negligible error even though LLMs and their derived joint distributions are defined over potentially infinite supports (all possible strings in a language).
(iii) We discuss an algorithm for hallucination detection based thresholding a finite-sample MI estimator, where the threshold is computed automatically through a calibration procedure. We show experimentally on closed-book open-domain question-answering benchmarks (such as TriviaQA, AmbigQA, and a dataset synthesized from WordNet) that when the data is mostly composed of either single-label or multi-label queries, our MI-based hallucination detection method surpasses a naive baseline (which is based on the likelihood of the response), and achieves essentially similar performance to that of more advanced baseline which based on the entropy of the output as a proxy for uncertainty. However, on datasets which contain both single- and multi-label samples at the same time, our method also significantly outperforms the entropy-basee baseline, by achieving a much higher recall rate on samples with high output entropy while maintaining similar error rates.
(iv) Focusing on a single self-attention head, we identify a simple mechanistic explanation for how the model output can be changed through iterative prompting using previous responses, as discussed earlier. Suppose that the prompt is composed from a query and repeated element (e.g.. a possibly wrong answer). If the query lies within the space spanned by the large principal components of a key-query matrix product, then the output will be generated according to the knowledge extracted from the training data (now stored in a value matrix). On the other hand, if the query has little overlap with the large principal components, then the repeated element likely be copied from the prompt.
2 Preliminaries
Conditional distributions and prompting. Let X' be the space of finite text sequences, that is X C Σ- where is a finite alphabet (and E' U Σ"). Moreover, consider a family of conditional distributions P {u X' + [0. 1] Exex f( z²) = Vr' E X'.. In the following. we let P E be the ground-trute truth conditional probability distribution over text sequences (responses) given a prompt, and we let Q E P be the learned language model. Given a fixed query E X and
possible responses ....... Y,, we define a family of prompts F (F. : X 1 E N}, such that Fe(x, Yi...., Yi) is defined as:
Consider the following question: Q: x
One answer to question Q is Y,. Another answer to question Q Y2- Another answer to question Q is Y.
Provide an answer to the following question:
Q: xr A:
Information-theoreti notions. Let μr, p¹ be distributions supported set 2 21 .... 2, where (2x); is a collection of countable sets. The entropy of a distribution p is defined as H()) = ELez (n=))n(1//tt
If pe are such that (²(2) 0 only if μu²) Leibler divergence between them defined PKI(H,
we have Kullback- Eeez p(2)ln()(()) In(u())//(())) For any E 2, we denote 2 (EI,..., 2t-1, 2i+1....; zn). and the marginal of the ith coordinate of J is given by p=(=)= E Eziez= mlz). The product distribution of the marginals of p is given by
0 I1 pi(z), and the mutuall information of μ is defined as [(u) DKI n))
3 Probability amplification by iteratively prompting
In this section demonstrate that, mentioned in the introduction, repeating possible responses several times in a prompt can have pronounced effects on the output of a language model. Consider == =What is the capital of the UK?" and Y1 Here we can repeat the sentence "Another answer to question Q is Paris." " an arbitrary number of times. Although the number of repetitions changes the behavior of the LLM, the correct response maintains a significant probability: as Figure shows, the conditional normalized probability of
Y, = "Another answer question is Paris." "
3 Following the usual convention, we define 0 In 0 and a In(a/0) oc for any a 'To obtain conditional normalized probabilities, we consider the probabilities of the two responses, and normalize them that they add to I.
3

---

mmm
Q: What the capiaal of the U/8
Q. Who was the firt US presiden?
Q Who the aathor of The Graper Wrach? be John Steinbeck (to Emer Hemingway 10 10
Q. Whon the Sorgest country in the world? Russio 99.9999)) and United Kingston
London (or 1.0) and Partr (1.29 10-10)
George Washington (0.999) und
Abrutsn Lincola (3.1 10 00).
10-0%).
Figure I: Single-label queries with low epistemic uncertainty: Conditional normalized probability of the correct completion given repetitions an incorrect response. Each figure shows the query and the considered two responses with their imitial probabilities, as response for the query, in parentheses (the first response is the correct one).
national inctrommntt hellnd? A: The hopp (0.936) and Uillromm pipez (0.063).
Which actor brveme
Q: Which louger ser comee or rat? A:A (0.538)
Monday's fuir what is Sutarday' 's child" A: Work hand for living (0.093) and Full (0.906).
Boad jilw Skyfoli? A: Raigh Finness 65 1) Judi Deach (0. (0.348).
and comel (0.461).
Figure 2: Single-label queries with high epistemic uncertainty: Conditional normalized probability of the correct completion given repetitions an incorrect response. Each figure shows the query and the considered two responses with their initial probabilities, response for the query, in parentheses (the first response is the correct onc).
Nome London (0.908) and Monchester (0.D41).
yellow fruit Ac: (U.715) 15) Lemon 284).
Q: Name drink, (0.880) and Beer (0.:344).
game played by more than plavers A: Vollesboll! (0.542) and Socver (0.457).
Figure 3: Multi-laber queries with aleatoric uncertainty: Conditional normalized probability of the first the two provided responses, both of which are correct, given repetitions of the second response in the prompt. Each figure shows the query and the considered two responses with their initial probabilities, as response for the query, in parentheses.
the correct response, "London" ", reduces from approximately to about 96% as we increase the number of repetitions of the incorrect response to 100. Figure shows more examples where, with initially low epistemic uncertainty in the response to the query (the aleatoric uncertainty is also low as consider single-response queries), the correct response maintains significant non-negligible probability even in the presence of repetitions of incorrect information, while the probability of predicting the latter increased.
Next, we consider a queries for which the model is more uncertain. For the prompt "What is the national instrument of Ireland?", we observe that responses "The harp" and "Uilleann pipes" " both have significant probabilities (the first answer the correct one). This time, by incorporating the incorrect response in the prompt multiple times, the probability of the correct answer quickly collapses to near zero, as shown in Figure 2, with significant epistemic uncertainty.
Finally, we consider multi-label queries for which the LLM confidently knows correct answer. This time, by incorporating a potential response the prompt, the probabilities of other correct answers stay relatively large. Figure shows four such examples.

---

4 Explanation through the lens of in-context vs. in-weight learning
The sensitivity of the response of an LLM to extra in-context information, observed above, can already be observed in a single attention head as explained next.
We consider an idealized attention mechanism as follows. Let E Raad' be an input matrix comprised of semantic feature vectors each of dimension d'. Each row is meant to represent complete statement (such as "Whal is the capital of the UK?" or "One answer to the question is Paris.", etc.) rather than a single token. Let X E R1xxd be the first row of Z. which represents the query of interest, such as "What is the capital of the UK?". Let E E R RIxd' d' be a special vector indicating the end of the input. The matrix Z X, denoting the Z matrix without its first row, represents the in-context information.
We assume the ground-truth distribution P is such that a query vector is mapped to its response, but statement simply copied. For example, for V = "What the capital of the UK?". P(- VV) would be a distribution with support on "London" " and its variations, while for V' = "What is the capital of the UK? One answer to the question is Paris.", P(- V') returns the same distribution. We assume a parameter matrix WV is learned such that V W estimates P(- V) for vector V.
Let WΩ, W W V E 12d be the query, key, and value matrices. A self-attention head with query X and context Z X is defined as
f(z; W WK, WV) = Softmax (d=TT9(zwKsTT ) zwv
where the output of the softmax is row vector of length
If X has appeared many times in the training data, then parameters Wº and W could be learned such that E (WWK) X is large, that is, X is within the space spanned by the large prin- cipal components of the key-query matrix product. Then, no matter what in-context informa- tion appears in Z. the probability assigned to X will dominate the softmax, and we will have
Softmax
E (ZWKK) Z XT, and therefore ((z W WK WV) ~ 1X).
Now, consider the case that X has not appeared many times in the training data, and vector Y is copied in many rows of Z. Then E (W(K)) could be small as X is not in the span of the large principal components of the key-query matrix product. Therefore f(z Wº, W WV) Y (ta E (ZW Z R YT. Even if X is in the span, repeating Y t times in Z would give a f-times increased total weight to Y inside the softmax, which can dominate the weight assigned to X when t is large enough, also resulting in Y as the answer.
since Softmax
5 Metric of epistemic uncertainty and its estimation
In this section we apply iterative prompting to estimate the epistemic uncertainty of a language model about responding to some query. The idea is to utilize the different behavior patterns observed in Section 3, which can be used to differentiate between two modes of high uncertainty: when the aleatoric uncertainty is high vs. when only the epistemic uncertainty is high. We then apply our new uncertainty metric to design a basee-based hallucination detection algorithm.
We will first present the uncertainty metric and its estimate for a distribution defined on the direct outputs of an LLM;; the changes needed to take semantic equivalences of language into account deferred to Appendix A (Kuhn et al., 2023; Farquhar et al., 2024).
Our uncertainty metric, similarly to the ones considered by, e.g., Wen et al. (2022); Osband et al. (2023), is based on analyzing the joint distribution of responses: if multiple responses are sampled jointly according to the ground-truth distribution, they should be independent (as one instantiation of a response should not affect other responses). To make this notion precise, we start with defining notion of the joint distribution over responses given query, derived from the language model through the prompting mechanism F. defined in Section 2:
Definition 5.1 (Pseudo joint distribution). Given family of prompt functions F, a conditional distribution μ E P. and n E N, we use notation to denote a pseudo joint distribution defined as ç(Y Yn x) μ(Yi Fo(x)) 2(Y2 Fi (i(
p(n, Fn-1(z, Yn-1)) (I)
5

---

The above is pseudo joint distribution since the standard conditioning in the chain-rule is replaced with prompt functions of the conditioning variables. In the following we focus on Q derived from the LLM and P derived from the ground truth.
Remark 5.2 (Sampling from Q). Note that sampling from Q can be simply done through a chain-
rule-like procedure as can be seen from the above definition, that is, to have (Y,,..., Yn) ~ Q we draw Yi Q(- Fo(x)), Y2 Q(- (x, (1)), Y3 Q(- F2(a, Y1, Y2)), and so on.
In the rest of the paper we drop subscripts in joint distributions and conditioning on query x (which is understood implicitly), for example, P = -r,
For any query x E X, let (x) denote the support of Q. We make the following assumption about the ground truth, which states that the model Q generates reasonable responses and that the distribution of such responses are independent according to the ground truth:
Assumption 5.3 (Ground truth independence assumption). For any query a E X. (i) there exists a sequence of valid responses (xx C X such that the ground-truth distribution satisfies
P(Y| F--(zz, Yi...., Y(-1)) = P(Y. | x) (ii) Vo((x) C ((x), that is, the model Q generates reasonable responses.
for any & E N and any (Y,,..., Yi) E v(a);
Note that the above assumption is heavily dependent on our prompt construction and the assumption that .i..... Yi-1 are valid responses; without these the independence assumption would not hold, for example, if .y,-.., Y, were partial answers, such as a step of an algorithm or a part of a story, or would completely redefine the problem ("Disregard the previous question. Instead answer the following...", "). because in such cases Y2 might indeed depend on the previous outputs Y1, ...... Yi-1- Roughly speaking, the assumption tells that the response distribution is insensitive to a query based on previously sampled responses. For example, for query x "Cappital of the UK:", the probability of Y22-222 = "London" " essentially does not change if a city is Y, = =Parris.
To measure epistemic uncertainty, we need quantify how far the estimated pseudo joint distribution Q is from the ground truth P. One natural choice is the following definition:
Definition 5.4 (Epistemic uncertainty metric). Given an input x E 2, we say that the epistemic uncertainty of Q is quantified by DKL (Q. P).
Here DKL measures how well Q approximates P for given query x. Namely, this metric determines if Q assigns large probability to an event which has a small probability under P. In case of LLMs, this means the LLM generates a sequence that is unlikely in the typical usage of the language. Given an input x, we want to estimate the above hallucination metric, but we only have access to Q, and so computing it explicitly is impossible. However, next we show that under Assumption 5.3 we can lower bound (K P) by a quantity which only depends on Q (the proof is given in Appendix E).
Theorem 5.5. For all pseudo joint distributions P and Q satisfying Assumption 5.3, DKL(Q, P) 2 I(¹).
The lower bound in the theorem holds uniformly for all P. and it is computable solely based on Q. This makes the bound applicable for decision making; in fact we chose to consider (Q.(Q. P) as the measure of epistemic uncertainty (out of similar distance measures) since it admits this property.
Also, note that have T(@)= D (Q. (+) Q = Ey Qun, 1 Ye, 11.1, Vn). Bn) + Q(Y.), because the independence assumption Assumption 5.3 does not necessarily (and, in practice, almost never) holds for Q.
In general Eyr, @(11..... ... 9t-1, Y,, 91+1, ...
Finally, quantity related to @K is DKL with arguments arranged in the opposite order, that is DEL (P, Q) which is (query) conditional excess risk of the LLM--driieed pseudo joint distribution Q under the logarithmic loss. Controlling the excess risk (for instance, upper-bounding it) for various algorithms is one of the central questions in learning theory, however it is much harder task than the one we consider here, because for the former we need to theoretically control all sources of errors (such generalization, estimation, and approximation error).

---

1: Input:
ME Mi(2
any (pseudo-) joint distribution over X
KEN.
sample size
71, 12
stabilization parameters (typically selected as 1/k)
2: Independently sample tuples X1, .... X (
3: Construct a set of indices of unique elements U =ii [k] X, xX, Vj <
4: Construct empirical distributions: let Z = Σjer ((Xx), and for all i E U, compute
fx(X,) Z
(X;;
and T (X.)
II
Σ
MXX,,,,.... Xi.j...... Xt,n
j=1 LEU =x,
5: Compute estimate of MI ((,,)) = ((X)) In
x(X++m
(X,++
Algorithm 1: MI estimator.
5.1 A computable lower bound on epistemic uncertainty
Theorem 5.5 gives lower bound on the epistemic uncertainty by the mutual information. However, to compute the mutual information term, in practice we need to evaluate Q on its entire support, which is potentially infinite. Practically speaking, it is impossible observe probabilities of all strings under the language model and so we must rely on finite sample. Therefore, we replace Q with an empirical distribution with a finite support; in the following we show that the error induced by such an approximation is controlled. To estimate the MI we employ the method given in Algorithm for generality it is presented for an arbitrary (pseudo) joint distribution μ4, but we keep in mind that our case of interest is Q. Note that most terms in the summations defining the product distribution o are zero (except the ones which correspond to the observed data). Adding ?1 and 72 in the estimator [m, 722 is intended to account for the total probability of missing observations, not included while constructing j and 7 making sure the estimate is bounded.
The bias introduced by (71.72 the last equation allows us rigorously bound the error in estimating ((4) via (71, 72). which is explored next. In particular, in Theorem 5.6 we prove gigg-probabilityy lower bound on [(4) in terms of Ig. The core of controlling the estimation error is in accounting for the missing mass, or in other words, how much of μ we miss out by only observing finite sample. In Appendix F, present more complete discussion and the proof of the bound on the estimation error for mutual information. Here we adapt this result to our particular case.
Define the missing mass as Us = =E x= μ(x) Ifxx (XI..... Xa1}. ready to present a non-as con-asymptotic bound on the estimation error, which depends on the estimator (e(1, 72), the expected missing mass, and the sample size:
Using this quantity, we are
Theorem 5.6. Suppose that Ta(T1: 72) is given by Algorithm 1, and assume that X is funite. For 71 1/(k (), and "/2 satisfying 722 2 71 + n01 - 2), with probability least - ô, we have
T(p) 2 (1 (1- (1- Temm, (1
ln(
+ +11 In + Ck where Ek =E(U +
k
Furthermore, given Saup E [0, 1), let X _ x2 such that 2²²) Ssupp- Then, for 7 1/(k ()), and 2/2 satisfying 7/2 2 71 + (1 Z). with probability at least 1 - 5. we have
| + (1+ II (1++)(1)) (ōsupp + +ww)
1(x) 2 (1 (1- (1
The theorem is a corollary of Theorem F.4 shown Appendix Note that in Theorem 5.6 we consider two bounds. The first one is pessimistic in the sense that it does not expect that the samples carry much information about the support, and most suitable in situations where we expect y to be spread out (uniformly) across its entire support. The price of not having samples covering the whole support in
7

---

this case is a factor n In |X appearing in the bound. For example, in case of a language model with 10, 000 tokens, considering all possible strings of length T tokens yields n in X T In (110000). and so [14) 2 (1 - εx) (n, 12) - (1/k + (1 + n Tln(1 + k In(10000)) Ex). Arguably, in rare, in natural languages
will not encounter all possible strings. To this end, consider an optimistic scenario where the effective support of Jr, denoted by X, is small with high probability. In this case, we can replace the size of the support for strings of length n, |2 in the first bound with the effective support size |x8,, and we only pay essentially a factor In(1 + 2 instead of v In(1 + k(x))- In case the effective sample size is only polynomial in n, this leads to an exponential reduction
practice, such situations
for the second term in the bounds. In fact, in Appendix F.4 we demonstrate some empirical evidence that on two question-answeriig - benchmarks, |.( rarely exceeds 100 with v(X) 2 0.95, while sampling responses from an LLM given a query.
Next we consider sufficient conditions for the estimator to converge to the mutual information. In particular, using the first bound in the theorem, we have (hiding logarithmic factors) I(n) = 2((1
B(U&)) TA 72) - B(U&)) as k -> co. This tells us that the rate of estimation error is essentially controlled by the expected missing mass ].[&)). which, as we will see, converges to zero as k - oc, however the decay can be very slow in general. For example, it is known that for finite support of size N, B[U²] < e x when &s I N and B[Ux] < N/(e k) otherwise (Berend and Kontorovich, 2012). For countable distributions with entropy bounded by h, one has E[U I h/ Ink)..
Despite these pessimistic bounds, in reality we expect the expected missing mass to be significantly smaller, especially when j heavy-tailed. is well-known that natural languages (and many artificial ones) follow a Zipf distribution, where probability of each word (or text piece) is proportional to 1/frre((eex)) for some exponent a > I, where freq() is a frequency of occurrence in the corpus (Piantadosi, 2014). Then, we expect that [[[ú]] should be much smaller than in such a case, since sampling from the tail of Zipf distribution a rare event. To this end, in Appendix F we show that if Q is Zipf with exponent a >> 1, then for any free parameter B > 0. E[UA] Oak -9)). Hence, the rate which the expected missing mass vanishes can be very fast (potentially matching a concentration rate 1/Vi le for a = 2).
Finally in Appendix F.4 we present a data- data-dependent estimation of E(U,] based on a concentration inequality for a missing mass and repetitive sampling from LLM, in the context of Q/A datasets showing that the expected missing mass is highly concentrated close to 0.
5.2 Score-based hallucination tests
Let Te(7, [T(()) computed in Algorithm 1 for μ = Q, to emphasize the explicit dependence on the query x. The uncertainty estimate (7, derived above can be used as a score indicating the strength of our belief that the LLM hallucinates for the given query x. Such score can then be used to design abstention policies: if the response deemed to be hallucinated, the system abstains from responding, while response is provided otherwise. Score-based abstention methods usually compute
score chosen by the user (such the response likelihood or the estimator 7(r) discussed earlier), and declare hallucination if the score is above or below a threshold, which is determined through calibration. To detect hallucinations successfully, the threshold can be adjusted through calibration on a given task using a hold-out (ground-truth) sample, see, for instance, the paper of Yadkori et al. (2024) where this calibration discussed in detail.
Given our estimated lower bound on the epistemic uncertainty, we can define an abstention policy (a policy which decides when the LLM should abstain from prediction) as ax(z) = if Z3 (71, 72, x) < A and (x) = 1 if Tx (71, 72, xr) 2 X, where À >> O is threshold parameter tuned on hold-out sample of some particular task. This policy abstains (ax(x) = 1) when the epistemic uncertainty in the prediction (response) is large. When the policy does not abstain (ax(x) = 0), any prediction from Q can be served. In the experiments, we compare a number of scoring functions for detecting hallucinations, including 7(7), the probability of the greedy (temperature zero) response, and an estimate of the entropy of the response distribution.
8

---

6 Experiments
In this section we evaluate our abstention method derived based on the MI estimate in Section 5.2 on a variety of closed-book open-domain question-answering tasks. our experiments we either sweep through all abstention thresholds (Figure 4), or optimize the threshold on some calibration data, as explained in the description of the relevant experiment (Figure 5).
Language model. We used Gemini 1.0 Pro model (Gemini Team, Google, 2023) to generate outputs and scores. Similar results were obtained with a - much smaller -emiin 1.0 Nano-1 model, which are deferred to Appendix H.
Datasets. We consider three different datasets and their combinations: As base datasets, we consider (i) a random subset of 50, 000 datapoints from the TriviaQA dataset (Joshi et al., 2017), and (ii) the entire AmbigQA dataset (with 12038 datapoints) (Min al., 2020). These datasets mostly contain single-label queries, and only contain a few multi-label ones.' Moreover, we created multi-label dataset based on the WordNet dataset (Fellbaum, 1998): We extracted all (6015) datapoints from ity subtree. For each datapoint (entity,
WordNet at depth 4 or more of the physical chi children) in WordNet, we constructed a query of the form "Name a type of entity." and children are considered target labels.
Comparison of responses and computing the output distributions. We use the F1 score thresh- olded at 0.25 to decide if two text sequences match. Additional details are provided in Appendix G.
Baselines. We consider abstention policies based on four scoring methods: (i) the probability of the greedy response (denoted by TO); (ūi) the semantic-entropy method of Kuhn et al. (2023) whose score is the entropy of k = 10 generated samples (denoted by S.E.); (iii) our proposed mutual information score as defined in Section 5 (and denoted by M.I.) with the choices of k = 10, n = 2. and 7/1 = 72 0 (the latter choice approximates the case that the number of potential responses can be very large in which case the theoretical choice of 71 and 72 would be very small); (iv) the self-verification method of Kadavath al. (2022) (denoted by S. Additional details provided in Appendix G.
Results. We consider the precision-recall (PR) trade-off for the various methods on the different datasets. Here, recall is the percentage of queries where the method does not abstain, and precision is the percentage of correct decisions among these queries. Figure 4ab show PR-curves for the baselines and the proposed method on TriviaQA and AmbigQA. As can seen, our method is better than the TO and S.V. baselines, but performs similarly to the S.E. method. This is because the TriviaQA and AmbigQA datasets contain mostly single-label queries, and therefore a first-order method such as S.E. is sufficient to detect hallucinations. The AmbigQA dataset contains a few multi-label queries, but upon closer inspection, we observe that the LLM has low entropy on most method such queries.
of these queries. Therefore., first-order method can perform well Our proposed method, as well as the baselines, make no mistakes on the WordNet dataset (as the prediction of the LLM is always correct), hence omit those results. The S.V. baseline performs significantly worse than the other methods when the recall is not high (is below about 0.8).
The similar performance for the S.F. and M.I. methods shown in Figure 4ab is due to the fact that the LLM has low entropy on most multi-label queries. However, idcally, an LLM should have higher entropy on multi-label queries (which would demonstrate broader knowledge, not focusing single possible answer). To include such queries, we mix the TriviaQA and AmbigQA datasets with our WordNet-basse based dataset with "truely" lubti-label queries constructed above. To enhance the intended effect, we filter our WordNet dataset by keeping only queries with entropy higher than 0.7 (approximately the entropy of the uniform distribution over two atoms). Then we have 842 remaining datapoints in WordNet. Note that when considered in isolation, both our proposed method and the semantic entropy method rarely make mistakes this dataset. Then create two new datasets by combining our 842 WordNet datapoints with 842 randomly selected datapoints from TriviaQA and AmbigQA, respectively, resulting in the TriviaQAAWordNe Figure 4cd show PR-curves for the S.E. and M.I. methods on these two combined datasets. Apart from low recall values, the performance of the S.E. method degrades noticeably with the addition
and AmbigQA+ WordNet datasets.
$ Note that the multi-label queries in these datasets typically behave as single-label ones in the sense that the LLM assigns overwhelming probability to a dominant response. In some figures, for better illustration, we show the error rate which is one minus the precision.

---

1.0 10
034
1.0
6.00
RC, scors
scoP
5.6. ccore
100m
00
0.4
0.6
0.9
1.0
0.6
(a) TriviaQA
(b) AmbigQA
(c) TriviaQA+
(d) A WordNet
Figure 4: PR-curve for the baseline and the proposed methods on various datasets. On the TriviaQA and AmbigQA datasets, M.I. and S.E. perform nearly identically, but they outperform the TO and S. S.V. baselines. For the S.E. and M.I. methods, the responses for a large number of queries can be clustered into single group, and therefore the semantic entropy and mutual information scores why the starting point of their curves is at a higher recall values. On the TriviQQAWWodlle A WordNet datasets with a significant number of high entropy multi-label queries, M.I. outperforms the S.F. baseline. The methods perform nearly identical on the not shown recall area.
This and
20
(a) TriviaQA+Wordyy
(b) TriviaQA+ WordNNt
(c) AmbigQA=WordNee
(d) AmbigQA+Wordin WordNet
Figure 5: Recall and error rates (one minus precision: percentage of mistakes when not abstaining) of the proposed and the baseline method on Torriee and AmbigQA+WordNe, datasets. On TriviaQA+Wa WorddNet and AmbigQA+WordNNe datasets, the methods are calibrated at target loss of 0.05 and 0.15, respectively. On the x-axis, the queries are partitioned according to the entropy the LLM's output. Error bars show 2 standard deviation confidence intervals (based on 10 repetitions). While the first-order S.E. method has similar recall and error rates to those of the proposed M.E. method on low-entropy queries, its recall values are nearly zero for queries with higher entropy.
of extra multi-label data. This precision/recall curve might look somewhat strange (with precision sometimes increasing with recall); this is due the fact that both methods are always correct on the large number of high-entropy WordNet queries, where the LLM's default predictions are correct.
The hardness with the combined datasets is that the predominantly single-label datasets (TriviaQA, AmbigQA) might need a different calibration threshold than the multi-label WordNet dataset, and this is better handled by our proposed method than by S.E. To better illustrate the improved abstention properties of our method, we examine how the two methods handle when the output of the LLM is diverse (i.e., has high entropy). order do this, we perform the following experiment: We create a calibration dataset by adding 500 random datapoints from the WordNet dataset to 500 random datapoints from TriviaQA, and another such random dataset for test. We determine the abstention thresholds on the calibration dataset for both the S.E. and the M.E. methods," and measure the performance (error rate, i.c. 1 minus precision, and recall) of the resulting abstention policies on the test set. We repeat this process 10 times and report mean values and 95% confidence intervals with Gaussian approximation. We perform similar evaluation process for mixtures of AmbigQA and WordNet datasets. Figure 5 show that while the S.E. method has similar recall and error rates to those of the proposed method on low-entropy queries, its recall values are much lower for queries with higher entropy, while the M.E. method makes only few mistakes on these queries.
References
Gustaf Ahdritz, Tian Qin, Nikhil Vyas, Boaz Barak, and Benjamin L. Edelman. Distinguishing the knowable from the unknowable with language models, 2024. URL htttss://arxe org/absi 2402. 03563.
'This is done by tixing the target loss rates of 0.05 for TriviaQA and 0.15 for AmbigQA, and finding threshold parameters that lead these rates the calibration set.
10

---

Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends() in Machine Learning, 16(4):494-555 591, 2023.
Javier Antorán, James Allingham, and José Miguel Hernández-Lobato, Depth uncertainty in neural networks. Conference Neural Information Processing Systems (NeurIPS), 2020.
Amos Azaria and Tom Mitchell. The internal state of an LLM knows when its lying. Conference on Empirical Methods in Natural Language Processing (EMNLP), 2023.
Daniel Berend and Aryeh Kontorovich. The missing mass problem. Statistics & Probability Letters, 102):1102-1110, 2012.
Daniel Berend and Aryeh Kontorovich. On the concentration of the missing mass. Electronic Communications in Probability, 2013.
Daniel Berend, Aryeh Kontorovich, and Gil Zagdanski. The expected missing mass under an entropy constraint. Entropy, 19(7):115, 2017.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learing (ICML), 2015.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint ar 2rXiv22033.12112 2023.
Collin Burns, Haotian Ye, Dan Klein, and Jacob Steinhardt. Discovering latent knowledge in language models without supervision. International Conference on Learning Representations (ICLR), 2023.
Chao Chen, Kai Liu, Ze Chen, Yi Gu, Yue Wu, Mingyuan Tao, Zhihang Fu, and Jieping Ye. INSIDE: LLMs' internal states retain the power of hallucination detection. In International Conference on Learning Representations (ICLR), 2024a.
Shiqi Chen, Miao Xiong, Junteng Liu, Zhengxuan Wu, Teng Xiao, Siyang Gao, and Junxian He. In-context sharpness as alerts: An inner representation perspective for hallucination mitigation. In Forty-first International Conference on Machine Learning, 2024b. URL https: //pperev//peeeiieer s
Xinyun Chen, Renat Aksitov, Uri Alon, Jie Ren, Kefan Xiao, Pengcheng Yin, Sushant Prakash, Charles Sutton, Xuezhi Wang, and Denny Zhou. Universal self-consistency for large language model generation, 2023.
Jeremy R. Cole, Michael JQ Zhang, Daniel Gillick, Julian Martin Eisenschlos, Bhuwan Dhingra, and Jacob Eisenstein. Selectively answering ambiguous questions. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2023.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiy preprint arXiv:/8100004800 2019.
Vikranth Dwaracherla, Zheng Wen, Ian Osband, Xiuyuan Lu, Seyed Mohammad Asghari, and Ben- jamin Van Roy. Ensembles for uncertainty estimation: Benefits of prior functions and bootstrapping. Transactions on Machine Learning Research (TMLR), 2023. ISSN 2835-8856.
S. Farquhar, J. Kossen, L. Kuhn, and Yarin Gal. Detecting hallucinations in large language models using semantic entropy. Nature, 2024.
Christiane Fellbaum. WordNet: An electronic lexical database. MIT press, 1998.
Yarin Gal. Uncertainty in deep learning. PhD thesis, University of Cambridge, 2016.
Gemini Team, Google. Gemini: family of highly capable multimodal models. arXiv preprint arXiv:2312.11885. 2023, [Online; accessed 01 O1-February-20244

---

Bairu Hou, Yujian Liu, Kaizhi Qian, Jacob Andreas. Shiyu Chang, and Yang Zhang. Decomposing uncertainty for large language models through input clarification ensembling. In International Conference on Machine Learing (ICML), 2024.
Mingjian Jiang, Yangjun Ruan, Sicong Huang, Saifei Liao, Silviu Pitis, Roger Grosse, and Jimmy Ba. Calibrating language models via augmented prompt ensembles. In Workshop on Challenges in Deployable Generative Al International Conference on Machine Learning, 2024.
Daniel D. Johnson, Daniel Tarlow, David Duvenaud, and Chris J. Maddison. Experts don't cheat: Learning what you don't know by predicting pairs. arXiv preprint arXiv:2402.08733, 2024.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. TriviaQA: large scale distantly supervised challenge dataset for reading comprehension. In Transactions of the Association for Computational Linguistics (ACL), pages 1601-1611, 2017.
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield Dodds, Nova DasSarma, Eli Tran-Johnson, and et al. Language models (mostly) know what they know. arXiv preprint arXiv:2207.05221/ 2022.
Nora Kassner and Hinrich Schütze. Negated and misprimed probes for pretrained language models: Birds can talk, but cannot fly. In Transactions of the Association for Computational Linguistics (ACL), 2020.
Satyapriya Krishna. On the intersection of self-correction and trust in language models, 2023, URL /ttpp::/arxiinn org/ abss/3111.. 02801.
Satyapriya Krishna, Chirag Agarwal, and Himabindu Lakkaraju. Understanding the effects of iterative prompting on truthfulness. In Forty-first International Conference on Machine Learning, 2024.
URL https: /tpprr/vie///eeeeeee//ee net/forum?idd jazckPPMM.... azcKPMME.
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. In International Conference on Learning Representations (ICLR), 2023.
Philippe Laban, Lidiya Murakhovs ka, Caiming Xiong, and Chien-Sheng Wu. Are you sure? challenging 1lms leads to performance drops in the flipflop experiment, 2024. URL https: //arxiv. org/ 2ttp///31..........
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Conference on Neural Information Processing Systems (NeurIPS), volume 30, 201
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Conference on Neural Information Processing Systems (NeurIPS), 2017b.
Daliang Li, Ankit Singh Rawat, Manzil Zaheer, Xin Wang, Michal Lukasik, Andreas Veit, Felix Yu, and Sanjiv Kumar. Large language models with controllable working memory. Transactions of the Association for Computational Linguistics (ACL), 2023.
Moxin Li, Wenjie Wang. Fuli Feng, Fengbin Zhu, Qifan Wang, and Tat-Seng Chua. Think twice before trusting: Self-detection for large language models through comprehensive answer reflection, 2024. URL https: //tppivv/////viv///// org/ abs 2abb//400
Zhen Lin, Shubhendu Trivedi, and Jimeng Sun. Generating with confidence: Uncertainty quantifica- tion for black-box large language models. arXiv preprint arXiv:2305. 19187, 2023.
Shayne Longpre, Kartik Perisetla, Anthony Chen, Nikhil Ramesh, Chris DuBois, and Sameer Singh. Entity-based knowledge conflicts in question answering. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2021.
Andrey Malinin and Mark Gales. Uncertainty estimation in autoregressive structured prediction. In International Conference Learning Representations (ICLR), 2020.
12

---

Potsawee Manakul, Adian Liusie. and Mark J. F. Gales. SelfCheckGPT: Zero-resource black-bor hallucination detection for generative large language models. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2023.
Sabrina J. Mielke, Arthur Szlam, Emily Dinan, and Y-Lan Boureau. Reducing conversational agents' overconfidence through linguistic calibration. In Transactions of the Association for Computational Linguistics (ACL), 2022.
Sewon Min, Julian Michael, Hannanch Hajishirzi, and Luke Zettlemoyer. AmbigQA: Answering ambiguous open-domain questions. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
R. M. Neal. Bayesian learning for neural networks. Springer Science & Busineess Media, 2012.
Ella Neeman, Roee Aharoni, Or Honovich, Leshem Choshen, Idan Szpektor, and Omri Abend. Dis- entqa: Disentangling parametric and contextual knowledge with counterfactual question answering. arXiv preprini arXiv:2211.088:: 1.05655, 2022.
Mesrob I Ohannessian and Munther A Dahleh. Distribution-dependeen performance of the good- turing estimator for the missing mass. In 19th International Symposium Mathematical Theory of Networks and Systems, MTNS, 2010.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Conference on Neural Information Processing Systems (NeurIPS), volume 29, 2016.
lan Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. Epistemic neural networks. In Conference Neural Information Processing Systems (NeurIPS). 2023.
Steven T Piantadosi. Zipf's word frequency law in natural language: A critical review and future directions. Psychonomic bulletin & review, 21:1112-1133 2014.
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge University Press, 2024.
Stephan Rabanser, Anvith Thudi, Kimia Hamidieh, Adam Dziedzic, and Nicolas Papernot. Selective classification via neural network training dynamics. arXiv preprint arXiv:2205 13532, 2022.
Shauli Ravfogel, Yoav Goldberg, and Jacob Goldberger. Conformal nucleus sampling. In Trans- actions of the Association for Computational Linguistics (ACL), pages 27-34. Association for Computational Linguistics, 2023.
Robert Tibshirani and Bradley Efron. An introduction to the bootstrap. Monographs on statistics and applied probability, 57(1), 1993.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations (ICLR), 2022.
Ziyu Wang and Chris Holmes. On subjective uncertainty quantification and calibration in natural language generation, 2024. URL https://aaatt :/arxivv////////////////// wwwpiiii.or//eeeeee org/abs/2400 05213.
Zheng Wen, Ian Osband, Chao Qin, Xiuyuan Lu, Morteza Ibrahimi, Vikranth Dwaracherla, Moham- mad Asghari, and Benjamin Van Roy. From predictions to decisions: The importance of joint predictive distributions. arXiv preprint arXiv:2107.09224 2022.
Yasin Abbasi Yadkori, Tlja Kuzborskij. David Stutz, András György, Adam Fisch, Arnaud Doucet, luliya Beloshapka, Wei-Hung Weng, Yua-Yuan Yang. Csaba Szepesvári, Ali Taylan Cemgil, and Nenad Tomasev. Mitigating Ilm hallucinations via conformal abstention. arXiv preprint arXiv:2405.01563. 2024.
Fan Yin, Jayanth Srinivasa, and Kai-Wei Chang. Characterizing truthfulness in large language model generations with local intrinsic dimension. Forty-first International Conference on Machine Learning, 2024. URL https:: cettps///operrveee/ http://ppeeeeeeeeeeeeeeeeeeeeeee http://www..eeererrrreoto//ot///
13

---

Gal Yona, Roee Aharoni, and Mor Geva. Narrowing the knowledge evaluation gap: Open-domain question answering with multi guati-granularity answers. arXiv preprint arXiv:2401.04695, 2024.
Jiaxin Zhang, Zhuohang Li, Kamalika Das, Bradley Malin, and Sricharan Kumar. Sac3; Reliable hallucination detection in black-box language models via semantic-aware cross-check consistency, In Conference on Empirical Methods Natural Language Processing (EMNLP), 2023.
Tony Z. Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In In International Conference Machine Learning, 2021.
Yukun Zhao, Lingyong Yan, Weiwei Sun, Guoliang Xing, Chong Meng. Shuaiqiang Wang, Zhicong Cheng, Zhaochun Ren, and Dawei Yin. Knowing what LLMs do not know: simple yet effective self-detection method, arXiv preprint arXiv:2310.17915 2024.
14

---

A Additional algorithms for taking semantic equivalences into account
Although Theorem 5.5 and Theorem 5.6 provide lower bound for the divergence between the output distribution Q of the LLM and the ground truth P, these distributions ignore the semantic equivalences between texts, and hence they are less concentrated than their variants which only consider semantically different outputs. Given a semantic equivalence definition, similarly to Kuhn et al. (202)); Farquhar et al. (2024), we propose constructing new ground-trute distribution pe and LLM output distribution Q', where we cluster together semantically equivalent texts, and the probability of cluster the sum of probabilities all semantically equivalent texts in that cluster. We similarity function to define semantic equivalences: two texts considered equivalent their similarity is greater than a given threshold т. Our choices for similarity functions in the experiments described in Section 6. We assume the similarity function and the similarity threshold induce a clustering of the space X, i.c., s(Y,Y') 2 T for Y, X and only if they are in the same cluster.
In practice, rather than constructing the aforementioned distribution Q' explicitly, we can draw sam- ples from Q' by sampling from Q and aggregating samples according to their clusters. The modified uncertainty--stimmttoon algorithm given Algorithm 2 in Appendix using only (semantically) different elements in the sample (the indices of these representative elements are collected in S), that is, we do not account for duplicate samples and we aggregate probabilities of samples that are lexically different but semantically equivalent. Algorithm 2 works with the aggregated probability distribution pz Q' (line 4) by summing cumulative probabilities over clusters. Note that (f),(A) 2 (1', by monotonicity property of KL-divergence (Polyanskiy and smaller support). Therefore, Theorem 5.6 implicitly gives a bound on T(n"), and eventually we have T(/) 2 I(yd). More importantly, we can also directly apply Theorem 5.5 and Theorem 5.6 the distributions f' and Q' and obtain that ( P')= 2 I(Q', giving lower bound on the much reduced (epistemic) uncertainty after taking semantic equivalences into account.
The estimator is constructed
Wu, 2024, Theorem 2.16) (this is because μ' is defined
15

---

1: Input: DE Mi(X")
any (pseudo-) joint distribution over X
EEN
sample size
71,72 2
stabilization parameters (typically selected as 1/k)
8: X" x X - R
a similarity function
R
similarity threshold
2: Independently sample tuples X1, ....... X2 ~ μ E Mi
Construct a of indices of unique elements U = {i E [k] X, X, Vj <j<
4: Construct cluster centers S C U according to the similarity function such that for i,t S. we have (X,, X,) < T and the cluster associated with X; is D(i) {j E U s(X,, 2 2) Compute the aggregated probabilities: for all E S,
((,))) = Σ m(X))
JED(I)
5: Construct empirical distributions: for all E S.
(X,,)
(xX.)
where 7= Σ (X,))
Z
JES
(X,) = II
Σ
i(X,,,,.... Xi.j X
j- (ES:Xe,=xX.,)
6: Compute estimate
((X)) + n (Xx) +
(17,)72) ((X))
iES
Algorithm 2: MI estimator, Python implementation with usage example is given in Appendix B.
16

---

I: Input: ME NEMI(X)
any distribution over X
EEN
sample size
71 2
stabilization parameters (typically selected 1/k)
s: X
similarity function
T R
a similarity threshold
2: Independently sample outputs XI,.., .... Xx ~ μr E (X)
3: Construct set of indices of unique elements U {i E [k] XX Vj <j
4: Construct cluster centers S c U according to the similarity function: for all it e S, we have s(x,, X2) and cluster associated with X, is D(i) (i E s(i,, 2 r)- Aggregated probabilities: for all i E.S.
(x,)
Σ m(X,), JED())
E a(x, JED(I)
5: Construct empirical distributions: for all i, S.
(X, (X,)
Z where Z -m((X,)
jES
|x,) (
where
Z: Σ | XX))
Z:
jES
A(X, x,) =
(X,, = (X.,) Σ (xx
JES
6: Compute estimate
7(X,, Xt) + m
[(mm)2) = MX,, X1) In
T (X,, X,) 77
LEES
Algorithm 3: Alternative MI estimator. A usage example given Appendix C
17

---

B Implementation and usage examples of Algorithm 1 and Algorithm 2
In this section we present an implementation of Algorithm and Algorithm 2 in Python with simple usage example. In particular, the code given in Listing generates synthetic joint distribution over binary tuples with correlated elements (function greate__yntheen wywtheticc.isstributtettt _distribution) Then, we compute exact mutual information of the distribution (function compute _atteee___eaacly and use implementation of our estimator (function MI MI_estimator to estimate a mutual in- formation. This is done for various sample sizes, number of random variables, and levels of correlation (a single experiment multiple experiments the exact value of the mutual information. practical applications, synthetic joint distribution (function create_ create_synthetil ceteeetiiddissiitieeeeeeeeeeeeee distribbttion
run_exppa implemented run_experiment The results of these eventually presented in plots showing convergence of the estimate
be replaced by an LLM-derived pseudo-joint distribution (see Definition 5.1). More detailed description of each function is given in Appendix B.I.
The example can be easily copied from listing. tex within 2406. 02543.
org/
Listing 1: Implementation and usage examples of Algorithm and Algorithm 2 synthetic joint distribution
Copyright 2024 Deaphind Technologien Limited.
Licensed
Apache license, Vereion 2.0 "License"); not use this file except in compliance with the License. You may obtain copy of the License at
#
#
# https://owx.app apw.ch. wawnchh.org/liooooo crg/L1ccome//LLccnese--0
* Unless required by applicable lav or agreed to in writing, software distributed under License distributed
# WITHOUT VARRANTIES OR CONDITIONS OF ANY KIKD, either expresa or implied.
See the License for the specific language governing pernissions and limitations under the License.
itertools import product, import nunpy as from matplotlib import pyplot plt
def www.theteeeiistriiiiiiieeeeee
temp): :
potential lanbda np.mean ([x for y combinations(z, 2)1)
= ar..arry(( (e-ra (C-p/CCCnpppeeppepe wxppp..ppptotttlllleeee temp) for x in spacel) y y.
sample_feetteeeece www.trronnnnttoooommmm jastt__diatrbbarioonpppe.. joint_dist, indices = ap-arange (ranne((len[in (len(joint_ _iitt)
sampled_indies indicee randon. choice cidieei p-joiat_dist, size-k)
sarpled_tuples tuplels [nanplea semmppedd_iae indicces]]]]
return tupleed_tuplee, impled_indicee
def cluster(tuples. joint_dist): return tuples, joint_dist
def sample_fron jatn_jjjiidddetibbutte cttpuuttioooonnoluuuueeeeeeeee clusterrrrpe,,,, joint_diet, k):
sampled, [e_ tuples, sampled_tuple tuple_indices www.uuuiuueeee in, in_eapple ofstices_f_uuiqueee.e
joint_ddat,
indices_of sampled, tuples sampled_tuple [indices_ uniguesiiinneeeee sam_ppple)
(eampled__uuppp tuplee, exis-0, retura_ inder--rrrr))
sampled, tupla_indices indices sanpled_tuple ttd_ttpe_eidiceess indices (indicos_of htt.icoooo.mmuusssnn.c.aaaaapppp coint_dist_oo_ddee owwponnasaaeeeeeeeeeee_eee_eee jointt_das [sanpled_tuule_tnnn indicea]
sampled, tuples, joint_diet_on, sn_aaple cluster saa tuples, joint_diet_on.ee
return loint_diet__o_________ sample,,, sappee__tpples
def compute__ie
compute_MI_exeee MI_ MII.__eaatllyppacc......a mu):
for (x_1, x) in cnmmraate(ppace):
mu_x mi[xi]
mu_x_prod -
for in range(1en(x)):
marg. indices [j for (j, enunerate(space) 2[i] x[1]]
mu_x_prod *- nu mu[marg_indices]
indices) (iiicess.smn sum()
total ma_x tpp.log(m__x/mox.prrodd
return total
def MI_ (__ertintttrrsamlld._r.... co__aplo,, g, gamma_)) ""Implements estinator (Algorithn 1)..
18

---

Arga:
sampled_tuples: nampy array tuplea sampled distribution after deduplication clustering. mo oo ca_plelee munpy array of probabilitien of the clusters. gamma_1: atabtiization paraneter. ganna_ stabilization paraneter.
Returns: (flost) nutual information.
Constructing empirical distribution (Vhat((Imu))) hat on_ ou__on_anppe mu_on_ aanple ma_on, on_.onnno...uu sunp..
Constructing enpirical product distribution (baat(maa-((ooiimme)) hat_mu_prod, www.prod_on_samplee np.zeron( (lan(hattmmoo_mmmmlo)). for (x_1, x) in anunerate (aapppedtttpees) tuples):
hat_mu_x.prot
for in range(ten(xx)):
narg_indices [] for (J, 2) (smpple tuplea) if a[i] x[i]]
bat_mu___prro
semple (marg. indices] audices].eunt .eun()
hat_ma_prod.aumm www.prrd_onn.ommm wttp__od_daappaaaeeeeee on__apple[x__ bat_mu_x.prod
Computing
nf Lesestinaee nat__mu_on_sampp
(pp.to((tat_m_oon + ganma_1) / (hat_ma_prod sample + gamma_ 2)
mi estiatteeee ssleestiuate.su)))
mi_estimate
qun_axperinent(a temp, ax):
up ap.randon.eeee(()) space up. syytthtir_disstriattttt
mi sg.array(Liet(prodaae
repeat=a)])
temprtemp)
mi exect compute_ MI, exactly(spacc,, mu)
k_range up. linspacee 1000, 20, dtyperint)
estinate
for & in range:
ma_ ou_on_ sampled_tupie tuples
wtw.e/frroooiotdiiiiiiiioeeee http::/aco...ooduuuuoooorrraaapp joint_dist-m,
gamma_1 gamma_2 - 1/k
cs_estimata NI_ wew.esstittorooceme (sampled_ tuples,, mu_on_cample, gamm__,, gama__)
all_mi_ent wet.eeettttt...p.. (mi_nddmi__ettttin
as (ai exact, 1inewidth-3, label="HI (exact value)", color="black")
ax.plot range, atl_mi_cstimat,, linoridthr3, label="NI estinator") ax.grid(); ax. legand))) ax xlabaetxxaalleeeeec ("k"); ylaseel ("NE astinate"); ww..atttiitler""Bee (nn)"+ ( $\tau=""*stt
temp_range [0.01, n_range 12, 4,
fig, axe (Lanett range), len(n_range), (igsizee(S+eenternn saapp_r 5+len(a (aange)))))) squeeze-False)
fig. fig.supritle(r" "I estination Snf-dimensions distribution $ipropto \exp(- Aaun 33 x_j \tau)s*"n)
for (1, tamp) in enmeerate(temp.ragg)) anmeratta(__rang)):
ax axe jx
run run_experiment (ara, teap-teap, ax*ax) subplots, haapppoott..juuttteppceeee (rspaccc hspacem0.4) plt.ahow()
B.1 Additional documentation for functions in Listing
create_eyathetic distribution temp)
synthetic distribution chich dependendencies variables.
Arge:
space: 1ist of tuples that the Joint distribution 1a supported (e.g. carteaian product).
temp: temperature paraneter.
Returns:
numpy array of probabilities (came length as space).
def htw.:rrroo.oottt..iiirbbtiote
diint_dist,
Samplea tuplea from a joint distributioo.
Arge:
19

---

space: list of tuples that the joint distribution is supported (e.g. cartesian product). dist: probability distribution (1-D numpy array) where each entry 1s probability tuple. k: sample size.
Retures:
numpy array of tuples nampled from the distribution. mumpy array of indicee of eampled tuples space.
def (tuple,, bint_
Cluatera tuples and aggragates probabilities than in the cluster.
Argo:
tuples: A numpy array of tuples sampled from the distribution after deduplication.
dist: probability distribution (1-D numpy array) where each entry is a probability of tuple.
Returns:
numpy array tuples sampled
distribution represening
cluster.
numpy array of prebabilities of clusters. Each probability is the aggregate of probabilitiea of all tuplea in the cluster.
def wwwt...oonntdiitrrioeiooooeeeeee
aad_:aaadddddddaaeeeaeeeeaa (space, jiint_dist, X)
Samples k tuples from a joint distribution and retains only representative
(removes duplicates).
Arga:
space: list of tuples that the joint distribution supported (e.g. cartesian product).
joint, dist: probability distribution (1-D numpy array) where each entry is probability tuple.
k: sample size.
Returas:
mumpy array of tuples nampled from the distribation after deduplication. mumpy array of probabilities of deduplicated tuples.
def compute_Ne Conpute_H__exactlye Mxacccllyyeppace
Computes information probability distribution exactly
Arga:
space: Tuple space (cartesian product)..
mu: probability distribution (1-D nampy array).
Returns: (fleat) matual information.
def (emppiaeddreeeedd___ mu_on on__oee ganns_1, ga Impleaente
(Algorithm
sampled_ tuples: nunpy arrey of tuples sempled from the distribution after deduplication and clustering. mm_on_ nample: numpy array of probabilities of the clusters. gamna_1: stabilization paraneter.
ganna_2: stabilization paraneter.
Recurns: (float) matual information.
def run experiment teap,
Rans experiment comparing exact mutual information estimation with Algorithm Plots resulte.
Arge:
n: number of variables in joint distribution.
tamp: tomperature Gibbs distribution (joint distribution). Higher temperature typically neans emaller MI. ax: pyplot axis object for plotting.
20

---

C Usage example of Algorithm 3
Algorithm is slight modification Algorithm that we use our experiments. We first explain Algorithm 3 via an example and then highlight the differences with Algorithm 2. In order to explain the implementation, we consider a running example with query z = ="What the capital of the UK?". Fl score as the similarity function s, similarity threshold
0.25, and number of samples k = 5.
Algorithm also takes the LLM distribution Q as input = Q.
Given the query, in step (2) of Algorithm 3, we sample & outputs from Q. Let's assume these samples X3 ="London", ", X2 "Loonon" ", X3 "London, UK", X1 "Pariss, and X5 = ="Berlin" In step (3), we construct a set of indices of unique elements. In our example, we would have (1,3, 4, 53. In step (4), we cluster responses and aggregate probabilities of each cluster. More precisely, if the Fl score of two responses is above 0.25, then they are in the same cluster. In our example, we have that (1 X3) > 0.666 0.25 and F1 (X1,, X4) FI X5) 0, and therefore cluster centers are 5 = {1, 4, For query z, let's assume LLM probabilities are
Q(xi x)) = 0.5, Q(2 xx) - 0.2, Q(x4| = 0.1, Q(xs ()) = 0.05,
Also assume conditional distributions are
Q(x Fi (zr, X1)) 0.6, Q(xa (1, Xi)) 0.15, Q(x, (i X1)) 0.05, Q(x: (2r X))) 0.04, ...
and so on (we have omitted writing Q- (I, X.)) and Q Q [r, Xs))). Then after step (4), the aggregated probabilities are
Q'(x 1z) -- 0.7, Q'(X+ = 0.1, Q'(xs x) = 0.05,
and aggregated conditional probabilities are
Q' (x, X))) 0.75, ((xX X1)) 0.05, Q'
0.04,
and (we have similar aggregations for Q'( (x, X,)) and Q' Fi Xs))). Next, in step (5), we construct empirical estimates. We will have that 7 0.85 and
(X1 I) 0.82, Q1(X+ 0.11, Q (2) 0.05, For estimated conditional distributions, we will have Z = 0.84, and
Q2(X, (I,, = 0.89,
0.06, Q2 (xxx 0.04,
and so on. The joint distribution ( 1)), the product of marginals @o (.. x). and the estimated mutual information I are trivially obtained by the equations in steps (5) and (6).
Next, we highlight the differences between Algorithm 2 (with the choice of 2) and Algorithm 3. The input distribution Algorithm 2 the pseudo-joint distribution Q. while the input to Algorithm is the LLM distribution Q. So in step (2) of Algorithm 2, each sample is tuple such as ("London" ", "Paris") "), while sample step (2) of Algorithm 3 is LLM output such as "London". Steps (3) and (4) of Algorithm 2 are similarly modified, and now the similarity function is defined over tuples.
21

---

D Related work
In this section we present an overview of the related literature.
D.1 Bayesian neural networks
In Bayesian framework, we can estimate the epistemic uncertainty by the uncertainty the posterior distribution (Neal, 2012; Gal, 2016; Wang and Holmes, 2024). Implementing Bayesian neural network however can be very challenging.
D.2 Iterative prompting
number of iterative prompting strategies are developed improve the factuality of LLMs (Chen et al., 2023; Krishna, 2023; Laban et al., 2024). The idea is to follow-up the LLM response with another question such as "Are you sure?". Krishna et (2024) show that such strategies might in fact degrade LLM truthfulness due to a pattern of apologetic responses, Krishna et al. (2024) propose improved iterative prompting strategies, where instead of asking the LLM re-think its response. the same question is posed again. They also propose strategies to collect more supporting facts and refine the final response accordingly. Li et al. (2024) propose an iterative prompting that instructs LLM to generate justifications for each answer before evaluating the correctness of the final answer. Different from these works, we assess hallucinations by measuring how LLM response changes with our iterative prompting scheme.
Perhaps the most related work ours is the parallel and independent work of Ahdritz al. (2024). Similar to us, Ahdritz et al. (2024) observe that in presence of high epistemic uncertainty, an LLM more likely to copy the information provided in its context. For a given query, Ahdritz al. (2024) propose considering top-k completions of the model, and then computing the entropy of the model conditioned on an iterative prompt composed the original query and each completion. The minimum of these entropies is considered as measure of the epistemic uncertainty. The method as it is, might fail on single-response queries where the model has low uncertainty. Nevertheless, we can design a two-stage process where we only consider completions that have probability higher than certain threshold in the first stage, and then compute the entropy of the model conditioned on an iterative prompt composed of the original query and each candidate completion in the second stage. By a proper tuning of the threshold of the first stage, we can potentially avoid mis-classification of low- unweertrrtantty ringee-rspoose queries. Tuning this threshold, however, would introduce extra complications. contrast, we propose a principled test using a mutual information score that is guaranteed to be lower bound on the KL-divergence between the LLM and the ground-truth. Further, we provide mechanistic explanations for why LLMs behave as described in the presence of high epistemic uncertainty.
D.3 Training models with pairs of responses
Wen et al. (2022); Osband et al. (2023); Johnson et al. (2024) show that we can decouple epistemic and aleatoric uncertainty if we train a model with paired observations.
We discuss the more recent work of Johnson et al. (2024) in more detail. The proposed approach first estimates model Pys,Ygl==(1) (z)) over pairs using a training dataset of the form "query, first observation, second observation".. At test time, for a prompt x and response y, Johnson et al. (2024) consider
( x) pv, (v x:) (prs v (y v, pvr (v) xx)
Py, v. (V1, U2 x) Pv, (y x) (y
as measure of epistemic uncertainty. Assume that an equivalence class & (that maps a prompt to the set of equivalent prompts) given, and let v(. (xx)) be a distribution (say, uniform) over class s (z). If the trained model is second order calibrated with respect to the equivalence class and the
22

---

distribution v, i.e.
py, (11 12)=
E
v(a' ((x))p(11 xx',
x'E((2)
PY, (111 V2 xx)
E
v(a'
((z))p(11 z')p(uz 2'),
r'E((2)
then it follows from definitions that in the class associated with
p(a' (())) (w I - plu x²))² = Σ u(a' (zz)))(z1z' (T)
Σ
x'E4(a)
The quantity on the right-hand side a measure of epistemic uncertainty. Notice that the equality states a coverage result, and is not point-wise Requiring the model to be second order calibrated is also a strong condition and ensuring it is highly non-trivial.
D.4 Epistemic neural nets
Ensemble methods are based on the classical idea of bootstrap for confidence estimation (Tibshirani and Efron, 1993), where multiple estimators for the regression function, each computed on a perturbed version the data (e.g., by drawing samples from the empirical distribution over the data), are combined.
The empirical distribution of the resulting estimates is then used to construct confidence intervals. While many of these methods can be interpreted as sample- based approximations to Bayesian methods, model-hyperpee hyperaaayperrrreetter selection (e.g.. scale of perturbations, learning) for ensemble methods is typically done using a validation on holdout data (a subset of the training data). Many recent papers have studied ensemble methods in the context of deep learning and reinforcement learning (Osband al., 2017a; Malinin and Gales, 2020). In the context of LLMs, the methods require training multiple language models, which is very expensive. Osband et al. (2023) introduces epistemic neural networks (epinets), which approximate ensemble methods by training single network with an artificially injected (controlled) source randomness. Rabanser et al. (2022) proposes to use intermediate model checkpoints quantify the uncertainty of the final model in its responses. While these approaches aim to mimic the bootstrap procedure during prediction, their validity is not justified by theoretical considerations, and hence remain heuristic approximations.
al., 2016; Lakshminarayanan
D.5 Hallucination detection using first-order methods
First-order methods consider variance in the response distribution as measure of hallucination (Ka- davath et al., 2022; Cole al., 2023; Manakul al., 2023; Lin al., 2023; Kuhn al., 2023; Wang et al., 2022; Jiang et al., 2024; Zhang et al., 2023; Zhao et al., 2024; Yadkori et al., 2024). A common limitation of these approaches is that they are only applicable to prompts where there exists a single correct response, they aim for detecting if one response (or multiple responses with the same meaning) dominant. On the other hand, when multiple responses are correct, there is an aleatoric uncertainty in the ground truth: If LLM correctly assigns negligiie scores multiple correct responses, most of these (if not all) will be declared as hallucination since, by design, only very few (typically at most one) responses can have scores higher than the threshold at the same time. Thus, hallucination detectors unaware alcatoric uncertainty will invalidate most of the correct answers.
Yona et al. (2024) design method that generates multiple responses, and then aggregates them into single response at a (typically higher) granularity level where no further uncertainty (contradiction) is left compared to the generated responses. Although not a strictly first order method, it does not differentiate between aleatoric and epistemic uncertainty.
D.5.1 Asking language models to quantify uncertainty verff-eeriiiattio))
Kadavath et al. (2022) propose to use LLM self-prompting to measure a model's uncertainty in its responses. More specifically, for given query, number of responses are generated, and then the model is queried the responses are correct. For this query, the arg-orbbbyliiyy "True" is returned measure of uncertainty. Related approaches are studied by Mielke et al. (2022).
23

---

D.6 Uncertainty estimation based on sensitivity to contexts
Kassner and Schütze (2020); Zhao et al. (2021) show that an LLM's responses can be influenced by irrelevant contexts, Longpre et al. (2021); Neeman et al. (2022) study two sources of knowledge: parametric knowledge stored the network weights, and contextual knowledge retrieved from external sources. They view reliance of the model on its parametric knowledge and ignoring relevant contextual information as hallucination. These works are mainly motivated by situations where the LLM's knowledge is outdated and it is instructed to use the (new) contextual information. Accordingly, they design strategies to prioritize contextual information over parametric knowledge, Longpre et al. (2021) also show that larger models are more likely to ignore in-context information in favor of in-weight information. They propose creating training data with modified contextual information so that the model learns to favor the contextual information. Neeman et al. (2022) propose to train model that predicts two answers: one based on parametric knowledge and one based on contextual information.
Similarly to Neeman et al. (2022), Li al. (2023) aims to design mechanism such that the model's behavior is influenced more by relevant context than by its parametric knowledge (controllability) while the model robust to irrelevant contexts (robustness). They improve controllability and robustness using finetuning.
Hou al. (2024) study an approach estimate model uncertainty due to ambiguity in a question. For a given question, their method generates multiple input clarification questions, and new question formed by augmenting the original question with each clarification question. The clarification questions are generated using an LLM with the aim of removing ambiguity in the question. This different than the problem we study as the model can be uncertain about the answer even the query itself has no ambiguity. For such queries, the method of Hou et al. (2024) might decide that no clarification needed, and therefore there no uncertainty.
D.7 Hallucination detection using internal states of LLMs
There are a number of papers that try to extract knowleegg/ruutiuuleess by inspecting hidden-layer activations of LLMs (Burns et al., 2023; Azaria and Mitchell, 2023; Chen al., 2024a,b; Yin et al., 2024). Such methods clearly require access to the LLM's ' internal states, which is not always possible, and severely limits the applicability these methods.
24

---

E
Omitted proofs
Proof of Theorem 5.5. In the following we will use abbreviations
Σ-Σ Σ
Σ
vir
where each n-tuple y belongs to V. Now,
-H(()) + Σ Mn) In
P(yl.....WWi vn)
=-1((²) + Σ Qu1 ,.. Un) In
II. Plys F1-1(11..... 91-1))
(using Definition 5.1)
=-((¹) + Σ Vn) In
(by the independence assumption)
II. P(m))
Focusing on the last (cross-entropy) term
Σ Ōun...... Mn) In II: P(m))
Own..... Σ In P(y))
(vi..... In P(y.)
1
Qui..... (Bh) In En Quv Vn)
Σ Von........ Mn) In
EI Quv...., Unh)
where in (a) we used the fact that entropy is no larger than cross-entropy. Thus,
Ōlvi..... Vn.) = I(@: .(.)))
@, 2 @iur..... Vn) In II. Ey Qun,,..,, Un)
4
25

---

Estimation of mutual information and missing mass problem
In this section, we discuss how to estimate the mutual information from finite sample, which may not cover the full distribution. To control the estimation error, we first introduce the concept of missing mass.
F.1 The missing mass problem
Let X' be countable set and suppose that Xi...., Xx μ Mi(2"") independently. In the following æ used as an element X rather than the query (as in Section 5). Then, the missing mass is defined as the random variable
Uk Σ (())
<(x) I(x & (X,,
TEA"
Here primarily interested in two questions: (i) how quickly Us approaches the expected missing mass EU,, where is not hard to see that
RU
Σ
- (())(1-(xx))*
2EA
and (ii) we are also interested in giving an estimate for EU₃, given μ and k. The first question is answered by the following theorem:
Theorem F.1 (Concentration of missing (Berend and Kontorovich, 2013)). For any t O, have an upper-tail bound
P (U > EU + t) S e
and moreover for universal constant 7.6821, we have an lower-tail bound
P (Uk < EU t) S -ak
Notably Ug exhibits sub-gaussian concentration (i.e. 1/Vk), which is surprisingly fast. As we will see next, the main bulk of the error incurred for missing a subset of the support is hidden in BUg.
In particular, when X' is finite with | N, Berend and Kontorovich (2012) showed that
* if N; en if N.
EUR <
In the countably infinite X, we cannot generally have a non-trivial bound on EUg only in terms of n. In fact, Berend and Kontorovich (2012) show a bound that depends on μ which is expected to be finite for rapidly decaying atoms. Interestingly, when the entropy of is bounded, one has the following result (Berend et al., 2017):
Theorem F.2. Let (p) S h < oc. For all n 2 1, we have EU 5
Note that these estimates are very pessimistic, and in reality we expect the expected missing mass to be significantly smaller. Since natural (and many artificial) languages follow Zipf distribution (Pi- antadosi, 2014), we expect that [[[x]] should be much smaller than in the above cases, since sampling from the tail of Zipf distribution is rare event. In Appendix F.4 we show the following:
Corollary F.3 (Expected missing mass of Zipf distribution). Consider distribution p(1) (-o, N) E [N], where a > and H(,, N) = Σm i- Then, for any B > 0,
EUUx] = o (2---=)-)))
Proof. The statement followss by combining Lemma F.9 and Proposition F.10.
26

---

F.2 Estimating mutual information from the partial support
Our goal is to estimate
[x(x)) 11
(w)) DKI(H,
E TEAN
u(x)ln In
by only having access to X,...., Xx μ.. Note that that the sample might cover only some part of the support of X and therefore are facing missing mass problem. In the following we consider estimator (7)) given by Algorithm 1.
In particular in Appendix F.3 we show the following
Theorem F4. Fix X S X². Fix y and suppose that 7/2 2 n(1 Z) + 7/. Then for any fixed ó E (0, 1), with probability at least 1 - 6,
(1 - [k) (1-xx) I</1,, 72)
11/72 In (et 2)) (2(23(())+
(2) +x)) I(m)
where
In (1)
6k = EU +
h
particular, Theorem F.4 implies the following:
Corollary F.S. Under conditions of Theorem E4,, there exists (ni,25) E (0, 1)2 such that
(1 (x-)x) ( + In EK I())
Note that, choosing any of the upper bounds on EU* discussed in Appendix F.I, we that Corollary F.5 implies asymptotic convergence as a sense
lim To (1i 78) < (p)) k+00
F.3
Proof of Theorem F.4
The proof will heavily rely the simple fact that
1,
if E (Xi,..., Xx):
1 [(x) =
(2)
0, otherwise.
Recalling that = [K] connection between UR and the quantities used in Algorithm 1:
X, * X, Vj <j i). this immediately implics the following
Proposition F.6. We have that
Σm(X)= [() -Ub
jES
Recall that the product distribution of is defined as
(x) = I p ......
1=1 3
27

---

Note that we use Ezh pl....) instead of ((zz) since these are not necessarily equal for some μ.. Now, using the definitions of In. fr, and po,
(11, 72)
0 Σ m((x))
In
(u(X,)
+ +71
17) In (1 (Xx) + -22)
Z
iES
u(xx) z + +1) In (x) + 722
Σ
(1 E(x)) u(z)
In
(by Eq. (2))
[((x) + + (x) +
(10 + -
(x)x) + 21
= 7 F
Σ
(1 - E(x)) 1(()
In
+ In
+ ū
Σ xE
((z)
In
(u(x) +
+
1 Σ (())
11 (1) + 71
In
Z
(z) + 7
Z
ulxx) +
z (sis)
xEx"
(
(1)
1
Σ #EX
(1-
((x) p(z) In
n (x) (x) + 71
Z
p (x) +22
(6n)
Now we control each of the terms individually. To control (i) we will first need the fact that q qin((q + m)/p) S q gll(g//) /p) + 71 for any q.p E [0, 1), 71 > O. Note that this follows since
q + 71 p
= q in 1+ 9 2)
+ 9 In (g)
in
S 71 + ql
(3)
using that In(1 a) S a for a we get
1. Getting back (i), and using the aforementioned inequality,
1 Σ
((x) + 71 (x) + +
(i)
u(z) In
xEX
Σ
p(z)ln In
m(x) + n (x)) +71
+ 1
Σ
p(x) In
[(x)+ + n 1 (1)))) +
Z
3EX
xEX"iE 1
((x) + n
1
1+11
((z)l11 In
+ Z
In
p(d" (2)
Z x
(x)x) +
711
[1(x) (1((x)
1+ 72) 1) m/2" | 10)
$ Z
Σ
|((x) In
+ +m
+ z
In
(by Equation (3))
zEλ
+ ž In (1+ + 71
) u(20 | .2)).
(DKI.(H, + +18871
= =
Furthermore,
Σ (()) In 41+ 1 1-2 "
z In (1+1) 2 7
(ii) Z
Next, observe that (iti) < lm(1/)). Finally, term (it) is controlled through the following fact shown at the end of this section:
Lemma E.7. Suppose that 71 > 0 while TO 2 71 + n11 -)). Then,
1
Σ
(1-((=)))(()
11 (x(x)) + 71)
7
70 (x)) + 72
ZEX
Putting everything together, we obtain
Ta( 72) S z
(DKL(H, u8) + 11817)
1 ) (M(27M) (2)) 1 In 1 m
(x( +1 11 2) + +ln11/2).
+ z
28

---

Finally, multiplying through by Z the entire inequality, and using the fact that 2 Lmm1122 $ Z. we get
z 7Im S (KL 1º) + 11/2 + In 1+ - (u(x* +1)1--2 2) +1-2
DKL(H, 2 + ph + In c (n(x² +1
To complete the proof we need to give a lower bound on Z. Note that Z = 1 - Ub by the definition of Z and Proposition F.6, and so Theorem F.1
P (1 BU > UK + th?
Using this concentration bound together with the choices of y (also setting Saupp 0 for the first inequality in the main statement) completes the proof Theorem F.4.
Proof of Lemma F.7. Observe that
n
2 (x) = ((x(xx)
II
Σ
Xt,n)
J=
1
{(x))
II
Σ
Xt,a)
j=1 x=,
1
(1- - -(()))
II
Σ
(1- -1- (1-E(2())(aa) = 2.),
1=1 2'EX"
(1 ((x))
II
Σ
(1
u(
Z
1=1
Now, using that fact that
E(d Iz I.,,,,,, "
Σ
S
1 - 7
arrive at
(x) N nn
1
(1 E(x))
II
u(a -ut,
j=1
1
(1 {(x))
II
Σ Mlcj.....,....... 2)
7m
1 n
(1 {(x)) (x)(z) n (1-2))
where to get (a) we used:
Proposition F88 For any P Pr E [0, 1] and 2 0, we have
a
(pr a) 2
p:)
n a
(=1
29

---

Proof. The statement following by lower-bounden the left-hand side by its linearization in (deriva- tive at 0), while realizing that it convex function of a.
The above gives us that
(x) + 1 (x) + 722
Σ
(1 - (1=(())))(())) In
Z
*EA"
1
Σ (1 {(x)))(x)) In
o (x) + 71
Z
J/2 (1- (1 (z) rll - 2)) + 72
m
and focusing on the case {(x)
(otherwise both sides are 0) the above equals to
(x) + 7
Σ p(x)ln In
ZR (11 (x) - n(1 - 2)) + 7/2
1 (2) + 71
S 7 #EX
Σ
u(x)ln
(100 (2) - m(1 Z))+ 7/2
1
(1(x)) (x) +
$ Z
Σ
u(z) In
n11 2) + 72
=EX²
0
by setting 2 + n(1 - 2).
F.4 Expected missing mass under Zipf distribution
We will rely machinery used by Ohannessian and Dahleh (2010) who established distribution- dependent bounds on the expected missing mass. As before let ya be supported on a countable set. The accrual function is defined
F(v) = Σ mi)
(v E [o, 1))
and moreover the accrual rates are defined as
In F(V)
In F(v) w= In
= lim inf
p = lim sup
In
We use the following result:
Lemma F99 (Ohannessian and Dahleh, 2010, Theorem 1), Let have lower and upper accrual rates
0 p S p cc. Then for every B 0 there exists ku such that for all l ko have:
E S k- (2-))
or equivalently, for every 3 > 0 we have that [U both 22kk (((k-(++))) and O(k O(k-(2())) Proposition F.10. Consider the distribution p(v) a (H N) for [N] where and H(a,N)= = -N i-a Then, 12"0 12(==1) as N + co.
Proof. The idea is to use Lemma F.9 to give upper bound on the missing mass. Therefore, need to establish lower bound on In F(v). For now, abbreviate
(v ((,
First note that for some 1 1 u N
i Eraz
> / (1+1)-a0
N
1
((1 (1++0 ((++u)2- - ()=-))-a).
a
30

---

On the other hand,
Σ < / (1+1) a-1 (1 NN
N
So,
In F(v) 2 In (1+ u)) (1)))) -In(1 - 1-Innn1i11 -N7-9)
2 In -1 NN)
and then
In (b) = Ω ((1 a) [n +1++)
(as - xc)
((1 a) In(2)
(11 - a) In([) (a)
a
+ a a-l In H (a, N))
=
In(v)
a
In(v)
Data-dependent estimate of the expected missing mass We perform an experiment designed to give data-dependent estimate of the expected missing mass EE[U]] for some specific datasets. Clearly, we cannot simply apply a concentration bound discussed in Appendix F.I since the complete support of the pseudo joint distribution derived from the LLM is unknown. To this end, we approximate with a finite support driven by the language model itself. In particular, given query we sample responses (at temperature 0.9) until their total probability mass reaches 0.95 we reach 1000 responses per query. In case of TriviaQA, we performed 1 123 queries in total. The mean and the median number of unique responses per query was eventually 118.3 and 22, respectively. case of the AmbigQA dataset, we performed 700 queries, while the mean and the median number of unique responses was 277 and 69, respectively.
At this point, denote the set of responses by X and let ÜR be the missing mass computed on X. Then, we have
In )
in( k
In In(
B
Up
Ür Up Ür + V
Ür +1 P(X)
which can be computed in practice. In Figure 6 we present our results in the form of empirical distributions of different quantities, where each observation corresponds to single query. We compute the bounds for TriviaQA and AmbigQA datasets (see Section 6 for details about these datasets). From Figure we can conclude that the expected missing mass for both datasets is very small: Both the missing mass computed on X and the resulting upper bound on E[U,] are concentrated close to while the cumulative probability of the approximate support X close to most of the time, showing that approximations meaningful.
31

---

F.l. saper Ixandar cly
wpe 2oard vi
ren
TriviaQA datasct
AmbigQA dataset
Figure 6: Distributions of bounds on the missing mass. The left figure for each dataset presents the empirical distribution of the upper bounds on the missing mass [.Uu). The middle figure presents the empirical distribution of Ug. the missing mass computed on finite support approximation (where the support is obtained by taking samples from the LLM until a cumulative probability 95% or 1000 samples are achieved). The right graph shows the empirical distribution of P(X), the cumulative probabilities of all responses generated by the language model. For each figure, one observation (sample) corresponds to a single query. The black curves represent the corresponding empirical cumulative distribution functions for the upper bounds on EU₃ and for Ük. and the empirical survival function (1 minus the empirical distribution function) for the distribution of P(X).
32

---

G Additional experiments details
Comparison of responses and computing the output distributions. We use the Fl score thresh- olded at 0.25 to decide if two text sequences match. When multiple responses are sampled, we approximate the output distribution of an LLM in a semantically meaningful way by collapsing matching responses into single response: we sample k 10 responses at temperature 0.9 for each query, and after eliminating repetitions, all those that match (according to the F1 score) are considered identical and their probabilities are aggregated. We only consider queries for which the greedy (temperature zero) and at least one of the random responses are shorter than 20 characters. This is because the Fl score (as a match function) and prg-pobbabilities (as a measure of uncertainty) are less reliable for longer sequences. After this filtering, we are left with 38870 datapoints for TriviaQA, 5315 datapoints for AmbigQA, and 3296 datapoints for WordNet.
As shown in prior works (e.g. Kuhn et al. (2023); Yadkori et al. (2024)), we can use LLM self- prompting to obtain more reliable text comparisons specially for longer outputs. Such an approach however is computationally much more expensive.
Baselines. We consider abstention policies based on four scoring methods. The first three are as follows: (i) the probability of the greedy response (denoted by TO); (ii) the semantic-entropy method of Kuhn et al. (2023) whose score is the entropy of k = 10 generated samples (denoted by S.E.). To calculate entropy. we first aggregate probabilities of equivalent responses and normalize the probabilities so that they sum to I (as described above); and (iii) our proposed mutual information score as defined in Section 5 (and denoted by M.I.) with the choices of k 10. n = 2, and n 722 = 0 (the latter choice approximates the case that the number of potential responses can be very large in which case the theoretical choice of " and 7/2 would be very small). To calculate the mutual information, as shown in Algorithm 3 (given in Appendix A), we first generate k = 10 random samples. Then for any response Y. we calculate the probability of all generated responses given the prompt Fi (ax Y). We construct estimates QYY) and Q(Y'lY) by aggregating probabilities of equivalent responses, and normalizing the probabilities so that they sum to 1.
The calculation of the mutual information is slightly different than the algorithms presented in Algorithm 1 and Algorithm 2 and takes advantage of the available lig-likelihood function in LLMs. Notice that the input μ in Algorithm is the LLM's output distribution Q as opposed to being the pscudo joint distribution Q in Algorithm 1. Another difference is that the similarity function now takes two texts input (as opposed taking two n-dimensional arrays of texts as inputs in Algorithm 2). As explained earlier, we use the Fl score as the similarity function and we use 0.25 the similarity threshold.
Each baseline also has a default choice which is taken when the relevant score is above a threshold, and hence the method does not abstain. For TO, the default choice is the greedy (temperature zero) response. For S.E., the default choice is the response with the highest (aggregate) probability among the generated random responses. For the M.I. method, the default choice is the sampled response with the highest probability according to the marginalized pseudo joint distribution.
We also consider version of the self- serfiieriiiattion method of Kadavath et al. (2022) (denoted by S. that, for a query x. first finds Y,, the element with the largest (aggregated) probability (which is the default choice of S.E. method), and then calculates the probability of token "True" (normalized for the two tokens "True" " and " "False") ") for the following query: "Consider the following question: Q: x. One unswer to question Q is Y1. Is the above answer to question Q correct? Answer True or False. A:". The default choice of this baseline the same as the default choice of the S.E. method. By this design, our intention is to construct a score that (unlike the first-order scores? we consider) is not sensitive to the size of the label set.
'In this context, the F1 score is calculated based on token inclusion (Joshi et al., 2017; Devlin et al., 2019): for two sequences a (aI,..., a,,) and b (ba..... bm). defining p = n bl/n and r= Ja n bl/m (where Janb] is the size of the intersection of and b, in which for repetitions an element y, we consider the minimum number of repetitions in a and b, i.e., min.e [o.b] ( : cs = y in calculating the size of the intersection) we define F1 = 2pr ((p + r). Relating to the standard definition of the Fl score, p and r play the role of precision and recall, respectively, if is thought of prediction of b.
'The scores l'O and S.E. are first order because they only consider the marginal distribution of a single response, unlike our uncertainty score which is based on MI estimation by considering (pseudo) joint distributions over multiple responses.
33

---

H Experiments with Gemini 1.0 Nano-1 model
In order show that our findings are not limited models of certain size, we conducted experiments with much smaller Gemini Nano model with 2B parameters. The results are shown in Figures 7 and
E25
2.40
2.0
3.30
Rocal
Recall
(a) TriviaQA
(b) AmbigQA
(c) TriviaQA+
(d) AmbigQA WordNet
Figure 7: The same figure as Figure 4, but for much smaller Gemini Nano model with 2B parameters. PR-Curve for the baseline and the proposed methods on various datasets. On TriviaQA and AmbigQA datasets, S.E. outperforms M.I. when the recall is low, but they perform similarly the recall increases (note that the large-looking difference on AmbigQA is actually at most 3%-poinss throughout, and also about most the same for TriviaQA when the recall is above 0.4). For larger recalls, the two methods perform similarly, with the S.E. method somewhat outperforming our M.I. method. Note that the performance of the Nano model is quite weak, especially compared to the Gemini Pro results presented the paper. On TriviaQA +orddNe and AmbigQA+ high entropy multi-label queries, M.I. outperforms S.E. baseline. Similarly to the experiments with Gemini Pro, the precision increases as the recall grows (above around 0.5), as the previously rejected WordNet data is accepted more and more.
datasets with the additional
1.0
M..
1.0
MJ.
0.8
S.E.
0.4
0.8
S.E.
0.4
3.66
003
20.6
E0.
0.4
0.2
02
0.0
03 6305077551 1.315711
0.305066300 1.515778
0.0
01 03 0500041111111
L110355 C.7 2.709111101 391113151715
Entrory
Entrayy
Entrayy
(a) WttideA+WordNett
(b) TordeeQAAWordNet
(c) AmmiigQA=oorNNe
(d) Wordeee
Figure 8: Recall and error rates (percentage of mistakes when not abstaining) for TriviaQA and AmbigQA as a function of the entropy of model responses. The methods are calibrated error rate 0.07 (as before, this error rate is computed by considering abstention as no error, i.e., error rate crrors/predictions abstentions)). based on 50 random samples. One can see that when the response entropy is small (the histogram is created with bins of withs 0.2), M.I. and S.E. have similar error and recall rates. On the other hand, for larger entropies, S.E. rejects all samples, while M.I. accepts some of them with reasonably small error rate. This is again very similar to our findings for the Gemini Pro model.
34

---

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: Main claims made in the abstract and introduction accurately reflect the paper's scope, contributions, claims, and results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in the introduction.
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 separate "Limitations" section in 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 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 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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: [Yes]
35

---

For each theoretical result, the paper provides the full set of assumptions and proofs. Some proofs are included in appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs 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 to provide short proof sketch 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, we disclose all the required information to reproduce our results in experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary 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 is often one good way 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 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 (e.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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. 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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
36

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: All the data is publicly available. Code is currently not available: organiza- tional policy forbids immediate publication of the source code without an internal review process. As the review process is long, it is unlikely that NeurlPS deadline could be met if we were to undergo a code review process.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
wwwssnnoooo onoolioPooooooo olicyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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: / //ippscc/ppuui htt//uulic//ae wwt.cc/ggg/////eeee SoodeSubmissiooneee
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 as much information as possible supplemental material (appended to paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
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:
All details are included experimental section.
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 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: Confidence intervals are present in all relevant plots (with details therein).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
37

---

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 or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, 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 out of range (e.g. negative error rates).
If error bars are reported in tables or 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 execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This is provided in the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or 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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make 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 attps://neurs wwweeurip..cpppuuuuu cttppblic///aeccccccccccc c/Ethi sesCuideeinnss!
Answer: [Yes]
Justification:
The authors followed the principles outlined NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not 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., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Ye]]
Justification: Broader impact statement is made at the beginning of the appendix.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
38

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 not tied to particular applications, let alone deployments. However, if there is 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 out 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 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of 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: This work uses existing and publicly-available language models, all the standard safeguards relevant models apply.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a 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 to 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 is 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 correctly reference the datasets, the only external assets used in this paper.
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.
39

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasttssss 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 it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce new assets in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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:
Our study does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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: The research does involve any human subjects or approval from IRB or equivalent.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor 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.
40

---

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.
41


Reviews:
[{"review_id": "ml1UvvWVoh", "reviewer": "Reviewer_DRXq", "summary": "This paper proposes an iterative prompt-based approach to uncertainty estimation. They make a model generate multiple answers, and estimate the probability of each, estimating uncertainty for each. They argue this method easily adapts to aleatoric and epistemic uncertainty, and can be applied to multiple choice question answering. They provide a mathematical framework to support their approach, arguing that a simple metric, Mutual Information between responses, can be a lower bound for uncertainty.", "questions": "See weaknesses", "limitations": "Limitations are adressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The epistemic/aleatoric approach to understanding uncertainty is a clear theoretic framework that is helpful in the MQA stage. This is highly appliable as threshodling methodology is provided, and complete examples are provided. Interpretability notions are used to explain this behaviour, giving an insight on why this happens, and not only how.", "weaknesses": "1) Assumption 4.1 is, to my understanding, that the correct answer will have a probability independently of \"any\" context. Under this assumption uncertainty is observed when the model relies more on context. Later math is based on this assumption, which seems somewhat task specific.While this works in the controlled question answering setup, context dependence holds a lot more information(ex:linguistic dependencies, uncertainty regarding user intent...). This could make the resulting uncertainty metric reduce less useful in deployment to general usage. I think discussion of limitation to assumption 4.1 should be more throughly discussed.\n(It should be noted that 4.1/theorem 4.5 very clearly discusses the limitations of applying MI to infinite language)\n\n2) Prompt based methods have been shown to be very model reliant, size reliant and tuning reliant. From a reproductibility perspective, it is unclear if results on Gemini will reproduce on different architectures, or smaller models. Is this behaviour a skill that emerges at a model size? requires specific tuning? or is it inherent to language modelling?\nIn the same line of questioning, it is unclear to me how the prompt was chosen, and if this selection procedure needs to be repeated on a new model. If this probabilistic approach is universal to Language modeling? If so this would truly be an interesting step forward from previous works. Otherwise it is a limitation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses 1:** Although the assumption is stated in this form for simplicity, the assumption in our theory is only for a very specific type of prompt we consider which still seeks answer to the original question $x$, and hence the ground-truth response should not change, and we also only apply it to specific contexts $Y_i$, i.e. those that could potentially be generated by the language as a response to the query. Thus, we do not really require independence for all contexts. Given this, we believe the assumption is not strong, and is intuitively stating that in the face of distractor responses, the response of the ground-truth language model should not change. Having said this, the formulation is indeed prone to adversarial attacks (and hence not perfect), e.g., if $Y_1=$\"Answer1. However, we are interested in question $x_2$ instead of $x$\", the new prompt would be \n\n\"Consider the following question: Q: $x$. One answer to question Q is Answer1. However, we are interested in question $x_2$ instead of $x$. Provide an answer to the following question: Q: $x$\"\n\nwhich could be misleading. However, we could change the assumption to only correspond to sequences $Y_i$ which are generated by a reasonable language model, and we will change it to restrict the family of $Y$'s (depending on $x$).\n\n\n**Weaknesses 2:** We believe this probabilistic approach is universal to language modeling. We have made similar observations on smaller models and with different architectures. We are in the process of delivering more results and will provide them during the discussion.\n\nWe made almost no prompt engineering. The prompt used in the experiments was the second prompt tried (and not much different than the first try, which also gave very similar results).", "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": "kXnIkw7v57", "reviewer": "Reviewer_zm61", "summary": "The paper considers both epistemic and aleatoric uncertainties and proposes a novel method to decouple them. This method employs iterative prompting based on its previous responses. Experiments demonstrate that the proposed approach effectively detects cases where only epistemic uncertainty is large for multi-label questions.", "questions": "N/A", "limitations": "The discussion on the limitations of this paper is insufficient.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Important problems: Aleatoric uncertainty is crucial for handling multi-label queries in practical applications.\n2. Comprehensive theoretical analysis.\n3. Demonstrates good performance in effectively dealing with multi-label queries by decoupling epistemic and aleatoric uncertainty.", "weaknesses": "1. **Limited application scope**: While I appreciate the method and performance of decoupling epistemic and aleatoric uncertainty for multi-label queries, it falls short in estimating uncertainty for single-label queries (Fig.5ab).\n\n2. **Overlooked over-confidence issues**: The paper overlooks the problem of over-confidence, where the model produces low entropy among multiple responses despite providing incorrect answers.\n\n3. **Limited dataset selection**: The paper filters the WordNet dataset, retaining only queries with entropy higher than 0.7. It claims that “both the proposed method and the semantic entropy method rarely make mistakes on this dataset, and therefore we are not adding any mistakes to either method.” This indicates that the selected dataset is relatively simple. However, as discussed in weakness 2, low entropy responses can still contain errors in more challenging datasets.\n\n4. **Limited model selection**: The paper does not validate the effectiveness of the method across different types of models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Limited application scope:** on single-label queries, we should not expect to perform better than a competitive first-order method (such as S.E.), which is specifically designed for such queries. Please note that Fig.5ab in fact shows that our method performs essentially as well as the S.E. method in estimating uncertainty in single-label queries.\n\n**Overlooked over-confidence issues:** this is an important open question, and a solution will most likely require additional novel ideas. \n\n**Limited dataset selection:** given that TriviaQA and AmbigQA already contain challenging queries with low-entropy responses, we wanted to add queries with high entropy responses to demonstrate the limitations of first-order methods. \n\n**Limited model selection:** We have made similar observations on smaller models and with different architectures. We are in the process of delivering more results and will provide them during the discussion.", "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": "qGKvBRFqfy", "reviewer": "Reviewer_DdzV", "summary": "In the paper, the authors address the challenge of distinguishing between epistemic and aleatoric uncertainty in large language models (LLMs). They develop methods to decouple these uncertainties, which is crucial for handling queries with multiple valid responses. Their approach involves iterative prompting of the LLM to generate responses and measuring the sensitivity of new responses to previous ones. This helps in identifying cases where epistemic uncertainty is high, indicating potential hallucinations by the model. They propose an information-theoretic metric to quantify epistemic uncertainty and derive a computable lower bound for this metric, which is validated through experiments on datasets like TriviaQA and AmbigQA.", "questions": "Section 2:\n1.  \"Moreover, consider a family of conditional distributions P ... \", if P is a set of distributions, why \\mu is defined as a function? what is the meaning of \\mu(x|x')?\n\n2. what is \"ground-truth conditional probability distribution\"? do you mean p(Y|X) where (X, Y) are data and label?\n\n3. where the \"possible responses Y1, . . . , Yt\" come from? Are they sampled from LLM Q with different decoding strategy?\n\n4. what is the physical meaning of Z_i and also where does the second subscript i come from in (Z_i)_i?\n\nSince the explanation of Z_i, \\mu are missing, it is hard for the reviewer to identify how the \"information-theoretical notations\" contributes to this paper.\n\nSection 3:\n\n5. \"To obtain conditional normalized probabilities, we consider the probabilities of the two responses, and normalize them so that they add to \" it is unclear to the reviewer why this normalization is applied and how this is conducted. Please describe this procedure formally and justify the reason why conduct this.\n\n6. The x-axis and y-axis labels are missing in Fig 1, Fig. 2, and Fig. 3. \n\n7. How the proposed iterative prompting strategy (and its so-called \"Conditional normalized probability\") connected to epistemic uncertainty is missing. Although pieces of descriptions are mentioned in the Introduction, they are ambiguous and informal. Conventional definition of epistemic uncertainty is usually the model approximation error, e.g., p(\\theta|D) where D is the training data. However, the new constructed input, i.e., the iterative prompt, is assumed to be significantly different from the D and how this is capable of quantify epistemic uncertainty is confusing for the reviewer.", "limitations": "No, the conclusion and limitations (and social impacts) are missing.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "1. The topic is important and interesting. \n2. The proposed iterative prompting strategy is practical and can be implemented easily.", "weaknesses": "1. The writing of this paper is poor and informal. The reviewer feels hard to understand the exact insights and the principles behind the paper. Please refer to Questions for a few of these confusions. The reviewer strongly recommends polishing the presentation carefully, especially those notations and definitions. \n2. The evaluation protocol is unclear to the reviewer. In Fig. 6, what is the meaning of the entropy in the x-axis? Also, some LLM UQ baselines are missing such as [1]\n\nReference:\n\n[1] Lin, Zhen, Shubhendu Trivedi, and Jimeng Sun. \"Generating with confidence: Uncertainty quantification for black-box large language models.\" arXiv preprint arXiv:2305.19187 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Definition of epistemic uncertainty, iterative prompting, and connection between them\n\n* _**Q:** How the proposed iterative prompting strategy connected to\n  epistemic uncertainty is missing._\n* **A:** Note that the definition of epistemic uncertainty is given in\n  Definition 4.4. It is a KL-divergence between pseudo-joint\n  distribution (Def. 4.2) constructed by iteratively prompting LLM and a\n  pseudo-joint distribution of ground truth --- the formal connection\n  is introduced and discussed in detail in Section 4.  The main idea\n  of the paper is a lower bound on this quantity (Theorem 4.5) which\n  can be computed by only having access to LLM and iterative prompting\n  (constructing pseudo-joint distribution).\n\n* _**Q:** Conventional definition of epistemic uncertainty is usually\n  the model approximation error, e.g., $p(\\theta|D)$ where $D$ is the\n  training data. However, the new constructed input, i.e., the\n  iterative prompt, is assumed to be significantly different from the\n  $D$ and how this is capable of quantify epistemic uncertainty is\n  confusing for the reviewer._\n* **A:** Note that $p(\\theta | D)$ as you mention, is typically\nencountered in Bayesian literature, whereas we look at the problem\nfrom the frequentist viewpoint.  In our setting $\\theta$ is not a\nrandom variable, but fixed throughout.  Note also that our metric of\nepistemic uncertainty and a theorem that suggests how to measure it\ndo not make any assumptions on the training data. That said, we\nconsider it as an advantage over methods where assumption on $D$ is\nrequired.\n\n* _**Q:** where the \"possible responses $Y_1, \\ldots , Y_t$\" come from? Are\n  they sampled from LLM Q with different decoding strategy?_\n* **A:** Responses $Y_1, \\ldots, Y_t$ are generated iteratively given\n  question $x$ exactly as described in the prompt in line 114. For\n  example, given question $x$, the first answer is $Y_1$; then given\n  $x, Y_1$, the second answer is $Y_2$; then we obtain $Y_3$ given $x,\n  Y_1, Y_2$, and so on. Kindly note that this is explained in Remark 4.3.\n\n## Unclear definitions and notation\n\n* _**Q:** \"Moreover, consider a family of conditional distributions\n  $\\mathcal{P}$ ... \", if $\\mathcal{P}$ is a set of distributions, why\n  $\\mu$ is defined as a function? what is the meaning of $\\mu(x|x')$?_\n* **A:** Here $\\mu$ is indeed a discrete conditional probability\n  distribution, which is a function defined on $\\mathcal{X}$ (the\n  space of finite text sequences) and that sums up to one. In other\n  words, $\\mathcal{P}$ is a set of discrete distributions, one for $x'\n  \\in \\mathcal{X}$. We will make this clearer in the updated version.\n\n* _**Q:** what is \"ground-truth conditional probability distribution\"?\n  do you mean $p(Y|X)$ where $(X, Y)$ are data and label?_\n* **A:** In the context of our paper $X$ is a query, while $Y$ is a\nresponse, hence $p$ is a stochastic model which captures relationships\nbetween queries and answers. In other words, it is a probabilistic\nmodel of language that we assume.  In general, in supervised learning,\n$(X, Y)$ are typically understood as input and label.\n\n* **Q:** what is the physical meaning of $Z_i$ and also where does the\n  second subscript $i$ come from in $(Z_i)_i$ ?\n* **A:** $Z_1, Z_2, \\ldots$ is a sequence of abstract random variables\n  with values in some measurable set $\\mathcal{Z}$. These are simply\n  used to introduce some general definitions and avoid the use of $X$\n  and $Y$ which are reserved for questions and answers.  A shorthand\n  notation $(Z_i)_i$ is commonly used for describing tuples,\n  i.e. $(Z_i)_i = (Z_1, \\ldots, Z_n)$.\n\n* _**Q:** Section 3: \"To obtain conditional normalized probabilities,\n  we consider the probabilities of the two responses, and normalize\n  them so that they add to one.\" it is unclear to the reviewer why this\n  normalization is applied_\n* **A:** We apply normalization to have easy comparison between\nexperiments with different number of repetitions of incorrect\nresponse.  In this way, it is easy to see that the factually correct\nanswer decreases from $1$ to smaller probability as the number of\nrepetitions increase.  Without normalization we would need to compare\nlog-likelihoods, in which case the change would not be as obvious.\n\n## Questions about evaluation protocol\n\n* _**Q:** In Fig. 6, what is the meaning of the entropy in the x-axis?_\n* **A:** In Fig. 6, the entropy on the x-axis represents the\nempirical entropy of the distribution of multiple answers obtained for\na single query. We measure this for all queries and construct a\nhistogram, by binning entropy values. This illustrates the frequency\ndistribution of entropy across different queries, thereby providing\ninsights into the variability and consistency of the responses.\nSpecifically, empirical entropy measures the uncertainty or randomness\nin the distribution of these answers. Higher entropy values indicate\ngreater diversity and less predictability among the answers, while\nlower entropy values suggest more uniform and predictable responses.\n\n* _**Comment:** Some LLM UQ baselines are missing such as (Zhen et al. 2023)._\n* **A:** Thank you for pointing this out, we will consider this\n  baselines in the updated version.", "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": "GjoMAAYhIS", "reviewer": "Reviewer_1raE", "summary": "This paper is about uncertainty quantification in LLMs, specifically illustrating some results based on an assumption involving independence of the distribution for a correct output for a question given some “iterative prompting”. The proposed information-theoretic measure is intended to help measure epistemic uncertainty of LLM output.", "questions": "Some comments and questions follow:\n\nThe title of the paper is too broad and could pretty much refer to any paper about uncertainty quantification in LLMs; I strongly recommend something more descriptive. One possibility is to use a sub-title such as “Iterative Prompting for Estimating Epistemic Uncertainty”.\n\nI don’t understand why recent references have been used to cite epistemic vs. aleatoric uncertainty; these are older ideas. Either cite something classic or remove them.\n\nThe paragraph starting on line 47 makes some factual errors. The prior work does not assume there is a single correct response. For instance, in the Kuhn et al. paper, all answers that meet a threshold on the Rouge-L score (as compared to some ground truth) are deemed to be correct. I suggest rewriting this paragraph.\n\nThe “contributions” part on page 2 is quite unclear, and some things only become clearer later. The authors should write this in plain language that is understandable at a high level, without getting into details. For instance, what is the “ground truth language”?  \n\nHallucinations are mentioned in the paper but never clearly defined or cited. I believe the notion here is different from that in other work.\n\nI recommend using title case for section headers.\n\nFig. 1 is really hard to read and has inconsistent y-scales across panels. Also, I see a drop in the probability in some panels. How is this consistent with what is mentioned in the text? Is it because it does not go to 0 quicker? Please clarify.\n\nI may be mistaken but I feel there may be something wrong with how Assumption 4.1 is written. It seems like Y_t must be a ground truth answer to the original question x (without the additional information in the prompt) but Y_1, through Y_t-1 can be any text. Is this true? The \n\nHow do we know that Assumption 4.1 is true? Is this based on the discussion in the preceding section? Does this depend on how long the ground truth response Y_t is? \n\nIs F_0(x) defined? Perhaps this is the case where the prompt is: “Provide an answer to the following question: Q: x. A:”\n\nI had a hard time figuring out what to make of the experiments. What is the main takeaway? When does the proposed approach perform better than baselines? There are other potential approaches (verbal and non-verbal, such as consistency-based approaches) that could be used as baselines. The P-R curves shown should mention coverage and accuracy; these are also known as accuracy-rejection curves.", "limitations": "Limitations do not seem to be discussed very much.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think the paper has several interesting ideas, and one of the strengths is the attempt to formalize epistemic uncertainty using information theoretic ideas. There is novelty in the approach, in my view, as well as potential for these ideas to be useful in practice.", "weaknesses": "I found it generally hard to understand various sections of the paper, even though I am generally familiar with literature in this space. I think the writing is somewhat unclear in a few places. For instance, what is the scope of the work? Exactly what kinds of tasks are the proposed methods suitable for? Why should the key assumption hold and why should one trust it from some anecdotal examples? \n\nSeveral statements do not seem fully explained or justified; I will mention a few later in my detailed comments. I’m also not sure that the paper does enough empirically to highlight the key ideas – if I’m mistaken, the authors should correct me. So, while I find the work interesting and potentially impactful, I feel there is room for improvement, particularly around the exposition. I am willing to revise my suggestion for the paper based on the discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank reviewer for many insightful suggestions, we will revise the\ntitle, references, improve section 2.\n\n## Scope, assumptions, and definitions\n\n* **Q:** What is the scope of the work? Exactly what kinds of\ntasks are the proposed methods suitable for?\n* **A:** Our main motivation was a question-answering systems where we\n  want to be able to detect whether answers to multiple-response\n  questions might be incorrect. Then, such systems can\n  abstain based on a high uncertainty score (Def. 4.4) after some calibration (see lines 219-229). Note that our proposed method is not suitable for\n  certification when the answer (or action) is correct with high\n  confidence.\n\n* **Q:** How do we know that Assumption 4.1 is true? Is this based on\n  the discussion in the preceding section? Does this depend on how\n  long the ground truth response $Y_t$ is?\n* **A:** The assumption is based on a common sense which we exemplify\nin this way: consider a query with single or multiple answers that\ncould be encountered in the language (literature, internet, and other\ntext sources). We assume that these answers are independent\n(i.e. occurrence of the answer in one textbook does not depend on\nthe occurrence in another source). In fact, we will only care about\nsuch queries. This should be independent from how long $Y_t$ is.\n\n* **Q:** I feel there may be something wrong with how Assumption 4.1\nis written. It seems like $Y_t$ must be a ground truth answer to the\noriginal question $x$ (without the additional information in the prompt)\nbut $Y_1$, through $Y_{t-1}$ can be any text. Is this true?\n* **A:** Thanks for pointing this out. Indeed, $Y_1, \\ldots, Y_{t-1}$\n  are understood as a collection of random variables distributed\n  according to the ground truth (i.e. thet not arbitrary texts).\n  \n* **Q:** Is $F_0(x)$ defined? Perhaps this is the case where the prompt\n  is: “Provide an answer to the following question: Q: x. A:”\n* **A:** Yes, you're correct. Thanks, we will define this.\n\n* **Comment:** Hallucinations are mentioned in the paper but never\n  clearly defined or cited. I believe the notion here is different\n  from that in other work.\n* **A:** Thanks for pointing out this oversight. In the context of our\n\twork a hallucination is a positive real quantity and it is\n\tcaptured by the KL divergence between pseudo-joint distributions\n\tof LLM and the ground-truth distribution respectively (Definition\n\t4.4).\n\n* **Q:** What is a ground-truth language?\n* **A:** In the context of our paper $X$ is a query, while $Y$ is a\nresponse, and ground truth $p$ is a stochastic model which captures\nrelationships between queries and answers. In other words, it is a\nprobabilistic model of language that we assume.\n  \n## Literature and Experiments \n\n* **Q:** Fig. 1 is really hard to read and has inconsistent y-scales\n  across panels. Also, I see a drop in the probability in some\n  panels. How is this consistent with what is mentioned in the text?\n  Is it because it does not go to 0 quicker? Please clarify.\n* **A:** The drop in probability is the behaviour we wanted to\n  pinpoint, that is, as the number of repetitions of incorrect answer\n  increases, the normalized probability drops. Indeed, it is\n  interesting that this varies for different prompts (sometimes drop\n  happens much faster). We suspect that this depends on the amount of\n  training data provided to the model, however it is hard to make\n  conclusions at this point and we leave this question as a future\n  research direction.\n\n* **Comment:** The paragraph starting on line 47 makes some factual\nerrors. [...]  in the Kuhn et al. paper, all answers that meet a\nthreshold on the Rouge-L score [...] are deemed to be correct.\n* **A:** Thanks for spotting this mistake, we will rewrite this\naccordingly. We meant this to be all semantically equivalent\nresponses.\n\n* **Q:** I had a hard time figuring out what to make of the\n  experiments. What is the main takeaway? When does the proposed\n  approach perform better than baselines? There are other potential\n  approaches (verbal and non-verbal, such as consistency-based\n  approaches) that could be used as baselines. The P-R curves shown\n  should mention coverage and accuracy; these are also known as\n  accuracy-rejection curves.\n* **A:** Thanks for pointing out alternative baselines and\n  metrics. The goal of our experiments is to validate that a lower\n  bound on the uncertainty metric (theorem 4.5) indeed captured\n  incorrect answers in multiple-answer questions. We chose semantic\n  entropy as a reference since it is arguably a conceptually closest\n  baseline (since our lower bound is a mutual infromation of the\n  pseudo-joint distribution).", "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 insightful comments. We are in the process of delivering more results with different LLM architectures and sizes, and we aim to provide the results during the discussion. We have already observed that small LLM models behave similarly. 

Please find our responses to other specific points below.

Meta-review: The reviewers are split about this submission (3, 5, 6, 7).  While some reviewers have noted its significance, theoretical backing, intuitive algorithmic setup, and solid empirical results on the evaluated settings, one reviewer is strongly opposed to acceptance due to issues with clarity and formalization.  While I tend to agree that the writing is perhaps more technically advanced than that of a "regular" LLM paper, I have to disagree that it is inaccessible.

For this reason, I am leaning towards acceptance.
Decision: Accept (poster)