To Believe or Not to Believe Your LLM: IterativePrompting for Estimating Epistemic Uncertainty

Authors: yasin abbasi yadkori
ilja  kuzborskij
andrás  györgy
csaba  szepesvári
george  washington
abraham  lincoln
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:34:33

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.

Main paper: 
 introduction: 
 Language models too occasionally suffer from hallucinations, or responses with low truthfulness, that do not match our own common or textbook knowledge (Bubeck et al., 2023; Gemini Team, Google, 2023) . At the same time, since LLMs work by modeling a probability distribution over texts, it is natural to 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 et al., 2022; Osband et al., 2023; Johnson et al., 2024) . Epistemic uncertainty arises from the lack of knowledge about the ground truth (e.g., facts or grammar in the language), stemming from various reasons such as insufficient amount of training data or model capacity. Aleatoric uncertainty comes from irreducible randomness in the prediction problem, such as multiple valid answers to the same query. Hence, truthfulness can be directly analyzed via looking at the epistemic uncertainty of a model in the sense that when the epistemic uncertainty is low, the model predictions must be close to the ground truth.Rigorously identifying when (either) uncertainty is small1 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 (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 (e.g. label) as they aim for detecting if one response is dominant (or multiple responses with the same meaning), that is, if 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 we address the above problem directly, and design methods to decouple 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. 2As a 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 a 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 is asked to provide a response given a query, then to provide another response given the query and the first response, then a third one given the query and the first two responses, an so on. This is in contrast to some of 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 a 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, we can force an 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-theoretic metric of epistemic uncertainty in LLMs (Section 5), which quantifies the gap between the LLM-derived 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-derived joint distribution over responses, and propose a finite-sample estimator for it.We prove that this finite-sample MI estimator sometimes suffers only a 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 on 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 a more advanced baseline which is 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-based 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 a 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 is likely to be copied from the prompt. 
preliminaries: 
 Conditional distributions and prompting. Let X be the space of finite text sequences, that is X ⊂ Σ * where Σ is a finite alphabet (andΣ * = ∞ n=1 Σ n ). Moreover, consider a family of conditional distributions P = {µ : X → [0, 1] | x∈X µ(x | x ) = 1 ∀x ∈ X }.In the following, we let P ∈ P be the ground-truth conditional probability distribution over text sequences (responses) given a prompt, and we let Q ∈ P be the learned language model. Given a fixed query x ∈ X and possible responses Y 1 , . . . , Y t , we define a family of prompts F = {F t : X → X | t ∈ N}, such that F t (x, Y 1 , . . . , Y t ) is defined as: Consider the following question:Q: x One answer to question Q is Y 1 . Another answer to question Q is Y 2 .[. . .] Another answer to question Q is Y t .Provide an answer to the following question: Q: x. A:Information-theoretic notions. Let µ, µ be distributions supported on set Z = Z 1 × • • • × Z n where (Z i ) i is a collection of countable sets. The entropy of a distribution µ is defined as H(µ) = z∈Z µ(z) ln(1/µ(z)). 3 If µ, µ are such that µ (z) = 0 only if µ(z) = 0, we have a Kullback- Leibler divergence between them defined as D KL (µ, µ ) = z∈Z µ(z) ln(µ(z)/µ (z)).For any z ∈ Z, we denote z \i = (z 1 , . . . , z i-1 , z i+1 , . . . , z n ), and the marginal of the ith coordinate of µ is given by µ i (z) = z \i ∈Z n-1 µ(z). The product distribution of the marginals of µ is given by µ ⊗ (z) = n i=1 µ i (z), and the mutual information of µ is defined asI(µ) = D KL (µ, µ ⊗ ). 
probability amplification by iteratively prompting: 
 In this section we demonstrate that, as mentioned in the introduction, repeating possible responses several times in a prompt can have pronounced effects on the output of a language model. Consider x ="What is the capital of the UK?" andY 1 = • • • = Y t ="Another answer to question Q is Paris."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 1 shows, the conditional normalized probability4 of the correct response, "London", reduces from approximately 1 to about 96% as we increase the number of repetitions of the incorrect response to 100. Figure 1 shows 3 more examples where, with initially low epistemic uncertainty in the response to the query (the aleatoric uncertainty is also low as we consider single-response queries), the correct response maintains a significant or non-negligible probability even in the presence of repetitions of incorrect information, while the probability of predicting the latter is 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 is 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 a correct answer. This time, by incorporating a potential response in the prompt, the probabilities of other correct answers stay relatively large. Figure 3 shows four such examples. 
explanation through the lens of in-context vs. in-weight learning: 
 The sensitivity of the response of an LLM to extra in-context information, as observed above, can already be observed in a single attention head as explained next.We consider an idealized attention mechanism as follows. Let Z ∈ R n×d be an input matrix comprised of n semantic feature vectors each of dimension d . Each row is meant to represent a complete statement (such as "What is the capital of the UK?" or "One answer to the question is Paris.", etc.) rather than a single token. Let X ∈ R 1×d be the first row of Z, which represents the query of interest, such as "What is the capital of the UK?". Let E ∈ R 1×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 a statement is simply copied. For example, for V = "What is the capital of the UK?", P ( • | V ) 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 matrixW V is learned such that V W V estimates P ( • | V ) for vector V . Let W Q , W K , W V ∈ R d ×dbe the query, key, and value matrices. A self-attention head with query X and context Z \ X is defined asf (Z; W Q , W K , W V ) = Softmax 1 √ d E W Q (ZW K ) ZW Vwhere the output of the softmax is a row vector of length n.If X has appeared many times in the training data, then parameters W Q and W K could be learned such that E W Q (W K ) X is large, that is, X is within the space spanned by the large principal components of the key-query matrix product. Then, no matter what in-context information appears in Z, the probability assigned to X will dominate the softmax, and we will have Softmax 1√ d E W Q (ZW K ) Z ≈ X , and therefore f (Z; W Q , W K , W V ) ≈ P ( • | X). 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 Q (W K ) X 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 Q , W K , W V ) ≈ Y since Softmax 1 √ d E W Q (ZW K ) Z ≈ Y .Even if X is in the span, repeating Y t times in Z would give a t-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. 
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 score-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 are 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 a notion of the joint distribution over responses given a query, derived from the language model through the prompting mechanism F defined in Section 2: Definition 5.1 (Pseudo joint distribution). Given a family of prompt functions F, a conditional distribution µ ∈ P, and n ∈ N, we use notation • to denote a pseudo joint distribution defined asµ(Y 1 , . . . , Y n | x) = µ(Y 1 | F 0 (x)) µ(Y 2 | F 1 (x, Y 1 )) • • • µ(Y n | F n-1 (x, Y 1 , . . . , Y n-1 )) . (1)The above is a 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 chainrule-like procedure as can be seen from the above definition, that is, to have(Y 1 , . . . , Y n ) ∼ Q we draw Y 1 ∼ Q(• | F 0 (x)), Y 2 ∼ Q(• | F 1 (x, Y 1 )), Y 3 ∼ Q(• | F 2 (x, Y 1 , Y 2 )), 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 ≡ P Y1•••Yn|x .For any query x ∈ X , let Y Q (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 x ∈ X , (i) there exists a sequence of valid responses Y(x) ⊂ X such that the ground-truth distribution satisfies Roughly speaking, the assumption tells that the response distribution is insensitive to a query based on previously sampled responses. For example, for query x ="Capital of the UK:", the probability of Y 2 ="London" essentially does not change if a city is Y 1 ="Paris".P (Y t | F t-1 (x, Y 1 , . . . , Y t-1 )) = P (Y t | x) for any t ∈ N and any (Y 1 , . . . , Y t ) ∈ Y(x); (ii) Y Q (x) ⊂ Y(x),To measure epistemic uncertainty, we need to 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 ∈ X , we say that the epistemic uncertainty of Q is quantified by D KL ( Q, P ).Here D KL measures how well Q approximates P for a given query x. Namely, this metric determines if Q assigns a 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 D KL ( Q, 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,D KL ( Q, P ) ≥ I( Q).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 D KL ( Q, P ) as the measure of epistemic uncertainty (out of similar distance measures) since it admits this property.Also, note that we haveI( Q) = D KL ( Q, Q ⊗ ) , Q ⊗ = i y \i Q(y 1 , . . . , y i-1 , Y i , y i+1 , . . . , y n ).In general y \i Q(y 1 , . . . , y i-1 , Y i , y i+1 , . . . , y n ) = Q(Y i ), because the independence assumption Assumption 5.3 does not necessarily (and, in practice, almost never) holds for Q.Finally, a quantity related to D KL ( Q, P ) is D KL with arguments arranged in the opposite order, that is D KL ( P , Q) which is a (query) conditional excess risk of the LLM-derived 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 a much harder task than the one we consider here, because for the former we need to theoretically control all sources of errors (such as generalization, estimation, and approximation error). , . . . , X k ∼ µ ∈ M 1 (X n ) 3: Construct a set of indices of unique elements U = i ∈ [k] : X i = X j ∀j < i 4:Construct empirical distributions: let Z = j∈U µ(X j ), and for all i ∈ U , computeµ(X i ) = µ(X i ) Z and µ ⊗ (X i ) = n j=1 t∈U :Xt,j =Xi,jμ(X t,1 , . . . , X i,j , . . . , X t,n )5: Compute estimate of MI I k (γ 1 , γ 2 ) = i∈U µ(X i ) ln µ(Xi)+γ1 µ ⊗ (Xi)+γ2Algorithm 1: MI estimator.Theorem 5.5 gives a 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 to observe probabilities of all strings under the language model and so we must rely on a 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 1; for generality it is presented for an arbitrary (pseudo) joint distribution µ, but we keep in mind that our case of interest is µ = Q. Note that most terms in the summations defining the product distribution µ ⊗ are zero (except the ones which correspond to the observed data). Adding γ 1 and γ 2 in the estimator I k (γ 1 , γ 2 ) is intended to account for the total probability of missing observations, not included while constructing µ and µ ⊗ , making sure the estimate is bounded.The bias introduced by (γ 1 , γ 2 ) in the last equation allows us to rigorously bound the error in estimating I(µ) via I k (γ 1 , γ 2 ), which is explored next. In particular, in Theorem 5.6 we prove a high-probability lower bound on I(µ) in terms of I k . 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 a finite sample. In Appendix F, we present a 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 asU k = x∈X n µ(x) I x ∈ {X 1 , . . . , X k } .Using this quantity, we are ready to present a non-asymptotic bound on the estimation error, which depends on the estimator I k (γ 1 , γ 2 ), the expected missing mass, and the sample size:Theorem 5.6. Suppose that I k (γ 1 , γ 2 ) is given by Algorithm 1, and assume that X is finite. Forγ 1 = 1/(k |X n |), and γ 2 satisfying γ 2 ≥ γ 1 + n(1 -Z), with probability at least 1 -δ, we haveI(µ) ≥ (1 -ε k ) I k (γ 1 , γ 2 ) - 1 k + (1 + n ln 1 + k |X |) ε k where ε k = E[U k ] + ln( 1 δ ) k . Furthermore, given δ supp ∈ [0, 1), let X ⊆ X n such that µ( X ) ≥ 1 -δ supp . Then, for γ 1 = 1/(k | X |), and γ 2 satisfying γ 2 ≥ γ 1 + n(1 -Z), with probability at least 1 -δ, we haveI(µ) ≥ (1 -ε k ) I k (γ 1 , γ 2 ) - 1 k + (1 + ln 1 + k | X |) (δ supp + ε k ) .The theorem is a corollary of Theorem F.4 shown in Appendix F. 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 it is most suitable in situations where we expect µ to be spread out (uniformly) across its entire support. The price of not having samples covering the whole support in this case is a factor n ln |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 ln |X | = n T ln(10000), and soI(µ) ≥ (1 -ε k ) I k (γ 1 , γ 2 ) -(1/k + (1 + n T ln(1 + k ln(10000))) ε k ).Arguably, in practice, such situations are rare, as in natural languages we will not encounter all possible strings. To this end, we consider an optimistic scenario where the effective support of µ, denoted by X , is small with high probability. In this case, we can replace the size of the support for strings of length n, |X | n , in the first bound with the effective support size | X |, and we only pay essentially a factor ln(1 + k| X |) instead of n ln(1 + k|X |). In case the effective sample size is only polynomial in n, this leads to an exponential reduction in n for the second term in the bounds. In fact, in Appendix F.4 we demonstrate some empirical evidence that on two question-answering benchmarks, | X | rarely exceeds ≈ 100 with µ( X ) ≥ 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(µ) = Ω((1 - E[U k ]) I k (γ 1 , γ 2 ) -E[U k ]) as k → ∞.This tells us that the rate of estimation error is essentially controlled by the expected missing mass E[U k ], which, as we will see, converges to zero as k → ∞, however the decay can be very slow in general. For example, it is known that for a finite support of size (Berend and Kontorovich, 2012) . For countable distributions with entropy bounded by h, one hasN , E[U k ] ≤ e -k N when k ≤ N and E[U k ] ≤ N/(e k) otherwiseE[U k ] ≤ h/ ln(k).Despite these pessimistic bounds, in reality we expect the expected missing mass to be significantly smaller, especially when µ is heavy-tailed. It is well-known that natural languages (and many artificial ones) follow a Zipf distribution, where probability of each word (or a text piece) is proportional to 1/freq(text)α for some exponent α > 1, where freq() is a frequency of occurrence in the corpus (Piantadosi, 2014) . Then, we expect that E[U k ] should be much smaller than in such a case, since sampling from the tail of Zipf distribution is a rare event. To this end, in Appendix F we show that if Q is Zipf with exponent α > 1, then for any free parameterβ > 0, E[U k ] = O(k -( α-1 α -β)) . Hence, the rate at which the expected missing mass vanishes can be very fast (potentially matching a concentration rate 1/√ k for α = 2).Finally in Appendix F.4 we present a data-dependent estimation of E[U k ] 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.Let I k (γ, x) ≡ I k (γ) computed as in Algorithm 1 for µ = Q, to emphasize the explicit dependence on the query x. The uncertainty estimate I k (γ, x) derived above can be used as a score indicating the strength of our belief that the LLM hallucinates for the given query x. Such a score can then be used to design abstention policies: if the response is deemed to be hallucinated, the system abstains from responding, while a response is provided otherwise. Score-based abstention methods usually compute a score chosen by the user (such as the response likelihood or the estimator I(γ) 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 is 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) asa λ (x) = 0 if I k (γ 1 , γ 2 , x) < λ and a λ (x) = 1 if I k (γ 1 , γ 2 , x) ≥ λ,where λ > 0 is a threshold parameter tuned on a hold-out sample of some particular task. This policy abstains (a λ (x) = 1) when the epistemic uncertainty in the prediction (response) is large. When the policy does not abstain (a λ (x) = 0), any prediction from Q can be served. In the experiments, we compare a number of scoring functions for detecting hallucinations, including I(γ), the probability of the greedy (temperature zero) response, and an estimate of the entropy of the response distribution. 
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. In 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 a Gemini 1.0 Pro model (Gemini Team, Google, 2023) to generate outputs and scores. Similar results were obtained with a -much smaller -Gemini 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 et al., 2020) . These datasets mostly contain single-label queries, and only contain a few multi-label ones. 5 Moreover, we created a multi-label dataset based on the WordNet dataset (Fellbaum, 1998) : We extracted all (6015) datapoints from WordNet at depth 4 or more of the physical_entity subtree. For each datapoint (entity, 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 thresholded 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 T 0); (ii) 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 γ 1 = γ 2 = 0 (the latter choice approximates the case that the number of potential responses can be very large in which case the theoretical choice of γ 1 and γ 2 would be very small); (iv) the self-verification method of Kadavath et al. (2022) (denoted by S.V.). Additional details are 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. 6 Figure 4ab show PR-curves for the baselines and the proposed method on TriviaQA and AmbigQA. As can be seen, our method is better than the T 0 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 of these queries.Therefore, a first-order method can perform as well as our method on such queries. 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 we 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.E. 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, ideally, an LLM should have higher entropy on multi-label queries (which would demonstrate broader knowledge, not focusing on a single possible answer). To include such queries, we mix the TriviaQA and AmbigQA datasets with our WordNet-based dataset with "truely" multi-label queries as 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 on this dataset. Then we create two new datasets by combining our 842 WordNet datapoints with 842 randomly selected datapoints from TriviaQA and AmbigQA, respectively, resulting in the TriviaQA+WordNet and AmbigQA+WordNet datasets. 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 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 to 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). In order to 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,7 and measure the performance (error rate, i.e., 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 a 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.Although Theorem 5.5 and Theorem 5.6 provide a 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. (2023) ; Farquhar et al. (2024) , we propose constructing new ground-truth distribution P and LLM output distribution Q , where we cluster together semantically equivalent texts, and the probability of a cluster is the sum of probabilities of all semantically equivalent texts in that cluster.We use a similarity function s to define semantic equivalences: two texts are considered equivalent if their similarity is greater than a given threshold τ . Our choices for similarity functions in the experiments are described in Section 6. We assume the similarity function and the similarity threshold induce a clustering of the space X , i.e., s(Y, Y ) ≥ τ for Y, Y ∈ X if and only if they are in the same cluster.In practice, rather than constructing the aforementioned distribution Q explicitly, we can draw samples from Q by sampling from Q and aggregating samples according to their clusters. The modified uncertainty-estimation algorithm is given in Algorithm 2 in Appendix A. The estimator is constructed 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 µ = Q (line 4) by summing over cumulative probabilities over clusters. Note that D KL (µ) ≥ D KL (µ ) by monotonicity property of KL-divergence (Polyanskiy and Wu, 2024, Theorem 2.16 ) (this is because µ is defined on a smaller support). Therefore, Theorem 5.6 implicitly gives a bound on I(µ ), and eventually we have I(µ) ≥ I(µ ). More importantly, we can also directly apply Theorem 5.5 and Theorem 5.6 to the distributions P and Q and obtain that D KL ( Q , P ) ≥ I( Q ), giving a lower bound on the much reduced (epistemic) uncertainty after taking semantic equivalences into account.1: Input: µ ∈ M 1 (X n ) . . . ., . . . , X k ∼ µ ∈ M 1 (X n ) 3: Construct a set of indices of unique elements U = i ∈ [k] : X i = X j ∀j < i 4:Construct cluster centers S ⊂ U according to the similarity function such that for all i, t ∈ S, we have s(X i , X t ) < τ and the cluster associated withX i is D(i) = j ∈ U : s(X i , X j ) ≥ τ .Compute the aggregated probabilities: for all i ∈ S,µ (X i ) = j∈D(i)µ(X j )5: Construct empirical distributions: for all i ∈ S,µ(X i ) = µ (X i ) Z , where Z = j∈S µ (X j ) µ ⊗ (X i ) = n j=1 t∈S:Xt,j =Xi,jμ(X t,1 , . . . , X i,j , . . . , X t,n )6: Compute estimateI k (γ 1 , γ 2 ) = i∈S µ(X i ) ln µ(X i ) + γ 1 µ ⊗ (X i ) + γ 2Algorithm 2: MI estimator. Python implementation with usage example is given in Appendix B. , . . . , X k ∼ µ ∈ M 1 (X ) 3: Construct a set of indices of unique elements U = i ∈ [k] : X i = X j ∀j < i 4:Construct cluster centers S ⊂ U according to the similarity function: for all i, t ∈ S, we have s(X i , X t ) < τ and cluster associated withX i is D(i) = j ∈ U : s(X i , X j ) ≥ τ . Aggregated probabilities: for all i, t ∈ S, µ 1 (X i ) = j∈D(i) µ(X j ), µ 2 (X t | X i ) = j∈D(t) µ(X j | X i ) 5: Construct empirical distributions: for all i, t ∈ S, µ 1 (X i ) = µ 1 (X i ) Z , where Z = j∈S µ 1 (X j ) µ 2 (X t | X i ) = µ 2 (X t | X i ) Z i , where Z i = j∈S µ 2 (X j | X i ) µ(X i , X t ) = µ 1 (X i ) µ 2 (X t | X i ) , µ ⊗ (X i , X t ) = µ 1 (X i ) j∈S µ 1 (X j ) µ 2 (X t | X j ) 6: Compute estimate I k (γ 1 , γ 2 ) = i,t∈S µ(X i , X t ) ln µ(X i , X t ) + γ 1 µ ⊗ (X i , X t ) + γ 2Algorithm 3: Alternative MI estimator. A usage example is given in Appendix CIn this section we present an implementation of Algorithm 1 and Algorithm 2 in Python with a simple usage example. In particular, the code given in Listing 1 generates a synthetic joint distribution over binary tuples with correlated elements (function create_synthetic_distribution). Then, we compute an exact mutual information of the distribution (function compute_MI_exactly) and use implementation of our estimator (function MI_estimator) to estimate a mutual information. This is done for various sample sizes, number of random variables, and levels of correlation (a single experiment is implemented by run_experiment) The results of these multiple experiments are eventually presented in as plots showing convergence of the estimate to the exact value of the mutual information. In practical applications, synthetic joint distribution (function create_synthetic_distribution) can be replaced by an LLM-derived pseudo-joint distribution (see Definition 5.1). More detailed description of each function is given in Appendix B.1.The example can be easily copied from listing.tex within https://arxiv.org/src/ 2406.02543.Listing """Implements MI estimator (Algorithm 1).space: a list of tuples that the joint distribution is supported on (e.g. a cartesian product). joint_dist: probability distribution (1-D numpy array) where each entry is a probability of a tuple. k: sample size.A numpy array of tuples sampled from the distribution. A numpy array of indices of sampled tuples in space.• def cluster(tuples, joint_dist)Clusters tuples and aggregates probabilities of them in the same cluster.Args: tuples: A numpy array of tuples sampled from the distribution after deduplication. joint_dist: probability distribution (1-D numpy array) where each entry is a probability of a tuple.A numpy array of tuples sampled from the distribution each represening a cluster.A numpy array of probabilities of clusters. Each probability is the aggregate of probabilities of all tuples in the cluster.• def sample_from_joint_distribution_and_cluster(space, joint_dist, k)Samples k tuples from a joint distribution and retains only representative elements (removes all duplicates).Args: space: a list of tuples that the joint distribution is supported on (e.g. a cartesian product). joint_dist: probability distribution (1-D numpy array) where each entry is a probability of a tuple. k: sample size.A numpy array of tuples sampled from the distribution after deduplication.A numpy array of probabilities of deduplicated tuples.• def compute_MI_exactly(space, mu)Computes mutual information of probability distribution mu exactly Args: space: Tuple space (cartesian product). mu: probability distribution (1-D numpy array).Returns: (float) mutual information.• def MI_estimator(sampled_tuples, mu_on_sample, gamma_1, gamma_2)Implements MI estimator (Algorithm 1).Args: sampled_tuples: A numpy array of tuples sampled from the distribution after deduplication and clustering. mu_on_sample: A numpy array of probabilities of the clusters. gamma_1: stabilization parameter. gamma_2: stabilization parameter.Returns: (float) mutual information.• def run_experiment(n, temp, ax)Runs one experiment comparing exact mutual information estimation with Algorithm 1. Plots results.Args: n: number of variables in a joint distribution. temp: temperature of a Gibbs distribution (joint distribution). Higher temperature typically means smaller MI. ax: pyplot axis object for plotting.Algorithm 3 is a slight modification of Algorithm 2 that we use in 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 x ="What is the capital of the UK?", F1 score as the similarity function s, similarity threshold τ = 0.25, and number of samples k = 5. Algorithm 3 also takes the LLM distribution Q as input µ = Q.Given the query, in step (2) of Algorithm 3, we sample k outputs from Q. Let's assume these samples are X 1 ="London", X 2 ="London", X 3 ="London, UK", X 4 ="Paris", and X 5 ="Berlin".In step (3), we construct a set of indices of unique elements. In our example, we would have U = {1, 3, 4, 5}. In step (4), we cluster responses and aggregate probabilities of each cluster. More precisely, if the F1 score of two responses is above 0.25, then they are in the same cluster. In our example, we have that F1(X 1 , X 3 ) > 0.666 > 0.25 and F1(X 1 , X 4 ) = F1(X 1 , X 5 ) = 0, and therefore cluster centers are S = {1, 4, 5}. For query x, let's assume LLM probabilities areQ(X 1 | x) = 0.5, Q(X 3 | x) = 0.2, Q(X 4 | x) = 0.1, Q(X 5 | x) = 0.05, • • • Also assume conditional distributions are Q(X 1 | F 1 (x, X 1 )) = 0.6, Q(X 3 | F 1 (x, X 1 )) = 0.15, Q(X 4 | F 1 (x, X 1 )) = 0.05, Q(X 5 | F 1 (x, X 1 )) = 0.04, • • •and so on (we have omitted writing Q(. | F 1 (x, X 4 )) and Q(. | F 1 (x, X 5 ))). Then after step (4), the aggregated probabilities areQ (X 1 | x) = 0.7, Q (X 4 | x) = 0.1, Q (X 5 | x) = 0.05, • • •and aggregated conditional probabilities areQ (X 1 | F 1 (x, X 1 )) = 0.75, Q (X 4 | F 1 (x, X 1 )) = 0.05, Q (X 5 | F 1 (x, X 1 )) = 0.04, • • •and so on (we have similar aggregations for Q(. | F 1 (x, X 4 )) and Q (. | F 1 (x, X 5 ))).Next, in step (5), we construct empirical estimates. We will have that Z = 0.85 andQ 1 (X 1 | x) ≈ 0.82, Q 1 (X 4 | x) ≈ 0.11, Q 1 (X 5 | x) ≈ 0.05, • • •For estimated conditional distributions, we will have Z 1 = 0.84, andQ 2 (X 1 | F 1 (x, X 1 )) ≈ 0.89, Q 2 (X 4 | F 1 (x, X 1 )) ≈ 0.06, Q 2 (X 5 | F 1 (x, X 1 )) = 0.04, • • •and so on. The joint distribution Q(., . | x), the product of marginals Q ⊗ (., . | x), and the estimated mutual information I k are trivially obtained by the equations in steps ( 5) and ( 6).Next, we highlight the differences between Algorithm 2 (with the choice of n = 2) and Algorithm 3. The input distribution to Algorithm 2 is the pseudo-joint distribution Q, while the input to Algorithm 3 is the LLM distribution Q. So in step (2) of Algorithm 2, each sample is a tuple such as ("London", "Paris"), while a sample in step (2) of Algorithm 3 is an LLM output such as "London". Steps (3) and (4) of Algorithm 2 are similarly modified, and now the similarity function is defined over tuples.In this section we present an overview of the related literature.In a Bayesian framework, we can estimate the epistemic uncertainty by the uncertainty in the posterior distribution (Neal, 2012; Gal, 2016; Wang and Holmes, 2024) . Implementing a Bayesian neural network however can be very challenging.A number of iterative prompting strategies are developed to 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 al. (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 to 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 to ours is the parallel and independent work of Ahdritz et al. (2024) . Similar to us, Ahdritz et al. (2024) observe that in presence of high epistemic uncertainty, an LLM is more likely to copy the information provided in its context. For a given query, Ahdritz et al. (2024) propose considering top-k completions of the model, and then computing the entropy of the model conditioned on an iterative prompt composed of the original query and each completion. The minimum of these entropies is considered as a 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-uncertainty single-response queries. Tuning this threshold, however, would introduce extra complications. In contrast, we propose a principled test using a mutual information score that is guaranteed to be a lower bound on the KL-divergence between the LLM and the ground-truth. Further, we provide a mechanistic explanations for why LLMs behave as described in the presence of high epistemic uncertainty. V (y | x) = pY1 (y | x) pY2|Y1 (y | y, x) -pY1 (y | x) = pY1,Y2 (y 1 , y 2 | x) -pY1 (y | x)p Y1 (y | x)as a measure of epistemic uncertainty. Assume that an equivalence class Φ (that maps a prompt to the set of equivalent prompts) is given, and let ν(. | Φ(x)) be a distribution (say, uniform) over class Φ(x). If the trained model is second order calibrated with respect to the equivalence class and the distribution ν, i.e.1 | x) = x ∈Φ(x) ν(x | Φ(x))p(y 1 | x ) , pY1,Y2 (y 1 , y 2 | x) = x ∈Φ(x) ν(x | Φ(x))p(y 1 | x )p(y 2 | x ) ,then it follows from definitions that in the class associated with x,x ∈Φ(x)ν(x | Φ(x))(p Y1 (y | x ) -p(y | x )) 2 = x ∈Φ(x) ν(x | Φ(x)) V (y | x ) .The quantity on the right-hand side is a measure of epistemic uncertainty. Notice that the equality states a coverage result, and it is not point-wise. Requiring the model to be second order calibrated is also a strong condition and ensuring it is highly non-trivial.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 of 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-hyperparameter 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 et al., 2016; Lakshminarayanan et 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 a single network with an artificially injected (controlled) source of randomness. Rabanser et al. (2022) proposes to use intermediate model checkpoints to 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.First-order methods consider variance in the response distribution as a measure of hallucination (Kadavath et al., 2022; Cole et al., 2023; Manakul et al., 2023; Lin et al., 2023; Kuhn et 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, as they aim for detecting if one response (or multiple responses with the same meaning) is dominant. On the other hand, when multiple responses are correct, there is an aleatoric uncertainty in the ground truth: If an LLM correctly assigns non-negligible scores to 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 of aleatoric uncertainty will invalidate most of the correct answers. Yona et al. (2024) design a method that generates multiple responses, and then aggregates them into a 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 (self-verification) Kadavath et al. (2022) propose to use LLM self-prompting to measure a model's uncertainty in its responses. More specifically, for a given query, a number of responses are generated, and then the model is queried if the responses are correct. For this query, the log-probability of "True" is returned as a measure of uncertainty. Related approaches are studied by Mielke et al. (2022) .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 in 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 a model that predicts two answers: one based on parametric knowledge and one based on contextual information.Similarly to Neeman et al. (2022) , Li et al. (2023) aims to design a mechanism such that the model's behavior is influenced more by relevant context than by its parametric knowledge (controllability), while the model is robust to irrelevant contexts (robustness). They improve controllability and robustness using finetuning.Hou et al. ( 2024) study an approach to estimate model uncertainty due to ambiguity in a question. For a given question, their method generates multiple input clarification questions, and a new question is 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 is different than the problem we study as the model can be uncertain about the answer even if the query itself has no ambiguity. For such queries, the method of Hou et al. ( 2024) might decide that no clarification is needed, and therefore there is no uncertainty.There are a number of papers that try to extract knowledge/truthfulness by inspecting hidden-layer activations of LLMs (Burns et al., 2023; Azaria and Mitchell, 2023; Chen et 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 of these methods.In this section, we discuss how to estimate the mutual information from a finite sample, which may not cover the full distribution. To control the estimation error, we first introduce the concept of missing mass.Let X be a countable set and suppose that X 1 , . . . , X k ∼ µ ∈ M 1 (X n ) independently. In the following x is used as an element of X n rather than the query (as in Section 5). Then, the missing mass is defined as the random variableU k = x∈X n µ(x) ξ(x) , ξ(x) = I{x ∈ {X 1 , . . . , X k }} .Here we are primarily interested in two questions: (i) how quickly U k approaches the expected missing mass EU k , where it is not hard to see thatEU k = x∈X n µ(x)(1 -µ(x)) k ;and (ii) we are also interested in giving an estimate for EU k given µ and k. The first question is answered by the following theorem:Theorem F.1 (Concentration of a missing mass (Berend and Kontorovich, 2013) ). For any t > 0, we have an upper-tail boundP (U k > EU k + t) ≤ e -tk 2 ,and moreover for a universal constant c ≈ 7.6821, we have an lower-tail boundP (U k < EU k -t) ≤ e -ctk 2 .Notably U k exhibits a sub-gaussian concentration (i.e. 1/ √ k), 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 EU k .In particular, when X is finite with |X | = N , Berend and Kontorovich (2012) showed thatEU k ≤ e -n N , if n ≤ N ; N e n , if n > N.In the countably infinite X , we cannot generally have a non-trivial bound on EU k 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 H(µ) ≤ h < ∞. For all n ≥ 1, we have EU k ≤ h k i=1 i -1 ≤ h ln(n) .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 a Zipf distribution (Piantadosi, 2014), we expect that E[U k ] should be much smaller than in the above cases, since sampling from the tail of a Zipf distribution is a rare event. In Appendix F.4 we show the following:Corollary F.3 (Expected missing mass of Zipf distribution). Consider distribution µ(i) = i -α /H(α, N ) for i ∈ [N ], where α > 1 and H(α, N ) = N i=1 i -α . Then, for any β > 0,E[U k ] = O k -( α-1 α -β) .Proof. The statement followss by combining Lemma F.9 and Proposition F.10.Our goal is to estimateI(µ) = D KL (µ, µ ⊗ ) = x∈X n µ(x) ln µ(x) µ ⊗ (x)by only having access to X 1 , . . . , X k ∼ µ. Note that that the sample might cover only some part of the support of X and therefore we are facing a missing mass problem. In the following we consider estimator I k (γ) given by Algorithm 1.In particular in Appendix F.3 we show the following Theorem F.4. Fix X ⊆ X n . Fix γ 1 > 0 and suppose that γ 2 ≥ n(1 -Z) + γ 1 . Then for any fixed δ ∈ (0, 1), with probability at least 1 -δ,(1 -ε k ) I k (γ 1 , γ 2 ) -| X |γ 1 + ln e + e γ 1 µ(X n \ X ) + ε k ≤ I(µ)whereε k = EU k + ln( 1 δ ) k .In particular, Theorem F.4 implies the following:Corollary F.5. Under conditions of Theorem F.4, there exists(γ * 1 , γ * 2 ) ∈ (0, 1) 2 such that (1 -ε k ) I k (γ * 1 , γ * 2 ) - 1 k + (1 + n ln 1 + k |X |) ε k ≤ I(µ) .Note that, choosing any of the upper bounds on EU k discussed in Appendix F.1, we can see that Corollary F.5 implies asymptotic convergence in as a senselim k→∞ I k (γ * 1 , γ * 2 ) ≤ I(µ) .F.3 Proof of Theorem F.4The proof will heavily rely on the simple fact thatEQUATIONRecalling that S = i ∈ [k] : X i = X j ∀j < i , this immediately implies the following connection between U k and the quantities used in Algorithm 1:Proposition F.6. We have that j∈S µ(X j ) = x∈X n (1 -ξ(x)) µ(x) = 1 -U k .Recall that the product distribution of µ is defined asµ ⊗ (x) = n i=1 x \i µ(x 1 , . . . , x i-1 , x i , x i+1 , . . . , x n ) .Note that we use x \i µ(• • • ) instead of µ(x i ) since these are not necessarily equal for some µ. Now, using the definitions of I k , µ, and µ ⊗ ,I k (γ 1 , γ 2 ) = 1 Z i∈S µ(X i ) ln µ(X i ) Z + γ 1 -ln µ ⊗ (X i ) + γ 2 = 1 Z x∈X n (1 -ξ(x)) µ(x) ln µ(x) Z + γ 1 -ln µ ⊗ (X i ) + γ 2 (by Eq. (2)) = 1 Z x∈X n (1 -ξ(x)) µ(x) ln µ(x) + γ 1 µ ⊗ (x) + γ 1 + ln µ ⊗ (x) + γ 1 µ ⊗ (x) + γ 2 + ln 1 Z = 1 Z x∈X n µ(x) ln µ(x) + γ 1 µ ⊗ (x) + γ 1 (i) + 1 Z x∈X n ξ(x) µ(x) ln µ ⊗ (x) + γ 1 µ(x) + γ 1 (ii) + ln 1 Z (iii) + 1 Z x∈X n (1 -ξ(x)) µ(x) ln µ ⊗ (x) + γ 1 µ ⊗ (x) + γ 2 (iv)Now we control each of the terms individually. To control (i) we will first need the fact that q ln((q + γ 1 )/p) ≤ q ln(q/p) + γ 1 for any q, p ∈ [0, 1], γ 1 > 0. Note that this follows sinceEQUATIONusing that ln(1 + a) ≤ a for a > -1. Getting back to (i), and using the aforementioned inequality, we get(i) = 1 Z x∈X n µ(x) ln µ(x) + γ 1 µ ⊗ (x) + γ 1 = 1 Z x∈ X µ(x) ln µ(x) + γ 1 µ ⊗ (x) + γ 1 + 1 Z x∈X n \ X µ(x) ln µ(x) + γ 1 µ ⊗ (x) + γ 1 ≤ 1 Z x∈ X µ(x) ln µ(x) + γ 1 µ ⊗ (x) + γ 1 + 1 Z ln 1 + γ 1 γ 1 µ(X n \ X ) ≤ 1 Z x∈ X µ(x) ln µ(x) µ ⊗ (x) + γ 1 + 1 Z ln 1 + 1 γ 1 µ(X n \ X ) (by Equation (3)) = 1 Z D KL (µ, µ ⊗ ) + | X | γ 1 + 1 Z ln 1 + 1 γ 1 µ(X n \ X ) .Furthermore,(ii) ≤ 1 Z x∈X n ξ(x) µ(x) ln 1 + 1 γ 1 = 1 -Z Z ln 1 + 1 γ 1 .Next, observe that (iii) ≤ ln(1/Z). Finally, term (iv) is controlled through the following fact shown at the end of this section: Lemma F.7. Suppose that γ 1 ≥ 0 while γ 2 ≥ γ 1 + n(1 -Z). Then,1 Z x∈X n (1 -ξ(x))µ(x) ln µ ⊗ (x) + γ 1 µ ⊗ (x) + γ 2 ≤ 0 .Putting everything together, we obtainI k (γ 1 , γ 2 ) ≤ 1 Z D KL (µ, µ ⊗ ) + | X |γ 1 + 1 Z ln 1 + 1 γ 1 µ(X n \ X ) + 1 -Z + ln(1/Z) .Finally, multiplying through by Z the entire inequality, and using the fact that Z ln(1/Z) ≤ 1 -Z, we getZ I k (γ 1 , γ 2 ) ≤ D KL (µ, µ ⊗ ) + | X |γ 1 + ln 1 + 1 γ 1 µ(X n \ X ) + 1 -Z + 1 -Z ≤ D KL (µ, µ ⊗ ) + | X |γ 1 + ln e + e γ 1 µ(X n \ X ) + 1 -Z .To complete the proof we need to give a lower bound on Z. Note that Z = 1 -U k by the definition of Z and Proposition F.6, and so by Theorem F.1P (1 -EU k > 1 -U k + t) ≤ e -tk 2 .Using this concentration bound together with the choices of γ (also setting δ supp = 0 for the first inequality in the main statement) completes the proof of Theorem F.4.Proof of Lemma F.7. Observe thatµ ⊗ (x) = (1 -ξ(x)) n j=1 t∈S:Xt,j =xj μ(X t,1 , . . . , x j , . . . , X t,n ) = 1 Z n (1 -ξ(x)) n j=1 t∈S:Xt,j =xj µ(X t,1 , . . . , x j , . . . , X t,n ) = 1 Z n (1 -ξ(x)) n j=1 x ∈X n (1 -ξ(x )) I{x j = x j } µ(x 1 , . . . , x j , . . . , x n ) = 1 Z n (1 -ξ(x)) n j=1 x \j(1 -ξ(x 1 , . . . , x j , . . . , x n )) µ(x 1 , . . . , x j , . . . , x n ) . Now, using that fact that x \j ξ(x 1 , . . . , x j , . . . , x n ) µ(x 1 , . . . , x j , . . . , x n )x \j ,xj ξ(x 1 , . . . , x j , . . . , x n ) µ(x 1 , . . . , x j , . . . , x n )= 1 -Z we arrive atµ ⊗ (x) ≥ 1 Z n (1 -ξ(x))   n j=1   x \j µ(x 1 , . . . , x j , . . . , x n ) + Z -1     + (a) ≥ 1 Z n (1 -ξ(x))   n j=1 x \j µ(x 1 , . . . , x j , . . . , x n ) -n(1 -Z)   + = 1 Z n (1 -ξ(x)) µ ⊗ (x) -n (1 -Z) +where to get (a) we used:Proposition F.8. For any p 1 , . . . , p n ∈ [0, 1] and a ≥ 0, we haven i=1 (p i -a) ≥ n i=1 p i -n a .Proof. The statement following by lower-bounding the left-hand side by its linearization in a (derivative at 0), while realizing that it is a convex function of a.The above gives us that1 Z x∈X n (1 -ξ(x))µ(x) ln µ ⊗ (x) + γ 1 µ ⊗ (x) + γ 2 ≤ 1 Z x∈X n (1 -ξ(x))µ(x) ln µ ⊗ (x) + γ 1 1 Z n (1 -ξ(x)) (µ ⊗ (x) -n(1 -Z)) + + γ 2and focusing on the case 1 -ξ(x) = 1 (otherwise both sides are 0) the above equals to1 Z x∈X n µ(x) ln µ ⊗ (x) + γ 1 1 Z n (µ ⊗ (x) -n(1 -Z)) + + γ 2 ≤ 1 Z x∈X n µ(x) ln µ ⊗ (x) + γ 1 (µ ⊗ (x) -n(1 -Z)) + + γ 2 ≤ 1 Z x∈X n µ(x) ln µ ⊗ (x) + γ 1 µ ⊗ (x) -n(1 -Z) + γ 2 ≤ 0 by setting γ 2 ≥ γ 1 + n(1 -Z).We will rely on some machinery used by Ohannessian and Dahleh (2010) who established distributiondependent bounds on the expected missing mass. As before let µ be supported on a countable set. The accrual function is defined asF (v) = µ(i)≤v µ(i) (v ∈ [0, 1])and moreover the accrual rates are defined asρ = lim inf v→0 ln F (v) ln v , ρ = lim sup v→0 ln F (v) ln vWe use the following result: Lemma F.9 (Ohannessian and Dahleh, 2010, Theorem 1). Let µ have lower and upper accrual rates 0 < ρ ≤ ρ < ∞. Then for every β > 0 there exists k 0 such that for all k > k 0 we have:k -(p+β) ≤ E[U k ] ≤ k -(p-β)or, equivalently, for every β > 0 we have thatE[U k ] is both Ω(k -(p+β) ) and O(k -(p-β) ). Proposition F.10. Consider the distribution µ(v) = i -α /H(α, N ) for i ∈ [N ] where α > 1 and H(α, N ) = N i=1 i -α . Then, ρ = Ω( α-1 α ) as N → ∞.Proof. The idea is to use Lemma F.9 to give an upper bound on the missing mass. Therefore, we need to establish a lower bound on ln F (v). For now, abbreviateu = (v H(α, N )) -1 α .First note that for some1 ≤ u ≤ N N i≥u i -α ≥ N u (1 + i) -α di = 1 α -1 (1 + u) 1-α -(1 + N ) 1-α .On the other hand,N i=1 i -α ≤ N 1 (1 + i) -α di ≤ 1 α -1 (1 -N 1-α ) . So, ln F (v) ≥ ln (1 + u) 1-α -(1 + N ) 1-α -ln(1 -N 1-α ) ≥ ln (1 + u) 1-α -(1 + N ) 1-αand thenln F (v) = Ω ((1 -α) ln(1 + u)) (as N → ∞) = Ω ((1 -α) ln(u)) = Ω (1 -α) ln((v H(α, N )) -1 α ) = Ω α -1 α ln(v) + α -1 α ln H(α, N ) = Ω α -1 α ln(v) .Data-dependent estimate of the expected missing mass We perform an experiment designed to give a data-dependent estimate of the expected missing mass E[U k ] for some specific datasets. Clearly, we cannot simply apply a concentration bound discussed in Appendix F.1 since the complete support of the pseudo joint distribution derived from the LLM is unknown. To this end, we approximate it with a finite support driven by the language model itself. In particular, given a query we sample responses (at temperature 0.9) until their total probability mass reaches 0.95 or we reach 1000 responses per query. In case of TriviaQA, we performed 1233 queries in total. The mean and the median number of unique responses per query was eventually 118.3 and 22, respectively. In 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, we denote the set of responses by X and let Ũk be the missing mass computed on X . Then, we haveE[U k ] ≤ U k + ln( 1 δ ) k ≤ Ũk + U k -Ũk + ln( 1 δ ) k ≤ Ũk + 1 -P ( X ) + ln( 1 δ ) k ,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 a single query. We compute the bounds for TriviaQA and AmbigQA datasets (see Section 6 for details about these datasets). From Figure 6 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 k ] are concentrated close to 0, while the cumulative probability of the approximate support X is close to 1 most of the time, showing that our approximations are meaningful.Comparison of responses and computing the output distributions. We use the F1 score8 thresholded 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 a 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 F1 score (as a match function) and log-probabilities (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 selfprompting 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 T 0); (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 1 (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 γ 1 = γ 2 = 0 (the latter choice approximates the case that the number of potential responses can be very large in which case the theoretical choice of γ 1 and γ 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 F 1 (x, Y ). We construct estimates Q(Y ) and Q(Y |Y ) 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 log-likelihood function in LLMs.Notice that the input µ in Algorithm 3 is the LLM's output distribution Q as opposed to being the pseudo joint distribution Q in Algorithm 1. Another difference is that the similarity function s now takes two texts as input (as opposed to taking two n-dimensional arrays of texts as inputs in Algorithm 2). As explained earlier, we use the F1 score as the similarity function and we use τ = 0.25 as 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 T 0, 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 a version of the self-verification method of Kadavath et al. (2022) (denoted by S.V.) that, for a query x, first finds Y 1 , 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 answer to question Q is Y 1 . Is the above answer to question Q correct? Answer True or False. A:". The default choice of this baseline is 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 scores9 we consider) is not sensitive to the size of the label set.In order to show that our findings are not limited to models of certain size, we conducted experiments with much smaller Gemini Nano model with 2B parameters. The results are shown in Figures 7 and 8 . 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 as the recall increases (note that the large-looking difference on AmbigQA is actually at most 3%-points throughout, and it is also about at 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 in the paper. On TriviaQA+WordNet and AmbigQA+WordNet datasets with the additional 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. 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 at error rate 0.07 (as before, this error rate is computed by considering abstention as no error, i.e., error rate = errors/(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 a reasonably small error rate. This is again very similar to our findings for the Gemini Pro model.• 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. 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or 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: [Yes] Justification: Broader impact statement is made at the beginning of the appendix. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This work uses existing and publicly-available language models, so all the standard safeguards relevant models apply.Guidelines:• The answer NA means that the paper poses no 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 a best faith effort.12. Licenses for existing assets Question: 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?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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new 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 is used. 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.For instance, by saying that predictions live in a confidence set with high probability.In technical terms this corresponds to giving a lower bound, rather than an upper bound, on the quantity capturing the uncertainty.Following the usual convention, we define 0 ln 0 = 0 and a ln(a/0) = ∞ for any a > 0.To obtain conditional normalized probabilities, we consider the probabilities of the two responses, and normalize them so that they add to 1.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.This is done by fixing the target loss rates of 0.05 for TriviaQA and 0.15 for AmbigQA, and finding threshold parameters that lead to these rates on the calibration 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 = (a1, . . . , an) and b = (b1, . . . , bm), defining p = |a ∩ b|/n and r = |a ∩ b|/m (where |a∩b| is the size of the intersection of a and b, in which for repetitions of an element y, we consider the minimum number of repetitions in a and b, i.e., min c∈{a,b} |{i : ci = y}|, in calculating the size of the intersection) we define F 1 = 2pr/(p + r). Relating to the standard definition of the F1 score, p and r play the role of precision and recall, respectively, if a is thought of as a prediction of b.The scores T 0 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
(It should be noted that 4.1/theorem 4.5 very clearly discusses the limitations of applying MI to infinite language)

2) 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?
In 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.
questions: questions: See weaknesses
limitations: limitations: Limitations are adressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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).

