# Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models

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

## Key facts

- Cited by 48 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 46 of its 68 references that are in the map.
- First posted on arXiv 16 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 46)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (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)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [What Disease does this Patient Have? A Large-scale Open Domain Question Answering Dataset from Medical Exams](https://mlsanity.com/paper/2009.13081/) (2020)
- [Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering](https://mlsanity.com/paper/2007.01282/) (2020)
- [ConceptNet 5.5: An Open Multilingual Graph of General Knowledge](https://mlsanity.com/paper/1612.03975/) (2016)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [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)
- [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)
- [Autoregressive Entity Retrieval](https://mlsanity.com/paper/2010.00904/) (2020)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Chain-of-Verification Reduces Hallucination in Large Language Models](https://mlsanity.com/paper/2309.11495/) (2023)
- [Reasoning with Language Model Prompting: A Survey](https://mlsanity.com/paper/2212.09597/) (2022)
- [Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text](https://mlsanity.com/paper/1809.00782/) (2018)
- [End-to-End Training of Multi-Document Reader and Retriever for Open-Domain Question Answering](https://mlsanity.com/paper/2106.05346/) (2021)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [Scalable Multi-Hop Relational Reasoning for Knowledge-Aware Question Answering](https://mlsanity.com/paper/2005.00646/) (2020)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals](https://mlsanity.com/paper/2101.03737/) (2021)
- [Knowledge-Driven CoT: Exploring Faithful Reasoning in LLMs for Knowledge-intensive Question Answering](https://mlsanity.com/paper/2308.13259/) (2023)
- [Subgraph Retrieval Enhanced Model for Multi-hop Knowledge Base Question Answering](https://mlsanity.com/paper/2202.13296/) (2022)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)

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

- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)
- [Youtu-GraphRAG: Vertically Unified Agents for Graph Retrieval-Augmented Complex Reasoning](https://mlsanity.com/paper/2508.19855/) (2025)
- [Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking](https://mlsanity.com/paper/2505.23495/) (2025)
- [Graph Retrieval-Augmented LLM for Conversational Recommendation Systems](https://mlsanity.com/paper/2503.06430/) (2025)
- [Reliable Reasoning Path: Distilling Effective Guidance for LLM Reasoning with Knowledge Graphs](https://mlsanity.com/paper/2506.10508/) (2025)
- [Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoning](https://mlsanity.com/paper/2503.01642/) (2025)
- [RiTeK: A Dataset for Large Language Models Complex Reasoning over Textual Knowledge Graphs in Medicine](https://mlsanity.com/paper/2410.13987/) (2024)
- [LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration](https://mlsanity.com/paper/2411.05844/) (2024)
- [Reason-Align-Respond: Aligning LLM Reasoning with Knowledge Graphs for KGQA](https://mlsanity.com/paper/2505.20971/) (2025)
- [Graph Counselor: Adaptive Graph Exploration via Multi-Agent Synergy to Enhance LLM Reasoning](https://mlsanity.com/paper/2506.03939/) (2025)
- [Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2510.08825/) (2025)
- [Taming the Untamed: Graph-Based Knowledge Retrieval and Reasoning for MLLMs to Conquer the Unknown](https://mlsanity.com/paper/2506.17589/) (2025)
- [Structured Extraction of Real World Medical Knowledge using LLMs for Summarization and Search](https://mlsanity.com/paper/2412.15256/) (2024)
- [Advancing Multi-Agent RAG Systems with Minimalist Reinforcement Learning](https://mlsanity.com/paper/2505.17086/) (2025)
- [Specification and Evaluation of Multi-Agent LLM Systems -- Prototype and Cybersecurity Applications](https://mlsanity.com/paper/2506.10467/) (2025)
- [RAG Safety: Exploring Knowledge Poisoning Attacks to Retrieval-Augmented Generation](https://mlsanity.com/paper/2507.08862/) (2025)
- [Ground-Truth Subgraphs for Better Training and Evaluation of Knowledge Graph Augmented LLMs](https://mlsanity.com/paper/2511.04473/) (2025)
- [ProgRAG: Hallucination-Resistant Progressive Retrieval and Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2511.10240/) (2025)
- [Ontology-Constrained Neural Reasoning in Enterprise Agentic Systems: A Neurosymbolic Architecture for Domain-Grounded AI Agents](https://mlsanity.com/paper/2604.00555/) (2026)
- [R2-KG: General-Purpose Dual-Agent Framework for Reliable Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2502.12767/) (2025)
- [PersonalAI: A Systematic Comparison of Knowledge Graph Storage and Retrieval Approaches for Personalized LLM agents](https://mlsanity.com/paper/2506.17001/) (2025)
- [Knowledge-Augmented Long-CoT Generation for Complex Biomolecular Reasoning](https://mlsanity.com/paper/2511.08024/) (2025)
- [DPRM: A Dual Implicit Process Reward Model in Multi-Hop Question Answering](https://mlsanity.com/paper/2511.08364/) (2025)
- [Making Theft Useless: Adulteration-Based Protection of Proprietary Knowledge Graphs in GraphRAG Systems](https://mlsanity.com/paper/2601.00274/) (2026)
- [Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling](https://mlsanity.com/paper/2602.21728/) (2026)
- [Efficient Multi-Hop Question Answering over Knowledge Graphs via LLM Planning and Embedding-Guided Search](https://mlsanity.com/paper/2511.19648/) (2025)
- [RPO-RAG: Aligning Small LLMs with Relation-aware Preference Optimization for Knowledge Graph Question Answering](https://mlsanity.com/paper/2601.19225/) (2026)
- [DiagLink: A Dual-User Diagnostic Assistance System by Synergizing Experts with LLMs and Knowledge Graphs](https://mlsanity.com/paper/2601.20311/) (2026)
- [To Know is to Construct: Schema-Constrained Generation for Agent Memory](https://mlsanity.com/paper/2604.20117/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have demonstrated impressive reasoning abilities, but they still struggle with faithful reasoning due to knowledge gaps and hallucinations. To address these issues, knowledge graphs (KGs) have been utilized to enhance LLM reasoning through their structured knowledge. 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 work, we introduce graph-constrained reasoning (GCR), a novel framework that bridges structured knowledge in KGs with unstructured reasoning in LLMs. To eliminate hallucinations, GCR ensures faithful KG-grounded reasoning by integrating KG structure into the LLM decoding process through KG-Trie, a trie-based index that encodes KG reasoning paths. KG-Trie constrains the decoding process, allowing LLMs to directly reason on graphs and generate faithful reasoning paths grounded in KGs. Additionally, GCR leverages a lightweight KG-specialized LLM for graph-constrained reasoning alongside a powerful general LLM for inductive reasoning over multiple reasoning paths, resulting in accurate reasoning with zero reasoning hallucination. Extensive experiments on several KGQA benchmarks demonstrate that GCR achieves state-of-the-art performance and exhibits strong zero-shot generalizability to unseen KGs without additional training.