# Graph-based Uncertainty Metrics for Long-form Language Model Outputs

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 28 Oct 2024.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [FActScore: Fine-grained Atomic Evaluation of Factual Precision in Long Form Text Generation](https://mlsanity.com/paper/2305.14251/) (2023)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [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)
- [SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Models](https://mlsanity.com/paper/2303.08896/) (2023)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answering](https://mlsanity.com/paper/2012.00955/) (2020)
- [Chain-of-Verification Reduces Hallucination in Large Language Models](https://mlsanity.com/paper/2309.11495/) (2023)
- [Calibration of Pre-trained Transformers](https://mlsanity.com/paper/2003.07892/) (2020)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [Surface Form Competition: Why the Highest Probability Answer Isn't Always Right](https://mlsanity.com/paper/2104.08315/) (2021)
- [Fine-Tuning or Retrieval? Comparing Knowledge Injection in LLMs](https://mlsanity.com/paper/2312.05934/) (2023)
- [Enhancing LLM Factual Accuracy with RAG to Counter Hallucinations: A Case Study on Domain-Specific Queries in Private Knowledge-Bases](https://mlsanity.com/paper/2403.10446/) (2024)
- [Linguistic Calibration of Long-Form Generations](https://mlsanity.com/paper/2404.00474/) (2024)
- [Fine-Grained Self-Endorsement Improves Factuality and Reasoning](https://mlsanity.com/paper/2402.15631/) (2024)
- [Unsupervised Improvement of Factual Knowledge in Language Models](https://mlsanity.com/paper/2304.01597/) (2023)

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

- [A Survey on Uncertainty Quantification of Large Language Models: Taxonomy, Open Research Challenges, and Future Directions](https://mlsanity.com/paper/2412.05563/) (2024)
- [SAFE: Multitask Failure Detection for Vision-Language-Action Models](https://mlsanity.com/paper/2506.09937/) (2025)
- [Uncertainty Quantification for Language Models: A Suite of Black-Box, White-Box, LLM Judge, and Ensemble Scorers](https://mlsanity.com/paper/2504.19254/) (2025)
- [LoVeC: Reinforcement Learning for Better Verbalized Confidence in Long-Form Generations](https://mlsanity.com/paper/2505.23912/) (2025)
- [UNCLE: Benchmarking Uncertainty Expressions in Long-Form Generation](https://mlsanity.com/paper/2505.16922/) (2025)
- [Why Semantic Entropy Fails: Geometry-Aware and Calibrated Uncertainty for Policy Optimization](https://mlsanity.com/paper/2605.21801/) (2026)
- [Fine-Grained Uncertainty Quantification for Long-Form Language Model Outputs: A Comparative Study](https://mlsanity.com/paper/2602.17431/) (2026)
- [All Roads Lead to Rome: Graph-Based Confidence Estimation for Large Language Model Reasoning](https://mlsanity.com/paper/2509.12908/) (2025)
- [SAGE: Answer-Conditioned Uncertainty Targets for Verbal Uncertainty Alignment](https://mlsanity.com/paper/2606.11512/) (2026)
- [Embedding Trust: Semantic Isotropy Predicts Nonfactuality in Long-Form Text Generation](https://mlsanity.com/paper/2510.21891/) (2025)
- [Beyond Single-Turn Confidence: Trajectory-Adapted Uncertainty Quantification for LLM Agents](https://mlsanity.com/paper/2608.11552/) (2026)

## Abstract (arXiv)

Recent advancements in Large Language Models (LLMs) have significantly improved text generation capabilities, but these systems are still known to hallucinate, and granular uncertainty estimation for long-form LLM generations remains challenging. In this work, we propose Graph Uncertainty -- which represents the relationship between LLM generations and claims within them as a bipartite graph and estimates the claim-level uncertainty with a family of graph centrality metrics. Under this view, existing uncertainty estimation methods based on the concept of self-consistency can be viewed as using degree centrality as an uncertainty measure, and we show that more sophisticated alternatives such as closeness centrality provide consistent gains at claim-level uncertainty estimation. Moreover, we present uncertainty-aware decoding techniques that leverage both the graph structure and uncertainty estimates to improve the factuality of LLM generations by preserving only the most reliable claims. Compared to existing methods, our graph-based uncertainty metrics lead to an average of 6.8% relative gains on AUPRC across various long-form generation settings, and our end-to-end system provides consistent 2-4% gains in factuality over existing decoding techniques while significantly improving the informativeness of generated responses.