2. **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.

3. **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.

4. **Limited model selection**: The paper does not validate the effectiveness of the method across different types of models.
questions: questions: N/A
limitations: limitations: The discussion on the limitations of this paper is insufficient.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. 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]

Reference:

[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).
questions: questions: Section 2:
1.  "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')?

2. what is "ground-truth conditional probability distribution"? do you mean p(Y|X) where (X, Y) are data and label?

3. where the "possible responses Y1, . . . , Yt" come from? Are they sampled from LLM Q with different decoding strategy?

4. what is the physical meaning of Z_i and also where does the second subscript i come from in (Z_i)_i?

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

Section 3:

5. "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.

6. The x-axis and y-axis labels are missing in Fig 1, Fig. 2, and Fig. 3. 

7. 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: limitations: No, the conclusion and limitations (and social impacts) are missing.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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? 

Several 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.
questions: questions: Some comments and questions follow:

The 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”.

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

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

The “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”?  

Hallucinations are mentioned in the paper but never clearly defined or cited. I believe the notion here is different from that in other work.

I recommend using title case for section headers.

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

I 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 

How 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? 

Is F_0(x) defined? Perhaps this is the case where the prompt is: “Provide an answer to the following question: Q: x. A:”

I 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: Limitations do not seem to be discussed very much.

