Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation
Authors: Shengjie Ma
Chengjin Xu
Xuhui Jiang
Muzhi Li
Huaren Qu
Cehao Yang
Jiaxin Mao
Jian Guo
Venue: ICLR 2025 Poster (2025)
Keywords: Retrieval Augmented Generation
Knowledge Driven Reasoning
Primary area: foundation or frontier models, including LLMs
TL;DR: We introduce Think-on-Graph 2.0 (ToG-2), a hybrid RAG framework that iteratively retrieves information from both unstructured and structured knowledge sources in a tight-coupling manner.

Abstract: Retrieval-augmented generation (RAG) has improved large language models (LLMs) by using knowledge retrieval to overcome knowledge deficiencies. However, current RAG methods often fall short of ensuring the depth and completeness of retrieved information, which is necessary for complex reasoning tasks. In this work, we introduce Think-on-Graph 2.0 (ToG-2), a hybrid RAG framework that iteratively retrieves information from both unstructured and structured knowledge sources in a tight-coupling manner. Specifically, ToG-2 leverages knowledge graphs (KGs) to link documents via entities, facilitating deep and knowledge-guided context retrieval. Simultaneously, it utilizes documents as entity contexts to achieve precise and efficient graph retrieval. 
ToG-2 alternates between graph retrieval and context retrieval to search for in-depth clues relevant to the question, enabling LLMs to generate answers.
We conduct a series of well-designed experiments to highlight the following advantages of ToG-2: 1) ToG-2 tightly couples the processes of context retrieval and graph retrieval, deepening context retrieval via the KG while enabling reliable graph retrieval based on contexts; 2) it achieves deep and faithful reasoning in LLMs through an iterative knowledge retrieval process of collaboration between contexts and the KG;  and 3) ToG-2 is training-free and plug-and-play compatible with various LLMs. Extensive experiments demonstrate that ToG-2 achieves overall state-of-the-art (SOTA) performance on 6 out of 7 knowledge-intensive datasets with GPT-3.5, and can elevate the performance of smaller models (e.g., LLAMA-2-13B) to the level of GPT-3.5’s direct reasoning. The source code is available on https://anonymous.4open.science/r/ToG2.

Published as a conference paper at ICLR 2025
THINK-ON-GRAPH 2.0: DEEP AND FAITHFUL LARGE LANGUAGE MODEL REASONING WITH KNOWLEDGE- GUIDED RETRIEVAL AUGMENTED GENERATION
Shengjie Ma Chengjin Xu Xuhui Jiang', Muzhi Li", Huaren Qu",
Cehao Yang', .Jixin Jiaxin Mao Jian Guo
1 IDEA Research, International Digital Economy Academy, Shenzhen, Guangdong. China
2 Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China
3 The Chinese University of Hong Kong, Sha Tin, New Territories, Hong Kong, China
4 The Hong Kong University of Science and Technology, Guangzhou, Guangdong, China
ABSTRACT
Retrieval-augmented generation (RAG) has improved large language models (LLMs) by using knowledge retrieval to overcome knowledge deficiencies. How- ever, current RAG methods often fall short of ensuring the depth and complete- ness of retrieved information, which is necessary for complex reasoning tasks. In this work, we introduce Think-on-Grapp 2.0 (ToG-2), a hybrid RAG frame- work that iteratively retrieves information from both unstructured and structured knowledge sources in a tight-coupling manner. Specifically, ToG-2 leverages knowledge graphs (KGs) to link documents via entities, facilitating deep and knowledge-guided context retrieval. Simultancously, it utilizes documents as en- tity contexts to achieve precise and efficient graph retrieval. ToG-2 alternates between graph retrieval and context retrieval to search for in-depth clues rele- vant to the question, enabling LLMs to generate answers. We conduct series well-designed experiments to highlight the following advantages of ToG-2: ToG-2 tightly couples the processes of context retrieval and graph retrieval, deepening context retrieval via the KG while enabling reliable graph retrieval based on contexts; 2) achieves deep and faithful reasoning in LLMs through an iterative knowledge retrieval process of collaboration between contexts and the KG; and 3) ToG-2 is training-fres and plug-an and--aa compatible with vari- ous LLMs. Extensive experiments demonstrate that ToG-2 achieves overall state- of-the-art (SOTA) performance on 6 out of 7 knowledge-intensinn
datasets with GPT-3.5, and can elevate the performance of smaller models (e.g., LLAMA-2- 13B) to the level of GPT-3.5's s direct reasoning. The source code is available on attps: /tt:::/gttttas com/ IDEA PinAI/ToG-2
INTRODUCTION
Retrieval- -ugmeente generation (RAG) has significantly enhanced the capabilities of large language models (LLMs) by retrieving relevant knowledge from external sources, promising solution to address the knowledge deficiencies and hallucination issues (Zhao et al. 2004). Despite this poten- tial, and researchers' attempts to incorporate various complex additional processes into RAG (Yul et al. 2023 Edge et al. 2024 Li et al. 2024c), LLMS still struggle to maintain human-like reason- ing trajectories [Kahneman] 2011) when handling complex tasks, which require continuous effort and motivation to integrate fragmented information and the structural relationships between them.
Many recent implementations of RAG mainly rely on vector retrieval of textual content within doc- uments (Ding et al.) 2024] Asai et al. 2023 Wang et al.) (023b)). Although vector embedding is effective for measuring the semantic similarity between two texts, text-based RAG struggles to cap- ture the structured relationship between texts and documents (Chen et al. 2023). Specifically, simple
Both authors contributed equally to this research.
Corresponding author

---

Published as a conference paper at ICLR 2025
Query: Where was runners broke Crag Virgin's
Boys Country record?
(o). Text-based RAG
Mybrid RAG
Relerence
Assistant: The given
Virgin
Cross Country chemstenshig
cinfartt Stree
relorencss do not prosido Josh Mathner's place of tf
2 Grilg Sleven Virgin Iben Augudd 2 16t5) is Americnn cisance nume: He vas torn. coliilit Srowe U.S
2 The H+S esbail shed stale seres niooys sports creer countyt 945))
-tewwed Suar Diy
[b]. KG based RAG
Reference
Sorr, Ican iistia sae seperpale and spaeific rnfimation perne sicie Crvig Vagiii Dlyge Piose Country iscced prosibet
X
CORTONL
Aselscant Sorry, ican not ansverthe quaetionatcall
Cripp Vigin
1584 Surmerr Ohyrpes X
Leteroniiggt Schoo
Think-on-Graph220
Asnistane: UMSA the Doys
(deg Yaggs
Bandung
von 2010 IRBA Class 36 salt champlo piopppp with onty seconde sote record held looks oecondul Cruig Vigan Anal Lakeo bom Kounas UPhaaioo Thavolore the
Figure 1: The illustration of differences among (a) text-based RAG, (b) KG-based RAG, (c) KG+Tex (Loose-coupling) Hybrid RAG, and (d) our proposed KGxTeex (Tight-coupling) RAG framework.
vector-based matching may overlook knowledge-level association between entities within different texts, e.g., Global Financial Crisis and The 2008 Recession, which are two surface names that refer to the same event; Harry Potter and Fantastic Beasts which are both written by J.K. Rowling. This limitation results in that most text-based RAG approaches are not suitable for multi-step reasoning or tracking logical links between different information fragments. As shown in Figure [a), the naive RAG, where generic retrievers search through large-scale corpora, the recall often focuses the level of superficial semantic similarity (Edge et al. 2024), but overlooks the structured relationship between Craig Virgin and Lukas Verzbicas, as well as texts containing one of them.
Knowledge Graphs (KGs) organize the structural relationships between entities from fragmented information and store knowledge in the form of triples. Some researchers have explored KG-based RAG approaches (Sun et al. 2024), which prompt LLMs by retrieving KG triples relevant to the question. Although KGs are effective for structuring high-level concepts and relationships, they inherently suffer from inner incompleteness and a lack of information beyond their ontology Li et al. (2024a|b). As shown in Figure [b), the KG is unable to provide detailed information about Lukas Verzbicas's 's competition records. Some recent works focus integrating text-based and KG-based RAG systems (Li et al., 2024c Edge et al., 2024). In this approach, information retrieved from both structured and unstructured knowledge sources is aggregated to prompt the LLM to answer questions but does not improve the retrieval results on one knowledge source through the other. As shown in Figure [c), such loose-coupling combination (KG+Teext) approaches still fall short in handling complex queries that require detailed information returned obtained through in-depth retrieval.
Considering the aforementioned challenges, we propose Think-on-Graph 2.0 (ToG-2), a tight- coupling hybrid (KGxTeex) RAG paradigm which effectively integrates unstructured knowledge from texts with structured insights from KGs, serving as a roadmap to enhance complex problem- solving. As shown in Figure [d), ToG-2 first initializes the starting point for graph search by extracting topic entities from the question. At the beginning of each retrieval round, ToG-2 explores more candidate entities by performing relation retrieval on the KG and retrieves relevant text from documents associated with these candidate entities. Following knowledge- guided context retrieval, ToG-2 prunes the candidate entities based on the results of the context retrieval, updates the set of topic entities and uses it as the starting point for the next round of retrieval. After each retrieval round, ToG-2 prompts the LLM to answer the question based on the highly relevant knowledge triples and contexts obtained during the retrieval process. If the retrieved information is insufficient to answer the question, the next round of retrieval continues for searching more in-depth clues. Such tight-coupling hybrid RAG paradigm makes L.M perform closer to human when solving complex
2

---

Published as a conference paper at ICLR 2025
problems: examining current clues and associating potential entities based on their existing knowl- edge framework, continuously digging into the topic until finding the answer.
ToG-2 achieves in-depth and reliable context retrieval through the guide of KGs and performs precise graph retrieval by treating documents node contexts, achieving a tight-coupling combination of KG and text RAG, enabling deep and comprehensive retrieval processes. (2) Faithful reasoning: ToG-2 iteratively performs a collaborative retrieval process based on KG and text, using retrieved heterogeneous knowledge as the basis for LLM reasoning and enhancing the faithfulness of LLM-generated con- tent (3) Efficiency and Effectiveness: a) ToG-2 is training-free -free and plug-ands aagg-and-ply framework that can be applied to various LLMs; b) ToG-2 can be executed between any associated KG and docu- ment database, while for purely document database, entities can be extracted from the documents first, and then graph can be constructed through relation extraction or entity co-occurrence (Edge) jtt al. (2024); c) ToG-2 achieves new SOTA performances on various complex knowledge reasoning datasets and can elevate the reasoning capabilities of smaller LLMs, e.g., Llama2-13B to level comparable to direct reasoning with powerful LLMs like GPT-3.5.
The advantage of ToG-2 can be summarized as: (1) In-depth retrieval:
2 RELATED WORKS
RAG aims to offer effective utilization of external knowledge sources with high interpretability. An important factor is the type of data retrieved. In this section, we will briefly review text-based RAG, KG-based RAG and hybrid RAG.
Text-based RAG approaches retrieve information based on the semantic similarities between ques- tions and texts (Gao et al., 2024; Qiu et al., 2024). However, these approaches have difficulties in capturing in-depth relationships between texts and the retrieved texts may contain redundant content. To address these challenges, ITER-RETGEN (Shao et al. 2023) follows an iterative strategy, merg- ing retrieval and generation in loop, alternating between "retrieval-augmente generation" and "generation-aug augmented retrieval". TTrivedi et al. (2023) combined RAG with the Chain of Thought (CoT) (Wei al. 2022a) method, alternating between CoT-ggided retrieval and retrieval-supported CoT processes, significantly improving GPT-3's performance on various Q&A tasks. While these optimizations enhance the recall of relevant texts, the whole retrieval process becomes more time- consuming and errors may accumulate over iterations, due to the lack of a reliable guide.
The structured knowledge representation of KGs is particularly beneficial to L.MSs because it intro- duces a level of interpretability and precision in the knowledge. Early approaches (Sun et al. 2020 2020) focused on embedding knowledge from KGs
Peters et al. 2019 Huang al.) 2024 Liu directly into the neural networks of LLMs. To maximize the utilization of the interpretability of
the KG, more recent studies (Tiang et al., 2024 Sun et al. 2024) have shifted towards using KGs to augment LLMs externally rather than embedding the knowledge directly into the models. KG-based RAG approaches involve translating relevant structured knowledge from KGs into textual prompts that are then fed to LLMs, however naturally suffer from the knowledge incompleteness of KGs.
The most relevant works to ToG-2 are hybrid RAG approaches that aim to integrate both KGs and un- structured data with LLM, leveraging the strengths of both to mitigate their respective weaknesses. Chain-of- -nohloof-KKoweddee (Li et al. 2024c) (CoK) is a hybrid RAG method that retrieves knowledge from Wikipedia, Wikidata and Wikitable to ground LLMs' outputs. GraphRAG (Edge et al. 2024) establishes a KG from documents and enables KG-enhanced text retrieval. HybridRAG (Sarmah) et al. 2024) retrieves information from both vector databases and KGs, achieving superior reason- ing performance compared to either text-based RAG or KG-based RAG methods alone. However, existing hybrid RAG approaches merely aggregate information retrieved from KGs and texts but do not improve the retrieval results on one knowledge source through the other. In this work, ToG-2 aims tightly couple KG-based RAG and text-based RAG methods, enabling both in-depth context retrieval and precise graph retrieval to enhance complex reasoning performances of LLMs.
METHODOLOGY
The proposed method ToG-2 draws from the ToG approach /Sun et al. (202)) in multi-hop searches within KGs, starting from key entities identified in the query and exploring outward based on
3

