Embedding Graph Kernel Entropy (EGKE): Fine-grained Hallucination Detection for LLMs from Embeddings

The gist: Embedding Graph Kernel Entropy (EGKE) proposes a variant of Kernel Language Entropy (KLE) that replaces its Natural Language Inference (NLI)-derived semantic graph with a Radial Basis Function (RBF) kernel applied to dense sentence embeddings, offering a symmetric and computationally efficient alternative for fine-grained hallucination detection in Large Language Models.

How it works

The proposed method addresses the computational overhead of NLI-based semantic comparison by replacing it with direct similarity computation in a continuous embedding space Embedding Graph Kernel Entropy (EGKE), a variant of Kernel Language Entropy (KLE) that replaces its NLI-derived semantic graph with a Radial Basis Function (RBF) kernel applied to dense sentence embeddings generated by a BGE embedding model, while retaining KLE’s graph Laplacian, heat kernel, and von Neumann entropy formulation unchanged By computing similarities directly in a continuous embedding space, the proposed method provides a symmetric and computationally efficient alternative to NLI-based semantic comparison.

The methodology involves four main stages for estimating semantic uncertainty

(Response preprocessing)

Generated responses often differ in capitalization, punctuation, or other superficial lexical characteristics that do not alter their semantic meaning, so each response is normalized by converting all text to lowercase and removing punctuation. Since many question-answer datasets contain short answers whose meanings depend heavily on the associated question, the question is concatenated with the cleaned response before encoding.

(Sentence embedding generation)

Each preprocessed response s˜i is transformed into a dense semantic vector using the pretrained embedding model BAAI/bge-large-en-v1.5 [16]. All responses corresponding to a question are encoded in a single batch, producing an embedding matrix E = [e1,..., en] T ∈ R n×d, where ei ∈ R d represents the embedding of response si and d is the embedding dimension.

(RBF similarity graph construction)

A fully connected weighted graph G = (V, E) is constructed over the n responses, where each pair of nodes (i, j) is connected by an edge with weight wij = exp − ei − ej2 / 2σ2. The squared Euclidean distance ei − ej2 is computed directly from the embedding tensors, and the resulting weight lies in (0, 1], attaining its maximum value of 1 when two responses are identical in embedding space and decaying toward 0 as they diverge. Unlike the NLI-based approach, which produces a sparse graph (edges only where entailment is detected), the RBF graph is fully connected, providing a smooth and globally consistent similarity structure over all response pairs.

(Heat kernel and von Neumann entropy computation)

Given the RBF-weighted graph G, the graph Laplacian is computed as L = D − W, where W is the weight matrix with entries Wij = wij and D is the diagonal degree matrix with Dii = P Σj Wij. The heat kernel is then derived as the matrix exponential of the scaled Laplacian Kt = e − tL, where t is a diffusion length-scale parameter. The kernel is then normalised to unit trace via Kˆij = p Kij / (Kii · Kjj · 1n). Embedding Graph Kernel Entropy (EGKE) is defined as the von Neumann entropy of this semantic kernel, EGKE(Kˆ) = −Σi λi log λi.

Contributions

The main contributions of this work are as follows

(NLI removal)

We remove the dependency on NLI, such as DeBERTa, based inference stage with an embedding-based semantic similarity mechanism using BGE representations and an RBF kernel. Unlike pairwise entailment inference, which requires a separate cross evaluation for each response pair and produces asymmetric relation scores, the proposed approach computes similarities directly in embedding space, yielding a symmetric similarity measure.

(Graph construction)

We construct a fully connected semantic graph from embedding-based response similarities and derive a heat kernel representation over the graph. This provides a continuous and globally consistent characterization of semantic relationships between generated responses.

(Uncertainty estimation)

Semantic uncertainty is estimated using von Neumann entropy computed over the resulting heat-kernel representation. This enables confabulation detection directly from semantic relationships encoded within the response graph.

Experimental Results

The proposed method is evaluated across 30 experimental setups—covering multiple question-answer datasets and open-weight LLM families—on both AUROC and AUARC. The evaluation utilized five question-answering benchmarks spanning distinct domains: TriviaQA [17], SQuAD [18], Natural Questions (NQ) [19], SVAMP [20], and BioASQ [21]. Experiments were conducted on six open-weight LLMs, including Falcon-7B and LLaMA2-7B. The evaluation metrics reported are AUROC and AUARC.

Discussion

