Allies: Prompting Large Language Model with Beam Search
Authors: Hao Sun
Xiao Liu
Yeyun Gong
Yan Zhang
Daxin Jiang
Linjun Yang
Nan Duan
Venue: EMNLP 2023 Findings (2023)
Keywords: Large Language Model
Question Answering
Beam Search

Abstract: With the advance of large language models (LLMs), the research field of LLM applications becomes more and more popular and the idea of constructing pipelines to accomplish complex tasks by stacking LLM API calls come true.
However, this kind of methods face two limitations: narrow information coverage and low fault tolerance.
In this work, we propose a novel method called ALLIES.
Given an input query, ALLIES leverages LLMs to iteratively generate new queries related to the original query, enabling an iterative reasoning process.
By iteratively refining and expanding the scope of the original query, ALLIES captures and utilizes hidden knowledge that may not be directly obtainable through retrieval.
We take zero-shot open-domain question answering (ODQA) as an application scene and evaluate ALLIES on the widely-used benchmarks, such as NQ, WebQ and TriviaQA.
The experimental results demonstrate that ALLIES significantly outperforms other zero-shot baselines, indicating its effectiveness in tackling those challenges.
Our code is available in https://github.com/microsoft/SimXNS/tree/main/ALLIES.

ALLIES: Prompting Large Language Model with Beam Search
Hao Sun'; Xiao Liu Yeyun Gong', Yan Zhang', Daxin Jiang', Linjun Yang', Nan Duan² Peking University, Microsoft Research Asia, Microsoft sunhao@stu. pku. edu. en, zhyzhy@01 eryzhy001@pk..o edu. cn, (xiaoliu2, yegong, (emnduuanemiccoooooooo. com
Abstract
access external corpora [Petroni et al., 2021J and utilizes retriever component for knowledge augmentation [Ram et al., 2023, Shi et al., 2023, Rashkin et al., 2021, Gao et al., 2022, Bohnet et al., 2022, Menick et al.. 2022] to improve their ability to provide comprehensive and accurate answers.
With the advance of large language models (LLMs), the research field of LLM applications becomes more and more popular and the idea of constructing pipelines accomplish com- plex tasks by stacking LLM API calls come true. However, this kind of methods face two limitations: narrow information coverage and low fault tolerance. In this work, we propose novel method called ALLIES. Given input query, ALLIES leverages LLMs to iteratively generate new queries related to the original query, enabling an iterative reasoning process. By iteratively refining and expanding the scope the original query, ALI.ES captures and lizes hidden knowledge that may not be directly obtainable through retrieval. We take zero- shot open-domain question answering (ODQA) application scene and evaluate ALLIES on the widely-use benchmarks, such as NQ. WebQ and TriviaQA. The experimental results demonstrate that ALLIES significantly outper- forms other zero-shot baselines, indicating its effectiveness in tackling those challenges. Our code is available in https: / /gi thub. com/ www.oosff/Si////////eeee http://reeeemai/ALLLLLEEE
However, despite the advancements, these methods still face two main limitations. (1) Firstly, narrow information coverage. When incorporating relevant information, the majority of these approaches only employ the query itself find or retrieve additional contextual information. Nonetheless, there are instances where responding to the query necessitates implicit knowledge that is related to the query but cannot be easily found solely using the given query. Consequently, the LLM may fail to acquire crucial information required for accurately responding to the query. (2) Secondly, low fault tolerance. Most of these methods follow the pipeline style, consisting of unique steps calling LLM APIS to generate responses to fulfill different needs in a single turn. It means that the model is expected to provide the correct response in single attempt. If an internal step fails, either the whole pipeline will face the risk of exception or the error will be propagated to downstream steps. Consequently, if the model fails find the necessary information or misinterprets the question, it may produce an incorrect response.
1 Introduction
With the emergence of large language models (LLMss [OpenAI, 2023, Scao al., 2022, Taylor et al., 2022, Chowdhery et al., 2022], researchers have explored their potential to generate responses, including answering queries with the in-context learning method [Brown et al., 2020]. In that method, the models are prompted with demon- strations such as human-selected query-respone pairs [Shoeybi al., 2019, Rae et al., 2021, Du al., 2022]. In this field, open-domain question answering [Chen et al., 2017, Izacard and Grave, 2021, 2020, Lazaridou et al., 2022] is an impor- tant and representative task that usually requires
To address the aforementioned limitations, we propose a novel approach called ALLIES that ap- plies a beam search strategy to generate responses. To better elaborate the method, we take open- domain question answering as the application scene and show an example of how ALLIES works in Figure 1. We adopt interactive and iterative process. Initially,
generate additional queries by asking the LLM what other information they require, based on the existing query-evidence pair. These generated queries serve as prompts for re- trieving relevant evidence from external sources.
This work was done during internship at MSRA. Xiao Liu is the corresponding author.

---

Original Question
when was the fins drbee's lieesse required?
Beare
Therefore, it can be inferree that the first drivers Eserse requined untlithe incroduction the Motor Car Act 1998
I.. in whitch country was the frus ditee's lcarse requires?))
1900.
Threshood
Gopylrmen
Complenaw
Beam (-
Ream
Based first regittation
The first driee's license mng uitemmene was mundased January 1904, the United singdom after the Motor Car Act 1959 received assent.....
f.r When did the United
f., Which mate
regitration Ondoow
Anewar Trand"
Kin Kingdom implement mondatory licensing for loar and what minimum qualitying age?
Arown
Jenuary 1906 0.3
of automooblees and what
Sort"
happen?]
Thvesholf Continue!
Thresbold Termivates
Figure 1: The example of answering question "when was the first driver's 's license required?" using ALLIES. The correct answer "January 1904".
The retrieved evidence is then added to the existing query-evidence pair. Next, we employ the LLM to respond to the initial query based on the augmented query-evidence pairs. Subsequently, we solicit the LLM to score the response. taking into account the query and the augmented query-evidence pair. This scoring process provides a measure of confidence in the generated response. The iterations continue until the score surpasses a predefined threshold, indicating sufficiently confident answer or the maximum depth of the tree traversal is reached. Once either of these conditions is fulfilled, the pro- cess terminates, and the answer outputted the final result. Responding to the query using ALLIES can be conceptualized as a tree traversal process, starting from the root node and progressing towards the leaf nodes, where each internal node in the tree represents a generated query.
make mistakes during the reasoning process. Any erroneous answers can be replaced by alternative answers, leading to more accurate and reliable sponses. This flexibility and adaptability contribute to the improved performance of our approach.
With the idea of ALLIES, we take zero-shot open- domain question answering (ODQA) as an applica- tion scene and evaluate ALLIES in several popular benchmarks. We conduct experiments on the NQ, TriviaQA and WebQ datasets. The results demon- strate that ALLIES significantly outperforms eral representative basclines while maintaining an acceptable cost. The case study further confirms the aforementioned advantages of our method.
In summary, our main contributions can sum- marized as follows:
1. We propose ALLIES, which leverages beam search strategy for response generation. Within this framework, tive and iterative process to enhance the accu- racy and robustness of the responses.
The main advantages of our method are two folds: (1) Firstly, we employ an extension strat- egy that extends the original question to multiple relevant questions, broadening the information cov- erage. This approach enables the LLM to gain a deeper understanding of the complex question by focusing on its constituent parts. By providing the LLM with more specific and targeted queries, we enhance their ability comprehend and process the question effectively. (2) Secondly, during the iterative process, we employ dynamic pruning technique that retains only the top B answers at each step. This increases the fault tolerance and robustness of our model by allowing the LLM to
adopt interac-
By extending the original question into multi- ple relevant questions and employing a dy- namic pruning technique, we improve the understanding of complex questions and in- crease the model's robustness. This allows for mistakes and alternative answers, resulting in more accurate and robust responses.
3. By taking zero-shot ODQA as an application scene, results on the NQ, TriviaQA and WebQ

---

datasets demonstrate the significant outperfor- mance of our method compared to baseline approaches. The case study further validates the advantages our approach.
Original Query
Beam Initialization
Beam 1
2 Related Work
Beam i
2.1 Open-Domain Question Answering
Bearn Expansion
Open-domain question answering is task that aims to provide answers questions without re- lying on specific context. This task can be cate- gorized into two settings: the open-book setting and the closed-book setting. In the ting, models [Chen et al., 2017, Izacard and Grave, 2021, 2020] typically consist of a retriever and a reader component. The retriever's role is to re- trieve relevant information from corpus such as Wikipedia [Chen al., 2017, Izacard and Grave, 2021] or web pages [Lazaridou et al., 2022, Nakano et al., 2021], while the reader focuses on answering the question based on the retrieved information.
Bear
bboo set-
Beam Pruning
Beam ( +
score meets the requirements
Bearn
Beam D
Termination
The final response with the highest score
Figure 2: The abstract process of ALLIES.
In the closed-book setting, models have no ac- cess to external corpus and have to rely on its model parameters to store all the information. Re- cent works find that large-scale language mod- els like T5 [Raffel al., 2020] can already an- swer questions without access to the external cor- pus. However, small-scale language models like RoBERTa [Liu et al., 2019] or GPT-2 [Radford et al., 2019] still face challenges in accurately an- swering questions in this setting.
(like works on QA with attribution) [Rashkin et al., 2021, Gao et al., 2022, Bohnet et al., 2022, Menick et al., 2022], which involve generating an answer using LLM and then refining with the help of verifier and retriever. The retrieved documents in the second stage serve as explanations for the generated answer.
3 Main Idea
The main idea of ALLIES is an interactive and it- erative process based on the widely-used search algorithm, beam search'. We use tuple with five slots to represent state, which is the element of beam. Each state (g, E, r,, consists of the original query q, the set of historical query comple- tions Q, the set of historical external evidences E, the current response r, and the estimated score s according to the current state. Assume the maxi- mum search depth is D, as illustrated in Figure 2, there are four main stages of ALLIES.
2.2 Large Language Model Enhanced Question Answering
recent times, there has been shift towards uti- lizing large language models (LLMs) for question answering [Chowdhery et al., 2022, Du et al., 2022, Liu et al., 20211. This research can be broadly cat- egorized into two lines of work. The first line of work focuses on preprocess methods [Borgeaud al.. 2022, Ram et al., 2023, Shi al.. 2023), which involve obtaining relevant documents and then utilizing LLMs to generate answers. Within this line work, there are two main approaches. Retrieve-thhen-read methods [Ram et al., 2023, Shi al., 2023] employ retrieval model to retrieve rel- evant documents, while generate-then-read meth- ods (Yu et al., 2022, Sun et al., 2022] fully leverage the capabilities of LLMs. Furthermore, researchers have demonstrated that combining generation and retrieval can lead to further gains [Yu et al., 2022]. The second line focuses on posthoc methods
3.1 Beam Initialization
In the beginning, we initialize the beam by asking the LLM to answer the query directly and by an- swering the query based on retrieved evidence. The retrieved evidence is obtained by first retrieving re- lated documents using the original query and then summarizing the documents. The generated tuples will be added the beam.
httpp://archhv..rrr//eaalllll/lp

---

Algorithm The process of generating the response to given query using ALLIES. Hyperparameters:
The maximum number K of generated queries, the maximum depth D of extension, the number N of documents from retrieval, the threshold S, and the beam size B.
Input: A query 4. Output: The answer
I: Clear the initial beam So = Ø
2: Answer the query with the model knowledge do = Answer 2.2).
3: Score the initial answer
Score(g, Ø3, 2, ou).
4: Add the current tuple to the initial beam So = So U (1y, 2, G, ao, so)).
The first seed.
5: Retrieve a evidence é1 = Retrieveegors: q, N).
6: Answer the query with the model knowledge
= Auswer(y, (4). (eil).
7: Score the initial answer
Score(g, (q). [e1] ..a). a1).
8: Add the current tuple to the initial beam So = So U (1u, (4). (e)).,
> The second seed.
9: for extension depth in 1 - D do
Extending within the depth.
10: Clear the heam for the current depth Sa 2.
11:
for each tuple in the previous beam (g. Q, E,
E S do Find the extended queries Q' As, 2 8, K).
b Iterate the previous tuples.
12:
13:
for each extended query q' E Q' do
> Try each possible extension.
14:
Retrieve evidence e' Retrieve (orr N...
15:
Try to answer with all the evidences a' Answerly Qu (e)EE
16:
Score the answer
Score(q, Q (4') ) ).)),
17:
Add the current extended tuple the beam Sa Sa Sa eu ( end for end for
18:
19:
20:
Trim the beam Sa by keeping only B tuples with largerest scores.
Prune the beam. Examine the exit.
21:
if tuple (g. 2, a, 8) Sa meets 2 S then
22:
Sp Sa.
23:
Exit the loop.
24:
end
25:
end
26:
Find the tuple (g. 2, Smax) E Sp with largest score smax and is the final answer.
3.2 Beam Expansion
Detailed Approach for ODQA
During the beam search process, we iteratively pop out one element from the front of the beam. For each element, we generate queries using the Ask Function. Then, for each generated query, we re- trieve relevant evidence and ask the LLM to answer the query based on both the retrieved evidence and the reasoning history. The LLM scores the gener- ated answers based on the reasoning history, and the newly formatted tuples are added to the end of the beam.
In this section, present the application of AL- LIES in ODQA, whose algorithm is illustrated in Algorithm There are four key functions used ALLIES, each serving a specific purpose. The cor- responding prompts are illustrated in Appendix C.
4.1 Answering Function Answer(g, Q,E)
This function takes as input the original query q. previously generated queries Q, and corresponding retrieval evidence E. It constructs a reasoning his-
tory (() e1) (92, (42,e2) ...}. by extracting 4 E Q and e E E. The function then asks the LLM to reason over the reasoning history and provide an answer to the original query.
3.3 Beam Pruning
At the end of each search depth, rank the newly generated answers and keep only top B answers.
4.2 Asking Function Ask(q, K)
Given the query 4. previously generated queries Q, corresponding retrieval evidence E, and the maximum number of queries to be generated K, this function constructs reasoning history ((g,ee)) (g2, e2) ,...) by extracting 4: and e, E E. The LLM is then asked reason over the reasoning history and determine what additional information it requires to answer the question. The function outputs the generated queries.
3.4 Beam Termination
If the highest-ranking answer in the beam has score exceeding the predefined threshold, the search process terminates, and the answer is out- putted. Otherwise, the process continues. If none of the elements in the beam reaches the thresh- old, we output the highest-scoring answer when the search reaches the maximum depth.

---

4.3 Retrieval Function Retrieve(Gori 9, N) Given the original query Gori, query q. and the max- imum number of documents to be retrieved N, this function uses a dense retriever to retrieve the top-N most similar documents. The LLM is then asked to extract the most useful information from the documents and summarize them, providing con- cise version of the retrieved information. We can also use LLM to directly generate background document like GENREAD [Yu et al., 2022] as an al- ternative and we call this function Retrieve' (qori).
architecture and performance of the dense retrieval component can be found in Appendix D. For the retrieval corpus, we use the Wikipedia dump from Dec. 20, 2018 as our retrieval corpus, encompass- ing collection of 21,015,324 documents.
5.3 Baselines
We compare our method with three groups of zero- shot QA baselines.
The first group comprises baselines that utilize retriever in their approach. This includes models such BM25 InstructGPT, Contriever + Instruct- GPT, Google + InstructGPT, and DPR + Instruct- GPT. These models employ a retriever to retrieve relevant information, which is then used by Instruct- GPT for answer generation. We obtained the re- ported performance numbers for these baselines from GENREAD (Yu et al., 2022].
4.4 Scoring Function Score(g, a)
Given the original query 9. previously gen- erated queries Q, corresponding retrieval evi- dence E, and the generated answer a from the LLM, this function constructs reasoning history { (91 e1), (92, e2) ....) by extracting qi E Q and G E E. The LLM is then asked to consider the rea- soning history and assess the probability that the candidate answer is the true answer. The function outputs score representing the confidence in the generated answer
The second group consists of baselines that do not utilize retriever in their approach. This group includes models such as GPT-3 [Brown al., 2020J, InstructGPT [Yu et al., 2022], FLAN [Wei et al., 2021J, GLaM [Du et al., 2022], and GEN- READ [Yu et al., 2022]. The reported performance numbers for these basclines are obtained from their respective original papers.
5 Experiment
5.1 Experimental Setting
The third group consists of models that we im- plemented ourselves, including directly answer, retrieve-then-ansser. GENREAD (Yu et al., 2022]. self-Ask [Press et al., 20221, and MCR [Yoran al., 2023]. Directly answer refers to the utilization of the LLM to directly answer the question. Retrieve- then-answel involves retrieval before answering. where we experimented with different numbers of retrieved documents and reported their correspond- ing performance, which is the simplified version of AL.IES without beam search. We implemented GENREAD, self-Ask, and MCR based on their code. However, we evaluate MCR only on the NQ dataset due to its high API cost. To ensure fairness among the baselines, we set the retrievers and LLM configurations to be the same.
In this section, we conduct experiments on three open-domain question-answering (QA) datasets: NQ [Kwiatkowski al., 2019], TriviaQA [Joshi et al., 2017], and WebQ [Berant et al., 2013]. Since we focus on zero-shot ODQA, we utilize only the complete test sets of NQ and WebQ. To reduce costs, we randomly selected 1000 samples from the TriviaQA test set for evaluation purposes. Original detailed statistics regarding these three datasets can be found in Appendix A.
We evaluate the performance using two met- rics: the exact match (EM) score and the Fl score. Specifically, a predicted answer considered cor- rect only its normalized form matches any of the normalized versions the answers provided in the answer list. The Fl score measures the word over- lap between the normalized version of the predicted answer and the answers in the provided answer list.
5.4 Main Results
We present the main results of our zero-shot exper- iments in Table 1. Based on these results, several observations can be made:
5.2 Implementation
We employ GPT-3.5-Turbo hosted by Azure Ope- nAl services as our large language model (LLM). As for the retriever component, we conduct sepa- rate finetuning for the NQ, TriviaQA, and WebQ datasets using their respective training sets. The
(1) Among the methods that utilize retriever, the choice of the retriever has significant impact on the model's performance. This indicates that the quality of the retrieved documents plays a crucial role in determining the overall system performance.

---

TriviaQA
WebQ
Method
EM
F1
EM
EM
*Method w/ retriever, reported by (Yi al., 2022].
BM25 InstructGPT
19.7
52.2
15.8
Contriever InstructGPT
18.0
51.3
16.6
Google InstructGPT
28.8
58.8
20.4
DPR InstructGPT
29.1
53.8
20.2
Method who retriever:
GPT-3 [Brown et al., 2020]
14.6
14.4
InstructGPT (Yu et al., 2022]
20.9
57.5
18.6
FLAN [Wei al., 2021]
18.6
55.0
GLaM [Du et al., 2022]
24.7
19.0
*Reimplmentation.
Directly Answer
20.8
32.5
49.2
60.8
20.8
37.5
Serrivve-Then-Anwwer (Top-1)
27.6
37.1
49.1
57.9
19.9
33.8
Serrive-TheenAAnwee (Top-5)
29.4
40.7
52.7
62.0
18.5
34.8
Retrieve-Then-AAsseer (Top-10)
28.2
39.5
52.4
61.6
17.4
32.9
GENREAD YYu al., 2022]
31.1
44.8
59.3
70.7
19.1
36.9
Self-Ask [Press al., 20221
26.4
36.5
59.4
68.5
15.1
29.5
MCR YYoan et al., 2023]
27.1
35.7
ALLIES
38.0
47.8
61.4
70.8
28.2
45.6
Table 1: Zero-shot open-domain QA performance.
NQ
WebQ
Method
NQ
TriviaQA
WebQ
Method
EM
F1
EM
AnsweA
59.2%
64.6%
70.0%
w/o Evidence
22.44
34.54
19.78
ALLIES
69.6%
72.9%
82.0%
Retrieve&Summary
38.00
47.82
27.26
43.13
GENREAD
37.98
49.47
28.20
45.49
Table 3: Query complementation analysis.
Table 2: Ablation study results on NQ and WebQ.
ablations by removing the evidence and using dif- ferent types of evidence, shown in Table
(2) Among the methods that do not use a re- triever, GENREAD achieves the highest perfor- mance. This demonstrates the effectiveness of the generate-then-read pipeline, where the model gen- erates background documents based on its knowledge without relying on external corpus. (3) Our implemented baselines, such as MCR and self-Ask, may not perform as well as expected. This is mainly because these methods heavily rely result parsing, which limits their generalizability to other applications.
Based on the results, we draw several conclu- sions: (1) When the evidence removed, we only provide the LLM with related queries without any background information. In this case, the model's 's performance drops significantly, which confirms that incorporating evidence into the model can greatly improve its understanding of the query. (2) When using the L.M--genrraedd background docu- ment (GENREAD), we observe that our model achieves slightly better results compared to re- trieval summary. This finding aligns with the observations made in GENREAD [Yu et al., 2022]. The improved performance can be attributed to the fact that LLMs have seen these related documents during pretraining, and the generated documents more specific and refined.
(4) Our proposed method, ALLIES, outperforms all existing baselines and achieves the highest per- formance on all datasets. This confirms the effec- tiveness of our model and demonstrates its superior- ity in open-domain question answering tasks. Ad- ditionally, method relies less result parsing, making it more generalizable other applications.
5.6 Query Complementation Analysis
By iteratively generating new queries to comple- ment the original query, our ALLIES is capable of expanding the information coverage of the original query and capturing hidden knowledge that may not be directly obtainable through retrieval with
5.5 Ablation Study
ALLIES, we utilize L.LMs ask questions and retrieve evidence based on those questions. To in- vestigate the effects the evidence, we conduct

---

Method
Retrieval Times
Times
Tokens Per API
Tokens Per Query
Directly Answer
54
1 54
GENREAD [Yu al., 2022]
342
1 342 342
Self-Ask [Press 2022]
490
x 490
Retriee--Then-Answar (Top-5)
744
1 744
ALLIES (GENREAD)
290
19 290 5510
ALLIES (Retrieval&Summary)
352
19 x 352 6688
MCR YYoaa al., 2023]
3029
x 3029 36348
Table 4: The effectiveness analysis of ALLIES.
the original query. To verify this, we conduct query complementation analysis that compares the
0.500
0.500
0.475
0.475
0.450
retrieval results of retrieve-then-answer and AL- LIES. Specifically, we record the percentage of retrieval results containing the ground truth answer and present the findings in Table 3.
0.425
0.425
0.400
0.400
0.375
0.375
0.350
0.350
- F1-Score
F1-Score
0.325
0.325
From the result, we can find that the retrieval results of ALLIES outperform those of retrieve- then-answer across all datasets, which verifies the effectiveness of ALLIES. By iteratively generating expand the knowledge scope of the retrieval results, leading more compre- hensive understanding of the original query and naturally producing better answers.
0.300
0.300
Depth
Figure 3: Performance comparison w.r. hyper-
parameters on NQ dataset.
new queries,
5.8 Human Evaluation
In this section, we conducted human evaluation to assess the accuracy of the scores generated by LLMs in our scoring function. We randomly se- lected 100 samples for score calculation and manu- ally verified the generated scores.
5.7 Effectiveness Analysis
In ALLIES, the use of multiple iterations of retrieval and generation may introduce additional costs. To analyze its effectiveness, we utilize the complete set of questions from the NQ dataset conduct the effectiveness analysis, which systematically com- pares the effectiveness of several methods.
Our findings indicate that 93 percent of the gen- erated scores align with the requirements for score calculation. This validation confirms the rationale behind using LLMs to calculate the scores. How- ever, we also observed some rare cases where two answers could both potentially address the ques- tion, but one of them was more accurate. In these cases, the LLMSs assigned the same score both answers, potentially leading to the selection of the less accurate answer. This issue can be attributed to the coarse nature of the prompt used for scor- ing, which can only assess the general relevance score. To address this issue, one possible solution for future work is to calculate the scores using an ensemble-and-we approach. This would involve asking LLMs to rank all possible answers instead of scoring them individually, which would poten- tially achieve more accurate and reliable scores.
As shown in Table 4, we can have the following conclusions: (1) Multi-turn QA methods, including ALLIES and MCR, incur higher model inference costs compared to single-turn QA methods such Directly Answer, GENREAD, Self-Ask, and Retrieve-Then-Answer This increase in cost is primarily due to the multiple API calls involved. (2) Among the multi-turn QA methods, although ALLIES requires more API calls, the token con- sumption per API significantly lower than that MCR, resulting in 1/6 inference cost of MCR. The higher token consumption per API in MCR can be attributed to the demonstration, which con- sumes substantial number of tokens. (3) Gen- crally, single-turn QA methods have lower token costs but exhibit lower model performance. In con- trast, ALLIES achieves significantly better model performance while maintaining an acceptable to- ken cost compared to MCR, thus demonstrating the effectiveness our method.
5.9 Hyper-parameter Study
Beam size and beam depth are two important param-pasameters our method. We study their effects by changing one parameter while fixing

---

Question: Who soldiers in ending the raid on the harper's ferry arsenal?
Answer: [Brevet Colonel Robert Lee,First Lieutenant Israel Greene]
Generated Query:
Whhat was the name of leader who led the soldiers in ending the raid on the Harper's is Ferry arsenal?
Who was the overall commander the soldiers who led the operation to retake the arsenal at Harpers Ferry?
Retrieved Evidence:
The soldiers who led the operation to retake the arsenal at Harpers Ferry were under the overall command of
Colonel Robert E. Lee.
Colonel Robert E. Lee was overall command of the operation to retake the arsenal, is possible that he may have played a role in leading the soldiers to end the raid.
Generated Answer with Score:
Answer 1: Colonel Robert E. Lee. Score: 0.8 v/
Answer 2: First Lieutenant Israel Greene. Score: 0.7
Model Predictions:
Directly Answer: John Brown Retrieve-Thhen-Aswaar John Brown ALLIES:: Colonel Robert E. Loc A
Question: When was the first driver's license required?
Answer: January 1904
Generated Query:
In which country was the first driver's license required?
When did the UK implement mandatory licensing for drivers and what was the minimum qualifying age? Retrieved Evidence:
The first drivers license requirement was mandated on January 1, 1904, in the United Kingdom after the Motor
Car Act 1903 received royal assent. The minimum qualifying age was set at 17, and every car owner... TTee first formal driving test in the UK was introduced with the Road Traftic Act 1934, which made compulsory testing for all new drivers. Prior to this, UK driving licenses were introduced by the Motor Car Act 1903...
Generated Answer with Score:
Answer I: January I, 1904, Score: 0.9
Answer 2: 1903. Score: 0.8
Model Predictions:
Directly Answer: 1903
Retrieve-Ther Answer:: July 1913
ALLIES: January 1904 V
Table 5: Case studies of the process of ALLIES.
other parameters and observing the performance trends, which are shown in Figure 3.
lieve this is mainly because, most cases, a beam depth of 2 provides the model with sufficient back- ground information. Increasing the beam depth beyond that only introduces more noisy informa- tion, which may complicate the generation of the correct answer for the LLM.
Study on Beam Size B. Beam size refers to the number of questions we keep at each layer during answer searching. From the results, we observe that the performance reaches its peak when the beam size (B) is set to 2. Values smaller or larger than this threshold lead to performance degradation. This is primarily because larger beam size pro- vides the model with more opportunities to make mistakes. However, when the beam size is too large, the model struggles to effectively rank the multiple candidates and select the best answer. Addition- ally, an increase in beam size also incurs additional computational costs.
5.10 Case Study
In this section, we provide examples that illus- trate the reasoning process of our ALLIES method, which is shown in Table 5. From these examples, we draw the following conclusions:
(1) The generated queries in our method are more specific and focused compared to the origi- nal query. This specificity improves the accuracy of the retrieval process, resulting in more accurate and relevant retrieved evidence. Consequently, the generated answers are of higher quality.
Study on Beam Depth D. Beam depth refers to the maximum depth our model can reach dur- ing answer searching. From the results, we find that the performance change during beam depth tuming is relatively small. This is mainly due to the carly stop mechanism implemented, where the answer searching can terminate before reach- ing the maximum search depth if the answer score surpasses the threshold. However, we also observe that when the beam depth is too large (c.g., 4), the model's performance starts to decline. We be-
(2) During the answer generation process, there might be instances where wrong answers are ini- tially predicted. However, our scoring function effectively assigns lower scores to these wrong an- swers based on the reasoning history. As result, the final output is the correct answer. This demon- strates the robustness of our method in handling potential mistakes and effectively filtering out in- correct answers.

---

6 Conclusion
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts. Paul Barham, Hyung Won Chung, Charles Sutton, Sebas- tian Gehrmann, et al. Palm: Scaling language model- ing with pathways. arXiv preprint wXxv:2204.02311 2022.
In this paper, we introduce ALLIES, novel method that addresses the limitations of using large lan- guage models (LLMs) for complex tasks. By lever- aging LLMs to generate related queries iteratively, ALLIES enables iterative reasoning and expands the original query's s scope to capture hidden knowledge, We evaluate ALLIES in zero-shot open-domain question answering and demonstrate its superiority over other baselines on benchmarks. As for future work, we plan to apply ALLIES in other complex tasks such as mathematical reasoning and so on.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems. 13:1877-, 2020.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catan- zaro. Megatron-lm: Training multi-billion parameter language models using model parallelism. arXiv preprint urXii:1909.0000 2019.
Limitations
In this work. we propose an effective response gen- eration method ALLIES. The limitations of the proposed method are as follows:
Jack W Rae, Sehastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides. Sarah Henderson, Roman Ring, Susan- nah Young, et al. Scaling language models: Meth- ods, analysis & insights from training gopher. arXiv preprimt arXiv:21122 14466,11,6666 2021.
(1) The computational cost of ALLIES is rela- tively high due the need for multiple API calls and document retrieval. This can limit its practical- ity in resource- resouree-intensive scenarios or systems with limited computational resources.
Nan Du, Yanping Huang, Andrew M Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, et al. Glam: Efficient scaling of language models with mixture- of-experts. In International Conference on Machine Learning, pages 5547-5569. PMLR, 2022.
(2) The operation of the model is based on the de- signed prompt. When applied to a new application scenario, crafting effective prompts may require additional time and effort from users.
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading wikipedia to answer ppma-domain questions. In Proceedings of the 55th Annual Meet- ing the Association for Computational Linguistics (Volume I: Long Papers), pages 1870-1879, 2017.
References
OpenAL. Gpt-4 technical report. OpenAI, 2023.
Teven Le Scao, Angela Fan, Christopher Akiki, EI- lie Pavlick, Suzana Ilie, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Mathhia Gallé, Jonathan Tow, Alexander M. Rush, Stella Biderman, Albert Webson, Pawan Sasanka Am- manamanchi, Thomas Wang, Benoît Sagot, Niklas Muennighoff, Albert Villanova del Moral, Olatunji Ruwase, Rachel Bawden, Stas Bekman, Angelina McMillan-Major Iz Beltagy, Huu Nguyen, Lucile Saulnier, Samson Tan, Pedro Ortiz Suarez, Vic- tor Sanh, Hugo Laurençon, Yacine Jernite, Julien Launay, Margaret Mitchell, Colin Raffel, Aaron Gokaslan, Adi Simhi, Aitor Soroa, Alham Fikri Aji, Amit Alfassy, Anna Rogers, Ariel Kreisherg Nitzav, Canwen Xu, Chenghao Mou, Chris Emezue. Christopher Klamm, Colin Leong, Daniel van Strien, David Ifeoluwa Adelani, and et al. BLOOM: 176b- parameter open-aceess multilingual language model. CoRR, abs/2211.08 1.05100.0000.. 2022.
Gautier Izacard and Edouard Grave. Leveraging pas- sage retrieval with generative models for open do- main question answering. In EACL 2021, pages 874- 880, 2021.
Gautier Izacard and Edouard Grave. Distilling knowl- edge from reader retriever for question answering. In International Conference on Learning Representa- tions, 2020.
Angeliki Lazaridou, Elena Gribovskaya, Wojeiech Stokowiec, and Nikolai Grigorev. Internet- augmented language models through few-shot prompting for open-domain question answering. arXiv preprint arXiv: 2...2220...1....000 2022.
Fabio Petroni, Aleksandra Piktus, Angela Fan, Patrick Lewis, Majid Yazdani, Nicola De Cao, James Thorn,, Yacine Jernite, Vladimir Karpukhin, Jean Maillard, et al. Kilt: a benchmark for knowledge intensive lan- guage tasks. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages 2523-2544, 2021.
Ross Taylor. Marein Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. Galac- tica: large language model for science. CoRR, abs/2211 1, 000085, 2022.

---

Ori Ram, Yoav Levine, Ita Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin
Jiacheng Liu, Alisa Liu, Ximing Lu, Sean Welleck, Peter West, Ronan Le Bras, Yejin Choi, and Han- naneh Hajishirzi. Generated knowledge prompt- ing for commonsense reasoning. arXiv preprint arXiv:21100083000 2021.
and Yoay Shoham. In-context relreeeal-augmentedd language models. arXiv preprint arXiv:2302.000 2300000300000, 2023.
Weijia Shi, Sewon Min, Michihiro Yasunaga, Min- joon Seo, Rich James, Mike Lewis, Luke Zettle- moyer, and Wen-tau Yih. Replug: Retrieval- augmented black-box language models. arXiv preprint 2rXiv:2311. 12652, 2023.
Sebastian Borgeaud, Arthur Mensch, Jordan Hoff- mann, Trevor Cai, Eliza Rutherford, Katie Milli- can, George Bm Van Den Driessche, Jean- Sapttttt Lespiau, Bogdan Damoc, Aidan Clark, et al. Im- proving language models by retrieving from trillions of tokens. In International conference on machine learning, pages 2206-2240. PMLR, 2022.
Hamnah Rashkin, Vitaly Nikolaev, Matthew Lamm, Lora Aroyo, Michael Collins, Dipanjan Das, Slav Petrov, Gaurav Singh Tomar, Iulia Ture, and David Reitter. Measuring attribution in natural language generation models. arXiv preprint arXiv:2112.12870, 2021.
Wenhao Yu, Dan Iter, Shuohang Wang, Yichong Xu, Mingxuan Ju, Soumya Sanyal, Chenguang Zhu, Michael Zeng. and Meng Jiang. Generate rather than retrieve: Large language models are strong context generators. arXiv preprint arXiv:2209. 10063, 2022.
Luyu Gao, Zhuyun Dai, Panupong Pasupat, Anthony Chen, Arun Tejasvi Chaganty, Yicheng Fan, Vin- cent Y Zhao, Ni Lao, Hongrae Lee, Da-Cheng Juan, al. Rarr: Researching and revising what language models say, using language models. arXiv preprint arXiv:2210.08722 2022.
Zhiqing Sun, Xuezhi Wang, Yi Tay, Yiming Yang, and Denny Zhou, Recitation-augmeente language mod- els. arXiv preprint arXiv:2210.01296, 2022.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Red- field, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Ken- ton Lee, et al. Natural questions: A benchmark for question answering research. TACL 2019, pages 452- 466, 2019.
Bernd Bohnet, Vinh Q Tran, Pat Verga, Roce Aharoni, Daniel Andor, Livio Baldini Soares, Jacob Eisenstein, Kuzman Ganchev, Jonathan Herzig, Kai Hui, et al. Attributed question answering: Evaluation and mod- eling for attributed large language models. arXiv preprint arXfv:2212.0000 2022.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly super- vised challenge dataset for reading comprehension. In ACI. 2017, pages 1601-1611, 2017
Jacob Menick, Maja Trebacz, Vladimir Mikulik, John Aslanides, Francis Song, Martin Chadwick, Mia Glacse, Susannah Young, Lucy Campbell- Gillingham, Geoffrey Irving, et al. Teaching lan- guage models to support answers with verified quotes. arXiv preprint arXiv:2203.1 11 147, 2022.
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. Semantic parsing on freebase from question- answer pairs. In EMNLP 2013, pages 1533-1544, 2013.
Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoe V Le.. Finetuned language models are zero-shot learners. International Conference on Learning Representutions, 2021.
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et Webgpt: Browser-assisted question- answering with human feedback. arXiv preprint arXiv:2112.09332. 2021.
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. Measuring and nar- rowing the compositionality gap in language models. arXiv preprint arXiv: 201.03350, 2022.
Colin Raffel, Noam Shazeer. Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Peter J Liu, et al. Exploring the limits of trans- fer learning with a unified text-to-text transformer. J. Mach. Learn Res,, 21 (1(44)):1-6) 2020.
Ori Yoran, Tomer Wolfson, Ben Bogin, Uri Katz, Daniel Deutch, and Jonathan Berant. Answering questions by meta-reasoning over multiple chains of thought. arXiv preprint 2304 200.233044..333 13007, 2023.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Man- dar Joshi, Danqi Chen, Omer Levy, Mike Lewis. Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1rXiv:197..1162. 2019.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-
scale similarity search with gpus. IEEE Trans- action's 's on Big Data 7(3::335-577 2021. doi:
URL https:// // doi org. / 1109/TBDATT 2019.292155
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language mod- els are unsupervised multitask learners. OpenAl blog, 18))9, 2019.

---

A Data Statistics
C.5
Scoring Function Score(g, 2, a)
Given the question: (query)
The statistics of used datasets are shown Table
and the candidate answer:
B Hyper-parameters
(answer)
and the Query-evidence pair: (query-evidence pair)
The detailed syper-parameterd are shown in Ta-
ble 6.
refer to the query-evidence pair below and utilize your own reasoning ability to assess the probability that the candidate answer is the true answer. Please provide number between and 1 as the output, following the guidelines below: If the probability is between 0 and 0.3, it signifies that the model has substantial evidence to suggest is an incorrect answer.
Detailed Prompts of the Functions
C.1 Answering Function Answer(g, Q,E)
Given the following query-evidence pair: (query-evidence pair)
Please refer to the query-evidence pair above, swer the following question with just one entity. Question: {query)
If the probability between 0.3 and 0.5, sug- gests that the model leans towards considering it an incorrect answer, but lacks concrete evidence. If the probability is between 0.5 and 0.7, it indicates that the model leans towards considering it correct answer, but lacks concrete evidence.
The answer is:
C.2 Asking Function Ask(q, 2,E, K)
If the probability is greater than 0.7, it signifies that the model has substantial evidence to suggest it is the correct answer.
Given the question:
(query)
and following query-evidence pair:
If the candidate answer docsn't provide clear so- lution to the question, the probability should be 0.
(query-evidence pair).
Please generate some questions that can help an- swer the given question with the following con- straints:
The score is:
D Dense Retriever
1. You should output no more than & questions.
2. You should directly output the ranked sub-
Dual Encoder. The predominant architecture cur- rently utilized for dense retrieval is known the dual encoder. This architecture employs dense vec- tor representations, denoted as q and d, to encode queries and documents, respectively. The similarity scores are then computed using the inner product as follows:
questions based on their importance.
3.The generated questions should be diverse and focus different aspects of the given question.
4. You should output in the following format:
Ranked Questions:
1. Questioon I]...
8 d) = Ed (E((d)
C.3 Retrieval Function Retrieve(Gori, 4 N)
where Eq(.) and Ep(-) refer to the query encoder and document encoder, respectively. To leverage the embeddings, existing solutions typically em- ploy approximate nearest neighbor (ANN) search algorithms such as FAISS [Johnson et al., 2021].
Given the original question:
(query)
and the provided document:
(doc)
output the factual information from the evidence
that is relevant to the question:
Performance of Dual Encoder. The pre-trained language model (PLM) used the training of re- trievers is COCONDENSER* The performances DEs on different datasets can be found in Table 7.
C.4 Retrieval Function Retrieve' (qors)
Generate a short background document from Wikipedia to answer the given question: {query)
"Luya/cc--condeeser-marro in huggingface.

---

Parameter
NQ
TriviaQA
WebQ
Threshold
0.8
0.8
0.8
Beam Size
3
Beam Depth
2
Retrieval Number
2
Expand Question Number
2
2
3
Evidence Type
Retrieval GPT-3.5-Turbo
GENREAD GPT-3.5-Turh,
GENREAD
L.M API
GPT-335-Turbb
Table 6: Hyper Hyper-parameters for ALLIES.
Dataset
R@1
R@s
R@20
R@50
R@ 100
R@ 1k
MRR@10 10
MAP@ 1k
NQ
46.43
68.86
80.28
84.40
86.86
92.06
56.03
21.96
TriviaQA
58.34
73.44
80.71
84.04
85.95
89.55
64.71
25.03
WebQ
52.31
72.10
80.41
83.76
85.63
90.80
60.72
21.50
Table 7: The results of the dual encoders on different datasets.
Datasets
Train
Valid
Test
NQ IKwiatkowski al., 2019]
79,168
8,757
3,610
TriviaQA [Joshi et al., 2017]
78,785
8.837
11,313
WebQ [Berant et al., 2013]
3,478
300
2,032
Table 8: Datasets splits and statistics.


Reviews:
[{"review_id": "jrL3lg1lMn", "reviewer": "Reviewer_2w8K", "summary": "", "questions": "1. What is the corpus for the retrieval?", "limitations": "", "rating": 3, "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": "Thank you for your valuable feedback. We would like to address your inquiries as follows:\n\n1. **Regarding the Corpus Source and Details**\n\n   We apologize for any oversight in providing complete details. Following [1,2], we use the Wikipedia dump from Dec. 20, 2018 as our retrieval corpus, encompassing a comprehensive collection of 21,015,324 documents. We will provide the corpus download link in the future version of the paper.\n\n2. **Regarding the API Times for GENREAD**\n\n   We extend our gratitude for identifying the discrepancy in the API times for GENREAD. We acknowledge this error and are committed to rectifying it in the future version of the paper.\n\n3. **Regarding the API Times for ALLIES (Retrieval&Summary)**\n\n   We deeply regret any confusion that may have arisen. In our experimentation, we utilized the complete set of questions from the NQ dataset to conduct the effectiveness analysis. It was observed that, on average, ALLIES requires 4.7 retrieval times to address a single question. For the sake of clarity and ease of comprehension, we have rounded this figure to 5. It is our intention to provide a more detailed illustration of this process in future versions of the paper.\n\n4. **Regarding WebQ's Performance Decline with Additional Context**\n\n   During our experimentation, we observed the trend of diminished performance on WebQ with the introduction of supplementary context. Following meticulous analysis, we have identified two principal explanations for this phenomenon:\n\n   - **False Positive Documents:** The retrieval process might yield documents that are not entirely relevant to the given question, as also acknowledged in [3]. Consequently, this introduces the presence of false positive documents, which in turn introduces noise information that may adversely affect the overall model performance.\n   - **Time-Dependent Questions:** Introduced in 2013, WebQ includes inherently time-dependent questions, featuring answers that may have become outdated over time. Contrastingly, the Wikipedia corpus (from Dec. 20, 2018) we employ is substantially more current. This temporal misalignment leads to discrepancies between the LLM's generation of new answers and the pre-existing answers within the WebQ dataset, which particularly impacts the EM and F1-Score metrics. This phenomenon of time-dependent answers is also explored in [2].\n\n5. **Regarding the Reproducibility Issue**\n\n   We have included our hyperparameter settings, detailed prompts, and comprehensive details about our dense retrievers in the Appendix. We will provide the corpus download link in the future version of the paper and open-source the code upon acceptance.\n\nWe greatly value your insightful feedback. If these clarifications meet your expectations, we kindly request your consideration in **raising the Soundness score and Reproducibility score**.\n\n**References:**\n\n[1] Karpukhin V, Oğuz B, Min S, et al. Dense passage retrieval for open-domain question answering[J]. arXiv preprint arXiv:2004.04906, 2020.\n\n[2] Yu W, Iter D, Wang S, et al. Generate rather than retrieve: Large language models are strong context generators[J]. arXiv preprint arXiv:2209.10063, 2022.\n\n[3] Singh Sachan D, Lewis M, Yogatama D, et al. Questions Are All You Need to Train a Dense Passage Retriever[J]. arXiv e-prints, 2022: arXiv: 2206.10658.", "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": "Iterative query augmentation with scoring function can improve the RAG pipeline significantly.", "reasons_to_reject": "While the paper demonstrates its effectiveness, there are some minor concerns that I would like to address:\n\n1. Lack of experiment details: \n- Providing explicit details regarding the corpus or external sources employed for retrieval purposes would be helpful\n- Table 4 could benefit from further explanation to improve understanding.\n    - It seems that the API time for GENREAD should be listed as 2 instead of 1.\n    - It is unclear which specific example was utilized to generate the results presented in Table 4. Does the \"retrieval&summary\" category for ALLIES indicate that the process was repeated five times?\n\n2. Unclear why WebQ results show performance decline with additional context which is contrast behavior with previous findings.", "questions_to_authors": "1. What is the corpus for the retrieval?", "paper_topic_and_main_contributions": "The paper introduces an iterative approach to enhance the retrieval-augmented generation (RAG) pipeline through query augmentation. \nThe method involves leveraging Language Models (LLMs) to generate additional related queries in an iterative manner, and then scoring the output using both the query and the retrieved evidence. \nThe effectiveness of the proposed approach is demonstrated through a comparison with the retrieve-then-read and generate-then-read pipelines.", "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": "RP8ax6rQpo", "reviewer": "Reviewer_rUD4", "summary": "", "questions": "Question A: What are the distinctions between the interactive and iterative process depicted in Figure 1 and the algorithm based on a chain of thought?\n\nQuestion B: While beam search is not a novel technique, what is the main contribution of its utilization in this paper?\n\nQuestion C: The authors state that InstructGPT is employed, indicating LLM alignment with human feedbacks. How is beam search implemented on the top InstructGPT?\n\nQuestion D: Does ALLIES provide an answer based solely on the top-1 retrieved evidence?\n\nQuestion E: The authors mention scoring the response using the LLM. How is the score qualified or evaluated?", "limitations": "", "rating": 3, "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": "Thank you for your insightful feedback. We have taken your inquiries into careful consideration and would like to provide detailed clarifications:\n\n1. **Regarding the Differences from Chain of Thought (CoT)**\n\n   We extend our apologies for any confusion caused. To clarify the distinctions between our algorithm and Chain of Thought, we highlight the following aspects:\n\n   - CoT employs an iterative chain approach, potentially exhibiting low fault tolerance. Conversely, our algorithm adopts an expand-and-iterative tree approach that permits LLM to make mistakes while answering questions.\n   - While most CoT-based methods rely on demonstrations to complement their prompts, our approach doesn't incorporate any demonstrations.\n\n   Notably, one of our baselines, Self-Ask[1], follows a CoT-style approach to answering questions. However, empirical results demonstrate its inferior performance compared to our method, despite incurring significantly higher computational costs. A detailed comparison will be included in the forthcoming version of our paper.\n\n2. **Regarding the Contributions of the Utilization of Beam Search**\n\n   The contributions of utilizing beam search in our work can be concisely outlined as follows:\n\n   - During Beam Expansion, additional queries are generated iteratively, driven by the LLM's inquiries about the required information. This strategy enhances the breadth of information coverage of the LLM.\n   - During Beam Pruning, we retain the top B highest-scoring answers, affording the LLM the capacity to make erroneous predictions, thereby bolstering the model's fault tolerance.\n\n3. **Regarding the Implementation of Beam Search on InstructGPT**\n\n   As stated in Section 3 and Algorithm 1, our beam search implementation unfolds as follows:\n\n   - Beam Initialization: LLM directly answers the question and generates answers based on evidence, respectively.\n   - Beam Expansion: LLM generates new queries iteratively, broadening information coverage.\n   - Beam Pruning: LLM scores generated answers, retaining the highest-scoring B answers.\n   - Beam Termination: Terminate the beam reasoning when answer scores exceed a threshold or maximum depth is reached.\n\n4. **Regarding the Number of Retrieved Evidence**\n\n   Detailed hyperparameters concerning the number of retrieved evidence are illustrated in Table 6 of the Appendix section. It's crucial to highlight that ALLIES supports diverse evidence types. Specifically, for NQ, the retriever retrieves the top-2 passages as evidence, whereas for TriviaQA and WebQ, GENREAD generates a background document serving as evidence.\n\n5. **Regarding the Evaluation of LLM-Generated Scores**\n\n   As detailed in Section 5.8, we conducted score calculations using 100 randomly selected samples, subjecting the generated scores to manual verification. Our findings indicate a 93 percent alignment between the generated scores and the criteria for score calculation.\n\nFurthermore, we are committed to facilitating a clearer understanding by incorporating additional illustrative examples throughout our paper. \n\nWe are sincerely grateful for your valuable feedback. If these clarifications meet your expectations, we kindly request your consideration in **raising the Soundness score**.\n\n**References:**\n\n[1] Press O, Zhang M, Min S, et al. Measuring and narrowing the compositionality gap in language models[J]. arXiv preprint arXiv:2210.03350, 2022.", "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 testing results appear favorable.", "reasons_to_reject": "The major contributions do not exhibit significant impact.  One instance is the utilization of beam search, which is not a new technique. Therefore, it is crucial to identify the main contribution of using beam search in this study. Additionally, it is important to elucidate the distinctions between the interactive and iterative process and the chain of thought approach.", "questions_to_authors": "Question A: What are the distinctions between the interactive and iterative process depicted in Figure 1 and the algorithm based on a chain of thought?\n\nQuestion B: While beam search is not a novel technique, what is the main contribution of its utilization in this paper?\n\nQuestion C: The authors state that InstructGPT is employed, indicating LLM alignment with human feedbacks. How is beam search implemented on the top InstructGPT?\n\nQuestion D: Does ALLIES provide an answer based solely on the top-1 retrieved evidence?\n\nQuestion E: The authors mention scoring the response using the LLM. How is the score qualified or evaluated?", "paper_topic_and_main_contributions": "For open domain question answering, this paper employed an extension strategy to broaden the scope of the original question by generating multiple relevant questions, which allows the LLM to develop a more comprehensive understanding of the complex question by examining its individual components. Throughout the iterative process, a dynamic pruning technique was utilized to narrow down the options, retaining only the top answers at each step.", "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": {"Typos_Grammar_Style_and_Presentation_Improvements": "It is hard to follow the \"Algorithm 1 The process of generating the response to a given query using ALLIES\" on page 4."}, "extra_text": {}}, {"review_id": "7rMg6rbslD", "reviewer": "Reviewer_KsFN", "summary": "", "questions": "1. How do beam depths larger than 3 impact the results? It would be beneficial to provide specific examples illustrating the effects of longer reasoning chains.\n2. With a larger beam size, can we expect the generation of more noisy or greater numbers of augmented queries?", "limitations": "", "rating": 4, "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 grateful for your positive feedback. Please allow us to address your questions as follows:\n\n1. **Regarding the Performance of Beam Depth Larger than 3**\n\n   In our experimentation, as outlined in Section 5.9, we examined the impact of varying the beam depth ranging from 1 to 4. During the rebuttal phase, we expanded the beam depth to 6, and the corresponding results are provided in the following table:\n\n   | Beam Depth |   1    |     2      |   3    |   4    |   5    |   6    |\n   | ---------- | :----: | :--------: | :----: | :----: | :----: | :----: |\n   | EM         | 0.3772 | **0.3792** | 0.3752 | 0.3633 | 0.3669 | 0.3631 |\n   | F1-Score   | 0.4720 | **0.4821** | 0.4756 | 0.4671 | 0.4692 | 0.4663 |\n\n   The observed trend indicates that performance declines as beam depth increases beyond 2. Our rationale for this outcome lies in the following facts:\n\n   - Most questions can be effectively addressed within a beam depth of 2, and raising the depth does not necessarily yield improved outcomes for these questions.\n   - For particularly challenging questions, a heightened beam depth might introduce more noise, potentially complicating the LLM's ability to generate accurate responses.  \n\n   In our upcoming paper version, we intend to provide specific examples that vividly illustrate the impact of extended reasoning chains.\n\n2. **Regarding the Impact of a Larger Beam Size**\n\n   In Section 5.9, we conducted an experiment where we adjusted the beam size within the range of 1 to 4. During the rebuttal phase, we expanded the beam size to 6, and the corresponding results are presented in the following table:\n\n   | Beam Size |   1    |     2      |   3    |   4    |   5    |   6    |\n   | --------- | :----: | :--------: | :----: | :----: | :----: | :----: |\n   | EM        | 0.3705 | **0.3792** | 0.3566 | 0.3665 | 0.3745 | 0.3721 |\n   | F1-Score  | 0.4768 | **0.4821** | 0.4645 | 0.4648 | 0.4743 | 0.4605 |\n\n   The results illustrate that our model's optimal performance is achieved with a beam size of 2. Values both below and above this threshold result in performance deterioration. This phenomenon can be explained by:\n\n   - A larger beam size provides the model with a greater variety of augmented queries and an increased ability to accommodate mistakes, potentially leading to improved performance.\n   - However, upon careful analysis, we noticed that the queries generated by beam size larger than 2 exhibit substantial similarity, yielding minimal additional information. Consequently, the model encounters challenges in effectively ranking multiple candidates and identifying the optimal answer, leading to a decline in performance.\n\n3. **Regarding the Reproducibility Issue**\n\n   We have included our hyperparameter settings, detailed prompts, and comprehensive details about our dense retrievers in the Appendix and we will open source the code upon acceptance.\n\nWe are grateful for your positive feedback. If these responses align with your expectations, we kindly request your consideration in **raising the Soundness score**. Your engagement contributes significantly to the advancement of our work.", "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. The paper identifies issues with stacking LLM queries and proposes a new framework to optimize iterative calling of LLM APIs.\n2. Allies presents a robust method for achieving prompt augmentation, enhancing the model's performance.\n3. Experimental results demonstrate the superior performance of Allies on open book QA benchmarks.\n4. The paper introduces a valuable approach for addressing the limitations of using LLMs for complex tasks.", "reasons_to_reject": "1. The limitations of beam depths are not thoroughly explored. Further investigation is needed to understand how longer reasoning chains affect performance.\n2. The potential impact of larger beam sizes could be explored further.", "questions_to_authors": "1. How do beam depths larger than 3 impact the results? It would be beneficial to provide specific examples illustrating the effects of longer reasoning chains.\n2. With a larger beam size, can we expect the generation of more noisy or greater numbers of augmented queries?", "paper_topic_and_main_contributions": "The paper introduces Allies, a novel method designed to address the limitations of using large language models (LLMs) for complex tasks. Allies leverages LLMs to generate related queries iteratively, enabling iterative reasoning and expanding the scope of the original query to capture hidden knowledge. The proposed method is evaluated in zero-shot open-domain question answering and outperforms other baselines on benchmark datasets.", "excitement": 4, "reproducibility": 3, "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": "tYYYmxvc7F", "reviewer": "Reviewer_7GwV", "summary": "", "questions": "- Concerning the issue of narrow information coverage, how do the authors view the relevance of their work in the context of query expansion [1]?\n- In relation to the low fault tolerance, how do the authors view the relevance of their work with self-consistency [2]?\n- Have the authors experimented with varying prompts at each step to assess prompt robustness?\n- In Figure 3, the paper presents the sensitivity of the beam size and depth. Could the authors provide their insights as to why an increase in depth leads to diminished performance?\n\n[1] Generation-augmented retrieval for open-domain question answering. ACL 2021\n[2] Self-consistency improves chain of thought reasoning in language models. ICLR 2023", "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 deeply appreciate your positive feedback. Here are the addressed points for your review:\n\n1. **Regarding the Distinction Between Our Work and GAR**\n\n   The distinctions between our work and GAR are delineated as follows:\n\n   - GAR emphasizes general semantic augmentation of the original query, while ALLIES concentrates on identifying gaps in LLM's knowledge and generating new queries to extend its knowledge boundaries.\n   - Unlike GAR, ALLIES-generated queries might be less related to the original query but significantly contribute to broadening the knowledge scope of the retrieved evidence. \n\n   A comparison with GAR will be integrated into the upcoming version of our paper.\n\n2. **Regarding the Distinction Between Our Work and Self-Consistency**\n\n   The distinctions between our work and Self-Consistency are delineated as follows:\n\n   - Self-Consistency generates multiple answers based on the same evidence input, while ALLIES generates answers considering various evidence inputs, including the previous reasoning process.\n   - While both methods enhance fault tolerance, ALLIES provides LLM with more evidence during reasoning, potentially yielding improved performance.\n\n   It's noteworthy that Self-Consistency could be integrated into our framework by allowing LLM to generate multiple answers in the Answering Function. A comparison with Self-Consistency will also be included in the future version of the paper.\n\n3. **Regarding the Prompt Choice**\n\n   We conducted experiments with five different prompts for each step and found that distinct prompts yielded similar results.\n\n4. **Regarding the Performance Degradation with Increased Beam Depth**\n\n   Upon meticulous analysis, we attribute the observed performance degradation when increasing the beam depth to the following reasons: \n\n   - Most questions can be answered within a beam depth of 2. Elevating the beam depth tends not to improve the results for these questions.\n   - For particularly challenging questions, heightened beam depth might introduce more noise, potentially leading to misleading information and performance degradation.\n\nWe deeply appreciate your positive feedback. If these clarifications align with your expectations, we kindly ask for your consideration in **raising the Excitement score**. Your feedback significantly contributes to the advancement of our work.", "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 paper effectively motivates its work by addressing the prevalent challenges of narrow information coverage and low fault tolerance encountered in existing methods utilizing LLMs for query responses.\n- The proposed ALLIES method is refreshingly innovative, employing an extension strategy for expansive information coverage and utilizing a dynamic pruning technique to maintain top-tier responses, thereby fostering the model's capacity to accommodate inaccuracies and alternative answers. This approach enhances response precision and reliability.\n- The paper successfully demonstrates the superiority of ALLIES over established methods through comprehensive experiments on zero-shot open-domain QA benchmarks, including NQ, TriviaQA, and WebQ, exhibiting marked improvements (+10 on NQ and WebQ).", "reasons_to_reject": "- There is a noticeable increase in computational costs due to the proposed method's iterative nature, encompassing the retrieval and generation process.\n- While the paper illustrates its limitations in the introduction, the authors fail to provide a comprehensive comparison between ALLIES and existing methods, leaving the contribution of this work less well-defined.\n- Despite the use of a single prompt in the paper, the sensitivity of the model to variations in the prompt was not evaluated, leaving an important aspect of the method unexplored.", "questions_to_authors": "- Concerning the issue of narrow information coverage, how do the authors view the relevance of their work in the context of query expansion [1]?\n- In relation to the low fault tolerance, how do the authors view the relevance of their work with self-consistency [2]?\n- Have the authors experimented with varying prompts at each step to assess prompt robustness?\n- In Figure 3, the paper presents the sensitivity of the beam size and depth. Could the authors provide their insights as to why an increase in depth leads to diminished performance?\n\n[1] Generation-augmented retrieval for open-domain question answering. ACL 2021\n[2] Self-consistency improves chain of thought reasoning in language models. ICLR 2023", "paper_topic_and_main_contributions": "This paper marks the introduction of ALLIES, an innovative approach that leverages a beam search strategy for response generation in open-domain question answering. With a unique extension strategy and dynamic pruning technique, ALLIES capably tackles the critical limitations of narrow information coverage and low fault tolerance associated with large language models. Demonstrated on popular benchmarks, ALLIES excels, significantly outperforming existing methods.\n\nOverall, the contribution of the paper is substantial, leading me to lean towards accepting it.", "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": {}}]

Author rebuttal:

Meta-review: Allies is a method for iteratively querying an LLM in a beam-search style. Specifically, they 
- use a query expansion method that retrieves relevant data and adds it to the prompt
- for each retrieved expansion, score it and prune the low-scoring ones
- repeat the above two steps until the score is > a certain threshold

Expansion followed by pruning enables augmenting with missing information + being tolerant to wrong retrievals. The retriever is fine-tuned. The answerer and the scorer are both ChatGPT3.5-turbo.

The method is in the same category as methods like self-ask, retrieve-then-ask, and GENREAD. It has been implemented and evaluated on open-domain QA for the datasets NQ, TriviaQA, and WebQ. Results are consistently better compared to relevant baselines.

Reviewers 1 and 2 had complaints about paper writing, which can be addressed in the camera-ready version.
Reviewers 3 and 4 questions have been answered. 

The method requires ~10x increase in number of API calls compared to some of the baselines in the same category. While expensive, it actually makes at interesting point about the fact that better results can be achieved if the user is willing to call the API many more times. 

Overall, the approach makes sense and the results are pretty positive.
Decision: Accept-Findings