# Towards Trustworthy Knowledge Graph Reasoning: An Uncertainty Aware Perspective

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 20 of its 36 references that are in the map.
- First posted on arXiv 11 Oct 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Towards Reasoning in Large Language Models: A Survey](https://mlsanity.com/paper/2212.10403/) (2022)
- [Are Emergent Abilities of Large Language Models a Mirage?](https://mlsanity.com/paper/2304.15004/) (2023)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Conformal Language Modeling](https://mlsanity.com/paper/2306.10193/) (2023)
- [Conformal Prediction with Large Language Models for Multi-Choice Question Answering](https://mlsanity.com/paper/2305.18404/) (2023)
- [Chain-of-Knowledge: Grounding Large Language Models via Dynamic Knowledge Adapting over Heterogeneous Sources](https://mlsanity.com/paper/2305.13269/) (2023)
- [Knowledge-Augmented Language Model Prompting for Zero-Shot Knowledge Graph Question Answering](https://mlsanity.com/paper/2306.04136/) (2023)
- [Knowledge-Driven CoT: Exploring Faithful Reasoning in LLMs for Knowledge-intensive Question Answering](https://mlsanity.com/paper/2308.13259/) (2023)
- [Boosting Language Models Reasoning with Chain-of-Knowledge Prompting](https://mlsanity.com/paper/2306.06427/) (2023)
- [TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases](https://mlsanity.com/paper/2210.12925/) (2022)
- [Give Us the Facts: Enhancing Large Language Models with Knowledge Graphs for Fact-aware Language Modeling](https://mlsanity.com/paper/2306.11489/) (2023)
- [Conformal Prediction for Deep Classifier via Label Ranking](https://mlsanity.com/paper/2310.06430/) (2023)
- [Conditional Diffusion Based on Discrete Graph Structures for Molecular Graph Generation](https://mlsanity.com/paper/2301.00427/) (2023)

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

- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [Towards Trustworthy Retrieval Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2502.06872/) (2025)
- [A Survey on LLM-based Conversational User Simulation](https://mlsanity.com/paper/2604.24977/) (2026)
- [Static Sandboxes Are Inadequate: Modeling Societal Complexity Requires Open-Ended Co-Evolution in LLM-Based Multi-Agent Simulations](https://mlsanity.com/paper/2510.13982/) (2025)
- [Conformal Path Reasoning: Trustworthy Knowledge Graph Question Answering via Path-Level Calibration](https://mlsanity.com/paper/2605.08077/) (2026)

## Abstract (arXiv)

Recently, Knowledge Graphs (KGs) have been successfully coupled with Large Language Models (LLMs) to mitigate their hallucinations and enhance their reasoning capability, such as in KG-based retrieval-augmented frameworks. However, current KG-LLM frameworks lack rigorous uncertainty estimation, limiting their reliable deployment in high-stakes applications. Directly incorporating uncertainty quantification into KG-LLM frameworks presents challenges due to their complex architectures and the intricate interactions between the knowledge graph and language model components. To address this gap, we propose a new trustworthy KG-LLM framework, Uncertainty Aware Knowledge-Graph Reasoning (UAG), which incorporates uncertainty quantification into the KG-LLM framework. We design an uncertainty-aware multi-step reasoning framework that leverages conformal prediction to provide a theoretical guarantee on the prediction set. To manage the error rate of the multi-step process, we additionally introduce an error rate control module to adjust the error rate within the individual components. Extensive experiments show that our proposed UAG can achieve any pre-defined coverage rate while reducing the prediction set/interval size by 40% on average over the baselines.