Embedding-based similarity is a viable substitute for NLI Our method achieves the highest average AUROC (0.793) and AUARC (0.553) across all 30 model–dataset settings, outperforming all compared baselines in aggregate. It also wins against most baselines in the majority of settings, with particularly strong gains over probabilistic baselines such as P(True) and ER, while remaining competitive with semantic baselines such as SE and DSE across datasets and models. A symmetric, distance-based measure in embedding space is therefore sufficient to construct a semantic graph that captures meaningful disagreement among sampled responses, while avoiding the computational overhead of running a separately loaded cross-encoder over every response pair. The RBF bandwidth σ = 0.1 is consistently optimal. A small σ is therefore better able to distinguish these two regimes by assigning near-zero weight to all but the closest response pairs.

Limitations

The proposed method relies on the quality of the BGE embedding mode as a proxy for semantic similarity. For highly specialised domains such as biomedical QA, a general-purpose sentence encoder may not capture domainspecific semantic relationships as reliably as an NLI model fine-tuned on in-domain data. Additionally, the RBF kernel introduces a hyperparameter σ that, while consistent across our experiments, may require tuning for new domains or model families. Unlike the entropy convergence plots proposed in [6] for the heat kernel, no analogous principled selection criterion currently exists for the RBF bandwidth in this setting.

Conclusion

We proposed an embedding-based hallucination detection method, a variant of Kernel Language Entropy (KLE) [6] that replaces NLI-based pairwise similarity estimation with an RBF kernel over dense sentence embeddings. Rather than running a cross-encoder for every pair of sampled responses, all responses to a question are encoded in a single batched forward pass, and pairwise similarities are computed in closed form from Euclidean distances in embedding space. This produces a symmetric, continuously graded similarity structure that is fed directly into a graph Laplacian, heat kernel, and von Neumann entropy pipeline for hallucination scoring. Evaluated across 30 experimental scenarios spanning five QA benchmarks and six open-weight LLMs, our method achieves the highest average AUROC and AUARC among all compared methods, outperforming the KLE in 24 of 30 scenarios on AUROC and 22 of 30 on AUARC, and dominating token-level and self-assessment baselines in the large majority of scenarios <ref:

1. Bold semantic uncertainty estimation using EGKE: The system can estimate semantic uncertainty by computing von Neumann entropy of this semantic kernel, which is defined as EGKE(Kˆ) = −X i λ i log λ i. This provides a measure of whether the model's generated responses are semantically concentrated with low semantic uncertainty or show a more uniformly distributed eigenspectrum, reflecting greater semantic diversity among generated responses and therefore higher semantic uncertainty.

2. Replace NLI dependency with continuous similarity: The system can compute pairwise similarities by using an RBF kernel applied to dense sentence embeddings generated by a BGE embedding model, which is described as providing a symmetric and computationally efficient alternative to NLI-based semantic comparison. This avoids the overhead of running a separate cross-encoder forward pass for every response pair.

3. Leverage batched encoding for efficiency: The system can encode all responses corresponding to a question in a single batch, producing an embedding matrix E = [e1,..., en] (3), allowing pairwise distances are computed in closed form rather than relying on sequential inference.

4. Optimize similarity weighting via bandwidth selection: The system can dynamically select the RBF bandwidth parameter σ, noting that the optimal bandwidth is dataset and model dependent, and using the result from Table I showing that σ = 0.1 consistently achieved the highest average performance.

5. Improve selective prediction behavior: The system's uncertainty estimate can be used to achieve stronger selective prediction behavior compared to baselines, as shown by its superior AUARC win rate against Semantic Entropy (SE), which is noted as achieving a higher AUARC win rate without SE’s DeBERTa-based NLI component.

Hallucination detection is critical for ensuring the reliability of Large Language Models (LLMs) in real-world deployments. While recent works, such as Semantic Entropy (SE) and Kernel Language Entropy (KLE), identify hallucinations by measuring semantic disagreement across multiple generated responses using Natural Language Inference (NLI) models, these methods depend on separately loaded NLI classifiers to estimate pairwise semantic similarity, introducing significant computational overhead. We propose Embedding Graph Kernel Entropy (EGKE), a variant of Kernel Language Entropy (KLE) that replaces its NLI-derived semantic graph with a Radial Basis Function (RBF) kernel applied to dense sentence embeddings generated by a BGE embedding model, while retaining KLE's graph Laplacian, heat kernel, and von Neumann entropy formulation unchanged. By computing similarities directly in a continuous embedding space, the proposed method provides a symmetric and computationally efficient alternative to NLI-based semantic comparison. We evaluate our approach across 30 experimental setups (covering multiple question-answer datasets and open-weight LLM families) using both AUROC and AUARC, and demonstrate that this RBF-based method achieves competitive hallucination detection performance against state-of-the-art methods.