# Decoding on Graphs: Faithful and Sound Reasoning on Knowledge Graphs through Generation of Well-Formed Chains

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

## Key facts

- Cited by 20 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 8 of its 49 references that are in the map.
- First posted on arXiv 24 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, 8 of 8)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2402.07630/) (2024)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [Knowledge-Driven CoT: Exploring Faithful Reasoning in LLMs for Knowledge-intensive Question Answering](https://mlsanity.com/paper/2308.13259/) (2023)
- [Retrieve-Rewrite-Answer: A KG-to-Text Enhanced LLMs Framework for Knowledge Graph Question Answering](https://mlsanity.com/paper/2309.11206/) (2023)
- [Complex Knowledge Base Question Answering: A Survey](https://mlsanity.com/paper/2108.06688/) (2021)

## Built on by (most cited first, 20 of 20)

- [Graph RAG-Tool Fusion](https://mlsanity.com/paper/2502.07223/) (2025)
- [Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking](https://mlsanity.com/paper/2505.23495/) (2025)
- [BYOKG-RAG: Multi-Strategy Graph Retrieval for Knowledge Graph Question Answering](https://mlsanity.com/paper/2507.04127/) (2025)
- [Reason-Align-Respond: Aligning LLM Reasoning with Knowledge Graphs for KGQA](https://mlsanity.com/paper/2505.20971/) (2025)
- [RJE: A Retrieval-Judgment-Exploration Framework for Efficient Knowledge Graph Question Answering with LLMs](https://mlsanity.com/paper/2510.01257/) (2025)
- [Beyond Chains: Bridging Large Language Models and Knowledge Bases in Complex Question Answering](https://mlsanity.com/paper/2505.14099/) (2025)
- [Advancing Multi-Agent RAG Systems with Minimalist Reinforcement Learning](https://mlsanity.com/paper/2505.17086/) (2025)
- [LLM Inference Enhanced by External Knowledge: A Survey](https://mlsanity.com/paper/2505.24377/) (2025)
- [From Symbolic to Neural and Back: Exploring Knowledge Graph-Large Language Model Synergies](https://mlsanity.com/paper/2506.09566/) (2025)
- [KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering](https://mlsanity.com/paper/2512.10999/) (2025)
- [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)
- [Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning](https://mlsanity.com/paper/2607.18481/) (2026)
- [To Know is to Construct: Schema-Constrained Generation for Agent Memory](https://mlsanity.com/paper/2604.20117/) (2026)
- [GAPD: Gold-Action Policy Distillation for Agentic Reinforcement Learning in Knowledge Base Question Answering](https://mlsanity.com/paper/2605.29584/) (2026)
- [RAG-Zeval: Towards Robust and Interpretable Evaluation on RAG Responses through End-to-End Rule-Guided Reasoning](https://mlsanity.com/paper/2505.22430/) (2025)
- [ReFactX: Scalable Reasoning with Reliable Facts via Constrained Generation](https://mlsanity.com/paper/2508.16983/) (2025)
- [Diagnosing Structural Failures in LLM-Based Evidence Extraction for Meta-Analysis](https://mlsanity.com/paper/2602.10881/) (2026)
- [Leveraging Trajectory Graphs for Pre-Execution Error Diagnosis in Agentic LLM Systems](https://mlsanity.com/paper/2607.27443/) (2026)
- [Constrained Entity Selection under Partial Knowledge for LLM-Based Knowledge Graph QA](https://mlsanity.com/paper/2608.24824/) (2026)
- [The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA](https://mlsanity.com/paper/2609.27669/) (2026)

## Abstract (arXiv)

Knowledge Graphs (KGs) can serve as reliable knowledge sources for question answering (QA) due to their structured representation of knowledge. Existing research on the utilization of KG for large language models (LLMs) prevalently relies on subgraph retriever or iterative prompting, overlooking the potential synergy of LLMs' step-wise reasoning capabilities and KGs' structural nature. In this paper, we present DoG (Decoding on Graphs), a novel framework that facilitates a deep synergy between LLMs and KGs. We first define a concept, well-formed chain, which consists of a sequence of interrelated fact triplets on the KGs, starting from question entities and leading to answers. We argue that this concept can serve as a principle for making faithful and sound reasoning for KGQA. To enable LLMs to generate well-formed chains, we propose graph-aware constrained decoding, in which a constraint derived from the topology of the KG regulates the decoding process of the LLMs. This constrained decoding method ensures the generation of well-formed chains while making full use of the step-wise reasoning capabilities of LLMs. Based on the above, DoG, a training-free approach, is able to provide faithful and sound reasoning trajectories grounded on the KGs. Experiments across various KGQA tasks with different background KGs demonstrate that DoG achieves superior and robust performance. DoG also shows general applicability with various open-source LLMs.