# Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning

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

## Key facts

- Cited by 44 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 38 of its 53 references that are in the map.
- First posted on arXiv 18 Oct 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 38)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [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)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [KILT: a Benchmark for Knowledge Intensive Language Tasks](https://mlsanity.com/paper/2009.02252/) (2020)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [Complexity-Based Prompting for Multi-Step Reasoning](https://mlsanity.com/paper/2210.00720/) (2022)
- [A Survey of Hallucination in Large Foundation Models](https://mlsanity.com/paper/2309.05922/) (2023)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [Verify-and-Edit: A Knowledge-Enhanced Chain-of-Thought Framework](https://mlsanity.com/paper/2305.03268/) (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)
- [Case-based Reasoning for Natural Language Queries over Knowledge Bases](https://mlsanity.com/paper/2104.08762/) (2021)
- [RnG-KBQA: Generation Augmented Iterative Ranking for Knowledge Base Question Answering](https://mlsanity.com/paper/2109.08678/) (2021)
- [Learning to Exploit Long-term Relational Dependencies in Knowledge Graphs](https://mlsanity.com/paper/1905.04914/) (2019)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-based Retrofitting](https://mlsanity.com/paper/2311.13314/) (2023)
- [Poolingformer: Long Document Modeling with Pooling Attention](https://mlsanity.com/paper/2105.04371/) (2021)
- [Don't Generate, Discriminate: A Proposal for Grounding Language Models to Real-World Environments](https://mlsanity.com/paper/2212.09736/) (2022)
- [Direct Fact Retrieval from Knowledge Graphs without Entity Linking](https://mlsanity.com/paper/2305.12416/) (2023)

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

- [Large Language Models Hallucination: A Comprehensive Survey](https://mlsanity.com/paper/2510.06265/) (2025)
- [Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities](https://mlsanity.com/paper/2506.18019/) (2025)
- [CypherBench: Towards Precise Retrieval over Full-scale Modern Knowledge Graphs in the LLM Era](https://mlsanity.com/paper/2412.18702/) (2024)
- [Ontology-Guided Reverse Thinking Makes Large Language Models Stronger on Knowledge Graph Question Answering](https://mlsanity.com/paper/2502.11491/) (2025)
- [Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking](https://mlsanity.com/paper/2505.23495/) (2025)
- [Self-supervised Quantized Representation for Seamlessly Integrating Knowledge Graphs with Large Language Models](https://mlsanity.com/paper/2501.18119/) (2025)
- [Reliable Reasoning Path: Distilling Effective Guidance for LLM Reasoning with Knowledge Graphs](https://mlsanity.com/paper/2506.10508/) (2025)
- [GraphCompliance: Structure-Aware Regulatory Compliance through Policy-Context Graph Alignment](https://mlsanity.com/paper/2510.26309/) (2025)
- [Reason-Align-Respond: Aligning LLM Reasoning with Knowledge Graphs for KGQA](https://mlsanity.com/paper/2505.20971/) (2025)
- [SGPT: Few-Shot Prompt Tuning for Signed Graphs](https://mlsanity.com/paper/2412.12155/) (2024)
- [Position: Foundation Models for Tabular Data within Systemic Contexts Need Grounding](https://mlsanity.com/paper/2505.19825/) (2025)
- [Unbiased Reasoning for Knowledge-Intensive Tasks in Large Language Models via Conditional Front-Door Adjustment](https://mlsanity.com/paper/2508.16910/) (2025)
- [Large Language Models Meet Text-Attributed Graphs: A Survey of Integration Frameworks and Applications](https://mlsanity.com/paper/2510.21131/) (2025)
- [Rank, Chunk and Expand: Lineage-Oriented Reasoning for Taxonomy Expansion](https://mlsanity.com/paper/2505.13282/) (2025)
- [Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2510.08825/) (2025)
- [PruneRAG: Confidence-Guided Query Decomposition Trees for Efficient Retrieval-Augmented Generation](https://mlsanity.com/paper/2601.11024/) (2026)
- [Advancing Multi-Agent RAG Systems with Minimalist Reinforcement Learning](https://mlsanity.com/paper/2505.17086/) (2025)
- [StepChain GraphRAG: Reasoning Over Knowledge Graphs for Multi-Hop Question Answering](https://mlsanity.com/paper/2510.02827/) (2025)
- [Debate over Mixed-knowledge: A Robust Multi-Agent Reasoning Framework for Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2511.12208/) (2025)
- [Agentic SPARQL: Evaluating SPARQL-MCP-powered Intelligent Agents on the Federated KGQA Benchmark](https://mlsanity.com/paper/2603.06582/) (2026)
- [R2-KG: General-Purpose Dual-Agent Framework for Reliable Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2502.12767/) (2025)
- [Towards Open-World Retrieval-Augmented Generation on Knowledge Graph: A Multi-Agent Collaboration Framework](https://mlsanity.com/paper/2509.01238/) (2025)
- [PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation](https://mlsanity.com/paper/2510.12434/) (2025)
- [Ensembling LLM-Induced Decision Trees for Explainable and Robust Error Detection](https://mlsanity.com/paper/2512.07246/) (2025)
- [PRAXIS: Integrating Program Analysis with Observability for Root-Cause Analysis](https://mlsanity.com/paper/2512.22113/) (2025)
- [When to Trust: A Causality-Aware Calibration Framework for Accurate Knowledge Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2601.09241/) (2026)
- [Construct, Align, and Reason: Large Ontology Models for Enterprise Knowledge Management](https://mlsanity.com/paper/2602.00029/) (2026)
- [Flow-Modulated Scoring for Semantic-Aware Knowledge Graph Completion](https://mlsanity.com/paper/2506.23137/) (2025)
- [Instance-Wise Monotonic Calibration by Constrained Transformation](https://mlsanity.com/paper/2507.06516/) (2025)
- [MMAPG: A Training-Free Framework for Multimodal Multi-hop Question Answering via Adaptive Planning Graphs](https://mlsanity.com/paper/2508.16051/) (2025)

## Abstract (arXiv)

Large Language Models (LLMs) have achieved impressive results in various tasks but struggle with hallucination problems and lack of relevant knowledge, especially in deep complex reasoning and knowledge-intensive tasks. Knowledge Graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning. However, existing KG-based LLM reasoning methods face challenges like handling multi-hop reasoning, multi-entity questions, and effectively utilizing graph structures. To address these issues, we propose Paths-over-Graph (PoG), a novel method that enhances LLM reasoning by integrating knowledge reasoning paths from KGs, improving the interpretability and faithfulness of LLM outputs. PoG tackles multi-hop and multi-entity questions through a three-phase dynamic multi-hop path exploration, which combines the inherent knowledge of LLMs with factual knowledge from KGs. In order to improve the efficiency, PoG prunes irrelevant information from the graph exploration first and introduces efficient three-step pruning techniques that incorporate graph structures, LLM prompting, and a pre-trained language model (e.g., SBERT) to effectively narrow down the explored candidate paths. This ensures all reasoning paths contain highly relevant information captured from KGs, making the reasoning faithful and interpretable in problem-solving. PoG innovatively utilizes graph structure to prune the irrelevant noise and represents the first method to implement multi-entity deep path detection on KGs for LLM reasoning tasks. Comprehensive experiments on five benchmark KGQA datasets demonstrate PoG outperforms the state-of-the-art method ToG across GPT-3.5-Turbo and GPT-4, achieving an average accuracy improvement of 18.9%. Notably, PoG with GPT-3.5-Turbo surpasses ToG with GPT-4 by up to 23.9%.