Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions

In plain words

Answering a hard question often takes several hops. You look something up, work out a fact, and that fact tells you what to look up next. A common system fetches documents once, using only the question, and hopes they cover every hop. For questions with several hops that often fails, because the second thing to look up is only known after the first step is worked out.

IRCoT, the method in this paper, makes the language model and the search engine take turns. The model writes one sentence of its reasoning. That sentence is then used as a search query, and the documents found are added to the model's context before it writes the next sentence. The loop stops when the reasoning reaches an answer or when a step limit is hit. Every document gathered along the way is handed to the model to write the final answer.

The authors report that this gives better search results and more accurate answers on four multi-hop question sets, and that the reasoning contains fewer invented facts. The method needs no training: a few hand-written examples of reasoning are placed in the prompt.

TL;DR

• IRCoT interleaves chain-of-thought (CoT) sentences with BM25 retrieval; the newest CoT sentence is the next query, and retrieved paragraphs are fed back to the reasoner §3.1 fig. 2.
• It needs no training: a few hand-written CoT demonstrations (20 questions annotated, 15 per demonstration set) and a base retriever §3.1 §4.1.
• Author-reported gains over one-step retrieval with GPT-3 (code-davinci-002): answer F1 60.7 vs 53.6 on HotpotQA, 68.0 vs 54.8 on 2WikiMultihopQA, 36.5 vs 29.4 on MuSiQue; IIRC is flat (49.9 vs 49.8) tab. 4.
• The official code uses several defaults the paper does not state (for example a 10-sentence cap instead of 8, a regex that makes the colon optional, and a filter that skips retrieval after "thus/so/therefore" sentences). Read "Paper vs code" before implementing ircot.py.

Problem

For multi-step, knowledge-intensive questions, retrieving with the question alone gives a retrieve-and-read system only the facts closest to the question. Later reasoning steps depend on facts that are only known after earlier steps have been worked out, and those facts may share no words with the question §1 fig. 1. The authors also observe that a reasoning chain generated without retrieval often contains factual errors early on, which derail the rest §5 tab. 2.

The paper assumes a retriever over a fixed corpus, a language model that can write CoT in a few-shot prompt, and a small set of annotated questions with their reasoning chains and supporting paragraphs §3.1. It does not study closed-book or fine-tuned settings, and it reports only few-shot results §4.

Method

Overview. IRCoT has two stages: a retriever that gathers paragraphs, and a reader that answers from them. The contribution is the retrieval stage; the reader uses standard prompting §3 §3.2.

Retriever (IRCoT). The procedure has three ingredients: a base retriever (BM25 over Elasticsearch in the paper), a language model with zero- or few-shot CoT generation, and annotated demonstrations §3.1 §4.1.

1. Base set. Retrieve K paragraphs with the question as the query §3.1.
2. Reason step. Prompt the language model with the paragraphs gathered so far, the question, and the CoT sentences generated so far. Keep only the first generated sentence and discard the rest of the output §3.1.
3. Exit check. Stop if the new sentence contains the string "answer is", or if the step limit is reached. The paper sets the limit to 8 §3.1 (footnote on the step limit).
4. Retrieve step. Use the last CoT sentence as the query, retrieve K paragraphs, and add them to the collected set §3.1.
5. Cap. The collected set is capped at 15 paragraphs so that a few demonstrations still fit in the context window §3.1 (footnote).
6. Output. On termination, all collected paragraphs are returned as the retrieval result §3 fig. 2.

# IRCoT retrieval loop  [§3.1] [fig. 2]
# Input:  question, retriever, llm, K, max_steps (8), max_paragraphs (15)
# Output: collected paragraphs

def ircot_retrieve(question, retriever, llm, K):
    # Base set: retrieve K paragraphs using the question  [§3.1]
    paragraphs = retriever.search(question, K)
    cot_sentences = []
    for step in range(max_steps):
        # Reason: next CoT sentence from question, paragraphs and CoT so far;
        # keep only the first generated sentence  [§3.1]
        prompt = build_cot_prompt(question, paragraphs, cot_sentences)
        sentence = first_sentence(llm.generate(prompt))
        cot_sentences.append(sentence)
        # Exit when the CoT reports an answer  [§3.1]
        if "answer is" in sentence:
            break
        # Retrieve: last CoT sentence is the query; add up to K new
        # paragraphs, keeping the total at most max_paragraphs  [§3.1]
        new_paragraphs = retriever.search(sentence, K)
        paragraphs = add_capped(paragraphs, new_paragraphs, max_paragraphs)
    return paragraphs

Reason-step prompt. Each demonstration and test prompt lists the paragraphs first, one block per paragraph, each block starting with its page title. Then comes the question line, and then the answer line holding the CoT sentences §3.1. In demonstrations the full CoT is shown, and the paragraphs are the gold supporting paragraphs plus M randomly sampled distractors, shuffled together. At test time the model sees every paragraph gathered so far and only the CoT generated so far §3.1. The value of M is searched over {1, 2, 3} §4.1.