---

Published as a conference paper at ICLR 2025
Query: Where was one of the runners born who almost broke Craig Virii'ss
Boys Cross Country record?
Tople prune
Reasoning
YES Output
Illincss
Craig Virgin
Cues NO
Comfects
Confecta
Relation Discovery
Coues
This
Relation Prune
Iteration
Sandburg High School
Evan Jager
Lebanon High School
1984 Summer Olymaics
Enilyy Discovery
Next Iteration
Entit--guieed Context Retrieval
Context- beadd based Ently Prune
Einis Iocated
C s
sductted 4
BB
pardbarn 1:5 L
Iteration #1 mepromoon
Next
Lukas Verzbicas
IHSA
Reasoning
YES Oulput
or max depth
Figure 2: An example illustrating the workflow of ToG-2.
tities and relationships with a prompt-driven inferential process. ToG-2 combines the logical chain extensions based on triples with unstructured contextual knowledge of relevant entities by iteratively performing Knowledge-guiders context retrieval and context-enhance graph retrieval, thus more ef- fectively integrating and utilizing heterogeneous external knowledge.
Specifically, ToG-2 begins by extracting entities from the given question as initial topic entities. It then performs an iterative process of graph retrieval, context retrieval and LLM reasoning. At the start of each iteration, ToG-2 selectively explores entities neighboring the current topic entities on the KG, using the newly encountered entities to refine the retrieval scope, thereby enhancing both efficiency and accuracy. Next, ToG-2 ranks and selects entities based on the query and the contextual knowledge retrieved from relevant documents, reducing ambiguity and ensuring accurate exploration for the next step. After, the LLM utilizes heterogeneous knowledge, including triple paths and entity contexts, to either answer the question or proceed with further rounds of retrieval if the information gathered is insufficient. this section, we will explain each step in detail.
3.1 INITIALIZTION
Given a question g. ToG-2 first identifies the entities present in q and links them entities in the KG. This step can be done by different entity linking (EL) methods, such as LLMs or specialized EL tools Then, ToG-2 performs a Topic Prune (TP) step select suitable entities as starting points of exploring in a KG, which prompts the LLM to evaluate q and appearing entities, selecting topic {e1, e ,, } and N is determined by I.IM.
entities 8D
Topic
Prior to the lst-round graph retrieval, ToG-2 uses dense retrieval models (DRMs, including dual- tower and single-tower models) extract the top-k chunks from the documents associated with the initial topic entities Etopie The LLM then evaluates whether this information is sufficient to answer the question, drawing on its own knowledge. If it concludes that the available information is adequate, no further steps will be required.
3.2 HYBRID KNOWLEDGE EXPLORATION
The following will illustrate how ToG-2 iteratively harmonizes and tightly couples heterogeneous knowledge. The iterative process will be explained in two main parts, Context-enhanced Graph Search and Knowledge-guided Context Retrieval. Formally, in the i-th iteration, the topic and their preceding triple paths are pi-1
entities are denoted Elopic {ei, 6 P ...., ter of exploration width (the max number of retained topic entities in each iteration, and p is
PJ-1), P. Pj = (p), P). ........2 1/ 1) where E [1, WJ. W is hyperparame-
We use entity linking API provided by Azure Al for wttpociinnttss///eeemmmmccooooo en en-us/azure/a http////orr//a--ervcceeess www.evieee//aaaaaaaeeeeeeee anguage- servi ce eete/etiiii recommencation

---

Published as a conference paper at ICLR 2025
single triple .r)" e)) containing rj- the relation between ej- and oj in the KG, which could be either direction. Note that i indicates the initialization phase and the pe is empty.
3.2.1 KNOWLEDGE- GRAPH SEARCH
By leveraging the rich structural connectivity of knowledge the KG, the graph search aims to explore and establish high-level concepts and relationships between the question and target infor- mation that seemingly distant from each other in semantic space.
Relation Discovery: At the beginning of the i-th iteration, through the function
Edge(e)) = {(r) hmm) | h E (True, False]),
we can find the relations for all topic entities. Edge() is function that searches for relationships of entities. indicates whether the direction of that relation r).m is pointing to the topic entity ej-
Relation Prune (RP): From the collected relation set ( We prompt the LLM to select and score the relations that are likely find entities containing helpful context information for solving We design two prompting manners:
PROMPT R 9, Edge(e))),
PROMPT RP embl @lopies q. Edge W )-
(3)
The detailed prompt is shown in Appendix E Table 15 16 and 17 The relations with low scores will be pruned. Equation 2 involves multiple calls to the LLM for entity pruning on each topic entity individually, while Equation processes the relation selection for all topic entities in a single simplifies the task for the LLM, but it is less efficient. Equation 3 reduces the number of API calls, thereby enhancing inference speed, and allowing the LLM to consider the interconnections between multiple reasoning paths simultaneously, facilitating selections from broader perspective. However, when all topic entities recall an excessive number of relations, this may challenge the capacity of a weak LLM to effectively handle long texts. The selected relations for all topic entities the i-th iteration are denoted as R' {r).m } (j E WJ). In the case of Figure 2 the topic entity ef Crag Virgin and its relation r = place of birth is pruned since it may lead to a location that unlikely to be relevant to a runner's 's performance.
operation. Equation 2
Entity Discovery: Given a topic entity eğ in Elopic and its corresponding selected relations r).m in R², function
Tail(e), (r).., hm)) = c).m)
(4)
identifies the connected entities {c),m } of the topic entities ej through the relation (r) (r)... hm).. In
the case of Figure 2 Crag Sandburg High Shool, Evan Jager the connected entities of Crag Sandburg High Shool after entity discovery.
context-based entity prune step will be executed later to select top-W entities from all the connected entities as new topic entities gi+l completing the entire graph retrieval step.
topice thereby
3.2.2 EXOWLEDGE-GUIDEE CONTEXT RETRIEVAL
In this step, ToG-2 digs granular information following high-level knowledge guidance provided by the KG. Once we get all candidate entities by Function 4 we collect the documents relevant to each candidate entity Cj forming a context pool of candidate entities for the current iteration. In the case of Figure 2 the context pool of the first iteration contains documents relevant to candidate entities including Crag Sandburg High School, Evan Jager, Lebanon High School, 1984 Summer Olympics and so on.
Entity-guides Context Retrieval: In order to find useful information within the document con- text of candidate entities, we apply DRMs to calculate the relevance scores of paragraphs. Rather than directly calculating relevance scores between context and the thestion- neglecting the relationship between each context and its corresponding entity-wa translate the current triple Pe (e), r..m of candidate entity c).m into brief sentence and append it to the context pend- ing score calculation. Formally, we formulate the relevance score of 2-th chunk of c) as:
m, DRM(g, [triple sentence Pel.m) chunks,
(5)
5

---

Published as a conference paper at ICLR 2025
Then the top- K scored chunks Ctz will be chosen references for the reasoning phase.
The selection of candidate entities is based on the rank scores of their context chunks. The ranking score of candidate entity c)mm is calculated as the exponentially decayed weighted sum the scores of its chunks that rank in top-K K (K denoted the Context Number for reasoning), which is formally formulated as:
Context-based Entity Prune:
K
score(c),m)
sk . wk 1l (the k--th ranked chunk is from cj,)), Σ
(6)
where Wi = ---ak 8%. is the score of the k-th ranked chunk, is the indicator function that equals the k-th chunk belongs e),m. and K and a are hyperparameters. Candidate entities with top-W scores will be selected as the topic entities gi+1 in the next iteration. Candidate Entities with low ttoric relevance scores like Evan Jager in the Figure are pruned.
3.3 REASONING WITH HYBRID KNOWLEDGE
At the end of the i-th iteration, we prompt LLM with all knowledge found, including Clues f-1 triple paths, top-K entities and the corresponding context chunks, to evaluate the given knowledge is sufficient to answer the question, where Clues' is the retrieval feedback from the previous iteration, aiming to maintain useful knowledge in historical context. If L.M judges the provided knowledge is enough to answer the question, it directly outputs the answer. Otherwise, we prompt LLM to output helpful clues Clues' summarized from existing knowledge and then reconstruct an optimized query based on accurate information until the maximum depth D is reached. The process formulated as:
Ans., Clues',
if the knowledge is sufficient.
PROMPT,s(q, Pt, Ctx', Clues'
otherwise.
The details of the prompts are shown in Appendix
F Table 18 and 19
4 EXPERIMENTS
4.1 DATASETS AND METRICS
We evaluated our method on different knowledge-intensive reasoning benchmark datasets, including two multi-hop KBQA datasets WebQSP (Yth et al. 2016) and QALDI0-on (Usbeck et al.) 2023).
multi-hop complex document QA dataset AdvHotpotQA (Ye & Durrett 2022) which is a challeng-
ing subset of HotpoiQA (Yang et al. 2018), a slot filling dataset Zero-Shot RE(Petroni et al. 2021
and two fact verification dataset FEVER (Torne et al. 2018) and Creak (Onoe et al.j (021). The
evaluation metric for FEVER and Creak is Accuracy (Acc.), while the metric for other datasets is Exact Match (EM). Recall and Fl scores are not used since knowledge sources are not limited to document databases. Following previous work (Li al. 2024c), full Wikipedia and Wikidata used as unstructured and structured knowledge sources for all of these datasets. Compared to the distractor setting, this full Wiki setting makes the retrieval process more challenging and can better evaluate the effectiveness of various methods on knowledge reasoning tasks.
Since Wikipedia is commonly used for training LLMs, a Nomain-specinn QA dataset that has not been exposed during the pre-training processes of the LLMs is needed for better evaluating different LLM-based approaches. We collect thousands of 2023-year Chinese financial statements as new corpus, and further build KG and manually design 97 multi-hop questions based on the corpus. In this paper, we refer to this dataset as ToG-FinQA. Companies and other organizations are extracted entities in the KG, with 7 types of relationships defined (subsidiary company, main business, supplier, sibling company, bulk transaction, subsidiary, and customer). Financial statements are used entity contexts. Please refer Appendix C for detailed information of ToG-FinQA.
4.2 BASELINES
We compare ToG-2 with both widely-used baselines and state-of-the ff--hhe-rt art methods to provide a more comprehensive overview: LLL--oyy methods without external knowledge, including Direct Rea-

---

Published as a conference paper at ICLR 2025
Datasets
Baseline Type
Method
WehQSP (EM)
AdvHoipaiQA (EM)
QALD-I0- 10-en
FEVER
Creak
Sero-Shot RE
(EM)
(Acc.)
(Acc.)
(EM)
Direct
65.9%
23.1%
12.0%
51.8%
89.7%
27. 7%
LLM-only
CaT
59.9%
30.8%
42.9%
37.8%
90.1%
28.8%
CoT-SC
61.1%
34.4%
45.3%
59.9%!
(56.2%1)
90.8%
45.4%
Text-hased RAG
Vanilla
67.9%
23.7%
42.4%
38.8%
89.7%
29.5%
KG-based RAG
ToG
76.2%
26.3%
50.2%
32.7%
93.8%
88.0%
Hybrid RAG
CoK
77.6%
35.4%
(34.1%
47.1%
63.5%
(58.5%)
90.4%
73.5%
Proposed
ToG-2
81.1% %
42.9%
54.1% %
63.1"
(59.7% 9)
93.5%
91.0%
Table I: Performance comparison different methods with GPT-3.5-turbo across various datasets. Note that the CoK model has 6-shot and 3-shot settings. We present the best performance of CoK under different shot settings for each dataset. For AdvHotpolQA and FEVER, we use the results reported in the original paper of CoK, where i represents the 3-shot setting and represents the 6-shot setting. Bold numbers represent the highest result under parallel settings.
Model
ToG-2
Vanilla RAG
CoT
ToG
GraphRAG
ToG-FinQA
34.0%
14.0%
6.2%
Table 2: ToG-FinQA Results
soning, Chain-of-Thought (Wei et al., 2022b), Beff-Consistency (Wang et al. 2023a): 2) Vanilla RAG, indicating the text-based RAG method that directly retrieves from entity documents and an- swers the question; 3) KG-based RAG method:
Think-on-Graph (Sun et al. 2024 a KG-based RAG method that searches useful KG triples for reasoning: Chain-of- -onnn-oe--oowedeg (Li et al. 2024c),
hybrid RAG method retrieving knowledge from Wikipedia, Wikidata and Wikitable; 5) GraphRAG (Edge et al. 2024), a hybrid RAG method that first builds KG from documents and enables KG- enhanced text retrieval. Notably, we only evaluate GraphRACE on ToG-FinQA due to its unaffordable computation cost during the indexing process on large corpus. For fair comparison, all baselines used with GPT-3.5-turbe and evaluated under an unsupervised setting.
4.3 IMPLEMENTATION DETAILS
We mainly use GPT-3.5-turbo as the backbone L.M for a fair comparison to other baselines. To evaluate the effect of backbone LLMs on ToG-2's performance, we conduct experiments with GPT- 4o, Llama3-8B and Qwen2-7B. Consistent with the ToG settings, we set the temperature parameter 0 for all generations. The width W and the maximum number of iterations (depth) is 3. During relation prune, we set threshold of 0.2 to filter relations with low relevance scores and then select the top W. For context retrieval, we utilize the BGE-embedding model without any fine-tuning. In entity prune, we maintain 10 (K 10) top-scored sentences for calculating entity scores. the reasoning stage, we employ a 2-shot demonstration for most of the datasets. Following CoK (Li et al., 2024c), employ 3-shot and 6-shot demonstration for FEVER and make the LLM exccute a self-consistency reasoning step first
4.4
MAIN RESULTS
The main results of several open-source datasets are shown in Table [ We note that ToG-2 out- performs other baselines on WebQSP, AdvHotpotQA, QALD-10-en, and Zero-Shot RE. Notably, WebQSP, AdvHotporQA and QALD-10-en are multi-hop reasoning datasets. On Fever, ToG-2 has a competitive performance to CoK since the fact statements in Fever mainly are about single-hop relations and thus do not need in-depth information retrieval. another fact verification dataset Creak, all fact statements can be verified based Wikidata. Thus, ToG-2 and ToG have similar per- formances on Creak. Meanwhile, compared to original ToG, ToG-2 achieved a substantial improve- ment AdyHotpotQA (16.6%) and also demonstrated notable enhancements (4.93% on WebQSP, 3.85% on QALD-10-en. 3% on Zero-Shot RE, and 10.4% on FEVER). This demonstrates the advantages of our XGxText RAG framework in addressing complex problems.
other datasets

---

Published as a conference paper at ICLR 2025
Llama-3-8B
Qwen2-7B
GPT-3.5-turb
GPT-4o
Direct
ToG-2
Direct
ToG-2
Direct
ToG-2
Direct
ToG-2
AdvHooiorQQ
20.8 34.7
(66.8% t) 17.9 30.8 (72.1% %
1) 23.1
42.9
(85.7% f) 47.7
53.3 (11.3% f
FEVER
35.5
52.9 (49.0% f) 38.6
53.1 1 (38.1 %
1)
51.8
63.1 (21.8% f) 66.2
70.1 (5.9% f)
ToG-FinQA
8.2
0
10.3
0
34.0
0
36.1
Table 3: Performance comparison of direct reasoning and ToG-2 with different backbone models.
Most LLMs have been pre-trained on Wikipedia which is also the unstructured knowledge source of datasets like AdvHotpoIQA and Fever, and thus LLM-only methods can work on these datasets. To further evaluate the effectiveness of different methods on domain -omain-specific reasoning scenarios where it is essential to retrieve information from specific knowledge sources since LLMs themselves usually lack relevant knowledge, we conduct an extra evaluation in our established ToG-FinQA dataset. Table 2 shows comparison of ToG-2 with CoT and the original RAG based on GPT- 3.5-turbo. ToG-2 demonstrates a notable advantage over other baselines in this task. Both vanilla RAG and CoT struggled, indicating that traditional RAG and CoT methods may not enable LLMs to solve unseen complex problems. GraphRAG only answered correctly 6.2%, suggesting that while loosely coupled hybrid RAG retrieve information from both knowledge graphs and documents, fails to perform multi-hop context retrieval and reasoning with the help of the KG. Compared to GraphRAG, ToG shows improved effectiveness, albeit limited, indicating that the knowledge framework provided by triples can better support multi-hop reasoning.
4.5 ABLATION STUDY
4.5.1
ABLATION OF LLM BACKBONES
To what extent do LLMs with varying capabilities benefit from the knowledge enhancement of ToG-2? To answer this research question, we analyzed the enhancement of ToG-2 under different LLM backbone selections through experiments on AdvHotpotQA and FEVER. The experimental results are shown in Table 3
We observe that ToG-2 can elevate the reasoning capability of weaker LLMs, e.g., Llama-3-8B, Qwen2-7B to the level of direct reasoning by more powerful L.LMs, e.g., GPT-3.5-turbo, which supports our intuition that ToG-2 helps LLMS with knowledge and comprehension bottlenecks. On the other hand, powerful LLMs, c.g., GPT-3.5-turbo and GPT-4o, can still benefit from ToG-2 to improve their own performances complex knowledge reasoning tasks, indicating that ToG-2 may achieve even higher performance with stronger LLMs. On AdvHotporQA and FEVER which use Wikipedia as knowledge sources, the most powerful LLMs among all backbone LLMs, GPT-4o experiences the least improvement since GPT-4o has a better memory for knowledge related to Wikipedia than other backbone LLMs, making its direct reasoning performance on these datasets already desirable. It is evident that LLMs with stronger reasoning ability like GPT-4o benefit more significantly from ToG-2 on ToG-FinQA when the relevant knowledge has not been exposed during pre-training and a knowledge retrieval process is necessary. In such scenarios, ToG-2 enables more in-depth knowledge retrieval and more reliable reasoning with stronger L.Mss
4.5.2 CHOICES OF ENTITY- PRUNING TOOLS
At the step of context-based entity prune, the selection of new topic entities should be based on the relevance of the corresponding contexts, which then reversely guides the next round of graph path exploration. In this experiment, we evaluate different methods for relevance scoring on a sampled set from AdvHotpotQA. In addition to the three DRM models BGedss--G---mbeennng BGF-rrranker, and Minilm-we we also tested the sparse retrieval model BM25 and generative ranking with I.LMss
What kind of tools are most suitable for tight coupling graph-based knowledge and document- based knowledge? First, Figure 3 presents various choices of pruning tools with a fixed number K = 10 of entity contexts. The BGE-Reranker demonstrates the best performance, followed by Minilm, which serves as lighter alternative to the former. Generative- tools show comparable results, while BM25, classic and efficient retrieval method, exhibits performance close to that of the advanced models. Considering the long runtime of LLMs and the lower accuracy of embedding models, employing reranker for entity pruning strikes the best
and embedding- based
8

---

Published as a conference paper at ICLR 2025
80
DBGE-Embarding 0Minim-L-8-2 BLLM
BBGE-Roranker @ BM25
LLM BBGE-Reranker
Score
38
36
34
EM Score
40
38
33
34
30
30
20
10
0
Entity Prune Tool
Context Length
10
(a) Performance different prune tools.
(b) Effect Context Number
Figure Comparative analysis of Entity-Pruning Tools.
balance of both. The observation also suggests that classic retrieval techniques like BM25 alongside more sophisticated models can still yield good results resource-efficcent manner.
Then we conduct another experiment in Figure 3p to find the best setting of context numbers K. Our findings indicate that BGE-Reranked tends to yield better results with longer context inputs, whereas LLM shows diminished effectiveness. Nevertheless, the overall performance of the pruning tool using BGE-Reranker slightly exceeds that of the LLM. We attribute this outcome reasonably more contexts allow for greater tolerance toward irrelevant documents, and DRMs can handle a large number of candidates. While LLM possesses strong discriminative capabilities and offers greater flexibility, its performance is significantly constrained by the input length. Thus, opt for entity pruning based on the DRM approach, considering its advantages in cost-effectiveness and enhanced generalization.
fact that
4.5.3 WIDTH & DEPTH SETTINGS
36.7
40.9
42.5
broader exploration scope necessarily better? To answer this research question, analyze the im- pacts maximum width W and depth settings. Figure 4 illustrates the performance of ToG-2 on AdvHoipotQA across varying maximum inference width and depth configurations. The results demon- strate a gradual improvement in model performance the width increases from 2; however, the marginal gains diminish beyond a width of 3. This trend is at- tributed the inference width, which corresponds to the number of top-W relevant entities retained at each step; greater width allows for more leniency in topic pruning. With respect to depth, the model's ss performance plateaus beyond a depth of These observations suggest that larger search scope is not always better; it should be adjusted according to the difficulty of the task.
dosth
36.4
38.6
39.6
Figure 4: Width and depth settings analysis.
4.6 RUNTIME ANALYSIS
Answer Type
Percentage
Direct Answer
16.13%
Equa- tion 3 in Relation Prune for efficiency. Under this setting, the reasoning process of ToG-2 needs most 2D (D 1D-1)++ 11 calls to the LLM. When using Equation relation pruning, ToG-2 needs most WD + + LLM calls and can achieve slightly higher performances on several datasets as shown Appendix B33 Table 7 In Table 7 we also report the results of an additional ablation study. By con- trast, ToG needs at most 2WD + D + LLM calls. We compare the specific runtime between ToG and ToG-2 different datasets in Appendix B.4 Table g Even though ToG-2 integrates additional knowl- edge through entity context, ToG-2 still manages
In the above-mentioned experiments,
Triple-enhanced Answer
9.68%
Doc-enhanced Answer
41.94%
Both-enhanced Answer
32.26%
Table 4: Sources of answer clue origins: Di- rect Answer refers to questions that can be answered directly without additional infor- mation. Triple-enhanced Answer refers to answers that use triple links as clues. Doc- enhanced Answer refers answers where entity context information provides clues for generating the answer. Both-enhanced An- swer refers to answers where both triple links and entity context information contribute.

---

Published as a conference paper at ICLR 2025
reduce the entity pruning phase to 68.7% of ToG's runtime average. This is because ToG relies on LLM- entity pruning, while ToG-2 leverages DRMs, which can handle more candidates and compute relevance scores faster.
4.7 MANUAL. ANALYSIS
To what extent does ToG-2 leverage the triple links and the contextual information? To gain deeper understanding of ToG-2's behavior, we randomly select 50 AdvHotpoIQA reasoning results from ToG-2 and perform a manual analysis about how triple link reasoning and the contextual in- formation of entities within the links contribute to the correct answers, respectively. As shown in Table 4 Doc-enhanced Answers have the highest proportion, at approximately 42%, while Triple- enhanced Answers are the least common, indicating that textual context is often the most important source of information for complex QA tasks. Triple links alone lack detailed context, making it difficult to provide deeper insights, and their role is more of a macro-level guide. Even without relying on the text information within the triples, key clues can still be navigated effectively. The proportion of Both-enhanced Answer shows significant utilization, suggesting that the combination of triple-link reasoning and entity context documents is highly effective pattern. Direct Answers account for 16% of the responses, showing that for complex questions, the LLM can directly answer relatively few questions and still relies heavily advanced information-enhancee pipelines.
We demonstrate two cases in AdvHotpotQA to show examples of Both-enhanced Answer and Doc- enhanced Answer. In the Both-enhanced case, the method not only derives that "the group of Black Indians associated with the Seminole people is Black Seminoles" " from the triple links information, but also leverages the context within the document of Black Seminoles to determine their settlement location. In the Doc-enhanced case, the approach utilizes triple links as guidance, ultimately idde- tifying the target information from the document context of Billy Corgan, a member of the band in the album. More cases in AdvHotpotQA and ToG-FinQA are shown in Appendix D
Creetfalen''s artwork done by photographer of which natiorsiity?
Where did the descendants the proup of black Indians associsted with the Seminole people sellle?
Qusstion
Dusstion
Crestfallen
codoomer
The Smashing Pumpkins
Semiinole
aubcless of Black Seminoles
Billy Corgan
member of
Black Indians in the United States
subolasr
Links
Triple Links
In 1895, Billy Cergan started dating Ukrainian photographer Yelena
Black Seminole Regions with significant populations United
Yemchuk, who later contr contributed several Smasning Pumpkins videos and album art...
States: Okdahoma, Florida, Texes; Mexico: Coahulla...
Billy Gorgan
United
S (Yes), Dased the given knowledge triplets. the group of black Seminola paopla Based on the retrieved sentences, Black Seminole settled in several to the question (Oklahoma. Florida.
G (Yes). Based on the retrieved sentences, the Ukrainian photographer who contrituted to several Smashing Pumpkins videos and album inclucing the artwork for '"Grestfallenn"" I" is Yalana Yemchuk. Therefore, the answer is (Ukrainian).
associated
Saminola.
regions. Therefore, Texas, and Coahulla Mexico)
Figure 5: Illustrations of Both-enhanced Answer (left side) and Doc-enhanced Answer (right side).
We also compare the outputs of ToG-2 and CoT regarding the selected questions. As shown in Appendix B.I Table 5 ToG-2 alleviates the hallucination issues of L.MSs compared CoT with in-depth knowledge retrieval, and tends to refuse answers more often when faced with insufficient knowledge. We also observe significant number of false negatives in the responses of ToG-2 when using EM as an evaluation metric, suggesting there is still untapped potential for our method.
CONCLUSION
Existing RAG systems based on KGs or texts struggle to ensure in-depth knowledge retrieval when dealing with complex knowledge reasoning tasks. In this work, we introduce a hybrid RAG paradigm, X RAG, which tightly couples KG-based and text-based RAG, and propose the Think-on-Graph 2.0 (ToG-2) algorithmic framework that enables reliable graph retrieval by using textual contexts, achieves knowledge-guice guided context retrieval via the KG, and iteratively perform cooperative retrieval process to obtain in-depth knowledge for achieving deep and faithful LLM rea- soning. Experimental results demonstrate that ToG-2 can significantly improve LLMs of different sizes and outperform existing various LLM reasoning methods and RAG methods without additional training costs.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannanch Hajishirzi. Self-rag: Learning to retrieve, generate, and critique through self-reflection, 2023. URL httptttss//aii...ottt
abs/23100 11511
Jiawei Chen, Hongyu Lin, Xianpei Han, and Le Sun. Benchmarking large language models in retrieval-augmented generation, 2023. URL http:::/t/a.....crtttt
2.0p./2.9..... 01431
Yujuan Ding, Wenqi Fan, Liangbo Ning. Shijie Wang. Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. A survey rag meets llms: Towards retrieval-augmentedd large language models. arXiv preprint wrXiv:2405.06211 2024.
Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson. From local to global: A graph rag approach to query-focused summariza- tion, 2024. URL httts:://tatiiiiieee
org/ abs/ 2404. 101.0 16130
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. Retrieval- generation for large language models: A survey, 2024. URL/attps://arxttt http:///wxxxv.....aaao.. http://ab//22211999993
Rikui Huang, Wei Wei, Xiaoye Qu, Wenfeng Xie, Xianling Mao, and Dangyang Chen. Joint multi- facts reasoning network for complex temporal question answering over knowledge graph. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 10331-10335. IEEE, 2024.
Zhouyu Jiang, Ling Zhong, Mengshu Sun, Jun Xu, Rui Sun, Hui Cai, Shuhan Luo, and Zhiqiang Zhang. Efficient knowledge infusion via kg-llm alignment, 2024. URL https://arxix:
org/ abs/ 2406 03746
Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, 2011.
Muzhi Li, Minda Hu, Irwin King, and Ho-fung Leung. The integration of semantic and struc- tural knowledge in knowledge graph entity typing. In Kevin Duh, Helena Gomez, and Steven Bethard (eds.), Proceedings of the 2024 Conference of the North American Chapter of the As- sociation for Computational Linguistics: Human Language Technologies (Volume 1: Long Pa- pers), pp. 6625 6638, Mexico City, Mexico, June 2024a. Association for Computational Linguis- tics. doi: 10. waw.:224.aa---oooo..66. URL //acl antholoohhhe httppss//aclaaatooooog..ooo org//024. naacl long. 3697
Muzhi Li, Cehao Yang, Chengjin Xu, Xuhui Jiang, Yiyan Qi, Jian Guo, Ho fung Leung, and Ir- win King. Retrieval, reasoning, re-ranking: A context-enriched framework for knowledge graph completion, 2024b. /ttttts://aattttt/
abs 08165
Xingxuan Li. Ruochen Zhao, Yew Ken Chia, Bosheng Ding, Shafiq Joty, Soujanya Poria, and Li- dong Bing.
Grounding large language models via dynamic knowledge adapting over heterogencoous sources. In International Conference on Learning Representationss 2024c. MKLL/tttts:///peeeevvie htt.:eeweeettoooorrddddgogggggaa
Daizong Liu, Xiaoye Qu, Jianfeng Dong, and Pan Zhou. Reasoning step-by-step: Temporal sentence localization in videos via deep rectification-moullatoo network. In Proceedings of the 28th International Conference Computational Linguistics, pp. 1841-1851, 2020.
Yasumasa Onoe, Michael J. Q Zhang, Eunsol Choi, and Greg Durrett. Creak: A dataset for com- monsense reasoning over entity knowledge, 2021. URL
01 6553
Matthew E Peters, Mark Neumann, Robert I. Logan IV, Roy Schwartz, Vidur Joshi, Sameer Singh, and Noah A Smith. Knowledge enhanced contextual word representations. arXiv preprint arXiv:1909.04164 2019.
Fabio Petroni, Aleksandra Piktus, Angela Fan, Patrick Lewis, Majid Yazdani, Nicola De Cao, James Thome, Yacine Jemite,, Vladimir Karpukhin, Jean Maillard, Vassilis Plachouras, Tim Rocktäschel, and Sebastian Riedel. Kilt: a benchmark for knowledge intensive language tasks, 2021. URL URIphttss: pattps://arxiv. http:///wwwww..oo/aaa////aaooa// /2009. 02252

---

Published as a conference paper at ICLR 2025
Zexuan Qiu, Zijing Ou, Bin Wu, Jingjing Li, Aiwei Liu, and Irwin King. Entropy-base -bssed decoding for retrieval- auggeettd large language models, 2024.
Bhaskarjit Sarmah, Benika Hall, Rohan Rao, Sunil Patel, Stefano Pasquali, and Dhagash Mehta. Hybridrag: Integrating knowledge graphs and vector retrieval augmented generation for efficient information extraction. arXiv preprint arXiv:2408. 04948, 2024.
Zhihong Shao, Yeyun Gong, Yelong Shen, Minlie Huang. Nan Duan, and Weizhu Chen, Enhancing retrieval-augmeened large language models with iterative eetrieval-generaate synergy. 2023. URL
https://are otg/ als///a///// 2305. 15294
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heuung-Yungg Shum, and Jian Guo. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph, 2024. URL cattps://arxiv// wttpvv...rg/a///3333/
0 07697
Yawei Sun, Lingling Zhang, Gong Cheng, and Yuzhong Qu. SPARQA: skeleton-based seman- tic parsing for complex questions over knowledge bases. CoRR, abs/2003. 2020. URL
https::/aaxiz wttpaa/wwww.rr//////.....33 13956
James Thore, Andreas Vlachos, Christos Christodoullpoulls,, and Arpit Mittal. Fever: a large-scale dataset for fact extraction and verification. arXiv preprint 1803:01800.053500 2018.
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Interleaving re-
trieval with chain torggio for knowledge-intensivee multi-step questions, 2023, URL
/tttps:/aaxivv.org/// 2ttp://ww...rr//aa//22.......0
Ricardo Usbeck, Xi Yan, Aleksandr Perevalov, Longquan Jiang, Julius Schulz, Angelie Kraft, Cedric Möller, Junbo Huang. Jan Reineke, Axel-Cyrille Ngonga Ngomo, et al. Qald-10-tt 10th chal- lenge on question answering over linked data. Semantic Web, (Preprint):1-15. 2023.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou, Self-consistency improves chain of thought reasoning in language models, 2023a. h http:: :/atts::/azaee http///aavvvvvv. org/abs/ 2203. 11171
Zhiruo Wang, Jun Araki, Zhengbao Jiang, Md Rizwan Parvez, and Graham Neubig. Learning to filter context for retrieval-augment
generation, 2023b. URL httts:://axxi..orrge
0811.08377
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed H. Chi, Quoe Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. CoRR, abs/2201. 11903,
2022a. URL http:://////aax...oooo//o///////
11903
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi. Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in 2022b.
neural information processing systems, 35:24824-24833
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint 10XXvv1800900000
2018.
Xi Ye and Greg Durrett. The unreliability of explanations in few-shot prompting for textual reason- ing. In Advances in Neural Information Processing Systems, 2022.
Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 201-206, 2016.
Wenhao Yu, Hongming Zhang, Xiaoman Pan, Kaixin Ma, Hongwei Wang, and Dong Yu. Chain- oftno Enhancing robustness in retrieval-augmented language models, 2023. URL :
// //aaxiiv.oo www.iv.orr/aas//311..1
09210
Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, and Bin Cui. Retrieval-aud augmentee generation for ai- ai-generated content: A survey. arXiv preprint 200. 2024.
12

---

Prompt LLM evaluates sufficiency of knowledge to answer PROMPT, P Ctxx', Clues--1) if Knowledge is sufficient then Output Ans; return end Published as a conference paper at ICLR 2025
A PSEUDOCODE
Algorithm 1: The ToG-2 Algorithm
Input: Question y
Output: Answer Ans
// Initialization.
Clues = Null;
Topic entities Goopic f Perform NER then Topic Prune;
Ctx + Retrieve top-k chunks from documents associated with Eoppc using DRM;
Prompt LLM evaluates the sufficiency of knowledge to answer q:
PROMPT (q, Ctx Clues")
Information sufficient then
Output Ans; return end else end
Outputs Clues";
for i to D do // Context Enhanced Graph Retrieval for e) E Elopic do Find relations Edge(e)) = {(r) j.m 1m)) }}:
|
end
Use LLM to select and score relations: R$ <- PROMPT RP. caw...mmmeeee.e (Etopei 4s for
j.o. E R2 do
Find connected entities cj.m Tail(e), (r).ms hm));
Collect documents of candidate entities c),,. and split into chunks;
end
Knowledge-guidee Context Retrieval for chunk?, j,m c.m do
Compute relevance score 8 J.m.= DRM(q, [tripllc.eentenccePee chankly..al
end
Ctz² Select top- K scored chunks; Compute scores for candidate entities based chunk scores: (core ()))
gi+1 + Select top-W entities;
topic
// Reasoning with Hybrid Knowledge
else
Outputs Clues":
end
end
Output failure or best effort answer;
13

---

Published as a conference paper at ICLR 2025
Category
Type
Definition
ToG-2 w/o SC
GPT3.5-SC
Correct
The answer correct.
100%
88.3%
Correct
False positive
Incorrectly judged as correct.
0%
11.7%
False negative
Correct answer but judged as incorrect due to ambiguous questions or labels.
38.7%
18.1%
Incorrect
Hallucination
Incorrect answer due to hallu- cination.
9.7%
72.7%
No Info.
Relevant information missing found in knowledge sources.
48.3%
Misunderstood
LLM misunderstood the question and gave an irrele- vant response.
3.2%
9.1%
Table Human study Correct and Incorrect cases from randomly sampled HotpotQA questions.
B ADDITIONAL EXPERIMENT ANALYSIS
B.1 MANUAL ANALYSIS (CONTINUR)
The manual analysis results presented in Table reveal several additional observations:
1) Even though ToG-2 consistently outperforms the baselines across various datasets, it still faces significant bottlenecks when comes to information retrieval. These issues are largely due in- complete knowledge sources and the limitations of retrieval models. For instance, Wikidata often contains inaccuracics, contradictions, or gaps, and many Wiki entities are missing key details on their Wikipedia pages. On the retrieval side, different types of questions require different informa- tion, and a one-size-fits- retrieval model can struggle without specific training. Therefore, ToG-2 comprehensive knowledge graphs
be further optimized through plug-ins that incorporate and more advanced retrieval models, which is convenient.
2) When handling less straightforward derstand the intent. For example, in the question "What number president nominated Annie Capulo become member of the Nuclear Regulatory Commission?" the correct answer is 45th but the model might answer Donald Trump (which, while true, isn't exactly what the question was asking).
complex questions, LLMs can sometimes misun-
3) EM (Exact Match), while often used assess model performance on QA problems, is not ideal to handle the complexity of such generating. EM struggles to match aliases correctly, and also can't handle answers with different levels of detail. For example, if the question "Where was A bor??" without specifying the level of detail, both New York and Manhattan should be accepted as correct answers. Researchers have attempted to use LLMS as evaluators, considering factors such efficiency, cost, and the potential bias in LLM evaluations, we opted to use EM for rough evaluation. While the role of the evaluator is indeed significant challenge in the era large language models, this work does not delve into that aspect.
B.2 SUPPLEMENTARY ANALYSIS FOR THE MAIN RESULTS
As we observed a performance discrepancy between ToG and ToG-2 on the Creak dataset in Table we aim to provide a more detailed analysis on this particular dataset. This analysis will offer insights into the underlying factors contributing the observed discrepancy. Furthermore, we will showcase and discuss the implications both methods in the context of the Creak dataset. Specifically, manually analyzed the reasoning process for 50 examples. providess an overview of the distribution of answer types for ToG-2, following the format of Table 4 in our paper.
these findings for understanding the strengths and limitations of
14

---

Published as a conference paper at ICLR 2025
Answer Type
ToG-2
Triple-cnhanee Answer
42%
Doc-enhanced Answer
24%
Both-enhanced Answer
34%
Table 6: Distribution of answer types for ToG-2 the Creak dataset.
Due to the relatively simple nature the questions in the Creak dataset, results can often be inferred directly using triples. As result, ToG already performs well this dataset, and the richer entity document information utilized by ToG-2 does not provide significant additional benefits. As shown in the table, ToG-2 produces higher proportion of Triple-enhanced Answers Creak compared to more complex datasets like HotpotQA.
We conducted detailed study of the behavior of ToG and ToG-2, highlighting three represen- tative cases that elucidate the primary reasons for the observed performance differences. These bad cases reveal distinct patterns in how each model approaches reasoning.
Case 1: One can watch Bugs Bunny on the television.
ToG-2 Response: (Yes), Bugs Bunny can be watched on television. The references mention the his- tory and success of the Bugs Bunny series, indicating its presence on various channels and streaming services over the years. The knowledge triplets also confirm Bugs Bunny's 's association with iconic works like Looney Tunes and notable creators like Tex Avery and Mel Blanc.
ToG Response: (Yes), the claim is (True). Based on the knowledge triplets, Bugs Bunny is beloved character from iconic works such as Looney Tunes, which was created by Warner Bros, and has been featured extensively in television broadcasts since its creation.
Label: True
The model failed to produce the expected output format (True). The LLM did not strictly follow the instructions, which is low-probability event but accounts for a large proportion of eтrors.
Error Reason:
Case 2: Quark served the man drink Star Trek: Deep Spuce Nine.
ToG-2 Response: [No], the claim is (False). The claim that "Quark served the man drink on Star Trek: Deep Space Nine" cannot be evaluated based on the given information. The references provide information about the character Quark is Ferengi bartender on Deep Space Nine, but there no specific mention of him serving drink to man.
ToG Response: (Yes), the claim is [True). The knowledge triplets confirm Quark's association with Star Trek: Deep Space Nine and his role as a bartender, serving drinks patrons in the series.
Label: True
The model's failure stems from two main issues: overcautiousness and semantic ambiguity. Despite identifying the golden sentence, "Quark was the bartender on Deep Space Nine," ToG-2's excessive caution prevented it from making implicit inferences without explicit evidence. Additionally, the phrase "the man" " implies a specific individual without sufficient context, leading to misinterpretation.
Error Reason:
Case 3: Parkinson's 's disease causes various hallucinations in people.
ToG-2 Response: (Yes), the claim (True). The retrieved references mention that Parkinson's disease psychosis (PDP) is present in around 20 percent of cases and comprises hallucinations, illu- sions, and delusions. This confirms that Parkinson's 's disease can indeed cause various hallucinations in people.
15

---

Published as a conference paper at ICLR 2025
ToG Response: {No), the claim is {False). The retrieved references do not provide any evidence linking Parkinson's disease to causing various hallucinations in people. As no supporting informa- tion was found, it is concluded that this condition does not lead to hallucinations.
Label: False
Error Reason: Although ToG-2's response appears reasonable from medical perspective, the golden label is "False." " This misalignment suggests that ToG-2's detailed document analysis can sometimes lead to conclusions that diverge from the dataset's annotations, particularly when the dataset lacks nuanced inferences.
Conclusion: ToG performs well in scenarios that demand rapid, triplet-based reasoning, while ToG- 2 demonstrates its strength in cases requiring detailed contextual reasoning. However, ToG-2's overcautious behavior and occasional divergence from the ground truth reveal its tendency to prevent hallucinations the cost of misalignment with less explicit labels. Additionally, the quality issues within some questions in the Creak dataset also limit the upper bound of model performance.
B.3 SUPPLEMENTARY ABLATION STUDIES
To evaluate the contribution of each component in ToG-2, we conducted comprehensive ablation experiments across WebQSP, AdvootpoQQA, QALD-10-en and FEVER. To conserve API costs, we sampled small subset of the FEVER dataset for ablation experiments. Compared to the per- formance on the other three datasets, on WebQSP, the effectiveness of Topic Prune (TP) is more pronounced, possibly due to the higher relative proportion of general entities in WebQSP questions, which tends introduce more unnecessary noise. Additionally, the retrieval feedback (Clue) also brought relatively consistent improvements across each dataset, indicating that adaptive query opti- mization help the LLM better understand the tasks.
Datasets
Model
WebQSP (EM)
AdvHotpoQQA
QALD-10-en
FEVER
(EM)
(EM)
(Acc.)
Direct
65.9%
23.1%
42.0%
52.1%
78.7%
40.9%
51.1%
56.3%
ToG-2 ToG-2/TP/Ctte
78.0%
40.2%
49.9%
56.0%
ToG-2/rP
77.0%
41.9%
52.9%
56.5%
ToG-2
81.1%
42.8%
54.1%
58.5%
Table 7: Influence of each module in ToG-2 on the final performance. / denote without. Clue: the retrieval feedback. TP: topic prune. /RC: replace relation prune 3 with Eq
B.4 RUNTIME ANALYSIS RESULTS
Does ToG-2 improve graph exploring efficiency compared to ToG? Therefore, first statis- tically compared the runtime of ToG and ToG-2 across different stages under the same settings. Specifically, we analyze the average number of iterations in answering each discrete question, along with the average runtime for each iteration.
The results Table show substantial improvement ToG-2's relation pruning time, reducing to just 45% of ToG's This gain comes from the relation pruning combination strategy, which cuts down the number of L.LM calls from W times to time each iteration. Even though ToG-2 integrates additional knowledge through entity context, ToG-2 still manages reduce the entity pruning phase to 68.7% of ToG's runtime on average across both datasets. This is because ToG relies on LLM- based entity pruning, while ToG-2 leverages DRMs, which can handle more candidates and compute relevance scores faster.
To better illustrate the efficiency of our method compared to the baselines, analyze the average total runtime and API call counts for each method on HotpotQA. The results are summarized in bello. ToG: For each question, ToG requires up to 2W D D 1 API calls, where W is the
16

---

Published as a conference paper at ICLR 2025
Dataset
Method
Avg. time per RP (s)
Avg. time per (8)
Avg. time per Reasoning (S)
Avg. Depth
ToG-2
6.4
5.9
2.21
FEVER
ToG
14.2
6.5
5.5
1.94
ToG-2
6.1
4.3
5.7
2.17
AdvHotpotQA
ToG
13.8
6.3
5,4
1.71
Table 8: Running time comparison of ToG-2 and ToG on FEVER and AdvHotpotQA datasets.
Method
Avg Total Time (s)
API Calls
ToG-2
27.3
5.4
NaiveRAG
10.2
1
ToG
69.3
16.3
CoK
30.1
11
Table 9: Comparison of API Call Counts and Runtime Across Methods.
maximum width (number of knowledge triplets explored in parallel) and D is the maximum iteration depth. This structure enables comprehensive multi-hop reasoning and knowledge exploration, but results in relatively high number of API calls per question.
CoK: To ensure fairness comparison, we restricted the knowledge domain to factual data from WikiData, Wikipedia, and DPR. We also adopted the update rat sationales... at once setting from the original implementation. CoK has a fixed API call count of 11 per question: domain selection call, chain-of chain-of-thought sub-question generation call, rationale editing calls, and I final answer generation call.
knowledge retrieval calls,
To simulate retrieval corpus, iterations. NaiveRAG uses a two-stage retrieval system that combines BM25 with BGE-Reranker, resulting in the fewest API calls among the compared methods.
NaiveRAG:
all entity documents encountered during ToG-2
ToG-2: For each question, ToG-2 requires up to 2D + (D - 1) + API calls, where:
2D: Calls for Relation Pruning (RP) and Reasoning during each iteration.
D 1: Query re-writing between iterations.
* 1: Topic Prune (TP).
Compared to baselines, ToG-2 achieves a good balance between cost-efficiency and performance. reduces the total API calls and runtime while maintaining robust reasoning capabilities.
B.5 IMPACT OF THRESHOLD SETTING IN RELATION PRUNE
We conducted threshold experiments in Relation Prune (RP) to analyze the effect of different thresh- old scores. Specifically, we compared the effects of three thresholds (0.2, 0.5, and 0.8) on the final results in the HotpotQA dataset. The results are summarized in Table 10
Threshold
Results (%)
Avg. Retained Score
0.2
42.9
0.65
0.5
43.2
0,68
0.8
40.0
0.92
Table 10: Effects of different thresholds on the final results in HotpotQA. The Avg. retained score represents the average score of all relations that pass through the threshold filtering.
When the threshold is set between 0.2 and 0.5, its impact the final result is minimal. However, when the threshold increases to 0.8, the results weaken significantly. We attribute this to two main reasons:
17

---

Published as a conference paper at ICLR 2025
1. During the relation pruning stage, the relations passing the threshold are further filtered by selecting the top relations based on the width W. Therefore, even the threshold set very low, relations with extremely low scores will ultimately fail to be included in the Top W. This explains why the Avg. retained score is very close when the threshold is 0.2 or 0.5. However, setting a reasonable threshold is still necessary prevent the inclusion of entirely irrelevant relations in cases where very few relations are found and are scored low (e.g,, low 0.1).
2. Relations with moderate relevance scores (c.g., 0.3-0.7) potentially lead to useful in- formation. A lower threshold allows for more tolerance for such potential. When the threshold is raised to 0.8, it overly amplifies the impact of the LLM's judgment during relation pruning on the entire process, leading to the loss of potentially valuable relations.
B.6 IMPACT OF SC SETTING
60
F iillstrates the impact of varying self-consistency
thresholds on the performance of ToG-2 on AdvHot- poIQA. As threshold increases, we observe a cor- responding performance improvement. This can be at- tributed stricter consistency demands placed on the LLM's multiple responses the threshold rises, which more effectively identifies and filters out complex ques- tions that challenging for the LLM to resolve di- rectly. These difficult cases are then handed over to ToG- enabling more accurate responses. Furthermore, while fewer questions are answered during the SC phase, they are answered with higher degree of certainty.
50
40.9
41.6
42.9
Score
39.6
40
30
20
10
0.5
0.6
0.7
0.8
SC threshold
Figure Impact of SC setting
B.7 IMPACT OF GRAPH COMPLETENESS
To investigate the impact of graph quality on the reasoning performance of ToG-2, we designed an experiment to quantify the specific effect Knowledge Graph (KG) quality on the model's conducted experiments
performance. Specifically, questions (100 in total) using simulated incomplete KGs. The incompleteness was introduced by randomly discarding relations and entities discovered during the Relation Discovery (Equation and Entity Discovery (Equation 4 stages. Specifically, we tested scenarios where 30%, 50%, and retained, while the rest were randomly removed. This systematic evaluation provided insights into the model's adaptability to varying levels of KG completeness. The results shown in Table
subset of randomly sampled HotpotQA
80% of the discovered entities and relations
KG Completeness (%)
Exploration Setting
EM (%)
100
Default
43
80
Default
41
50
Default
35
30
Default
23
30
Adjusted
29
Table 11: Impact of KG Completeness on ToG-2.0 Performance with Default (W 3, and Adjusted (W 8, D = 2) Exploration Strategies
At 80% completeness, the model demonstrated robust performance with minimal impact compared to the fully complete KG, indicating its strength at high completeness levels. With 50% complete- ness, moderate performance degradation was observed, suggesting that ToG-2.0 remains resilient to moderate KG incompleteness. However, 30% completeness, performance dropped significantly due to sparse connections in the graph, highlighting the challenges posed by severe KG incomplete- ness.
To mitigate this, adjustments were made to the exploration strategy: By increasing the exploration width (W) to 8 and reducing the exploration depth (D) to 2, the model was able broaden its
18

---

Published as a conference paper at ICLR 2025
search scope, compensating for the missing information. This adjustment led notable recovery in performance, bringing closer to an acceptable level despite the significant KG incompleteness. These findings emphasize the model's adaptability and provide insights into potential strategies for handling incomplete KGs.
B.8 SIGNIFICANCE TEST
Statistical significance is key factor in evaluating model performance. To assess this, we conducted pairwise t-tests on select datasets where we had access to both ToG-2 and baseline results. However, many of the baseline results reported Table were directly cited from their respective original papers other related works. As result, do not have access to the detailed outputs of these baseline models for individual questions, preventing us from performing significance tests on those baselines at this time.
For the WebQSP, Zero-Shot-RE, QALD-10-aa -0-een,,,, and Creak datasets, we computed pairwise t-tests comparing ToG-2 with CoK and ToG as in Table 12
(ToG-2 vs.) Method WebQSP
Zero-Shot-RE
QALD-10-en
Creak
CoK
p < 0.05
p p< 0.01
p < 0.05
p < 0.05
ToG
p < 0.05
p < 0.05
< 0.05
p 0.9
Table 12: ToG-2 significantly outperforms CoK and ToG on most datasets (p < 0.05), except on Creak where the difference with ToG is not significant (p >> 0.9), indicating similar performance this dataset.
C TOG-FINQA DATASET OVERVIEW
The dataset comprises three main components: (1) document corpus, (2) knowledge graph, and (3) QA pairs. Table 13 provides a summary of the key statistics for each component.
Component
Statistic
Value
Document Corpus
Total documents
17,013
Average document length
40,469
Knowledge Graph
Total entities
671,806
Total edges
565,994
Average edges
0.84
Maximum edges
3,982
Median edges
1.0
QA Pairs
Total QA pairs
97
Topics
Market Analysis, Competitor Analysis, Transactions, Customer Analysis, Supplier Analysis
Table 13: Key Statistics of the Chinese Financial QA Dataset
We automatically sample some candidate triple paths based on predefined meta- meta-path rules, such as supplier-customer-uupplee meta-path that might explore competitive relationships), while pre- serving the entity context involved along the path. These triple paths, along with their contextual information, then manually inspected and filtered to select candidates that can logically and factually form multi-hop questions with objective answers.
19

---

Published as a conference paper at ICLR 2025
D OTHER CASES
We present two cases of ToG-FinQA in Figure On the left side is Both-endanced case with the topic of Supplier Analysis. From the triple relationships of predicate relation customers and subject relation suppliers, two suppliers of ZEC were identified, and information related to recycling was found in their documents. On the right side is also a Both-endanced case, candidate entities were identified through paths of the same customer or supplier. and then the context in the documents of the candidate entities was used to confirm that Nanjing Jujong is the target entity.
(8 RB?
[Whch suppliers Zhenhua E-Chem Inc. are commilted
[Wh are the main compelllors of Jinfatech (with the same customers suppliers)?]
recycling??
Question
Question
((EEC))
supzler
& (Huuyyy
2 Bidā(Jinfatech)
client
3E (iet(Yanfeng
Cobalt)
Plastic Omnium)
suppleer
# (EMM)
(CChina Jushi)
suppler
2 / 8
(Naniing Julong)
Triple Links
(The company's main buainess the recycling and processing of used power batteries, electronic waste, scrapped vehicles,
Ejj0 f $7
plastics, strategic resources such as nickel, cobalt, lithium, and tungsten.]
[The main business is the research, production, and
Contexts of Nanjing Julong
Contexts of Nanjing Julang
I TE Al * BT tn H & f #0
...दह itt # RR [ Ix [..at the same time, company is also developing a circular recycling business...
[The company mainly engaged research, production, and sales of new polymer materials and their composites.
Consexts of Jinfateeh
Consexts of Jinlatech
knowledge graph triples SE (iii(iiaatttc sentences there is overiapping business in the market.
(Yes).
(Yes). Based on the knowledge graph triples and retrieved references suppliers ZEC committed
(Nanjing Juloon) has the same customers and suppliers
according
recycling are (l Cobalt) and # (GEM))
Answer
Therefore the answer { RE (Nanjing Julong))
Answer
Figure 7: ToG-FinQA Cases
Figure 8 shows Triple-enhanced case in HotpotQA, where the common style of the two movies is identified by solely utilizing the triple links.
What type movie
Wishing Stairs and Voice
Question
Wishing Stairs
Voice
Film
gancR
Links
(Yes). Bused given knowledge triplets, both Wishing Stairs and Voice are horror films.
Figure 8: Triple-enhanced Case
20

---

Published as a conference paper at ICLR 2025
E PROMPTS
Topic Prune Prompt
Given a question and a group of related topic entities derived from the Wikipedia knowledge graph, the task is to select which of these entities suitable as starting points for reasoning the Wiki knowledge graph to find information and clues that are useful for answering the question. Note that your output should be strictly JSON formatted: {id: entity).
Here are examples showing how to analyze and output a ISON formatted answer:
Example
Question: What major city is the Faith Lutheran Middle School and High School located in?
Topic entities: {
"Q111": "Faith Lutheran Middle School",
"Q39722": "Faith Lutheran High School"
Analysis:
All entities are directly related to the core of the cesstioonfindiin the possible information about
Faith Lutheran and its location.
Output:
["Q111": "Faith Lutheran Middle School", "Q39722": "Faith Lutheran High School")
Example 2:
Question: How many Turkish verbs ending with "us" with their lemma?
Topic entities: { "Q24905": "verb"
Analysis:
Q24905 "verb" focuses verbs, which action words in language. The task involves not just identifying verbs but specifically Turkish verbs that end with the suffix "us," Therefore, the entity "verb" is too broad and does not point to specific Turkish verb. Thus there is no suitable topic entity as starting point for reasoning. Output: 0
Example 3:
Question: On which island is the Indonesian capital located?
Topic entities: {
"Q252": "Indonesia",
"Q23442": "island"
Analysis:
Q252 "Indonesia" represents the country of Indonesia. Considering the question is about the capital of Indonesia and which island it is located on, the entity "Indonesia" is directly related the core of the question-finding the capital of Indonesia and then identifying the island it is situated on. Therefore, this entity is highly suitable as starting point for reasoning.
Q23442 "island" represents the concept of an island. While the question does indeed relate to island, the concept of "island" itself is too broad and does not point to specific geographical location or country. From the perspective
reasoning on a knowledge graph, trying find the capital of a specific country based solely on the concept of an island is less relevant and efficient compared to starting from that country. Hence, Q252 "Indonesia" the more suitable topic entity as starting point for reasoning on the knowledge graph. It directly connects to the key information of the question and effectively guide the search for entities related to the answer within the knowledge graph.
Output:
("Q252": "Indonesia")
Table 14: Topic Prune
21

---

Published as a conference paper at ICLR 2025
Relation Prune Prompt
Please retrieve %8 relations (separated by semicolon) that contribute to the question and their contribution on a scale from 0 to 10. Question: Mcsih Pasha's unele became emperor in what year? Topic Entity: Mesih Pasha
Relations: child
2. country_off _of_ citizensshp
date birth
4. family
father
languages_spoken
7. military rank
occupation
9. place_of.ceeeeee _of_heath
10. pesl
Answer:
(family (Score: 10)): This relation is highly relevant as it can provide information about the family background of Mesih Pasha, including his uncle who became emperor.
[father (Score: 4)}: Unele father's brother, so father might provide some information as well.
3. (position held (Score: 1)}: This relation is moderately relevant as it can provide information
about any significant positions held by Mesih Pasha or his unele that could be related to becoming an emperor.
4.
Question: Van Andel Institute was founded in part by what American businessman, who was best known as co-founder of the Amway Corporation? Topic Entity: Van Andel Institute Relations:
1. affiliation
country
donations
4. educated at
employer
Answer:
1. affiliation (Score: 8): This relation is relevant because it can provide information about the individuals or organizations associated with the Van Andel Institute, including the American busi- nessman who co-founded the Amway Corporation.
donations (Score: 3): This relation is relevant because it provide information about the financial contributions made to the Van Andel Institute, which may include donations from the American businessman in question.
educated_at (Score: 3): This relation is relevant because it can provide information about the educational background of the American businessman, which may have influenced his involvement founding the Van Andel Institute.
4.
Table 15: Topic Prune Prompt
22

---

Published as a conference paper at ICLR 2025
Relation Prune CMB Prompt
# Task:
1. Carefully review the question provided.
From the list of available relations for their corresponding entity, select the %s that you believe are most likely to link to the entities that can provide the most relevant information to help answer the provided question.
For each selected relation, provide score between to 10 reflecting its usefulness answering the question, with 10 being most useful. Provide brief explanation for your choices, highlighting how each selected relation potentially contributes to answering the question.
# The input follows the below format:
Question:[The question text]
Entity 1:[The name of the entity 1]
Available Relations: [A relation list of entity to be chosen.] Entity 2:[The name of the entity 2]:
Available Relations:[A [A relation list of entity 2 to be chosen.]
...(Cnntinue in the same manner for additional entities)
# Below examples:
# Examplel:
Question: Mesih Pasha's uncle became emperor in what year?
Topic Entity: Mesih Pasha
Relations: child
2. country of citizenship date_of
4. family
5. father
sanguages-spoken, spoken, written. .rr signed
7. military rrak
Answer:
1. [family (Score: 1.0)): This relation is highly relevant as it can provide information about the
family background of Mesih Pasha, including his uncle who became emperor.
2. [father (Score: 0.4)]: Uncle is father's brother, so father might provide some information as well.
# Example2:
Question: what the attitude Joe Biden towards China?
Entity I: china
Relations:
1. alliance
International_reltiooo
political_syster _system
4. population
Entity 2: joe biden
Relations:
volitical_positiio
2. presidency
family
4. carly_life
Answer:
Entity 1:
1. {alliance (Score: 8)): This relation is highly relevant it can provide information about the
relationship between china and other parties.
2. {political system (Score: 7)}: This relation is relevant as it can provide information about the
policies that might reflect the relationship between china and other parties.
3.
Table 16: Relation Prune CMB Prompt
23

---

Published as a conference paper at ICLR 2025
Relation Prune CMB Prompt (Continue)
Entity 2:
1. [political.position position (Score: 10)}: This relation is highly relevant it can provide information
about Joe Biden's 's political position to other parties or countries.
2. (presidency (Score: 2)}: This relation is slightly relevant as it can provide information about Joe Biden's 's position, which might provide clues answer the question.
3.
# For questions involving multiple entities, you are required to analyze the relation list for each entity separately. Then select the %5 most relevant relations for each entity, based on the analysis as done in the given example. It's essential to maintain strict adherence to the line breaks and format in the provided example for clarity and consistency: Answer:
Entity I: The Name of Entity
[Relation] (Score: }) Explanation.
2. [Relation2 (Score: Y) Explanation.
Entity 2: The Name of Entity 2 [Relation] (Score: X)}: Explanation
Relation22 (Score: Y)}: Explanation
... (Continue in the same manner for additional entities)
Now, will provide you with new question with %s entities and relations. Please analyze following all the guidance above carefully.
# For questions involving multiple entities, you are required analyze the relation list for each entity separately. Then select the %s most relevant relations for each entity, based on the analysis as done in the given example. # It's essential to maintain strict adherence to the line breaks and format as seen in the provided example for clarity and consistency: Answer:
Entity I: The Name Entity
1. [Relation] (Score: X)}: Explanation. (Relation2 (Score: Y)}: Explanation.
Entity 2: The Name of Entity [Relation] (Score: X)}: Explanation
2. [Relation2 (Score: Y)}: Explanation
(Continue in the same manner for additional entities)
# Now, I will provide you with new question with %s entities and relations. Please analyze it following all the guidance above carefully.
Table 17: Relation Prune CMB Prompt (Continue)
24

---

Published as a conference paper at ICLR 2025
Reasoning Prompt (QA)
Given question, some clues, the associated retrieved knowledge triplets and related contexts, you are asked to evaluate if these resources, combined with your pre-existing knowledge, are sufficient formulate an answer ({ (es)) or (No)).
Your answer must begin with (Yes) or [No}.
If Yes),, please note that the analyzed answer entity must be enclosed in curly brackets {xxxxxx) [No), means resources are useless or provide clues that are helpful but insufficient to answer the question conclusively. Based on the given knowledge, please summarize any insights (if any) so far that may help answer the question, which must also be enclosed in curly prackets(xxxxx)
Here are some examples:
# Example 1:
Question:
The Sentinelese language is the language of people one of which islands in the Bay of Bengal ?
(Clues):
None
(Knowledge triplets):
Sentinelese language, Indigenous to, Sentinelese people
(Triplet's related context):
The Sentinelese, also known the Sentinel and the North Sentinel Islanders, indigenous people who inhabit North Sentinel Island in the Bay of Bengal in the northeastern Indian Ocean. (Knowledge triplets):
Bay Bengal, area, Andaman and Nicobar Islands (Triplet's related context):
Andaman and Nicobar Islands are an archipelagic island chain in the eastern Indian Ocean across the Bay of Bengal, they are part of India. They are within the union territory of the Andaman and Nicobar Islands
# Answer:
(Yes) The analyzed answer entity is (Andaman and Nicobar Islands].
# Example 2:
Question:
Who is the coach of the team owned by the most famous English former professional footballer?
(Clues):
The most famous English former professional footballer is David Beckham.
(Knowledge triplets):
David Beckham, co-owned, Inter Miami CF (Triplet's related context):
Inter Miami CF, founded in 2018, is professional soccer club based Miami, Florida. It competes in Major League Soccer (MLS) as part of the Eastern Conference. David Beckham made a 3 years contract with his major coach.
# Answer:
(No) The given knowledge provides helpful information that the footballer is David Beckham and David Beckham's 's ownership of Inter Miami CF, but they do not explicitly mention who the coach is. The useful information for now is {the team owned by the famous English former professional footballer David Beckham is Inter Miami CF}
Now, please carefully consider the following case:
Table 18: Reasoning Prompt (QA).
Reasoning Prompt (QA)
Given a question and some knowledge gained so far, please predict the additional evidence that needs be found answer the current question, and then provide suitable query for retrieving this potential evidence. Note that the query must be included in curly brackets [xxx].
Table 19: Query Re-form Prompt
25


Reviews:
[{"review_id": "4G9rUsf4ei", "reviewer": "Reviewer_9CdM", "summary": "This paper presents Think-on-Graph 2.0 (ToG-2), a RAG framework that integrates both unstructured text and structured knowledge graphs in a tightly coupled manner to improve retrieval quality and reasoning accuracy for LLMs. ToG-2 addresses key limitations of current RAG methods, which often fail to retrieve sufficiently deep and contextually rich information for complex reasoning tasks. By alternating between context retrieval and KG-based retrieval, ToG-2 effectively links and enriches information sources, guiding LLMs in producing more reliable and contextually informed answers. On various tasks (multi-hop KBQA, multi-hop complex document QA, slot filling, and fact verification), ToG-2 achieves satisfying performance in comparison with different RAG baselines (text-based, KG-based, and hybrid).", "questions": "- Could you conduct a statistical significance test (e.g., two-tailed t-test) to compare ToG-2 with the baselines in Table 1, and report the p-values?\n\n- Could you study the effect of KG quality on the performance of ToG-2 by using incomplete WikiData as KG (e.g., with 10%, 20%, or 50% of the entities/relations)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ The proposed tight-coupling approach is well-motivated. It uses KGs to guide the retrieval of document contexts while simultaneously treating these documents as entities in the KG, thereby creating a feedback loop that enhances both retrieval depth and context fidelity.\n\n+ The iterative retrieval process is intuitive. It mimics human reasoning by continuously refining the search for information based on initial retrieval results.\n\n+ Experiments are comprehensive. Six datasets across four different tasks are examined. Baselines using CoT, text-only RAG, KG-based RAG, and hybrid RAG are compared. Besides performance comparison, the authors also conduct ablation studies, efficiency analysis, and case studies to verify some of their design choices.", "weaknesses": "- Statistical significance tests are not conducted. It is not clear whether the gaps between ToG-2 and the baselines are statistically significant or not in Table 1. In fact, the improvement is subtle in some columns. Also, the statistical significance of ablation studies should be considered.\n\n- The quality and completeness of the KG used in ToG-2 can significantly influence its retrieval accuracy and reasoning performance. The effect of KG quality on the performance of ToG-2 is not accurately quantified. Although the authors add a ToG-FinQA dataset in their experiments with a newly built KG, the quality of this KG is also unknown. It would be valuable to explore the performance of ToG-2 with incomplete WikiData.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QJkQoBOFCd", "reviewer": "Reviewer_8nFX", "summary": "This manuscript presents a framework designed to augment the reasoning capabilities of Large Language Models (LLMs) through the integration of knowledge graphs. The framework addresses several limitations inherent in current methodologies by implementing three key strategies: hybrid knowledge exploration, knowledge-guided graph search, and knowledge-guided context retrieval. The objective is to mitigate issues such as constrained knowledge retrieval and the scarcity of informed knowledge within LLMs.", "questions": "- What about total runtime and API call counts compared to other baselines like direct LLM methods and text-based RAG approaches ?\n- Table 7 should clarify whether it reports the reasoning time for each discrete query or for each RP and EP iteration, given that multi-hop reasoning entails successive RP and EP cycles.\n\n- The question also arises: Why does ToG outperform ToG 2.0 in the Creak dataset? To make it more actionable, more detailed analysis of the performance on the Creak dataset should be provided, including potential reasons for this discrepancy and its implications for the method's strengths and limitations.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The manuscript adeptly delineates the constraints of LLMs in reasoning through complex queries and proposes a systematic and coherent methodology to surmount these limitations.\n\n- The incorporation of hybrid knowledge, derived from both knowledge graphs and wiki documents, constitutes an intuitive approach to enhancing the inferential competencies of LLMs, which, to the best of my knowledge, is a novel contribution to the field.\n\n- Table 1 offers a comparative analysis with appropriately set benchmarks, demonstrating the superiority of the proposed ToG 2.0 model as a new SOTA solution. The authors further substantiate this claim through empirical experiments.\n\n- The figures and graphics were well done and helped with understanding the methodology of the paper substantially.", "weaknesses": "- The incremental contributions of ToG 2.0 over its predecessor, ToG, are noteworthy but not transformative. \n> Specifically, the core improvements include the addition of context-retrieval and context-guided entity pruning to ToG's existing Relation exploration and Entity exploration.\n\n\n- Although  LLM costs is not normally a point of significant concern for the soundness/rigor of a work. However, the methodology is financially demanding, as processes such as Knowledge Exploration, Relation Pruning, Relation Discovery, Entity Pruning, and Reasoning all necessitate frequent calls to the LLM API. The associated high costs may deter further exploration by researchers within the Graph RAG community. \n> Constructively, it is suggested that the authors elaborate on a refined cost analysis and contemplate the implementation of optimizations to reduce API calls. Such measures would effectively address the raised concerns about `extensive utilization of LLM APIs’ and simultaneously provide pragmatic suggestions for further enhancement.\n\n\n- I harbor reservations regarding the efficiency of this approach. Empirically, processes that require extensive utilization of LLM APIs are inherently time-consuming. As evidenced by the time expenditures for Relation Pruning (RP), Entity Pruning (EP), and Reasoning detailed in Table 3, the task at hand is laborious. The documentation lacks clarity on whether Table 7 provides the RP, EP, and reasoning times for each individual sample. If it does, then for multi-hop Knowledge Graph (KG) reasoning tasks, compounded by the size of the dataset, the task becomes significantly time-consuming when juxtaposed with direct LLM-only methods or Text-based RAG approaches. Additionally, ToG 2.0 necessitates grounding in the vast corpus of external Wikipedia data. \n> I contend that evaluating the efficiency of this method solely in comparison to ToG 1.0 lacks impartiality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uJ99D9Mo4r", "reviewer": "Reviewer_wm5v", "summary": "This paper introduces Think-on-Graph 2.0 (ToG-2), a novel hybrid retrieval-augmented generation (RAG) framework that aims to enhance large language model (LLM) reasoning by combining structured knowledge from knowledge graphs (KGs) with unstructured knowledge from texts. The key innovation is the \"tight-coupling\" approach between KG-based and text-based RAG, where KGs guide deeper context retrieval while textual context enables more precise graph retrieval. The framework iteratively performs knowledge-guided context retrieval and context-enhanced graph retrieval to obtain comprehensive information for LLM reasoning. The authors demonstrate ToG-2's effectiveness through extensive experiments across multiple knowledge-intensive datasets, showing state-of-the-art performance on 6 out of 7 benchmarks and the ability to elevate smaller LLMs' reasoning capabilities to be comparable with larger models.", "questions": "1. How does the performance of ToG-2 scale with significantly larger knowledge graphs or document collections?\n\n2. Could you provide more details about the failure modes of the system and potential strategies to address them?\n\n3. How sensitive is the system to the quality of the initial entity linking step? What happens when entity linking fails?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Technical Innovation: The tight-coupling approach between KG and text-based RAG is novel and well-motivated, addressing limitations of previous hybrid approaches.\n\n2. Comprehensive Evaluation: The experimental validation is thorough, covering multiple datasets and including detailed ablation studies. The creation of ToG-FinQA shows commitment to robust evaluation.\n\n3. Implementation Details: The paper provides detailed implementation guidance and pseudocode, making it reproducible.\n\n4. Analysis Depth: The manual analysis and runtime studies provide valuable insights into the framework's behavior and efficiency.", "weaknesses": "1. Scalability Analysis: While runtime comparisons are provided, there could be more discussion about the framework's scalability with very large knowledge graphs or document collections.\n\n2. Error Analysis: Though there is some manual analysis of error cases, a more systematic categorization of failure modes could be valuable.\n\n3. Hyperparameter Sensitivity: While some hyperparameters are studied (width and depth), a more comprehensive analysis of other parameters' impact would be helpful.\n\n4. ToG-FinQA Dataset: While valuable, the dataset is relatively small (97 QA pairs). A larger dataset would strengthen the domain-specific evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GiAH5RL3B1", "reviewer": "Reviewer_HRGs", "summary": "ToG-2 is an iterative RAG framework that combines unstructured and structural knowledge from the input to answer the given question. Concretely, ToG-2 extracts multiple entities from the query, extracts their neighboring entities, filters out these entities via relation pruning to extract a set of candidate entities, and identifies (and prunes) retrieved entity context candidate entity. Experiments show that ToG-2 achieves state-of-the-art on the majority of datasets.", "questions": "Did the authors notice that ToG-2 performs better without relation pruning (when topic pruning and retrieval feedback are also removed) than when only topic pruning and retrieval feedback are removed?\n\nIt is mentioned that “ToG-2 selectively explores entities neighboring the current topic entities on the KG, using the newly encountered entities to refine the retrieval scope, thereby enhancing both efficiency and accuracy.” (lines 161-180, pages 3-4). How is ToG-2 able to enhance/improve efficiency if there are more entities considered (via neighbors in the knowledge graph) compared to just the entities extracted from the query?\n\nIn figure 3b, the performance of ToG-2 when using BGE-Ranker decreases as the number of entities considered increases (from 38% to 33% when the number of entities jumps from 3 to 5). This seems to be counter-intuitive, as the larger the entity space, the more likely it would increase performance (which is the case when using LLMs). Why would this be the case?\n\nWhy not consider a dynamic number of candidate topic entities (dynamic based on the iteration)? Logically, it’s more likely that first order neighbors of an entity in the query would be more important than entities in the second order neighborhood (although this assumption might be invalid when dealing with very granular inputs).\n\nWhat is “CMB” with respect to relation pruning (equation 3, tables 11 & 12)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "State-of-the-art performance is achieved on all but one dataset\n\nToG-2 conducts extensive experimentation to verify their novelty", "weaknesses": "1. Figures\n\nThe main figure, as well as the introduction, indicates that ToG-2 is distinctly different from Text-based RAG, KG-based RAG, and Hybrid (text- + KG-based) RAG. Upon inspection, it appears that ToG-2 is just a fancy version of Hybrid RAG in that entities are selected based on a n-order neighborhood of the entities identified in the query. While ToG-2 is no doubt different from previous Hybrid RAG approaches, it should still be considered a Hybrid RAG approach.\n\nThe caption of the main figure should give a description of the flow of the methodology. Given that there are multiple modules in ToG-2, and that important information of these modules are not depicted (more in the following comment) an explanation of the information flow is necessary.\n\nWhile the main figure provides a nice overview of ToG-2, it is missing important detailed information. For example, relation/entity scoring and the prompts used aren’t able to be determined by looking at the main figure. Consider creating another figure that depicts these details.\n\n2. Experiments\n\nNo analysis of threshold scores for relation pruning (“The relations with a low score will be pruned” on page 5, lines 230-231). How much would performance vary if the threshold is changed? What does the distribution of relation scores from the LLM look like? These are questions that should’ve been answered. Considering that ToG-2 is a multistage pipeline, and that relation pruning is one of the first steps in the pipeline, analysis here is vital given that error from this module will propagate through your remaining modules. Furthermore, there isn’t any mention (let alone the reasoning) of the threshold score used in ToG-2. In the code, the score that is used is 0.2 (https://anonymous.4open.science/r/ToG2/wiki_func.py, line 38). This should have been mentioned in the manuscript and not have been identified solely by investigating the repository.\n\nTable 6, the influence of each module (which should be in the main content), indicates that the removal of relation pruning increases performance across all datasets (the increase in performance in from row 2 to row 3). This appears to nullify the contribution that relation pruning offers.\n\nExperiments involving LLMs should’ve been repeated multiple times given that LLMs have been shown to vary greatly based on the prompt.\n\n3. Grammatical/formatting errors\n\nOn page 1, line 40, there is a space missing between “issues” and “(Zhao et al., 2024)” \n\nThe query in the main figure “Where was one of the runners born who almost broke Craig Virgin’s Illinois Boys Cross Country record?” should be re-worded for clarity. Consider stating “What was the birthplace of one of the runners who almost broke Craig Virgin’s Illinois Boys Cross Country record?”.\n\nConsider removing the word “and” on line 228, page 5 between equations 2 and 3, as the current format is an unorthodox way of introducing two equations simultaneously.\n\n“Figure 2” needs a space between “Figure” and “2” on page 5, line 239.\n\nThe “a” in “Given a topic entities” in line 241, page 5 should be removed.\n\nThe citations in section 4.2 are in double parenthesis. This needs to be fixed.\n\nThe title of section 4.5.3 “Width&Depth Settings” is missing a space between “Width” and “&” as well as “&” and “Depth”.\n\nThe ablation study comparing the performance when removing different modules (Table 6) should be put in the main content, not in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)