Multi-hop reasoning

Overview

A multi-hop question cannot be answered from one passage or one fact. The system must find a first fact, use it to reach a second, and so on until it has the answer. The shared problem is that a correct final answer does not show that the chain was followed. The benchmark behind the first variant addresses it by asking for three outputs at once: the answer, the supporting sentences and the evidence triples that spell out the reasoning path 2011.01060 §2.1.

The seven papers on this page take different routes. One builds benchmarks with gold chains, from templates or from crowd-written steps. One gets a language model to write its own sub-questions with prompts only. One interleaves reasoning sentences with retrieval, so each new sentence becomes the next search query 2212.10509 §3.1. One loops a frozen model over a given context, selecting facts and then deriving one new fact from them 2205.09712 §4. One trains small models from scratch on synthetic chains and studies whether recurrence helps them generalize. One changes pretraining so that linked documents share a training input, and reports its largest gains on multi-document QA 2203.15827 §4.2 2203.15827 §5.3. Their settings differ, so their numbers are not directly comparable 2101.02235 §5.2 2210.02406 §4 2212.10509 §4 2604.07822 app. A 2203.15827 §5.1 2205.09712 §5.

Variants

Template-generated chains over Wikipedia and Wikidata

This is the construction of 2WikiMultiHopQA. Two Wikidata triples are chained, and a question template is filled in from them.

• Question types. Four types: comparison, inference, compositional and bridge-comparison 2011.01060 §2.2. An inference question names one entity and one relation, and the answer is reached through a logical rule. A compositional question names the entity and both relations 2011.01060 app. A.3 2011.01060 app. A.4.
• Sources. Summary paragraphs of English Wikipedia articles give the context. Wikidata triples give the evidence 2011.01060 §3.1.
• Templates and rules. Templates were written by hand. Inference uses 28 logical rules over single-valued relations, checked by hand 2011.01060 §3.2 2011.01060 app. A.3.
• Generation checks. Each object of a triple must appear in the matching Wikipedia summary. Bridge questions also need paragraph checks 2011.01060 §3.2 2011.01060 alg. 1 2011.01060 alg. 2.
• Distractors and split. A bigram tf-idf retriever adds distractor paragraphs, and a single-hop model splits the data into harder and easier parts 2011.01060 §3.2 2011.01060 tab. 1.
• Size. 192,606 questions in total 2011.01060 tab. 1.

Joint scoring of answer, supporting facts and evidence

This is the metric defined for the benchmark. It can be applied to any system that outputs an answer, sentences and triples in the same format.

• Per-task scores. Answer, supporting-fact and evidence scores are each computed as exact match and F1 2011.01060 §2.1.
• Joint score. Precision and recall are each the product of the three task values. Joint EM is 1 only when all three tasks match exactly 2011.01060 §2.1 2011.01060 eq. 1.

HotpotQA-style baseline with an evidence branch

The paper's baseline extends the HotpotQA baseline with one block that predicts evidence. The question predicts the relations, and the context gives the subject and object of each relation 2011.01060 §5.2.

• Result. Test joint F1 of 5.41, with evidence F1 of 14.94 and answer F1 of 43.93 2011.01060 tab. 5. These are author-reported numbers.
• Gap to humans. On 100 test samples, the human average reaches 66.69 joint F1 and the model 9.79 2011.01060 tab. 7 2011.01060 §5.3.

Implicit-step questions with decomposition and evidence (StrategyQA)

The questions in StrategyQA do not state their reasoning steps, so a strategy has to be inferred before the facts can be looked up 2101.02235 §1. The benchmark has yes/no questions only.

