Semantic Token Clustering for Efficient Uncertainty Quantification in Large Language Models Qi Cao, Andrew Gambardella, Takeshi Kojima, Yutaka Matsuo, Yusuke Iwasawa Abstract Large language models (LLMs) have demonstrated remarkable capabilities across diverse tasks. However, the truthfulness of their outputs is not guaranteed, and their tendency toward overconfidence further limits reliability. Uncertainty quantification offers a promising way to identify potentially unreliable outputs, but most existing methods rely on repeated sampling or auxiliary models, introducing substantial computational overhead. To address these limitations, we propose Semantic Token Clustering (STC), an efficient uncertainty quantification method that leverages the semantic information inherently encoded in LLMs. Specifically, we group tokens into semantically consistent clusters using embedding clustering and prefix matching, and quantify uncertainty based on the probability mass aggregated over the corresponding semantic cluster. Our approach requires only a single generation and does not depend on auxiliary models. Experimental results show that STC achieves performance comparable to state-of-the-art baselines while substantially reducing computational overhead. 1 1 1 Code will be available at https://github.com/ccqq77/semantic_token_clustering . 1 Introduction Large language models (LLMs) achieve impressive performance across diverse tasks but still fail to guarantee factual accuracy, which is a critical limitation, especially in high-stakes domains such as healthcare, law, and science. Their tendency to generate plausible-sounding yet incorrect responses further complicates error detection, underscoring the need for effective uncertainty quantification to identify and manage unreliable outputs. A natural approach is to allow LLMs to explicitly express their uncertainty verbally. However, due to the well-known overconfidence problem Xiong et al. 2024 , LLMs often exhibit high confidence even when their responses are plausible but incorrect. Recent studies have attempted to address this issue by quantifying uncertainty in natural language generation, for example, by sampling multiple generations, leveraging external natural language inference (NLI) models to estimate the semantic relationships among them, and measuring uncertainty using semantic dispersion Kuhn et al. 2023 ; Farquhar et al. 2024 ; Lin et al. 2024 . Despite their effectiveness, most prior approaches require repeated sampling or auxiliary models Kuhn et al. 2023 ; Farquhar et al. 2024 ; Lin et al. 2024 , introducing substantial computational overhead and failing to fully exploit the semantic structure encoded in the LLM’s internal representations. In this work, we propose Semantic Token Clustering (STC) , a novel and efficient approach for uncertainty quantification that directly leverages internal semantic representations, thereby eliminating the need for external models and multiple generations. Our method achieves performance comparable to state-of-the-art baselines while substantially reducing computational overhead. Our method offers three key advantages: Leveraging internal representations. The method employs token embedding clustering to link the internal semantic representations of LLMs with uncertainty quantification, enabling more effective use of their inherent semantic structure. Easy and self-contained implementation. The method requires no fine-tuning, supervised data collection, or external models, relying solely on unsupervised uncertainty quantification in a self-contained manner. It can therefore be readily applied to any off-the-shelf white-box LLM. Computational efficiency. Our approach quantifies uncertainty from a single generation, and computationally intensive steps such as embedding clustering are performed offline, minimizing inference-time overhead. It is particularly suitable for resource-constrained and low-latency scenarios. 2 Related Work Existing uncertainty quantification methods for LLMs can be broadly categorized into supervised and unsupervised approaches. Supervised methods typically train additional probes to predict the correctness of generations ( Azaria and Mitchell 2023 ; Liu et al. 2024 ) . However, these methods require labeled data and additional training, and they are not guaranteed to generalize to out-of-distribution data, which limits their flexibility and applicability. In contrast, unsupervised methods quantify uncertainty directly from model outputs, logits, or internal states without additional training. Logit-based metrics, such as Perplexity ( Fomicheva et al. 2020 ) , compute uncertainty scores directly from token-level logits. Sampling-based methods such as Semantic Entropy ( Kuhn et al. 2023 ; Farquhar et al. 2024 ) , EigenScore ( Chen et al. 2023 ) , and various semantic dispersion metrics ( Lin et al. 2024 ) quantify uncertainty by measuring the semantic diversity/consistency across multiple stochastic generations. Closely related to our work, Claim Conditioned Probability (CCP) ( Fadeeva et al. 2024 ) quantifies token-level uncertainty from a single generation but relies on an NLI model, incurring significant computational overhead. Despite their effectiveness, existing unsupervised methods either overlook semantic consistency or rely on multiple generations and external models. In contrast, our approach directly leverages semantic information inherently encoded in LLMs, enabling efficient and self-contained uncertainty quantification from a single generation. Table 1 summarizes the key differences between our method and existing baselines. Table 1: Key differences between the proposed uncertainty quantification method and existing methods. Semantic Aware Single Sample External Model Free Overhead Perplexity ✗ ✓ ✓ Low P(True) ✗ ✓ ✓ Medium Predictive Entropy ✗ ✗ ✓ High LN Entropy ✗ ✗ ✓ High TokenSAR ✓ ✓ ✗ Medium ConU ✓ ✗ ✗ High Semantic Entropy ✓ ✗ ✗ High Ecc ✓ ✗ ✗ High EigV ✓ ✗ ✗ High Deg ✓ ✗ ✗ High EigenScore ✓ ✗ ✓ High SentenceSAR ✓ ✗ ✗ High SAR ✓ ✗ ✗ High CCP ✓ ✓ ✗ High Ours ✓ ✓ ✓ Low 3 Problem In this study, we focus on uncertainty quantification in LLMs for specific generations. Specifically, given an input prompt x and a generated response y , the goal is to estimate a score aligned with the risk that the response y is incorrect. Formally, the uncertainty estimate can be expressed as: \mathcal{U}(x,y)=g\!\left(\hat{p}\big(C=0\mid x,y\big)\right), (1) where C is a binary correctness indicator, and g is a monotonically increasing link function. In this study, we aim to develop a computationally efficient method to quantify uncertainty directly from a single generation. Figure 1: Illustration of the proposed method. Token embedding clustering is performed in the pre-computation stage. During inference, we aggregate next-token probability mass over embedding-clustered and prefix-matched tokens to quantify uncertainty. Figure 2: Performance comparison between our method and baseline approaches across different models and datasets. For clarity, only the top seven methods ranked by performance are shown in each subfigure, with methods ordered by descending performance. Metric: AUROC. Figure 3: Efficiency comparison across methods. The performance (AUROC) and relative execution time overhead (%) are plotted on the y-axis and x-axis, respectively, illustrating the efficiency of the proposed method. The relative execution time overhead represents the additional execution time required for uncertainty quantification relative to basic inference. For clarity, only the top ten methods ranked by performance are shown in each subfigure. 4 Methodology Our method quantifies uncertainty using the model’s next-token probability distribution at each decoding step, as it directly reflects uncertainty in token selection. Since probability mass is often distributed across multiple semantically consistent tokens (e.g., “TV” vs. “television”), the probability of a single token may underestimate the model’s confidence. To address this, we cluster candidate tokens based on semantic similarity and aggregate their probability mass within each cluster to obtain a cluster-based estimate. As shown in Figure 1 , our method measures token-level uncertainty by grouping tokens using embedding clustering and prefix matching. The uncertainty score is computed through a two-stage process: Pre-computation Stage. Inspired by recent work on text embedding, in particular LENS Lei et al. 2025 , we group tokens into semantically consistent clusters based on their embeddings using an unsupervised clustering algorithm, such as Agglomerative Clustering Müllner 2011 (implementation details are provided in Appendix C ). Examples of these clusters are shown in Appendix A . The clustering is performed offline, enabling the resulting clusters to be directly used during inference without introducing additional computational overhead. Inference Stage. During inference, we aggregate token probabilities within each semantic cluster at every decoding step to compute an uncertainty score. Because tokenization does not always align with meaningful semantic units, individual tokens may lack sufficient semantic information when considered in isolation. To address this, we incorporate additional semantic information from subsequent context through prefix matching. Specifically, we check whether a candidate token serves as a prefix of the subsequent generation. For example, regardless of whether the subsequent generation is “television” as a single token or split into “tele” and “vision”, the tokens “television”, “tele”, and “televis” are all considered prefix-matched. This process enhances the semantic consistency of clusters by grouping tokens that remain consistent with the subsequent generation. Formally, the embedding-clustered token set is defined as \mathcal{T}_{i}^{\mathit{e}}=\{\,t\in\mathcal{V}\mid\text{cluster}(t)=\text{cluster}(y_{i})\,\}, (2) where \mathcal{T}_{i}^{\mathit{e}} denotes the set of tokens identified through embedding clustering, \mathcal{V} denotes the model vocabulary, and \text{cluster}(\cdot) maps each token to its corresponding semantic cluster. Similarly, the prefix-matched token set is defined as \mathcal{T}_{i}^{\mathit{p}}=\{\,t\in\mathcal{V}\mid\text{norm}(y_{i:})~\mathrel{\text{startswith}}~\text{norm}(t)\,\}, (3) where \mathcal{T}_{i}^{\mathit{p}} denotes the set of tokens identified through prefix matching, \text{norm}(\cdot) performs case- and space-insensitive normalization, and y_{i:} denotes the substring of the remaining output sequence starting from position i . At each decoding step, the clustered probability mass is computed by aggregating the probabilities of all semantically consistent tokens: \hat{p}_{c}(y_{i}\mid x,y_{