Learning to Plan for Retrieval-Augmented Large Language Models from Knowledge Graphs (2024)

1 Introduction

The past few years have witnessed significant innovations in LLMs Ouyang etal. (2022); Touvron etal. (2023); Chowdhery etal. (2023); AI@Meta (2024). While LLMs excel in many natural language processing tasks, they still face challenges, particularly the smaller models, in handling complex question-answering (QA) tasks Press etal. (2023); Shao etal. (2023); Yao etal. (2022); Xiong etal. (2024a); Huang etal. (2024).

To improve the performance of LLMs on complex QA tasks, past research has tried various methods: (1) Employing carefully designed prompt strategies to guide the model in reasoning, such as Chain of Thought (CoT) Kojima etal. (2022); Wei etal. (2022) and Tree of Thought (ToT) Yao etal. (2024) methods; (2) Utilizing retrieval techniques to obtain supplemental information from external knowledge source Lewis etal. (2020); Guu etal. (2020); (3) Combining prompt strategies with retrieval enhancements, as exemplified by methods like ReAct Yao etal. (2022) and Self-Ask Press etal. (2023).The third approach has garnered widespread research interest due to its integration of the advantages of the first two methods.The fundamental idea of this class of methods is to guide LLMs in breaking down a complex question into multiple simpler sub-questions and then use a retrieval-augmented generation (RAG)Huang etal. (2023, 2024) method to answer each sub-question, thereby deducing the answer to the original complex question. However, planning for complex questions is non-trivial, especially for smaller LLMs (with fewer than 10 billion parameters), which often require supervised fine-tuning Aksitov etal. (2023); Chen etal. (2023a); Qin etal. (2023).

This raises a widely concerning issue: how to obtain supervised data for learning the planning ability on complex questions. Manual annotation is time-consuming and labor-intensive, making it difficult to scale.Most existing methods attempt to distill knowledge from teacher LLMs Yao etal. (2022); Aksitov etal. (2023), which places excessive trust in the teacher LLMs and, in reality, cannot guarantee the accuracy of the distilled knowledge. These challenges inspire us to explore new ways of obtaining supervised planning data.

Knowledge Graphs (KGs)Pan etal. (2017b, a) usually store accurate knowledge in a structured way.We find that a KG pattern can be viewed as the abstract of a complex question, as shown in Figure 1, which reveals the connection between question planning and patterns.This opens up the possibility of constructing training data to enhance the planning capabilities of LLMs using KGs.Specifically, we start by grounding predefined patterns in an open-domain KG to extract numerous instances, which we then verbalize into complex questions and corresponding sub-questions in natural language. In this way, we effectively create a large number of accurate planning data for fine-tuning.Being fine-tuned with these planning data,LLMs’ capability of generating plans for complex questions is enhanced, resulting in better final answers by parsing and executing these plans.We refer to this innovative framework as Learning to Plan from Knowledge Graphs (LPKG).

Additionally, we construct a Comprehensive Logical QA benchmark, CLQA-Wiki, from a subset of Wikidata Vrandecic and Krötzsch (2014) via grounding rich patterns as aforementioned.Existing complex QA benchmarks Yang etal. (2018); Ho etal. (2020); Press etal. (2023); Trivedi etal. (2022)primarily focus on multi-hop and comparison-type questions and lack logical operations. Furthermore, most questions are labeled with only one answer, whereas in reality, they often have multiple correct answers.The CLQA-Wiki benchmark evenly covers multi-hop, comparison, intersection, and union types of questions,which is more comprehensive and challenging for complex QA evaluation.

Our contributions can be summarized as follows:(1) We introduce a novel framework LPKG that enhances the planning ability of LLMs using data constructed from KG patterns;(2) We develop a comprehensive and challenging evaluation benchmark, named CLQA-Wiki, to more effectively assess the performance of LLMs on complex QA tasks;(3) Our proposed framework LPKG achieves better results than popular baselines on multiple conventional complex QA benchmarks, and we verify the effectiveness of the introduction of KG-sourced planning data.

