Debate-on-Graph: Reliable and Adaptive Reasoning of Large Language Model on Uncertain Knowledge Graph

• URL: http://arxiv.org/abs/2607.17266v1
• Date: Sun, 19 Jul 2026 14:17:37 GMT
• Title: Debate-on-Graph: Reliable and Adaptive Reasoning of Large Language Model on Uncertain Knowledge Graph
• Abstract summary: Large language models (LLMs) have demonstrated remarkable capabilities in natural language processing.<n>LLMs often suffer from hallucinations and lack of relevant knowledge when dealing with question answering (QA) tasks.<n>We propose Debate-on-Graph (DoG), a new framework that enables LLMs and UKGs to collaborate adaptively for reliable reasoning.
• Score: 8.035556855886657
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Large language models (LLMs) have demonstrated remarkable capabilities in natural language processing. However, LLMs often suffer from hallucinations and lack of relevant knowledge when dealing with question answering (QA) tasks. To mitigate these issues, knowledge graphs (KGs) have been utilized to enhance LLM reasoning. Nevertheless, KGs often contain noise and errors, while existing KG-enhanced LLM approaches are generally unable to identify and filter such noisy and erroneous content, which can instead amplify hallucinations and pose challenges for reliable reasoning. Uncertain knowledge graphs (UKGs), which associate each triple with a confidence score to quantify uncertainty, offer a promising direction to address this challenge. Compared with prior work, we investigate how to leverage UKGs to support LLMs for QA. We propose Debate-on-Graph (DoG), a new framework that enables LLMs and UKGs to collaborate adaptively for reliable reasoning. Specifically, we first design a heuristic search algorithm tailored for UKGs to extract reliable and question-relevant subgraphs, thereby reducing noise and errors in retrieved knowledge. We then introduce a Multi-Agent Debate mechanism, which yields reliable answers through adaptive adversarial debates, aiming to fully exploit the knowledge in UKGs while preserving the reliability of retrieved evidence. Extensive experiments on four benchmark QA datasets show that DoG achieves state-of-the-art performance over existing LLM reasoning methods and KG-based baselines, while enabling reliable and adaptive reasoning. Our code is available at https://github.com/seucoin/Debate-on-Graph.

Related papers

• Multi-hop Reasoning and Retrieval in Embedding Space: Leveraging Large Language Models with Knowledge [7.792321858331646]
  We propose an embedding-based retrieval reasoning framework EMBRAG.<n>We show that our approach achieves the new state-of-the-art performance in KG reasoning tasks.
  arXiv  Detail & Related papers  (2026-02-25T23:55:21Z)
• ProgRAG: Hallucination-Resistant Progressive Retrieval and Reasoning over Knowledge Graphs [2.9539912037183362]
  Large Language Models (LLMs) demonstrate strong reasoning capabilities but struggle with hallucinations and limited transparency.<n>We propose ProgRAG, a multi-hop knowledge graph question answering (KGQA) framework that decomposes complex questions into sub-questions and extends partial reasoning paths.<n> Experiments on three well-known datasets demonstrate that ProgRAG outperforms existing baselines in multi-hop KGQA.
  arXiv  Detail & Related papers  (2025-11-13T12:14:36Z)
• Enrich-on-Graph: Query-Graph Alignment for Complex Reasoning with LLM Enriching [61.824094419641575]
  Large Language Models (LLMs) struggle with hallucinations and factual errors in knowledge-intensive scenarios like knowledge graph question answering (KGQA)<n>We attribute this to the semantic gap between structured knowledge graphs (KGs) and unstructured queries, caused by inherent differences in their focuses and structures.<n>Existing methods usually employ resource-intensive, non-scalable reasoning on vanilla KGs, but overlook this gap.<n>We propose a flexible framework, Enrich-on-Graph (EoG), which leverages LLMs' prior knowledge to enrich KGs, bridge the semantic gap between graphs and queries.
  arXiv  Detail & Related papers  (2025-09-25T06:48:52Z)
• Knowledge Graphs, Large Language Models, and Hallucinations: An NLP Perspective [5.769786334333616]
  Large Language Models (LLMs) have revolutionized Natural Language Processing (NLP) based applications including automated text generation, question answering, and others. They face a significant challenge: hallucinations, where models produce plausible-sounding but factually incorrect responses. This paper discusses these open challenges covering state-of-the-art datasets and benchmarks as well as methods for knowledge integration and evaluating hallucinations.
  arXiv  Detail & Related papers  (2024-11-21T16:09:05Z)
