F i D e L i S : Faithful Reasoning in Large Language Models for Knowledge Graph Question Answering (2025)

Abstract: Large Language Models (LLMs) are often challenged by generating erroneous or hallucinated responses, especially in complex reasoning tasks. Leveraging Knowledge Graphs (KGs) as external knowledge sources has emerged as a viable solution. However, existing KG-enhanced methods, either retrieval-based or agent-based, encounter difficulties in accurately retrieving knowledge and efficiently traversing KGs at scale. In this paper, we propose a unified framework, FiDeLiS, designed to improve the factuality of LLM responses by anchoring answers to verifiable reasoning steps retrieved from KGs. To achieve this, we leverage step-wise beam search with a deductive scoring function, allowing the LLM to validate reasoning process step by step, and halt the search once the question is deducible. In addition, we propose a Path-RAG module to pre-select a smaller candidate set for each beam search step, reducing computational costs by narrowing the search space. Extensive experiments show that our method, as a training-free framework, not only improve the performance but also enhance the factuality and interpretability across different benchmarks.

## introduction large language models (llms) have shown impressive reasoning capabilities in tackling complex tasks @xcite . however, their reasoning processes are not always reliable, and can be prone to generating outputs that are either inconsistent with real-world facts @xcite or show flawed reasoning process @xcite . such limitations significantly undermine the trustworthiness of llms in practical, real-world applications @xcite ). 1 code is released at https://github.com/y-sui/ fidelis . to address this issue, leveraging knowledge graphs (kgs) as external knowledge sources has emerged as a viable solution @xcite @xcite . unlike traditional retrieval-augmented generation (rag) that relies on web pages or documents @xcite @xcite , kgs represent information in a structured and interconnected format, where each fact is stored as entities and relations. this format supports explicit, traceable reasoning processes @xcite and facilitates multi-hop reasoning through graph traversal. moreover, each fact in a kg can be traced back to its source @xcite , providing both context and original details, which further enhances the information authenticity and reliability of the reasoning processes. existing kg-enhanced llm reasoning methods face notable challenges and can be roughly categorized into two primary approaches: retrievalbased and agent-based paradigms @xcite . retrieval-based methods @xcite @xcite retrieve relevant kg facts to support llm reasoning by either prompting @xcite or fine-tuning llms to learn the underlying structure of kg @xcite . these methods often suffer from incomplete or imprecise information extraction due to a lack of contextual understanding or an inability to fully capture the graph structure @xcite . our error analysis ( §4.3) of a strong retrieval-based method, rog @xcite reveals that only 67% of the generated reasoning steps are valid, with 33% containing format errors or referencing non-existent kg facts. in contrast, agent-based methods @xcite treat llms as interactive agents that explore kgs iteratively to construct reasoning paths and generate answers. while this approach by nature can enhance reasoning accuracy, it is computationally expensive, resulting in high latency and scalability limitations. as illustrated in figure 1 , how to balance the trade-off between faithfulness and efficiency remains a critical challenge for existing kg-enhanced reasoning methods. to this end, we propose fidelis, a unified framework designed to enhance both the factual accuracy and reasoning efficiency of llms. fidelis grounds llm responses in verifiable reasoning steps derived from a kg through two core components: (1) deductive-verification beam search (dvbs), which systematically constructs and validates reasoning paths step-by-step to ensure logical consistency and factual correctness (detailed in §3.2). this module also prevents premature termination and incorrect path extensions, thereby guaranteeing the validity of generated reasoning chains. (2) path-rag, a retrieval-augmented mechanism that pre-selects a constrained set of candidate entities and relations at each reasoning step to mitigate computational inefficiencies. by combining semantic similarity with graph-based connectivity analysis, path-rag effectively narrows the search space, significantly reducing latency without compromising recall or accuracy (discussed in §3.1). extensive experiments demonstrate that fidelis outperforms strong baselines in both accuracy and efficiency, providing a scalable, training-free solution for kg-enhanced llm reasoning. our main contributions are summarized as follows: ## preliminary notation. to facilitate the demonstration of our method, we define the necessary notation below: ## conclusion this paper proposes a retrieval-exploration interactive method specifically designed to enhance intermediate steps of llm reasoning grounded by kgs. the path-rag module and the use of deductive reasoning as a calibration tool effectively guide the reasoning process, leading to more accurate knowledge retrieval and prevention of misleading reasoning chains. extensive experiments demonstrate that our method, being training-free, not only reduces computational costs but also offers superior generality. we believe this study will significantly benefit the integration of llms and kgs, or serve as an auxiliary tool to enhance the interpretability and factual reliability of llm outputs.