2 Related Works

3 Method

3.2 Construction of Planning Data

Basic KG Patterns.

Inspired by previous work on complex logic queries within KGs Ren and Leskovec (2020), we define the basic KG patterns as shown in Figure 3. The set of KG patterns is denoted as $\mathcal{P}=\{1p,2p,3p,2i,3i,2u,ip,pi,compare\}$.Specifically, $p,i,u$ respectively indicate projection, intersection, and union. 1$p$, 2$p$, and 3$p$ represent queries that span from one to three hops, 2$i$ and 3$i$ respectively represent the intersection of two sub-queries and three sub-queries, 2$u$ represents the union of two sub-queries, and $ip$ and $pi$ represent complex queries that combine two-hop with intersection logic. In addition, we also combine pairs of triples that have numeric tail entities and the same relations to construct comparison patterns, denoted as $compare$.

Grounding.

Given a KG, we first ground these patterns in it to extract instances:

$$\mathcal{I}_{pat}=f_{pat}(\mathcal{KG}),pat\in\mathcal{P}$$

(1)

where $\mathcal{I}_{pat}$ are the instances grounded by knowledge graph $\mathcal{KG}$ of pattern $pat$, ${f_{pat}}$ is the corresponding extraction function. For example, an instance of the $2p$ pattern can be “(Inkheart, (cast member, educated at))”.To best meet the needs of open-domain QA, we use Wikidata15k Chen etal. (2023b), a subset of the open-domain KG Wikidata, as $\mathcal{KG}$.

Verbalization.

Subsequently, based on the grounded instances, we need to verbalize them bottom-up into sub-questions and assemble them into complex questions. There are several methods for this step, such as a templates-based method, manual annotation, or utilizing an LLM. Since the template-based approach often lacks fluency in language expression, and the manual method is time-consuming and labor-intensive, we opt for an LLM-based method. Specifically, we write a small number of verbalization examples for each pattern type. These examples are used as demonstrations $De_{1}$ to fill in the prompt. Finally, we concatenate a grounded instance $i\in\mathcal{I}_{pat}$ to the prompt, asking an LLM to verbalize it to a natural language question:

$$\{\{Q_{s_{n}}\}_{n=1}^{k},Q_{c}\}=llm(concat(De_{1},i))$$

(2)

where $\{Q_{s_{n}}\}_{n=1}^{k}\text{ and }Q_{c}$ represent the resulting sub-questions and complex question respectively, $concat$ is string level concatenation. We use GPT-4 as $llm$ here. It is important to note that here the $llm$’s role is merely to transform the data format; the sub-questions and complex question still originate from the structure of the KG itself, without introducing any knowledge from the $llm$ in the task of question planning. The prompt we use can be found in Appendix C.1.

Filling.

We then extract sub-questions and complex questions from the output of the $llm$. Subsequently, we built a set of planning templates $\mathcal{T}_{pat}$ for the planning process of questions corresponding to each pattern. The $\{Q_{s_{n}}\}_{n=1}^{k}$ obtained in the previous step will be filled into fixed positions in $\mathcal{T}_{pat}$ corresponding to their pattern type, thereby obtaining the output for training. The $Q_{c}$ obtained in the previous step is concatenated to the end of a fixed instruction $Ins$ and some planning demonstrations $De_{2}$ (also constructed from KGs), thus obtaining the input for training data:

$$x=concat(Ins,De_{2},Q_{c})$$

(3)

$$y=\mathcal{T}_{pat}.fill(\{Q_{s}\}_{n=1}^{k}),pat\in\mathcal{P}$$

(4)