• Decoding on Graphs: Faithful and Sound Reasoning on Knowledge Graphs through Generation of Well-Formed Chains [66.55612528039894]
  Knowledge Graphs (KGs) can serve as reliable knowledge sources for question answering (QA) We present DoG (Decoding on Graphs), a novel framework that facilitates a deep synergy between LLMs and KGs. Experiments across various KGQA tasks with different background KGs demonstrate that DoG achieves superior and robust performance.
  arXiv  Detail & Related papers  (2024-10-24T04:01:40Z)
• Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models [92.71304585906624]
  Large language models (LLMs) struggle with faithful reasoning due to knowledge gaps and hallucinations.<n>We introduce graph-constrained reasoning (GCR), a novel framework that bridges structured knowledge in KGs with unstructured reasoning in LLMs.<n>GCR achieves state-of-the-art performance and exhibits strong zero-shot generalizability to unseen KGs without additional training.
  arXiv  Detail & Related papers  (2024-10-16T22:55:17Z)
• Can Knowledge Graphs Make Large Language Models More Trustworthy? An Empirical Study Over Open-ended Question Answering [30.12049172634714]
  We introduce OKGQA, a benchmark specifically designed to evaluate Large Language Models augmented with Knowledge Graphs.<n> OKGQA reflects practical complexities through diverse question types and incorporates metrics to quantify both hallucination rates and reasoning improvements.<n>We propose a benchmark variant, OKGQA-P, to assess model performance when the semantics and structure of KGs are deliberately perturbed and contaminated.
  arXiv  Detail & Related papers  (2024-10-10T16:29:21Z)
• Debate on Graph: a Flexible and Reliable Reasoning Framework for Large Language Models [33.662269036173456]
  Large Language Models (LLMs) may suffer from hallucinations in real-world applications due to the lack of relevant knowledge. Knowledge Graph Question Answering (KGQA) serves as a critical touchstone for the integration. We propose an interactive KGQA framework that leverages the interactive learning capabilities of LLMs to perform reasoning and Debating over Graphs (DoG)
  arXiv  Detail & Related papers  (2024-09-05T01:11:58Z)
• LinkQ: An LLM-Assisted Visual Interface for Knowledge Graph Question-Answering [1.5238808518078564]
  LinkQ is a system that leverages a large language model (LLM) to facilitate knowledge graph (KG) query construction through natural language question-answering.<n>LLM interprets a user's question, then systematically converts it into a well-formed query.<n>LinkQ guards against the LLM hallucinating outputs by ensuring users' questions are only ever answered from ground truth KG data.
  arXiv  Detail & Related papers  (2024-06-07T15:28:31Z)
• Logic Query of Thoughts: Guiding Large Language Models to Answer Complex Logic Queries with Knowledge Graphs [102.37496443389203]
  'Logic-Query-of-Thoughts' (LGOT) is the first of its kind to combine knowledge graph reasoning and large language models.<n>Our experimental findings demonstrate substantial performance enhancements, with up to 20% improvement over ChatGPT.
  arXiv  Detail & Related papers  (2024-03-17T17:01:45Z)
• CLadder: Assessing Causal Reasoning in Language Models [82.8719238178569]
  We investigate whether large language models (LLMs) can coherently reason about causality. We propose a new NLP task, causal inference in natural language, inspired by the "causal inference engine" postulated by Judea Pearl et al.
  arXiv  Detail & Related papers  (2023-12-07T15:12:12Z)
• Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-based Retrofitting [51.7049140329611]
  This paper proposes Knowledge Graph-based Retrofitting (KGR) to mitigate factual hallucination during the reasoning process. Experiments show that KGR can significantly improve the performance of LLMs on factual QA benchmarks.
  arXiv  Detail & Related papers  (2023-11-22T11:08:38Z)
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning [104.92384929827776]
  Large language models (LLMs) have demonstrated impressive reasoning abilities in complex tasks. They lack up-to-date knowledge and experience hallucinations during reasoning. Knowledge graphs (KGs) offer a reliable source of knowledge for reasoning.
  arXiv  Detail & Related papers  (2023-10-02T10:14:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.