Learning Derivation Orders over Extracted Facts for Multi-Hop Question Answering

A multi-hop question such as "In what city was the director of Inception born?" can only be answered in order. First find who directed the film, then look up where that person was born. Retrieval systems that collect evidence in one shot fail because they do not yet know the middle entity, the "bridge," to search for. Agentic loops fix this by alternating reasoning and retrieval, but they are slow and fragile: one wrong intermediate step derails everything after it. We propose a single learned retrieval step that turns retrieved passages into small fact triples (subject, relation, object) and then selects a subset of those facts together with an order. Every selected fact must be supported by the question or by a fact placed earlier. Because the selection is an ordering, the resulting chain of reasoning can never loop back on itself. Because the ordering is a smooth relaxation, the answer loss from a language model can train it directly.

The key distinction is where acyclicity lives. Earlier work that pushed "no cycles" constraints into knowledge graph extraction imposed them on the knowledge itself. That forces the extractor to delete real reciprocal relations such as "A is married to B" and "B is married to A." We leave the extracted knowledge graph free to contain cycles and impose acyclicity only on the derivation: the graph of which fact depends on which other fact to answer this particular question. The mechanism is borrowed from differentiable causal discovery, where a directed acyclic graph is written as a soft topological order combined with an upper-triangular edge pattern. We reuse that construction as the retriever for multi-hop question answering over automatically built graphs.

Core Claim

We claim that a question-specific, acyclic-by-construction ordering over text-extracted facts, trained only from answer supervision, recovers the gains of multi-step retrieval with one retrieval pass and one generation call. We further claim that it beats edge-independent differentiable subgraph sampling specifically because it rules out ungrounded and circular evidence.

This differs from the closest work in three concrete ways. D-RAG trains a graph retriever end to end with an LLM generator by sampling each triple independently with Gumbel-Softmax, a trick that makes discrete sampling differentiable. It does this over a curated Freebase graph, with entity linking assumed solved, and it places no structural constraint on the sampled subgraph. HGNet does extract graphs from raw scientific text and adds a differentiable loss against cycles. That loss applies to a static corpus taxonomy, answers no questions, and, by the authors' own account, severs legitimate circular links. Diff-Comb Explainer enforces connectivity and tree constraints with an exact integer-programming solver used as a network layer. It selects pre-written sentences from curated explanation banks (WorldTree, ARC) rather than facts extracted from open text. Our proposal combines text-to-graph extraction, answer-driven training, and acyclicity on the derivation rather than on the knowledge. None of these three does all of that.

Mechanism

For each question we retrieve the top passages with a standard dense retriever. An LLM prompted with a few examples extracts triples from them in one pass, as in Pan et al. and DALK, and each triple keeps a pointer to its source sentence. This gives a pool of $d$ candidate facts, typically 50 to 200. At that size, stability problems that plague continuous structure learning on thousands of variables are not a concern.

From the extraction we compute a fixed compatibility matrix $C \in \{0,1\}^{d \times d}$. Here $C_{ij}=1$ when fact $i$ mentions an entity that is the subject of fact $j$, so $i$ could hand its information to $j$. A small encoder scores each fact against the question and produces a soft permutation $\Pi$ via Gumbel-Sinkhorn, following Differentiable DAG Sampling. The soft dependency matrix is

$$A = C \odot \left(\Pi^\top T \,\Pi\right),$$

where $T$ is the strictly upper-triangular all-ones matrix. The term $\Pi^\top T \Pi$ is therefore a soft "fact $i$ comes before fact $j$" indicator, and $A$ is acyclic for any hard permutation. Each fact also gets a selection probability $s_j$ from Gumbel-Softmax and a query-anchoring score $q_j$, which measures string or embedding match between its subject and the question's entities. A selected fact counts only if it is grounded:

$$\tilde s_j = s_j \cdot \max\Big(q_j,\ \max_{i} s_i A_{ij}\Big),$$

so fact $j$ enters the evidence only if the question anchors it or an earlier selected fact supplies its subject.

The selected facts, their source sentences, and their order are given to a small generator LLM. The generator is frozen in one setting and fine-tuned with low-rank adapters in another. Training maximizes answer likelihood with the lower-bound objective used by D-RAG. The only structural novelty relative to D-RAG is the ordered, grounded selection. This makes the central ablation clean.

The knowledge graph itself is never pruned. If the text states both directions of a reciprocal relation, both triples stay in the pool, and a derivation may use either one, but never in a loop.

Research Program

The work has three stages.

The first stage is diagnostic and could falsify the motivation. Section 4 of our source material asserts that cyclic, ungrounded subgraphs from edge-independent sampling cause generator hallucinations, citing Wang et al. 2025, but no paper in our file measures this. We will port D-RAG's sampler to text-extracted graphs on MuSiQue and HotpotQA. We will then measure how often its selected evidence contains facts with no grounded predecessor, and how often it contains loops among entities. Finally, we will test whether these errors predict wrong answers once retrieval recall is controlled for. If ungrounded or circular evidence is rare or does not predict errors, the ordering layer has nothing to fix, and we would redirect the project toward extraction quality.

The second stage builds the ordered retriever and compares three ways of getting acyclicity. The first is our by-construction ordering. The second is a penalty using the matrix-exponential constraint $\operatorname{Tr}(e^{W \odot W}) - d$ from the NOTEARS family (Brouillard et al.). The third is the spectral-radius penalty from Stable Differentiable Causal Discovery. Penalty methods guarantee acyclicity only at convergence, so their intermediate evidence sets can loop. We expect the ordering to train faster and more stably at this problem size, but this is an empirical question.