• Data. 2,780 questions. Each has a decomposition into steps, and each retrieval step has Wikipedia paragraphs that answer it 2101.02235 §2.2 2101.02235 §4.
• Collection. Crowd workers write a question from a Wikipedia term. Questions that at least four of five pretrained solvers answer correctly are removed, and so are questions that all three fine-tuned solvers answer correctly 2101.02235 §3.1. The decomposition is written before evidence is matched, so the writer does not see the context 2101.02235 §3.2.
• Quality check. In a 100-question sample checked by the authors, 82 were judged to have implicit steps 2101.02235 tab. 5.
• Cost. About $4 per example, with three evidence matchers per decomposition 2101.02235 §4.
• Baselines. Accuracy with no context is 63.6 ± 1.3. With gold paragraphs it is 70.7 ± 0.6, and with gold paragraphs plus the last step 72.0 ± 1.0. Experts reach 87% 2101.02235 tab. 9 2101.02235 tab. 7. These are author-reported test-set numbers.
• Retrieval. Recall@10 is 0.174 for question-based BM25 retrieval, 0.195 with a predicted decomposition and 0.282 with a gold decomposition 2101.02235 tab. 9. Accuracy with predicted-decomposition retrieval is 61.7 ± 2.2 2101.02235 tab. 9.
• Licence. The paper's own licence is CC0. The dataset's licence is not confirmed in the card, so do not copy the dataset into a derived work.

Prompt-level decomposition into sub-questions (DecomP)

Decomposed Prompting uses prompts only. No model is trained 2210.02406 §2.

• Mechanism. A decomposer prompt writes a program of sub-tasks. Each sub-task goes to a few-shot prompt, a symbolic function, or a recursive call of the same procedure 2210.02406 §3 2210.02406 §3.3. A controller sends each answer back to the decomposer until it writes an end marker 2210.02406 §3.2.
• Letter concatenation. The method outperforms chain-of-thought (CoT) and least-to-most prompting across the tested lengths 2210.02406 §4.1 2210.02406 fig. 7.
• List reversal. The decomposed method generalizes to longer lists, where base CoT does not 2210.02406 §4.2 2210.02406 fig. 8.
• Open-domain QA. Decomposed retrieval beats the no-context baseline in every setting reported. Results are answer F1 on 300 dev questions per dataset 2210.02406 §4.4 2210.02406 fig. 12. The corpora for the 2WikiMultihopQA and MuSiQue settings pool paragraphs from the train, dev and test questions, so the numbers do not reflect a corpus built from evaluation questions alone 2210.02406 app. A.1.
• Math. Adding a CoT answer-extraction sub-task raises the reported GSM8K score from 36 to 50.6 and MultiArith from 78 to 95 2210.02406 §4.5 2210.02406 app. B. The metric is not stated, and the samples are 300 and 200 examples. The gain comes from one change in answer extraction 2210.02406 app. B.
• Model size. Only GPT-3-sized models reliably produced the structured output, so the decomposer cannot simply be a small model 2210.02406 §4.4.

Interleaved retrieval and reasoning (IRCoT)

IRCoT retrieves in the middle of a chain of thought. The model writes one sentence, and that sentence becomes the next search query. The paragraphs found are added to the prompt before the next sentence is written 2212.10509 §3.1 fig. 2. No weights are trained: the method is few-shot prompting over a base retriever 2212.10509 abstract.

• Loop. The first retrieval uses the question. The loop ends when a sentence contains "answer is" or the step limit is reached. The paper sets the limit to 8 and caps collected paragraphs at 15 2212.10509 §3.1.
• Demonstrations. The authors annotated 20 questions per dataset and sampled three demonstration sets of 15 2212.10509 §4.1 2212.10509 app. G.
• Readers. GPT-3 uses chain-of-thought prompting for the answer; Flan-T5 uses direct prompting 2212.10509 §3.2 2212.10509 §4.1.
• Results. Author-reported answer F1 with GPT-3 (code-davinci-002), IRCoT against one-step retrieval: 60.7 against 53.6 on HotpotQA, 68.0 against 54.8 on 2WikiMultiHopQA, 36.5 against 29.4 on MuSiQue, and 49.9 against 49.8 on IIRC 2212.10509 tab. 4. With Flan-T5-XXL (11B), IRCoT is above one-step retrieval on all four sets, from 42.5 against 40.0 on IIRC to 66.5 against 51.2 on 2WikiMultiHopQA 2212.10509 tab. 4.
• Factual errors. In a manual check of 40 questions per dataset, the authors count 50% fewer reasoning chains with a false fact than one-step retrieval on HotpotQA, and 40% fewer on 2WikiMultiHopQA 2212.10509 §5 fig. 7.
• Cost. Each retrieval step needs its own reasoning call, and the prompt shows every paragraph gathered so far, so it grows with each step 2212.10509 limitations 2212.10509 §3.1.