Comments: title: Additional experimental results
Request for interaction
Thanks for clarifications
comment: Thank you for your feedback, and for considering our response in your revised review.
We strongly disagree that a significant revision is needed for the paper. Definitions, notations, evaluation protocol, etc. are already explained in detail in the paper, and we simply repeated the existing definitions in our rebuttal. Therefore, it is not clear what should be changed and why.
We conducted additional experiments with a smaller language model, Gemini Nano, and the results are posted above as a comment to all reviewers. A link to an anonymised external page containing figures is shared with the area chair. 

Regarding weakness 1: We are not sure what explanations are missing, but we would be happy to provide additional clarifications in the remaining time.
We conducted some additional experiments with a smaller language model, more precisely a 2B Gemini Nano model, which demonstrate that our findings with the much larger Gemini Pro models hold true in this much smaller scale. 

Due to the heavy computational requirements, we could not finish the experiments in time to upload figures (the replications of Figures 5 and 6 from the paper for this model) during the rebuttal, and given the submission policies, we cannot share a link to an external page here. We give a summary of the results in tables below, and have also shared an anonymized link to the figures with the area chair, and hopefully it will be shared with the reviewers.

------------------------------------------------------------------------------------

Precision and recall results (Figure 5):


TriviaQA:
\begin{array}{l|c|c|c|c|c|}
\text{Recall} &0.2 & 0.4 & 0.6 & 0.8 & 1.0 \\\\
\hline
\text{Precision (M.I. score)} & 0.4 & 0.38 & 0.38 & 0.37 & 0.35 \\\\
\text{Precision (S.E. score)} & 0.47 & 0.42 & 0.39 & 0.38 & 0.35
\end{array}

