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

# Debate-on-Graph: Reliable and Adaptive Reasoning of Large Language Model on Uncertain Knowledge Graph
Source: [https://arxiv.org/html/2607.17266](https://arxiv.org/html/2607.17266)
11institutetext:School of Computer Science and Engineering, Southeast University, Nanjing, China11email:\{213232231,213231269,tianxingwu\}@seu\.edu\.cn22institutetext:Key Laboratory of New Generation Artificial Intelligence Technology and Its Interdisciplinary Applications \(Southeast University\), Ministry of Education, China###### 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 proposeDebate\-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](https://github.com/seucoin/Debate-on-Graph)\.

## 1Introduction

Large language models \(LLMs\) have demonstrated remarkable capabilities in natural language processing\[[2](https://arxiv.org/html/2607.17266#bib.bib22),[14](https://arxiv.org/html/2607.17266#bib.bib16),[31](https://arxiv.org/html/2607.17266#bib.bib19),[40](https://arxiv.org/html/2607.17266#bib.bib15)\]\. However, when dealing with question answering \(QA\) tasks, LLMs often suffer from hallucinations\[[15](https://arxiv.org/html/2607.17266#bib.bib31)\]and lack of relevant knowledge, which can undermine the reliability of their responses\. To mitigate these issues, knowledge graphs \(KGs\)\[[12](https://arxiv.org/html/2607.17266#bib.bib35)\], which describe real\-world facts in the form of triples denoted as\(h​e​a​d,r​e​l​a​t​i​o​n,t​a​i​l\)\(head,relation,tail\), or simply\(h,r,τ\)\(h,r,\\tau\), have been frequently utilized to enhance LLM reasoning\[[26](https://arxiv.org/html/2607.17266#bib.bib25),[16](https://arxiv.org/html/2607.17266#bib.bib2)\]\. As a structured and non\-parametric external knowledge source, KGs offer a complementary strategy to alleviate the inherent limitations of LLMs\[[18](https://arxiv.org/html/2607.17266#bib.bib47),[21](https://arxiv.org/html/2607.17266#bib.bib30)\]\.

Prior studies on KG\-enhanced LLM reasoning can be broadly categorized into two paradigms:retrieval\-basedandagent\-basedapproaches\[[17](https://arxiv.org/html/2607.17266#bib.bib3)\]\. Retrieval\-based approaches\[[16](https://arxiv.org/html/2607.17266#bib.bib2),[37](https://arxiv.org/html/2607.17266#bib.bib28),[19](https://arxiv.org/html/2607.17266#bib.bib4)\]employ an external retriever to fetch relevant facts from KGs and incorporate them into the LLM input for reasoning, while agent\-based approaches\[[26](https://arxiv.org/html/2607.17266#bib.bib25),[30](https://arxiv.org/html/2607.17266#bib.bib26),[10](https://arxiv.org/html/2607.17266#bib.bib27)\]treat LLMs as agents that directly interact with KGs, starting from an initial entity and iteratively exploiting reasoning paths until the LLM decides the augmented knowledge is sufficient\.

However, since the automatic process has been widely applied in the construction of KGs, they may often contain noise and factual errors\[[43](https://arxiv.org/html/2607.17266#bib.bib43)\]\. Despite notable progress, both categories of KG\-enhanced approaches remain sensitive to such imperfections, posing challenges for reliable reasoning\. Specifically, in retrieval\-based approaches, retrievers may retrieve irrelevant or incorrect facts, which can mislead generation; in this case, the injected evidence not only fails to reduce hallucinations but may even amplify them\[[19](https://arxiv.org/html/2607.17266#bib.bib4)\]\. For agent\-based approaches, noisy or erroneous triples can mislead the LLM at early interaction steps, making the entire multi\-step process unreliable\[[26](https://arxiv.org/html/2607.17266#bib.bib25)\]\.

Uncertain knowledge graphs \(UKGs\), which have attracted increasing attention recently, are ideally suited for capturing the uncertainties inherent in real\-world scenarios\. A UKG associates each triple with a confidence score to quantify uncertainty, where the score represents the probability of that triple being true\[[3](https://arxiv.org/html/2607.17266#bib.bib41),[24](https://arxiv.org/html/2607.17266#bib.bib12)\]\. Thus, each fact is expanded from a triple\(h,r,τ\)\(h,r,\\tau\)to a quadruple as\(h,r,τ,c\)\(h,r,\\tau,c\)\. For example,\(Twitter, competeswith, Facebook, 0\.85\)represents the probability of the fact “Twitter competes with Facebook” is 0\.85\. This design captures the inherent uncertainty of real\-world knowledge, which paves the way for identifying and filtering noisy or erroneous knowledge, opening up new opportunities for reliable reasoning\.

Compared with prior work, we investigate how to leverage UKGs to assist LLMs for QA \(i\.e\., the UKGQA task\) for reliable reasoning\. Here, a key new challenge ishow to fully exploit the knowledge in UKGs while reserving the reliability of retrieved evidence, as there is always a trade\-off between knowledge utility and reliability\. We propose that an ideal approach should adapt to each question, striking a balance between knowledge utility and reliability, and using this balance to guide retrieval so that LLMs can reduce hallucinations and perform reliable and effective reasoning\.

To address this challenge, we proposeDebate\-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 for UKGs to extract reliable and question\-relevant subgraphs, thereby reducing noise and errors in retrieved knowledge\. The algorithm also supports tunable hyperparameter to dynamically expand the subgraph if needed\. We then introduce aMulti\-Agent Debate \(MAD\)mechanism\[[9](https://arxiv.org/html/2607.17266#bib.bib36),[13](https://arxiv.org/html/2607.17266#bib.bib37)\]with four roles: a Proponent Agent, a Challenger Agent, a Decision\-Making Agent, and a Judge Agent\. The Proponent and Challenger engage in adversarial debates under an information\-asymmetric setting, which reduces the LLM’s over\-reliance on retrieved content and improves robustness to noisy or erroneous facts\. The Decision\-Making Agent subsequently determines whether expand the subgraph or terminate the debate, aiming to fully exploit the UKG while keeping retrieval reliable\. Finally, the Judge Agent synthesizes the debate outcomes and determines the final answer\.

Overall, the contributions of our work are three\-fold:

- −\-We present Debate\-on\-Graph, a new framework that facilitates adaptive collaboration between LLMs and UKGs for reliable reasoning\.
- −\-We propose a heuristic search algorithm tailored for UKGs that can dynamically extract reliable and question\-relevant subgraphs, thereby reducing noise and errors in the retrieved knowledge\.
- −\-We design a MAD\-based answer generation strategy that guides LLMs to yield reliable answers through adaptive interaction with UKG subgraphs, aiming to fully exploit the UKG while keeping retrieval reliable\.

## 2Related Work

### 2\.1Uncertain Knowledge Graph

Deterministic Knowledge Graphs \(DKGs\), such as Freebase\[[1](https://arxiv.org/html/2607.17266#bib.bib38)\]and Wikidata\[[32](https://arxiv.org/html/2607.17266#bib.bib40)\], consist of deterministic facts, have been utilized for different applications\[[11](https://arxiv.org/html/2607.17266#bib.bib57),[7](https://arxiv.org/html/2607.17266#bib.bib56),[25](https://arxiv.org/html/2607.17266#bib.bib55)\]\. In contrast, UKGs associate each triple with a confidence score, thereby capturing the universal uncertainty and fuzziness of real\-world knowledge\. Representative examples of UKGs include NELL\[[3](https://arxiv.org/html/2607.17266#bib.bib41)\]and ConceptNet\[[24](https://arxiv.org/html/2607.17266#bib.bib12)\]\.

Recently, the task of UKG completion, which encompasses confidence prediction and link prediction, has attracted increasing attention\[[33](https://arxiv.org/html/2607.17266#bib.bib48)\]\. Current research\[[5](https://arxiv.org/html/2607.17266#bib.bib50),[8](https://arxiv.org/html/2607.17266#bib.bib51),[41](https://arxiv.org/html/2607.17266#bib.bib44),[6](https://arxiv.org/html/2607.17266#bib.bib53),[39](https://arxiv.org/html/2607.17266#bib.bib49)\]in this domain primarily focuses on normal relational learning, which embeds entities and relations while preserving both graph structures and confidence information\. Moreover, recent studies have extended this focus to few\-shot relational learning to address the long\-tail distribution of relations commonly observed in real\-world UKGs\[[43](https://arxiv.org/html/2607.17266#bib.bib43),[34](https://arxiv.org/html/2607.17266#bib.bib52)\]\. However, the task of leveraging UKG to support LLMs for QA remains unexplored\. UKGs are essential for many downstream applications, such as dietary recommendation\[[23](https://arxiv.org/html/2607.17266#bib.bib46)\]and upper limb motor recovery\[[38](https://arxiv.org/html/2607.17266#bib.bib45)\]\.

### 2\.2KG\-enhanced LLM Reasoning

To mitigate the hallucinations and knowledge gaps inherent in LLMs, integrating KGs with LLMs has established itself as a critical research direction\[[21](https://arxiv.org/html/2607.17266#bib.bib30),[4](https://arxiv.org/html/2607.17266#bib.bib54)\]\. Existing methodologies can be primarily categorized intoretrieval\-basedandagent\-basedparadigms\.

Retrieval\-based approaches focus on identifying and extracting relevant knowledge from KGs to augment the input context of the LLM\. Early works in this domain often linearize knowledge triples directly, whereas recent advancements exploit the structural information of the graph\. For instance, MindMap\[[37](https://arxiv.org/html/2607.17266#bib.bib28)\]utilizes KGs to elicit a cognitive map for the LLM, thereby revealing reasoning pathways\. RoG\[[16](https://arxiv.org/html/2607.17266#bib.bib2)\]generates relation paths as plans to retrieve valid reasoning subgraphs\. Similarly, GNN\-RAG\[[19](https://arxiv.org/html/2607.17266#bib.bib4)\]employs Graph Neural Networks to retrieve answer candidates and extract the shortest paths connecting question entities\. While effective for direct fact retrieval, these approaches often overlook the rich structural dependencies within KGs and struggle to handle the noise introduced by irrelevant retrieved information\.

In contrast, agent\-based approaches treat the LLM as an autonomous agent that interactively explores the KG to perform complex reasoning\. Instead of a static retrieval step, these approaches navigate the graph structure iteratively to locate answers\. For instance, ToG\[[26](https://arxiv.org/html/2607.17266#bib.bib25)\]implements a beam search strategy, enabling the LLM to discover reasoning paths step\-by\-step\. PoG\[[30](https://arxiv.org/html/2607.17266#bib.bib26)\]focuses on pruning irrelevant information to enhance the faithfulness and interpretability of the reasoning process\. KARPA\[[10](https://arxiv.org/html/2607.17266#bib.bib27)\]leverages the global planning capabilities of LLMs to pre\-plan relation paths, matches them via an embedding model, and aggregates them to avoid stepwise local optima\. However, agent\-based paradigms are prune to errors, as noisy or erroneous triples encountered during interaction can significantly mislead the entire trajectory of the LLM on KGs\.

## 3Preliminary

In this section, we introduce the basic concepts and notation used throughout the paper\.

###### Definition 1\(Uncertain Knowledge Graph\)

An Uncertain Knowledge Graph is defined as𝒢​\(ℰ,ℛ,𝒯\)\\mathcal\{G\}\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\), whereℰ\\mathcal\{E\},ℛ\\mathcal\{R\}and𝒯\\mathcal\{T\}denote the set of entities, relations and uncertain knowledge triples, respectively\.

Each triplet∈𝒯t\\in\\mathcal\{T\}is a quadruple:

t=\(h,r,τ,c\),h,τ∈ℰ,r∈ℛ,c∈\(0,1\],t=\(h,r,\\tau,c\),\\quad h,\\tau\\in\\mathcal\{E\},\\ r\\in\\mathcal\{R\},\\ c\\in\(0,1\],\(1\)whereccis the confidence score indicating the probability that the triple is true\.

###### Definition 2\(Uncertain Knowledge Graph Question Answering\)

Given a natural language questionQQand a UKG𝒢\\mathcal\{G\}, Uncertain Knowledge Graph Question Answering is a task aiming to design a functionffthat predicts an answeraausing the knowledge from𝒢\\mathcal\{G\}, i\.e\.,a=f​\(Q,𝒢\)a=f\(Q,\\mathcal\{G\}\)\.

###### Definition 3\(Topic Entities\)

Topic Entities are a set of entities:ℰtopic=\{e1,e2,…,eJ\}\\mathcal\{E\}\_\{\\text\{topic\}\}=\\\{e\_\{1\},e\_\{2\},\\ldots,e\_\{J\}\\\}that are related to the UKG\-based question, whereej∈ℰe\_\{j\}\\in\\mathcal\{E\}denotes thejj\-th entity in the questionQQ\.

The set of topic entities can be obtained via named entity recognition \(NER\) and entity linking techniques\.

###### Definition 4\(Reasoning Paths\)

A Reasoning Path from entityuuto entityvvis an ordered sequence of triples:

p=⟨t1,t2,…,tk⟩,p=\\langle t\_\{1\},t\_\{2\},\\ldots,t\_\{k\}\\rangle,\(2\)where each triple has the formti=\(hi,ri,τi,ci\)t\_\{i\}=\(h\_\{i\},r\_\{i\},\\tau\_\{i\},c\_\{i\}\)andh1=u,τk=v,τi=hi\+1​for​i=1,…,k−1\.h\_\{1\}=u,\\quad\\tau\_\{k\}=v,\\quad\\tau\_\{i\}=h\_\{i\+1\}\\ \\text\{for\}\\ i=1,\\ldots,k\-1\.

###### Definition 5\(Path Confidence\)

Given a reasoning pathp=⟨t1,…,tk⟩p=\\langle t\_\{1\},\\ldots,t\_\{k\}\\ranglewith triple confidences\{ci\}i=1k\\\{c\_\{i\}\\\}\_\{i=1\}^\{k\}, the confidence of the whole path is defined as the product of its triple confidences:

C​o​n​f​\(p\)=∏i=1kci\.Conf\(p\)=\\prod\_\{i=1\}^\{k\}c\_\{i\}\.\(3\)

###### Definition 6\(Path–Question Semantic Relevance\)

Letf​\(⋅,⋅\)f\(\\cdot,\\cdot\)denote a similarity function between the pathppand the questionQQ:

S​R​\(p,Q\)=f​\(p,Q\)\.SR\(p,Q\)=f\(p,Q\)\.\(4\)

We calculatef​\(⋅,⋅\)f\(\\cdot,\\cdot\)using a pre\-trained language model \(PLM\), e\.g\. SentenceBERT\[[22](https://arxiv.org/html/2607.17266#bib.bib1)\]\.

###### Definition 7\(Reasoning Path Score\)

Given a questionQQ, the Reasoning Path Score of pathppis determined by their semantic relevance and Path Confidence:

S​c​o​r​e​\(p,Q\)=S​R​\(p,Q\)⋅\(C​o​n​f​\(p\)\)αScore\(p,Q\)=SR\(p,Q\)\\cdot\(Conf\(p\)\)^\{\\alpha\}\(5\)whereα\\alphais a hyperparameter controlling the trade\-off between question relevance and Path Confidence\.

This matches the intuition that a path should be preferred when it is both semantically aligned with the question and supported by high\-confidence triples\.

###### Definition 8\(Entity Distance\)

The entity distance between entitiesuuandvvis defined as:

D​i​s​t​a​n​c​e​\(u,v\)=minp∈𝒫​\(u,v\)⁡H​o​p​\(p\)C​o​n​f​\(p\)\.Distance\(u,v\)=\\min\_\{p\\in\\mathcal\{P\}\(u,v\)\}\\frac\{Hop\(p\)\}\{Conf\(p\)\}\.\(6\)where𝒫​\(u,v\)\\mathcal\{P\}\(u,v\)denotes the set of reasoning paths fromuutovv, andH​o​p​\(p\)Hop\(p\)represents the number of hops inpp\.

Entity Distance favors shortness \(as smallerH​o​p​\(p\)Hop\(p\)reduces the distance\) and reliability \(as largerC​o​n​f​\(p\)Conf\(p\)reduces the distance\), thereby prioritizing paths that are both concise and trustworthy\.

## 4The Approach: Debate\-on\-Graph

The overall framework of DoG, as illustrated in Fig\.[1](https://arxiv.org/html/2607.17266#S4.F1), consists of two steps: Step 1 for reliable subgraph extraction and Step 2 for multi\-agent based answer generation, which are detailed in Sections[4\.1](https://arxiv.org/html/2607.17266#S4.SS1)and[4\.2](https://arxiv.org/html/2607.17266#S4.SS2), respectively\.

![Refer to caption](https://arxiv.org/html/2607.17266v1/x1.png)Figure 1:The overview of Debate\-on\-Graph framework\.For UKGQA tasks, given a questionQQ, we first obtain the set of topic entities via NER and entity linking techniques\. Subsequently, for each topic entity, we employ the subgraph extraction algorithm to extract a question\-relevant subgraph111For question with multiple topic entities, we simply perform subgraph extraction for each one of them, retrieving a corresponding set of subgraphs to answer the question\.\. Finally, we convert the subgraph into textual descriptions, and apply the multi\-agent based framework to obtain the final answer\.

### 4\.1Reliable Subgraph Extraction

To effectively reduce noise and errors in UKGs, we propose a heuristic subgraph extraction algorithm, as illustrated in Fig\.[2](https://arxiv.org/html/2607.17266#S4.F2)\. This algorithm operates on a best\-first search paradigm, designed to dynamically extract question\-relevant subgraphs that are both semantically aligned with the query and factually reliable\. The algorithm initiates with a topic entityec​e​n∈ℰt​o​p​i​ce\_\{cen\}\\in\\mathcal\{E\}\_\{topic\}, which serves as the central entity and a potential starting anchor for the search process\. To manage the search space efficiently, we maintain a priority queue that orders candidate entities based on their distance to the center entity\.

![Refer to caption](https://arxiv.org/html/2607.17266v1/x2.png)Figure 2:The overview of the subgraph extraction algorithm\.For a specific entityeein UKG𝒢\\mathcal\{G\}, the algorithm iteratively explores its neighborhood to identify the most promising expansion paths\. Specifically, we first sample all unvisited direct neighborsℰc​a​n​dn​e​i=\{e1n​e​i,e2n​e​i,…,enn​e​i\}\\mathcal\{E\}^\{nei\}\_\{cand\}=\\\{e^\{nei\}\_\{1\},e^\{nei\}\_\{2\},\\ldots,e^\{nei\}\_\{n\}\\\}ofee\. The core challenge lies in evaluating the utility of these neighbors given the uncertainty inherent in the UKG\. To address this, we retrieve the set of existing reasoning paths𝒫c​a​n​d​\(ein​e​i\)\\mathcal\{P\}\_\{cand\}\(e^\{nei\}\_\{i\}\)fromec​e​ne\_\{cen\}toeeand extend them by appending the connecting triple\(e,r,ein​e​i\)\(e,r,e\_\{i\}^\{nei\}\)for each neighborein​e​ie^\{nei\}\_\{i\}, generating a candidate set of extended paths defined as:

𝒫c​a​n​d​\(ein​e​i\)=\{p⊕\(e,r,ein​e​i\)∣p∈𝒫s​e​l​e​c​t​\(e\)\},\\mathcal\{P\}\_\{cand\}\(e^\{nei\}\_\{i\}\)=\\\{p\\oplus\(e,r,e^\{nei\}\_\{i\}\)\\mid p\\in\\mathcal\{P\}\_\{select\}\(e\)\\\},\(7\)where⊕\\oplusdenotes the path concatenation operation\. We then evaluate each of these extended paths individually using the path scoring functionS​c​o​r​e​\(p,Q\)Score\(p,Q\)defined in Eq\. \([5](https://arxiv.org/html/2607.17266#S3.E5)\), which integrates both the semantic relevanceS​R​\(p,Q\)SR\(p,Q\)and the path confidenceC​o​n​f​\(p\)Conf\(p\)\.

To prevent the retrieval of irrelevant noise and to control the scale of the subgraph, we employ a selective pruning strategy\. Instead of expanding all neighbors, we select only the top\-WWentities with the highest maximum path scores\. Formally, we define the score of a neighboren​e​ie\_\{nei\}as the maximum score among all paths reaching it, and retrieve the set of selected entitiesℰs​e​l​e​c​tn​e​i\\mathcal\{E\}\_\{select\}^\{nei\}as:

ℰs​e​l​e​c​tn​e​i=Top​\-​Wen​e​i∈ℰc​a​n​dn​e​i\(maxp∈𝒫c​a​n​d​\(en​e​i\)⁡Score​\(p,Q\)\)\\mathcal\{E\}\_\{select\}^\{nei\}=\\mathop\{\\mathrm\{Top\\text\{\-\}\}W\}\\limits\_\{e\_\{nei\}\\in\\mathcal\{E\}^\{nei\}\_\{cand\}\}\\left\(\\max\_\{p\\in\\mathcal\{P\}\_\{cand\}\(e\_\{nei\}\)\}\\mathrm\{Score\}\(p,Q\)\\right\)\(8\)where𝒫c​a​n​d​\(en​e​i\)\\mathcal\{P\}\_\{cand\}\(e\_\{nei\}\)denotes the set of extended paths from the center entityec​e​ne\_\{cen\}to neighboren​e​ie\_\{nei\}\. This hyperparameterWWacts as an adaptive expansion width, allowing the algorithm to focus computational resources on the most plausible branches of knowledge\.

Furthermore, to ensure the quality of the retrieved evidence, we calculate a dynamic scoring threshold based on these selected entities\. Only reasoning paths that exceed this threshold are retained in the path set𝒫s​e​l​e​c​t\\mathcal\{P\}\_\{select\}for each selected neighbor:

𝒫s​e​l​e​c​t=\{p∈𝒫c​a​n​d∣S​c​o​r​e​\(p,Q\)≥mine∈ℰs​e​l​e​c​tn​e​i⁡S​c​o​r​e​\(en​e​i\)\},\\mathcal\{P\}\_\{select\}=\\left\\\{p\\in\\mathcal\{P\}\_\{cand\}\\mid Score\(p,Q\)\\geq\\min\_\{e\\in\\mathcal\{E\}\_\{select\}^\{nei\}\}Score\(e\_\{nei\}\)\\right\\\},\(9\)where𝒫c​a​n​d\\mathcal\{P\}\_\{cand\}denotes the set of candidate paths extending to the selected entity andS​c​o​r​e​\(en​e​i\)Score\(e\_\{nei\}\)represents the score of entityen​e​ie\_\{nei\}\.

Subsequently, the algorithm updates the priority queue with these selected neighbors\. If a neighboren​e​ie\_\{nei\}is encountered for the first time, it is inserted into the queue with a priority determined by its Entity Distance to the center entity\. Conversely, ifen​e​ie\_\{nei\}is already present in the queue, we merge the newly discovered paths with the existing ones, keeping only the top\-KKpaths with the highest scores, and update its priority if a shorter or more confident path is found\. The expansion process repeats by extracting the entity with the minimum Entity Distance from the priority queue, until the distance of the closest candidate exceeds a pre\-defined maximum thresholdDm​a​xD\_\{max\}\. Finally, the extracted subgraph is constructed from the union of all high\-quality triples contained within the reasoning path sets of the visited entities, providing a robust and concise knowledge basis for the subsequent reasoning phase\.

#### 4\.1\.1The critical role ofKKin the algorithm

As a critical hyperparameter in the subgraph extraction algorithm,KKdictates the maximum number of reasoning paths retained for each entity\. It effectively modulates the trade\-off between knowledge utility and reliability\. WhenKKis set to a conservative value, the constructed subgraph contains only the most reliable and semantically relevant paths; however, this strict filtering may result in an information deficit, preventing the model from deriving a determinate answer\. Conversely, an excessively largeKKincorporates a wealth of information but inevitably introduces lower\-confidence paths and noise, thereby amplifying the risk of hallucinations and diminishing the reliability of the reasoning process\. Consequently, finding an optimalKKis essential to balance knowledge utility against evidence reliability, which will be reflected in the next section\.

Due to the space limitation, the pseudo\-code of subgraph extraction is shown in the supplementary material\.

### 4\.2Multi\-Agent Debate for Answer Generation

Despite the efficacy of the heuristic search algorithm in extracting relevant subgraphs, there may be still some residual noise or factual inaccuracies in the extracted context, which can inadvertently mislead the LLM\[[13](https://arxiv.org/html/2607.17266#bib.bib37)\]\. Meanwhile, we aim to fully exploit the knowledge in UKGs while reserving the reliability of retrieved evidence\. To tackle these challenges, we propose aMulti\-Agent Debate \(MAD\)mechanism\[[9](https://arxiv.org/html/2607.17266#bib.bib36),[13](https://arxiv.org/html/2607.17266#bib.bib37)\]that dynamically navigates the trade\-off between knowledge utility and evidence reliability\. This mechanism operates by adaptively adjusting the subgraph expansion parameterKKto guide the LLM toward a reliable answer\.

The MAD\-based framework consists of four distinct roles: aProponent AgentRpR\_\{p\}, aChallenger AgentRcR\_\{c\}, aDecision\-Making AgentRdR\_\{d\}, and aJudge AgentRjR\_\{j\}\. A critical feature of this design is an information\-asymmetric setting between the debating roles\. The Proponent Agent is granted access to the retrieved UKG subgraph description corresponding to the current expansion levelKK, allowing it to ground its arguments in external evidence\. In contrast, the Challenger Agent is restricted from accessing the subgraph, forcing it to rely exclusively on its internal knowledge\. This design is critical to mitigating the LLM’s tendency to over\-rely on retrieved context; if both agents possessed identical access to the subgraph, they might unthinkingly converge on erroneous retrieved facts rather than critically evaluating their validity\[[13](https://arxiv.org/html/2607.17266#bib.bib37)\]\.

The debate unfolds as an iterative optimization process over a pre\-defined candidate set of expansion thresholdsΘ=\{k1,k2,…,kn\}\\Theta=\\\{k\_\{1\},k\_\{2\},\\dots,k\_\{n\}\\\},kj\>kik\_\{j\}\>k\_\{i\}ifj\>ij\>i\. In the initial round, the Proponent generates a preliminary response based on the most reliable subgraph𝒢Qk1\\mathcal\{G\}\_\{Q\}^\{k\_\{1\}\}constructed withK=k1K=k\_\{1\}, while the Challenger initiates the response based on its internal knowledge:

yp1=ℛp​\(Q,𝒢Qk1\)y^\{1\}\_\{p\}=\\mathcal\{R\}\_\{p\}\(Q,\\mathcal\{G\}\_\{Q\}^\{k\_\{1\}\}\)\(10\)yc1=ℛc​\(Q\)y^\{1\}\_\{c\}=\\mathcal\{R\}\_\{c\}\(Q\)\(11\)whereyp1y^\{1\}\_\{p\}andyc1y^\{1\}\_\{c\}represent the response from the Proponent Agent and Challenger Agent in the first round, respectively\.

In subsequent rounds, both agents refine their responses by critiquing the opponent’s previous response, thereby exposing inconsistencies or logical gaps:

ypi=ℛp​\(Q,𝒢Qkj,\{yp<i\},yci−1\),for​i≥2y^\{i\}\_\{p\}=\\mathcal\{R\}\_\{p\}\(Q,\\mathcal\{G\}\_\{Q\}^\{k\_\{j\}\},\\\{y^\{<i\}\_\{p\}\\\},y^\{i\-1\}\_\{c\}\),\\quad\\text\{for \}i\\geq 2\(12\)yci=ℛc​\(Q,\{yc<i\},ypi−1\),for​i≥2y^\{i\}\_\{c\}=\\mathcal\{R\}\_\{c\}\(Q,\\\{y^\{<i\}\_\{c\}\\\},y^\{i\-1\}\_\{p\}\),\\quad\\text\{for \}i\\geq 2\(13\)
Throughout this process, the Decision\-Making Agent acts as a meta\-controller, evaluating the state of the debate after every round to select one of three actions: First, if the debate is thorough and the debaters reach a consensus, the debate is terminated\. Second, if the agents remain in disagreement but the evidence is sufficient, the debate proceeds to the next round to further clarify the arguments\. Third, and most notably, if the Decision\-Making Agent identifies that the Proponent lacks sufficient evidence to refute the Challenger or support its claim, it triggers an expansion of the subgraph from current levelkjk\_\{j\}to the next levelkj\+1k\_\{j\+1\}and continues the debate\. This adaptive expansion, formalized as Eq\. \([14](https://arxiv.org/html/2607.17266#S4.E14)\), injects richer knowledge into the Proponent’s context when necessary, allowing for more comprehensive reasoning in the subsequent round\. In this way, DoG realizes adaptive reasoning by dynamically selecting both the evidence scope and the number of debate rounds for each question\.

ACTIONi=ℛd​\(Q,𝒢Qkj,ypi,yci\)\\text\{ACTION\}\_\{i\}=\\mathcal\{R\}\_\{d\}\(Q,\\mathcal\{G\}\_\{Q\}^\{k\_\{j\}\},y^\{i\}\_\{p\},y^\{i\}\_\{c\}\)\(14\)whereACTIONi\\text\{ACTION\}\_\{i\}denotes one of three aforementioned actions\.

Finally, once the debate concludes or reaches the maximum debate roundrm​a​xr\_\{max\}, the Judge Agent synthesizes the debate outcomes to derive a final, verified answeraa\.

a=ℛj​\(Q,ypr,ycr\)a=\\mathcal\{R\}\_\{j\}\(Q,y^\{r\}\_\{p\},y^\{r\}\_\{c\}\)\(15\)wherer≤rm​a​xr\\leq r\_\{max\}denotes the final round of debate\.

The overall Multi\-Agent Debate procedure and the prompt templates for the debate agents can be found in the supplementary material\.

## 5Experiments

In the experiments, we aim to answer the following research questions:RQ1:How does DoG perform compared with state\-of\-the\-art LLM reasoning methods and KG\-based baselines across different QA benchmarks?RQ2:What is the contribution of each component in DoG?RQ3:Can DoG perform adaptive reasoning?RQ4:How do hyperparameters affect the performance of DoG?RQ5:How efficient is DoG in terms of runtime, LLM calls, and token usage compared to other baselines?

### 5\.1Experimental Setup

#### 5\.1\.1Datasets

To comprehensively evaluate the effectiveness of our proposed framework, we conduct experiments on four benchmark datasets across two distinct domains: Commonsense QA and Medical QA\. For the domain of commonsense QA, we select CommonsenseQA \(CSQA\)\[[28](https://arxiv.org/html/2607.17266#bib.bib9)\], CommonsenseQA 2\.0 \(CSQA 2\.0\)\[[29](https://arxiv.org/html/2607.17266#bib.bib10)\], and OpenBookQA \(OBQA\)\[[20](https://arxiv.org/html/2607.17266#bib.bib11)\], utilizing ConceptNet\[[24](https://arxiv.org/html/2607.17266#bib.bib12)\]as the background UKG\. For Medical QA, we employ MedQA\-US, with MedKGent\[[42](https://arxiv.org/html/2607.17266#bib.bib13)\]as the underlying UKG\. The statistics of the datasets are summarized in Table[1](https://arxiv.org/html/2607.17266#S5.T1), while details are provided in the supplementary material\.

Table 1:The statistics of datasets and UKGs used in experiments\.
#### 5\.1\.2Baselines

We compare DoG with two categories of baselines: 1\)LLM reasoning methods, and 2\)KG\-enhanced LLM methods\. For LLM Reasoning methods, we evaluate the intrinsic performance of LLMs without external knowledge using Zero\-shot, Few\-shot prompting\[[2](https://arxiv.org/html/2607.17266#bib.bib22)\], Chain\-of\-Thought \(CoT\)\[[36](https://arxiv.org/html/2607.17266#bib.bib23)\], and Self\-Consistency \(SC\)\[[35](https://arxiv.org/html/2607.17266#bib.bib24)\]\. For KG\-enhanced LLM methods, we compare them against representative retrieval\-based and agent\-based methods, including Think\-on\-Graph \(ToG\)\[[26](https://arxiv.org/html/2607.17266#bib.bib25)\], MindMap\[[37](https://arxiv.org/html/2607.17266#bib.bib28)\], ODA\[[27](https://arxiv.org/html/2607.17266#bib.bib29)\], Paths\-over\-Graph \(PoG\)\[[30](https://arxiv.org/html/2607.17266#bib.bib26)\]and KARPA\[[10](https://arxiv.org/html/2607.17266#bib.bib27)\]\. The details of the baselines are listed in the supplementary material\.

#### 5\.1\.3Implementation Details

DoG is a plug\-and\-play framework compatible with any open\-source or proprietary LLMs\. We conduct experiments using two LLMs: Qwen3\-8B111[https://huggingface\.co/Qwen/Qwen3\-8B](https://huggingface.co/Qwen/Qwen3-8B)\[[40](https://arxiv.org/html/2607.17266#bib.bib15)\], and GPT\-4o\-mini\[[14](https://arxiv.org/html/2607.17266#bib.bib16)\]\. Qwen3\-8B is deployed locally using the vLLM library, while GPT\-4o\-mini is accessed via the OpenAI API\. For the generation configuration, we set the temperature to 0\.5 and the maximum token length to 1024 for all agents\. In the subgraph extraction phase, we employ all\-MiniLM\-L6\-v2111[https://huggingface\.co/sentence\-transformers/all\-MiniLM\-L6\-v2](https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2)as the pre\-trained language model to compute semantic relevance\. All experiments are performed on two NVIDIA GeForce RTX 4090 GPUs\.

Regarding the hyperparameters of DoG, we set the trade\-off factorα=1\\alpha=1, the expansion widthW=3W=3, and the maximum distance thresholdDm​a​x=3D\_\{max\}=3\. In the MAD phase, we define the candidate set ofKKasΘ=\{1,3,5\}\\Theta=\\\{1,3,5\\\}and the maximum debate roundrm​a​x=3r\_\{max\}=3\. We use Accuracy \(%\) as the evaluation metric\.

### 5\.2Main Results \(RQ1\)

Table 2:Accuracy \(%\) comparison of DoG and DoG\-E with different baselines on four QA datasets\. The best results are highlighted inbold\.As Table[2](https://arxiv.org/html/2607.17266#S5.T2)indicates that DoG consistently achieves state\-of\-the\-art performance across all datasets and backbone models\. Specifically, DoG with Qwen3\-8B and GPT\-4o\-mini exhibit competitive performances on MedQA, outperforming the second\-best by 10\.3% and 7\.2%, respectively\. While the LLM reasoning methods, such as CoT and SC, exhibit promising performances, they are still limited by the lack of external knowledge sources\. Existing KG\-enhanced methods frequently underperform compared to the LLM only method\. This is because they are generally unable to identify and filter noise and errors in UKGs, amplifying LLM hallucinations instead\.

Existing KG\-enhanced LLM methods typically ignore the confidence labels in UKGs\. For a fair play, we introduceDoG\-E, a variant that sets the confidence scores of all triples in UKGs to1\.01\.0\. As shown in Table[2](https://arxiv.org/html/2607.17266#S5.T2), DoG\-E maintains strong performance across different datasets and backbone models\. While it experiences a slight performance drop compared to the standard DoG, it still outperforms most baseline methods\. This demonstrates that DoG does not heavily depend on the confidence labels within UKGs\.

### 5\.3Ablation Studies \(RQ2\)

We conduct ablation studies to analyze the effectiveness of the subgraph extraction module and the MAD mechanism\. We compare DoG with three types of variants: 1\)w/o MAD and w/ UKG, where we remove the MAD mechanism and use an LLM to generate answers directly based on the retrieved UKG triples, settingK=1,3,5K=1,3,5respectively; 2\)w/ MAD and w/o UKG, where the Proponent Agent and the Challenger Agent engage in debates without external knowledge; 3\)w/ MAD and w/o Info Asymmetry, where both debaters have access to the retrieved subgraph\. We employ GPT\-4o\-mini as the backbone LLM\.

As shown in Table[3](https://arxiv.org/html/2607.17266#S5.T3), the full DoG framework consistently achieves the highest accuracy across all four datasets\. Removing the MAD mechanism results in a substantial performance drop regardless of whether K is set to11,33, or55, indicating its importance in filtering noise and errors within UKGs\. Furthermore, relying solely on the MAD mechanism without external knowledge sources leads to a consistent performance decline across all benchmarks\. Although the MAD mechanism alone can stimulate the internal reasoning capabilities of the LLM, the absence of external evidence restricts its capacity to fully resolve knowledge gaps\. The information\-asymmetric setting in MAD is also proved to be crucial, which prevents agents from over\-relying on retrieved knowledge\.

Table 3:Ablation studies of DoG\.
### 5\.4Effectiveness Analysis \(RQ3\)

In this section, we investigate whether DoG can perform adaptive reasoning, i\.e\., whether it can dynamically select the evidence scope and the number of debate rounds according to each question\. We compare DoG with variants with fixedKK, in which the Decision\-Making Agent can decide whether to continue or terminate the debate, without expanding the subgraph\. We employ GPT\-4o\-mini as the backbone LLM\.

Table 4:Comparison of DoG and variants with a fixedKK\.As shown in Table[4](https://arxiv.org/html/2607.17266#S5.T4), the full DoG framework with dynamic subgraph expansion consistently outperforms the variants with a fixedKK\. This demonstrates that adaptively adjusting the parameterKKeffectively navigates the trade\-off between knowledge utility and evidence reliability\.

![Refer to caption](https://arxiv.org/html/2607.17266v1/x3.png)
![Refer to caption](https://arxiv.org/html/2607.17266v1/x4.png)

Figure 3:Distribution ofKKand debate round of DoG\.To further validates the adaptive reasoning of DoG, we also analyze the distribution ofKKand debate round when it terminates, as shown in Fig\.[3](https://arxiv.org/html/2607.17266#S5.F3)\. For general commonsense tasks, the Decision\-Making Agent mainly selects not to expand the subgraph, indicating that the most reliable and semantically relevant knowledge are often sufficient for answering the question\. Conversely, in the specialized medical domain of MedQA, the distribution shifts toward largerKK, reflecting the necessity for broader knowledge retrieval when handling complex domain\-specific questions\.

Moreover, the debate round distribution reveals that the majority of questions across all datasets require the maximum three rounds of debate\. This indicates that the agents consistently engage in deep adversarial reasoning to resolve information asymmetries before converging on a final reliable answer\.

### 5\.5Hyperparameter Analysis \(RQ4\)

We first analyze the impact of the trade\-off factorα\\alphain the path scoring function \(Eq\. \([5](https://arxiv.org/html/2607.17266#S3.E5)\)\)\. As shown in Fig\.[4\(a\)](https://arxiv.org/html/2607.17266#S5.F4.sf1), the performance of DoG exhibits a consistent inverted\-U trend across all datasets, peaking uniformly atα=1\.0\\alpha=1\.0\. Deviating from this optimal value leads to a noticeable degradation in performance across all datasets, indicating that a preferred reasoning path should be both reliable and semantically relevant\.

![Refer to caption](https://arxiv.org/html/2607.17266v1/x5.png)\(a\)Analysis of trade\-off factorα\\alpha\.
![Refer to caption](https://arxiv.org/html/2607.17266v1/x6.png)\(b\)Analysis of expansion widthWW\.

Figure 4:Hyperparameter analysis of DoG on Qwen3\-8B\.We also investigate the impact of the expansion widthWW\. As shown in Fig\.[4\(b\)](https://arxiv.org/html/2607.17266#S5.F4.sf2), the performance of DoG reaches its peak across all datasets whenWWis set to33\. WhenWWis too small, the restrictive expansion limits the diversity of the retrieved knowledge, potentially omitting critical reasoning paths and leading to suboptimal performance due to an information deficit\. Conversely, asWWincreases beyond33, we observe a general decline and fluctuation in accuracy\. This degradation suggests that an excessively large expansion width incorporates irrelevant or low\-confidence entities, thereby introducing noise into the subgraph that ultimately misleads the LLM during the MAD phase\.

### 5\.6Efficiency Analysis \(RQ5\)

DoG is a plug\-and\-play framework that can be seamlessly applied to various LLMs without any additional training cost\. For LLM calls, DoG requires at least44LLM calls \(only one debate round\) and at most3×rm​a​x\+13\\times r\_\{max\}\+1LLM calls during the MAD phase\.

To show the efficiency of DoG, we compare the average runtime, number of LLM calls, and token usage per question with retrieval\-based \(MindMap\) and agent\-based methods \(ToG\) on OBQA\. We employ GPT\-4o\-mini as the backbone LLM\.

Table 5:Efficiency comparison of DoG with different baselines on OBQA\.As shown in Table[5](https://arxiv.org/html/2607.17266#S5.T5), DoG are most efficient in terms of runtime\. As a multi\-turn framework, DoG requires more LLM calls and token usage than the retrieval\-based MindMap\. However, it demonstrates a significant efficiency advantage over the agent\-based ToG method, due to the adaptive termination mechanism in the MAD phase\.

## 6Limitations & Future Work

In this section, we discuss the limitations and future directions of DoG\.

- •Absence of Dedicated Benchmarks for the UKGQA Task\.The QA datasets utilized in our experiments are not highly relevant to the corresponding UKGs, which leads to limited performance gains for DoG on these datasets\. In the future, we intend to develop benchmarks tailored for the UKGQA task to further validate our method\.
- •Moderate Computational Overhead\.Although DoG outperforms some existing agent\-based methods in terms of efficiency, it still requires multiple calls of LLM in the MAD phase, which introduces moderate computational overhead\. In the future, we will explore agent pruning or confidence\-based early termination mechanism to better balance performance and efficiency\.

## 7Conclusion

In this paper, we presentDoG, a new framework that enables adaptive collaboration between LLMs and UKGs for reliable reasoning\. We developed a heuristic search algorithm tailored for UKGs to extract question\-relevant subgraphs, thereby effectively reducing noise and errors in the retrieved knowledge\. Additionally, we introduced a Multi\-Agent Debate \(MAD\) mechanism that generates robust answers via adaptive adversarial debates\. This approach fully exploits the information within UKGs while preserving the reliability of the retrieved evidence\. Extensive experiments on four benchmark QA datasets demonstrate that DoG achieves state\-of\-the\-art performance, surpassing both existing LLM reasoning methods and KG\-based baselines\.

\{credits\}

#### 7\.0\.1Acknowledgements

This work is supported by the NSFC \(Grant No\. 62376058, 52378009, 62276063\), ZhiShan Young Scholar Program of Southeast University, the Southeast University Interdisciplinary Research Program for Young Scholars, and the Big Data Computing Center of Southeast University\.

#### 7\.0\.2\\discintname

The authors have no competing interests to declare that are relevant to the content of this article\.

## References

- \[1\]K\. Bollacker, C\. Evans, P\. Paritosh, T\. Sturge, and J\. Taylor\(2008\)Freebase: a collaboratively created graph database for structuring human knowledge\.InProceedings of the 2008 ACM SIGMOD international conference on management of data,pp\. 1247–1250\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p1.1)\.
- \[2\]T\. Brown, B\. Mann, N\. Ryder, M\. Subbiah, J\. D\. Kaplan, P\. Dhariwal, A\. Neelakantan, P\. Shyam, G\. Sastry, A\. Askell,et al\.\(2020\)Language models are few\-shot learners\.Advances in neural information processing systems33,pp\. 1877–1901\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2),[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.5.5.1)\.
- \[3\]A\. Carlson, J\. Betteridge, B\. Kisiel, B\. Settles, E\. Hruschka, and T\. Mitchell\(2010\)Toward an architecture for never\-ending language learning\.InProceedings of the AAAI conference on artificial intelligence,Vol\.24,pp\. 1306–1313\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p4.2),[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p1.1)\.
- \[4\]H\. Chen\(2024\)Large Knowledge Model: Perspectives and Challenges\.Data Intelligence6\(3\),pp\. 587–620\.Cited by:[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p1.1)\.
- \[5\]X\. Chen, M\. Chen, W\. Shi, Y\. Sun, and C\. Zaniolo\(2019\)Embedding Uncertain Knowledge Graphs\.InProc\. of AAAI,Vol\.33,pp\. 3363–3370\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[6\]Y\. Chen, T\. Wu, Y\. Liu, Y\. Wang, and G\. Qi\(2024\)Uncertain Knowledge Graph Completion with Rule Mining\.InProc\. of WISA,pp\. 100–112\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[7\]Y\. Chen, H\. Li, G\. Qi, T\. Wu, and T\. Wang\(2022\)Outlining and Filling: Hierarchical Query Graph Generation for Answering Complex Questions Over Knowledge Graphs\.IEEE Transactions on Knowledge and Data Engineering35\(8\),pp\. 8343–8357\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p1.1)\.
- \[8\]Z\. Chen, M\. Yeh, and T\. Kuo\(2021\)PASSLEAF: A Pool\-bAsed Semi\-Supervised LEArning Framework for Uncertain Knowledge Graph Embedding\.InProc\. of AAAI,Vol\.35,pp\. 4019–4026\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[9\]Y\. Du, S\. Li, A\. Torralba, J\. B\. Tenenbaum, and I\. Mordatch\(2023\)Improving factuality and reasoning in language models through multiagent debate\.InForty\-first International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p6.1),[§4\.2](https://arxiv.org/html/2607.17266#S4.SS2.p1.1)\.
- \[10\]S\. Fang, K\. Ma, T\. Zheng, X\. Du, N\. Lu, G\. Zhang, and Q\. Tang\(2025\)KARPA: a training\-free method of adapting knowledge graph as references for large language model’s reasoning path aggregation\.InFindings of the Association for Computational Linguistics: ACL 2025,pp\. 24724–24746\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p3.1),[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.13.13.1)\.
- \[11\]Q\. Guo, F\. Zhuang, C\. Qin, H\. Zhu, X\. Xie, H\. Xiong, and Q\. He\(2020\)A Survey on Knowledge Graph\-based Recommender Systems\.IEEE Transactions on Knowledge and Data Engineering34\(8\),pp\. 3549–3568\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p1.1)\.
- \[12\]A\. Hogan, E\. Blomqvist, M\. Cochez, C\. d’Amato, G\. D\. Melo, C\. Gutierrez, S\. Kirrane, J\. E\. L\. Gayo, R\. Navigli, S\. Neumaier,et al\.\(2021\)Knowledge graphs\.ACM Computing Surveys54\(4\),pp\. 1–37\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2)\.
- \[13\]W\. Hu, W\. Zhang, Y\. Jiang, C\. J\. Zhang, X\. Wei, and L\. Qing\(2025\)Removal of hallucination on hallucination: debate\-Augmented RAG\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 15839–15853\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p6.1),[§4\.2](https://arxiv.org/html/2607.17266#S4.SS2.p1.1),[§4\.2](https://arxiv.org/html/2607.17266#S4.SS2.p2.5)\.
- \[14\]A\. Hurst, A\. Lerer, A\. P\. Goucher, A\. Perelman, A\. Ramesh, A\. Clark, A\. Ostrow, A\. Welihinda, A\. Hayes, A\. Radford,et al\.\(2024\)GPT\-4o system card\.arXiv preprint arXiv:2410\.21276\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2),[§5\.1\.3](https://arxiv.org/html/2607.17266#S5.SS1.SSS3.p1.1)\.
- \[15\]Z\. Ji, N\. Lee, R\. Frieske, T\. Yu, D\. Su, Y\. Xu, E\. Ishii, Y\. J\. Bang, A\. Madotto, and P\. Fung\(2023\)Survey of hallucination in natural language generation\.ACM Computing Surveys55\(12\),pp\. 1–38\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2)\.
- \[16\]L\. Luo, Y\. Li, G\. Haffari, and S\. Pan\(2024\)Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning\.InProceedings of the International Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2),[§1](https://arxiv.org/html/2607.17266#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p2.1)\.
- \[17\]L\. Luo, Z\. Zhao, G\. Haffari, Y\. Li, C\. Gong, and S\. Pan\(2025\)Graph\-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models\.InForty\-second International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p2.1)\.
- \[18\]C\. Ma, Y\. Chen, T\. Wu, A\. Khan, and H\. Wang\(2025\)Large language models meet knowledge graphs for question answering: synthesis and opportunities\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 24578–24597\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2)\.
- \[19\]C\. Mavromatis and G\. Karypis\(2025\)GNN\-RAG: Graph Neural Retrieval for Efficient Large Language Model Reasoning on Knowledge Graphs\.InFindings of the Association for Computational Linguistics: ACL 2025,pp\. 16682–16699\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p2.1),[§1](https://arxiv.org/html/2607.17266#S1.p3.1),[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p2.1)\.
- \[20\]T\. Mihaylov, P\. Clark, T\. Khot, and A\. Sabharwal\(2018\)Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering\.InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,pp\. 2381–2391\.Cited by:[§5\.1\.1](https://arxiv.org/html/2607.17266#S5.SS1.SSS1.p1.1)\.
- \[21\]S\. Pan, L\. Luo, Y\. Wang, C\. Chen, J\. Wang, and X\. Wu\(2024\)Unifying large language models and knowledge graphs: a roadmap\.IEEE Transactions on Knowledge and Data Engineering36\(7\),pp\. 3580–3599\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2),[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p1.1)\.
- \[22\]N\. Reimers and I\. Gurevych\(2019\)Sentence\-BERT: Sentence Embeddings using Siamese BERT\-Network\.InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing \(EMNLP\-IJCNLP\),pp\. 3982\.Cited by:[§3](https://arxiv.org/html/2607.17266#S3.p4.1)\.
- \[23\]H\. Sha, F\. Gong, B\. Liu, R\. Liu, H\. Wang, and T\. Wu\(2025\)Leveraging retrieval\-augmented large language models for dietary recommendations with traditional chinese medicine’s medicine food homology: algorithm development and validation\.JMIR Medical Informatics13\(1\),pp\. e75279\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[24\]R\. Speer, J\. Chin, and C\. Havasi\(2017\)ConceptNet 5\.5: An Open Multilingual Graph of General Knowledge\.InProceedings of the AAAI conference on artificial intelligence,Vol\.31\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p4.2),[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p1.1),[§5\.1\.1](https://arxiv.org/html/2607.17266#S5.SS1.SSS1.p1.1)\.
- \[25\]E\. A\. Stathopoulos, A\. Vassiliades, S\. Diplaris, S\. Vrochidis, and I\. Kompatsiaris\(2024\)Applied logic and semantics on indoor and urban adaptive design through knowledge graphs, reasoning and explainable argumentation\.The Knowledge Engineering Review39,pp\. e4\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p1.1)\.
- \[26\]J\. Sun, C\. Xu, L\. Tang, S\. Wang, C\. Lin, Y\. Gong, L\. Ni, H\. Shum, and J\. Guo\(2023\)Think\-on\-graph: deep and responsible reasoning of large language model on knowledge graph\.InThe Twelfth International Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2),[§1](https://arxiv.org/html/2607.17266#S1.p2.1),[§1](https://arxiv.org/html/2607.17266#S1.p3.1),[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p3.1),[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.9.9.1)\.
- \[27\]L\. Sun, Z\. Tao, Y\. Li, and H\. Arakawa\(2024\)ODA: observation\-driven agent for integrating LLMs and knowledge graphs\.InFindings of the Association for Computational Linguistics: ACL 2024,pp\. 7417–7431\.Cited by:[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.10.10.1)\.
- \[28\]A\. Talmor, J\. Herzig, N\. Lourie, and J\. Berant\(2019\)CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge\.InProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 \(Long and Short Papers\),pp\. 4149–4158\.Cited by:[§5\.1\.1](https://arxiv.org/html/2607.17266#S5.SS1.SSS1.p1.1)\.
- \[29\]A\. Talmor, O\. Yoran, R\. L\. Bras, C\. Bhagavatula, Y\. Goldberg, Y\. Choi, and J\. Berant\(2022\)CommonsenseQA 2\.0: Exposing the Limits of AI through Gamification\.arXiv preprint arXiv:2201\.05320\.Cited by:[§5\.1\.1](https://arxiv.org/html/2607.17266#S5.SS1.SSS1.p1.1)\.
- \[30\]X\. Tan, X\. Wang, Q\. Liu, X\. Xu, X\. Yuan, and W\. Zhang\(2025\)Paths\-over\-Graph: knowledge graph empowered large language model reasoning\.InProceedings of the ACM on Web Conference 2025,pp\. 3505–3522\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p3.1),[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.12.12.1)\.
- \[31\]G\. Team, R\. Anil, S\. Borgeaud, J\. Alayrac, J\. Yu, R\. Soricut, J\. Schalkwyk, A\. M\. Dai, A\. Hauth, K\. Millican,et al\.\(2023\)Gemini: a family of highly capable multimodal models\.arXiv preprint arXiv:2312\.11805\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2)\.
- \[32\]D\. Vrandečić and M\. Krötzsch\(2014\)Wikidata: a free collaborative knowledgebase\.Communications of the ACM57\(10\),pp\. 78–85\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p1.1)\.
- \[33\]J\. Wang, T\. Wu, S\. Chen, Y\. Liu, S\. Zhu, W\. Li, J\. Xu, and G\. Qi\(2024\)UnKR: a python library for uncertain knowledge graph reasoning by representation learning\.InProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval,pp\. 2822–2826\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[34\]J\. Wang, T\. Wu, and J\. Zhang\(2022\)Incorporating Uncertainty of Entities and Relations into Few\-Shot Uncertain Knowledge Graph Embedding\.InProc\. of CCKS,pp\. 16–28\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[35\]X\. Wang, J\. Wei, D\. Schuurmans, Q\. Le, E\. Chi, S\. Narang, A\. Chowdhery, and D\. Zhou\(2022\)Self\-consistency improves chain of thought reasoning in language models\.arXiv preprint arXiv:2203\.11171\.Cited by:[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.7.7.1)\.
- \[36\]J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, F\. Xia, E\. Chi, Q\. V\. Le, D\. Zhou,et al\.\(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in neural information processing systems35,pp\. 24824–24837\.Cited by:[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.6.6.1)\.
- \[37\]Y\. Wen, Z\. Wang, and J\. Sun\(2024\)MindMap: Knowledge Graph Prompting Sparks Graph of Thoughts in Large Language Models\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 10370–10388\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.17266#S2.SS2.p2.1),[§5\.1\.2](https://arxiv.org/html/2607.17266#S5.SS1.SSS2.p1.1),[Table 2](https://arxiv.org/html/2607.17266#S5.T2.5.11.11.1)\.
- \[38\]T\. Wu, X\. Wu, J\. Li, H\. Sha, H\. Wang, Y\. Chen, Y\. Jiang, L\. Liu, Y\. Lan, and X\. Lu\(2025\)Supervised prediction of post\-stroke upper limb motor recovery with uncertain knowledge graph and large language model\.Health Information Science and Systems13\(1\),pp\. 63\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[39\]T\. Wu, S\. Zhu, J\. Wang, N\. Xu, G\. Qi, and H\. Wang\(2025\)Uncertain knowledge graph completion via semi\-supervised confidence distribution learning\.Advances in Neural Information Processing Systems38,pp\. 171548–171567\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[40\]A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv,et al\.\(2025\)Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p1.2),[§5\.1\.3](https://arxiv.org/html/2607.17266#S5.SS1.SSS3.p1.1)\.
- \[41\]S\. Yang, W\. Zhang, R\. Tang, M\. Zhang, and Z\. Huang\(2022\)Approximate inferring with confidence predicting based on uncertain knowledge graph embedding\.Information Sciences609,pp\. 679–690\.Cited by:[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.
- \[42\]D\. Zhang, Z\. Wang, Z\. Li, Y\. Yu, S\. Jia, J\. Dong, H\. Xu, X\. Wu, Y\. Zhang, T\. Zhang,et al\.\(2025\)MedKGent: A Large Language Model Agent Framework for Constructing Temporally Evolving Medical Knowledge Graph\.arXiv preprint arXiv:2508\.12393\.Cited by:[§5\.1\.1](https://arxiv.org/html/2607.17266#S5.SS1.SSS1.p1.1)\.
- \[43\]J\. Zhang, T\. Wu, and G\. Qi\(2021\)Gaussian metric learning for few\-shot uncertain knowledge graph completion\.InInternational conference on database systems for advanced applications,pp\. 256–271\.Cited by:[§1](https://arxiv.org/html/2607.17266#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.17266#S2.SS1.p2.1)\.