Selection-inference loop over a given context (SI)

Selection-Inference wraps a frozen LLM in a loop over a fixed context. Each step has two few-shot prompts on the same model. A selection step picks a few facts from the context, and an inference step derives one new fact from those facts alone, without the question. The new fact is appended to the context 2205.09712 §4 2205.09712 alg. 1.

• Causal trace. Selection scores each candidate context item instead of generating free text. The authors found free generation often invented facts, which breaks the link between the trace and the answer 2205.09712 §4.1.
• Step budget. The number of steps is fixed per task, not learned. For bAbI tasks 1, 2, 3 and 15 the paper uses one step, and for bAbI 16 two 2205.09712 app. D. A halting rule is left to future work 2205.09712 §7.
• Results. Author-reported 5-shot generative accuracy, averaged over the tasks, for Gopher 7B: 58.75% with SI, against 2.94% for vanilla prompting and 41.32% for chain-of-thought (CoT) prompting on the same model 2205.09712 §5 2205.09712 fig. 4a.
• Fine-tuned variant. The selection and inference steps are trained separately, on single steps only. The paper reports 78.95% for this variant 2205.09712 §6 2205.09712 fig. 4b. Prompt-only SI is reported in §6 as 57.93%; see Contradictions.
• Limits. Retrieval is out of scope, so the context must already hold the facts 2205.09712 §4. The authors name the selection module as the main failure point 2205.09712 app. G.

Recurrent-depth transformers on synthetic knowledge-graph chains

Loop, Think, & Generalize trains small models from scratch on synthetic two-hop and longer queries over a knowledge graph. The model gets a start entity and a relation sequence, and must output the end entity in one forward pass 2604.07822 §3.1 2604.07822 §4.

• Recurrence. A stack of 4 layers is applied R times. R = 1 is the vanilla model 2604.07822 §4 2604.07822 §5.1.
• Systematic generalization. The vanilla 4-layer model fails on combinations of facts never seen together. With R = 4 the model generalizes, after three grokking stages. Convergence takes about 2k epochs at R = 4 and about 7k at R = 2 2604.07822 §5.2 2604.07822 fig. 3.
• Depth extrapolation. Raising recurrence at inference extends the reachable chain length. In the main curriculum setup, R = 8 reaches 24 hops and R = 6 reaches 17 2604.07822 §6.2 2604.07822 fig. 5. In the matched data setup, R = 8 reaches 19 hops, the same as the dynamic model 2604.07822 §6.2 2604.07822 fig. 7.
• Overthinking. For the dynamic model, out-of-distribution accuracy stops improving after about 15 iterations 2604.07822 §6.2 2604.07822 fig. 8. The authors say adaptive halting does not fix this 2604.07822 §6.2.
• Adaptive halting. Each example stops once successive predictions differ by less than a KL threshold and the entropy is below a threshold. The paper gives 0.01 and 3.00 2604.07822 §6.2 2604.07822 app. C.
• Limits. The tokens and vocabulary are synthetic, and the authors do not claim the results carry over to LLMs trained at scale 2604.07822 app. A. Without a permutation constraint on the graph, a model can reach high accuracy by reading a short suffix of the relations 2604.07822 app. K. Grokking to 4 hops took over 1.3M training steps 2604.07822 §6.2.

Document-link pretraining (LinkBERT)

LinkBERT changes what a pretraining input contains rather than how questions are answered. An anchor segment is paired with a second segment that is contiguous, random or from a linked document, and a three-way relation loss is added to masked language modeling 2203.15827 §4.2 eq. 1. The linked document is chosen with probability inversely proportional to its in-degree 2203.15827 §4.3.

