Abstract
Reliable uncertainty quantification (UQ) is critical for the safe deployment of Large Language Models (LLMs). Current black-box methods, such as Semantic Entropy (SE), often suffer from significant underestimation bias when sample sizes are small, as they overlook potential semantic categories not present in the sample. We introduce a hybrid estimator for "Semantic Alphabet Size" that integrates Good-Turing and spectral estimation techniques to account for these unobserved meanings. Our method demonstrates superior performance in reducing bias and detecting hallucinations across diverse benchmarks and models, including Gemma, Llama, and Mistral.
Introduction
Large Language Models are notorious for "hallucinating"—generating factually incorrect but confident-sounding responses. To deploy them safely, we need reliable Uncertainty Quantification (UQ). One popular approach is Semantic Entropy (SE), which involves sampling multiple responses from a model and clustering them by meaning. If the model provides many semantically different answers, it is likely uncertain.
However, most "black-box" SE methods suffer from a major flaw: they systematically underestimate uncertainty when sample sizes are small (e.g., only 10 samples). This happens because a small sample is unlikely to capture the full "alphabet" of possible meanings the model could produce. This paper addresses this gap by borrowing techniques from population ecology to estimate the size of the "unseen" semantic alphabet.
Methodology
The authors propose a way to estimate the Semantic Alphabet Size—the total number of unique meanings a model might generate for a given prompt—even if some of those meanings aren't present in the current sample.
- Semantic Clustering: Natural Language Inference (NLI) models group responses into semantic equivalence classes (e.g., "The sky is blue" and "It's blue" belong to the same class).
- Hybrid Alphabet Size Estimator ($|\hat{S}|_{Hybrid}$): This combines Good-Turing Estimation (using "singletons" to estimate unobserved categories) with Spectral Estimation (analyzing the eigenvalues of the response entailment graph Laplacian).
- Coverage-Adjusted Entropy: The estimated alphabet size is used to adjust standard entropy calculations via a Chao-Shen style estimator, scaling observed frequencies to account for the "missing" tail of the distribution.
Experimental Evaluation
The method was evaluated across several benchmarks:
- Standard QA: HotpotQA and SQuAD 2.0.
- Domain-Specific: BioASQ (biomedical questions).
- POTATO (Plethora Of accepTable cATegOries): A new synthetic dataset introduced in this paper featuring questions with a very high number of possible correct semantic answers (up to 700+), providing a rigorous stress test for alphabet size estimation.
Results and Key Insights
Reduced Bias in Uncertainty Estimation
The proposed hybrid DSE estimator significantly reduces the underestimation bias compared to standard methods. As shown in the figure below, the hybrid method tracks the "true" entropy much more closely than canonical Discrete Semantic Entropy (DSE) across multiple models (Gemma, Llama, Mistral, Phi).
Superior Hallucination Detection
In head-to-head comparisons for detecting incorrect responses (using AUROC), the hybrid alphabet size estimators outranked almost all other black-box UQ methods. Surprisingly, simply estimating the number of semantic categories (alphabet size) is often a better predictor of model incorrectness than calculating complex entropy metrics. This provides a highly interpretable signal: it literally represents how many different things the model thinks it could say.
Discussion and Limitations
While the hybrid estimator offers a significant step forward, it remains sensitive to the accuracy of the underlying NLI model used for clustering. If the NLI model fails to recognize semantic equivalence, uncertainty estimates will be inflated. Furthermore, like all diversity-based UQ, these methods struggle when a model is "confidently wrong"—consistently generating the same incorrect answer with zero diversity. Future work will explore the behavior of massive models (e.g., Llama-3-70B) in these under-sampled regimes.
Summary updated