where $.fill$ is a filling function of templates $\mathcal{T}_{pat}$. Inspired by Aksitov etal. (2023), we use a code-formatted input $x\text{ and output }y$ here (shown in “Input” and “Output” in Figure 2) to facilitate formatting and subsequent parsing and execution of the output plan (more details in Appendix C.2).In the end, we obtain 9000 training data entries $\mathcal{D}_{train}=\{x_{n},y_{n}\}_{n=1}^{9000}$, with 1000 entries for each pattern. We randomly select 100 items from the training sets for manual verification, with an accuracy rate of over 95%.

4 New BenchMark: CLQA-Wiki

The conventional complex QA datasets include HotPotQA Yang etal. (2018), 2WikiMultiopQA Ho etal. (2020), MuSiQue Trivedi etal. (2022), and Bamboogle Press etal. (2023). Despite their widespread use in evaluating the QA performance of language models, we identify some problems with these datasets:

(1) All these datasets are primarily focused on multi-hop and comparison-type questions. The types of questions are not balanced and comprehensive enough, and less attention is paid to questions involving intersection and union logic, which are also very common in reality.

(2) Except for MuSiQue, the questions on the rest of the other three datasets only have one answer, whereas many questions in reality often have multiple answers. For example, the answer to an intersection question “Which country borders with Russia and China at the same time?” is a set [Mongolia, Kazakhstan, North Korea].

In light of this, we aim to construct a new testing benchmark that embodies more comprehensive logic and allows for an unrestricted number of answers to more thoroughly evaluate the performance of language models on various logical questions. Considering the detailed pattern structures and unrestricted number of answer entities in KGs, we construct a test set based on Wikidata15k.

Similar to the method used to construct the planning data, we extract instances from Wikidata15k (which do not appear in the training data) and use GPT-4 to do verbalization. Moreover, for each instance, we can obtain all the answer entities from Wikidata15k, which we then designate as the answers to the questions. After manual quality checks, we obtain a test set called CLQA-Wiki, which contains 1,200 pieces of data featuring a variety of Comprehensive Logical QA pairs. The question types and their distribution are listed in Table 1. It is worth noting that we have constructed 9 types of testing questions until now, and for newly defined patterns, we can also quickly construct corresponding questions using the above method, showing the better scalability of our dataset.

5 Experiment

We aim to answer the following research questions in our experiments:

$\bullet$ RQ1: Can LPKG outperform baseline methods on conventional complex QA datasets?

$\bullet$ RQ2: Can planning data derived from KGs help improve the planning ability of the LLMs?

$\bullet$ RQ3: Can planning data derived from KGs be more helpful in improving the LLMs’ planning ability compared to normal distillation methods?

$\bullet$ RQ4: Can LPKG outperform baseline methods on the new benchmark CLQA-Wiki?

5.3 Results on CLQA-Wiki (RQ4)

Main Results

	CLQA-Wiki
	Precision	Recall
CoT	0.0605(+80.6%)	0.0641(+103.4%)
Direct RAG	0.0814(+34.2%)	0.0789(+65.3%)
ReAct	0.0264(+314.0%)	0.0270(+382.9%)
Self-Ask	0.0385(+183.8%)	0.0423(+208.2%)
ICLPKG(GPT-3.5)	0.0907(+20.5%)	0.1014(+28.6%)
LPKG(Llama3)	0.1112	0.1344

We then conduct testing based on the CLQA-Wiki benchmark. Given that answers in this benchmark may have multiple candidates, we adjust the instructions for QA LLMs to require them to output all potential answers in a specified list format. This adjustment is made to facilitate the extraction and evaluation of the responses. Since Llama3-8B-Instruct is more powerful than CodeQwen1.5-7B-Chat as shown in Table 2, we only conduct LPKG with Llama3 here.Experimental results are presented in Table 6. It can be seen that CLQA-Wiki is a very challenging dataset, but LPKG(Llama3) still outperforms the baseline methods. At the same time, compared to ICLPKG(GPT-3.5), LPKG(Llama3) has an average improvement of over 20%, highlighting the importance of using KG-sourced planning data.

