# FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering

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

## Key facts

- Cited by 39 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 53 of its 81 references that are in the map.
- First posted on arXiv 22 May 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 30 of 53)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [What Disease does this Patient Have? A Large-scale Open Domain Question Answering Dataset from Medical Exams](https://mlsanity.com/paper/2009.13081/) (2020)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [Galactica: A Large Language Model for Science](https://mlsanity.com/paper/2211.09085/) (2022)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [Towards Reasoning in Large Language Models: A Survey](https://mlsanity.com/paper/2212.10403/) (2022)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Models](https://mlsanity.com/paper/2212.04088/) (2022)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering](https://mlsanity.com/paper/2104.06378/) (2021)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Binding Language Models in Symbolic Languages](https://mlsanity.com/paper/2210.02875/) (2022)
- [Key-Value Memory Networks for Directly Reading Documents](https://mlsanity.com/paper/1606.03126/) (2016)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [A Survey of Large Language Models for Healthcare: from Data, Technology, and Applications to Accountability and Ethics](https://mlsanity.com/paper/2310.05694/) (2023)
- [Rethinking with Retrieval: Faithful Large Language Model Inference](https://mlsanity.com/paper/2301.00303/) (2022)

## Built on by (most cited first, 30 of 39)

- [Efficient Inference for Large Reasoning Models: A Survey](https://mlsanity.com/paper/2503.23077/) (2025)
- [UniGraph2: Learning a Unified Embedding Space to Bind Multimodal Graphs](https://mlsanity.com/paper/2502.00806/) (2025)
- [Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models](https://mlsanity.com/paper/2410.13080/) (2024)
- [EvoTest: Evolutionary Test-Time Learning for Self-Improving Agentic Systems](https://mlsanity.com/paper/2510.13220/) (2025)
- [Evaluating the Paperclip Maximizer: Are RL-Based Language Models More Likely to Pursue Instrumental Goals?](https://mlsanity.com/paper/2502.12206/) (2025)
- [Meta-Reasoner: Dynamic Guidance for Optimized Inference-time Reasoning in Large Language Models](https://mlsanity.com/paper/2502.19918/) (2025)
- [Can Knowledge Graphs Make Large Language Models More Trustworthy? An Empirical Study Over Open-ended Question Answering](https://mlsanity.com/paper/2410.08085/) (2024)
- [Harnessing Large Language Models for Knowledge Graph Question Answering via Adaptive Multi-Aspect Retrieval-Augmentation](https://mlsanity.com/paper/2412.18537/) (2024)
- [TopicAttack: An Indirect Prompt Injection Attack via Topic Transition](https://mlsanity.com/paper/2507.13686/) (2025)
- [Enabling Self-Improving Agents to Learn at Test Time With Human-In-The-Loop Guidance](https://mlsanity.com/paper/2507.17131/) (2025)
- [Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation](https://mlsanity.com/paper/2502.18771/) (2025)
- [BYOKG-RAG: Multi-Strategy Graph Retrieval for Knowledge Graph Question Answering](https://mlsanity.com/paper/2507.04127/) (2025)
- [Align-GRAG: Anchor and Rationale Guided Dual Alignment for Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2505.16237/) (2025)
- [Chain-of-Probe: Examining the Necessity and Accuracy of CoT Step-by-Step](https://mlsanity.com/paper/2406.16144/) (2024)
- [Beyond Seen Data: Improving KBQA Generalization Through Schema-Guided Logical Form Generation](https://mlsanity.com/paper/2502.12737/) (2025)
- [ReMindRAG: Low-Cost LLM-Guided Knowledge Graph Traversal for Efficient RAG](https://mlsanity.com/paper/2510.13193/) (2025)
- [EvoClinician: A Self-Evolving Agent for Multi-Turn Medical Diagnosis via Test-Time Evolutionary Learning](https://mlsanity.com/paper/2601.22964/) (2026)
- [Generalizing Graph Transformers Across Diverse Graphs and Tasks via Pre-training](https://mlsanity.com/paper/2407.03953/) (2024)
- [GraphRAFT: Retrieval Augmented Fine-Tuning for Knowledge Graphs on Graph Databases](https://mlsanity.com/paper/2504.05478/) (2025)
- [DAMR: Efficient and Adaptive Context-Aware Knowledge Graph Question Answering with LLM-Guided MCTS](https://mlsanity.com/paper/2508.00719/) (2025)
- [Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2510.08825/) (2025)
- [Advancing Multi-Agent RAG Systems with Minimalist Reinforcement Learning](https://mlsanity.com/paper/2505.17086/) (2025)
- [Beyond Black-Box Interventions: Latent Probing for Faithful Retrieval-Augmented Generation](https://mlsanity.com/paper/2510.12460/) (2025)
- [Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning](https://mlsanity.com/paper/2607.18481/) (2026)
- [Semantic Parsing with Candidate Expressions for Knowledge Base Question Answering](https://mlsanity.com/paper/2410.00414/) (2024)
- [Encoder-Free Knowledge-Graph Reasoning with LLMs via Hyperdimensional Path Retrieval](https://mlsanity.com/paper/2512.09369/) (2025)
- [Structured Semantic Information Helps Retrieve Better Examples for In-Context Learning Applied to Few-Shot Relation Extraction](https://mlsanity.com/paper/2601.20803/) (2026)
- [RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering](https://mlsanity.com/paper/2603.20017/) (2026)
- [The Scaling Properties of Implicit Deductive Reasoning in Transformers](https://mlsanity.com/paper/2605.04330/) (2026)
- [Mapping Text to Multiplex Graph: Prompt Compression as L'evy Walk-Guided Graph Pruning](https://mlsanity.com/paper/2607.01241/) (2026)

## Abstract (arXiv)

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. Code is released at https://github.com/Y-Sui/FiDeLiS.