PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Alexander Nikitin, Jannik Kossen, Yarin Gal, Pekka Marttinen

arXiv:2405.20003v1cs.LGcs.AIcs.CL

TL;DR

Reliable LLM deployment requires uncertainty estimates that reflect semantic meaning and help detect hallucinations, rather than merely lexical or syntactic variation. KLE encodes similarities among generated answers or semantic clusters with unit trace positive semidefinite kernels and uses von Neumann entropy, generalizing semantic entropy. Across 60 scenarios, KLE outperforms baselines, including in black-box settings, while requiring multiple samples and leaving other kernel choices and applications for future study.

  • Problem

    Uncertainty estimation for LLMs should capture semantic uncertainty relevant to answer correctness and hallucination detection rather than lexical or syntactic variation.

  • Method

    KLE encodes semantic similarities among generated answers or semantic clusters with unit trace positive semidefinite kernels and quantifies uncertainty using von Neumann entropy.

  • Results

    KLE outperforms baseline uncertainty methods across 60 scenarios spanning 12 models and five datasets, with KLE(KHEAT) operating without token-level probabilities.

  • Takeaways & Limitations

    KLE provides fine-grained semantic uncertainty estimation for both white-box and black-box LLMs and is an expressive generalization of semantic entropy.

  • Takeaways & Limitations

    KLE requires multiple LLM samples, and its evaluation focuses on NLI-based semantic kernels and selected natural-language-generation applications.

Abstract

from arXiv · show

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

1 Introduction

LLM hallucinations create risks in high-stakes applications, motivating uncertainty estimation that targets semantic meaning rather than lexical or syntactic variation. KLE addresses this gap with similarity-aware kernels, generalizes semantic entropy, and performs strongly across 60 evaluation scenarios.

  • Hallucinations in LLM generations pose significant risks in high-stakes applications, creating a need for reliable detection methods.
  • Uncertainty estimation can support safer deployment by identifying likely model errors and enabling abstention or human consultation.
  • Semantic uncertainty is more relevant to answer correctness than lexical or syntactic variation, while token likelihoods conflate these uncertainty types.
  • Semantic entropy treats semantically equivalent answers as identical, missing graded relations such as the closer similarity between “apple” and “granny smith.”
  • KLE encodes semantic similarities with unit trace positive semidefinite kernels and measures uncertainty using von Neumann entropy.
  • 60 scenarios across 12 models and five datasets show KLE methods outperforming baselines, while KLE(KHEAT) also works without token-level probabilities.

2 Background

Predictive entropy measures uncertainty over generated sequences, but natural-language uncertainty often concerns meaning rather than tokens. Semantic entropy addresses this by clustering semantically equivalent outputs, while retaining assumptions about the model's uncertainty sources.

  • Predictive entropy quantifies average uncertainty about an output random variable given an input.
  • The uncertainty framework assumes LLMs capture both epistemic and aleatoric uncertainty and does not attempt to distinguish between them.
  • For sequential models, output-sequence probabilities are built from conditional token probabilities and used to define predictive entropy over all possible sequences.
  • Naive predictive entropy measures uncertainty in token space, although the uncertainty relevant to natural-language generation often lies in semantic space.
  • Semantic entropy estimates uncertainty over clusters of outputs with identical semantic meaning, distinguishing paraphrases from answers with different meanings.
  • Semantic clusters are equivalence classes defined by a reflexive, symmetric, and transitive semantic relation, often estimated using bidirectional entailment.
  • When token likelihoods are unavailable, discrete semantic entropy approximates cluster probabilities using the fraction of generated texts assigned to each cluster.

3 Kernel Language Entropy

Kernel Language Entropy (KLE) estimates semantic uncertainty by encoding similarities among generated answers or semantic clusters in unit-trace positive semidefinite kernels and measuring their von Neumann entropy. It supports graph-based construction, practical hyperparameter selection, and theoretically generalizes semantic entropy while retaining greater expressiveness.

  • Method: KLE has direct and cluster-based variants: KLE operates on generated texts, whereas KLE-c operates on semantic-equivalence clusters.KLE-c is cheaper and more interpretable because it uses smaller kernels, while KLE is more general for non-trivial clusterings.
  • Method: KLE combines semantic kernels with von Neumann entropy to quantify uncertainty from fine-grained similarities among generations.The kernels are unit-trace positive semidefinite matrices, and the entropy is computed from their eigenvalues.
  • Semantic graph kernels: Semantic kernels encode similarities between generated texts or semantic clusters, allowing KLE to represent semantic distances rather than only equivalence relations.The construction uses semantic graphs derived with NLI models and graph kernels that incorporate graph locality.
  • Implementation: Computationally, KLE adds O(N^3) kernel and entropy operations to semantic entropy’s sampling and O(N^2) entailment computations.The paper states that this additional elementary-operation cost is negligible relative to LLM or entailment-model forward passes.
  • Semantic graph kernels: Entropy Convergence Plots provide a validation-free option for selecting heat- and Matérn-kernel hyperparameters by examining entropy as graph density increases.The method avoids parameter settings where the von Neumann entropy quickly collapses toward zero at large lengthscales.
  • Generalization: KLE can recover semantic entropy for any semantic clustering, while alternative kernels make it more expressive than semantic entropy.The theorem establishes equivalent kernels over texts and clusters, and KLE is more general than KLE-c for non-trivial clusterings.

