Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions
Authors: Shulin Cao
Jiajie Zhang
Jiaxin Shi
Xin Lv
Zijun Yao
Qi Tian
Lei Hou
Juanzi Li
Venue: EMNLP 2023 Findings (2023)
Keywords: LLMs; Probabilistic Tree-of-thought Reasoning; Hallucination; Knowledge-intensive Complex QA
TL;DR: Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions

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.

Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions
Shulin Cao'r, Jiajie Zhang',, Jiaxin Shi', Xin Lv', Zijun Yao', Qi Tian"!
Juanzi Li Lei Hou'
Departmeett of Computer Science and Technology, Tsinghua University, Beijing, China "Cloud BU, Huawei Technologies
{caosl19, stajie-z19Jemails tsinghua. edu. cn
tian. qi 1ehuawei. com, (houlei, lijuanzi Jetsinghua..nnn...oo ieg edu. cn
Abstract
Understand Reason
Large language models (LLMs) are capable of answering knowledge-intenne innteeivi complex ques- tions with chain-of- -f-thughht (CoT) reasoning. However, they tend generate factually incor- rect reasoning steps when the required knowl- edge is not available or up-to-date models' parameters. Recent works turn to retrieving external knowledge to augment CoT reasoning. Despite being promising, these chain-based methods suffer from: Negative retrieval. Un- necessary or incorrect retrieval may mislead the reasoning; Limited sight. Lacking the ability to look backward or forward, local error in one step will propagate along the chain.
Understand
Reason
Figure I: In chain-of-though reasoning. the error in one step propagates to the final answer due limited sight. Tree-of-thoughh reasoning can eliminate this problem by reconsidering the answer on the non-leaf nodes. The red edge means error propagation.
this paper, we propose a novel ap- proach: Probabilistic Tree-of-thought Rea- soning (Prob Tree). First, LLMs translate complex question into query tree, which each non-root node denotes sub-question of its parent node. Then, probabilistic reasoning conducted over 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 know]- edge, thus eliminating the negative retrieval problem. For non-leaf nodes, with the hierar- chical structure, LLMs have broader sights and are able to globally reason with the information from child nodes. thus recovering from local errors. The experiments three Complex QA datasets under the open-domain setting show that our approach outperforms SOTA methods significantly, demonstrating the effect of proba- bilistic tree-of of-thoughtt reasoning.
infer the answer, and involves various reasoning capabilities such as multi-hop inference, attribute comparison, and set operation (Yang et al., 2018; Trivedi et al., 2022b; Cao et al., 2022). Large lan- guage models (LLMs) (Brown et al., 2020; Ouyang et al., 2022; Chowdhery et al., 2022) have shown to be capable of this task by breaking questions into sequence of reasoning steps, termed chain- of-thought (CoT), before arriving at final an- swer (Wei et al., 2022; Kojima al., 2022). How- ever, they tend to generate factually incorrect rea- soning steps when the required knowledge not available or up-to-date in their parameters (Trivedi et al., 2022a; Yao et al., 2022).
To mitigate this problem, retrieval-augne augmented LLMs have attracted increasing attention (Shi al., 2023; Jiang et al., 2023), which retrieve knowl- edge from an external datastore when needed and then perform CoT reasoning conditioning on the retrieved knowledge. Typically, they retrieve multi- ple times in an iterative way. using the last gener- ated sub-question (Press et al., 2022) or reasoning step (Trivedi al., 2022a) as the query to retrieve documents and generate the next one based it. Despite leading to performance gains, these chain-basee methods are still unsatisfactory for two
1 Introduction
Answering wowlledg--intessive complex questions requires reasoning over multiple knowledge facts
Indicates equal contribution. Conresponding author.

---

reasons: 1) Negative Retrieval. They ignore that unnecessary or incorrect external knowledge may mislead the LLM reasoning (Jiang et al., 2023). E.g., we investigate the inference results of IR- CoT (Trivedi et al., 2022a) (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 look forward and backward, 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 questiossn incor- rect, causing the final answer incorrect.
in the answer, and propose quantify answer con- fidence with explanation logits. During forward propagation, for each node, LLMs choose the most confident answer from three QA modules: 1) Child- aggregating QA that reasons with child question- answer pairs; 2) Open-book QA that reasons with the external knowledge including the retrieved para- graphs for itself and its descendants'; 3) Closed- book QA that employs the implicitly encoded para- metric knowledge.
In evaluation, we instantiate ProbTree on three Complex QA datasets under the open- domain setting: HotporQA (Yang et al., 2018), MusiQue (Trivedi et al., 2022b), and 2WikiMul- tihopQA (Ho et al., 2020). Experimental results using OpenAI GPT3 (text-davinci-00)) show that ProbTree improves the performance signifi- cantly, by 3.9%, 7.3%, and 5.2% Fl score on the three datasets respectively compared with existing SOTA models.
To this end, inspired by previous works that conduct optimization on tree-like computation graphs (Bai et al., 2022; Liu et al., 2023; Zhang et al., 2023), in this paper, we propose a novel ap- proach: 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 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 decom- posed. Second, reasoning is conducted over the tree, by solving questions from leaf root with post-order traversal, considering the confidence of both question decomposing and answering. Via ProbTree, we can alleviate the above two prob- lems: 1) During reasoning, for leaf nodes, Closed- book QA that employs parametric knowledge and Open-book QA that reasons with retrieved exter- nal knowledge are conducted simultancously, and LLMs choose a more confident answer from them based on self-evaluation, thus eliminating the nega- tive retrieval problem; 2) On non-leaf nodes, LLMs are able to globally reason with the information from child nodes. With the hierarchical struc- ture of tree, LLMs have broader sights and can recover from wrong decompositions or incorrectly answered sub-questions, thus alleviating the prob- lem of error propagation.
Our contributions include: a) exploring the LLM capacity of answering knowledge-intensive complex questions and proposing the tree-of- thought reasoning approach for the first time: b) bringing uncertainty into reasoning and propos- ing self-evaluation based method to quantify an- swer confidence, which enables integrating exter- nal and parametric knowledge a unified frame- work; c) demonstrating the effeet of ProbTrec with in-depth analyses, and proving the effect of each component with careful ablation studies. Our codes and datasets can be obtained from https: //g thub. wwt..///---////oooTrree..o
Related Work
Retrieval-augnmented Large Language Models
For -ugmmette LLMs. previous works typ- ically adopt one-time retrieval, i.e., retrieve knowl- edge using only the input question once (Borgeaud et al., 2022; Izacard et al., 2022; Shi et al., 2023). This line of work, however, cannot meet the need of complex questions that require multi-hop infer- ence. 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 (Press et al., 2022) which prompts LLMs to decompose a question into sub-questions and triggers retrieval
Specificully, given the observation that LLMs tend to be well-calibrated and low probability often indicates a lack of knowledge (Jiang et al., 2021; Kadavath et al., 2022; Jiang et al., 2023), we hy- pothesize that likelihood of the explanation (i.e., reasoning steps in CoT) indicates LLM confidence
For leaf nodes, the output from Child-aggregating QA is empty, and the external knowledge in Open-book QA only contains the retrieved paragraphs for itself.

---

