GENUINE : Graph Enhanced Multi-level Uncertainty Estimation for Large Language Models (2025)

Abstract: Uncertainty estimation is essential for enhancing the reliability of Large Language Models (LLMs), particularly in high-stakes applications. Existing methods often overlook semantic dependencies, relying on token-level probability measures that fail to capture structural relationships within the generated text. We propose GENUINE: Graph ENhanced mUlti-level uncertaINty Estimation for Large Language Models, a structure-aware framework that leverages dependency parse trees and hierarchical graph pooling to refine uncertainty quantification. By incorporating supervised learning, GENUINE effectively models semantic and structural relationships, improving confidence assessments. Extensive experiments across NLP tasks show that GENUINE achieves up to 29% higher AUROC than semantic entropy-based approaches and reduces calibration errors by over 15%, demonstrating the effectiveness of graph-based uncertainty modeling. The code is available at https://github.com/ODYSSEYWT/GUQ.

## introduction large language models (llms) have demonstrated remarkable capabilities in conversation @xcite , logical reasoning @xcite , and scientific discovery @xcite . models such as gpt-4 @xcite , gemini @xcite , and deepseek @xcite , trained on vast corpora and aligned to human preferences, have significantly expanded the potential of ai. however, despite these advancements, llms are prone to well-documented reliability issues, including hallucinations and factual inaccuracies @xcite . these issues pose serious risks, particularly in high-stakes applications such as medical diagnosis @xcite , financial decision-making @xcite , and legal advisory systems @xcite , where figure 1 : an example highlighting the role of graph pooling to identify tokens' significance in uncertainty estimation. critical tokens are identified by graph pooling through dependency parsing tree and backpropagation of ground truth label, which makes the uncertainty task aware. a represents the adjacency matrix for a tree structure, where connected tree nodes are assigned value 1 while others are assigned value 0. g represents the pooling method, and f represents the information propagating through the pooling process. previous studies have explored various approaches to quantify uncertainty in llm outputs. some methods rely on self-evaluation through modified prompts @xcite , though they often inherit the model's biases. others use token-level uncertainty measures based on logits, entropy, or probability distributions @xcite @xcite . recent advancements, such as semantic entropy, cluster semantically equivalent generations and measure entropy as an uncertainty indicator @xcite . however, most existing methods treat all tokens equally, overlooking findings that certain tokens carry more semantic weight in determining output validity @xcite @xcite . recently, some approaches @xcite emphasize the different contributions of each token in uncertainty estimation. @xcite depends on external, smaller models to estimate token importance. while admitting that these smaller models can capture the semantics between different tokens. they inherently operate independently of the llm's internal representations, which introduce inconsistencies, misinterpret token dependencies @xcite . besides, using an external model to estimate semantic importance also adds significantly more computational cost and latency, especially in longer contexts. with the recognition of these limitations, we propose to use semantic parsing trees to help identify the contributions of different tokens, as they purely represent the semantic meaning between different tokens, and recent studies @xcite have demonstrated that semantic structure can further improve llms' performance. to illustrate this issue, consider the example in fig. 1 . a user inquires about legal items to carry in the united states, but the model responds with a list of illegal items, such as a gun, knife, and club. the misunderstanding stems from the token "legal," which is central to the query's meaning. a minor modification, replacing the word legal with illegal, would render the response appropriate. this example underscores two insights: certain tokens are disproportionately influential in determining output validity. dependency parse trees effectively capture the hierarchical structure of sentence meaning by identifying core decision points. building on these insights, we propose leveraging dependency parse trees and graph pooling techniques to infer llm prediction uncertainty in a structured and interpretable manner. modeling uncertainty estimation as a graphbased problem offers several advantages. graphs inherently capture dependencies between generated tokens, reflecting the autoregressive nature of llms, where each token influences subsequent ones. by representing an llm response as a struc-tured graph, we can propagate and aggregate critical information across tokens, ensuring that semantically significant tokens contribute more substantially to the overall uncertainty estimate. however, this approach introduces several challenges. determining the optimal graph structure that accurately represents token dependencies remains an open question. selecting appropriate graph pooling techniques that summarize uncertainty information effectively without losing essential context is difficult. addressing these challenges is essential to fully realize the potential of graph-based uncertainty estimation. our approach integrates multiple uncertainty features to enhance robustness. specifically, we utilize probability distributions, entropy-based measures, and llm embeddings to model uncertainty. we introduce a hierarchical strategy to address the challenge of aggregating uncertainty over longform text. we construct a dependency parse tree for each sentence to extract structural and semantic relationships. we merge sentence-level trees into a document-level graph by connecting their root nodes. we apply graph pooling techniques to model uncertainty across the entire paragraph efficiently. genuine involves learning pooling functions that adaptively fuse different features, capturing both local and global dependencies within the text. experimental results prove that genuine outperforms other baselines, highlighting the critical role of structural relationships in uncertainty estimation. furthermore, we compare the effectiveness of probability-based and embedding-based features across various datasets and llms, offering insights into their respective utilities. given that commercial llms typically provide only probabilityrelated features, our findings suggest an intriguing direction for future research. exploring whether open-source llms, which offer both probability and embedding features, can facilitate superior uq compared to their commercial counterparts. the following are our main contributions: • we highlight the role of semantically significant tokens in uncertainty estimation, demonstrating how structural relationships can enhance model uncertainty assessment. ## background this section defines the problem, provides the necessary background, and features helpful for uncertainty estimation in llms, laying the foundation for our proposed approach. ## approach this section details our approach, including graph formulation, hierarchical learning, and joint optimization, enabling a more structured and contextaware uncertainty estimation for llms. ## experiments this section evaluates genuine across multiple dimensions: (1) effectiveness in assessing uncertainty (section 5.2), (2) an ablation study to analyze the role of two modules (section 5.3), (3) a scalability test to assess computational efficiency (section 5.4), (4) the impact of dependency parse trees on uncertainty estimation (appendix 5.6), (5) a parameter analysis to determine the sensitivity of genuine to hyperparameter tuning (appendix b.4), (6) the impact of llm parameters on genuine's uncertainty estimation performance (appendix b.5), and (7) the impact of training dataset size and noisy labels on genuine's performance (section 5.5 and appendix b.6). due to space constraints, the results on dimensions 4, 5, 6, and 7 are presented in appendix b. ## conclusion this paper introduces dependency-based semantic structures for uncertainty estimation in llms. our findings prove that incorporating structural information enhances uncertainty modeling, leading to more accurate and calibrated estimates. gen-uine outperforms existing uncertainty estimation methods (auroc), particularly in long-form text generation, while also improving calibration metrics (ece, nll, brier). our results show that semantic graphs derived from dependency parse trees enhance uncertainty modeling, making them valuable for evaluating llms' outputs and guiding future improvements in adaptive uncertainty estimation in dynamic, real-world settings. the association for computational linguistics (volume 1: long papers), pages 1601-1611, vancouver, canada. association for computational linguistics. saurav kadavath, tom conerly, amanda askell, tom henighan, dawn drain, ethan perez, nicholas schiefer, zac hatfield-dodds, nova dassarma, eli tran-johnson, et al. 2022. language models (mostly) know what they know. corr. amir hosein khasahmadi, kaveh hassani, parsa moradi, leo lee, and quaid morris. 2020. memorybased graph networks. in international conference on learning representations. lorenz kuhn, yarin gal, and sebastian farquhar. 2023. semantic uncertainty: linguistic invariances for uncertainty estimation in natural language generation. in the eleventh international conference on learning representations. chen li, yang liu, fei liu, lin zhao, and fuliang weng. 2014. improving multi-documents summarization by sentence compression based on expanded constituent parse trees. in proceedings of the 2014 conference on empirical methods in natural language processing (emnlp), pages 691-701, doha, qatar. association for computational linguistics. chin-yew lin and franz josef och. 2004. automatic evaluation of machine translation quality using longest common subsequence and skip-bigram statistics. in proceedings of the 42nd annual meeting of the association for computational linguistics (acl-04), pages 605-612, barcelona, spain. stephanie lin, jacob hilton, and owain evans. 2022. teaching models to express their uncertainty in words. transactions on machine learning research.