Research map / Large language models / Language, safety and interpretability
Graph-based Uncertainty Metrics for Long-form Language Model Generations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Graph Uncertainty, which builds a response-claim bipartite entailment graph and uses graph centrality (notably closeness) for claim-level uncertainty, plus an uncertainty-aware decoding method that keeps only confident claims.
Problem
Claim-level uncertainty estimation for long-form LLM generations in black-box settings, where existing self-consistency methods only count entailment and miss richer semantic relations; also improving factuality at decoding time.
Approach
Model sampled responses and decomposed claims as a bipartite entailment graph; self-consistency is equivalent to degree centrality, and generalizing to other centrality measures (closeness, PageRank, eigenvector, betweenness) yields better claim-level uncertainty. Closeness centrality performs best and is used to filter claims before LLM-based synthesis.
Key results
- Closeness centrality achieves average 6.8% relative AUPRC gains over baselines across GPT-3.5, GPT-4, and Llama-3 settings on FActScore and PopQA.
- Uncertainty-aware decoding with closeness yields consistent 2-4% factuality gains and about 70% more true claims at 95% precision versus baselines, on FActScore with GPT-3.5-turbo.
- Self-consistency (degree centrality) is a strong baseline that beats prior verbalized-confidence methods; closeness reaches up to over 6% AUROC and 12% AUPRC-Negative gains over SC in some settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use closeness centrality instead of the strongest listed baseline for claim-level uncertainty | Graph Uncertainty · FActScore and PopQA | AUPRC-Negative: 0.781 -> 0.848; 0.801 -> 0.859; 0.670 -> 0.733; 0.708 -> 0.751; 0.739 -> 0.837; 0.771 -> 0.850; 0.656 -> 0.754; 0.721 -> | Helped |
| Use closeness centrality instead of SC + VC for Llama-3 with 5 samples on PopQA | Graph Uncertainty · PopQA | AUPRC-Negative: 0.666 -> 0.699 | Helped |
| Use closeness centrality instead of SC for Llama-3 with 10 samples on PopQA | Graph Uncertainty · PopQA | AUPRC-Negative: 0.652 -> 0.713 | Helped |
| Add verbalized confidence to self-consistency scores | Claim-level uncertainty estimation · FActScore and PopQA | AUPRC-Negative | Helped |
| Use in-line rather than post-hoc verbalized confidence | Claim-level uncertainty estimation · FActScore and PopQA | AUPRC-Negative | Hurt |
| Use closeness centrality in uncertainty-aware decoding instead of the best SC-based baseline | UAD · FActScore | factuality: 2-4% | Helped |
| Use closeness centrality in uncertainty-aware decoding | UAD · FActScore at 95% precision | true claims: 70% more | Helped |
| Expand the candidate claim set from greedy output claims to claims from multiple samples (ablation) | UAD · FActScore | factuality and informativeness | Mixed |
| Increase the number of sampled responses used to construct the claim set (ablation) | Closeness-centrality uncertainty estimation · FActScore | AUPRC-Negative | Helped |
| Add closeness centrality in place of SC-based uncertainty estimates (ablation) | UAD with multi-sample claims · FActScore | factuality-informativeness tradeoff | Helped |
| Use post-hoc rather than in-line verbalized confidence to break SC ties (ablation) | UAD with multi-sample claims · FActScore | factuality-informativeness tradeoff | Helped |
Surprising findings
- In-line verbalized confidence usually underperforms post-hoc verbalized confidence, suggesting that combining decomposition with confidence elicitation hurts estimation.
- Verbalized confidence on Natural Questions/other settings can underperform SC, and GPT-4 PH-VC is weaker than GPT-3.5 on some setups.
Limitations
- Graph construction adds substantial inference compute and latency.
- Claim decomposition assumes claims can be decontextualized, which fails for dependent claims.
- Auto-annotation with GPT-4-Turbo has higher false negative rates on Natural Questions.
Experimental setup
Datasets: FActScore PopQA Natural Questions
Benchmarks: FActScore long-form PopQA Natural Questions
Metrics: AUROC AUPRC-Negative factuality informativeness
Baselines: Self-Consistency (SC) SC+VC PH-VC IL-VC P(True) CoVe Greedy decoding Conformal Factuality Decoding
Builds on: self-consistency conformal factuality FActScore chain-of-verification
Closest papers by meaning
- Forking Paths in Neural Text Generation (ICLR 2025 · similarity 0.90)
- SPANUQ: Span-Level Uncertainty Quantification for Large Language Model Generation (NeurIPS 2026 · similarity 0.90)
- Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities (NeurIPS 2024 · similarity 0.89)
- Distinguishing the Knowable from the Unknowable with Language Models (ICML 2024 · similarity 0.89)
- Improving Uncertainty Estimation through Semantically Diverse Language Generation (ICLR 2025 · similarity 0.89)
- Towards Trustworthy Knowledge Graph Reasoning: An Uncertainty Aware Perspective (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.