Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
Authors: Jiashuo Sun
Chengjin Xu
Lumingyuan Tang
Saizhuo Wang
Chen Lin
Yeyun Gong
Lionel Ni
Heung-Yeung Shum
Jian Guo
Venue: ICLR 2024 poster (2024)
Keywords: Knowledge Graph
Chain-of-Thought
Large Language Models
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Although large language models (LLMs) have achieved significant success in various tasks, they often struggle with hallucination problems, especially in scenarios requiring deep and responsible reasoning. These issues could be partially addressed by introducing external knowledge graphs (KG) in LLM reasoning. In this paper, we propose a new LLM-KG integrating paradigm ``$\hbox{LLM}\otimes\hbox{KG}$'' which treats the LLM as an agent to interactively explore related entities and relations on KGs and perform reasoning based on the retrieved knowledge. We further implement this paradigm by introducing a new approach called Think-on-Graph (ToG), in which the LLM agent iteratively executes beam search on KG, discovers the most promising reasoning paths, and returns the most likely reasoning results. We use a number of well-designed experiments to examine and illustrate the following advantages of ToG: 1) compared with LLMs, ToG has better deep reasoning power; 2) ToG has the ability of knowledge traceability and knowledge correctability by leveraging LLMs reasoning and expert feedback; 3) ToG provides a flexible plug-and-play framework for different LLMs, KGs and prompting strategies without any additional training cost; 4) the performance of ToG with small LLM models could exceed large LLM such as GPT-4 in certain scenarios and this reduces the cost of LLM deployment and application. As a training-free method with lower computational cost and better generality, ToG achieves overall SOTA in 6 out of 9 datasets where most previous SOTAs rely on additional training.

Published as a conference paper at ICLR 2024
THINK-ON-GRAPH DEEP AND RESPONSIBLE REASON- ING OF LARGE LANGUAGE MODEL ON KNOWLEDGE GRAPH
Jiashuo Sun Chengjin Luuminguunn Taag Saizhuo Wang
Chen Lin Yeyun Gong Lionel M. Ni Heung- Yeung Shum 14 Jian Guo 15t
'DDE Research, International Digital Economy Academy
Xiaamn University
University of Southern California
"The Hong Kong University of Science and Technology
The Hong Kong University of Science and Technology (Guangzhou)
6 Microsoft Research Asia
ABSTRACT
Although large language models (LL.S) have achieved significant success in vari- ous tasks, they often struggle with hallucination problems, especially in scenarios requiring deep and responsible reasoning. These issues could be partially addressed by introducing external knowledge graphs (KG) in LLM reasoning. this paper, we propose new LLM-KG integrating paradigm "LLM @ KG" which treats the LLM as an agent to interactively explore related entities and relations on KGs and perform reasoning based on the retrieved knowledge. We further implement this paradigm by introducing a new approach called Think-on-Grapy (ToG), which the LLM agent iteratively executes beam search KG, discovers the most promising reasoning paths, and returns the most likely reasoning results. We use number of well-designed experiments to examine and illustrate the following advantages of ToG: 1) compared with LLMs,, ToG has better deep reasoning power; 2) ToG has the ability knowledge traceability and knowledge correctability by leveraging LLMs reasoning and expert feedback; 3) ToG provides flexible plug- and-play framework for different LLMs, KGs and prompting strategies without any additional training cost; 4) the performance of ToG with small LLM models could exceed large LLM such as GPT-4 in certain scenarios and this reduces the cost of L.M deployment and application. As training-free method with lower computational cost and better generality, ToG achieves overall SOTA out of 9 datasets where most previous SOTAs rely additional training. Our code is publicly available at /atlttp::/// //tpthuu// com/ IDEA- Faaa-FiinA/Too
INTRODUCTION
Large language models (LLMs)) Ouyang et al. 2022 OpenAl 2023
Thoppilan et al. 2022, Brown
jtt al., [2000a] Chowdhery al. 2022 Touvron al. 2023) have demonstrated remarkable perfor- mance across various natural language processing tasks. These models capitalize on pre-training techniques applied to vast text corpora to generate responses that are coherent and contextually appropriate. Despite their impressive performance, LLMs have substantial limitations when facing complex knowledge reasoning tasks (Petroni et al. 2021 Talmor et al. 2019 Talmor & Berant 2018 Zhang al. 2023) that require deep and responsible reasoning. Firstly, LLMs usually fail to provide accurate answers to questions requiring specialized knowledge beyond what was included in the pre-training phase (out-of-date knowledge in Figure Ta), or questions requiring long logic chain and multi-hop knowledge reasoning. Secondly, LLMs lack responsibility, explainability and transparency.
* "Equal contribution.
I Work done during internship at IDEA Research.
1 "orresponding author.

---

