To Believe or Not to Believe Your LLM

Yasin Abbasi Yadkori; Ilja Kuzborskij; András György; Csaba Szepesvári

Source-linked AI summary

To Believe or Not to Believe Your LLM

Yasin Abbasi Yadkori, Ilja Kuzborskij, András György, Csaba Szepesvári

arXiv:2406.02543v2Jun 4, 2024cs.LGcs.AIcs.CL

TL;DR

LLMs can be uncertain because they lack knowledge or because several answers are inherently possible, while standard uncertainty scores may fail to separate these sources in multi-answer settings. The paper uses iterative prompting to construct response joint distributions and derives a mutual-information-based epistemic-uncertainty estimator. The resulting approach supports hallucination detection across single- and multi-answer queries, with limitations from prompting assumptions and semantic equivalence handling.

Problem
Standard uncertainty quantification can be insufficient for distinguishing epistemic uncertainty from aleatoric uncertainty when multiple responses are correct.
Method
The paper uses iterative prompting to derive an information-theoretic epistemic-uncertainty metric, a mutual-information lower bound, and a finite-sample estimator from multiple model responses.
Results
The approach supports hallucination detection in both single- and multi-answer settings, and the finite-sample estimator can sometimes have negligible error on infinite-support response distributions.
Takeaways & Limitations
Separating epistemic from aleatoric uncertainty enables hallucination detection for multi-response queries rather than measuring total uncertainty alone.
Takeaways & Limitations
The analysis depends on a prompt construction whose independence assumption may fail for partial answers, and its divergence bound can be loose when semantic equivalences are ignored.

Abstract

from arXiv · show

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.

1 Introduction

The paper targets epistemic uncertainty in LLM responses, especially when multiple answers are valid, and develops iterative-prompting methods to distinguish it from aleatoric uncertainty. It derives information-theoretic estimators and applies them to hallucination detection, while analyzing how repeated responses can alter model outputs.

Motivation: Epistemic uncertainty reflects missing knowledge about the ground truth, whereas aleatoric uncertainty reflects irreducible randomness such as multiple valid answers.The distinction is central because total uncertainty alone cannot separate a truthful multi-answer predictor from an unreliable predictor.
Motivation: Standard uncertainty methods based on likelihood, entropy, or ensembling are generally limited when queries admit multiple correct responses.A perfect predictor may have high aleatoric uncertainty, making total output uncertainty insufficient for identifying epistemic uncertainty.
Approach: The paper uses iterative prompting to construct a joint distribution over multiple responses by conditioning each new response on the query and previous responses.The construction applies the chain rule of probability and compares the resulting dependence structure with the independence expected from ground-truth responses.
Contributions: Iterative prompting can force an LLM toward a desired response when that response is repeatedly added to the prompt.The paper further studies this amplification phenomenon mechanistically in transformer self-attention.
Contributions: The authors derive an information-theoretic metric and a computable mutual-information lower bound for epistemic uncertainty that is insensitive to aleatoric uncertainty.This enables epistemic uncertainty estimation even when several responses are valid.
Contributions: The finite-sample mutual-information estimator can sometimes have negligible error despite distributions supported on potentially infinitely many strings.The paper also proposes thresholding this estimator, with automatically calibrated thresholds, for hallucination detection.

2 Preliminaries

The preliminaries formalize text sequences, conditional distributions, prompting functions, and information-theoretic quantities used to analyze LLM-generated responses. They distinguish the ground-truth conditional distribution from the learned language model and define the prompt construction for sequential responses.

Basic definitions: The paper models finite text sequences over a finite alphabet and denotes conditional distributions over these sequences by a family of probability kernels.The notation introduces X as the space of finite text sequences and P as the family of conditional distributions.
Conditional distributions and prompting: The ground-truth conditional distribution is denoted P, while Q denotes the learned language model conditional distribution.Both distributions map prompts to probability distributions over response sequences.
Conditional distributions and prompting: For a fixed query and previous responses, the prompting family constructs a prompt containing the query and the responses before requesting the next answer.The displayed template asks for another answer after listing earlier answers to the same question.
Information-theoretic notions: The preliminaries define entropy, Kullback–Leibler divergence, marginals, and the product distribution of marginals for later uncertainty analysis.These quantities support comparisons between a joint response distribution and the distribution implied by independent coordinates.

3 Probability amplification by iteratively prompting

Iterative prompting reveals how repeating candidate responses changes an LLM’s conditional probabilities. Correct answers remain robust under low epistemic uncertainty, while repetition can amplify incorrect or alternative answers when uncertainty or aleatoric multiplicity is present.