In addition, we conduct more fine-grained experiments based on the type of questions, and the experimental results are shown in Figure 4. We found that LPKG(Llama3) performs more prominently on some complex questions, such as the 3$p$, 2$i$, and 2$u$ questions, demonstrating the advantages of our framework in dealing with complex logic questions. At the same time, we also found that direct retrieval performs well on some types of questions, such as 3$i$ and compare questions. This may be due to the fact that in the process of verbalizing these questions, the assembly of sub-questions into complex questions is relatively straightforward, allowing answers to each sub-questions to be obtained directly through the retrieval of complex questions or the knowledge of the LLM itself.

Case Study

To more intuitively demonstrate the effectiveness of KG-source planning data, we conduct a case study on CLQA-Wiki, detailed in Figure 5 in Appendix A. When planning a 2$i$ question “What sport is associated with John Madden and Ben Johnson?”, GPT-3.5 generates some meaningless sub-questions and incorrectly defines the question type, which will definitely lead to incorrect answers. But LPKG(Llama3) could identify it as a 2$i$ question and provide the correct sub-questions and planning steps, thereby helping to obtain the correct answer during final parsing and execution.

6 Conclusion

In this paper, we try to enhance the planning ability in retrieval-augmented LLMs using KGs. Specifically, we design a framework for Learning to Plan from KG (LPKG). The proposed LPKG framework first utilizes the rich patterns in the KGs to construct planning data, then fine-tune planning LLMs based on such data to enable them to conduct planning on downstream datasets, and ultimately get the final answer through parsing and execution. The experimental results reveal the excellent performance of the LPKG framework and also demonstrate the effectiveness of using KG-sourced data to enhance LLMs’ planning ability. Finally, we construct CLQA-Wiki, providing a more challenging complex QA benchmark for the community.

Limitation

In our view, the limitations of our work at the current stage mainly stem from two aspects:

(1) During the fine-tuning phase of planning LLMs, we simply mixed various types of questions together uniformly for training. We have not yet explored the impact of question type distribution on the experimental results, which could be the focus of future work.

(2) At present, the datasets we test have explicit types of questions (multi-hop, comparison, and union/intersection), but in reality, some question types may be implicit or even not be included in the types we define. The future direction of our work can be to study planning methods for these types of unclear questions.

Acknowledgement

This work is founded by National Natural Science Foundation of China (NSFC62306276/NSFCU23B2055/NSFCU19B2027), Zhejiang Provincial Natural Science Foundation of China (No. LQ23F020017), Yongjiang Talent Introduction Programme (2022A-238-G), Chang Jiang Scholars Program (J2019032), Fundamental Research Funds for the Central Universities (226-2023-00138).

References