4 Related Work

Related work covers uncertainty estimation, calibration, sequential-model uncertainty, and alternative hallucination-detection strategies. KLE is positioned as a complementary approach focused on fine-grained semantic uncertainty.

  • Uncertainty quantification: Prior work studies language entropy, calibration, uncertainty estimation in classification and sequential models, and uncertainty elicitation from LLMs.These approaches span calibration techniques, performance improvements from uncertainty measurement, and prompted or fine-tuned uncertainty statements.
  • Hallucination detection: Hallucination detection also uses external knowledge bases, hidden-state interventions, probes, and fine-tuning beyond model-uncertainty methods.The paper describes these directions as distinct alternatives to uncertainty estimation.
  • KLE’s position: KLE is complementary to several hallucination-detection directions and can be combined with them sequentially or used to improve them.Its focus is estimating more fine-grained semantic uncertainty.

5 Experiments

Experiments evaluate KLE across 60 dataset-model scenarios, finding that KLE variants outperform baselines while supporting black-box use and practical hyperparameter selection.

  • Datasets and Models: Experiments cover 60 dataset-model pairs across knowledge, biomedical, search-question, and mathematical natural language generation tasks.The evaluation includes TriviaQA, SQuAD, BioASQ, Natural Questions, and SVAMP.
  • Baselines: KLE is compared with semantic entropy, discrete semantic entropy, token predictive entropy, embedding regression, and P(True).The comparison uses established uncertainty-quantification baselines for predicting response correctness.
  • Main Results: KLE(KHEAT) and KLE(KFULL) outperform the baselines across 60 scenarios, with KLE(KHEAT) achieving the strongest overall results.The main comparison uses pairwise win rates and a binomial significance test; values at least 0.62 indicate p < 0.05.
  • Main Results: KLE(KHEAT) does not require token-level probabilities, enabling evaluation in black-box LLM settings.The reported result concerns the best-performing method in the experiments.
  • Hyperparameters: Default hyperparameters perform similarly to validation-set selection, supporting entropy-convergence-based selection without validation data.The comparison uses 100 validation samples per dataset except SVAMP, where default hyperparameters are used.
  • Design Choices: KLE improves over semantic entropy because its kernel metric represents similar but non-equivalent answers as semantically related.Semantic entropy separates such answers into different clusters and can therefore assign higher uncertainty.

6 Discussion

The discussion presents KLE as a fine-grained generalization of semantic entropy for more reliable LLM uncertainty estimation, while identifying sampling cost and scope boundaries.

  • Discussion: KLE encodes similarity in the semantic space of answers through semantic kernels, providing fine-grained uncertainty estimation and generalizing semantic entropy.The paper also studies NLI-based semantic graphs and kernel hyperparameters.
  • Broader Impact: More accurate uncertainty estimates can filter out a proportion of erroneous LLM outputs in applications requiring safer and more reliable use.This is presented as a broader impact of the method.
  • Limitations: KLE requires multiple LLM samples, increasing generation cost; its NLI-based kernels and applicability to code generation also require further evaluation.The paper notes that other semantic kernels, such as embedding-based kernels, warrant investigation.

Supplementary Material: Kernel Language Entropy: Fine-grained Uncertainty

The supplementary material supplies foundational definitions and linear-algebra results used in the paper’s kernel analysis and proofs.

  • Kernel Definitions: A positive semidefinite kernel is defined on a nonempty set through a symmetric function satisfying the positive-semidefiniteness condition.For finite sets, the kernel is represented by a positive semidefinite matrix of size |X|.
  • Linear Algebra: The supplementary results characterize eigenvalues of block-diagonal matrices as the combined eigenvalues of their diagonal blocks.The determinant factorization provides the corresponding proof route.
  • Linear Algebra: The all-ones matrix lemma supplies the eigenvalue structure needed for analyzing kernel blocks.The cited lemma states that an all-ones matrix has one nonzero eigenvalue and the remaining eigenvalues equal to zero.
  • Semantic Clustering: An equivalence relation is introduced as a binary relation that satisfies the standard relation properties, including transitivity.The displayed supplementary passage explicitly gives the transitivity condition.

B Theoretical Results and Proofs