3 Probability amplification by iteratively prompting: Figure 1 compares low-epistemic-uncertainty single-label queries using conditional normalized probability of the correct completion versus repetitions of an incorrect response.Each example includes the query, two responses, and their initial probabilities.
3 Probability amplification by iteratively prompting: Figure 2 uses the same conditional normalized probability measure to examine high-epistemic-uncertainty single-label queries under repeated incorrect responses.The first listed response is treated as correct in each example.
3 Probability amplification by iteratively prompting: For high-epistemic-uncertainty single-label queries, repeating an incorrect response can rapidly collapse the correct answer’s probability toward zero.The paper reports this behavior for the examples shown in Figure 2.
3.1 In-context learning vs. in-weight learning: For multi-label queries with aleatoric uncertainty, repeating one correct response leaves the probability of another correct response relatively large.Figure 3 presents four examples in which both provided responses are correct.
3 Probability amplification by iteratively prompting: Conditional normalized probabilities are obtained by considering the two response probabilities and normalizing them to sum to 1.
3.1 In-context learning vs. in-weight learning: An idealized attention model distinguishes in-weight learning from in-context information by representing the query as the first row and the remaining statements as context.The query is X, while Z \ X denotes the in-context information.
3.1 In-context learning vs. in-weight learning: When the query is strongly represented in training, attention can dominate context and approximate P(· | X), whereas repeated context responses can dominate when the query is weakly represented.Repeating Y increases its total softmax weight, potentially producing Y as the answer even when X is represented.

4 Metric of epistemic uncertainty and its estimation

The paper constructs pseudo joint distributions through iterative prompting and defines epistemic uncertainty as their divergence from a ground-truth pseudo distribution. Mutual information provides a computable lower bound based only on the LLM-derived distribution, with finite-sample estimation and semantic-equivalence extensions.

Assumptions: The ground-truth independence assumption requires each response distribution to remain unchanged when previously sampled responses are embedded in the prompt.The assumption depends on prompt construction and may fail when outputs are partial answers or otherwise depend on one another.
Pseudo joint distributions: Iterative prompting constructs a pseudo joint distribution by conditioning each response on the query and all preceding responses.The construction replaces standard chain-rule conditioning with prompt functions applied to previous outputs.
Metric: Epistemic uncertainty is quantified by DKL(eQ, eP), measuring whether the LLM-derived distribution assigns high mass to events that are unlikely under the ground truth.This divergence captures cases where the model generates sequences unlikely in typical language use.
Computable lower bound: Theorem 4.5 establishes DKL(eQ, eP) ≥ I(eQ), making mutual information a lower bound on epistemic uncertainty.The bound holds uniformly for all ground-truth pseudo joint distributions satisfying the independence assumption.
Estimation: The mutual-information lower bound is computable solely from the LLM-derived distribution and is estimated from sampled response tuples with an MI estimator.The paper gives a finite-sample estimator and non-asymptotic bounds, while noting that estimation error depends on expected missing mass.

5 Score-based hallucination tests

The paper uses the estimated mutual-information lower bound as a hallucination score and compares thresholded abstention against likelihood, entropy, and similarity-based procedures. Scores are calibrated on task-specific hold-out data before deciding whether to abstain.

Hallucination scores: The estimated lower bound bI_k(γ, x) serves as a query-specific score for the strength of belief that the LLM hallucinates.The score can be used to design abstention policies that withhold responses judged likely to be hallucinated.
Estimation considerations: The estimator’s convergence analysis relates its error to expected missing mass, whose decay can be slow in general.The paper connects this quantity to Good-Turing estimation but does not directly use the Good-Turing estimator.
Abstention policy: The abstention policy abstains when bI_k(γ1, γ2, x) ≥ λ and serves the prediction otherwise.The threshold λ is tuned on a hold-out sample for the task.
Comparisons: The experiments compare the MI score with the probability of the greedy response and an estimated response-distribution entropy.The paper also describes similarity-based clustering and an MI estimator implementation for grouped responses.

6 Experiments

The experiments evaluate mutual-information-based abstention against likelihood, semantic-entropy, and self-verification baselines on closed-book question-answering datasets. The proposed method is especially useful when queries have genuinely high-entropy multi-label answers.

Datasets: The study evaluates abstention policies on TriviaQA, AmbigQA, WordNet, and mixtures containing high-entropy multi-label queries.The evaluation uses closed-book open-domain question answering and combines mostly single-label datasets with WordNet-derived multi-label data.
Results: Figure 5 shows M.I. and S.E. outperforming T0 and S.V. on TriviaQA and AmbigQA, while M.I. and S.E. perform similarly there.These datasets are dominated by single-label or low-entropy queries, making first-order semantic entropy competitive with mutual information.
Results: On TriviaQA+WordNet and AmbigQA+WordNet, M.I. outperforms S.E. when the datasets contain many high-entropy multi-label queries.The methods are nearly identical over the unshown recall range.

7 Conclusions

The paper proposes mutual-information-based uncertainty estimation to separate epistemic from aleatoric uncertainty in LLM responses. This enables hallucination detection for multi-response queries without changing model training, using iterative prompting instead.

Conclusion: The method estimates epistemic uncertainty through mutual information over joint distributions of multiple LLM responses.It provides a provable lower bound on the LLM response’s epistemic uncertainty.
Conclusion: The resulting abstention method performs significantly better than first-order methods on mixed single-label and multi-label datasets.First-order methods quantify overall response uncertainty rather than epistemic uncertainty alone.
Conclusion: Iterative prompting supplies multiple responses and avoids modifying the LLM’s training procedure.The approach uses the sequential nature of LLMs to construct the required response distributions.

