Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities

Summary

The authors propose a novel Kernel Language Entropy (KLE) method for uncertainty estimation in white- and black-box LLMs. KLE defines positive semidefinite unit trace kernels to encode the semantic similarities of LLM outputs and quantifies uncertainty using the von Neumann entropy. It considers pairwise semantic dependencies between answers (or semantic clusters), providing more fine-grained uncertainty estimates than previous methods based on hard clustering of answers. We theoretically prove that KLE generalizes the previous state-of-the-art method called semantic entropy and empirically demonstrate that it improves uncertainty quantification performance across multiple natural language generation datasets and LLM architectures.

Strengths

1. The authors propose Kernel Language Entropy, a novel method for uncertainty quantification in natural language generation. 2. The authors propose concrete design choices for our method that are effective in practice, for instance, graph kernels and weight functions. 3. The authors empirically compare our approach against baselines methods across several tasks an LLMs with up to 70B parameters (60 scenarios total), achieving SoTA results.

Weaknesses

1. The motivation is clear in Fig 1, but why choose the kernel to solve the problem, this part is not very clear. 2. The proposed method looks like it depends on the sampling times, which is expensive. How is the performance when we sample few times?

Questions

1. How do I get the final answer based on 10 samplings? For example, in fig 1, what could be the final answer of LLM2, majority vote?

Rating

7

Confidence

5

Soundness

3

Presentation

4

Contribution

3

Limitations

the authors adequately addressed the limitations

Summary

The paper introduces the method "Kernel Language Entropy", capturing semantic similarities of output sequences via semantic kernels and subsequently estimating uncertainty using the von Neumann entropy.

Strengths

- The paper proposes a novel approach to estimate uncertainty in LLMs. - It presents a solid theoretical foundation by showing that Kernel Language Entropy generalizes Semantic Entropy.

Weaknesses

The primary area for improvement is the paper's structure. The paper is quite difficult to follow due to definitions and expressions not being clearly contextualized, for instance: - **Sections and Headings**: Section 3 is inconsistent in its use of subsections and subheadings. It begins with a motivating example (subheading), followed by the formal definition of PSD kernels without a subheading. The definition of semantic kernels is embedded in the text without a subheading, making it less prominent than the practical approach for constructing semantic kernels, which has a dedicated subsection at the end of the section. Also, VNE is given more prominence than the main concept, KLE (starting with the definition of KLE (subheading) as the VNE, followed by deriving its properties, would improve coherence). - **Kernels**: In Section 3.1, two explicit kernels ($K_{heat}$ and $K_{Matérn}$) are introduced. In Section 5, the authors then propose to use $K_{heat}$ and $K_{full}$, with $K_{full}$ being a weighted sum of $K_{heat}$ and $K_{SE}$. The previously proposed $K_{Matérn}$ is no longer considered in the main experiments, while $K_{SE}$ has not been introduced before. It only becomes clear in Section B of the Appendix that $K_{SE}$ is equal to Semantic Entropy, which is referred to as $SE$ in Section 5. Also, the importance of the weighting factor for $K_{full}$ is not discussed. In general, the criteria for choosing between kernels are unclear (and not all kernels consistently outperform the baselines across datasets).

Questions

- Is the rather small model Llama 3 8B Instruct capable of evaluating the correctness of an output sequence? Have you considered other (statistics-based) metrics to evaluate the correctness? - Have the authors considered utilizing a regression model that directly assigns a single value to the semantic similarity instead of unintuitively having to aggregate the three classes of the NLI model?

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors adequately addressed limitations.

Summary

In this work, the authors propose Kernel Language Entropy, which shares a similar concept to semantic uncertainty but additionally considers semantic similarity. Based on this proposed theory, they design graph kernels and weight functions to estimate LLM uncertainty. Furthermore, they demonstrate that their method generalizes semantic entropy. The empirical results confirm the effectiveness of the proposed method across various tasks and LLMs.

Strengths

Originality: This paper extends semantic entropy to Kernel Language Entropy, which additionally takes into account the semantic similarity between clusters. The idea is well-motivated. Quality: This paper provides detailed theoretical analysis and designs several variants. The experimental results demonstrate the effectiveness of these designs. The experiments are extensive. Clarity: This paper is well-structured. Significance: This paper focuses on estimating LLM uncertainty, which is significant for LLM applications, as they often make mistakes in their responses. The techniques proposed in this work could be beneficial in addressing this issue.

Weaknesses

1. KLE requires iterative sampling from the LLM, which is computationally costly. This leads to delayed responses and limits its applicability. 2. It seems that this method can only estimate the confidence regarding whether the LM will correctly answer the query, but it cannot predict the confidence for a given answer. For example, in scenarios like ranking candidate answers, we can use P(True) or PE to estimate answer confidence, which KLE cannot do.

Questions

