Conformal Path Reasoning: Trustworthy Knowledge Graph Question Answering via Path-Level Calibration

Knowledge Graph Question Answering (KGQA) offers grounded, interpretable reasoning, but existing methods often fail to provide reliable coverage guarantees over retrieved answers. While Conformal Prediction (CP) offers a principled framework for producing prediction sets with statistical guarantees, prior conformal KGQA methods suffer from two critical pitfalls: violated coverage guarantees due to invalid calibration, and weak score discriminability that yields excessively large prediction sets. We propose Conformal Path Reasoning (CPR), a novel trustworthy KGQA framework built on two key innovations. First, query-level conformal calibration over path-level scores preserves exchangeability to ensure valid coverage guarantees. Second, we introduce the Residual Conformal Value Network (RCVNet), a lightweight module trained via PUCT-guided exploration to learn discriminative path-level nonconformity scores. Extensive experiments show that CPR significantly improves the Empirical Coverage Rate by 45\% while reducing prediction set size by 52\% on average over conformal baselines across benchmark datasets, highlighting its effectiveness for reliable conformal reasoning over knowledge graphs.

Knowledge graphs are structured databases that store real-world facts, powering many question-answering systems. However, these systems typically return only a single answer without indicating how reliable it is. In high-stakes applications like medical diagnosis or financial risk assessment, this lack of uncertainty quantification can lead to dangerous decisions. Existing methods for measuring reliability either fail to provide rigorous statistical guarantees or produce overly large answer sets that are impractical to use. We present Conformal Path Reasoning (CPR), a trustworthy knowledge graph question answering framework. Instead of evaluating each step of reasoning separately, CPR assesses the reliability of entire reasoning paths, ensuring valid statistical guarantees. We further introduce a lightweight neural network that learns to distinguish correct reasoning paths from plausible but incorrect alternatives. Our experiments show that CPR improves the answer coverage rate by 45\% while reducing the average prediction set size by 52\% compared to previous methods. This enables safer deployment of knowledge graph systems in high-stakes domains, where users receive a concise set of candidate answers backed by a clear reliability guarantee.