Uncertainty Quantification for Black-Box LLMs via Star Graphs Connectivity: Exploring Alternatives for Semantic Density

Abstract

Large language models (LLMs) excel in natural language processing but are prone to generating hallucinations. One approach to detecting hallucinations in LLM outputs is uncertainty quantification. These methods assign relative scores to generated responses, indicating their likelihood of being correct or hallucinatory. A well-known technique is Semantic Density, which uses the “density” of a target response in the semantic space as a proxy for its confidence. This approach addresses two limitations of Semantic Entropy: its uncertainty score is prompt-wise, and it only checks for binary semantic equivalence rather than capturing nuanced differences between two responses. Despite the success of Semantic Density, it relies on token-level probabilities, which are inaccessible in black-box LLMs, limiting its broader applicability. In this paper, we propose alternatives to Semantic Density by reconstructing uncertainty indicators from Semantic Entropy. We introduce a weighted star graph centered on the target response, reflecting the fine-grained semantic relationships between the target and other semantics within the output space. We propose using the connectivity of this star graph as a proxy for the confidence of the target response. Specifically, we present three methods based on graph density, the spectral radius of the adjacency matrix, and the spectral radius of the graph Laplacian. Our analysis shows that our approaches have a comparable computational cost to Semantic Density but outperform it in terms of both applicability and performance, making them robust alternatives.