• Results. Author-reported MRQA F1 for LinkBERT against BERT at the same scale: HotpotQA 54.6 against 49.8 (tiny), 78.2 against 76.0 (base) and 80.8 against 78.1 (large) 2203.15827 tab. 1. The authors report the average gain as +4.1, +2.6 and +2.5 2203.15827 abstract.
• Link source matters. For LinkBERT-tiny, random links match BERT-tiny on HotpotQA (49.8). Replacing hyperlinks with TF-IDF neighbours gives 50.0, and hyperlinks give 54.6 2203.15827 tab. 5 2203.15827 §5.5.
• Few labels. With 10% of the fine-tuning data, LinkBERT-base reaches 70.5 on HotpotQA against 64.8 for BERT-base 2203.15827 tab. 4.
• Cost. Continued pretraining of base takes 4 days on four A100 GPUs, and tiny takes 1 day on two 2080 Ti GPUs 2203.15827 §5.1. The cost of building the link graph is not stated.
• Limits. The paper's pretraining code is not in its repository, so the link sampling and the relation head cannot be checked against code 2203.15827 §4 README.md. The MRQA split is not the official one, so its numbers are not comparable to leaderboard results 2203.15827 §5.2.

When to use which

Joint scores are much lower than single-task scores. Report all three task scores with the joint score, so a reader can see where a system fails.

Implementation sketch

Joint score from per-task precision and recall 2011.01060 eq. 1. The paper's evaluation script follows this form; the zero check is an extra guard that the paper does not discuss.

# Joint F1 from the three tasks  [arxiv:2011.01060 §2.1] [eq. 1]
# Inputs: precision and recall per task, as floats in [0, 1]

def joint_f1(answer, support, evidence):
    # Joint precision is the product of the three task precisions
    p_joint = answer.p * support.p * evidence.p
    # Joint recall is the product of the three task recalls
    r_joint = answer.r * support.r * evidence.r
    if p_joint + r_joint == 0:
        return 0.0
    # Harmonic mean of the joint precision and recall
    return 2 * p_joint * r_joint / (p_joint + r_joint)

Contradictions

• StrategyQA retrieval. The paper's text says predicted decompositions do not yet beat question-based retrieval 2101.02235 §5.2. Its table reports Recall@10 of 0.195 for predicted decompositions and 0.174 for question-based retrieval 2101.02235 tab. 9. Both are given here as reported; the difference is not resolved.

• 2WikiMultiHopQA tables. The paper's tables may differ from its latest release: the repository says tables 5, 6 and 7 were recomputed later, and the updated numbers are not transcribed here 2011.01060 tab. 5 2011.01060 §5.2.

• Selection-Inference numbers. Section 5 gives 2.94% for vanilla 7B, 41.32% for CoT 7B and 58.75% for prompt-only SI on the generative setting 2205.09712 §5. Section 6 gives 0.34% and 15.73% for vanilla and CoT 7B, and 57.93% for prompt-only SI, on a task subset the paper does not state 2205.09712 §6. The introduction's ratios differ again from §5 2205.09712 §1. Both sets are given here as reported.

• DecomP on 2WikiMultiHopQA. IRCoT's main comparison lists DecomP at 59.3 F1 on 2WikiMultiHopQA, below IRCoT's 68.0 2212.10509 tab. 1. Its appendix gives an updated table where a newer DecomP beats IRCoT there by 2.8 points 2212.10509 app. C tab. 3. Both are given here as reported. The comparison is leaderboard-style and not head-to-head.

Other numbers on this page come from different settings and metrics, so they are not contradictions.

Papers

• 2WikiMultiHopQA paper, arXiv:2011.01060: builds 2WikiMultiHopQA from Wikipedia and Wikidata, defines the joint metric and reports a baseline with evidence scores.
• Did Aristotle Use a Laptop?, arXiv:2101.02235: StrategyQA, a crowd-built yes/no benchmark with implicit steps, decompositions and per-step evidence.
• Selection-Inference, arXiv:2205.09712: frozen-LLM loop that selects facts from a given context and derives one new fact per step, with a fine-tuned variant.
• Decomposed Prompting, arXiv:2210.02406: prompt-only decomposition into sub-questions, with sub-tasks that can be prompts, functions or recursive calls.
• Interleaving Retrieval with Chain-of-Thought Reasoning, arXiv:2212.10509: IRCoT, alternating reasoning sentences with BM25 retrieval, using the newest sentence as the query.
• Loop, Think, & Generalize, arXiv:2604.07822: recurrent-depth transformers on synthetic knowledge-graph chains, with grokking, depth extrapolation and overthinking.
• LinkBERT, arXiv:2203.15827: pretrains BERT-style encoders on linked documents in one input, with a three-way relation loss; reports MRQA gains over BERT.