• AI@Meta (2024)AI@Meta. 2024.Llama 3 model card.
• Aksitov etal. (2023)Renat Aksitov, Sobhan Miryoosefi, Zonglin Li, Daliang Li, Sheila Babayan, Kavya Kopparapu, Zachary Fisher, Ruiqi Guo, Sushant Prakash, Pranesh Srinivasan, etal. 2023.Rest meets react: Self-improvement for multi-step reasoning llm agent.arXiv preprint arXiv:2312.10003.
• Arakelyan etal. (2021)Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. 2021.Complex query answering with neural link predictors.In ICLR. OpenReview.net.
• Asai etal. (2023)Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. 2023.Self-rag: Learning to retrieve, generate, and critique through self-reflection.CoRR, abs/2310.11511.
• Chan etal. (2024)Chi-Min Chan, Chunpu Xu, Ruibin Yuan, Hongyin Luo, Wei Xue, Yike Guo, and Jie Fu. 2024.RQ-RAG: learning to refine queries for retrieval augmented generation.CoRR, abs/2404.00610.
• Chen etal. (2023a)Baian Chen, Chang Shu, Ehsan Shareghi, Nigel Collier, Karthik Narasimhan, and Shunyu Yao. 2023a.Fireact: Toward language agent fine-tuning.arXiv preprint arXiv:2310.05915.
• Chen etal. (2023b)Xiang Chen, Duanzheng Song, Honghao Gui, Chengxi Wang, Ningyu Zhang, Jiang Yong, Fei Huang, Chengfei Lv, Dan Zhang, and Huajun Chen. 2023b.Factchd: Benchmarking fact-conflicting hallucination detection.CoRR, abs/2310.12086.
• Chen etal. (2022)Xuelu Chen, Ziniu Hu, and Yizhou Sun. 2022.Fuzzy logic based logical query answering on knowledge graphs.In AAAI, pages 3939–3948. AAAI Press.
• Chowdhery etal. (2023)Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, HyungWon Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, YiTay, 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 Levskaya, 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, AndrewM. Dai, ThanumalayanSankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel.2023.Palm: Scaling language modeling with pathways.J. Mach. Learn. Res., 24:240:1–240:113.
• Feng etal. (2023)Zhangyin Feng, Xiaocheng Feng, Dezhi Zhao, Maojin Yang, and Bing Qin. 2023.Retrieval-generation synergy augmented large language models.volume abs/2310.05149.
• Gao etal. (2023)Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, YiDai, Jiawei Sun, Qianyu Guo, Meng Wang, and Haofen Wang. 2023.Retrieval-augmented generation for large language models: A survey.CoRR, abs/2312.10997.
• Guu etal. (2020)Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang. 2020.Retrieval augmented language model pre-training.In ICML, volume 119 of Proceedings of Machine Learning Research, pages 3929–3938. PMLR.
• Hamilton etal. (2018)WilliamL. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. 2018.Embedding logical queries on knowledge graphs.In NeurIPS, pages 2030–2041.
• Hao etal. (2023)Shibo Hao, YiGu, Haodi Ma, JoshuaJiahua Hong, Zhen Wang, DaisyZhe Wang, and Zhiting Hu. 2023.Reasoning with language model is planning with world model.In EMNLP, pages 8154–8173. Association for Computational Linguistics.
• Ho etal. (2020)Xanh Ho, Anh-KhoaDuong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020.Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps.arXiv preprint arXiv:2011.01060.
• Huang etal. (2023)Wenyu Huang, Mirella Lapata, Pavlos Vougiouklis, Nikos Papasarantopoulos, and JeffZ. Pan. 2023.Retrieval augmented generation with rich answer encoding.In Proceedings of the 13th International Joint Conference on Natural Language Processing and the 3rd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics, pages 1012–1025.
• Huang etal. (2024)Wenyu Huang, Guancheng Zhou, Hongru Wang, Pavlos Vougiouklis, Mirella Lapata1, and JeffZ. Pan. 2024.Less is More: Making Smaller Language Models Competent Subgraph Retrievers for Multi-hop KGQA.In Proc. of Empirical Methods in Natural Language Processing (EMNLP 2024).
• Khot etal. (2023)Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. 2023.Decomposed prompting: A modular approach for solving complex tasks.In ICLR. OpenReview.net.
• Kojima etal. (2022)Takeshi Kojima, ShixiangShane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.Large language models are zero-shot reasoners.Advances in neural information processing systems, 35:22199–22213.
• Lewis etal. (2020)Patrick S.H. 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. 2020.Retrieval-augmented generation for knowledge-intensive NLP tasks.In NeurIPS.
• Li etal. (2024)Xingxuan Li, Ruochen Zhao, YewKen Chia, Bosheng Ding, Shafiq Joty, Soujanya Poria, and Lidong Bing. 2024.Chain-of-knowledge: Grounding large language models via dynamic knowledge adapting over heterogeneous sources.In The Twelfth International Conference on Learning Representations.
• Lin etal. (2023)XiVictoria Lin, Xilun Chen, Mingda Chen, Weijia Shi, Maria Lomeli, Rich James, Pedro Rodriguez, Jacob Kahn, Gergely Szilvasy, Mike Lewis, Luke Zettlemoyer, and Scott Yih. 2023.RA-DIT: retrieval-augmented dual instruction tuning.CoRR, abs/2310.01352.
• Luo etal. (2023)Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. 2023.Reasoning on graphs: Faithful and interpretable large language model reasoning.CoRR, abs/2310.01061.
• Mialon etal. (2023)Grégoire Mialon, Roberto Dessì, Maria Lomeli, Christoforos Nalmpantis, Ramakanth Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi-Yu, Asli Celikyilmaz, Edouard Grave, Yann LeCun, and Thomas Scialom. 2023.Augmented language models: a survey.CoRR, abs/2302.07842.
• Ouyang etal. (2022)Long Ouyang, Jeffrey Wu, XuJiang, Diogo Almeida, CarrollL. 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, PaulF. Christiano, Jan Leike, and Ryan Lowe. 2022.Training language models to follow instructions with human feedback.In NeurIPS.
• Pan etal. (2023)JeffZ. Pan, Simon Razniewski, Jan-Christoph Kalo, Sneha Singhania, Jiaoyan Chen, Stefan Dietze, Hajira Jabeen, Janna Omeliyanenko, Wen Zhang, Matteo Lissandrini, ussa Biswas, Gerard deMelo, Angela Bonifati, Edlira Vakaj, Mauro Dragoni, and amien Graux. 2023.Large language models and knowledge graphs: Opportunities and challenges.Transactions on Graph Data and Knowledge.
• Pan etal. (2017a)J.Z. Pan, D.Calvanese, T.Eiter, I.Horrocks, M.Kifer, F.Lin, and Y.Zhao, editors. 2017a.Reasoning Web: Logical Foundation of Knowledge Graph Construction and Querying Answering.Springer.
• Pan etal. (2017b)J.Z. Pan, G.Vetere, J.M. Gomez-Perez, and H.Wu, editors. 2017b.Exploiting Linked Data and Knowledge Graphs for Large Organisations.Springer.
• Press etal. (2023)Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, NoahA. Smith, and Mike Lewis. 2023.Measuring and narrowing the compositionality gap in language models.In EMNLP (Findings), pages 5687–5711. Association for Computational Linguistics.
• Qin etal. (2023)Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, etal. 2023.Toolllm: Facilitating large language models to master 16000+ real-world apis.arXiv preprint arXiv:2307.16789.
• Ren etal. (2020)Hongyu Ren, Weihua Hu, and Jure Leskovec. 2020.Query2box: Reasoning over knowledge graphs in vector space using box embeddings.In ICLR. OpenReview.net.
• Ren and Leskovec (2020)Hongyu Ren and Jure Leskovec. 2020.Beta embeddings for multi-hop logical reasoning in knowledge graphs.Advances in Neural Information Processing Systems, 33:19716–19726.
• Shao etal. (2023)Zhihong Shao, Yeyun Gong, Yelong Shen, Minlie Huang, Nan Duan, and Weizhu Chen. 2023.Enhancing retrieval-augmented large language models with iterative retrieval-generation synergy.In EMNLP (Findings), pages 9248–9274. Association for Computational Linguistics.
• Shi etal. (2023)Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. 2023.REPLUG: retrieval-augmented black-box language models.CoRR, abs/2301.12652.
• Sun etal. (2023)Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Heung-Yeung Shum, and Jian Guo. 2023.Think-on-graph: Deep and responsible reasoning of large language model with knowledge graph.CoRR, abs/2307.07697.
• Touvron etal. (2023)Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian 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, PunitSingh 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, EricMichael Smith, Ranjan Subramanian, XiaoqingEllen Tan, Binh Tang, Ross Taylor, Adina Williams, JianXiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov,and Thomas Scialom. 2023.Llama 2: Open foundation and fine-tuned chat models.CoRR, abs/2307.09288.
• Trivedi etal. (2022)Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022.Musique: Multihop questions via single-hop question composition.Transactions of the Association for Computational Linguistics, 10:539–554.
• Vrandecic and Krötzsch (2014)Denny Vrandecic and Markus Krötzsch. 2014.Wikidata: a free collaborative knowledgebase.Commun. ACM, 57(10):78–85.
• Wang etal. (2023)Xuezhi Wang, Jason Wei, Dale Schuurmans, QuocV. Le, EdH. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023.Self-consistency improves chain of thought reasoning in language models.In ICLR. OpenReview.net.
• Wei etal. (2022)Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, EdH. Chi, QuocV. Le, and Denny Zhou. 2022.Chain-of-thought prompting elicits reasoning in large language models.In NeurIPS.
• Wu etal. (2024)Yike Wu, YiHuang, Nan Hu, Yuncheng Hua, Guilin Qi, Jiaoyan Chen, and JeffZ. Pan. 2024.CoTKR: Chain-of-Thought Enhanced Knowledge Rewriting for Complex Knowledge Graph Question Answering.In Proc. of Empirical Methods in Natural Language Processing (EMNLP 2024).
• Xiong etal. (2024a)Siheng Xiong, Ali Payani, Ramana Kompella, and Faramarz Fekri. 2024a.Large language models can learn temporal reasoning.arXiv preprint arXiv:2401.06853.
• Xiong etal. (2024b)Siheng Xiong, Yuan Yang, Ali Payani, JamesC Kerce, and Faramarz Fekri. 2024b.Teilp: Time prediction over knowledge graphs via logical reasoning.In Proceedings of the AAAI Conference on Artificial Intelligence, volume38, pages 16112–16119.
• Xu etal. (2022)Zezhong Xu, Wen Zhang, Peng Ye, Hui Chen, and Huajun Chen. 2022.Neural-symbolic entangled framework for complex query answering.In NeurIPS.
• Yan etal. (2024)Shi-Qi Yan, Jia-Chen Gu, Yun Zhu, and Zhen-Hua Ling. 2024.Corrective retrieval augmented generation.CoRR, abs/2401.15884.
• Yang etal. (2018)Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, WilliamW Cohen, Ruslan Salakhutdinov, and ChristopherD Manning. 2018.Hotpotqa: A dataset for diverse, explainable multi-hop question answering.arXiv preprint arXiv:1809.09600.
• Yao etal. (2024)Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2024.Tree of thoughts: Deliberate problem solving with large language models.Advances in Neural Information Processing Systems, 36.
• Yao etal. (2022)Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022.React: Synergizing reasoning and acting in language models.arXiv preprint arXiv:2210.03629.
• Zhang etal. (2023)Zhuosheng Zhang, Aston Zhang, MuLi, and Alex Smola. 2023.Automatic chain of thought prompting in large language models.In ICLR. OpenReview.net.
• Zhou etal. (2023)Denny Zhou, Nathanael Schärli, LeHou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, QuocV. Le, and EdH. Chi. 2023.Least-to-most prompting enables complex reasoning in large language models.In ICLR. OpenReview.net.

Appendix A Case Study

Cases are shown in Figure 5 where we mark the bad parts of the ICLPKG (GPT-3.5) planning in red, and the corresponding parts of LPKG (Llama3) in blue. In order to highlight the core difference, the “Thought” in planning is omitted in the cases.

Appendix B Prevention of Data Leakage

In the experiment, we used data from knowledge graph sources as training data, which may raise concerns about data leakage, specifically the overlap between the training data and the four multi-hop test sets(HotPotQA, 2WikiMQA, Bamboogle, MusiQue). We calculate the semantic similarity between the training and testing questions. We use the BGE-M3 model to embed the training and testing questions into high-dimensional vectors and calculate their cosine similarity. We found that the similarity between the testing and training questions does not exceed 0.8, and is generally below 0.6. This indicates that there is almost no high degree of overlap between the training data and the testing data.

In addition, when conducting experiments on our own test set CLQA-Wiki, we excluded questions similar to those in CLQA-Wiki from the training data (with similarity scores above 0.9), ensuring no high overlap between the training and testing data.

Appendix C Prompt Content