Reader. Two prompting strategies are used §3.2:

• CoT prompting: the same template, but at test time the model writes the whole CoT. The final sentence should read "answer is: ..."; if it does not, the full generation is returned as the answer §3.2.
• Direct prompting: the answer field holds only the final answer §3.2.

The paper uses direct prompting for Flan-T5 models and CoT prompting for GPT-3, because these choices scored better in the reader comparison §4.1 tab. 4. The IRCoT CoT itself can also serve as the answer, but the paper found that a separate reader works better §4.1 (footnote) tab. 6.

Flan-T5 prompt differences. For Flan-T5 the question line is prefixed with "Answer the following question by reasoning step-by-step." (CoT) or "Answer the following question." (direct), to follow the model's training format app. G.

IIRC. IIRC questions are grounded in a main passage, and the other paragraphs come from Wikipedia pages linked from it. The main passage is always included in the input. The model first generates a list of Wikipedia page titles (the paper uses 3 at test time), each generated title is mapped to the closest corpus title with BM25, and retrieval is then limited to those pages app. B.

Corpora. HotpotQA uses its own Wikipedia corpus. For 2WikiMultihopQA and MuSiQue, the corpus is all supporting and non-supporting paragraphs from the train, dev and test sets. For IIRC, it is all paragraphs of the Wikipedia pages in the dataset. The paper reports corpus sizes of 5,233,329 (HotpotQA), 430,225 (2WikiMultihopQA), 139,416 (MuSiQue) and 1,882,415 (IIRC) paragraphs app. A §4.

Demonstrations. The authors wrote CoT annotations for 20 questions per dataset. For each dataset they sample three demonstration sets of 15 questions §4.1 app. G (the full CoT texts are in listings 1 to 4 of the appendix).

Hyperparameters

Results

Author-reported. Setup: four open-domain multi-hop QA datasets (HotpotQA, 2WikiMultihopQA, MuSiQue answerable subset, IIRC answerable subset), 500 test questions per dataset, few-shot prompting, metric answer F1 §4 §5. Baseline: one-step BM25 retrieval (OneR) with the same reader, and no retrieval (NoR) §4.1.

Answer F1 with the paper's chosen readers (mean ± std over three demonstration sets) tab. 4:

Gains of IRCoT QA over OneR QA, as stated in the text §5:

• Flan-T5-XXL: +9.4 (HotpotQA), +15.3 (2WikiMQA), +5.0 (MuSiQue), +2.5 (IIRC).
• GPT-3: +7.1 (HotpotQA), +13.2 (2WikiMQA), +7.1 (MuSiQue); no gain on IIRC, where the authors note that NoR QA is already close.

Retrieval recall (fixed-budget optimal recall, at most 15 paragraphs) is shown only in figures; the text gives these gains over OneR §5 fig. 3:

• Flan-T5-XXL: +7.9 (HotpotQA), +14.3 (2WikiMQA), +3.5 (MuSiQue), +10.2 (IIRC).
• GPT-3: +11.3, +22.6, +12.5, +21.2 (same order).

Factual errors. In a manual check of 40 random questions per dataset, the authors counted CoTs with at least one false fact. Compared with OneR, IRCoT reduced these by 50% on HotpotQA and 40% on 2WikiMultihopQA §5 fig. 7.

Model size. IRCoT recall beats OneR at every Flan-T5 size, including 0.2B, and the gap grows with size §5 fig. 8. For QA, IRCoT beats OneR at every size except 0.2B. The authors state that Flan-T5-XL (3B) with IRCoT outperforms GPT-3 with OneR §5 fig. 9. The exact per-size numbers are only in the figures and are not reproduced here.

Out-of-distribution. Demonstrations from one dataset are used to answer questions from another. The paper reports the same trend as in-distribution, but IIRC is excluded from this experiment §5 fig. 5 fig. 6.

Comparison with other LLM-based open-domain QA systems (EM | F1, GPT-3, values as published by those systems; the authors say the comparison is not head-to-head) tab. 1:

The appendix gives an updated table that adds DecomP (newer version) and DSP. There, DSP beats IRCoT on HotpotQA by 2.0 points and newer DecomP beats it on 2WikiMultihopQA by 2.8 points; IRCoT remains best on MuSiQue app. C tab. 3.

Reader ablation. Without the separate reader, the answer is taken from the CoT produced during retrieval. Flan-T5-XXL does clearly worse (52.6 vs 59.1 on HotpotQA). GPT-3 is mixed: it is slightly better without the reader on HotpotQA (61.0 vs 60.7) and 2WikiMQA (70.4 vs 68.0), and worse on MuSiQue and IIRC tab. 6.

Paper vs code

Official code: stonybrooknlp/ircot at commit 3c1820f698eea5eeddb4fba3c56b64c961e063e4, Apache-2.0. The repository is linked from the paper's abstract, and its owner is the authors' lab README.md.

