Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions (2023)

Abstract: Large language models (LLMs) are capable of answering knowledge-intensive complex questions with chain-of-thought (CoT) reasoning. However, they tend to generate factually incorrect reasoning steps when the required knowledge is not available or up-to-date in models’ parameters. Recent works turn to retrieving external knowledge to augment CoT reasoning. Despite being promising, these chain-based methods suffer from: 1) Negative retrieval. Unnecessary or incorrect retrieval may mislead the reasoning; 2) Limited sight. Lacking the ability to look backward or forward, a local error in one step will propagate along the chain. In this paper, we propose a novel approach: Probabilistic Tree-of-thought Reasoning (ProbTree). First, LLMs translate a complex question into a query tree, in which each non-root node denotes a sub-question of its parent node. Then, probabilistic reasoning is conducted over the tree, by solving questions from leaf to root considering the confidence of both question decomposing and answering. During reasoning, for leaf nodes, LLMs choose a more confident answer from Closed-book QA that employs parametric knowledge and Open-book QA that employs retrieved external knowledge, thus eliminating the negative retrieval problem. For non-leaf nodes, with the hierarchical structure, LLMs have broader sights and are able to globally reason with the information from child nodes, thus recovering from local errors. The experiments on three Complex QA datasets under the open-domain setting show that our approach outperforms SOTA methods significantly, demonstrating the effect of probabilistic tree-of-thought reasoning.

