Research map / Large language models / Retrieval and knowledge
Towards Trustworthy Knowledge Graph Reasoning: An Uncertainty Aware Perspective
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 UaG, an uncertainty-aware KG-LLM reasoning framework that uses conformal prediction for graph traversal and answer selection, with Learn Then Test to control error propagation across components, reaching target coverage while shrinking prediction sets.
Problem
KG-LLM frameworks for multi-hop KGQA lack rigorous uncertainty estimation, so their answers cannot be trusted in high-stakes settings where errors are costly.
Approach
Applies conformal prediction to each step of KG traversal (candidate paths and neighbors) and to LLM answer filtering via similarity scores, then uses Learn Then Test with a binomial tail p-value and FWER control to jointly tune per-component error rates so the end-to-end coverage guarantee holds.
Key results
- UaG achieves ECR of 92.3% at alpha=0.1 on WebQSP and 87.2% at alpha=0.15 on WebQSP, with prediction set sizes of 68.6 and 39.1 respectively at those levels.
- The abstract claims reduction of prediction set size by 40% on average over baselines while achieving any pre-defined coverage rate.
- UaG-Top-3 reaches 73.4 Hits@1 on WebQSP, below RoG (85.7) but above prompting baselines such as ToG (57.4) and StructGPT (72.6).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UaG instead of Top K for uncertainty-aware prediction | KGQA · WebQSP, α=0.35 | SS: 6.2 -> 2.6 | Helped |
| Use UaG instead of Split CP for uncertainty-aware prediction | KGQA · CWQ, α=0.6 | SS: 3.0 -> 2.6 | Helped |
| Fine-tune the SentenceTransformer used for graph traversal (ablation) | UaG · KGQA | prediction set size | Helped |
| Pre-train the LLM backbone (ablation) | UaG · KGQA | model performance | No clear effect |
| Use cosine similarity instead of L1 similarity (ablation) | UaG · KGQA | prediction efficiency | Helped |
Surprising findings
- Fine-tuning the LLM backbone did not yield substantial gains and may increase uncertainty, while fine-tuning the sentence transformer for graph traversal significantly reduced prediction set size.
- Cosine similarity outperformed L1 similarity for prediction efficiency while maintaining the error rate.
Limitations
- Baselines produce invalid (missing) prediction sets at some risk levels, and UaG is not designed for traditional Hits@1 KGQA, achieving lower Hits@1 than RoG.
- Uses the top p-value heuristic (n=1) instead of a conservative FWER correction, so the rigorous guarantee depends on this choice.
- Evaluated only on two KGQA datasets (WebQSP, CWQ) with Freebase.
Experimental setup
Datasets: WebQSP CWQ Freebase
Benchmarks: WebQSP CWQ
Metrics: empirical coverage rate average prediction set size Hits@1
Baselines: Top-K Split CP CLM LoFreeCP RoG TIARA DeCAF COT ToG KD-CoT StructGPT
Builds on: conformal prediction Learn Then Test Conformal Language Modeling LoFreeCP RoG
Closest papers by meaning
- Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.90)
- Argument Graph Uncertainty: Quantifying Uncertainty from the Logical Structure of Reasoning Chains (NeurIPS 2026 · similarity 0.90)
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models (ICML 2025 · similarity 0.89)
- Graph-based Uncertainty Metrics for Long-form Language Model Generations (NeurIPS 2024 · similarity 0.89)
- Deliberation on Priors: Trustworthy Reasoning of Large Language Models on Knowledge Graphs (NeurIPS 2025 · similarity 0.89)
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph (ICLR 2024 · similarity 0.88)
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.