# GENUINE: Graph Enhanced Multi-level Uncertainty Estimation for Large Language Models

arXiv: https://arxiv.org/abs/2509.07925 · HTML: https://mlsanity.com/paper/2509.07925/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 58 references that are in the map.
- First posted on arXiv 9 Sep 2025.

## Builds on (most cited first, 25 of 25)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Teaching Machines to Read and Comprehend](https://mlsanity.com/paper/1506.03340/) (2015)
- [Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback](https://mlsanity.com/paper/2305.14975/) (2023)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [CoQA: A Conversational Question Answering Challenge](https://mlsanity.com/paper/1808.07042/) (2018)
- [Trustworthy LLMs: a Survey and Guideline for Evaluating Large Language Models' Alignment](https://mlsanity.com/paper/2308.05374/) (2023)
- [Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling](https://mlsanity.com/paper/1703.04826/) (2017)
- [Uncertainty Quantification with Pre-trained Language Models: A Large-Scale Empirical Analysis](https://mlsanity.com/paper/2210.04714/) (2022)
- [Can ChatGPT Defend its Belief in Truth? Evaluating LLM Reasoning via Debate](https://mlsanity.com/paper/2305.13160/) (2023)
- [Uncertainty Estimation and Quantification for LLMs: A Simple Supervised Approach](https://mlsanity.com/paper/2404.15993/) (2024)
- [(A)I Am Not a Lawyer, But...: Engaging Legal Experts towards Responsible LLM Policies for Legal Advice](https://mlsanity.com/paper/2402.01864/) (2024)
- [Memory-Based Graph Networks](https://mlsanity.com/paper/2002.09518/) (2020)
- [Neural Extractive Text Summarization with Syntactic Compression](https://mlsanity.com/paper/1902.00863/) (2019)
- [Embedding Uncertain Knowledge Graphs](https://mlsanity.com/paper/1811.10667/) (2018)
- [Evaluating LLM -- Generated Multimodal Diagnosis from Medical Images and Symptom Analysis](https://mlsanity.com/paper/2402.01730/) (2024)
- [Do BERT-Like Bidirectional Models Still Perform Better on Text Classification in the Era of LLMs?](https://mlsanity.com/paper/2505.18215/) (2025)
- [Efficient Dependency-Guided Named Entity Recognition](https://mlsanity.com/paper/1810.08436/) (2018)
- [Rethinking Semantic Parsing for Large Language Models: Enhancing LLM Performance with Semantic Hints](https://mlsanity.com/paper/2409.14469/) (2024)

## Built on by (most cited first, 3 of 3)

- [A Systematic Evaluation of Black-Box Uncertainty Estimation Methods for Large Language Models](https://mlsanity.com/paper/2606.19868/) (2026)
- [Position: Uncertainty Quantification in LLMs is Just Unsupervised Clustering](https://mlsanity.com/paper/2605.19220/) (2026)
- [Bi-NAS: Towards Effective and Personalized Explanation for Recommender Systems via Bi-Level Neural Architecture Search](https://mlsanity.com/paper/2607.01387/) (2026)

## Abstract (arXiv)

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.