Estimating Semantic Alphabet Size for LLM Uncertainty Quantification

Lucas H. McCabe, Rimon Melamed, Thomas Hartvigsen, H. Howie Huang

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.

  1. 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).
  2. 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).
  3. 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.
High-level schematic of semantic alphabet size estimation: (A) Sampling from the LLM, (B) Clustering into semantic categories, and (C) Estimating the full alphabet size including unobserved classes.

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).

Ratios of DSE estimators to true entropy (SE*). Values below 1.0 indicate underestimation. The hybrid method (solid line) significantly outperforms canonical DSE (dotted line) at low sample sizes (n).

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

BibTeX
@inproceedings{mccabe2026estimating,
  author = {Lucas H. McCabe and Rimon Melamed and Thomas Hartvigsen and H. Howie Huang},
  title = {{Estimating Semantic Alphabet Size for LLM Uncertainty Quantification}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=uYK6GPVg1O},
}
Figure