Lune

NeurIPS2024Top-tier venue

Graph-based Uncertainty Metrics for Long-form Language Model Generations

Mingjian Jiang, Yangjun Ruan, Prasanna Sattigeri, Salim Roukos, Tatsunori B. Hashimoto

Abstract

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 uncertaintyaware 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 1 .

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Rethinking Uncertainty Estimation in LLMs: A Principled Single-Sequence Measure cites Uncertainty Estimation in Autoregressive Structured Prediction
  • Self-Consistency Improves Chain of Thought Reasoning in Language Models cites Language Models are Few-Shot Learners
  • Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs cites Self-Consistency Improves Chain of Thought Reasoning in Language Models
  • Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs cites Language Models are Few-Shot Learners
  • Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs cites Uncertainty Estimation in Autoregressive Structured Prediction
  • DoLa: Decoding by Contrasting Layers Improves Factuality in Large Language Models cites Language Models are Few-Shot Learners
  • Complementing Self-Consistency with Cross-Model Disagreement for Uncertainty Quantification cites Self-Consistency Improves Chain of Thought Reasoning in Language Models
  • Semantic Uncertainty Quantification of Hallucinations in LLMs: A Quantum Tensor Network Based Method cites Self-Consistency Improves Chain of Thought Reasoning in Language Models
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Rethinking Uncertainty Estimation in LLMs: A Principled Single-Sequence MeasureLukas Aichberger, Kajetan Schweighofer, Sepp HochreiterICLR 2026 · 12 citations
  2. Complementing Self-Consistency with Cross-Model Disagreement for Uncertainty QuantificationKimia Hamidieh, Veronika Thost, Walter Gerych, Mikhail Yurochkin et al.ICLR 2026 · 12 citations
  3. Semantic Uncertainty Quantification of Hallucinations in LLMs: A Quantum Tensor Network Based MethodPragatheeswaran Vipulanandan, Kamal Premaratne, Dilip SarkarICLR 2026 · 4 citations

Builds on16

  1. Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
  2. Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMsMiao Xiong, Zhiyuan Hu, Xinyang Lu, Yifei Li et al.ICLR 2024 · 867 citations
  3. Self-Consistency Improves Chain of Thought Reasoning in Language ModelsXuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le et al.ICLR 2023 · 681 citations
  4. Uncertainty Estimation in Autoregressive Structured PredictionAndrey Malinin, Mark J. F. GalesICLR 2021 · 439 citations
  5. DoLa: Decoding by Contrasting Layers Improves Factuality in Large Language ModelsYung-Sung Chuang, Yujia Xie, Hongyin Luo, Yoon Kim et al.ICLR 2024 · 354 citations

Related papers

  1. GAUSS: Graph-Assisted Uncertainty Quantification using Structure and Semantics for Long-Form Generation in LLMsKarthik Somayaji NS, Yuxuan Yin, Peng LiICML 2026
  2. GENUINE: Graph Enhanced Multi-level Uncertainty Estimation for Large Language ModelsTuo Wang, Adithya Kulkarni, Tyler Cody, Peter A. Beling et al.EMNLP Findings 2025 · 1 citation
  3. Enhancing Uncertainty Modeling with Semantic Graph for Hallucination DetectionKedi Chen, Qin Chen, Jie Zhou, Xinqi Tao et al.AAAI 2025 · 13 citations
  4. AGSC: Adaptive Granularity and Semantic Clustering for Uncertainty Quantification in Long-text GenerationGuanran Luo, Wentao Qiu, Wanru Zhao, Wenhan Lv et al.ACL 2026 · 2 citations
  5. Fact-Checking the Output of Large Language Models via Token-Level Uncertainty QuantificationEkaterina Fadeeva, Aleksandr Rubashevskii, Artem Shelmanov, Sergey Petrakov et al.ACL Findings 2024 · 29 citations
Dusk over the sea between two cliffs drawn in fine vertical lines