AmbigQA:
\begin{array}{l|c|c|c|c|c|}
\text{Recall} & 0.2& 0.4& 0.6& 0.8& 1.0 \\\\
\hline
\text{Precision (M.I. score)} &0.205& 0.195& 0.2&  0.195& 0.185 \\\\
\text{Precision (S.E. score)} & 0.21& 0.225& 0.215& 0.2& 0.185
\end{array}

TriviaQA+WordNet:
\begin{array}{l|c|c|c|c|c|}
\text{Recall}& 0.2& 0.4& 0.6& 0.8& 1.0 \\\\
\hline
\text{Precision (M.I. score)}& 0.52& 0.47& 0.5& 0.55& 0.65 \\\\
\text{Precision (S.E. score)}& 0.45& 0.35& 0.45& 0.55& 0.65
\end{array}

AmbigQA+WordNet:
\begin{array}{l|c|c|c|c|c|}
\text{Recall}& 0.2& 0.4& 0.6& 0.8& 1.0 \\\\
\hline
\text{Precision (M.I. score)}& 0.35& 0.4& 0.45& 0.55& 0.62 \\\\
\text{Precision (S.E. score)}& 0.27& 0.23& 0.4& 0.55& 0.6
\end{array}

This is a replication of the results presented in Figure 5 in the paper, but for a much smaller Gemini Nano model with 2B parameters. On TriviaQA and AmbigQA datasets, S.E. outperforms M.I. when the recall is low, but they perform similarly as the recall increases (note that the difference on AmbigQA is at most 3%-points throughout, and it is also about at 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 in the paper. On TriviaQA+WordNet and AmbigQA+WordNet datasets with the additional high entropy multi-label queries, M.I. outperforms the S.E. baseline. Similarly to the experiments presented in the paper, the precision increases as the recall grows (above around 0.5), as the previously rejected WordNet data is accepted more and more.

------------------------------------------------------------------------------------

Recall and error rates as functions of the entropy of the model's responses (Figure 6)

TriviaQA+WordNet:
\begin{array}{l|c|c|c|c|}
\text{Entropy bin}& 0.1& 0.3& 0.5& 0.7 \\\\
\hline
\text{M.I. Recall}& 0.3& 0.09& 0.09& 0.05 \\\\
\text{S.E. Recall}& 0.37& 0.0& 0.0& 0.0 \\\\
\text{M.I. Error}& 0.48& 0.2& 0.0& 0.0 \\\\
\text{S.E. Error}& 0.48& 0.0& 0.0& 0.0
\end{array}

AmbigQA+WordNet:
\begin{array}{l|c|c|c|c|}
\text{Entropy bin}& 0.1& 0.3& 0.5& 0.7 \\\\
\hline
\text{M.I. Recall}& 0.2& 0.05& 0.09& 0.05 \\\\
\text{S.E. Recall}& 0.2& 0.0& 0.0& 0.0 \\\\
\text{M.I. Error}& 0.6& 0.05& 0.0& 0.0 \\\\
\text{S.E. Error}& 0.6& 0.0& 0.0& 0.0
\end{array}

The methods are calibrated at error rate 0.07 (as in the paper, this error rate is computed by considering abstention as no error, i.e., error rate = #errors/(#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 a reasonably small error rate. This is again very similar to our findings for the Gemini Pro model.
Thank you for your response. The reviewer has thoroughly re-examined both the response and the clarified manuscript but still believes that significant revisions are necessary for the paper to be accepted. Therefore, the reviewer's evaluation remains unchanged.
Dear Reviewer,

I would appreciate if you could comment on the author's rebuttal, in light of the upcoming deadline.

Thank you,
Your AC
Results promised on smaller models, other architectures, or other models in general were not provided (I completely understand those results are hard to provide in such a short timeline). Nonetheless despite your intuition that your results are universal, there is as of now no evidence. 

After thinking about your argument on weakness 1 for some time, I believe perhaps part of the issue is perhaps clarity? I did not understand what you're explaining here in the paper. I will leave my score as is, but pointing out that weaknesses I pointed out are not addressed, and are strong limitations that should be mentioned should this paper be accepted.
I thank the authors for responding to many of my questions and for being willing to make some edits, such as title change, adding references, adding some definitions, etc. Although I find the paper to be empirically somewhat on the weaker side, I think there is some value to the literature from novel ideas. I will increase my score marginally in the expectation that exposition related issues will be suitably addressed in a revision.
Thank you for your response. I look forward to seeing those results. I am also taking some more time to digest your explanation on context, and will come back to you, I need to think it out.