q't When the religious order that founded Harvard College, arrive the region of the U.S. served by the Rainbow Times?
[OB]: ((1847, -0. 0.14)))
[CB]: ((1636, -0. (62))
[CA]: ((1630, -0.091))
Which religious order founded
= Which region of the U.S. is served by the Rainbow Times?
qa When did arrive +
Harvard College?
[OB]: [[Unknown, -0. -0.167))
[OB]: ((New England, -0.181)
[OB] ((1630, -0. 00.04))
[CB]: ((Puritan, -0. -0.158))
[CB]: ((New England, (rggand,.0.2600) -0.260))
[CB]: ((1620, -0.056) [CA]: (
[CA]: ((Puritan, -0.12))
[CA]: (
q: Who founded Harvard College? [OB]: ((John Harvard,-O. 1673
qº Which religious order was a part of?
[OB]: ([Unknown, -0. 142)) [CB]: ((Puritan, -0.109)) [CA]: ()
Decomposing
[OB] Open-book QA [CB] Closed-book QA
[CB]: (MMassachusetts
Forward propagation
General Court, -0.154)
Reference assignment
[CA]Chid-aggregssing QA
[CA]: ()
Figure 2: Illustration of the reasoning phase of ProbTree. In this phase, reasoning is conducted over the tree by solving questions from leaf to node via a forward propagation. For each node, LLMs choose the most confident answer from three QA modules: -agreeaggggg QA, Open-book QA, and Closed-book QA.
every sub-question, IRCoT (Trivedi et al., 2022a)
rely heavily on supervision data which are expen- sive to obtain (e.g., sub-question annotations), and need to call specially-trainee sub-modules such link predictors, neural readers, semantic parsers, etc. In contrast, our work turns fully exploring the potentials of L.MMs, i.e., whether this method- ology can help improve LLMs' ability.
which triggers retrieval every CoT sentence (i.e., reasoning step), which leverages the generation (the complete CoT reasoning steps) from the previous turn concate- nated with the original question as the query for next turn generation, DSP (Khattab et al., 2022) which employs task-aware programs to decompose the question and perform retrieval to solve sub- questions, etc.
(Shao al., 2023)
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.
Compared with their works, we are the first to organize the complex information needs with a tree structure, which has broader sights and more flexi- bility. Besides, we are the first to bring uncertainty into reasoning for integrating parametric and exter- nal knowledge in unifided famework.
Query Tree Given question Q, its query tree is T, in which the root node is the input ques- tion, and each non-root node is 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 dº and its child nodes are (q)""".q") For- mally, for non-leaf node g' T. child' con- tains its child nodes index, and the child nodes are: 3. For non-leaf node q'. reference tokens indicating entity variables such as "#k" (k n) may appear in its child question childdj j 2 2, referring to the an- swer of question gehild's, For example, in Fig. 2, the "#1" in g² (ghhil))) means the answer of gt (gchild)).
Reasoning on Tree-like Computation Graphs Tree is basic data structure in computer science, and there have been works that employ tree struc- ture to solve complex tasks in recent years. For example, Yao et al. (2023) prompts LLMs to per- form BFS or DFS searching to solve tasks that need planning such as Game 24. Given complex logical query natural language question, several works derive tree-like computation graph from the input, and then reason over the tree recursively obtain the global solution (Bai al., 2022; Liu et al., 2023; Zhang et al., 2023). The tree structure brings explainability to their model. However, they
9¹ .children = (qchiidi .......ghsi., chiidi..

---

Overview The question answering task is disen- tangled into two phases: understanding and reason- ing. First, the understanding phase (Section 3.1) transforms the user imput question into a query tree with the language understanding ability of LLMss At the same time, the confidence scores of question decomposing are calculated, which will be used in the next probabilisticc reasoning phase (Sec- tion 3.2). As shown in Fig. 2, we bring uncer- tainty into reasoning by considering the answer confidence from different QA modules. Specifi- cally, during reasoning, LLM try to solve questions from leaf to root via post-order traversal. E.g., in Fig. 2. (q",4% g", ,4,4444 "2,.". )²) are solved in order. For questions that contain reference tokens, the reference tokens are first assigned with concrete entity that is from previous answer. E.g., for g¹, "#1" refers the answer of 9 "Massachusetts General Court", and qº is reformed as "Which re- ligious order was Massachusetts General Court a part of?" before answering. For question solving, for node g¹, the optimal answers for its child nodes have been obtained, and LLMs consider answer- ing o' based on 1) the answers of its sub-questions QA); 2) the retrieved external knowledge (Open-book QA); and the parametric knowledge (Closed-book QA). For each QA mod- ule, LLMs output the confidence in the answer, and take the answer with the highest confidence as the final optimal solution for q'
In this phase, given question Q, its query tree T is obtained, where Q the dd in T. In addition. for each non-leaf node g¹ E T, the decomposition score ds' is calculated to denote the confidence that 2²t can be decomposed into q¹ .children.
Basically, as shown in Fig. 3, the query tree is generated by LLMs with few-shot prompting. The query tree is output in JSON format, where the key is the parent question, and the value is a list of child questions. A challenge here is to calcu- late the decomposing score. Given the observation that a generative pre-training model will assign a higher probability of high quality generations than unqualified ones, we calculate ds' with the condi- tional probability of LLMs. Specifically, LLMs generate the query tree in BFS order, i.e., all nodes present in the same level are generated first before generating the next level. Assume the generated tree before q' is denoted as beefore, and the seri- alized senquence of q² .children is seq'. Suppose seq' = (#1, ... F, ... =lseg')) ds' is calculated based on the average log- lig-liiel of seg':
ds 1 Iscq'l
logp(æ, (Q, T fore .q')..
sse'
(1)
Here [+ mcans concatenation following the speci- fied order.
3.2 Reasoning
3.1 Understanding
In this phase, given T, fqe is conducted to find the optimal solution for q¹ from leaf root on T in post-order traversal,
Input
generate
jeon decompastion original pomplex
the formel given question sub-question is parent. leaf question,
(2)
stomic questions that cannot furthor decomposed.
<xmmples>>
Here, at is the optimal answer for q', and st is the corresponding confidence score.
When did raligious order founded Harvard College, anive region of U.S. by Rainbow Times?
In general, the optimal answer is the most con- fident answer from three QA modules: 1) Child- aggregating QA Seas 2) Open-book QA fob and 3) Closed-bood QA feh. Formally,
Output
1 When ald the refigious our ortfer that founded Harvard College, arrive in the rigion the U.S. served by the Rainbow Times?" !
"Which religious order founded Harvard College?".
"Which region of the U.S. served by the Rainbow Times?".
"When did #1 arrive #29"
before
(dea s fcolg' T,ds'), (a (66) fall', T),
(3)
raligriuss order founded Harvard Collage?":
(4)
founded Harvard Collega?".
"Which religious order was part
of children
(a's ('6)) = faa(''),
(5)
m² argmaxmeloa, ob, ob) sn
(6)
Figure 3: Given question, LLMs generate the query tree with few-shot prompting. The query tree is JSON format. The parent question is denoted as purple, and the list of child questions are denoted as green.
(a (..s') = (ain., Si..).
(7)
Here, d d's and o' are the candidate answers from the three QA modules respectively, and s

---

6' S's are the respective confidence scores. In the following, we will introduce the three QA modules detail.
Open-book QA The basic implementation of fob is similar that of fees and s. is also calculated with the CoT explanation logits (Bqq 8). The differ- ence lies in the construction of context c.
Input
Intuitively, for a question, the retrieved para- graphs for its descendants may contain the sup- porting evidence. Therefore, we take the related paragraphs o' d'-para as the context e:
Given a quesiion and contex,, answer the queston and explain why. <Exampees>>
Consaxt:
religious founcied Hervard College?
Which region ohe the U.S. served by the Rainbow Times? New England.
When did Puriian arrive in New England? 1630.
Quastion:
did religious order founded Harvard College, anive
region the U.S. served by the Rainbow Times?
lohsld U j=1
Anower:
p'para = R(O')U
q childj
ppara, paaaa (10)
Output
College, region served the Times, New Engiand, So the answer is: 1630.
religious
where R(q')) is the retrieved paragraphs with of query.
Figure 4: An illustration for the prompt of foa- The child question- guestion-answer answer pairs are denoted with green, and the explanation of answer is denoted with purple.
Closed-book QA For feb the basic implementa- tion is similar that of fob, except that the context for the question q' is empty. s's is also calculated with the CoT explanation logits (Bq. 8).
bhidd-ggggggating QA As shown in Fig. 4, for a question, the question-answer pairs of its child nodes are packed into the prompt as its context, based on which LLMs perform CoT reasoning. This way, LLMS meta-reason with the informa- tion from child nodes, and give comprehensive answer for the parent question. This is effective to recover from the wrong question decomposition or incorrectly answered sub-questions, helping with the error propagation due to limited sight in chain- based methods. Specifically, given a question g¹, o', is outputed by the LLM ("1630" in Fig. 4). The challenge here is to obtain the confidence s'a. Intuitively, the likelihood of the explanation in- dicates the confidence of its derived answer. There- fore, suppose the context is denoted as c, and the explanation e = (51,'.. "' )fle) the confi- dence si. is calculated as:
4 Experimental Settings
4.1 Datasets
We evaluate ProbTree three Complex QA datasets under the open-domain setting: Hot- potQA (Yang et al., 2018), MuSiQue (Trivedi al., 2022b) and 2WikiMultiHopQA (2WikiMQA) (Ho et al., 2020). We use the same retrieval corpora as IRCoT (Trivedi et al., 2022a): for HotpotQA, we use the October 2017 Wikipedia dump; for MuSiQue and 2WikiMQA, they are constructed by combining all supporting and non-supporting paragraphs for all the questions in their train, dev, and test sets.
For each dataset, we also use the same develop- ment and test set provided by IRCoT (Trivedi et al., 2022a). Specifically, they randomly sampled 100 questions from the original dev set the dev set, and another 500 as the set.
g1
log (ogp(z)(e2))
4.2 Implementation Details
In addition, the correctness of a is also de- pendent the correctness of its context, i.e., the question-answer pair of its child nodes. Therefore, the final confidence score sf is:
We instantiate ProbTree with OpenAl GPT3 feext-davinci-ee3 (Ouyang et al., 2022). The temperature is set to 0 for stable output.
Following IRCoT (Trivedi et al., 2022a), we use BM25 (Robertson and Zaragoza, 2009) im- plemented with Elasticsearch for the retriever R. For node q¹ C T, we retrieve top- paragraphs as R(q'), where K E {3.5, 7} is selected based on the dev set.
|child'
1
(ds*
+
s childy + +.
|n|
+
j=1

---

HorpoiQA Bridge
MuSiQue
2WikIMQA
Method
Overall
Comparison
Overall
Zhop
Shop
4hop
Overall
Bridge
Inference Comparison Compge-Cnnnnioon
Without Retrieval
Direct
39.5
35.1
59.8
16.9
17.9
15.6
16.1
33.6
12.8
26.3
52.6
56.2
62.2
With Retrieval
Onci
53.2
50.0
22.6
16.0
73.7
IRCoT
60,2
58.0
69.4
34.2
44.2
26.3
20.1
63.8
46.2
45.4
91.6
79.0
Self-Ask
49.4
45.3
68.6
33.4
42.3
26.2
20.8
66.6
51.9
57.0
85.5
80.0
44.7
RETGEN
MCR
$7.0
67.9
62.6 (2.1
61.0
69.8
ProbTree
41.5 (7.3
71.8
64.1" (3.9 f)
60.9*
79.1"
Table 1: Answer F1 results of different methods. We highlight the best results in bold and second with an underline. * means add the top-1 snippet from Google Search into R(q") for leaf questions, via SerpAPI service com/) with the query format "en. hon.wikippe wikipedia. org g.". Color grey denotes the methods using different settings from ours, including GPT versions, retrievers and test samples. The results of ReAct and ITER- RETGEN from (Shao et al., 2023), and the results of MCR from their original paper.
4.3 Baselines
Method
HotpoiQA 64.1
MuSiQue 41.5
2WikIMQA
ProbTree
71.8
We mainly compare ProbTree with representative models that are in the same setting us, including set, document corpora, and retriever:
SD
51.7 (12.4
39.0 (2.5 [)
69.2 (2.6 4)
w/o CA
63.9 1)
34.8 (6.7 J)
65.1 (6.7 4)
w/ RC
53.2 (10.9 1)
(16.
52.0 (19.8
w/ SC@3
62.4 (1.7
38.4 (3.1
68.8 (3.0
w/ SC
63.0
40.7 (0.8
70.1 (1.7
Direct Prompting prompts an LLM to directly predict an answer.
CB
63.6 (0.5 4)
38.4 (3.1
70.4
(144
w/o OB
46.3 (17.8
23.2
(18.3
42.3
(29.5
Table 2: Ablation results that demonstrate the effect of 1) Tree-of-though reasoning: Sequential decompo- sition (SD), ProbTree without Child-aggregating QA (w/o CA); 2) Probilistic reasoning that integrates para- metric and external knowledge in unified framework: ProbTree with random choosing (w/ RC), with Self- consisency (w/ SC@3 and w/ SC@5), ProbTree without Jos (w/o OB), without feb (w/o CB).
CoT Prompting prompts an LLM generate step-by-step explanation before giving the answer.
One-step Retrieval (OneR) augments CoT Prompting by using the original complex ques- tion as a query to retrieve K paragraphs. K E {5, 10, 15) is selected based on the dev set.
IRCoT (Trivedi et al., 2022a) interleaves re- trieval with CoT generation by triggering retrieval every CoT sentence to generate the next one. We re-implement it with text-davinci-003 (Details in Appendix C.1).
Experimental Results
5.1 Overall Results
As shown in Table 1, our method achieves the best performance all three datasets. Compared with the SOTA method IRCoT, ours improves the Fl score by 2.4%, 7.3%, and 8.0% (5.2% compared with Self-Ask) respectively, demonstrating the ef- fect of ProbTree. We attribute the improvement to three reasons: a) IRCoT suffers from the problem of eтror propagation due to limited sight in chain- of thouttt reasoning. In contrast, the hierarchical structure of tree makes our method have broader sights and more error-tolerant; We bring uncer- tainty into reasoning and choose the most confident answer from Closed- and Open-book QA. However, IRCoT simply depends on the retrieved externl knowledge, which may mislead the LLM reason-
Self-Ask (Press et al., 2022) interleaves retrieval with follow-up sub-question generation by trigger- ing retrieval every sub-question generate the next one. We re-implement with text-davinci-003 (Details in Appendix C.2).
In addition, we include other recent approaches ReAct (Yao et al., 2022), ITER-RETGEN (Shao et al., 2023) and MCR (Yoran al., 2023). Their results are not generally apples-to-apples compar- isons, since they span variety of evaluation set- tings, including GPT versions, test samples, and retrievers. Nonetheless, we report them here as qualitative reference points.

---

ing: c) Our query tree represents the user intent very well. In contrast, IRCoT employs the last generated CoT sentence as the query, which only mentions the bridge entity, and is insufficient to represent the query intent accurately.
Which Canadian rock band released a song called "Counterparts" " and had drummer who was in- ducted into the Modern Drummer Hall Fame? Gold Answer: Rush
Question:
Sequential Decomposition
Step I: Which Canadian rock band released song called "Counterparts")
We also provide in-depth analyses of reasoning abilities in Table 1, from which we can observe that our method performs well on all types of ques- tions, showing good generalizability and robust- ness. Compared with HotpoiQA and 2WikiMQA, MuSiQue is more challenging and less cheatable, containing 2-4 hop questions with six different composition structures. Table I shows that the existing results on MuSiQue are low, especially for questions with complex compositional struc- ture, i.e., or 4-hop questions. Our method im- proves the performance on these complex questions largely, with 11.8% Fl score on 3-hop questions. 2WikiMQA contains questions generated by hand- crafted templates. They contain the complex "In- ference" questions that test the implicit reasoning ability, and Seridge-comparioon questions that re- quire both finding the bridge entities and doing comparisons obtain the answer. Our methods improve largely on these questions, with 11.7% for "Inference" and 15.2% for "Bridge-comparison"" In addition, on HotpotQA, after adding the top-1 snippet from Google Search for each leaf question, ProbTTree achieves a higher Fl result (64.1% 1% v.s. 62.6%), demonstrating that better aub-modules can further improve the overall performance.
Answer The Canadian rock band Rush released song called "Counterparts". So the answer is: Rush.
Step 2: Which drummer of #1 was inducted into the Modern Drummer Hall of Fame? (incorrect sub-question) Answer 2: The drummer of Rush is Neil Peart. Neil Peart was inducted into the Modern Drummer Hall of Fame in 1983. So the answer is: Neil Peart. Final Answer: Neil Peart
ProbTree (Child-Aggregattion QA)
Context:
Which Canadian rock band released song called "Coun- terparts"? Rush
Which drummer of Rush was inducted into the Moder Dru- mmerr Hall of Fame? Neil Peart. (incorrect sub- question)
Question:
Which Canadian rock hand released a song called "Coun- terparts" and had a drummer who was inducted into the Modern Drummer Hall of Fame?
Answer: The Canadian rock band Rush released a song called "Counterparts" and had a drummer, Neil Peart, who was inducted into the Modern Drummer Hall of Fame. So the answer is: Rush.
Table 3: When generating unneccessary or incorrect sub-questions. SD cannot recover from the wrong de- compositions, while the Child-aggreiating Q4 in Prob- Tree enables meta-reasoning with the information from sub-questions to get the correct answer.
reasoning. Table 3 shows a case where ProbTree can recover from local errors, while SD cannot.
5.2 blation Study
2) ProbTree without Child-aggregating QA (w/o CA), where the answer of each node is se- lected from Closed- and Open-book QA. The per- formance drops on all the datasets. This is be- cause Closed-book QA for complex questions of- ten fails due to hallucination, and Open-book QA for complex questions also makes mistakes due to large number of distractor paragraphs (As shown in Table 11 in the Appendix). In contrast, Child- aggregating QA concisely summarizes information from sub-questions.
We conduct a series of ablation studies to prove the effect of each component in ProbTree. The results are in Table 2.
5.2.1 Effect of Tree-of-thought Reasoning
We conduct two ablation studies: 1) Sequential Decomposition (SD). It decomposes the com- plex question into sequence of atomic questions, solves them step by step by selecting the most con- fident answer from Close-book and Open-book QA in ProbTree, and takes the answer of the last atomic question as the final answer. For example, SD of 7 in Fig. 2 is: (² ?²); 3)2 Compared with ProbTree, Fl scores drop by 13.6%, 2.5%, and 2.6% on the three datasets, demonstrating the su- periority of tree-based reasoning over chain-based
3.
5.2.2 Effect of Probabilistic Reasoning
We bring uncertainty into reasoning for integrating parametric and external knowledge in a unifided famework. In this section, we prove the rationality of our confidence calculation method and the effect of knowledge integration.
'Reference tokens in questions change accordingly. F.g., in SD, q² is "When did #2 arrive in #3?"

---

Dataset
Ev.
An.
Rt.
Rs.
De.
Cf.
tually, the predictions are correct, however, they are measured as incorrect because our predictions are aliases of the gold answers, or questions with 1 1-to-N relations have multiple answers, while the gold annotations do not cover all of them. We at- tribute this type of error to the evaluation rather than the failure of our approach. (2) Inaccurate Data Annotation. We attribute this type of error to the dataset rather than the failure of our approach. For example, the annotated answer of the question in the released dataset is incorrect. Error. None of the retrieved paragraphs relevant to the target question, therefore the Open-book QA does not work. (4) Reasoning Error. Supporting paragraph is retrieved but Open-book QA still gives wrong prediction, or sub-questions have been cor- rectly answered but Child-aggregating QA makes mistakes. (5) Decomposition Error. The gener- ated query tree is incorrect, causing errors of the final answer. (6) Inaccurate Confidence: The cor- rect prediction from Open-book Closed-bood or Child-aggregating QA is not the most confident. In all, Decomposition Error is most challeng- ing in HotpotQA since it contains questions with complicated syntactic structures. Retrieval, reason- ing, and decomposition errors make up more than 30% on cach dataset, which may be reduced by using a more powerful retriever and backend LLM. Only small percentage of errors are caused by the confidence mechanism of ProbTree.
HotpotQA
38%
16%
8%
6%
16%
16%
MuSiQue
46%
16%
12%
8%
12%
6%
2WikiMQA
46%
8%
14%
14%
8%
10%
Table 4: Errors of ProbTree can be grouped into Evalua- tion limitation (Ev.). Inaccurate Data Annotation (An.), Retrieval Error (Rt.), Reasoning Error (Rs.), Decompo- sition Error (De.) and Inaccurate Confidence (Cf.).
Confidence: To demonstrate the rationality of confidence calculation, we compare our method with (1) Ranoonly-choosing (RC) one of these three answers as the final answer; (2) Self- consistency (Wang et al., 2022b) that samples (SC@3) or 5 (SC@5) CoTs for Child-aggregating. Open-book and Close-book QA respectively, and selects the most frequent answer from the 9/15 CoT's as the optimal answer (Details in Appendix C.3). Results in Table 2 show that ProbTree sig- nificantly outperforms RC, and beats SC@3 and SC@5 while using much fewer OpenAl API calls, demonstrating the effect of our confidence calcula- tion method that takes the explanation likelihood as the indicator of answer confidence.
(3) Retrieval
Knowledge Intergration: We respectively re- move Closed- (w/o CB) and Open-book QA (w/o OB) from the overall framework and evaluate the final performances. As shown in Table 2, the Fl results drop for both cases. Fig. 2 shows exam- ple from MuSiQue. For the sub-question "Who founded Harvard Colledge", the Open-bot QA is misled by a retrieved distractor sentence and gives a wrong prediction "John Harvard", while the Closed-book QA gives the correct prediction " "aasaacusettss General Courr" with higher confi- dence. On the other hand, for the sub-question "When did Puritan arrive in New England?", the Closed-book QA hallucinates and gives a wrong prediction " "1620", while the Open-book QA gives the correct prediction " "1630" with higher confi- dence based on the retrieved supporting paragraphs. From the case we can see probabilistic reasoning enables ProbTree to make better use of both para- metric and external knowledge.
7 Discussion and Conclusion
In this paper. we explore the LLM capacity of an- swering knowledge-intensse complex questions and propose a probabilistic tree-of-thought reason- ing 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 (Qin et al., 2023) in which LLMs start from understanding the user instruction, learn decompose complex task into several subtasks, and conquer each sub-task by selecting appropri- ate tools. In our case, LLMs start from under- standing the complex question, decompose it into a query tree, and reason over the tree to solve ques- tions by selecting an appropriate API from Child- aggregating QA, Open-book QA, and Closed-book QA. In the future, we hope to extend our approach to other complex tasks.
6 Error Analysis
We manually analyze 150 errors (50 per dataset) output by ProbTree. As shown in Table 4, the main reasons for error can be grouped into the follow- ing categories: (1) Evaluation Limitation. Ac-
In addition, for Complex QA, in this paper, the external knowledge is limited to document corpora

---

which mainly contain unstructured text. We hope cover other structured knowledge sources such as knowledge bases (KBs) (Wang et al., 2022a) and tables in the future, since knowledge from dif- ferent 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.
Institute for Guo Qiang, Tsinghua University (2019GQB0003).
References
Yushi Bai, Xin Lv, Juanzi Li, and Lei Hou. 2022. Answering complex logical queries on knowledge graphs via query computation tree optimization. ArXiv preprint, abs/2212.09567.
8 Limitations
Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George van den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, Diego de Las Casas, Aurelia Guy. Jacob Menick, Roman Ring. Tom Hennigan, Saffron Huang, Loren Maggiore, Chris Jones, Albin Cassirer, Andy Brock, Michela Pagamini, Geoffrey Irving, Oriol Vinyals. Simon Osindero, Karen Si- monyan, Jack W. Rae, Erich Elsen, and Laurent Sifre. 2022. Improving language models by retrieving from trillions of tokens. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Bal- timore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 2206-2240 PMLR.
ProbTrec relies on a backend language model that (I) has good few-shot CoT reasoning ability; (2) is well-calibrated; (3) has long context size. Cur- rently, only several LLMs with over 100B param- eters meet these requirements, which limits Prob- Tree to some extent.
For each node, ProbTree selects a most confident answer from Open-book, Closed-bood bookk and Child- aggregating QA, which brings additional compu- tational costs compared to methods (Trivedi et al., 2022a; Press al., 2022) that simply depend on retrieved knowledge. A possible improvement method is to incorporate active retrieval (Jiang et al., 2023) into the framework. In addition, as for external knowledge sources, we are limited to docu- ment corpora that mainly contain unstructured text. In the future, we can take other knowledge sources into consideration, such as structured knowledge bases and tables.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah. Jared Kaplan. Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Fric Sigler. Mateusz Litwin. Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learners. In Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual.
9 Ethical Considerations
LLMs suffer from hallucination, i.e., generating factually incorrect information and are also possi- ble generate biased offensive replies. Though retrieval-augmented approaches are expected al- leviate these issues, there still a risk of being hacked through targeted means such as injecting misleading context into prompts or adding harm- ful knowledge into the retrieval corpora. Hence additional care and protective measures should be taken if such systems are deployed in user-facing applications.
Shulin Cao, Jiaxin Shi, Liangming Pan, Lunyiu Nie. Yutong Xiang, Lei Hou, Juanzi Li, Bin Hc, and Han- wang Zhang. 2022. KQA Pro: A dataset with plicit compositional programs for complex question answering over knowledge base. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers). pages 6101-6119, Dublin, Ireland. Association for Computational Linguistics.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebas- tian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam M. Shazeer. Vinod- kumar Prabhakaran, Emily Reif, Nan Du, Benton C. Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengeheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Gareía,
All the datasets and encyclopedias used in this work are publicly published with permissible li- censes.
10 Acknowledgements
This work is supported by grants from Cloud BU, Huawei Technologies, Tsinghua University Initiative Scientific Research Program, and the

---

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 Lewkowycz, Erica Mor- eira, Rewon Child, Oleksandr Polozov, Katherine Lee. Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Díaz. Orhan Firat, Michele Catasta, Jason Wei, Kathleen S. Meier-Hellstem, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022. Palm: Scaling language modeling with pathways. ArXiv preprint, abs/2204.02311.
Ye Liu, Semih Yavuz, Rui Meng, Dragomir R. Radev, Caiming Xiong, and Yingbo Zhou. 2023. Answering complex questions over text by hybrid question pars- ing and exccution. ArXiv preprint, abs/2305.077 00799799.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Car- roll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welin- der, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. 2022. Training language models to follow instructions with human feedback. ArXiv preprint, abs/2203.02155.
Xanh Ho, AhhaKhoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020. Constructing multi- hop QA dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th Inter- national Conference on Computational Linguistics, pages 6609-6625, Barcelona, Spain (Online). Inter- national Committee on Computational Linguistics.
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis. 2022. Measuring and narrowing the compositionality gap in language models. ArXiv preprint, abs/2210.03350.
Yujia Qin, Shengding Hu, Yankai Lin, Weize Chen, Ning Ding, Ganqu Cui, Zheni Zeng, Yufei Huang, Chaojun Xiao, Chi Han. Yi Ren Fung. Yusheng Su, Huadong Wang, Cheng Qian, Runchu Tian, Kunlun Zhu, Shi Liang. Xingyu Shen, Bokai Xu, Zhen Zhang, Yining Ye, Bo Li, Ziwei Tang, Jing Yi, Yu Zhu, Zhen- ning Dai, Lan Yan, Xin Cong. Ya-Ting Lu, Weilin Zhao, Yuxiang Huang, Jun-Han Yan, Xu Han, Xian Sun, Dahai Li, Jason Phang, Cheng Yang. Tong- shuang Wu, Heng Ji, Zhiyuan Liu, and Maosong Sun. 2023. Tool learning with foundation models. ArXiv preprint, abs/2304.08354
Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane A. Yu, Armand Joulin, Sehastian Riedel, and Edouard Grave. 2022. Few-shot learning with retrieval augmented language models. ArXiv preprint, abs/2208 .3299..
Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. 2021. How can we know when language models know? on the calibration of language models for question answering. Transactions of the Associa- tion for Computational Linguistics, 9:962-977.
Zhenghao Jiang, Frank Xu, Luyu Gao, Zhiqing Sun, Yu Daisy Liu, Jane Dwivedi- Yu, Yiming Yang. Jamie Callan, and Graham Neubig. 2023. Ac- tive retrieval augmented generation. ArXiv preprint, 2ts/2305.06983..
Stephen E. Robertson and Hugo Zaragoza. 2009, The probabilistic relevance framework: Bm25 and be- yond. Found. Trends Inf. Retr. 3:333-389.
Zhihong Shao, Yeyun Gong, Yelong Shen, Minlie Huang, Nan Duan, and Weizhu Chen. 2023. En hancing retrieval- augmented large language models with iterative retrieval- genneratnn synergy. ArXiv preprint, abs/2305. 15294.
Saurav Kadavath, Tom Conerly, Amanda Askell, T. J. Hemighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zachary Dodds, Nova DasSarma, Eli Tran- Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, John Kernion, Shauna Kravec. Liane Lovitt. Kamal Ndousse, Catherine Olsson, Sam Ringer. Dario Amodei, Tom B. Brown, Jack Clark, Nicholas Joseph, Benjamin Mann, Sam McCandlish, Christopher Olab, and Jared Kaplan. 2022. Language models (mostly) know what they know. ArXiv preprint, abs/2200.05221..
Weijia Shi, Sewon Min, Michihiro Yasunaga, Min- joon Seo, Rich James, Mike Lewis. Luke Zettle- moyer, and Wen tau Yih. 2023. Replug: Retrieval- augmented black-box language models. ArXiv preprint, abs/2301.12652.
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022a. Interleav- ing retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions. ArXiv preprint, 1bs/22
O. Khattab, Keshav Santhanam, Xiang Lisa Li, David Leo Wright Hall, Percy Liang, Christopher Pouts, and Matei A. Zaharia. 2022. Demonstrate-seard predict: Composing retrieval and language mod- cls for knowledge-imtensive nip. ArXiv preprint, 1os/2222.110244
Harsh Trivedi. Niranjan Balasubramanian. Tushar Khot, and Ashish Sabharwal. 2022b. MuSiQue: Multi- hop questions via single- hop question composition. Transactions of the Association for Computational Linguistics, 10:539-554.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. ArXiv preprint, abs/2205.1191k
Xiaxia Wang, Tengteng Lin, Weiqing Luo, Gong Cheng, and Yuzhong Qu 2022a. Ckgse: A prototype search engine for chinese knowledge graphs. Data Intelli- gence, 4:41-65.

---

Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. 2022b. Self-consistency im- proves chain of thought reasoning in language mod- els. ArXiv preprint, abs/2203.11177
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed H Chi, Quoe V Le, Denny Zhou, al. 2022. Chain-of thouhtt prompting elicits rea- soning in large language models. In Advances in Neural Information Processing Systems.
Zhilin Yang, Peng Qi, Saizheng Zhang. Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christo- pher D. Manning. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answering. Proceedings of the 2018 Conference on Empiri- cal Methods in Natural Language Processing, pages Brussels, Belgium. Association for Com- putational Linguistics.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimban. 2023, Tree of thoughts: Deliberate problem solving with large language models. ArXiv preprint, abs/2305. 10601.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning acting language models. ArXiv preprint, abs/2210.03629
Oni Yoran, Tomer Wolfson, Ben Bogin, Uri Katz, Daniel Deutch, and Jonathan Berant. 2023. Answering questions by meta-reasoning over multiple chains of thought. ArXiv preprint, abs/2304.13007.
Jiajie Zhang, Shulin Cao. Tingjia Zhang, Xin Lv, Jiaxin Shi, Qi Tian, Juanzi Li, and Lei Hou. 2023. Rea- soning over hicrarchical question decomposition tree for explainable question answering. ArXiv preprint, abs/2305.

---

A Pilot Study for Our Confidence Mechanism
text-davinci-003 for fair comparison. We use the same format of prompt as the original paper. and select five paragraphs for each demonstration example in the prompt, including all the supporting paragraphs and several distractor paragraphs. The key hyperpurameter of IRCoT is K, the number of paragraphs to retrieve at each step. We select optimal K E {2,4, 6, 8} based on the performance the dev set.
Estimating the confidence levels associated with the responses of LLMs is an important research topic. In the existing literature, methods can be grouped into three categories: 1) logits-based meth- ods that focus on the probabilities derived from model logits; 2) verbalized confidence that di- rectly asks a model to output its confidence; 3) consistency-bart based methods that yield multiple re- sponses and use consistency as surrogate for con- fidence.
Table shows that the answer Fl results re- implemented by us are slightly lower than that of the original paper. We think the gap is due to two reasons: (1) the context size of text-davinci-000 is only half of that of podde-dvvnnc--ee 8 112)), so we can only use at most 5 demonstration examples in the prompt. while the original paper uses 15. (2) As shown in Table 7, the RMM2-based retriever used in the original paper has higher recall of supporting paragraphs than our implemen- tation on MuSiQue and 2 2WikiMQA. Here the recall is computed according to 15 retrieved paragraphs using the original question as the query.
Before initiating the reasoning framework, we first conducted a pilot study to investigate whether our explanation logits-based confidence is effective. As shown in Table 5, we compare different confi- dence calibration methods. For each method, given a question, we query LLMs multiple times (decode response with greedy decoding, and sample an- other four with temperature 0.7), calculate the confidence score for each response, and take the most confident one as the final answer. Better an- swer Fl indicates better confidence calibration. We randomly sampled 500 questions from HotpotQA, and 500 from MuSiQue to conduct the pilot study, Answer Fl results show that our explanation logits- based confidence outperforms others, including the model itself estimating its uncertainty in language, and taking answer tokens as part of scoring.
(4097 v.s.
C.2 Implementation Details of Self-Ask
Self-Ask (Press et al., 2022) uses text -ext-divinc and Google Search the original paper, and we re-implement it with text text-davinci-001 and BM25-based retriever. We follow Yoran et al. (2023) to prepend newly retrieved paragraphs to the original question. We use the same format of prompt Yoran et al. (2023), and select five paragraphs for each demonstration example in the prompt, including all the supporting paragraphs and several distractor paragraphs. We retrieved top- K paragraphs for each sub-question, where K E {3, 5, 7} is selected based on the dev set.
In addition, we found that the average confidence score for the 500 examples in HotpotQA is -0.142, and the average confidence score for ex- amples with answer F1 1.0 is -0. 109, and that of examples with answer F1 0.0 is -0.176. The low confidence of incorrect answers and high score of correct ones indicates the effect of our method.
B Statistics of Test Sets
We use test sets provided by IRCoT (Trivedi et al., 2022a) for HotporQA, MuSiQue, and 2WikiMQA. Specifically, they randomly sampled 500 questions from the original dev set each dataset as the test set. The numbers of different types of questions in the test set of each dataset are listed in Table 9.
C.3 Implementation Details of ProbTree with Self-consisitency
Suppose we respectively sample n CoTs in Closed- book, Open-book, and Child-aggregating QA for each node in the query tree. We set the temperature t 0 for the first CoT and t 0.7 for the other 1 CoT's Then we collect answers after "So the answer is:" from all these 3n CoTs, and select the most frequent one as the optimal answer. If there are multiple most frequent answers with the same number of occurrences, we randomly select one.
Implementation Details of Baselines
C.1 Implementation Details of IRCoT
IRCoT (Trivedi et al., 2022a) uses code-davinci-002 as the backend LLM in the original paper, and we re-implement with

---

Datasets
logits (explanation)
logits (explanation ans)
logits (ans)
verbalize
consistency
vanilla
HotpotQA 47.8
47.5
43.7
44.5
47.6
47.1
MuSiQue 26.0
25.4
24.1
22.0
25.7
25.2
Table Pilot study to investigate whether our explanation based confidence is effective. Logits (explanation ans) means answer tokens themselves part of the scoring.
Method
QA
MuSiQue
2WikiMQA
E Details of Other Recent Approaches
IRCaT (ours)
60.2
34.2
63.8
IRCoT (Trivedi et al., 2022a)
61.2
35.5
65.2
We introduce the details of other recent approaches. Their results are not generally aaples-to-apples and we report them qualitative reference points. ReAct (Yao et al., 2022) interleaves reasoning. searching for information (action), and collect- ing retrieved knowledge (observation), until reach- ing the action of finalizing an answer. ITER- RETGEN (Shao et al., 2023). ITER- RETGEE leverages the CoT output from the previous it- eration as the query to help retrieve more rele- vant knowledge, and outputs new CoT output in the next iteration. MCR (Yoran et al., 2023). MCR meta-reasons
ProbTree
64.1
41.5
71.8
Table 6: Answer F1 results of IRCoT re- re-implemented by us, IRCoT in the original paper, and ProbTree.
HotpotQA
MuSiQue
2WikIMQA
IRCoT (ours)
64.2
37.5
53.7
IRCoT (Trvedi et al. 2022a)
61.5
44.6
68.1
Table 7: Recall of BM25-based retriever for IRCoT implemented by us and the original paper.
Method
HotpotQA
MuSiQue
2WikiMQA
multiple chains of thought, mixes information between them, and selects the most relevant facts in generating an explanation and predicting the answer. We use the results ReAct and ITER-RETGEN implemented by Shao et al. (2023). They use text-davinci -003 as the back- end LLM, choose the first 500 questions from the development sets of each dataset for evaluation, and October 2017, December 2021, and December 2018 Wikipedia dump for HotpotQA, MuSiQue, and 2WikiMQA, respectively. They also fine-tune dense retriever via distillation. MCR (Yoran al., 2023) uses code-davinci-002 randomly samples 500 questions from the development set of each dataset for evaluation, and uses Google Search via SerpAPI as the retriever.
ProbTree
64.1
41.5
71.8
w/o ds'
63,9
41.3
71.6
w/o descendants
62.3
39.7
71.8
Table Answer Fl results of ProbTree without decom- position score (w/o ds') or retrieved paragraphs from descendants (w/o descendants).
D Additional Ablation Study
D.1 Effect of Decomposing Score
To show the effect considering question decom- posing certainty in reasoning, we remove ds from Eq. 9 and calculate s as:
lehildy Σ ==1
child; + 8.
(11)
oz
n
+
F Percentage of Different QA Strategies
For the percentage of sub-questions that were an- swered using Closed-bood bbok,, Open-bone bbok, and Child- aggregating QA respectively, we differentiate leaf and non-leaf questions because leaf nodes do not use Child-aggregating QA. As shown in Table 10, for non-leaf nodes, only less than 10% are an- swered using Closed-book QA, small part of them answered using Open-book QA, and most of them answered using Child-aggregating QA, which shows that LLMS rely more on question de- composition when facing complex questions. For Icaf nodes, LLMs rely on both internal and external knowledge, and rely more on external knowledge.
Table 8 shows that ignoring decomposing certainty causes a slight performance drop on all the datasets.
D.2 Effeet of Incorporating Retrieved Paragraphs from Descendants
In the Open-book QA module, the external knowl- edge for non-leaf node q¹ contains the re- trieved paragraphs for itself and all its descen- dants (Liq. 10). As shown in Table 8, removing retrieved paragraphs for descendants from q pprr causes a performance drop on both HotpotQA and MuSiQue.

---

HotpoiQA
MuSiQue
2WikiMQA
Overall
Bridge Comparison Overall
2hop
Shop
4hop
Overall Bridge Inference Comparison Sadge-Comparison
500
412
500
254
154
92
500
79
119
Table 9: Number of different types of questions in the test set of each dataset.
Leaf Nodes
Non-Icaf Nodes
Dataset
CB
OB
CB
OB
CA
HotpotQA
23.0%
77.0%
8.1%
31.7%
60.2%
MuSiQue
41.1%
58.9%
9.8%
18.8%
71.4%
2WikiMQA
17.7%
82.3%
1.3%
11.7%
87.0%
Table 10: Percentage of different QA strategies.
Question: Who is Philip Of Navarre's father-in-law?
Gold Answer: Louis France
G Prompts
Open-book Q4
Prompt:
To illustrate the prompt of ProbTree, we take 2WikiMQA an example. We take the 20 manually written question-CoT pairs from IR- CoT (Trivedi et al., 2022a) as the base to create prompts for query tree generation and Closed-booe book QA. For query tree generation, we use the ques- tions from IRCoT, and manually write query trees for them (Fig. 5). For Closed-book QA, since the exemplars from IRCoT only contain complex ques- tions, we add 4 exemplars for leaf nodes, and the final prompt contains 24 exemplars (Fig. 6). For Open-book QA, we mannualy write 3 annotations for leaf nodes (Fig. 7), and another 3 for non-leaf nodes (Fig. 8). For Child Child-aggregating QA, we man- nually write exemplars (Fig. 9). We also show the prompt (Fig. 10) for SD that is designed as an ablation study. Specifically, we take the 20 ques- tions from IRCoT and manually write sequential decompositions for them.
#4 Wikipedia Title: Philip Navarre
Text: ... and his wife and cousin, Joan II of Navarre
#6 Wikipedia Title: Blanche of Navarre, Queen France Text: Blanche of Navarre (1330- 1398) was Queen France as the wife King Philip VI... #8 Wikipedia Title: Joan of Navarre Text: she was the only surviving child of Louis X of France.
Question:
Who is Philip III Of Navarre's father-in-law?
Answer: Philip III of Navarre was married to Blanche of Navarre, Blanche of Navarre's 's father was King Charles III of Navarre. Thus, Philip III of Navarre's father-in-law is King Charles III of Navarre. So the answer is: King Charles III of Navarr.. (s.s: -0.101)
Child-ngggggating QA
Prompt:
Context:
is Philip Navarre married to? Joan
Navarre
father Joan of Navarre? Louis France.
Question:
Who Philip III Of Navarre's 's father-in-law?
Answer: Philip III OF Navarre married to Joan
Navarre is Louis X of France. Thus, the father-in-law of Philip III Of Navarre is Louis X of France. So the answer is: Louis X of France. (Sea: -0.033)
Navarre, The father of Joan
H
Case Study
We show a case in Table 11, which the Child- aggregating QA gives the right answer by summur- izing information from sub-questions, while Open- book QA makes a mistake due to large number of distractor paragraphs.
Table 11: An illustration of Open-book and Chid- aggregating QA for the root node. We mark mislcading retrieved paragraphs and corresponding wrong predic- tion red. In this case, Open-book QA makes mis- take due to large numbers distractor paragraphs. contrast, Child-age Shild-aggregating QA concisely summarizes information from sub-questions and gives the right an- swer confidently.

---

Please generate a hierarchical question decompasition tree (HQDT) with json format for given question. In this tree, the root node is the original complex question, each non-root node is sub-question of its parent. The Ieaf nodes are atomic questions that cannot be further decomposed.
Q: When did the director of film Hypocrite (Film) die?
A: ("When did the director of film Hypocrite (Tilm) die?": ["Who is the director of film Hypocrite (Film)?". "When did #1 die?"I].
Q: Do director of film Coolie No. I (1995 Film) and director of film The Sensational Trial have the same nationality?
A: ("Do director of film Coolie No. (1995 Film) and director of film The Sensational Trial have the same nationality?": I ('hhat is the nationality of the director of film Conlie No. I (1995 Film)?", "What is the nationality of the director of film The Sensational Trial?"]. "What is the nationality of the director of film Conlie No. I (1995 Film)?"; Wh is the director of film Cuolie No. 1 (1995 Film)?" ?". "What the nationality of #1?"). "What the nationality of the director of film The Sensational Trial?": ["Who is the director of film The Sensational Trial?", "What is the nationality of #1?"I). I].
Q: Are both Kurram Garhi and Trojkrsti located the same country?
A: ["Are both Kurram Garbi and Trojkrsti located in the same country?": : ("Which country is Kurram Garhi located in?", "Which
country is Trojkrsti located in?")..
Q: Who was born first out of Martin Hodge and Ivania Martinich?
A: ( ("Who was born first of Martin Hodge and Ivania Martinich?": ["When Martin Hodge born?", "When was Ivania Martinich born?"l).
Q: Which film came out first, The Night Of Tricks or The Genealogy?
A: ("Which film came out first. The Night Of Tricks or The Genealogy?": ["When was the film The Night Of Tricks published?".
"When was the film The Genealogy published?"]
Q: When did the director of film Laughter In Hell die?
A: ("When did the director of film die?"I].
In Hell die?": ["Who is the director of film Laughter In Hell?", "When did #1
Q: Which film has the director died later, The Gal Who Took the West or Twenty Plus Two?
A: ("Which film has the director died later. The Gal Who Took the West or Twenty Plus Two?": ["When did the director of film
The Gal Who Took the West die?". "When did the director of film Twenty Plus Two die?"]. "When did the director of film The Gal Who Thok the West die?": ['Who is the director of film The Gal Who Took the West?", "When did #1 die?"). "When did the director of film Twenty Plus Two die?": ["Who the director of film Twenty Plus Two?", "When did #1 die?")).
Q: Who Boraqchin (Wife Of ÄUgedei)'s father-in-law?
A: ("Who is Boragehin (Wife Of AUgedeiy's ' lithe--inllw??" ["Who is Boragehin married to?", "Who is the father of #1?"
Q: What is the cause of death of Grand Duke Alexei Alexandrovich Of Russia's 's mother?
A: ("What What is the cause of death of Grand Duke Alexei Alexandrovich Of Russia's 's mother?": [ ("Who is the mother of Grand
Duke Alexei Alexandrovich Of Russia?". "What is the cause of death of #1?")).
Q: Which film has the director died carlier, When The Mad Aunts Arrive or The Miracle Worker (1962 Filmj?
A: ("Which film has the director died earlier. When The Mad Aunts Arrive or The Miracle Worker (1962 Film)) ["When did film The Miracle Worker (1962 Film) die?"]. "When did the director of film When The Mad Aunts Arrive die?": [ ['Who is the director of film When The Mad Aunts Arrive?", "When did #1 die?")." "When did the director of film The Miracle Worker (1962 Film) dic?": ["Who is the director of film The Miracle Worker (1962 Film)?". "When did #1 die?"I}.
the director film When The Mad Aunts Arrive die?". "When did the director
Q: Which album was released carlier. What'S S Inside Cassandra's S Dream (Album)?
A: ("Which album was released carlier, What's ' Inside or Cassandra's 'S Dream (Album)?": ['When was the album What'S 'S Inside released?". "When was the album Cassandra's Dream (Album) released?")
Q: Are both mountains, Serre Mourene and Monte Galbiga, located in the same country?
A: ("Are both mountains, Serre Mourene and Monte Galbiga, located in the same country?": ['Which country was the mountain Serre Mourene located in?", "Which country was the mountain Monte Galbiga located in?"!].
Q: What is the date of birth of the director of film Best Friends (1982 Film)?
A: ("What is the date of birth of the director of film Best Friends (1982 Film)?": ("Who is the director of film Best Friends (1982
Film)?". "What the date of birth of #1?"]).
Q: Which film has the director born first, Two Weeks With Pay Chhailla Babu?
A: "Wichh film has the director born first. Two Weeks With Pay or Chhailla Babu?": ["When was the director of film Two film Chhailla Babu born?",, J.. "When was the director of film Two Weeks With Pay born?": ["Who is the director of film Two Weeks With Pay?", "When was #1 horn?"], "When was the director of film Chhailla Babu born?": ['Who is the director of film Chhailla Babu?", "When was #1 born"]]]
Weeks With Pay born?". "When was the director
Q: Who is the grandchild of Krishna Shah (Nepalese Royaly?
A: ("Who is the grandchild of Krishna Shah (Nepalese Royal)?": ["Who is the child of Krishna Shah (Nepalese Royaly?", "Who
is the child of #1?"]]-
Q: When was the director of film P.S. Jerusalem born?
A: (" ('When was the director of film P.S. Jerusalem born?"; ["Who is the director of film P.S. Jerusalem?", "When was #1
bomn"]]
Q: Which album was released more recently, If I Have to Stand Alone or Answering Machine Music?
A: ("Which album was released more recently, If I Have Stand Alone Answering Machine Music?"; ["When was the album
If Have to Stand Alone released?". "When was the album Answering Machine Music released?"]).
Q: Where did the director of film Maddalena (1954 Film) die?
A: "Where did the director of film Maddalena (1954 Film) die?": ["Who is the director of film Maddalena (1954 Film)?",
"Where did #1 die?"I}-
Q: When did the director of film The Boy And The Fog die?
A: ("When did the director of film The Boy And The Fog die?": ["hho is the director of film The Boy And The Fog?", "When
did #1 die?']].
Q: Are the directors of films The Sun of the Sleepless and Nevada (1927 film) both from the same country?
A: (" A"Are the directors of films The Sun of the Sleepless and Nevada (1927 film) both from the same country?": ["hhi country
is the director of film The Sun of the Sleepless from?". "Which country is the director of film Nevada ( (1927 film) from?"]. "Which country is the director of film The Sun the Sleepless from?": [ ('Who is the director film The Sun the Sleepless?" "Which country is #1 from?"). "Which country the director of film Nevada (1927 film) from?": ("Who is the director film Nevada (1927 film??, "Which country is #1 fIom?"|]
Figure 5: Instruction and exemplars for the 2WikiMQA query tree generation prompt.

---

Please answer the question by thinking step-by-step.
Q: When did the director of film Hypoerite (Film) die?
The film Hypocrite was directed by Miguel Morayla. Miguel Morayla died on 19 June 2013, So the answer is: June 2013, Q: Do director of film Coolie No. (1995 Film) and director of film The Sensational Trial have the same nationality?
A: Coolie No. 1 (1995 film) was directed by David Dhawan. The Sensational Trial was directed by Karl Freund. David Dhawan's nationality is India. Karl Freund's s nationality is Germany. Thus, they do not have the same nationality. So the answer is: no.
Q: Are both Kurram Garhi and Trojkrsti located in the same country?
A: Kurram Garhi is located in the country of Pukistun. Trojkrsti is located in the country of Republic of Macedonia. Thus, they
are not in the sume country. So the answer is: no.
Q: Who was born first out of Martin Hodge and Ivania Martinich?
A: Martin Hodge was born on 4 February 1959. Ivunia Martinich was born on 25 July 1995. Thus, Martin Hodge was born first.
So the answer is: Martin Hodge.
Q: Which film came out first, The Night Of Tricks or The Genealogy?
A: The Night of TTrccks was published in the year 1939. The Genealogy was published in the year 1979. Thus, The Night of Tricks came out first. So the answer The Night Of Tricks.
Q: When did the director of film Laughter In Hell die?
A: The film Laughter In Hell was directed by Edward I.. Cahn. Edward L., Cahn died on August 25, 1963. So the answer is:
August 25, 1963.
Q: Which film has the director died later. The Gal Who Took the West or Twenty Plus Two?
A: The film Twenty Plus Two was directed by Joseph M. Newman. The Gal Who Took the West was directed by Frederick de Cordova. Joseph M. Newman died on January 23, 2006. Fred de Cordova died on September 15, 2001. Thus, the person to die later from the two is Twenty Plus Two. So the answer is: Twenty Plus Two.
Q: Who is Boraqchin (Wife Of AUgedci)'s father-in-law.?
A: Boragehin is married to Aggedei Khan. AUgedii Khan's father is Genghis Khan. Thus, Boraqchin's 's father-in-law is Genghis Khan. So the answer is: Genghis Khan. A: The mother of Grand Duke Alexci Alexandrovich of Russia is Maria Alexandrovna. Maria Alexundrovnu died from tuberculoiis. So the answer is: tuberculosis.
Q: Which film has the director died earlier, When The Mad Aunts Arrive or The Miracle Worker (1962 Filmy?
When The Mad Aunts Arrive was directed by Franz Josef Gottlieb. The Miracle Worker (1962 film) was directed by Arthur Penn. Franz Josef Gottlieh died on 23 July 2006. Arthur Penn died September 28, 2010. Thus, the two, the director die carlier Franz Josef Gottlich, who directed When The Mad Aunts Arrive. So the answer When The Mad Aunts Arrive.
Q: Which album was released earlier, What'S S Inside or Cassandra's 'S Dream (Album))
A: What's Inside was released in the year 1995. Cassandra's is Dream (alhum) was released in the year 2008. Thus, of the two, the album to release carlier is What's Inside. So the answer is: What's Inside.
Q: Are both mountains, Serre Mourene and Monte Galbiga, located in the same country?
A: Serre Mourene is located in Spain. Monte Galbiga is located in Italy. Thus, the two countries are not located in the same
country. So the answer is: no
Q: What is the date of birth of the director of film Best Friends (1982 Film)?
The film Best Friends was directed by Norman Jewison. Norman Jewison was born on July 21, 1926. So the answer is: July
21, 1926.
Q: Which film has the director born first, Two Weeks With Pay or Chhailla Babu?
Two Weeks with Pay was directed by Maurice Campbell. Chhailla Babu was directed by Joy Mukherjee. Maurice Campbell was burn November 28, 1919. Joy Mukherjee was born on 24 February 1939. Thus, from the two directors, Chhailla Babu was born first, who directed Two Weeks With Pay. So the answer is: Two Weeks With Pay.
Q: Who is the grandchild of Krishna Shah (Nepalese Royal)?
A: Krishna Shah has child named Rudra Shah. Rudra Shah has a child named Prithvipati Shah. Thus, Krishna Shah has a grandchild named Prithvipati Shah. So the answer is: Prithvipati Shah.
Q: When was the director of film P.S. Jerusalem born?
A: P.S. Jerusalem was directed by Danae Flon. Danae Flon was born on December 23, 1970. So the answer is: December 23, 1970.
Q: Which album was released more recently, If Have to Stand Alone or Answering Machine Music?
I Have Stand Alone was published in the year 1991. Answering Machine Music was released the year 1999. Thus, of the two, the ulbum to release more recently is Answering Machine Music. So the answer is: Answering Machine Music.
Q: Where did the director of film Maddalena (1954 Film) die?
A: The film Muddalena is directed by Augusto Genina. Augusto Genina died in Rome. So the answer is: Rome.
Q: When did the director of film The Boy And The Fog die?
A: The director of The Boy and the Fog is Roberto GavaldA, sn. Roberto GavaldĀ, sn died on September 4. 1986. So the answer
is: September 4, 1986.
Q: Are the directors of films The Sun of the Sleepless and Nevada (1927 film) both from the same country?
A: The director of Sun of the Sleepless is Temur Babluani. The director of Nevada (1927 film) is John Waters. John Waters is from the country of America. Temur Bahluani is from the country of Georgia. Thus, John Walters and Temur Bahluani are not from the same country. So the answer is: no.
Q: Who is the director of film Hypocrite (Film)?
The film Hypocrite was directed by Miguel Morayta, So the answer is: Miguel Morayta.
Q: When did Franz Josef Gottlieb die?
A: Franz Josef Gottlieb died on 23 July 2006. So the answer is: 23 July 2006.
Q: When was the album What'S Inside released?
A: What's 's Inside was released in the year 1995. So the answer is: 1995.
Q: Which country was the mountain Serre Mourene located in?
A: Serre Mourene is Incated in Spain. So the answer is Spain.
Figure 6: Instruction and exemplars for the 2WikiMQA Closed-book Q4 prompt, including 24 examplars.

---

Given a question and the relevant Wikipedia text, answer the question and explain why. If you are unsure, answer Unknown.
#1 Wikipedia Title: Hypocrite (fil)
Text: Hypoerite (Spanish: Hipóerita..t) is 1949 Mexican thriller film directed by Miguel Morayta and starring Antonio Badú, Leticia Palma. Carmen Molina and Luis Beristäin. The film included the song "Hipócrita.. The film's 's sets were designed by Francisco Marco Chillet.
#2 Wikipedia Title: Who? (fil)
Text: Who? is 1974 film bused on the 1958 novel of the same name by Algis Budrys. It was directed by Jack Gold and stars Elliorr Gould, Trevor Howard, and Joseph Bova. Some video releases were retitled "The Man in the Steel Mask" or "Roboman", Wikipedia Title: Who Is the Guilty?
Text: Who is the Guilty? sometimes" Who is to Blame?") is a 1925 Georgian silent film directed by Alexandre Tsutsunava #4 Wikipedia Title: Who Is the Man?
Tex:: Who Is The Man?( 1924) is a British silent film drama directed Walter Summers. The film was based on the successful
French play" Daniel" by Louis Verneuil and is notable as the first screen appearance of John Gielgud. #5 Wikipedia Tirle: Deceit (1923 film)
Text: Deceit sometimes referred to as The Deceit) is a 1923 American silent black- and- white film. It is conventional melodrama directed by Oscar Micheaux. Like many of Micheauxá films," Deceit" casts cleries in a negative light. Although the film was shot in 1921, it was not released until 1923. It is not known whether the film currenlly survives, which suggests that is a lost film. The 1922 film" The Hypucrite" was shown within" Deceit" us a film within a film.
Q: Who is the director of film Hypocrite (Film)?
A: The film Hypocrite is directed by Miguel Morayta, So the answer is: Miguel Morayla.
#1 Wikipedia Title: Kurram Garhi
Text: Kurram Garhi is small village located near the city of Bannu, which is the part of Khyber Pukhtunkhwa province of Pukistaan. Its population upproximately 35000. Barren hills near this village. This village the burder of Kurram Agency. Other nearby villages are Peppal. Surwangi and Amandi Kala. #2 Wikipedia Title: Kurram Garhi Hydropower Plant
Text: Kurram Garhi Hydropower Plant( KGHPP) is a small, low- head, run- of- the- river hydroelectric power generation station of 4.0 megawatt generation capacity( four units of 1.0 MW cach), located at Kurram Garhi, a small town in Bannu KPK province of Pakistan on the flows of Kuchkot Canal from Kurram River. It small hydel power generating plant constructed and put in commercial operation on February 1958 with the Average Annual generating capacity of 17 million units( GWh) of least expensive electricity.
Wikipedia Title: Country
Text: " Country Is" is song written and recorded by American country music artist Tom T. Hall. was released in September 1974 as the second and final single from the album of the same name," Country Is", The song Halls fifth number country chart. The single went to number one for a single week and spent total of eleven weeks the country chart. #4 Wikipedia Title: Which Way Is Up?
the
Text: Which Way is Up? is 1977 American comedy film starring Richard Pryor and directed by Michuel Schultz. It is a remake of the 1972 Italian comedy film" The Seduction of Mimi". Richard Pryor plays three roles: an orange picker who has two women at the sume time, the orunge pickers father, and u reverend who gets the orange pickers wife pregnant.
#S Wikipedia Title; In Country
Text: Country 1989 American drama film produced and directed by Norman Jewison, starring Bruce Willis and Emily Lloyd. The screeppla by Frank Pierson and Cyuthia Cidre was based on the novel by Bobbie Ann Mason. The original music score was composed by James Horner. Willis carned best supporting actor Golden Globe nomination for his role. Q: Which country Kurram Garhi located in?
A: Kurram Garhi is located in the country of Pakistan. So the answer is: Pakistan.
#1 Wikipedia Title: Neer Shah
Text: Neer Rikram Shah, also known as Nir Shah, is Nepalese movie actor, a poet, lyricist, movie director, and husinessman.
He is related to the Royal family of Nepal. #2 Wikipedia Title: Gajraj Mishra Text: TRajguru Gajraj Mishra also spelled Gajaraj Mishra was a Nepalese politician, ambassador, diplomat and a royal priest p Shah dynasty. He was always inclined to his disciple Prince Regent Bahadur Shah of Nepal. Gujraj Mishra was disfavoured by his disciple King Pratap Singh Shah due to his support to Prince Bahadur Shah. He was also disfavoured by Pratap Singh's son Rana Rahadur Shah.
#3 Wikipedia Title: Princess Helen Shah of Nepul
Text: Princess Helen Shah of Nepal( September 21, 1926- September 12, 2008) was member of the former Nepalese royal family. She was the wife of Prince Basundhara of Nepal, a son of King Tribhuvan of Nepal and his second wife. Queen Ishwari. #4 Wikipedia Title: Krishna Shah (Nepulese royal)
Text: Krishna Shah (?-1661) was the king of the Gorkha Kingdom in the Indian subcontinent, present-day Nepal. He was the futher of Rudra Shah.
#5 Wikipedia Title: Ajaya Pratap Shah
Text: Ajay Pratap Shah( died September 12.? in Lucknow, India) was a Nepalese politician. helonging to the Rastriya Prajatantra Purty. In 1999 parliamentary election he was elected from the Kapilvastu- constituency, with 14091 votes. After the royal coup d' d'état February 2005, Shah went into exile India. After his death, RPP nominated his son, Abhisek Pratap Shah, to take his parliamentary seat in January 2008
Q: Who is the child of Krishna Shah (Nepalese Royal)?
A: Krishna Shah was the father of Rudra Shah. So the answer is: Rudra Shah.
Figure 7:
Instruction and examplars for the 2WikiMQA Open-book QA (leaf node) prompt, including 3 examplars.

---

Given a question and the relevant Wikipedia text, answer the question and explain why. If you are unsure, answer Unknown.
#1 Wikipedia Title: Hypocrite (film)
Text: Hypocrite (Spanish: Hipóerita...) is 1949 Mexican thriller film directed by Miguel Morayta and starring Antonio Badú, Leticia Palma, Carmen Molina and Luis Beristáin. The film included the song "Hipócrita". The film's 's sets were designed by Francisco Marco Chillet.
#2 Wikipedia Title: When the Legends Die
Text: When The Legends Dic is a 1963 novel, by Hal Borland, and Del.uxc Color film released in 1972 by Twentieth Century-For -Fxx.
#3 Wikipedia Title: Who Is the Guilty?
Text: Who is the Guilty? ( sometimes" Who is to Blame?") is a 1925 Georgian silent film directed by Alexandre Tsutsunava
#4 Wikipedia Title: Miguel Morayta
Text: Miguel Morayta( 15 August 1907 - 19 June 2013) was a Spanish film director and screenwriter. He directed 74 films between 1944 and 1978. At the outbreak of the Spanish Civil War. Morayta was a Spanish artillery officer. who joined the Republican side. After Francisco Franco's 's victory, he left Spain for France and Africa, finally arriving in Mexico in 1941, where he started his career. He was living in Mexico when he died aged 105.
#5 Wikipedia Title: Joselito vagabundo
Text: Joselito vagahundo(" Joselito Vagahond") as 1966 Mexican film. It stars Sara Garefa and is directed by Miguel Morayta. Q: When did the director of film Hypocrite (Film) die? A: The film Hypocrite was directed by Miguel Morayta. Miguel Morayta died 19 June 2013, So the answer is: 19 June 2013.
#1 Wikipedia Title: Kurram Garhi
Text: Kurram Garhi small village located near the city of Bannu, which is the part of Khyber Pakhtunkhwa province of Pakistan. Its population is approximately 35000. Barren hills are near this village. This village is the border of Kurram Agency. Other nearby villages are Peppal, Surwangi and Amandi Kala. #2 Wikipedia Title: Kurram Garhi Hydropower Plant
Text: Kurram Garhi Hydropower Plant( KGHPP) a small, low- head, run- of- the- river hydroclcctric power generation station of 4.0 megawatt generation capacity( four units 1.0 MW cach), located Kurram Garhi, small town in Bannu KPK province of Pakistan on the flows of Kuchkot Canal from Kurram River. It is a small hydel power generating plant constructed and put in commercial operation on February 1958 with the Average Annual generating capacity of 17 million units( GWh) least expensive electricity.
#3 Wikipedia Title: Trojkrsti
Text: Trojkisti is village in Municipality of Prilep. Republic of Macedonia.
#4 Wikipedia Title: All Men Are the Same
Text: All Men Are the Same is a 1994 Spanish comedy film directed by Manuel Gómez Pereira.
#5 Wikipedia Title: The Both
Text: The Both is an American musical duo consisting of Aimee Mann and Ted Leo, both of whom had longstanding musical
careers before beginning a collaboration in 2013. Their first album, self- titled" The Both", was released in April 2014.
Q: Are both Kurram Garhi and Trojkrsti located in the same country?
A: Kurram Garhi is located in the country of Pakistan. Trojkrsti is located in the country of Republic of Macedonia. Thus. they are not in the same country. So the answer is: no.
#1 Wikipedia Title: Krishna Shah (Nepalese royal)
Text: Krishna Shah (?-1661) was the king of the Gorkha Kingdom in the Indian subcontinent, present-day Nepal. He was the father of Rudra Shah.
#2 Wikipedia Title: Neer Shah
Text: Neer Bikram Shah, also known as Nir Shah, is Nepalese movie actor, poet, lyricist, movie director, and businessman.
He is related to the Royal family of Nepal.
#3 Wikipedia Title: Gajraj Mishra Text: Rajguru Gajraj Mishra also spelled Gajaraj Mishra was Nepalese politician, ambassador, diplomat and royal priest of Shah dynasty. He was always inclined to his disciple Prince Regent Bahadur Shah of Nepal. Gajraj Mishra was disfavoured by his disciple King Pratap Singh Shah due to his support to Prince Bahadur Shah. He was also disfavoured by Pratap Singh's 's son Rana Bahadur Shah.
#4 Wikipedia Title: Princess Helen Shah of Nepal
Text: Princess Helen Shah of Nepalç September 21, 1926 - September 12, 2008) was a member of the former Nepalese royal family. She was the wife of Prince Basundhara of Nepal, son of King Tribhuvan of Nepal and his second wife, Queen Ishwari.
#5 Wikipedia Title: Rudra Shah
Text: Rudra Shah (?-1673) the king of the Gorkha Kingdom in the Indian subcontinent, present-day Nepal. He was the father of Prithvipati Shah.
Q: Who is the grandchild of Krishna Shah (Nepalese Royal)?
A: Krishna Shah has child named Rudra Shah. Rudra Shah has child named Prithvipati Shah. Thus, Krishna Shah has grandchild named Prithvipati Shah. So the answer is: Prithvipati Shah.
Figure 8: Instruction and examplars for the 2WikiMQA Open-book QA (non-leaf node) prompt, including 3 examplars.

---

Given a question and a context, answer the question and explain why.
Context:
Who the director of film Hypocrite? Miguel Morayta.
When did Miguel Morayta die? 19 June 2013.
Question:
When did the director film Hypocrite (Film) die?
Answer:
The film Hypocrite was directed by Miguel Morayta. Miguel Morayta on June 2013. So the answer June 2013.
Context:
When was the director film Weeks With Pay born? November 28, 1919.
When was director film Chhailla Babu bor? 24 February 1939.
Question:
Which film has the director born first, Two Weeks With Pay or Chhailla Babu?
Answer:
The director of Two Weeks With Pay was born on November 28, 1919. The director of Chhailla Babu With Pay was born on 24 February 1939. Thus, Two Weeks With Pay has the director born first. So the answer is: Two Weeks With Pay.
Context:
Where is Phu Luong located? Vietnam.
Which country is Vietnam in? Southeast Asia.
Question:
Which country contains Phu Luong?
Answer:
Phu Luong located in the country Vietnam. So the answer is: Vietnam.
#
Context:
Who is the mother of Abraham Lincoln? Nancy Hanks Lincoln.
Who is the father of Naney Hanks Lincoln? James Hanks.
Who is the father of James Hanks? Joseph Hanks,
Question:
Who the maternal grandfather of Abraham Lincoln?
Answer:
The mother of Ahraham Lincoln is Nancy Hanks Lincoln. The father of Nancy Hanks Lincoln James Hanks. Thus, the maternal grandfather Abraham Lincoln is James Hanks, So the answer is: James Hanks.
Figure 9: Instruction and examplars for the 2WikiMQA Child-aggregating QA prompt, including 4 examplars.

---

Please decompose the question into sub-questions.
Q: When did the director of film Hypocrite (Film) die?
A: ["Who is the director of film Hypocrite (Film)?", "When did #1 die?"]
Q: Do director of film Coolie No. 1 (1995 Film) and director of film The Sensational Trial have the same nationality?
A: ('Who is the director of film Coolie No. 1 (1995 Film)?", "What the nationality of #12, "Who is the director of film The Sensational Trial?", "What is the nationality of #3?". "Are #2 and #4 the same country?"]
Q: Are hoth Kurram Garhi and Trojkrsti located in the same country?
('Which country Kurram Garhi located in?", "Which country is Trojkrsti located in?", "Are #1 and #2 the same country?"|
Q: Who was born first of Martin Hodge and Ivania Martinich?
A: ("When was Martin Hodge born?", "When was Ivania Martinich born?", "Martin Hodge was born on #1. Ivania Martinich
was born on #2. Which of they was born first?"]
Q: Which film came out first, The Night Of Tricks or The Genealogy?
A: [ ("When was the film The Night Of Tricks published?". "When was the film The Genealogy published?". "The Night Of
Tricks was published on #1. The Genealogy was published on #2. Which them came out first?"]
Q: When did the director of film Laughter Hell die?
A: ('Who is the director of film Laughter In Hell?", "When did #1 die?"]
Q: Which film has the director died later, The Gal Who Took the West or Twenty Plus Two?
A: ("Who is the director of film The Gal Who Took the West?", "When did #1 die?". "Who is the director of film Twenty Plus
Two?", "When did #3 die?". "The director of The Gal Who Took the West died on #2, The director of Twenty Plus Two died on #4. Which of these two film has the director died later?")
Q: Who is Boraqchin (Wife Of AUgedei)'s s father-in-lww?
A: ["Who is Boraqchin married to?". "Who is the father of #1?"]
Q: What is the cause of death of Grand Duke Alexei Alexandrovich Of Russia's 's mother?
A: ("Who is the mother of Grand Duke Alexei Alexandrovich Of Russia?", "What is the cause of death #1?"|
Q: Which film has the director died earlier. When The Mad Aunts Arrive or The Miracle Worker (1962 Film)?
A: ["Who is the director of film When The Mad Aunts Arrive?". "When did #1 die?". "Who is the director of film The Miracle Worker (1962 Film)?". "When did #3 die?". "The director of When The Mad Aunts Arrive died on #2. The director of The Miracle Worker (1962 Film) died on #4. Which of these two film has the director died carlier!"]
Q: Which album was released earlier. What'S 'S Inside or Cassandra's 'S Dream (Album)?
A: ["When was the album What'S S Inside released?", "When was the album Cassandra's 'S Dream (Album) released?", "What'S
Inside released on #1. Cassandra'S S Dream (Album) was released on #2. Which of them was released earlier?"]
Q: Are both mountains, Serre Mourene and Monte Galbiga, located in the same country?
A: ['hhich country was the mountain Serre Mourene located in?". "Which country was the mountain Monte Galbiga located
in?". "Are #1 and #2 the same country?")
Q: What is the date of birth of the director of film Best Friends (1982 Film)?
A: ["Who is the director of film Best Friends (1982 Film)?". "What is the date of birth of #1?"]
Q: Which film has the director horn first, Two Weeks With Pay Chhailla Bahu?
('Who is the director of film Two Weeks With Pay?". "When was #1 born?". . "Who the director of film Chhailla Babu?",
"When was #3 born?", "The director of Two Weeks With Pay was born on The director of film Chhailla Bahu was born
#4. Which of these two film has the director born first?"|
Q: Who is the grandchild of Krishna Shah (Nepalese Royaly?
A: ["Who is child of Krishna Shah (Nepalese Royal)?", "Who is the child of #1?")
Q: When was the director of film P.S. Jerusalem born?
A: ['Who is director of film P.S. Jerusalem?", "When was #1 boru?"]
Q: Which album was released more recently. Have to Stand Alone or Answering Machine Music? A: I ('When was the album If Have to Stand Alone released?", "When was the alhum Answering Machine Music released?", "I Have to Stand Alone was released on #1. Answering Machine Music was released on #2. Which of them was released more recently?")
Q: Where did the director of film Maddalena (1954 Film) die?
A: ["Who is the director of film Maddalena (1954 Film)?". "Where did #1 die?")
Q: When did the director of film The Boy And The Fog die?
A: ["Who is the director of film The Boy And The Fog?". "When did #1 die?")
Q: Are the directors of films The Sun of the Sleepless and Nevada (1927 film) both from the same country?
A: ['Who is the director of film The Sun of the Sleepless?". "Which country is #1 from?", "Who is the director of film Nevada
(1927 film)?", "Which country is #3 from?", "Are #2 and #4 the same country?"]
Figure 10: Instruction and examplars for the 2WikiMQA sequential decomposition generation prompt, including 20 examplars.


Reviews:
[{"review_id": "uF7oybKlrC", "reviewer": "Reviewer_3643", "summary": "", "questions": "A: It seems strange that the answer tokens themselves are not part of the scoring, is there a reason for this?\nB: Could there be a way for the system to recover from decomposition mistakes (e.g., subquestions that cannot be answered)", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad to hear that the reviewer finds our reasoning system useful and analyses insightful.\n\n### Confidence Scoring\n**Q:**\nThe scoring based on probabilities per token seems quite fragile, even if it's seemingly effective here. Could have some more analysis of this, and perhaps compared to an approach where the model itself estimates its uncertainty in language.\n\nIt seems strange that the answer tokens themselves are not part of the scoring, is there a reason for this?\n\n**A:**\nThank you for raising this question. Actually, estimating the\nconfidence levels associated with the responses of LLMs is an important research topic. In the existing literature, methods can be grouped into three categories:  1) **logits**-based methods that focus on the probabilities derived from model logits; 2) **verbalized** confidence that directly asks a\nmodel to output its confidence; 3) **consistency**-based methods that yield multiple responses and use consistency as a surrogate for confidence.\n\nBefore initiating the reasoning framework, we first conducted a pilot study to investigate whether our explanation logits-based confidence is effective. \nAs shown in the following table, we compare different confidence calibration methods. For each method, given a question, we query LLMs multiple times (decode one response with greedy decoding, and sample another four with\ntemperature t = 0.7), calculate the confidence score for each response, and take the most confident one as the final answer. Better answer F1 indicates better confidence calibration.\nWe randomly sampled 500 questions from HotpotQA, and 500 from MuSiQue to conduct the pilot study. Answer F1 results show that our explanation logits-based confidence outperforms others, including the model itself estimating its uncertainty in language, and taking answer tokens as part of scoring.\n\n\n\n|          | logits (explanation) | logits (explanation+ans) | logits (ans) | verberlize | consistency | vanilla\n|----------|:--------:|:-------:|:--------:| :--------:| :--------:| :--------:|\n| HotpotQA |   47.8  | 47.5   |   43.7 | 44.5 | 47.6 | 47.1\n| MuSiQue  |   26.0  |  25.4  |   24.1 | 22.0 | 25.7 | 25.2\n\n\n### Recovering from Decomposition Mistakes\n\n\n\n**Q:** Could there be a way for the system to recover from decomposition mistakes (e.g., subquestions that cannot be answered)\n\n\n**A:** Yes. The system can recover from decomposition mistakes. Because for each question, the most confident answer is selected from Closed-book QA (CB), Open-book QA (OB) and Child-aggregating QA (CA). For each QA strategy, LLMs have the chance to output a correct answer even if the decomposition is wrong. The correct answer can be selected as the final answer because its confidence score is often higher compared with the wrong ones. Specifically, CB does not rely on decomposition. OB reasons with the retrieved paragraphs for itself and its descendants. Wrong descendant due to decomposition mistake will cause irrelevant retrieved paragraphs, and OB can recover from it. CA can also\nrecover from wrong decompositions because LLMs can extract useful information from child information and output a correct answer (a concrete example is shown in Table 3 in the paper).", "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": "Shows a potentially useful way of incorporating multiple strategies into a reasoning system. Gets good scores versus comparable systems. \n\nUseful analyses and ablations, giving insights into the performance", "reasons_to_reject": "Possibly not enough novelty to warrant acceptance.\n\nThe scoring based on probabilities per token seems quite fragile, even if it's seemingly effective here. Could have some more analysis of this, and perhaps compared to an approach where the model itself estimates its uncertainty in language.", "questions_to_authors": "A: It seems strange that the answer tokens themselves are not part of the scoring, is there a reason for this?\nB: Could there be a way for the system to recover from decomposition mistakes (e.g., subquestions that cannot be answered)", "paper_topic_and_main_contributions": "The paper utilizes various prompts to answer multi-hop questions (HotpotQA, MusiQue, 2WikiMultihopQA). It first generates subquestions which might form a tree (where answers of some questions feed into other questions), and then answers each subquestion by traversing the tree.\n\nThe main innovation over similar previous work is that each subquestion is answered using 3 different strategies, and each strategy is scored and the best one is used. The three strategies are: 1) Child-aggregate: Show child questions and answers in the tree as context, 2) Open-book: Context is retrieve snippets for the subquestions from a corpus, 3) Closed-book: No context (rely on models own knowledge).\n\nEach answer is preceded by an explanation. The main way of scoring each answer is the average log-probability of each token in the explanation. The child-aggregate strategy also includes average token scores for the decomposition and the child answers.\n\nAnswer F1 scores are compared with various baselines and existing models, showing general gains, some of them quite substantial. There is also some analysis breaking down performance per reasoning type, ablation of many of the components (leave out one of the strategies, pick random answers rather than higher scoring one). Also, there's a useful error analysis breaking down the types of errors being made, including a small (~5-15%) number attributed to the confidence scoring not selecting the correct answer.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zRAsPKA37J", "reviewer": "Reviewer_M8kU", "summary": "", "questions": "1. Please comprehensively explain the difference between the contributions in this paper and [1].\n2. Can some simple semantic parsing method be used to decompose the question? Why is the maximum number of nodes in each layer set to 3? Can different numbers be used for decomposition?\n3. Can uncertainty estimation of the intermediate answers be used with other reasoning frameworks, such as sequential decomposition?\n4. Does the uncertainty truly reflect the quality of the decomposition and the accuracy of the answers? Case studies or statistics of the consistency between incorrect answers and uncertainty scores are desired.\n5. Why child-aggregation reasoning can generate accurate answers with incorrect sub-question context shown in Table 3?\n\n[1] Zhang, Jiajie, et al. \"Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering.\"  ACL 2023.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad to hear that the reviewer finds our experiment results are significant and the presentation is easy to follow.\n\n### Contribution\n**Q**: Please comprehensively explain the difference between the contributions in this paper and [1].\n\n**A**: We admit that reasoning on tree-like computation graphs has been proposed before. It's a research methodology whose core is to derive tree-like computation graphs and reason with uncertainty estimation. In this paper, we are exploring whether this methodology can help improve LLMs' ability, i.e., reduce hallucination in model generation, which is a crucial issue for today's LLMs.\n\nSpecifically, we propose to integrate internal (parametric) and external (non-parametric) knowledge in a probabilistic way for LLMs. And during realization, due to the characteristics of LLMs, several unique challenges are posed: 1) how to estimate the answer confidence with the LLM itself is an open problem; 2) how to propagate confidence scores globally when there are local mistakes caused by inaccurate in-context learning such as wrong decompositions.\n\nFor 1), given the observation that LLMs tend to be well-calibrated and low probability often indicates a lack of knowledge, 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, which is demonstrated effective with various experimental results. For 2), we propose Child-aggregating QA to globally reason with the information from child nodes which makes recovering from local mistakes possible, such as wrong question decompositions and incorrectly answered sub-questions. Reasoning with Child-aggregating QA, Open-book QA and Closed-book QA comprehensively reduces the hallucination and improves the reasoning abilities of LLMs significantly.\n\nFor the differences between [1] and our paper, there are 3 aspects: 1) **Confidence Quantifying**. [1] relies on supervisedly trained modules to give confidence, e.g., Longformer-large reading comprehension model pretrained on SQUAD. However, for LLMs, self-calibration is needed. 2) **Decomposition Accurary**. [1] uses large-scale of (question, sub-question) parallel data to supervisedly train a question decomposer with high accuracy. However, for LLMs, question decomposition is conducted with few-shot prompting, which is not that accurate. How to recover from the local wrong decomposition is a unique challenge. 3) **Question Type Coverage**. [1] uses 6 predefined symbolic functions to solve specific types of questions, such as [Verify] and [Count]. The coverage is limited, and some questions cannot be represented by the predefined functions (\"In between Atsushi Ogata and Ralpha Smart who graduated from Harvard College?\" in HotpotQA). For LLMs, the language understanding ability of LLMs.\n\n### Decomposing Method\n**Q**: Can some simple semantic parsing method be used to decompose the question? Why is the maximum number of nodes in each layer set to 3? Can different numbers be used for decomposition?\n\n**A**: Semantic parsing based decomposition is not suitable in our framework. Semantic parsing translates questions into logical forms such as SPARQL and lambda-calculus, which is mainly used in KBQA. In our paper, we need natural language to serve as queries for retrieving information from document corpora, and serve as prompt to query LLMs. Therefore, semantic parsing which outputs logical forms is not suitable.\n\nNote that we set the maximum number of child nodes for each node to be 3 (instead of each layer). This is because complex questions can be decomposed into 2 or 3 simper sub-questions, and questions with more than 3 hops can be recursively decomposed (see Figure 2 in our paper for example).\n\n### Uncertainty Estimation\n**Q1**: Can uncertainty estimation of the intermediate answers be used with other reasoning frameworks, such as sequential decomposition?\n\n**A2**: Yes, Section 5.2.1 and the \"SD\" in Table 2 in our paper is just the case of sequential decomposition with our uncertainty estimation method. \nThe following table contains the performance of sequential decomposition (SD) from our submitted paper:\n\n|          | HotpotQA | MuSiQue | 2WikiMQA |\n|----------|:--------:|:-------:|:--------:|\n| OneR     |   53.2   |  25.7   |   48.1   |\n| IRCoT    |   60.2   |  34.2   |   63.8   |\n| Self-Ask |   49.4   |  33.4   |   66.6   |\n| SD       |   51.7   |  39.0   |   69.2   |\n| ProbTree (ours) |   64.1   |  41.5   |   71.8   |\n\nWe can see that SD outperforms Self-Ask on HotpotQA and outperforms all the baselines except ProbTree on MuSiQue and 2WikiMQA, showing that our uncertainty estimation is also useful for other reasoning frameworks.\n\n**Q2**: Does the uncertainty truly reflect the quality of the decomposition and the accuracy of the answers? Case studies or statistics of the consistency between incorrect answers and uncertainty scores are desired.\n\n**A2**: We manually analyze 150 errors (50 per dataset) output by ProbTree and find only a small (~5-15%) number attributed to the uncertainty estimation not selecting the correct answer. The ablation study (lines 476-490) also proves our uncertainty estimation method can better truly reflect the quality of LLM outputs compared with self-consistency.\n\nActually, before initiating the reasoning framework, we first conducted a pilot study to investigate the uncertainty estimation. We wanted to investigate the incorrect answers and their uncertainty scores. We randomly sampled 500 questions from HotpotQA, and found that the average confidence score for all the 500 examples is ***-0.142***, and the average confidence score for examples with answer F1 ***1.0*** is ***-0.109***, and that of examples with answer F1 ***0.0*** is ***-0.176***. The low confidence of incorrect answers and high score of correct ones indicates the effect of our method.\n\n### Child-aggregation Reasoning\n**Q**: Why child-aggregation reasoning can generate accurate answers with incorrect sub-question context shown in Table 3?\n\n**A**：Evidence has shown that LLMs possess the ability to recognize what is true or useful in the given context to some extent [2][3].  For example, [2] shows LLMs are calibrated on multiple choice questions and True/False tasks. [3] shows that LLMs have the ability to select useful information from multiple reasoning chains (some chains may be wrong), aggregate them and output the final right answer. \n\nIn our case, LLMs can also select useful and relevant information from (sub-question, answer) pairs and based on that further reason. For example, the correct decomposition of ***q0*** should be <***q1***,  ***q2***>. However, the LLM incorrectly decomposes it as <***q1***,  ***q2'***>. For Child-aggregating QA, since we give LLMs the original question ***q0*** as context, it knows that it should find which Canadian rock band had a drummer that was inducted into the Modern Drummer Hall of Fame. ***q2'*** indicates that Rush is the eligible band. Combined with the answer of ***q1***, LLM can give the accurate answer \"Rush\". Therefore, Child-aggregating QA meta-reasons with information from child nodes, and enables our ProbTree to recover from the wrong decomposition. \n\n|          |Detailed question | Answer |\n|----------|:--------:|:--------:|\n| q0    |   Which Canadian rock band released a song called \"Counterparts\" and had a drummer who was inducted into the Modern Drummer Hall of Fame?   | Rush |\n| q1    |   Which Canadian rock band released a song called \"Counterparts\"?   | Rush |\n| q2    |   Which Canadian rock band had a drummer who was inducted into the Modern Drummer Hall of Fame?   | Rush |\n| q2'   |   Which drummer of Rush was inducted into the Modern Drummer Hall of Frame?  | Neil Peart |\n\n\n### Answer Extraction\n**Q** The process of extracting the intermediate answers for the next step of reasoning is not discussed. \n\n**A**: The output of LLMs is in the format \"{explanation} So the answer is: {answer}\", so the answer can be extracted programmatically after \"So the answer is: \". We will add the details in our revision.\n\n\n\n\n[1] Zhang, Jiajie, et al. \"Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering.\" ACL 2023.\n\n[2] Kadavath, Saurav, et al. \"Language models (mostly) know what they know.\" arXiv preprint arXiv:2207.05221, 2022.\n\n[3] Ori, Yoran, et al. \"Answering Questions by Meta-Reasoning over Multiple Chains of Thought\". arXiv preprint arXiv:2304.13007, 2023.", "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": "1. It presents a probabilistic tree-of-thought reasoning framework, which not only decomposes the reasoning process on complex questions into a tree structure but also considers the uncertainty of the intermediate answers to eliminate the error.\n2. It presents a self-evaluation-based method to quantify answer confidence.\n3. The experiment results are significant and promising. The overall presentation of the paper is good and easy to understand.", "reasons_to_reject": "1. The idea of question decomposition, uncertainty estimation, and even the notations used in this paper are highly similar to reference [1], which diminishes the contributions and novelties of this paper.\n2. The decomposition of the questions could be further discussed. Can we just use some simple semantic parsing method to decompose the question?\n3. The calculated uncertainty could be further analyzed. Whether the uncertainty can truly reflect the quality of the decomposition and the accuracy of the answers is still unclear.\n4. The process of extracting the intermediate answers for the next step of reasoning is not discussed.\n\n[1] Zhang, Jiajie, et al. \"Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering.\"  ACL 2023.", "questions_to_authors": "1. Please comprehensively explain the difference between the contributions in this paper and [1].\n2. Can some simple semantic parsing method be used to decompose the question? Why is the maximum number of nodes in each layer set to 3? Can different numbers be used for decomposition?\n3. Can uncertainty estimation of the intermediate answers be used with other reasoning frameworks, such as sequential decomposition?\n4. Does the uncertainty truly reflect the quality of the decomposition and the accuracy of the answers? Case studies or statistics of the consistency between incorrect answers and uncertainty scores are desired.\n5. Why child-aggregation reasoning can generate accurate answers with incorrect sub-question context shown in Table 3?\n\n[1] Zhang, Jiajie, et al. \"Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering.\"  ACL 2023.", "paper_topic_and_main_contributions": "This paper proposes a novel approach to solving complex questions with probabilistic CoT reasoning over a query tree, eliminating the negative retrieval problem and limited sight of chain-based methods. The paper makes several contributions, including exploring the LLM's capacity to decompose complex questions and proposing the probabilistic tree-of-thought reasoning approach. It brings uncertainty into reasoning and proposes a self-evaluation-based method to quantify answer confidence. Then, different kinds of reasoning mechanisms can be integrated into a unified framework and automatically chosen to conduct reasoing. Last, it conducts comprehensive experiments and evaluates the effect of each component with careful ablation studies.", "excitement": 2, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "N/A", "Typos_Grammar_Style_and_Presentation_Improvements": "N/A"}, "extra_text": {}}, {"review_id": "WGwBpic28C", "reviewer": "Reviewer_ahcZ", "summary": "", "questions": "Q1: on the error analysis: did you find any errors caused by questions which included wrong assumptions, e.g., who was the first female president of the united states? Are there many of those and how would your model handle them?\nQ2: Curious about the % of subquestions that were answered using CB, OB, and CA respectively.\nQ3: Will you publish the code and data for reproducibility?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very pleased to know that the reviewer finds our work is well-motivated and intuitive with sufficient experimental results.\n\n### Questions with Wrong Assumptions\n**Q**: Did you find any errors caused by questions that included wrong assumptions, e.g., who was the first female president of the united states? Are there many of those and how would your model handle them?\n\n**A**: Yes, our model can handle them, though the benchmark datasets themselves don't contain such questions. Our model can say \"none\" or \"unknown\" for questions with wrong assumptions. For the question *\"who was the first female president of the united states?\"*, our system chooses the most confident one from CB and OB shown below, so the final answer is \"none\".\n\n| QA Strategy         | Output | Confidence |\n|----------|:--------:|:--------:|\n| CB   |   The first female president of the United States has not yet been elected. So the answer is: none.  | -0.137 |\n| OB    |   Unknown. The Wikipedia article \"Female president of the United States in popular culture\" does not mention any real-life female presidents of the United States, only fictional ones. So the answer is: Unknown.| -0.269 |\n\n### CA, CB, OB Percentage\n**Q**: Curious about the % of subquestions that were answered using CB, OB, and CA respectively.\n\n**A**: Thank you for your question. The results are as follows:\n\n|          | leaf questions |       | non-leaf questions |       |       |\n|----------|:--------------:|:-----:|:------------------:|:-----:|:-----:|\n|          |       CB       |   OB  |         CB         |   OB  |   CA  |\n| HotpotQA |      23.0%     | 77.0% |        8.1%        | 31.7% | 60.2% |\n| MuSiQue  |      41.1%     | 58.9% |        9.8%        | 18.8% | 71.4% |\n| 2WikiMQA |      17.7%     | 82.3% |        1.3%        | 11.7% | 87.0% |\n\nWe differentiate leaf and non-leaf questions because leaf nodes do not use CA. For non-leaf nodes, only less than 10% are answered using CB, a small part of them are answered using OB, and most of them are answered using CA, which shows that LLMs rely more on question decomposition when facing complex questions that need multi-step reasoning. For leaf nodes, LLMs rely on both internal and external knowledge, and rely more on external knowledge. We will add this investigation to our revision.\n\n### Publish Codes\n**Q**: Will you publish the code and data for reproducibility?\n\n**A**: Yes, we will publish the codes and data upon acceptance.\n\n### More Intrinsic Experiments\n**Q**: Lack of intrinsic experiment with various instantiations of the ProbTree method's parameters, e.g., choice of LLM, choice of retrieval model, choice of external knowledge source.\n\n**A**: Thank you for your advice. The main reason we choose them is to follow the tradition of previous works for fair comparison. We will add more experiments with different models, retrivers and external knowledge sources in our revision.", "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": "- The problem is well-motivated.\n- The methodology is intuitive and well-explained.\n- Experiments against SOTA methods seem sufficient.\n", "reasons_to_reject": "- Lack of intrinsic experiment with various instantiations  of the ProbTree method's parameters, e.g., choice of LLM, choice of retrieval model, choice of external knowledge source.", "questions_to_authors": "Q1: on the error analysis: did you find any errors caused by questions which included wrong assumptions, e.g., who was the first female president of the united states? Are there many of those and how would your model handle them?\nQ2: Curious about the % of subquestions that were answered using CB, OB, and CA respectively.\nQ3: Will you publish the code and data for reproducibility?", "paper_topic_and_main_contributions": "Recently, chain-of-thought (CoT) has been used to improve the results in tasks like question answering, trough converting a complex question into a number of simpler subquestions. This work argues two main limitations in this solution: (1) its sequential nature will result in incorrect final answers due to at least 1 incorrect answer in the chain of subquestions and (2) any mistake in the retrieval step will likely cause a mistake in the proceedings steps (misleading the reasoning).\n\nThis paper proposes replacing CoT reasoning with Tree-of-thought reasoning, where a complex question is decomposed into a tree. Every node in the tree represents a subquestion. The process of answering starts at the bottom with leaf nodes (questions that cannot be further decomposed). Going up, subquestions are answered over LLMs using zero-shot prompts, external-knowledge-augmented prompts, or an aggregation from previous answers. Experiments show that this new methodology outperforms previous CoT methods. ", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "- Table 4 is not mentioned (referred to) in the text.\n- Line 879 typo"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes prompting strategies for multi-hop question answering on HotpotQA, MusiQue, and 2WikiMultihopQA. It generates a set of subquestions that forms a tree (i.e., answers to some questions feed into other questions) and then answers each subquestion by traversing the tree. The reviewers found the results convincing and the paper well-written. On the other hand, two reviewers noted similarities between the proposed approach and other approaches inspired by chain-of-thought prompting. Thus, they had lower excitement scores than soundness scores.
Decision: Accept-Findings