• Step limit. The paper sets the maximum at 8 steps §3.1 (footnote). The code defaults to 10 for both the CoT generator and the exit controller ircot.py ircot.py. The released IRCoT configs do not override it ircot_codex_hotpotqa.jsonnet. The configs therefore run with 10, unless the 8 in the paper is applied separately.
• Exit string. The paper says the CoT stops at the string "answer is:" §3.1. The config regex is .* answer is:? (.*)\.?, so the colon is optional ircot_codex_hotpotqa.jsonnet. The exit check applies this regex to each new sentence ircot.py.
• Retrieval query. The paper uses the last CoT sentence as the query §3.1. The code first removes "reasoning" sentences: any sentence starting with "thus", "so", "that is,", "therefore" or "hence", or an arithmetic line of the form a + b = c ircot.py. The query is the last remaining sentence, and falls back to the question if none is left ircot.py. If the query is empty, that step does no retrieval ircot.py.
• Long paragraphs. The paper does not mention length limits. The code discards retrieved paragraphs over 600 words ircot.py, and truncates paragraphs in prompts to the first 350 words by default ircot.py ircot.py.
• Near-duplicate paragraphs. The code skips a retrieved paragraph that closely matches one already collected, using a fuzzy-match threshold of 90 ircot.py ircot.py. The paper does not describe this.
• Cap. The paper caps the set at 15 §3.1. The code enforces the cap per paragraph, and the configs set 15 ircot.py ircot_codex_hotpotqa.jsonnet.
• Retrieval count. The paper tunes K on {2, 4, 6, 8} for IRCoT §4.1. The released IRCoT configs use 6 ircot_codex_hotpotqa.jsonnet. The OneR configs use 5, which is in the paper's OneR grid {5, 7, ..., 15} §4.1.
• Decoding. The paper states no sampling settings. The GPT-3 generator defaults to temperature 0, max_tokens 300 and stop sequence \n gpt3generator.py. The Flan-T5 server defaults to greedy decoding (do_sample false) serve.py. The configs set max_length 200 for Flan-T5 ircot_flan_t5_xxl_hotpotqa.jsonnet.
• Shuffling. The paper shuffles the sampled distractors with the gold paragraphs in demonstrations §3.1. The IRCoT configs set shuffle_paras: false for the CoT generator ircot_codex_hotpotqa.jsonnet. The order of paragraphs in test prompts therefore follows retrieval order.
• Models and API. The released code calls code-davinci-002 through the OpenAI API ircot_codex_hotpotqa.jsonnet. The paper says this model was deprecated after submission [Limitations]. Results with GPT-3 cannot be re-run exactly; Flan-T5 results can [Limitations].

Pitfalls

• Step limit ambiguity. The paper's 8 and the code's 10 differ (see above). Pick one, and report it.
• Reasoning-sentence filter. The code's filter changes which paragraphs are retrieved in some steps. An implementer who follows only the paper will get different recall on questions where the model writes "so" or "therefore" sentences.
• Retrieval depends on generation. Each retrieval step needs a separate CoT call. The authors note that this makes IRCoT more expensive than one-step retrieval, and that dynamically deciding when to retrieve is future work [Limitations].
• Context budget. Every collected paragraph is repeated in every later prompt, so the prompt grows with each step. The cap of 15 and the 8K (GPT-3) and 6K (Flan-T5) limits interact: demonstrations can be dropped to fit §4.1.
• Model support. The method needs a model that can produce zero- or few-shot CoT, and that accepts long inputs. The authors say CoT ability is less common in models under about 20B, but the Flan-T5 family works here [Limitations] §5.
• Recall metric. The paper's recall is "fixed-budget optimal recall" under the 15-paragraph cap, not Recall@k. Results from other retrieval metrics are not comparable §4.1 (footnote).
• Reader choice matters. Flan-T5 and GPT-3 use different readers §4.1 tab. 4. Using the wrong one changes F1 by several points.
• IIRC needs special handling. IIRC uses title generation and a main-passage input app. B. The generic loop above is not what the paper describes for IIRC.
• Hyperparameter search uses dev data. Each setting is searched on 100 dev questions per dataset, and results are reported on a separate 500-question test set. The dev and test samples are drawn at random, and the paper gives no seed §4.
• Demonstration variance. The reported spread is over three demonstration sets, not over decoding seeds §4.1 tab. 4.
• Not stated: the seed for sampling the questions and demonstrations; temperature and generation length in the paper; the exact prompt for the title-generation step beyond the template shown app. B.

Lineage

• Builds on: the retrieve-and-read paradigm §3; chain-of-thought prompting §1 §3.2; GPT-3 (code-davinci-002) as the generator §4.1.
• Compared against: Internet-augmented QA, RECITE, ReAct, SelfAsk and DecomP (leaderboard style, not head-to-head) §5 tab. 1. DecomP is also in the wiki: DecomP.
• Superseded by: not stated in the content available for this card.