## introduction answering knowledge-intensive complex questions requires reasoning over multiple knowledge facts * indicates equal contribution. † corresponding author. to infer the answer, and involves various reasoning capabilities such as multi-hop inference, attribute comparison, and set operation @xcite @xcite . large language models (llms) @xcite @xcite have shown to be capable of this task by breaking questions into a sequence of reasoning steps, termed chainof-thought (cot), before arriving at a final answer @xcite . however, they tend to generate factually incorrect reasoning steps when the required knowledge is not available or up-to-date in their parameters @xcite . to mitigate this problem, retrieval-augmented llms have attracted increasing attention @xcite , which retrieve knowledge from an external datastore when needed and then perform cot reasoning conditioning on the retrieved knowledge. typically, they retrieve multiple times in an iterative way, using the last generated sub-question @xcite or reasoning step @xcite as the query to retrieve documents and generate the next one based on it. despite leading to performance gains, these chain-based methods are still unsatisfactory for two reasons: 1) negative retrieval. they ignore that unnecessary or incorrect external knowledge may mislead the llm reasoning @xcite . e.g., we investigate the inference results of ir-cot @xcite (one of the sota retrieval-augmented llms) , finding that around 10% of questions are incorrectly answered due to this reason; 2) limited sight. lacking the ability to look forward and backward, a local error in one step will propagate along the chain, deteriorating the whole reasoning process. e.g., as shown in fig. 1 , an incorrectly answered sub-question will cause the following generated sub-questions incorrect, causing the final answer incorrect. to this end, inspired by previous works that conduct optimization on tree-like computation graphs @xcite @xcite , in this paper, we propose a novel approach: probabilistic tree-of-thought reasoning (probtree). in all, we disentangle qa into two stages: understanding and reasoning. as shown in fig. 1 , first, llms translate a given question into a query tree via the language understanding ability. in this tree, the root node is the original complex question, and each non-root node is the sub-question of its parent. each leaf node is an "atomic" question that cannot be further decomposed. second, reasoning is conducted over the tree, by solving questions from leaf to root with post-order traversal, considering the confidence of both question decomposing and answering. via probtree, we can alleviate the above two problems: 1) during reasoning, for leaf nodes, closedbook qa that employs parametric knowledge and open-book qa that reasons with retrieved external knowledge are conducted simultaneously, and llms choose a more confident answer from them based on self-evaluation, thus eliminating the negative retrieval problem; 2) on non-leaf nodes, llms are able to globally reason with the information from child nodes. with the hierarchical structure of tree, llms have broader sights and can recover from wrong decompositions or incorrectly answered sub-questions, thus alleviating the problem of error propagation. specifically, given the observation that llms tend to be well-calibrated and low probability often indicates a lack of knowledge @xcite @xcite , we hypothesize that likelihood of the explanation (i.e., reasoning steps in cot) indicates llm confidence in the answer, and propose to quantify answer confidence with explanation logits. during forward propagation, for each node, llms choose the most confident answer from three qa modules: 1) childaggregating qa that reasons with child questionanswer pairs; 2) open-book qa that reasons with the external knowledge including the retrieved paragraphs for itself and its descendants foot_0 ; 3) closedbook qa that employs the implicitly encoded parametric knowledge. in evaluation, we instantiate probtree on three complex qa datasets under the opendomain setting: hotpotqa @xcite , musique @xcite , and 2wikimul-tihopqa @xcite . experimental results using openai gpt3 (text-davinci-003) show that probtree improves the performance significantly, by 3.9%, 7.3%, and 5.2% f1 score on the three datasets respectively compared with existing sota models. our contributions include: a) exploring the llm capacity of answering knowledge-intensive complex questions and proposing the tree-ofthought reasoning approach for the first time; b) bringing uncertainty into reasoning and proposing a self-evaluation based method to quantify answer confidence, which enables integrating external and parametric knowledge in a unified framework; c) demonstrating the effect of probtree with in-depth analyses, and proving the effect of each component with careful ablation studies. our codes and datasets can be obtained from https: //github.com/thu-keg/probtree . ## related work retrieval-augmented large language models for retrieval-augmented llms, previous works typically adopt one-time retrieval, i.e., retrieve knowledge using only the input question once @xcite @xcite . this line of work, however, cannot meet the need of complex questions that require multi-hop inference. recently, another line of work arose, which adopt multi-time retrieval during the generation process to meet the complex information needs. the representative works include selfask @xcite which prompts llms to decompose a question into sub-questions and triggers retrieval 𝑞 % : which religious order founded harvard college? ## methodology in this section, we first formalize the query tree, then overview our framework, and finally introduce the details of each component of the framework. query tree given a question q, its query tree is t , in which the root node is the input question, and each non-root node is a sub-question of its parent node. each leaf node is an "atomic" question that cannot be further decomposed. we index the nodes of t with bfs ordering. for example, in fig. 2 , the root node q is indexed with q 0 , and its child nodes are q 1 , q 2 , q 3 . formally, for a non-leaf node q @xmath0, child i contains its child nodes index, and the child nodes are: overview the question answering task is disentangled into two phases: understanding and reasoning. first, the understanding phase (section 3.1) transforms the user input question into a query tree with the language understanding ability of llms. at the same time, the confidence scores of question decomposing are calculated, which will be used in the next probabilistic reasoning phase (section 3.2). as shown in fig. 2 , we bring uncertainty into reasoning by considering the answer confidence from different qa modules. specifically, during reasoning, llm try to solve questions from leaf to root via post-order traversal. e.g., in fig. 2 , q 4 , q 5 , q 1 , q 2 , q 3 , q 0 are solved in order. for questions that contain reference tokens, the reference tokens are first assigned with a concrete entity that is from a previous answer. e.g., for q 5 , "#1" refers to the answer of q 4 "massachusetts general court", and q 5 is reformed as "which religious order was massachusetts general court a part of?" before answering. for question solving, for node q i , the optimal answers for its child nodes have been obtained, and llms consider answering q i based on 1) the answers of its sub-questions (child-aggregating qa); 2) the retrieved external knowledge (open-book qa); and 3) the parametric knowledge (closed-book qa). for each qa module, llms output the confidence in the answer, and take the answer with the highest confidence as the final optimal solution for q i . ## error analysis we manually analyze 150 errors (50 per dataset) output by probtree. as shown in in all, decomposition error is most challenging in hotpotqa since it contains questions with complicated syntactic structures. retrieval, reasoning, and decomposition errors make up more than 30% on each dataset, which may be reduced by using a more powerful retriever and backend llm. only a small percentage of errors are caused by the confidence mechanism of probtree. ## discussion and conclusion in this paper, we explore the llm capacity of answering knowledge-intensive complex questions and propose a probabilistic tree-of-thought reasoning approach. actually, we think this paper shows an example that llms leverage the strengths of specialized tools to accomplish complex tasks, i.e., tool learning @xcite in which llms start from understanding the user instruction, learn to decompose a complex task into several subtasks, and conquer each sub-task by selecting appropriate tools. in our case, llms start from understanding the complex question, decompose it into a query tree, and reason over the tree to solve questions by selecting an appropriate api from childaggregating qa, open-book qa, and closed-book qa. in the future, we hope to extend our approach to other complex tasks. in addition, for complex qa, in this paper, the external knowledge is limited to document corpora which mainly contain unstructured text. we hope to cover other structured knowledge sources such as knowledge bases (kbs) @xcite and tables in the future, since knowledge from different sources complement each other. this can be achieved by incorporating other qa modules during reasoning such as semantic parsers that can execute on kbs or tables.