The theoretical results construct kernels whose von Neumann entropy equals semantic entropy, proving that KLE and KLE-c generalize the clustering-based method.

  • KLE: For any semantic clustering, a semantic kernel over texts exists whose von Neumann entropy equals semantic entropy.The proof constructs a block-diagonal kernel with one block per semantic cluster.
  • KLE: The constructed block-diagonal kernel has blocks sized by cluster membership and satisfies positive semidefiniteness and unit trace.These properties ensure it is a valid semantic kernel for the entropy construction.
  • KLE: The eigenvalues of each block yield the cluster contribution -p(Ci|x) log p(Ci|x) to von Neumann entropy.The remaining eigenvalues in each block are zero, using the convention 0 log 0 = 0.
  • KLE-c: For any semantic clustering, a kernel over semantic clusters also exists whose von Neumann entropy equals semantic entropy.This establishes the corresponding generalization result for KLE-c.
  • Implication: The theorems provide an explicit semantic-kernel form that recovers semantic entropy, rather than only asserting an abstract generalization.The same construction shows that KLE can reproduce the earlier uncertainty measure.

C Kernel Hyperparameters

The appendix examines kernel hyperparameter selection and illustrates KLE's fine-grained uncertainty estimates on an NQ example. Default choices and validation-based selection both support strong performance against existing methods.

  • Hyperparameter selection: Entropy convergence plots provide one strategy for selecting heat and Matérn kernel hyperparameters by examining von Neumann entropy across progressively denser graphs.The plots vary graph density by adding edges and relate entropy to the number of edges.
  • Hyperparameter selection: Default hyperparameters t = 0.3, α = 0.5, ν = 1, and κ = 1, as well as validation-based selection, outperform existing methods.The appendix reports this pattern across the investigated experimental comparisons.
  • Kernel choices: Both normalized and standard graph Laplacians can be used with heat and Matérn kernels.The degree matrix inverse is identified as the Moore-Penrose inverse in the displayed formulation.

D Additional Experimental Details

Additional details describe the kernel visualizations, experimental resources, dataset licenses, and the scope of the supplementary results.

  • Kernel visualizations: The appendix visualizes heat and Matérn kernels on a 2-d grid and reports their parameter settings as Heat Kernel (t = 1) and Matérn Kernel (ν = 5/2, κ = 3).These visualizations accompany the additional experimental results.
  • Hardware and resources: Llama 2 70B experiments used two NVIDIA A100 80GB GPUs, while the remaining models used one NVIDIA A100 80GB.Generation took one to seven hours per scenario, with evaluation taking roughly four additional hours.
  • Licenses: The paper releases its code under BSD-3-Clause-Clear and uses datasets distributed under several stated open licenses.The listed dataset licenses include CC BY 2.5, Apache 2.0, CC BY-SA 4.0, MIT, and CC BY-SA 3.0.

D.1 Models and datasets

The experiments use five question-answering and reasoning datasets and a diverse model set, including models with varying accuracy. KLE is reported to remain effective across these varied scenarios, especially for instruction-tuned models.

  • Datasets: The evaluation uses TriviaQA, NQ, SQuAD, BioASQ, and SVAMP.The appendix provides samples from each dataset used in the experimental evaluation.
  • Models: The models span varying accuracy levels across tasks, which is relevant because uncertainty methods should work regardless of downstream model effectiveness.The appendix presents model accuracy alongside the evaluation scenarios.
  • Models: KLE's reported efficacy across diverse models supports its applicability to settings where model performance fluctuates.This conclusion is stated in the supplementary discussion of real-world deployment scenarios.
  • Instruction tuning: KLE significantly outperforms existing methods on instruction-tuned models but only marginally outperforms them on non-instruction-tuned models.The authors hypothesize that calibration differences may contribute to this split and note that DSE significantly outperforms SE on an instruction-tuned AUROC split.

D.3 Detailed results of UQ

Detailed results compare uncertainty quantification methods across models and datasets, while supplementary material distinguishes lexical, syntactic, and semantic variability. The reported comparisons favor KLE, with interpretation focused on semantic variation.

  • Detailed comparisons: Results are shown for a wide range of models across five datasets, separately covering non-instruction-tuned and instruction-tuned models.The appendix notes that ER failed for Llama 2 13B non-instruction-tuned experiments except BioASQ, with failed cases assigned zero scores.
  • Variability types: The paper distinguishes semantic, syntactic, and lexical variability when discussing variation in generated answers.The semantic focus is accompanied by a stated possibility of extending kernels to other text-analysis modalities.
  • Scenario summary: Figure D.5 summarizes 60 experimental scenarios comparing instruction-tuned and non-instruction-tuned models, with KLE methods labeled KLE(·).The figure caption identifies the comparison scope and method labels.
Loading 2405.20003v1…