A Implementation and usage examples of Algorithm 1 and Algorithm 2

The appendix implements sampling, clustering, exact mutual-information computation, and a finite-sample mutual-information estimator. Synthetic experiments compare estimated and exact mutual information across distribution dimensions and temperatures.

Synthetic evaluation: The plotted outputs place sample size k on the x-axis and mutual-information estimates on the y-axis alongside the exact value.The experiment produces a grid over temperature and distribution dimension.
Sampling and clustering: The implementation samples tuples from a joint distribution, removes duplicates, and clusters similar tuples while aggregating their probabilities.Cluster representatives and aggregate probabilities form the empirical support used by subsequent calculations.
Mutual information: The exact mutual-information routine computes dependence among variables from a probability distribution over tuple space.For each tuple, it compares its joint probability with the product of its marginal probabilities.
Synthetic evaluation: The synthetic experiment compares exact mutual information with Algorithm 1 over sample sizes k ranging from 10 to 1000.The experiment varies the number of variables and the temperature of a Gibbs distribution.
Iterative prompting: The appendix notes that iterative prompting can force a desired response by repeatedly adding it to the prompt.This phenomenon is investigated mechanistically for transformer LLMs and is relevant to the paper’s prompting-based uncertainty analysis.

C.3 Training models with pairs of responses

The related approaches discussed here separate or estimate uncertainty using paired-response training, ensembles, response aggregation, self-prompting, contextual interventions, clarification questions, or hidden-layer activations. Their requirements and limitations differ from the paper’s output-only iterative-prompting approach.

Paired-response training: Paired-response methods can decouple epistemic and aleatoric uncertainty, but require training data containing query and paired observations.One described approach estimates a model over response pairs and assumes second-order calibration with respect to prompt equivalence classes.
Paired-response training: The associated equality is a coverage result rather than a pointwise guarantee, and second-order calibration is difficult to ensure.These conditions are identified as strong and highly non-trivial.
Ensembles: Ensemble methods combine estimators trained on perturbed data, but applying them to LLMs requires training multiple language models and is very expensive.Their hyperparameters are typically selected using validation data.
First-order methods: First-order hallucination detectors use response-distribution variance or dominance and commonly assume a single correct response.With multiple correct responses, they can classify many correct answers as hallucinations.
Other approaches: Other related methods aggregate multiple responses, ask the model to verify answers, modify contextual reliance, clarify ambiguous questions, or inspect hidden-layer activations.Activation-based methods require access to internal model states, limiting applicability.

D Omitted proofs

The omitted proofs establish the mutual-information identity used to relate the LLM-derived and ground-truth response distributions, then introduce missing mass to control finite-support estimation.

The proof identifies the relevant mutual information as I(eQ; Y1, . . . , Yn).
Finite-sample mutual-information estimation requires controlling the portion of the distribution absent from the observed sample.
The missing mass is introduced for independent samples from a distribution on a countable product space.

E.1 The missing mass problem

This section formulates missing mass as the unobserved probability mass in finite samples and reviews concentration and expectation bounds, including limitations for countably infinite supports.

The missing mass measures probability assigned to outcomes absent from k independent samples.
The section studies both concentration of Uk around E[Uk] and estimation of E[Uk] from the distribution and sample size.
Uk has sub-gaussian concentration, so deviations from the expected missing mass decrease rapidly with sample size.
For countably infinite supports, no generally non-trivial bound on E[Uk] depends only on the sample size n.
When the distribution has bounded entropy H(µ) ≤ h, an available bound is E[Uk] ≤ h ln(n).
The reviewed estimates are pessimistic, while Zipf-distributed languages are expected to have substantially smaller expected missing mass.

E.3 Proof of Theorem E.4

The proof connects missing mass to the estimator’s auxiliary quantities and uses concentration and logarithmic inequalities to derive a high-probability estimation bound under specified parameter conditions.

The proof relates the missing mass Uk to the quantities used in Algorithm 1 through a product-distribution identity.
The estimator’s error terms are controlled using inequalities involving γ1, γ2, the support mass Z, and the missing mass.
The proof obtains a lower bound on Z from concentration of the missing mass and completes the theorem by selecting the γ parameters accordingly.

E.4 Expected missing mass under Zipf distribution

The section estimates expected missing mass on finite approximations driven by LLM samples and reports that the resulting missing mass and its upper bound are typically near zero.

The analysis approximates the unknown response support by sampling from the LLM until reaching cumulative probability 95% or 1000 samples.
For TriviaQA and AmbigQA, missing mass on the approximate support and its upper bound on E[Uk] are concentrated close to 0.
The cumulative probability of the approximate support is close to 1 most of the time, supporting the meaningfulness of the finite-support approximation.
Figure 7 compares empirical distributions of the upper bound on E[Uk], approximate missing mass ˜Uk, and cumulative support probability P(˜X) across queries.