Published as a conference paper at ICLR 2024
Question: What is the majority party now in the country where Canberra is located?
LLM-onty
(Chen-o Thouught Prompe: Lera thes alon by slep Ruppors Canbirs capital of Ausinall According my knowledge Sepliebber 2021 the prime minister of Australla is Scot Moniion who is member the Liberal So the answer should be Liberal Party. X
LLM (3
(Rooed: Please generate SPAROL query forthis
Canberra
Canberra In occaddin
Responce: Sorry, based on my querry reaut from the knowledge base, I cannot answer your question since do not have onough infommaiion X
queston
Magerty pary Austrslaile
Hesponee: SELECT Reauetry huorty WHEREl
IaLoaaeein
Nut Fourd
Aeuurry daprop mapetthhary Jparty
Kanbeera dhome stocatedis fooustry.
Australia
mapetyParry
Labor Party
LLM @ KG
"Think"
Thisk
Looking for triles related In Canberra
most relevent is [Conberra, eapilal answering the Locking
most relevant one (Pustrala. thony Albanese)
TThnk"
Annthony Abbaneee from Lebor Party.
fnromiaion collected for this quesiion.
Australia
graph
graph
LLM-inherent innowledgo
Condlude
loader
Canbera
caniial
Australo
peine minister
Nionnsse
the Ausinalas Leber
The answer Labor Party
2019
(c)
Figure I: Representative workflow of three LLM reasoning paradigms: (a) LLM-only (e.g.. Chain-of- Thought prompting), (b) LLM @ KG (e.g., KBQA via LLM-generated SPARQL query), (c) LLM @ KG (e.g., Think-on-Graphh.
raising concerns about the risk of ballucinations or toxic texts. Thirdly, the training process for LLMs is often expensive and time-consuming, making it challenging to keep their knowledge up to date.
Recognizing these challenges, natural and promising solution is to incorporate external knowledge such as knowledge graphs (KGs) to help improve LLM reasoning. KGs offer structured, explicit, and editable representations of knowledge, presenting complementary strategy to mitigate the
limitations of LLMs (Pan et al. 2023). Researchers (Li et al., 20236) et al., 2022] Back et al.,
2023b; Yang et al. 2023 Wang al. 2023a Jiang al.) 2023) have explored the usage of KGs as external knowledge sources to mitigate hallucination in LLMs. These approaches follow a routine: retrieve information from KGs, augment the prompt accordingly, and feed the increased prompt into LLMs (as illustrated in Figure [p.. In this paper, we refer to this paradigm as "LLM + KG". Although aiming to integrate the power of LLMM and KG, in this paradigm, LLM plays the role of translator which transfers input questions to aanchineunderstandaal but it does not participate in the graph reasoning process directly. Unfortunately. the loose-coupling LLM @ KG paradigm has its own limitations, and its success depends heavily on the completeness and high quality of KG. In Figure Tp, for example, although LLM successfully identified necessary relation types required to answer the question, the absence of the relation "majority party" leads to failure in retrieving the correct answer.
command for KG searching and reasoning,
Building upon these considerations, propose new tight-coupling "LLM @ KG" paradigm where KGs and LLMS work in tandem, complementing each other's 's capabilitiess in each step of graph reasoning. Figure provides an example illustrating the advantage of LLM @ KG. In this example, the missing relation "majority party" resulting in the failure in Figure DD can be complemented by reference triple (Australia, prime minister. Anthony Albanese) discovered by the LLM agent with dynamic reasoning ability Yao et al. 2022), as well as the political party membership of Anthony Albanese coming from LLM's inherent knowledge. In this way. the LLM succeeds in generating the correct answer with reliable knowledge retrieved from KGs. As an implementation of this paradigm, we propose an algorithmic framework Sebinkk-on-Graplee (meaning: L.MMs "Think" along the reasoning paths "on" knowledge "graph" step-by-step. abbreviated as ToG below), for deep. responsible, and efficient LLM reasoning. Using the beam search algorithm (Jurafsky & Martin 2009) in KG/LLM reasoning (Atif et al.) 2023 Sun et al.] 2023a; Xie et al.) 2023 Liu et al. (002)), ToG allows LLM to dynamically explore a number of reasoning paths in KG and make decisions accordingly. Given an input question, ToG first identifies initial entities and then iteratively calls the
LLM to retrieve relevant triples from KGs through exploration (looking for relevant triples in KG via "on graph" step) and reasoning (deciding on the most relevant triples via "think" step) until adequate
2

---

Published as a conference paper at ICLR 2024
Question:
What is the majority pazty now in the country whare Canberra is located?
Depth
Depib
Austreler Cappal Temiary
Depth 3
Labor Party
condinent
tamlory
country
poliscal party
Canberra
Austraiia
Arthony Alseniiee
courtry
sontowe
Vccsputton
heard govorument
Vrime Miniseer
Pottidan
Auseralia
Depit
Not Infomationn
Australlan Capttal Temikry
Depth
cantral bank
05
Depeh
diienshpp
25
partiff
continant
Enough Information
Anthany
pollical
Limtinent
herriorr
Cenbeera
ocuntry
cappbllc
Australia
Reasoning
head govermment
Australia
Roasoning
affashakder
Grospolion
Party
Australian
Territory
Prime Minister
Australia
Anthony Albanese
Prime Minister
Australia
Politician
Reasoning
Enough
Answer
Reasoning
Canberra - capital of Austrolia prite miristar - Anthony Albanese- - politicll party Labor Party
Labor Party
Gonerate
Canberra - capiaal Australia head gevernment Prime Minister of Australia- offoshhlder Arthony Albansse
Canberra - caplal of Australia prima mirialer - Anthony Allbanase -cosupation Politicinn
An example workflow of ToG. The glowing entities are the central entities where the search starts at each iteration (depth), and the entities with boldface are the selected central entities for the next iteration after pruning. At each pruning step, the darkness of the edges represents the ranking score given by LLM, and the dashed lines indicate relations that have been pruned due to low evaluation scores.
Figure 2:
information through the top-N reasoning paths in beam search gathered to answer the question (judged by LLMs in "Think" step) or the predefined maximum search depth is reached.
The advantage of ToG can be abbreviated as (1) Deep reasoning: ToG extracts diverse and multi- hop reasoning paths from KGs as the basis for LLM reasoning, enhancing L.MMs* deep reasoning capabilities for moowledge-nttensin tasks. (2) Responsible reasoning: Explicit, editable reasoning paths improve the explainability of the reasoning process of LLMs, and enable the tracing and correction of the provenances of models' outputs.
(3) Flexibility and efficiency: a) ToG is plug- and-play framework that can be applied to variety of LLMss and KGs seamlessly. b) Under ToG framework, knowledge can be updated frequently via KG instead of LLM whose knowledge-update expensive and slow. ToG enhances the reasoning ability of small LLMs (e.g.. LLAMA2-70B) be competitive with big LLMs (e.g., GPT-4).
METHODS
ToG implements the "LLM & KG" paradigm by asking LLM to perform beam search on knowledge graph. Specifically, it prompts the LLM to iteratively explore multiple possible reasoning paths on KGs until the LLM determines that the question paths. ToG constantly updates and maintains top-N reasoning paths P p= {P1- P2,.... PN) for the question after each iteration, where N denotes the width of beam search. The entire inference process of ToG contains the following 3 phases: initialization, exploration, and reasoning.
be answered based on the current reasoning
2.1 THINK-ON-GRAN
2.1.1
INITIALIZATION OF GRAPH SEARCH
Given question, ToG leverages the underlying LLM to localize the initial entity of the reasoning paths on knowledge graph. This phase can be regarded as the initialization of the top-N reasoning paths P. ToG first prompts L.LMs to automatically extract the topic entities in question and gets the
3

---

Published as a conference paper at ICLR 2024
top-N topic entities E = {ef,el, eQ,,............... ...., e., to the question. Note that the number of topic entities might possibly be less than N.
2.1.2 EXPLORATION
At the beginning of the D-th iteration, each path Pn consists of D triples, i.e., Pn [( J.n o M2=1" where eh and ea denote subject and object entities, r is specific relation between them, (ch, rd J,n. (o,)) and (cat) jnn e are connected to each other. The sets of the tail entities and relations in P are denoted as FD-1 (c D-1 eN - and (r .22 1 ......N ".
pd+1
respectively.
The exploration phase in the D-th iteration aims to exploit the LLM to identify the most relevant top-N entities ED from the neighboring entities of the current top-N entity set ED based on the question x and extend the top-N reasoning paths P with ED To address the complexity of handling numerous neighboring entities with the LLM, we implement a two-step exploration strategy: first, exploring significant relations, and then using selected relations to guide entity exploration.
Relation Exploration Relation exploration is beam search process with the depth of I and the width of from DD to RD. The whole process can be decomposed into two steps: Search and Prune. The LLM serves an agent automatically complete this process.
Search At the beginning of the D-th iteration, the relation exploration phase first searches out relations Reand,n linked to the tail entity e for each reasoning path Pu. These relations are
aggregated into Re In the case of Figure 2 E { (Canberra) and R Reand denotes the of all relations linked to Canberra inwards or outwards. Notably, the Search procedure can be easily completed by executing two simple pre-defined formal queries shown in Appendix E. and E.2 which makes ToG adapt well to different KGs without any training cost.
Prune Once we have obtained the candidate relation sets R and the expanded candidate reason- ing paths Poend from the relation search, we can utilize the LLM select out new top-N reasoning paths P ending with the tail relations RD from Peand based on the literal information of the ques- tion x and the candidate relations R.D Raand The prompt used here can found Appendix F. As shown in Figure 2 the LLM selects top-3 relations {capital of, country, territory) } out from all relations linked to the entity Canberra in the first iteration. Since Canberra is the only topic entity, the top-3 candidate reasoning paths are updated (Canberra, capital of), (Canberra, country), (Canberra, territory)].
Entity Exploration Similar to relationship exploration, entity exploration is also beam search process performed by the LLM from R.' to ED, and consists of two steps, Search and P Prune.
Search Once we have obtained new top-N reasoning paths and the set of new tail relations RD from relation exploration, for each relation path Pn E P. we can explore a candidate entity set Baand, by querying (c r ?) or (?, : eD-1), where DD1 Tn denote the tail entity and relation of Pn- We can aggregate { {E' cand, 1 2ennd,21... E N') into E and expand top-N reasoning paths P to Prand with the tail entities E.D For the shown case, El Fannd can be represented as Australia, Australia, Australian Capital Territory).
Prune Since the entities in each candidate set E is expressed in natural language, we can leverage the LLM to select new top-N reasoning paths P ending with the tail entities E out from Peand- The prompt used here be found in Appendix [...2. As shown in Figure 2 Australia and Australian Capital Territory are scored as 1 since the relations capital of, country and territory are only linked one tail entity respectively, and the current reason- ing paths are updated as { (Canbbrra, capital of, Australia), (Canberra, country, Australia), (Canberra, territory, Australian Capital Territory)].
After executing the two explorations described above, we reconstruct new top-N reasoning paths P where the length of each path increases by 1. Each prune step requires at most N L.M calls.
4

---

Published as a conference paper at ICLR 2024
2.1.3 REASONING
Upon obtaining the current reasoning path P through the exploration process, we prompt the LLM to evaluate whether the current reasoning paths are adequate for generating the answer. If the evaluation yields a positive result, we prompt the LLM to generate the answer using the reasoning paths with The prompt used for evaluation and generation can be found in Appendix E.3.3 and E.3.4 Conversely, if the evaluation yields a negative result, we repeat the Exp 1 orat on and Rea Reasoning steps until the evaluation is positive or reaches the maximum search depth Dmax If the algorithm has not yet concluded, it signifies that even upon reaching the Dmaz ToG remains unable to explore the reasoning paths to resolve the question. In such scenario, ToG generates the answer exclusively based on the inherent knowledge in the LLM. The whole inference process of ToG contains D exploration phases and D evaluation steps well as generation step, which needs at most 2ND + + calls to the LLM.
the query as imputs as illustrated in Figure 2
2.2 RELATION-BASED THINK-ON-GRAPI
Previous KBQA methods, particularly based on semantic parsing, have predominantly relied on rela- tion information in questions to generate formal queries (Lan et al. 2022). Inspired by this, we propose relation-base -based ToG (ToG-R) that explores the top-N relation chains {pn- = (c) Tny Tn. ....... r -2)) ) starting with the topic entities {el {c X 1== instead of triple-based reasoning paths. ToG-R sequentially performs relation search, relation prune and entity search in each iteration, which the same as ToG. Then ToG-R performs the reasoning step based on all candidate reasoning paths ending with F obtained by entity search. If the L.M determines that the retrieved candidate reasoning paths do not contain enough information for the LLM to answer the question, we randomly sample N entities from the candidate entities Liunnd and continue to the next iteration. Assuming that entities in each entity set Bunnd, probably belong to the same entity class and have similar neighboring relations, the results of pruning the entity set (E ( 1.N might have little impact the following relation exploration. Thus, we use the random beam search instead of the LLM-constrained beam search in ToG for entity prune, referred as random prune. Algorithm D and 2 show the implementation details of the ToG and ToG-R. ToG-R needs at most ND + D + calls to the LLM.
Compared ToG, ToG-R offers two key benefits: 1) It eliminates the need for the process of pruning enúties using the LLM. thereby reducing the overall cost and reasoning time. 2) ToG-R primarily emphasizes the literal information of relations, mitigating the risk of misguided reasoning when the literal information of intermediate entities is missing or unfamiliar to the LLM.
3
EXPERIMENTS
3.1 EXPERIMENTAL DESIGN
3.1.1 DATASETS AND EVALUATION METRICS
In order to test ToG's s ability on multi-hop knowledge-intensive reasoning tasks, we evaluate ToG on five KBQA datasets Multi-hop and Single-hop): CWQ (Talmor & Berant 2018), WebQSP (Yih et al. (0166). GrailQA (Gu et al. 202T). QALD10-en (Perevalov et al. 2022)) Simple Questions (Bordes et al., 2015). Moreover, in order to examine ToG on more generic tasks, we also prepare one open-d QA dataset: WebQuestions (Berant et al. 2013);; two slot filling datasets: T-REx (ElSahar et al., 2018) and Zero-Shot RE (Petroni et al. [021]; ); and one fact-checking dataset: Creak only randomly selected 1,000 samples each for testing in order to save computational cost. For all datasets, exact match accuracy (Hits @ 1) is used our evaluation metric following previous works (Li et al. 2023b
(One et al.. 2021). Note that, for two big datasets GrailQA and Simple Questions,
Baek et al. 2023b Jiang et al. 2023 Li et al. 2023a).
3.1.2
METHODS SELECTED FOR COMPARISON
We compare with standard prompting (IO prompt) (Brown et al. 2020b). Chain-of- ThoThhthh prompting (CoT prompt) (Wei et al. (022), and Self- coff-sonsstenccy (Wang et al. 2023c) with 6 in-context exemplars and "step-by-step reasoning chains. Moreover, for each dataset, we pick previous state-of- the-art (SOTA) works for comparison. We notice that fine-tuning methods trained specifically on
5

---

Published as a conference paper at ICLR 2024
Hop KBQA
Singl-Hop KBQA
Opei-Dooniin QA
Slot Filling
Foct Chocking
Method
CWQQ
WelQSP
GraiiA
QALDI9-05
Shmple Questionss
Welquesnkoss
T-REX
Willeur externai Knowledge
10 prompt w/ChiIGTT
37.6
63.3
29.4
42.0
20.0
48.7
33.6
27.7
89.7
CJT w/ChiGPT
38.8
62.2
28.1
42.9
20.3
48.5
32.0
28.8
90.1
wiChaGPP
With esternal Louneledgee
Price FT SOTA
70.4"
K2.1"
75.47
45.4
85.8
56.35
87.71
14.67
WM.2
Price Promsting SCIT
74.4"
ToGi- w/ChuntaPT
58.9
75.8
36.4
45,4
86.5
TDG (Ours) WCChiGPT
57.1
76.2
68.7
50.2
53.6
54.5
76.8
58.0
91.2
Toti-R (Oun) WIGPT-4
69.5
81.9
80.3
54.7
38.5
57.1
73.5
80.9
95.4
W
Table 1:
The ToG results for different datasets.
The prior FT (Fine-tuned) and prompting SOTA
include the best-known results: a: Das et al. (202I); 3: Yu et al. (2023); y Gu et al. (2023);
Santana al. (2022): ; Back et al. (202a)) Ç: Kedia et al. (2022) ; mp Glass al. (022); A: Petroni
et al. 2021) ; 6: Yu et al. (2022); k:
Liet al. 2023a).
evaluated datasets usually have advantage by nature over methods based on prompting without training, but sacrificing the flexibility and generalization on other data. For a fair play. therefore, we compare with previous SOTA among prompting -aased methods and previous SOTA among all methods respectively. Note that the paper Tan et al. (2023) is not involved in comparison because its results are not based on standard exact match and thus incomparable.
3.1.3 EXPERIMENT DETAILS
Method
CWQ
WebQSP
Given the plug-and-play convenience of ToG, we try three LLMs in experiments: ChatGPT. GPT-4 and Llama-2. We use OpenAI API call ChatGPT (GPT-3.5-turbo) and GPT-4 Llama- 2-70B- -hBt- (Touvron et al. 2023) runs with A100-40G without quantization, where the tem- perature parameter is set to 0.4 for exploration process (increasing diversity) and set to 0 for rea- soning process (guaranteeing reproducibility). The maximum token length for the generation set to 256. In all experiments, we set both width N and depth Diaa to for beam search. Freebase (Bollacker et al. (0088) is used as KG for CWQ, WebQSP, GrailQA, Simple Questions, and Webquestions, and Wikidata /Vrandečié & Krötzsch 2014) is used KG for QALDIO-en, T-REx, Zero-Shot RE and Creak. We use 5 shots ToG-reasoning prompts for all the datasets.
Fine-tuned
NSM (He ct al. 2021
53.9
74.3
CBR- BRR-KBQA (Das et al.
2021
67.1
TIARA (Shu ét al, 2022
75.2
DeCAF Yu et al.
2023
70.4
82.
Prompting
KD-CoT Wane et al.
2023b
50.5
73.7
StructGPT Tiang al.
2025
72.6
KB-BINDER
20238
74.4
LLama2-70B Chat
CoT
39.1
57.4
ToG-R ToG
57.6
68.9
53.6
63.7
Gain
(+18.5)
(+11.5)
CharGPT
CoT
38.8
62.2
ToG-R
57.1
75.8
ToG
58.9
76.2
Gain
(+20.1)
(+14.0)
GPT-4
3.2
MAIN RESULTS
CoT
46.0
67.3
ToG-R
67.6
81.9
3.2.1
COMPARISON TO OTHER METHODS
ToG
69.5
82.6
Gain
(+23.5)
(+15.3)
Since CoT uses external KG to enhance LLM, we first compare it with those methods lever- aging external knowledge as well. As we can see in Figure even if ToG is a training-free prompting-bar method and has natural disad- vantage in comparison with those fine-tuning methods trained with data for evaluation, ToG with GPT-4 still achieves new SOTA performance in 6 out of datasets, including WebQSP, GrailQA,
Table 2: Performances of ToG using different back- bone models on CWQ and WebQSP.
(GPT-3.5-turfe and GPT-4 both from https:// comm

---

Published as a conference paper at ICLR 2024
QALD1O-en, WebQuestions, Zero-Shot RE and Creak. Even for some dataset without SOTA, e.g.. CWQ, the performance of CoT has already been close to SOTA (69.5% v.s. 70.4%) If comparing with all promoting-basee methods, both ToG with GPT-4 and its weaker version ToG with ChatGPT can win the competition in all datasets. In particular, the improvement of 1.6% on open-domain QA dataset WebQuestions demonstrates the ToG's generality on open-domain QA tasks. We also notice that the performance of ToG on single-hop KBQA dataset is not as good as its performance on other datasets. These results indicate that ToG is more effective on multi-hop datasets in general, which supports our argument that ToG enhances the deep reasoning capability of LLMs.
We also see from Figure that, compared with those methods without leveraging external knowledge (e.g, IO, CoT and SC prompting methods), the advantage of ToG is more significant. For example, the performance improves 51.8% and 42.9% on GrailQA and Zero-Shot RE, respectively. turns out that benefits from external KG can not be ignored in reasoning.
ToG outperforms ToG-R on most datasets since the triple-based reasoning paths provide additional intermediate entity information compared to the relation chains retrieved by ToG-R. More detailed analysis of the answers generated by ToG can be checked Appendix [.2 And the results of previous methods each dataset are reported in Appendix C for better comparison,
3.2.2 PERFORMANCES WITH DIFFERENT BACKBONE MODELS
Given ToG's flexibility of plug-and-play, we evaluate how different backbone models affect its performance on two datasets CWQ and WebQSP. Table shows that, as we expected, the performance of CoT improves with the size (also reflecting partially the reasoning ability) of backbone models (GPT-4> ChatGPT> > Llama-2). Furthermore, we see that, the larger the backbone model, the larger the gap between CoT and ToG (the gain increases from 18.5% for Llama-2 to 23.5% for GPT-4 on CWQ, and from 11.5% for Llama-2 to 15.3% for GPT-4 on WebQSP), and this indicates more potential of KG can be mined using a more powerful LLM.
In addition, even if using the smallest model Llama-2 (70B parameters), ToG outperforms CoT with GPT-4. This implies a much cheaper technical route for LLM deployment and application, i.e., TOG with cheap small LLM may be a candidate for substituting expensive big LLM, especially in vertical scenarios that external KGs can cover.
3.2.3 ABLATION STUDY
We perform various ablation studies to understand the importance of different factors in ToG. We conduct our ablation studies on two subsets of the test sets of CWQ and WebQSP, each of which contains 1,000 randomly sampled questions.
Do search depth and width matter for ToG? To ex- plore the influence of the search depth Dmaz and the beam width N on ToG's performance, under settings with depths ranging from 1 to and widths from to 4. As shown in F ToG's performance im- proves with the search depth and width. This also implies that ToG's performance could potentially be improved with the increment of the exploration depth and breadth. However, considering the computational cost (which in- creases linearly with the depth), we set both the depth and width to as the default experimental setting. On the other hand, the performance growth diminishes when the depth exceeds This mainly because only small part of questions have the reasoning depths (based the number of relations in SPARQL, as seen in Figure [2] in the Appendix) of greater than 3.
Method
CWQ
WebQSP
conduct experiments
CoT
37.6
62.0
ToG
w/ Freebase
58.8
76,2
w/ WikiData
54.9
68.6
ToG-R
w/ Freebase
59.2
75.1
w/ WikiData
51.9
66.7
Table 3: Performances of ToG using
different source KGs on CWQ and We- bQSP.
Do different KGs affeet ToG's performance? One of the main advantages of ToG is its plug-and play capabilities. As shown in Table ToG achieves significant improvements with different source KGs on CWQ and WebQSP, compared CoT. On the other hand, different source KGs might have
7

---

Published as a conference paper at ICLR 2024
CWQ
WebOSP
00.0
56.3
TrG 1rC-Ft
02.0
57.5
76.0
TGGR
2 2,0.0
2
2 70000
8 6075
47.5
72.
62.5
58.0
70.0
80.0
Depths
Widths
Depths
Widthe
Figure Performances of ToG with different search depths and widths.
different effects the performance of ToG. Notably, Freebase brings more significant improvements on CWQ and WebQSP than Wikidata, since both datasets are constructed upon Freebase. Moreover, in very large KG like Wikidata, the searching and pruning processes relatively challenging.
How do different prompt designs affect ToG? We perform additional experiments to determine which types of prompt representations can work well for our approach. The results are presented in Table "Triples" denotes using triple formats as prompts to represent multiple paths, such as "(Canberra, capital of, Australia), (Australia, prime minister, Anthony Albanese)). "Sequences" refers to the utilization of sequence format, as illustrated in Figure [ "Sentences" involves converting the triples into natural language sentences. For example, "(Canberra, capital of, Australia)" can be converted "The capital of Canberra is Australia." The result shows that the utilization of triple- based representations for the reasoning paths yields the highest degree of efficiency and superior performance. Conversely, when considering ToG-R, each reasoning path is relation chain starting from a topic entity, rendering it incompatible with the triple-based prompt representation. Consequently, the transformation of ToG-R into the natural language form results in excessively lengthy prompts, thereby leading to notable deterioration in performance.
Method
CWQ
WebQSP
ToG
w/ Triples
58.8
76.2
w/ Sequences
57.2
73.2
w/ Sentences
58.6
73
ToG-R
w/ Sequences
59.2
75.1
w/ Sentences
50.1
67.3
Table 4: Performances of ToG using dif- ferent prompting designs.
Comparing the affects from different pruning tools. Other than the LLM, lightweight models that mea- sure text similarity like BM25 and SentenceBERT, can be employed as pruning tools in the exploration phase. We can select top-N entities and relations based on their literal similarities with the question. We investigate the impacts of different pruning tools on the performance of the ToG, as demonstrated Table 5 The replacement of the LLM with either BM25 or SentenceBERT results in the significant performance degradation our approach. Concretely, the results CWQ drop on average by 8.4%, and the results on WebQSP drop on average by 15.1% The results show that the L.MS perform best pruning tool in terms of effectiveness. On the other hand, after utilizing the BM25 or SentenceBERT,, we only need D calls the LLM instead of 2 + D as we discuss in Section 2.1.3 which enhances the efficiency of ToG.
Method
CWQ
WebQSP
ToG
w/BM25
51.4
58.7
w/SentenceBERT
$1.7
66.3
w/ChaIGPT
58.8
76.2
ToG-R
w/BM25
49.4
57.3
W/St
50.1
60.1
w/ChaIGPT
59.2
75.1
Table 5: Performances of ToG using dif- ferent pruning tools.
We conduct additional ablation studies the effect of the number of seed exemplars and the difference between ToG and naive beam search on the KG, which can be seen in Appendix B.I
3.3 KNOWLEDGE TRACEABILITY AND CORRECTABILITY IN ToG
The quality of KG is very important for correct reasoning by ToG. An interesting feature of ToG is knowledge traceability and knowledge correctability during LLM reasoning, and it provides way to improve KG's quality using ToG itself and reduce the cost of KG construction and correction. As illustrated in Figure the explicit reasoning paths of the ToGs can be displayed to users. If potential
8

---

Published as a conference paper at ICLR 2024
Hore
explores:
moscot Phonatic's fram's spring training stadiuum?
Philii Phanatic Jeam Philadelphia Philiis- Location Philadelphia
2. Phillie Phanatic 7eam Philadelphia Phillies - Avena Stedium Bright House Field
reasening ig stadium Phana Bright
spting pearing
6D
3. Phillie Phanadi- Team Philodelohia Phillkes Mascot Phillic Phanadc.
frw sterium liscyy second path.
the
Self- Ee--Evelustion
Plecatio
Manral
Toem
Philakkphen
Malless
Phili
Matcot
Toam
Fhiladoptca
Spectrumm Field Cleawater
Aweaditadumi
Armapnddaa
Florkda arich having proviosity hew named Bright Hous Fold Need to cornect this error on the knowledge graph?
Lecalion
Locatica
(hisdelpiia
Slusse Fiely
Boga!
Philaeloun
Spacmmn
Fidid
Yes. Please help me to correct the knowledge graph.
SV
Kaunng
[ three paths explorec:
Phillia Plunalic Townn Piilechelphie Phillias Lecation Pislachelphia
ressoring pathe,
2 Phillie Phanatic Tean Phitadelphia Phillies Arena Stadium -Spectrum Field
the Piiadalpia Prilics
5. Philie Phanatic leam Philadelphia Phillies- Mascol - Philie Phanatic.
Figure 4: The illustration of knowledge traceability and correctability of ToG.
errors in ToG answers are discovered by human users/experts or other LLMss, ToG has the ability to trace back and examine the reasoning path, find suspicious triples with errors, and correct them.
Take the case in Figure 4as as an example. Given the input question "What is mascot Phillie Phanatic's team's spring training stadium?", ToG outputs the wrong answer "Bright House Field" in the first round. Then ToG traces back all reasoning paths, localizes the cause of the error may come from the
second reasoning path (Phillic Phanatic Team, Philadelphia Phillies Arena Stadium, Bright House Field), and analyzes that the eлror comes from the old name "Sppectum Field" of "Bright House Field" in the outdated triple (Philadelphia Phillies, Arena Stadium, Bright House Field). According to the hints from ToG, the user ask LLM to correct this eπror and answer the same question with the correct information. This example reveals that ToG not only enhances LLM with KG, but also improves the quality of KG with LLM,, known knowledge infusion (Moiseev al. 2022
RELATED WORK
Reasoning with LLM Prompting Chain-of-Thought (CoT) Wei et al. 2022) has been shown to be effective in enhancing LLM reasoning. It creates a series of prompt instances according to reasoning logic under few-shot learning paradigm in order to improve LLM's performance on complex tasks. The thought of CoT has been improved along different dimensions, including Auto-CoT (Zhang et al.) 2022). Complex-Cor
(Wang et al., 2023c). Iter-CoT (Sun et al. 2023b), ToT (Yao et al.) (2023). GoT (Besta et al.) 2023) and so on. Given the limitation that all these works only use the knowledge in training data, recent efforts such as ReAct (Yao et al.) (2022) attempt utilize the information from external sources to further improve the reasoning performance.
(Fu et al. 2023).
KG-enhanced LLM KG has advantages dynamic, explicit, and structured knowledge representa- tion and techniques combining L.MSs with KGs have been studied. Early studies (Peters et al. 2019 Luo al. (024) embed structured knowledge from KGs into the underlying neural networks during the pretraining or fine-tuning process. However, KG embedded in LLM sacrifices its own nature of explainability in knowledge reasoning and efficiency in knowledge updating (Hu et al. 2023).
Recent works instead combine LLMs with KGs by translating relevant structured knowledge from KGs to textual prompts for LLMs. All the methods belong to the LLM < KG paradigm we defined in the introduction section. On the other hand, Jiang et al. (2023) asks LLM to explore KG and so it can be regarded as a special case of ToG, which belongs to the LLM X KG paradigms.
5 CONCLUSION
We introduce the LLM @ KG paradigm for integrating LLMs and KGs and propose the Think- on-Graph (ToG) framework, which leverages LLM as an agent participating in KG reasoning for better docision-making Experimental results demonstrate that ToG outperforms existing fine-tuning based methods and compping-bassed methods without additional training cost and mitigates the hallucination issue of L.LMs.

---

Published as a conference paper at ICLR 2024
6 ACKNOWLEDGEMENT
We express our sincere gratitude to the esteemed reviewers for their invaluable feedback and con- structive comments, which significantly contributed to the improvement and refinement of this paper. Their insightful suggestions and meticulous attention to detail have played a pivotal role in enhancing the quality and clarity of our research work.
REFERENCES
Farah Atif, Ola El Khatib, and Djellel Eddine Difallah. Beamqa: Multi-hop knowledge graph question answering with sequence-to-sequencce prediction and beam search. In Hsin-Hsi Chen, Wei-Jou (Edward) Duh, Hen-Hsen Huang, Makoto P. Kato, Josiane Mothe, and Barbara Poblete (eds.). Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2023, Taipei, Taiwan, July 23-27, 2023. pp. 781-790. ACM, 2023. URL https: /tt////oiiooo org 0. 11 145/ 353 961886688888 3591 698
doi: (0.1145/3539618 18.358.3311 399.
Jinheon Baek, Alham Fikri Aji, Jens Lehmann, and Sung Ju Hwang. Direct fact retrieval from knowledge graphs without entity linking. In Anna Rogers, Jordan L. Boyd-Graber, Graber, and Naoaki Okazaki (eds.), Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL. 2023, Toronto, Canada, July 9- 14, 2023, pp. 10038- 10055. Association for Computational Linguistics, 2023a. doi: 10. 18653// 12022 acl.oog..... URL
acl- 558
Jinheon Back, Alham Fikri Aji, and Amir Saffari. Knowledge augmeeted language model prompting for zero-shot knowledge graph question answering, 2023b.
Debayan Banerjee, Pranav Ajit Nair, Ricardo Usbeck, and Chris Biemann. Gett-qa: Graph embedding based 12t transformer for knowledge graph question answering, 2023.
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. Semantic parsing freebase from question-answer pairs. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. EMNLP 2013, 18-21 October 2013, Grand Hyatt Seattle. Seattle, Washington, USA, A meeting of SIGDAT, a Special Interest Group of the ACL, pp. 1533-1544. ACL, 2013.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models, 2023.
Kurt D. Bollacker, Colin Evans, Praveen K. Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collaboratively created graph database for structuring human knowledge. SIGMOD Conference, 2008.
Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. Large-scale simple question answering with memory networks. CoRR, abs/1 htss/1506.02075. 2015. URL http::t/axxvv..orrrr
abs/1506..22 02075]
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florin, Balcan, and Hsuan- TieunTTienha Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a. URL | Atsttaaa wtw.atttttllll..mm 145700d6bfcb44
new.riinnnnnnnnnnnnnooeoe Abstractt
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Berbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh,
10

---

Published as a conference paper at ICLR 2024
Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models few-shot learners. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020b. 1457c0d 4b4 9674 4 wtw.e11eeeaaaaeeeeee..
neurips CC htt.cc//pppp httpp/aape/22/////ap/p ract -html
Shulin Cao, Jiaxin Shi, Zijun Yao, Xin Lv, Jifan Yu, Lei Hou, Juanzi Li, Zhiyuan Liu, and Jinghui Xiao. Program transfer for answering complex questions over knowledge bases. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), ACL 2022, Dublin, Ireland,
May 22-27. 2022. pp. 8128- 81888840..4080 Assocciaioo for Computational Linguistiies 2022. doi: 10.18653/
v1/2022.acl-long.5555 URL htt.https:s : org. 10. 11w.1.1/111122222.2222 ac long. 559
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstent Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways, 2022.
Rajarshi Das. Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay- Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum. Case-based reasoning for natural language queries over knowledge bases, 2021.
Michiel de Jong, Yury Zemlyanskiy, Joshua Ainslie, Nicholas FitzGerald, Sumit Sanghai, Fei Sha, and William Cohen. Fido: Fusion-in-decoder optimized for stronger performance and faster inference. arXiv preprint arXiv:2212.081153 2022.
Cicero Nogueira dos Santos, Zhe Dong, Daniel Cer, John Nham, Siamak Shakeri, Jianmo Ni, and Yun hsuan Sung. Knowledge prompts: Injecting world knowledge into language models through soft prompts, 2022.
Hady ElSahar, Pavlos Vougiouklis, Arslen Remaci, Christophe Gravier, Jonathon S. Hare, Frédérique Laforest, and Elena Simperl. T-rex: A large scale alignment of natural language with knowledge base triples. In Nicoletta Calzolari, Khalid Choukri, Christopher Cieri, Thierry Declerck, Sara Goggi. Kôiti Hasida, Hitoshi Isahara, Bente Macgaard. Joseph Mariani, Hélène Mazo, Asunción Moreno, Jan Odijk, Stelios Piperidis, and Takenobu Tokunaga (eds.), Proceedings of the Eleventh International Conference on Language Resources and Evaluation, LREC 2018, Miyazaki, Japan, May 7-12, 2018, European Language Resources Association (ELRA), 2018 URL http://www Irec- conf. pttp:/ocecpppggg..// www.inngssrreeee11 1rec2018/ /tt///uumaaaaam ieeerreeesse 632 html
Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot. Complexity-based prompting for multi-step reasoning. In The Eleventh International Conference Learning Representationss ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL httllttppp//ppeeeeeete net/ met/pdffid=yfliin
19
Michael Glass, Gaetano Rossiello, Md Faisal Mahbub Chowdhury, Ankita Naik, Pengshan Cai, and Alfio Gliozzo. Re2G: Retrieve, rerank, generate. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp.
Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. 10.53v/l 1///22/222222// maa.emmanna-aannn...m URL https: / ac ant
2022. naac -mainn 194
11

---

Published as a conference paper at ICLR 2024
Yu Gu, Sue Kase, Michelle Vanni, Brian M. Sadler, Perey Liang, Xifeng Yan, and Yu Su. Beyond LLD.; three levels of generalization for question answering on knowledge bases. In Jure Leskovec, Marko Grobelnik, Mare Najork, Jie Tang, and Leila Zia (eds.). WWW '21: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, pp. 3477 3488. ACM / IW3C2, 2021. doi: 01//5//344281.34499999
|RI /wt:///oiiio org 100 1ee.11144444444
3449992
Yu Gu, Xiang Deng, and Yu Su. Don't generate, discriminate: A proposal for grounding language models to real-world environments, 2023.
Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. Improving multi-hop knowledge base question answering by learning intermediate supervision signals. Liane Lewin- Eytan, David Carmel, Elad Yom-Tov, Eugene Agichtein, and Eygeniy Gabrilovich (eds.), WSDM '21, The Fourteenth ACM International Conference on Web Search and Data Mining, Virtual Event, Israel, March 8-12, 2021, pp. 553-561. ACM, 2021. doi: 10. 10.1145/443796334447555 URL https: //doi. org. 10. 11411 1tt..//0/1..11333777855111111110 3441755
Linmei Hu, Zeyi Liu, Ziwang Zhao, Lei Hou, Liqiang Nie, and Juanzi Li. A survey of knowledge enhanced pre-trained language models. IEEE Transactions on Knowledge and Data Engineering, 2023.
Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji-Rong Wen. Structgpt: A general framework for large language model to reason over structured data, 2023.
Dan Jurafsky and James H. Martin. Speech and language processing: an introduction to natural language processing, computational linguistics, and speech recognition, 2nd Edition. Prentice Hall series in artificial intelligence. Prentice Hall, Pearson Education International, 2009. ISBN 9780135041967 URL htt.:/ttts///// wor Locat. orreettoroooolcccooooooooo /10ell///31130000
Akhil Kedia, Mohd Abbas Zaidi, and Haejun Lee. Fic: Building global probability space by leveraging early fusion in encoder for open-domain question answering. Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022. pp. 4246-4260, Association for Computational Linguistics, 2022. doi: (0.18653/v1/2222 emnlp-main.288 2855.
emnlp pelll-mmiinn maw.. 285
Yunshi Lan and Jing Jiang. Query graph generation for answering multi-hop complex questions from knowledge bases. Association for Computational Linguistics, 2020.
Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. Complex knowledge base question answering: A survey. IEEE Transactions on Knowledge and Data Engineering, 2022.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-zuugmenter generation for knowledge-inlensivee intensive nlp tasks, 2021.
Tianle Li, Xueguang Ma, Alex Zhuang, Yu Gu, Yu Su, and Wenhu Chen. Few-shot in-context learning knowledge base question answering. In Anna Rogers, Jordan I.. Boyd-Graber, and Naoaki Okazaki (eds.). Proceedings of the 61st Annual Meeting of the Association for Computational Linguisticss (Volume Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023, pp. 6966-6980. Association for Computational Linguistics, 2023a. doi: 10. 1225333/122222alllloooo acw.//20o......ooooeooe 385
URL
Xingxuan Li, Ruochen Zhao, Yew Ken Chia, Bosheng Ding, Lidong Bing, Shafiq Joty, and Soujanya Poria. Chain of knowledge: A framework for grounding large language models with structured knowledge bases, 2023b.
Wei Liu, Weihao Zeng, Keqing He, Yong Jiang, and Junxian He. What makes good data for alignment? comprehensive study of automatic data selection in instruction tuning. In The Twelfth International Conference on Learning Representations, 2024, URL ptttstps:: htttps://openreiiie. www.fooruuiidaaaaammmmm
12

---

Published as a conference paper at ICLR 2024
Ye Liu, Semih Yavuz, Rui Meng, Dragomir Radev, Caiming Xiong, and Yingbo Zhou. Uni parserr Unified semantic parser for question answering on knowledge base and database. arXiv preprint arXiv:2211.05165, 2022.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, 2019.
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning. In International Conference Learning Representations, 2024.
Fedor Moiseev, Zhe Dong, Enrique Alfonseca, and Martin Jaggi. SKILL: structured knowledge infusion for large language models. In Marine Carpuat, Marie-Cathering Catherine de Marneffe, and Iván Vladimir Meza Ruíz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human I Language Technologies, NAACI. Seattle, WA, United States, July 10-15, 2022, pp. Linguistics, 2022. doi: 10. 18653/6/vvvl1 1/2//// www.n-aaalaaaaa 113. URL httpps://dda org/10
Association for Computational
18653/v1/202 naacl ma meain.11 113
Yasumasa Onoe, Michael Q. Zhang, Eunsol Choi, and Greg Durrett. CREAK:
A dataset for commonsense reasoning over entity knowledge. In Joaquin Vanschoren and Sai-Kit Yeung (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurlPS Datasets and Benchmarks 2021, December 2021, virtual, 2021. URL benchmarks proceddigs.............o........ pptppeeeddrrssrrrrrpp....pppp/pp
cc/pappr//221//
#sst:/5733cccc2222000ffffaa22223 Abstrrr Abstracttroune2.teee homud2hhmm..
OpenAl. Gpt-4 technical report, 2023.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. arXiv Preprint, 2022. doi: 00448500/2Xi..2203.0112 URL httphhtt:/// httpps:////oi http://o..orr/////////////////// 48550/ arXiv. 02155
Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: A roadmap. arXiv preprint arXiv:2306. 08302, 2023.
A. Perevalov, D. Diefenbach, R. Usbeck, and A. Both. Qald-9-plus: A multilingual dataset for question answering over dbpedia and wikidata translated by native speakers. In 2022 IEEE 16th International Conference on Semantic Computing (ICSC), pp. 239-234, Los Alamitos, URL CA. USA, jan 2022. IEEE Computer Society. doi: 10. (1109//CSSC2281.22222000 00045 https: /oi. oeeecc/pperrrccceee..../.....0/0
Matthew E. Peters, Mark Neumann, Robert Logan, Roy Schwartz, Vidur Joshi, Sameer Singh, and Noah A. Smith. Knowledge enhanced contextual word representations. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 43-54, Hong Kong, China, November 2019. Association for Computational Linguisties. doi: 10. 10.18653/11DD19-1000 URL www.aaaooooooooooooo...
Fabio Petroni, Aleksandra Piktus, Angela Fan, Patrick Lewis, Majid Yazdani, Nicola De Cao, James Thorne, Yacine Jernite, Vladimir Karpukhin, Jean Maillard, Vassilis Plachouras, Tim Rocktäschel, and Sebastian Riedel. Kilt: benchmark for knowledge intensive language tasks, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, (1(1):5485555)) 2020.
Manuel Alejandro Borroto Santana, Bernardo Cuteri, Francesco Ricca, and Vito Barbara. SPARQL- QA enters the QALD challenge. In Xi Yan, Meriem Beloucif, and Ricardo Usbeck (eds.),
13

---

Published as a conference paper at ICLR 2024
Proceedings of the 7th Natural Language Interfaces for the Web of Data (NLIWoD) co-located with the 19th European Semantic Web Conference (ESWC 2022), Hersonissos, Greece, May 29th, 2022, volume 3196 of CEUR Workshop Proceedings, pp. 25-31 CEUR-WS.org. 2022. URL https: ctt//eeurrreee ws org / Vol- 10ooo-311660 3196 20119//pape3....m pdd
Yiheng Shu, Zhiwei Yu, Yuhan Li, Börje Karlsson, Tingting Ma, Yuzhong Qu, and Chin- Yew Lin. TIARA: Multi-grained retrieval for robust question answering over large knowledge base. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp.
Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.186533V 2ttp://w/222...mmmmmaam.. 2022. wmnlp-nama.. 555
URL https: https////y/aaaanoooooooooo
Haitian Sun. Tania Bedrax- Weiss, and William W. Cohen. Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text, 2019.
Hao Sun, Xiao Liu, Yeyun Gong, Anlei Dong, Jingwen Lu, Yan Zhang, Daxin Jiang, Linjun Yang, Rangan Majumder, and Nan Duan. Beamsearchqa: Large language models are strong zero-shot QA solver. CoRR, 105/23355117666 2023a. doi: 10.485550/rXx..2235... 14766. URL
https://doi wrw/o0.............o............ 48550/ att.v 2305. 14766
Jiashuo Sun, Yi Luo, Yeyun Gong, Chen Lin, Yelong Shen, Jian Guo, and Nan Duan. Enhancing chain-of-thoughts prompting with iterative bootstrapping in large language models, 2023b.
Alon Talmor and Jonathan Berant. The web knowledge- for answering complex questions. In Marilyn A. Walker, Heng Ji, and Amanda Stent (eds.), Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 1-6, 2018, Volume I (Long Papers), pp. n18-1059. URL hhttps://dos http:///oooooog//0.. org/10, 11653//1/11118881 1059
Association for Computational Linguistics. 2018. doi: 10.18653/v11 1/
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsenseqa: A question answering challenge targeting commonsense knowledge. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Techuologies, NAACL-HLE 2019, Minneapolis. MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pp. 4149 4158, 2019. /ooi org/10 1865188633188 v1 n1 9-14
doi: 10. 10.18853/v1/1 1/t33//1//111/// 1421.
Yiming Tan, Dehai Min, Yu Li, Wenbo Li, Nan Hu, Yongrui Chen, and Guilin Qi. Evaluation of chatgpt as a question answering system for answering complex questions. arXiv preprint arXiv:2303.07992, 2023.
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, YaGuang Li, Hongrae Lee, Huaixiu Steven Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang, Maxim Krikun, Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Yanqi Zhou, Chung-Ching Chang, Igor Krivokon, Will Rusch, Mare Pickett, Kathleen S. Mellst-ells Meredith Ringel Morris, Tulsee Doshi, Renelito Delos Santos, Toju Duke, Johnny Soraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Diaz, Ben Hutchinson, Kristen Olson, Ale- jandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravi Rajakumar, Alena Butryna, Matthew Lamm, Viktoriya Kuzmina, Joe Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Agüera y Arcas, Claire Cui, Marian Croak, H. Chi, and Quoc Le. Lamda: Language mod- els for dialog applications. CoRR, 2022. URL https::/aaaxiiii org 2ta.o///220.000 2201.0823999
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei. Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh
14

---

Published as a conference paper at ICLR 2024
Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, lliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023.
Denny Vrandečié and Markus Krötzsch. Wikidata: A free collaborative knowledgebase, Commun. ACM, 57(10))78 85, sep 2014. ISSN 0001-0782. doi: 10. 10.1145/262948, URL https://doi brg/100.1155222248
Jianing Wang. Qiushi Sun, Nuo Chen, Xiang Li, and Ming Gao. Boosting language models reasoning with -onolleege prompting, 2023a.
Keheng Wang. Feiyu Duan, Sirui Wang. Peiguang Li. Yunsen Xian, Chuantao Yin, Wenge Rong. and Zhang Xiong. Knowledge-driven cot: Exploring faithful reasoning in Ilms for innteedge-intensive question answering, 2023b.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023c. URL/attss://openeeeee pdf P NIMMr
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Ed H. Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv Preprint, 2022. URL
htttps://arxins http::///aaaioooor//a/////00/ wwtp://///bbbb///o/// /201. 11903
Tianbao Xie, Chen Henry Wu, Peng Shi, Ruiqi Zhong, Torsten Scholak, Michihiro Yasunaga, Chien- Sheng Wu, Ming Zhong, Pengcheng Yin, Sida I. Wang, Victor Zhong, Bailin Wang, Chengzu Li, Connor Boyle, Ansong Ni, Ziyu Yao, Dragomir Radev, Caiming Xiong, Lingpeng Kong, Rui Zhang, Noah A. Smith, Luke Zettlemoyer, and Tao Yu. UnifiedSKG: Unifying and multi- tasking structured knowledge grounding with text-to-text language models. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 602-631, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL https: /tt:://acllaan www.aannnnooogy...oo. 220///222222 2022. emnlp main. 39
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min- Yen Kan, Junxian He, and Qizhe Xie. Decomposition enhances reasoning via self-evaluation guided decoding. 2023.
Linyao Yang, Hongyang Chen, Zhao Li, Xiao Ding, and Xindong Wu. Chatgpt is not enough: Enhancing large language models with knowledge graphs for fact-aware language modeling, 2023.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023.
Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Was 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, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 2: Short Papers. The Association for Computer Linguisties, 2016. doi: 2033
10. 10.18653/v 1/p66/3/1/11-2233
Donghan Yu, Sheng Zhang, Patrick Ng, Henghui Zhu, Alexander Hanbo Li, Jun Wang, Yiqun Hu, William Wang, Zhiguo Wang, and Bing Xiang. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases, 2023.
Wenhao Yu, Chenguang Zhu, Zhihan Zhang, Shuohang Wang, Zhuosheng Zhang, Yuwei Fang. and Meng Jiang. Retrieval augmentation for commonsense reasoning: A unified approach. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 4364-4377 Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.186533v 2022. emn mommlp-main... 294
URL https: // ac wwtp/aaannooooooooogggooo
15

---

Published as a conference paper at ICLR 2024
Hang Zhang, Yeyun Gong, Xingwei He, Dayiheng Liu, Daya Guo, Jiancheng Lv, and Jian Guo. Noisy pair corrector for dense retrieval. arXiv preprint arXiv:2311.03798, 2023.
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. arXiv Preprint, 2022. doi: 104455004XX1.2210003333 URL https 7/doi w0.50.0..../5////a..a.oo http://rrxxv.22..0333333
16

---

Sensitivity to the Number of Seed Examplars To bet- ter understand how sensitive ToG is sensitivity the num- ber of seed exemplars, we employ sensitivity analysis shown Figure [ We conduct zero experiment and select 1-6 examples from the training set few-shot setting. In the few-shot tests, we randomly chose M of (1,2, 2, 4, 6) exemplars as demonstrations and replicated the experiments three times. As the number of cxamples in the demonstrations increases, the overall performance also generally improves. However, the performance peaks for ToG and ToG-R differ (with the best performance for ToG at 5-shot and for ToG-R at 4-shot). Moreover, ToG's zero- shot performance outpaces ToG-R. This can be attributed Published as a conference paper at ICLR 2024
A
ALGORITHM FOR ToG
We summarize the comprehensive algorithmic procedure of ToG and ToG-R, as shown in Figure Algorithm and 2
Algorithm ToG
Algorithm 2 TooG-R
Require: Input x, L.M π, depth limit Dmaz sam- sam- Ren-Rree Input æ; LLM n, depth limit Dmaz ple limit N.
ple limit N. Initialize F.O Extract entities x;, P x- 0.
Initialize F <- Extract entities on s; P
M + 0.
M + 0.
while D S Dmax do
while D Dmaz do R Regand: Peand t- Search(z, ED-1, ,P
R Peand t Search(x, ED P)
RD. P +- Prune(n, Reand: Peand)
Rd P. Prune(T, R P Pownd)
FD
Peand- Poend < Search(ar F.D-1, RR, P)
F Peand t- Search(r, FD-1, RD, P)
E Prune(n, I, E Poand)
if Reesonning(T, 2, P.D ED cand) then Generate(TT, x, P, E cand))
Reesoniigg(, v, P) then Generate(T, x, P) break
break end if
end if Increment D by 1. end while
ED P Random Prune( Peond)
Increment D by end while
if D > Dman then Generate(T, x)
if D > Dmaz then Generate(T, x)) end if
end
B ADDITIONAL ABLATION STUDY AND EXPERIMENT ANALYSIS
In this section, we conduct more experiments for ablation study in addition to Section 3.2.3 and analyze experimental results of ToG in detail.
B. ADDITIONAL ABLATION STUDY
Search Algorithm
Dataset
EM
CWQ
30.1
Naive Beam Search
WebQSP
46.1
CWQ
59.2
TOG-R
WebQSP
75.1
CWQ
58.8
TOG
WebQSP 76.2
Table 6: The results of Naive Beam
Search, ToG methods CWQ and We- bQSP.
to ToG having fully completely explored paths, ensuring commendable performance even in zero-shot. In contrast, ToG-R omits entities in the path, but its average performance with demonstrations is superior to ToG.
Difference with Naive Beam Search ToG is slightly different from the beam search. ToG uses the top-N reasoning paths evidence while the naive beam search chooses the most plausible path as the only reasoning path. We conduct naive topl- topl-beam search methods for ToG on CWQ and WebQSP. For each depth of the ToG, choose the reasoning path with the highest plausibility, to evaluate if
17

---

Published as a conference paper at ICLR 2024
ToG
ToG-R
ToG
ToG-R
60
78
74
56
72
Accuracy
Agpuracy
70
154
86
52
64
50
62
2 Number seed examples
Number seed examples
Figure 5: Exemplar sensitivity analysis for CWQ and WebQSP for ToG, where "0" denotes zero-shot and "k" denotes k-shot.
CWQ
WebCSSP
GraliQA
2000
Holucteen Fareet
100
500
Nekoo Forell beer
700
Dakis Cepr
Fommet Ovor
Sample
1500
400
Emer Samplee
500
300
500
OCT
TeG
Tac--
Toc--t
Figure 6: The erroneous instances and categories in the CWQ, WebQSP, and GrailQA of IO, CoT, and ToG.
the current reasoning path is sufficient to answer the questions. The experiment results are shown in Table In naive beam search, the calibration error accumulates along the inference, leading the instability of the final result. We believe that ToG can partially alleviate this issue by considering the top-N reasoning paths.
B.2 RESULT ANALYSIS
We conduct a detailed analysis the answers generated by ToG and ToG-R.
Error Analysis We considered three types of errors: (1) Hallucination error, (2) Refuse error and (3) Format error. The distribution is shown in Figure 6 Our approach has significantly reduced the hallucination and refusal to answer error types in IO and COT. For GrailQA, ToG even reduces these types of errors by 50% and 60%, respectively. Moreover, in ToG's error samples, there are still many instances of ballucination and refusal to answer errors. This is because the current search depth and width both set to 3. By increasing the search depth and width, these error instances will further decrease (refer to Section 3.2.3). Furthermore, we currently generalize incorrect answers as hallucinations, but there are various categories within hallucinations, which we won't 't discuss in this paper. Additionally, after applying ToG, there's a slight increase in samples with format errors. This result shows that the explored paths lead to noticeable increase in the tokens, sometimes even exceeding the maximum output limit. However, the rate from this issue is negligible (less than 3%).
Evidence of Answers We conducted an analysis of the correctly answered samples in three datasets to investigate the evidence for LLM in generating answers as shown in Figure 7 Evidently, significant portion the answers are derived from the paths explored by ToG. while roughly 20% rely exclusively on the intrinsic knowledge embedded within LLM's parameters for generating
2LLM will refuse answer due lack of information.
18

---

Published as a conference paper at ICLR 2024
responses. is worth noting that around 7% of the correctly answered samples require combination of knowledge from both the explored paths and LLM's s inherent knowledge (as elaborated in Appendix Table 2T.. This distinction sets approach apart from traditional graph- based search methods, does not necessitate the path to encompass the node containing the correct answer entirely. Instead, the explored paths supplement and reference LLM's inherent knowledge. The distribution of answer types for ToG-R is almost indistinguishable from that of ToG, proving the robustness of our approach.
CWQ
WebQSP
GrailQA
Both
Both
Both
LLM Inherent
LLM Inherent
LLM Inherent
60%
93%
3%
4%
13%
27%
3%
Figure 7: The proportions of ToG's evidence of answers on CWQ, WehQSP, and GrailQA datasets.
CWQ
Poths
WebQSP
Paths
GrailQA
Paths
Both
LLM Inherent
LLM Inherent
LLM Inherent
55%
78%
2%
20%
17%
25%
5%
Figure 8: The explored path overlap ratio of ToG-R on CWQ, WebQSP, and GrailQA datasets.
We also conduct an analysis of the correctly answered samples in three datasets to investigate the ratio of overlap between the paths explored by ToG and the ground-truth path in SPARQL. The definition of overlap ratio is the ratio of overlapping paths the total number of relations in ground-trutt SPARQL:
The Overlap Ratio between the Explored Paths and Ground-truhh Paths
Count(Rel(Pathss n Re((SPARQL))
Coun(Re(((PARQQL)
where Rel(*) denotes all the unduplicated relations in the and Count denotes the number of 3 Figure 9 is path schematic which takes the case shown Table 22 for example. It can be observed from Figure 10 that the paths explored by ToG are identical to the golden paths of an average of 30% correct samples, while the paths of an average of 21% correct samples are completely different from the golden path. This indicates that ToG has successfully explored a completely and approximately new path in the knowledge graph space to reach the final answer entity. For ToG-R, the disparity between the two is primarily evident in the CWQ dataset, where the percentage of intervals (25,50) in ToG results is quite significant (nearly 40%), whereas ToG-R results tend to be more evenly distributed as shown in Figure 11] We contend that this discrepancy arises from the disregard of entity, thereby enhancing the diversity of explored relations. This represents significant application of knowledge graph reasoning academic research.
We approximately calculate the length of path by counting the number of relations in the ground-truth SPARQI..
19

---

Published as a conference paper at ICLR 2024
Explored Path
Philli Phanate
Mhilndelphia Phallice
stndium
Bright House Fieki
Ground Truth
Phillie Phanatic
leam
Pailadelphis
Phillies
mmining_.pmun
uaniity
facilty
Dright Ioous
(rart( SPARQI
(Couri mascol, anens, stadium] A [leam missee. tniniing ground. faciliy)))
Couns_Re)(SAARQL.)
Count
grouad, facilit)))
Figure Path schematic to calculate overlap.
CWQ
WebQSP
GrailQA
60%
40%
30%
Percentage
Percentage
30%
30%
20%
20%
20%
10%
0%
(20.75)(75100) Overlap Ratio
(50,79)75,100)
(C0.75((75100)
Overlap Ratio
Overlap Ratio
Figure 10: The explored path overlap ratio of ToG on CWQ, WebQSP, and GrailQA datasets.
CWQ
WebaSP
GrailQA
35%
20%
30%
30%
Percentage
15%
Parcentage
25%
Percentage
20%
10%
18%
19%
10%
8%
[0.25] (25,50) (50.79](251100) Overlap Ratio
100
[0.25] (25.50) (70,75
100
(0.25) (25,50) (50 700
100
Overlap Ratio
Overiap Ratio
Figure 11: The path overlap ratio of ToG-R on CWQ. WebQSP, and GrailQA datasets.
CWQ WebQSP
1200
1000
800
600
400
Length of paths SPARQL
Figure 12: The lengths of the ground-truth SPARQL queries within the CWQ and WebQSP datasets, computed based on relation numbers.
20

---

Published as a conference paper at ICLR 2024
0.8
Model
Model
ToG ToG-R
ToG
ToG R
0.6
CoT
OoT
0.4
0.4
0.2
0.2
0.0
0.0
8+
Longth of patns SPAROL
Longt of putto SPAROL
Figure 13: ToG, ToG-R and CoT's performance among CWQ and WebQSP dataset.
The Reasoning Depth of Questions We calculate the reasoning depth of testing questions based on the number of relations within their ground-truth SPARQI. queries on CWQ and WebQSP. The counts of questions with different reasoning depths are shown in Figure 12 We analyze the performances of ToG, ToG-R, and CoT on testing questions of both datasets with different reasoning depths. As illustrated in Figure 13, the performances of CoT show roughly decreasing trends on both datasets, with the reasoning depth of testing questions increasing. Conversely, ToG and ToG-R can partially counteract the performance degradation caused by the increment of reasoning depths of questions, especially on CWQ. Generally, the performance difference between ToG and CoT becomes more significant on deeper questions.
B.2. EFFICIENCY OF ToG
There many solutions to improve efficiency and reduce the computational complexity (proportional to the number of calling LLMs) of ToG from the original O(ND) to O(D), where D is the depth (or equivalently length) of the reasoning path, and N is the width of the beam-search (how many paths are remained in the pool in each iteration).
Solution 1 Reducing computational complexity from O(ND) to O(D) by using lightweight model in pruning. The bottleneck of computation is the pruning step, which contributes N D times calling, and it is important to optimize it for computational efficiency. A technical route is to replace LLM with small models such as BM25 and Sentence-BERS in the pruning step since the small models are much faster than LLM calling. In this way, we can reduce the number of LLM calling from 2N D+ + + D+ When D=3, for example, there are only 4 times LLM calling. However, this optimization sacrifices the accuracy due to the weaker scoring model in pruning. For instance, as shown in Table 5 of the manuscript, the performance of ToG on WebQSP drops from 76.2% to 66.3% after replacing ChatGPT with SentenceBERT for pruning. To alleviate the issue of the performance degradation, we can appropriately increase the search width to compensate the loss because increasing search width can improve the chance of the optimal path to be selected in the pool and it doesn't I affect the number of L.LM calling. To empirically verify this, we increase the search width from 3 to 5 and reevaluate ToG with SeRtenceBERT as the pruning model on WebQSP. The accuracy rises to from 66.3% to 68.5% and could be further improved with a greater width since the greater width would not cause increase in the number of LLM calls.
Reducing computational complexity from O(ND) to O(D) by unifying the prompts in the same pruning step. Another solution on speeding up the pruning step is to employ the LLM at once to score all components of N candidate sets for obtaining top-N candidates, instead of calling the LLM N times to score N candidate sets separately. Through this solution, either entity pruning step or relation pruning step only need I LLM call for each iteration. Thus, the maximum number of LLM calls per question needed for ToG and ToG-R would drop to 2D + D - 1 and D + D + 1.
Solution 2
Solution 3 Optimizing pruning step to make the actual calls of LLMs much less than the previously estimated 2ND + D + 1 and closer to some common prompting methods such as CoT-SC. For ToG and other LLM-based methods, the computational time (cost complexity) in the inference phase mainly depends on how many times calling LLM. For each question, ToG needs at most 2ND + D +1 times. Meanwhile, ToG-R needs at most ND + D + times as mentioned in Section 2
21

---

Published as a conference paper at ICLR 2024
Dataset
CWQ 14.3
WebQSP 11.2
GrailQA 10.4
QALDIO-EN
SimpleQuestion 8.7
Average LLM Calls
11.4
Table 7: Average Number of LLM Calls per Question (Part 1)
Dataset
WebQuestion 10.5
T-REx 7.7
Zero-Shot RE
Creak 8.0
Average LLM Calls
7.6
Table 8: Average Number of LLM Calls per Question (Part 2)
Given the beam search width N and maximal reasoning depth D, ToG's initialize the search from the entity mostly aligning with the keyword in question. In each iterative step of the reasoning path, ToG starts from each of the N entities/relations (nodes/edges on knowledge graph) and searches all its neighboring relations/entities. Given the search width N, ToG always keep N "most-likely" candidate reasoning paths in the pool, and thus there are always N candidate entity sets Feand,n and
N candidate relation sets Riannd Consequently, it needs N LLM calls for entity pruning and N calls for relation pruning, respectively, as well as one additional LLM call for reasoning (evaluating if the information from the current candidate paths are enough not). We have point it out that, for each of the N starting entities, all its neighbor entities/relations are NOT scored one by one. On the contrary, all its neighbor entities/relations are "translated" into "one" prompt altogether and are sent to LLM, which output the top-N candidates at one-time. Therefore, each starting entity only calls LLM once for pruning and so N starting entities calls LLM N times in one iterative step. Consequently, there are totally 2ND + D times calling after reasoning D steps. In the end, there is an additional calling that "translate" " the final path to unbestadestt language and answer the user. Therefore, ToG requires 2 ANDD= + D + 1 LLM calls in total. Since most questions can be answered within 3 hops (means depth of reasoning path is 3), and the performance is usually good enough when the search width N=3 as tested in Figure the total number of LLM calling is 2 3 x 3 3 = 22. So the computational time is about 21 times longer than that of LLM-only. With a similar performance to ToG, its variant ToG-R only calls LLM for ND + D + times by using random entity pruning instead of 4LM-based entity pruning, saving nearly half of computational time.
2ND + D + is the maximal computational complexity. In most cases, ToG does not need 2ND + D + LLM calls for question because the whole reasoning process might be early stopped before the maximum reasoning depth D) is reached if LLM determines enough information has been retrieved. Likewise, ToG-R does not really need ND + D + 1 LLM calls in most cases. As an illustration, Table Gabbleaaddd and Table show the average numbers of LLM calls per question needed by ToG on different datasets. It can be seen that in the four multi-hop KBQA datasets, the average numbers of LLM calls (ranging from 10 15) are significantly smaller than 22, which is the theoretical maximum number of LLM calls calculated from 2ND + D + 1 when N=3 and D=3. We can also see that this AVERAGE number gets even smaller (< 10) for single-hop reasoning datasets, such as SimpleQuestion and T-REx.
C DATASET
The statistics of the datasets used in this paper are shown in Table 9 We also provide detailed result table for each dataset, shown in Table to Table [8] illustrating the enhancements of ToG compared to the previous iime-tnnngg-bsee and prompting- bbasd relevant works. For QALDIO- en, WebQuestions, Zero-Shot RE, and Creak, ChatGPT-based ToG reached a new ofate-of-the-arr. Furthermore, GPT-4-based ToG exceeded the fine-tuning based approaches on almost all Multi-Hop KBQA datasets, where on CWQ, ToG close to the state-of of-the-art (69.5%).
22

---

Published as a conference paper at ICLR 2024
Dataset
Answer Format
Train
Test
Licence
Complex WebQuestions
Entity
27,734
3,531
WebQSP
Entity/Number
3,098
1,639
CC License
GrailQA #
Entity/Number
44,337
1,000
QALD-10
Entity/Number
333
MIT License
Simple Quesiton*
Entity/Number
14,894
1,000
CC License
WebQuestions
Entity/Number
3,778
2,032
T-REx
Entity 2,284,168
5,000
MIT License
Zero-Shot RE
Entity 147,909
3,724
MIT License
Creak
Bool
10,176
1,371
MIT License
Table 9: The statistics of the datasets used in this paper. denotes we randomly selected 1,000 samples from the GrailQA and Simple Questions set to constitute the testing set owing to the abundance of test samples.
Model
Method
EM
QGG (Query Graph Generator)
Lan & Jiang 2020
44.1
Fine-Tuning
PulINet (un et al. 2019
45.9
NSM+h (He al.
202T
53.9
CBR-KBOA (Das ct al.
2021
67.1
DecAF (Yu et al. 2023
70.4
KD-CoT (Wang al.
2023b)
49.2
ChatGPT
ToG
57.1
ToG-R
58.9
ToG
53.6
Llama2-70B-Chat
ToG-R
57.6
ToG
67.6
GPT-4
ToG-R
69.5
Table 10: The statics of Fine-Tuning min-Tnning, prompting-basee based methods of Complex WebQuestions dataset.
Model
Method
EM
KD-CoT (Wang et al. 2023b)
73.7
Fine-Tuning
NSM (He ct al. 2021
74.3
Program Transter
Cao et al.
2022
74.6
TIARA (Shu et al.
2002
75.2
DecAF Yu et 2023
82.1
Code-davinci-002
KB-BINDER (Li et al.
2023a
74.4
StructGPT (Jiang et al.
2023)
72.6
ChatGPT
ToG-R
75.8
ToG
76.2
ToG-R
69.4
Llama2-70B-Chat
ToG
64.1
ToG-R
81.9
GPT-4
ToG
82.6
Table 11: The statics of Fine-Tuue Fine-Tuning, compting-based methods of WebQSP dataset.
23

---

Published as a conference paper at ICLR 2024
Model
Method
E.
DecAF Yu et al. 2023)
68.4
UniParser (Liu et al. 2022)
69.5
Fine-Tuning
TIARA (Shu et al. 2022)
73.0
Pangu (Gu et al. 2023
75.4
Code-davinci-002
KB-BINDER (Li al. 2023a)
53.2
ToG-R
66.4
ChatGPT
ToG
68.7
ToG-R
80.3
GPT4
ToG
81.4
Table 12: The statics of Fine- Line-Tuning, prompting-basee based methods of GrailQA dataset
Model
Method
Acc
Fine- Tuning
OPARQI-QA(Santany et al. 2022
45.4
ToG-R
48.6
ChatGPT
ToG
50.2
ToG
53.8
GPT-4
ToG-R
54.7
Table 13: The staties of Fine-Tuning, prompting- methods of QALDI0-en dataset.
Model
Method
EM
T5-LARGE+KPs (oos Santos al.
2022
58.3
Fine-Tume Fine-Tuning
Memory Networks (Bordes et al. 2015)
63.9
GETT-QA (Banerjee et 2023
76.1
DiFaR et al. 2023a)
85.8
ToG-R
45.4
ChatGPT
ToG
53.6
ToG-R
58.6
GPT-4
ToG
66.7
Table 14: The staties of Fine-Tuning prompting-based methods of SimpleQuetsions dataset.
Model
Method
EM
T (Raffel al.
2020)
43.5
Fine-Tuning
PaLM (Chowdhery et al. 2022
43.5
RAG Lewis et al. 2021
45.2
FiDO de Jong al. 2022
51.1
FiE+PAQ (Kedia et al.
2022)
56.3
PALM2
Few-shot (Li et
2023a)
28.2
BeamSearchQAAuan Fine-tuned Retrieeer (Sun et al. 2023a
27.3
ChatGPT
ToG-R
53.2
ToG
54.5
ToG-R
57.1
GPT4
ToG
57.9
Table 15: The statics of Fine-Tuning prompting-base based methods of WebQuestions dataset.
24

---

Published as a conference paper at ICLR 2024
Model
Method
EM
Model
Method
EM
MetaRAG
78.7
Multitask DPR BART
58,0
Wikipedia
81.3
MetaRAG
71.6
Fine-Tuning
Fine-Tuning
single ngram
83.7
KGI_
72.6
KGL
84.4
Wikipedia
74.0
Re2G Glass al. 2022)
87.7
single ngram
74.6
ToG-R
75.3
ToG-R
86.5
ChatGPT
ChatGPT
ToG
76.8
ToG
88.0
ToG-R
75.5
ToG-R
86.9
GPT-4
GPT-4
ToG
77.1
ToG
88.3
Table 16:
The statics of Fine-Tuning, crompting-basee methods of T-REx dataset, where data are from the leaderboard.
Table 17: The statics of Fine-Tuning,
prompting coompiing-bssed methods of Zero-Shot RE, where data are from the leaderboard.
Model
Method
EM
RoBERTa-Lanee Large (Liu et al.
2019)
80.6
Fine-Tuning
T5-3B Raffel et al. 2020
85.6
RACo-Large Yu et al. 2022)
88.2
ToG-R
93.8
ChatGPT
ToG
91.2
ToG-R
95.4
GPT-4
ToG
95.6
Table 18: The staties of Fine-Tunm Tuning,nn prompting-bas -baed methods Creak dataset.
D CASE STUDY
In this section, we present a case analysis of the CWQ dataset to evaluate the utility and limitations of the ToG. We compared ToG with IO, CoT and the New Bing search engine We have selected four examples for analysis, each with top-3 reasoning paths and normalized scores.
In the first example in Table 19 ToG initially identifies "Arthur Miller" and "Lucian", in the question and subsequently expands its reasoning path through the Expl oora ion and Reasoning ng processes. After conducting two iterations of the search, ToG successfully arrived the correct answer, as links the two entities with the reasoning path, which represents the perfect route for locating solutions. Additionally, the presence
TaiName_Entig in intermediate steps of reasoning paths, reflects the incompleteness of the knowledge graph (i.e., some entities lack the "name" relation). However, ToG is still capable performing the next reasoning step, as all available relations contain relevant information. We observe that IO and CoT do not answer the query correctly since they lack the appropriate knowledge, and New Bing do not retrieve the appropriate information during the retrieval process.
In the second example shown in Table 20 IO prompt and CoT even New Bing suffer from hallucination issue and provide an erroneous answer, "Florida", since the "Renegade" the mascot of "Florida State Seminoles" instead of "fight song". ToG obtain the reasoning path "Renegade" - wtwprrssfiggtttonn...o
team" "Pittsburgh Steeler". However, this reasoning path does not lead to final answer, but combined with LLMs', ToG can answer the correct answer "Pennsylvania".
The third example in Table 21 demonstrates example of the ToG-R, where ToG ignores the intermediate entities and focuses on the information in the relations instead. After two-hop of reasoning to "Harvard College". combined with LLMs', ToG gives the final result: "Massachusetts"" It can be observed that IO and CoT do not have background knowledge, and New Bing answers the question correctly since retrieves the correct information.
The final example is shown in Table 22 Where ToG generates reasoning path to the final question (Path 1). Notably, the Ground-Truth reasoning path for the answer sports.sports tetppportttttttteaaaaaeaeaa mascot base. saseeeschemasttgingg.o team waceeaaaatrrraaaaeeeeaa traindnggground wewaadrosaaat.tfccccco facility
"Accessed version July 2023.
25

---

Published as a conference paper at ICLR 2024
- maase.schemastagingg... more hop than ToG. The ToG enables the exploration of new reasoning paths to reach the correct an- swer, which represents significant application of knowledge graph reasoning. However, the answer to the current question in the KB, is "Bright House Field", which is incorrect since "Philadelphia Phillies" training stadium is "Spectrum Field" now. This example exemplifies constraint of ToG, specifically its dependence on the correctness of the KB, where the incorrect KB has negative impact on ToG's reasoning accuracy. However, depicted in Figure ToG presents novel framework construct automated knowledge infusion to the KG.
Team extra.training - (retrievable from the SPARQL), which is
Question
Who influenced Arthur Miller that was influenced by Lucian?
Reasoning
Arthur Miller + influuence.nsluence _oceeee__oeeeeee htw.en..od......eeeeeee influenced__y + William Shake- speare influence.influence www...inllleeneeeeccc.e by Lucian. (Path 1, Score: 0.75)
Paths
Lucian infftercceinffuenne www.s/ienneoooeeeiinnnooeooo node.inffuenced. by Socrates + infuu ence.influence_eee iroode.iflueecced_by - Parmenides. (Path 2, Score: 0.2)
Arthur Miller + people.person. education
perssontttonn - UnName Entity + educa- tion. con.education..sii - Arthur Miller. (Path 3, Score: 0.05)
Outputs
10: Edmund Wilson.
CoT: Arthur Miller was influenced by the playwright and director Thornton Wilder, who in turn was influenced by Lucian of Samosata.
New Bing: I'm not sure about Lucian's influence Arthur Miller. However, Arthur Miller was influenced by Henrik Ibsen and Eugene O'Neill. He was also influenced by the events of the McCarthy
and the Salem witch trials.
ToG: Based on given knowledge triples, we can infer that Arthur Miller was influenced by William Shakespeare, who was directly influenced by Lucian
Ground Truth
William Shakespeare.
Table 19: Case for ToG. The wrong answers are highlighted with red color, and the correct answers are highlighted with blue color.
Question
What is the state where the team whose fight song is "Renegade" is from?
Reasoning
Renegade + sports.fight_st http:lfgghhsoooppossssssss - Pittsburgh Steelers. (Path 1, Score: 0.67)
Paths
Renegade sports.sports teapoottstemfiighr__oo UnName UntttmeEEtity. (Path Score: 0.33)
Outputs
10: Florida.
CoT: The team whose fight song is "Renegade" is the Florida State Seminoles, and they are from the state of Florida in the United States.
New Bing: The team whose fight song "Renegade" is the Florida State Seminoles. They are from the state of Florida in the United States.
ToG: Based on the given knowledge triples, the team with the fight song "Renegade" is the Pittsburgh Steelers. The Pittsburgh Steelers are professional American football team, and they are from the state of Pennsylvania.
Ground Truth
Pittsburgh Pennsylvania.
Table 20: Case for ToG. The wrong answers are highlighted with red color, and the correct answers are highlighted with blue color.
26

---

Published as a conference paper at ICLR 2024
Question
What state is the college that Sampson Salter Blowers is grad student of located?
Reasoning Paths
Sampson Salter Blowers A dilicaaion.eduucation.sue
+ educa-
wwd.uution.issiiutiiii. (Harvard College). (Path 1, Score: 0.75)
Sampson Salter Blowers inlicattio.educattion tion.
educa-
+ {}. (Path 2, Score:
0.2)
Sampson Salter Blowers -
education. inlecationeducattio.. education.studen. peo-
ple.person.education - (). (Path 3, Score: 0.05)
Outputs
10: Unknown.
CoT: I'm sorry, but I do not have enough information to answer your question. Can you please provide more context details about Sampson Salter Blowers and the college he attended?
I'm sorry but I couldn't 't find any information about Sampson Salter Blowers being grad student. However, he was a noted North American lawyer, Lovalist and jurist from Nova Scotia who graduated from Harvard College with ba in 1763 and an ma in 1765. He was admitted as an attorney in the Suffolk Inferior Court 1766.
New Bing:
ToG: Based on the given relations chains, Sampson Salter Blowers is a grad student of Harvard College. Therefore, the answer to the question is Harvard College, which is located in Massachusetts.
Ground Truth
Massachusetts.
Table 21: Case for ToG-R. "Unknown" denotes LLM is unable to generate a valid response. The wrong answers are highlighted with red color, and the correct answers are highlighted with blue color.
Question
What is mascot Phillie Phanatic's 's team's spring training stadium?
Reasoning
Phillie Phanatic - sports.sports_cett tearttttttamttaanaa trscttaammmmccoottttt -> Philadelphia Phillies +
wttp:/aeeeaaaaaaaeeeeaeeee sstddium - Bright House Field. (Path 1, Score: 0.8)
Paths
Phillie Phanatic + spoorts.sportsstiii.. petppootsseetttteeeeeeeeee teeam.teammmasteeeee - Philadelphia Phillies 4 ports.sports team__eam____ location.teams Philadelphia. (Path 2, Score: 0.15)
team.team iaaeamaamaatrrraaaaaaaaaaaaaaaas mascor - Philadelphia Phillies Phillie Phanatic + sports.sports taappoortstttmttaaam
spports.pports_eece
+ Phillie Phanatic. (Path 3, Score: 0.05)
Outputs
10: Spectrum Field.
First, the mascot Phillie Phanatic represents the Philadelphia Phillies baseball team. Second, the Philadelphia Phillies' spring training stadium is located in Clearwater, Florida and is known as Spectrum Field. The answer is Spectrum Field.
CoT:
New Bing:
The Philadelphia Phillies' spring training stadium is called BayCare Ballpark.
ToG:
The spring training stadium for Phillie Phanatic's team, the Philadelphia Phillies, is Bright House Field.
Ground Truth
Bright House Field (KB), Spectrum Field (Actual).
Table 22: Case for ToG. The wrong answers are highlighted with red color, and the correct answers are highlighted with blue color.
27

---

Published as a conference paper at ICLR 2024
E SPARQL AND PROMPTS
In this section, we show all the prompts that need to be used in the main experiments. First, pre-define SPARQL for Freebase queries, which can executed by simply filling in the appropriate mid and relation. For Wikidata, abstain from employing executable SPARQL, rather we directly engage in querying through nine pre-defined service APIs.
E.1 PRE-DEFINED SPARQL
E.1.1 RELATION SEARCH
PREFIX ns:
SELECT ?relation
WHERE
ns:mid Prelation ?x
PREPIX ns: <http:// freebase com/ns/>
SELECT ?relation
WHERE {
?x ?relation ns:mid.
E.1.2 ENTITY SEARCH
PREFIX ns: http://ddd...eebbeee.co////////
SELECT 2tailEntity
WHERE {
ns:mid nstrelation ?tailEntity
PREFIX no: <http://rdf... http:://tf.trrbbeeeec.o
SELECT PtailEntity
WHERE {
EtailEntity ns:mid ns:relation
E.1.3 CONVERT MID TO LABEL
PREFIX ns: <http://rdf. httt:::/rd..frccbaacccoo freebase.com/nss
SELECT DISTINCT ?tailEntity WHERE
?entity cestype.object. name ?tailEntity (IInt((eentie ns:mid)
UNION
Pentity htctp://wwwww..org/ http://wwww..o////0/////////aaa/ ?tailEntity FILTER (Pentity ns:mid)
E.2 PRE-DEFINED APIS
28

---

head_qid: str, Published as a conference paper at ICLR 2024
def label2gid(selš, label: str)
def label2pid(self, label: str) >> str:
def pid2label (self, pid: str) >> str!
def gid21abel (self, qid: str) -> str:
def ret_all_relation of ann_entttyyyite (seit, entity gid: str)
-> tpt,ict tp.iist|:
def relation_pid: str)
-> tp. tp.
def get_ taaitaallles_eetaeeeee head and relation (self, head_ str, relation_pid: str) >> tp.List
def get_external_idgiiee aeaedaddeaieeeeaaaaaaaddddd relation_pid: str) tp.
(self, head str,
def mid2qid (self, mid: str) -> str:
E.3 TOG
E.3.1 RELATION PRUNE
Please retrieve À relations (separated by semicolon) that contribute to the question and rate their contribution on scale from to 1 (the sum of the scores of & relations is 1).
In-Context Few-shot
Q: [Query)
Topic Entity: (TTppc Entity)
Relations:
(list of relations)
A:
E.3.2 ENTITY PRUNE
Please the entities' contribution the question scale from 0 (the of the scores of all entities is 1).
In-Context Few-shot
Q: [Query)
Relation: (Current Relation]
Entites:
(list of entities)
Score:
E.3.3 REASONING
Given question and the associated retrieved knowledge graph triples (entity, relation, entity), you asked answer whether it's sufficient for you answer the question with these triples and your knowledge (Yes or No).
In In-Context Few-shot
Q: (Query)
Knowledge triples: (Explored Paths)
29

---

Published as a conference paper at ICLR 2024
A:
E.3.4 GENERATE
Given question and the associated retrieved knowledge graph triples (entity, relation, entity), you are asked to answer the question with these triples and your own knowledge.
In In-Context Few-shot
Q: (Query)
Knowledge triples: (Explored Paths)
A:
E.4 ToG-R
E.4.1 REASONING
Please answer the question using Topic Entity, Relations Chains and their Candidate Entities that contribute to the question, you asked to answer whether it's sufficient for you to answer the question with these triples and your knowledge (Yes or No).
In-Context Few-shot
Q: [Query)
Topic Entity, with relations chains, and their candidate entities: [Explored Relation Chains)
A:
E.5 COT AND IO
E.5.1
COT PROMPT
Q: What state is home the university that is represented in sports by George Washington Colonials men's basketball?
A: First, the education institution has sports named George Washington Colonials men's 's bas- ketball in is George Washington University, Second, George Washington University is in Washington D.C. The answer is Washington, D.C.
Q: Who lists Pramatha Chaudhuri as an influence and wrote Jana Gana Mana?
A: First, Bharoto Bhagyo Bidhata wrote Jana Gana Mana. Second, Bharoto Bhagyo Bidhata lists Pramatha Chaudhuri as an influence. The answer is Bharoto Bhagyo Bidhata.
Q: Who was the artist nominated for an award for You Drive Me Crazy?
A: First, the artist nominated for an award for You Drive Me Crazy is Britney Spears. The answer is Jason Allen Alexander.
Q: What person born Siegen influenced the work of Vincent Van Gogh?
A: First, Peter Paul Rubens, Claude Monet and etc. influenced the work of Vincent Van Gogh. Second, Peter Paul Rubens born in Siegen. The answer is Peter Paul Rubens.
Q: What is the country close Russia where Mikheil Saakashvii holds government position?
A: First, China, Norway, Finland, Fstonia and Georgia is close to Russia. Second, Mikheil Saakashvii holds government position at Georgia. The answer is Georgia.
Q: What drug did the actor who portrayed the character Urethane Wheels Guy overdosed on?
A: First, Mitchell Lee Hedberg portrayed character Urethane Wheels Guy. Second, Mitchell Lee Hedberg overdose Heroin. The answer is Heroin.
Q: (Query)
30

---

Published as a conference paper at ICLR 2024
A:
E.5.2 I0 PROMPT
Q: What state is home to the university that is represented in sports by George Washington Colonials men's basketball?
A: Washington, D.C.
Q: Who lists Pramatha Chaudhuri as an influence and wrote Jana Gana Mana?
A: Bharoto Bhagyo Bidhata.
Q: Who was the artist nominated for an award for You Drive Me Crazy?
A: Jason Allen Alexander.
Q: What person born in Siegen influenced the work of Vincent Van Gogh?
A: Peter Paul Rubens.
Q: What is the country close Russia where Mikheil Saakashvii holds government position?
A: Georgia.
Q: What drug did the actor who portrayed the character Urethane Wheels Guy overdosed on?
A: Heroin.
Q: (Query)
A:
31


Reviews:
[{"review_id": "1nkAf1hlOy", "reviewer": "Reviewer_nifq", "summary": "This work aims at improving the integration of knowledge graphs (KGs) in LLMs. The authors propose a method called Think-on-Graph (ToG) that performs beam-search on knowledge graphs, keeping track and exploring reasoning paths. Specifically, they use a \"search\" operation backed by the KG and a \"prune\" operation backed by the LLM. Through the experiments on benchmarks of KBQA/open QA/etc, the authors find an advantage of ToG in several of them compared to prior work. They also perform analyses on the effect of individual components of ToG like the selection of KG, search depth, pruning method, etc.", "questions": "Please see the weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes an intuitive and novel method in LLM-KG integration. The experiments are performed on a variety of datasets. The performance of the method is overall positive. The analyses on each component of the method is extensive. The writing of the paper is overall clear.", "weaknesses": "The reliance on very strong (production-level) LLMs and the choice of baselines. The authors explored the use of Llama-2-chat (70b), ChatGPT, and GPT-4 as the LLM in the ToG method. From Table 1 and Table 2, it seems that the strength of the LLM is essential to the method (Llama worse than ChatGPT, ChatGPT much worse than GPT-4). And the performance advantage on 6 out of 9 benchmarks is only observed with GPT-4. Additionally, though the authors show GPT-4 benefits from ToG compared to non-KG prompting (e.g., CoT), stronger prompting methods targeting for compositionality may be investigated, for example, self-ask [1]. Web search and vanilla retrieval augmentation methods can also be investigated [2].\n\nEfficiency of the method. The process of beam search and pruning with LLMs can be costly. An extensive comparison on decoding time and cost across all methods should be performed and discussed. \n\n[1] Press et al. 2022. Measuring and Narrowing the Compositionality Gap in Language Models. https://arxiv.org/abs/2210.03350\n[2] Kasai et al. 2022. RealTime QA: What's the Answer Right Now? https://arxiv.org/abs/2207.13332", "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": "dZ5muK4j3x", "reviewer": "Reviewer_ezze", "summary": "The paper proposes ToG (Think-on-Graph) for deep, responsible, and efficient LLM reasoning with knowledge graphs with a new paradigm of \"LLM×KG.\" The ToG is with the searching and pruning procedures to conduct deep reasoning. Empirical results on five KBQA datasets with extensive experiments justify the effectiveness of the proposed ToG method.", "questions": "What is the running-time efficiency of ToG?\n\nHow do the KGs used in the experiment part solve the limitation of out-of-date knowledge?\n\nThe beam search with pruning adopted by ToG is quite relevant to the progressive reasoning methods equipped with learnable search and pruning mechanisms, which also come from the KG areas (e.g., AdaProp [1] and Astarnet [2]). I would suggest the paper have a discussion with these relevant works. In addition, is it possible to achieve a kind of learnable pruning as an enhancement of ToG?\n\n[1] Zhang et al. AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning. KDD 2023.\n\n[2] Zhu et al. A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs. NeurIPS 2023.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is rather solid and detailed from a technical perspective.\n\nThe figures are clear and easy to understand.\n\nThe solution of LLM×KG is reasonable and new to the LLM community.\n\nThe depth and width of Toc are clearly investigated in the ablation study.\n\nThe limitations of the proposed method are extensively discussed in Appendix A.\n\nSeveral technical details, case studies, and evaluation results are also elaborated on in the Appendix.", "weaknesses": "The writing of the paper can be largely improved. \n\nBesides, the mathematical notations and equations can be improved to be clearer.\n \nIt would be better to summarize the frequently used notations in one table or sentence.\n\nThe empirical performance of ToG is not consistently the best, which is outperformed by the \"prior finetune SOTA\" in some cases of Tab. 1. Although not requiring training is a major benefit of ToG, its reasoning power is not fully convincing enough. I would suggest the paper make a further discussion and explanation for that.\n\nBesides, the important baseline, \"Prior Prompting SOTA\" in Tab.1, is not sufficiently evaluated and compared. It would be much better and more convincing to fill in the blanks in Tab.1. \n\nThe paper mentions the hallucination problem many times and uses it as the motivation of ToG. However, the hallucination problem is not sufficiently studied. As far as I can see, there is only one preliminary analysis of error is provided in Appendix D.2.\n\nThe paper is empirically driven and lacks in-depth analysis, whether from methodological or theoretical perspectives.", "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": "WJZA3ZPYzn", "reviewer": "Reviewer_K4jf", "summary": "This paper presents a novel approach called Think-on-Graph (ToG) to synergize the LLMs and KGs for reasoning. ToG enables LLMs as agents to iteratively execute searches on KGs to discover promising reasoning paths, which are then used to guide the LLMs to generate accurate answers. ToG is a general framework that can be applied to various LLMs and KGs. Extensive experiments on several datasets show that ToG can significantly improve the reasoning performance of LLMs.", "questions": "1. Can the authors discuss the cost of ToG in detail? What is the average number of calls for the reasoning? What is the overall price for the ChatGPT/GPT-4 API calls?\n\n2. Can the authors explain the inconsistency I discussed above and present a clear illustration of the whole reasoning process?\n\n3. Can the authors explain how ToG can generalize to different KGs? How LLMs in ToG understand the meaning of relations in different KGs without additional training?\n\n4. Can other search algorithms be used for ToG? For example, depth-first search, breadth-first search, A* search, etc.\n\n5. Can ToG be used to solve complex reasoning problems that cannot be solved by path-based reasoning? For example, in GrailQA, there are questions like: \"How many TV programs has Bob Boyett created?\". This question needs to count the KG structures to get the answer. Besides, there are other complex questions requiring intersection, union, and negation operations. Can ToG be used to solve these kinds of questions? Maybe a limitations section can be added to the paper.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-presented and easy to follow. The authors provide a clear motivation and a good introduction to the problem.\n\n2. The proposed framework can be easily plugged into existing LLMs and KGs without incurring additional training costs.\n\n3. Extensive experiments on several datasets show that ToG can significantly improve the reasoning performance of LLMs.", "weaknesses": "1. The computational cost of ToG is relatively high. The searching process of ToG involves multiple LLM calls, which may be costly and limit its practical applicability in some settings. \n\n2. Some details are inconsistent in the paper. For example, in the approach introduction section, ToG selects the next step triples/relations based on current expended reasoning paths. However, in the prompt illustrated in G.3, I cannot find the current reasoning paths used for the pruning process.\n\n3. I have concerns that ToG might not understand the meaning of relations well and generalize to different KGs. The relations defined in KGs are usually in diverse formats. For example, the relations in Freebase are defined in a hierarchical format, while the relations in Yago have clearer semantics. If the relations do not reveal the clear semantics, the searching process of ToG might be misled.", "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": "YYoD5qEUdD", "reviewer": "Reviewer_LtPr", "summary": "This paper presents an LLM-KG integration paradigm to incorporate structural knowledge stored in KGs in LLMs reasoning, namely Think-on-Graph (ToG). ToG makes LLM serve as an agent to walk on KGs by iteratively searching and pruning relations and entities from KGs. Experiments show that ToG could enhance the LLM’s reasoning capabilities and achieve SOTA on 6 datasets. ToG also exhibits knowledge traceability and correctability to improve KG quality.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. Good written paper, very easy to read.\n2. Strong experimental performance, achieving SOTA on 6 datasets without training.\n3. The motivation is strong and clear, incorporating external knowledge (KGs) would be an important problem to enhance LLMs.", "weaknesses": "1. I believe it would be interesting to see the ToG performance when encountering the knowledge conflict between external KG knowledge and parametric knowledge stored in LLMs, which is an aspect to test the robustness of ToG.\n2. I am concerned that ToG would bring too many intermediate steps and cause high latency in reasoning and expensive deployment, especially when using API-based black-box models like GPT-4.\n3. It would be interesting to see the performance of ToG when incorporating the KGs of low quality (sparsity, noisy, etc), since most KGs are sparse and out of date to some extent. So investigating the impact of KG quality would enhance the understanding of ToG method and its limitations. \n4. I would encourage authors to present experiment results on small LLMs, such as 7B and 13B.", "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)