1. Which sample do you choose as the final answer among multiple samples, the answer in the biggest cluster or just a random one? I did not find this detail (perhaps I missed it), but it is important. 2. Since the answer correctness is determined by an 8b model, I am curious about how reliable the predicted label is. From my previous experience, even GPT-3.5 is not capable of reliably estimating the correctness of model responses, especially when the responses are phrases. Tian et al. [1] also noted a similar issue, as seen in their Appendix C. [1]. Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback. 3. Can this method be applied to long-form responses? Considering that long-form responses typically consist of multiple claims. 4. Missing the following related work: Language Models (Mostly) Know What They Know LitCab: Lightweight Language Model Calibration over Short- and Long-form Responses

Rating

6

Confidence

2

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors acknowledge the issue of computational cost. Investigating ways to elicit confidence from the LLM itself could be a possible direction for addressing this.

Summary

This paper is highly motivated by and heavily draws from Kuhn et al. (ICLR, 2023) “Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation.” In Kuhn’s original paper they propose an unsupervised way to calculate the semantic uncertainty of LLMs by (1) generating a set of outputs from an LLM, (2) clustering these outputs by semantic equivalence via an NLI model, and (3) plugging in these clusters to an equation for “semantic entropy.” This paper proposes an extension of the strict clusters of Kuhn et al.~by creating a “semantic graph” and calculate the “graph kernel” for the uncertainty metric. Thus, the authors attempt to measure the semantic entropy *between* clusters rather than just *within* clusters (the latter which is the approach of the previous work, Kuhn et al. (2023)). The authors provide a lot of math and theory trying to justify that their generalization from Kuhn et al. is meaningful. However, the empirical experiments show modest to no performance gains from their generalization on real-world QA datasets and LLMs.

Strengths

1. The authors have crafted a very extensive empirical set-up with 12 different LLMs on five datasets. They also get 10 LLM outputs per input and also obtain confidence intervals over 1000 bootstrap resamples (line 286-287). They combine this with five different baseline models for comparison to their proposed methods. I commend the authors on this extensive and painstaking experimental set-up. 2. The authors seem very well-versed in the previous literature and identify a clear gap in Kuhn et al.: that the “hard clustering” of Kuhn et al. misses what could be a softer clustering of semantic similar (which the authors tackle by constructing a semantic graph with weights between clusters).

Weaknesses

1. **The claims are not backed by strong enough evidence.** On line 59, the authors claim their approach achieves SoTA results. However, the empirical results (Table 1) are little to modest gains over baselines. Additionally, the bolding in Table 1 is misleading. Results should only be bolded if the method’s confidence interval is non-overlapping the confidence intervals of other methods (which they are not). For example, in Table 1 for AUROC on BioASQ, $0.88 \pm 0.03$ for KLE (K_FULL) is overlapping with P(True) at $0.86 \pm 0.03$. Likewise for SVAMP AUROC with $0.77 \pm 0.02$ for KLE (K Heat) and ER at $0.75 \pm 0.02$. This also makes me skeptical of how the authors are calculating the “win rates” for the other figures as well. 2. Additionally the authors do not investigate the **error/accuracy of intermediate models** that the experimental set-up relies upon. A key part of the authors pipeline is using DeBERTa-Large-MNLI to predict whether LLM outputs entail one another and create their semantic graph (line 262). However, DeBERTa-Large-MNLI is also an imperfect model. What was the accuracy of this model on the domains/datasets in the authors’ empirical pipeline? Are there ways to propagate uncertainty from this intermediate NLI model downstream to the final uncertainty calculations of other LLM’s outputs? 3. Additionally, see the questions below.

Questions

1. In the abstract, you motivate this work by saying “by detecting factually incorrect model responses, commonly called hallucinations.” Yet, you never actually show that you detect hallucinations (which require world knowledge that is external and more complex than the “semantic uncertainty” you’re actually targeting). How do you justify this disconnect? 2. On line 25 you cite two works that you use to justify “As LLM predictions tend to be well-calibrated.” However there is an *enormous* body of literature that shows the opposite. I would recommend hedging on this statement or providing citations of the opposite (non-calibration) findings. 3. Figure 1 lacks some details and motivation. In this example, I would not expect the named entity outputs, (e.g., “Laplace” or “Kolmogorov and Laplace”) to have any other lexical variants that have similar semantic meaning because these are named entities. In this figure, what does the little boxes next to “Semantic Kernels” represent? I would recommend explaining this more (e.g., I think you’re implying that blue means more similarity between particular clusters?) 4. In Figure 3’s caption, please explain why only “values larger than or equal to 0.62” correspond to a p-value less than 0.05. 5. I would recommend explaining how you are calculating AUPRC and why it is important. I know Kuhn et al. also use this metric but you do not make clear what this metric is in your standalone work. From re-reading Kuhn et al., I took away that they calculated an “entropy score” to predict whether a model’s answer to a question is correct. They vary the threshold of the entropy score for correctness prediction to get AUROC.

Rating

4

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

Addressed.

Response

> Statistical significance is achieved primarily by repeating the experiment with many different models and datasets "Statistical significance" has a precise, technical meaning as in [Berg-Kirkpatrick 2012](https://aclanthology.org/D12-1091.pdf). Per my comment "Results should only be bolded if the method’s confidence interval is non-overlapping the confidence intervals of other methods (which they are not)", in each of the 5 datasets, how many times did your method have better point estimates and non-overlapping CIs with the baselines' for *both* metrics?