# Debate on Graph: a Flexible and Reliable Reasoning Framework for Large Language Models

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

## Key facts

- Cited by 19 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 16 of its 63 references that are in the map.
- First posted on arXiv 5 Sep 2024.

## Placed in

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

## Builds on (most cited first, 16 of 16)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate](https://mlsanity.com/paper/2305.19118/) (2023)
- [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023)
- [A Survey on In-context Learning](https://mlsanity.com/paper/2301.00234/) (2022)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [A Survey of Hallucination in Large Foundation Models](https://mlsanity.com/paper/2309.05922/) (2023)
- [A Survey on Hallucination in Large Vision-Language Models](https://mlsanity.com/paper/2402.00253/) (2024)
- [Better Zero-Shot Reasoning with Role-Play Prompting](https://mlsanity.com/paper/2308.07702/) (2023)
- [Exploring Collaboration Mechanisms for LLM Agents: A Social Psychology View](https://mlsanity.com/paper/2310.02124/) (2023)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [RoCo: Dialectic Multi-Robot Collaboration with Large Language Models](https://mlsanity.com/paper/2307.04738/) (2023)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [KnowledgeNavigator: Leveraging Large Language Models for Enhanced Reasoning over Knowledge Graph](https://mlsanity.com/paper/2312.15880/) (2023)
- [Right for Right Reasons: Large Language Models for Verifiable Commonsense Knowledge Graph Question Answering](https://mlsanity.com/paper/2403.01390/) (2024)
- [On the Decision-Making Abilities in Role-Playing using Large Language Models](https://mlsanity.com/paper/2402.18807/) (2024)

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

- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [From Individual to Society: A Survey on Social Simulation Driven by Large Language Model-based Agents](https://mlsanity.com/paper/2412.03563/) (2024)
- [Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models](https://mlsanity.com/paper/2410.13080/) (2024)
- [IRT-Router: Effective and Interpretable Multi-LLM Routing via Item Response Theory](https://mlsanity.com/paper/2506.01048/) (2025)
- [DAMR: Efficient and Adaptive Context-Aware Knowledge Graph Question Answering with LLM-Guided MCTS](https://mlsanity.com/paper/2508.00719/) (2025)
- [CoT2-Meta: Budgeted Metacognitive Control for Test-Time Reasoning](https://mlsanity.com/paper/2603.28135/) (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)
- [PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation](https://mlsanity.com/paper/2510.12434/) (2025)
- [Semantic Parsing with Candidate Expressions for Knowledge Base Question Answering](https://mlsanity.com/paper/2410.00414/) (2024)
- [From Static to Dynamic: Adaptive Monte Carlo Search for Mathematical Process Supervision](https://mlsanity.com/paper/2509.24351/) (2025)
- [RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering](https://mlsanity.com/paper/2603.20017/) (2026)
- [EcoThink: A Green Adaptive Inference Framework for Sustainable and Accessible Agents](https://mlsanity.com/paper/2603.25498/) (2026)
- [Cognitive Inception: Agentic Reasoning against Visual Deceptions by Injecting Skepticism](https://mlsanity.com/paper/2511.17672/) (2025)
- [Reward on Path: Learning Intermediate Supervision Signals for Knowledge Graph Question Answering](https://mlsanity.com/paper/2605.10791/) (2026)
- [PersonalAI 2.0: Enhancing knowledge graph traversal/retrieval with planning mechanism for Personalized LLM Agents](https://mlsanity.com/paper/2605.13481/) (2026)
- [EvolveNav: Proactive Preflection and Self-Evolving Memory for Zero-Shot Object Goal Navigation](https://mlsanity.com/paper/2606.18235/) (2026)
- [AGE: Adaptive-masking for Graph Embedding in Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2607.00052/) (2026)
- [When Order Matters: First-Speaker Bias and Mitigation through Personality in Sequential Multi-Agent Debate](https://mlsanity.com/paper/2609.38964/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) may suffer from hallucinations in real-world applications due to the lack of relevant knowledge. In contrast, knowledge graphs encompass extensive, multi-relational structures that store a vast array of symbolic facts. Consequently, integrating LLMs with knowledge graphs has been extensively explored, with Knowledge Graph Question Answering (KGQA) serving as a critical touchstone for the integration. This task requires LLMs to answer natural language questions by retrieving relevant triples from knowledge graphs. However, existing methods face two significant challenges: textitexcessively long reasoning paths distracting from the answer generation, and textitfalse-positive relations hindering the path refinement. In this paper, we propose an iterative interactive KGQA framework that leverages the interactive learning capabilities of LLMs to perform reasoning and Debating over Graphs (DoG). Specifically, DoG employs a subgraph-focusing mechanism, allowing LLMs to perform answer trying after each reasoning step, thereby mitigating the impact of lengthy reasoning paths. On the other hand, DoG utilizes a multi-role debate team to gradually simplify complex questions, reducing the influence of false-positive relations. This debate mechanism ensures the reliability of the reasoning process. Experimental results on five public datasets demonstrate the effectiveness and superiority of our architecture. Notably, DoG outperforms the state-of-the-art method ToG by 23.7% and 9.1% in accuracy on WebQuestions and GrailQA, respectively. Furthermore, the integration experiments with various LLMs on the mentioned datasets highlight the flexibility of DoG. Code is available at urlhttps://github.com/reml-group/DoG.