The third stage studies robustness. We will inject extraction errors (dropped bridge triples, swapped entities) and measure how gracefully each retriever degrades. We will also test cross-domain transfer, training on MuSiQue and testing on 2WikiMultihopQA. The robustness study matters because extraction quality, not the reasoning layer, may turn out to be the bottleneck.

Baselines

The naive reference point is single-shot dense retrieval. The same top passages go straight to the same generator, with no extraction and no selection. It is how practitioners would deploy the system with zero engineering, and every other number should be read against it. For orientation, the original HotpotQA paper reports 58.28 answer F1 for its BiDAF baseline in the distractor setting. MuSiQue reports human answer F1 of 78.0 and shows single-hop models dropping about 30 F1 points relative to HotpotQA, which is why MuSiQue is our primary benchmark.

The key ablation is edge-independent Gumbel-Softmax selection in the style of D-RAG over the same extracted fact pool. It uses the same encoder, the same generator, the same objective, and the same number of selected facts, and differs only in the missing ordering and grounding term. D-RAG itself reports 70.3 Hits@1 and 63.8 F1 on ComplexWebQuestions and 89.1 Hits@1 on WebQSP over Freebase. We will also run our ordering layer on ComplexWebQuestions over its curated graph so the two methods meet on D-RAG's home ground. Beating this ablation on MuSiQue answer F1 by a margin outside seed variance, with a clear drop in ungrounded-fact rate, is the minimum result that justifies the idea.

The strongest existing system for extracted-graph multi-hop QA in our file is GraphSearch. It runs a six-module prompted agent loop over text and triple channels and reports 51.00 substring exact match on MuSiQue, versus 35.00 for LightRAG. IRCoT is the canonical interleaved baseline. It reports gains of 11–21 retrieval-recall points and up to 15 QA F1 points, but our file contains no absolute per-dataset number, so no reported result was found on Lacuna for IRCoT's absolute MuSiQue score, and we will reproduce it.

We will run both systems with the same generator model and the same passage index. We will report accuracy together with the number of LLM calls and tokens per question, since our method uses one extraction pass and one generation call. "Beating" GraphSearch has two possible meanings: exceeding its substring exact match at equal generator size, or matching it within two points at a fraction of the calls. We will state in advance which of the two we achieve.

Two further baselines isolate the differentiable ingredient. The first is discrete beam search over the extracted graph from question entities, with a learned fact scorer. The second is Diff-Comb Explainer's solver layer, given a connectivity-plus-tree constraint over the same fact pool. All learned methods get the same hyperparameter search budget and the same GPU hours.

Why not just…?

Why not just let an agent loop like IRCoT or GraphSearch handle ordering through prompting? These loops do produce ordered evidence, and on accuracy alone they may win. HGNet reports that prompted general LLMs produce circular structures when asked to build graphs. IRCoT and Wang et al. document that one bad intermediate step derails the rest. Neither result shows that a learned single-pass ordering does better. The honest comparison is accuracy per LLM call. If GraphSearch stays well ahead even when we give our generator an extra verification pass, the claim reduces to an efficiency result, and we will present it as that.

Why not just search for paths in the extracted graph? A path from a question entity is acyclic and grounded by definition, so this alternative is the most serious threat. We see two differences. Beam search needs either gold paths or reinforcement learning to train its scorer, while our method learns from answers alone. And many MuSiQue compositions branch into two parallel sub-questions that merge, which a single path cannot represent but a partial order can. We will train the beam searcher with MuSiQue's gold decompositions, giving it more supervision than we use. If it still matches us on the branching subset, the differentiable ordering is not earning its keep.

Why not just extract, detect cycles with a standard graph algorithm, and prune? Pruning after the fact cannot learn which edge to drop for this question. Differentiable DAG Sampling reports that heuristic pruning severs useful edges and that by-construction sampling improved undirected AUC-ROC by 25% on synthetic graphs. That evidence comes from causal discovery, not question answering. Worse, pruning the knowledge graph repeats HGNet's error of deleting reciprocal relations. We include post-hoc pruning of D-RAG's selected evidence as a variant of the key ablation, which directly tests this alternative.

Why not just skip the graph and give raw passages to a long-context model? Triples compress evidence for small generators, a benefit reported by DRAG and KnowTrace. GraphSearch's triple channel helped on MuSiQue. Still, extraction errors can outweigh these benefits. The naive baseline and a long-context variant with all retrieved passages settle this at each generator size. We expect the graph to help most for small generators and least for large ones.

Proposed Experiments

The primary evaluation uses MuSiQue-Ans, HotpotQA (distractor and full-wiki), and 2WikiMultihopQA, with ComplexWebQuestions as the curated-graph control. We report answer F1 and exact match, plus substring exact match on MuSiQue for comparability with GraphSearch. We also report supporting-fact F1, and chain-order accuracy against MuSiQue's gold decompositions, meaning whether selected facts respect the gold hop order. Two further measures are the rate of ungrounded selected facts and the number of LLM calls and tokens per question. All results are averaged over three seeds.

The first decisive check is the stage-one diagnostic: does ungrounded or circular evidence predict errors at all? The second is the head-to-head against edge-independent selection on MuSiQue. If ordering does not improve answer F1 and cut the ungrounded rate relative to that ablation, the proposal fails. The third is the branching-question subset against supervised beam search, which decides whether a partial order buys anything over paths. The fourth is the comparison of by-construction ordering against penalty-based acyclicity, which decides whether the causal-discovery machinery matters or any structural prior would do.