HyperProve: Answer-Guided Hypergraph Expansion for Multi-Hop Question Answering¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: NLP Understanding
Keywords: Multi-Hop QA, Retrieval-Augmented Generation, Atomic-Fact Hypergraph, Answer-Guided Retrieval, Local Graph Expansion
TL;DR¶
Addressing evidence drift and context collapse in multi-hop QA, HyperProve organizes corpus evidence into a synonym-aware hypergraph of atomic facts, carries validated intermediate answers and supporting hyperedges as structural retrieval state, and performs query-biased local random-walk expansion to construct faithful multi-hop evidence chains.
Background & Motivation¶
Retrieval-augmented generation (RAG) grounds language models in external knowledge corpora, yet standard retrieval pipelines still predominantly treat question answering as a one-shot relevance matching task: given a complex query, retrieve passages independently similar to the query surface form, and prompt a reader model to generate the final response. While this formulation succeeds when question-bearing keywords directly overlap with the target answer text, it severely breaks down in multi-hop question answering. In multi-hop reasoning, crucial evidence is distributed across distinct facts linked through intermediate bridge entities, relational chains, and temporal or geographic constraints. Consequently, the next necessary fact along the reasoning chain is frequently dissimilar to the original question at the lexical level, becoming relevant only after preceding facts have resolved the correct bridge entity.
Recent efforts tackle this challenge through graph-structured retrieval or iterative reasoning pipelines, yet both paradigms suffer from critical design gaps. Graph-based RAG methods such as HyperGraphRAG, HGRAG, and PropRAG leverage entity-passage hypergraphs or proposition paths to capture high-order facts, but their traversal remains primarily guided by one-shot incidence expansion, fixed-query diffusion, or static proposition beam search against the unchanged global question. Under such unconditioned traversal, graph search frequently retains globally similar distractor entities and strays off-course once an intermediate bridge diverges. Conversely, iterative retrieval systems like IRCoT, HopRAG, and ChainRAG adapt queries or interleave reasoning steps across hops, but propagate state purely as rewritten text or loose passage sets. Because they fail to convert the validated intermediate answer together with its supporting facts into a structural retrieval frontier, subsequent hops can easily lose evidence provenance, restart from surface similarity, or follow plausible false-positive branches.
The angle of attack in this work is that robust multi-hop retrieval must couple query-driven reasoning with structural provenance preservation. Core idea: decompose complex queries into dependent sub-questions, carry intermediate answers along with their supporting atomic-fact hyperedges as a stateful structural frontier, and bias local hypergraph expansion via both structural connectivity and rewritten sub-query semantics.
Method¶
Overall Architecture¶
The HyperProve architecture operates in two main phases: offline synonym-aware hypergraph construction and online answer-guided multi-hop reasoning. In the offline phase, each corpus passage is parsed into participating entities and self-contained atomic facts represented as hyperedges connecting entities and source document nodes. Entity mentions with cosine embedding similarity above a threshold are linked to allow cross-passage overlap. In the online phase, an input multi-hop question is decomposed into a sequence of dependent sub-queries. At each reasoning hop, the system updates a question-answer memory and forms a hybrid seed set combining the carried structural hyperedge frontier from the preceding hop with fresh dense retrieval seeds. Within a bounded local hypergraph neighborhood, personalized PageRank is performed using a transition matrix that linearly balances structural incidence and query-biased semantic relevance. The ranked atomic facts and corresponding passages are evaluated to resolve the sub-query, iteratively advancing the frontier until a final answer is generated, or triggering a reader fallback when an intermediate hop remains unresolved.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
Q["Input Multi-Hop Question & Corpus"] --> A["Atomic-Fact Hypergraph Construction<br/>Entity extraction ยท Synonym linking ยท Structural matrix Ts"]
A --> B["Stateful Frontier Propagation & Hybrid Seeding<br/>Sub-query decomposition ยท Memory rewriting ยท Frontier Ct โช Dense seeds Ft"]
B --> C["Query-Biased Local Hypergraph Transition & PPR<br/>Mixture of Ts and query-biased Tq ยท Local power iteration"]
C --> D{"Sub-query Evaluation & Answer Integration<br/>All answered โ IntegrateAnswers / Any unresolved โ ReaderFallback"}
D --> E["Final Answer a & Grounded Evidence Chain"]
Key Designs¶
1. Atomic-Fact Hypergraph Construction: Preserving Multi-Entity Context and Source Provenance
Standard knowledge graph triples \((s, r, o)\) split multi-participant facts into binary fragments, causing severe context collapse when statements involve temporal qualifications, spatial modifiers, or more than two entities. HyperProve instead models each corpus passage \(d_j\) as a set of atomic facts represented as hyperedges \(h_i = (x_i, A_i, d_{\sigma(i)})\), where \(x_i\) is the self-contained factual assertion, \(A_i\) is the set of participating entity nodes, and \(\sigma(i) = j\) points to its source document node, yielding incidences \(h_i \sim A_i \cup \{d_{\sigma(i)}\}\). To overcome surface lexical variation across documents, entity name embeddings are compared, and mentions exceeding cosine similarity threshold \(\eta = 0.8\) are expanded into a synonym set \(A_i^+ = A_i \cup \text{Syn}(A_i)\).
The framework constructs hyperedge-entity incidence matrix \(B_{he}\) and hyperedge-document incidence matrix \(B_{hd}\). To penalize generic uninformative hub entities and exceptionally long passages generating disproportionate numbers of atomic facts, degree matrices \(D_e\) and \(D_d\) are incorporated into the structural adjacency formulation: $\(W_s = B_{he} D_e^{-1} B_{he}^\top + B_{hd} D_d^{-1} B_{hd}^\top\)$ Self-loops are removed, and row-normalization yields the sparse structural transition matrix \(T_s = \text{RowNormalize}(W_s - \text{diag}(W_s))\), ensuring transitions among atomic facts reflect genuine shared multi-entity relationships and common provenance.
2. Query-Biased Local Hypergraph Transition & PPR: Balancing Structural Connectivity and Sub-Query Alignment
Unconstrained graph diffusion easily spreads probability mass over irrelevant topological neighbors, while purely dense passage retrieval ignores relational structure. At hop \(t\), HyperProve first extracts a bounded local subgraph \(G_t^\star\) of at most 600 hyperedges via random-walk expansion from current seeds on \(T_s\). Let \(T_{s,t}^\star\) be the row-normalized restriction of \(T_s\) onto \(G_t^\star\). In parallel, the semantic cosine similarity \(c_{t,k} = \cos(\phi(q'_t), \phi(x_k))\) between candidate hyperedge text \(x_k\) and the rewritten sub-query \(q'_t\) is computed.
To prevent irrelevant structural neighbors from siphoning transition probability, a gating threshold \(\theta = 0.4\) filters candidates: $\(T_{q,t}^\star[i, k] = \frac{\exp(c_{t,k}/\tau)}{\sum_{\ell \in N_{t,\theta}(i)} \exp(c_{t,\ell}/\tau)}\)$ for \(k \in N_{t,\theta}(i)\), where \(N_{t,\theta}(i) = \{k \in N_t(i) : c_{t,k} > \theta\}\). If no neighbor passes the threshold, the row falls back cleanly to the structural matrix. The overall transition matrix \(M_t\) balances topological navigation and semantic relevance via parameter \(\alpha\): $\(M_t = \alpha T_{s,t}^\star + (1 - \alpha) T_{q,t}^\star\)$ Personalized PageRank ranking over the local hypergraph is computed via power iteration: $\(\pi_t^{(r+1)} = (1 - \gamma) u_t^\star + \gamma M_t^\top \pi_t^{(r)}\)$ using restart distribution \(u_t^\star\) placed on the current hop seeds (with default settings \(\tau = 1, \theta = 0.4, \alpha = 0.5, \gamma = 0.85\)), ensuring probability mass concentrates on structurally connected evidence specifically relevant to the immediate sub-query.
3. Stateful Frontier Propagation & Hybrid Seeding: Bridge Entity Transfer and Local Trap Escape
Following decomposition of question \(Q\) into sub-queries \((q_1, \dots, q_m)\), carrying evidence state across steps is essential. When sub-query \(q_{t-1}\) is resolved (ANSWERED), the predicted bridge entity \(b_t\) and participating entities \(E_t\) of supporting hyperedges \(U_t\) are extracted to construct the next structural frontier \(C_{t+1} = \text{FindHyperedges}(\{b_t\} \cup E_t, H)\). If unresolved, the top-\(K_c\) hyperedges under \(\pi_t\) are carried forward as partial evidence.
Crucially, relying solely on carried structural frontiers exposes the pipeline to compounding error traps: if an intermediate bridge is flawed, the system risks becoming trapped in a disconnected or erroneous neighborhood. HyperProve resolves this by deploying a hybrid seed set for every hop \(t > 1\):
$\(S_t = \text{TopK}(C_t, K_c) \cup \text{DenseTopK}(q'_t, H, K_d)\)$
with \(K_c = K_d = 10\). The injection of fresh dense seeds \(F_t = \text{DenseTopK}(q'_t, H, K_d)\) conditioned on the rewritten query \(q'_t\) provides an essential escape hatch to recover gold evidence outside the current hyperedge cluster. If all sub-queries are resolved, intermediate answers are merged via IntegrateAnswers(Q, R); otherwise, ReaderFallback aggregates top documents via cross-hop max-merging and invokes the reader model once on the full question.
A Worked Example¶
Consider a complex 4-hop query from the MuSiQue benchmark requiring resolution of a city population ranking constrained by an entity chain:
1. Initial Decomposition & Parallel Resolution (Hop 1): The question is split into sub-queries seeking the performer of the song "Still Swingin'" and the headquarters of the organization "Pathology". Dense seeds select starting hyperedges, and local PPR converges on two independent atomic facts: "Still Swingin' is a song by American rock band Papa Roach." (resolving bridge entity Papa Roach) and "Pathology is based in San Diego." (resolving bridge entity San Diego).
2. Frontier Transfer & Geographic Binding (Hop 2): Using Papa Roach as the structural bridge frontier, the rewritten query searches for its place of origin. Local hypergraph expansion directly navigates through shared entity nodes to "Papa Roach was formed in Vacaville, California.", binding the geographic scope to California.
3. Constraint Confluence & Ranked Retrieval (Hops 3-4): The intermediate answers supply both the target entity San Diego and the regional constraint California. The rewritten query asks for the rank of the San Diego urban area within California. Because the carried hyperedge explicitly preserves the modifier "San Diego urban area" and its source provenance rather than flattening to generic city statistics, the local transition isolates the precise comparative fact and rejects distractor facts regarding generic city population rankings. The reader correctly concludes with the answer third-largest, whereas baselines like ChainRAG lose the modifier constraints and return 2nd.
Key Experimental Results¶
Main Results¶
HyperProve was evaluated on three multi-hop open-domain QA benchmarks: MuSiQue, HotpotQA, and 2WikiMultiHopQA (1,000-question subsets each). All methods utilized BGE-M3 as the retriever and GPT-OSS-20B as the backbone reader LLM. Reported metrics include LLM-as-a-judge answer accuracy (Acc), Exact Match (EM), and token-level F1 (mean ยฑ standard deviation across three runs).
| Category | Method | MuSiQue (Acc / EM / F1) | HotpotQA (Acc / EM / F1) | 2Wiki (Acc / EM / F1) |
|---|---|---|---|---|
| Dense Retrieval | Contriever | 47.80 / 22.30 / 32.10 | 55.55 / 44.40 / 57.50 | 69.60 / 38.50 / 43.70 |
| BGE-M3 | 51.50 / 27.80 / 39.70 | 68.12 / 47.80 / 61.80 | 72.18 / 48.20 / 54.50 | |
| Structured RAG | HippoRAG2 | 52.00 / 37.20 / 48.60 | 81.70 / 62.70 / 75.50 | 86.40 / 65.00 / 71.00 |
| PropRAG | 50.90 / 29.30 / 46.73 | 85.80 / 57.80 / 73.79 | 77.50 / 58.00 / 68.78 | |
| HyperGraphRAG | 55.13 / 42.20 / 53.80 | 77.89 / 63.90 / 73.80 | 77.72 / 68.30 / 71.30 | |
| HGRAG | 58.60 / 41.19 / 55.04 | 80.10 / 54.90 / 69.43 | 85.00 / 64.10 / 74.10 | |
| Iterative Retrieval | IRCoT | 56.67 / 34.10 / 47.60 | 85.23 / 55.70 / 71.20 | 83.65 / 60.70 / 74.30 |
| T2RAG | 54.67 / 34.30 / 45.60 | 81.33 / 54.20 / 67.30 | 83.75 / 66.70 / 74.40 | |
| HopRAG | 67.18 / 42.40 / 54.90 | 85.51 / 61.10 / 68.26 | 86.66 / 62.00 / 76.06 | |
| ChainRAG | 60.01 / 41.20 / 54.15 | 85.46 / 60.70 / 74.66 | 82.48 / 63.30 / 74.39 | |
| Ours | HyperProve | 71.60 / 42.83 / 59.23 | 91.30 / 63.92 / 76.64 | 91.40 / 69.70 / 80.01 |
Ablation Study¶
On the 1,000-question MuSiQue benchmark, component ablations broken down across reasoning depth (518 2-hop, 316 3-hop, and 166 4-hop examples) show the distinct necessity of each module:
| Configuration | Overall Acc (%) | 2-hop Acc (%) | 3-hop Acc (%) | 4-hop Acc (%) | Impact & Mechanism |
|---|---|---|---|---|---|
| HyperProve (Full Model) | 71.60 | 78.00 | 72.96 | 49.40 | Integrates hypergraph structure, frontier propagation, and fresh seeds |
| w/o bridge entity | 64.50 | 69.11 | 67.41 | 44.58 | Eliminates cross-hop entity binding; steep drops across all depths |
| w/o fresh dense seed | 61.30 | 71.24 | 59.18 | 34.34 | Trapped in local hypergraph traps; 4-hop accuracy collapses by 15.06% |
| w/o decomposition | 51.28 | 58.11 | 49.05 | 33.73 | Reverts to monolithic retrieval; incapable of multi-step factual chaining |
| w/o structural matrix \(T_s\) | 62.13 | 67.02 | 64.65 | 42.06 | Removes multi-entity and provenance paths; disrupts structural continuity |
| w/o query transition \(T_{q,t}^\star\) | 58.17 | 65.20 | 58.60 | 35.40 | Random walks lack sub-query semantic guidance, diffusing into noise |
Key Findings¶
- Crucial Escape Function of Fresh Dense Seeds: Omitting fresh dense seeds (
w/o fresh dense seed) inflicts the sharpest penalty on deeper reasoning chains, causing 4-hop accuracy to plummet from 49.40% to 34.34%. This underscores that carrying structural frontiers alone can act as an informational echo chamber; fresh dense seeds are essential to break out of locally incorrect graph neighborhoods. - Superior Evidence Chain Faithfulness: Measuring gold-passage retrieval at top-10 budget (Recall@10), HyperProve secures 82.31% on MuSiQue, 96.20% on HotpotQA, and 98.15% on 2WikiMultiHopQA, surpassing the best iterative baselines by 13.98 to 14.89 points. Furthermore, the average cumulative gold-passage coverage gain after the first hop reaches +41.24 (compared to +26.35 for ChainRAG and +25.98 for HopRAG), demonstrating that later hops systematically recover missing evidence rather than redundant text.
- Balanced Accuracy-Latency Pareto Frontier: During inference across 1,000 MuSiQue questions, HyperProve uses 9.6M tokens and 31.9K seconds of execution time, outperforming the heavy iterative baseline HopRAG (67.18% Acc) by 4.42 points while consuming 26.5M fewer tokens and reducing latency by 13.3K seconds.
Highlights & Insights¶
- Atomic Facts as State Carriers: Rather than reducing intermediate reasoning to plain text strings or fragmented binary triples, HyperProve encapsulates facts, participating entities, and document provenance in hyperedges, completely eliminating the loss of contextual modifiers during multi-step reasoning.
- Gated Semantic-Topology Coupling: Combining structural adjacency \(T_s\) with a cosine-gated semantic transition matrix \(T_{q,t}^\star\) ensures that probability diffusion is constrained by physical document/entity topology while being actively biased toward the immediate sub-query goal.
- Broad Transferability: The paradigm of coupling stateful frontier progression with fresh jump-out seeds is highly relevant beyond open-domain QA, extending naturally to multi-file code dependency navigation, multi-step anti-fraud transaction graph audit, and long-horizon scientific hypothesis discovery.
Limitations & Future Work¶
- Computational Overhead in Graph Construction: Offline passage parsing into entities and atomic facts incurs substantial LLM token expenses (20.8M tokens for 11,656 passages), which currently poses scalability hurdles for web-scale or real-time updating corpora. Distillation of extraction models remains an open exploration.
- Cascading Error Propagation: As highlighted in Case Study 2, when the model resolves an unsupported or erroneous entity at an intermediate step, subsequent expansion faithfully pursues this false frontier, generating locally consistent but globally hallucinated evidence chains. Incorporating uncertainty quantification and multi-frontier hypotheses represents a vital next step.
- Static Open-Domain Corpus Assumptions: Experiments rely on stable Wikipedia corpora with unambiguous gold answers; performance under heavily conflicting, temporally volatile, or highly noisy domain-specific enterprise data requires further benchmarking.
Related Work & Insights¶
- vs PropRAG: PropRAG operates over proposition paths via beam search, but scores all paths against the unchanged original question, leaving it vulnerable to semantic distractors; HyperProve dynamically rewrites sub-queries and updates structural frontiers.
- vs HyperGraphRAG / HGRAG: HyperGraphRAG and HGRAG employ hypergraphs with fixed-query diffusion or one-shot incidence expansion; HyperProve introduces stateful, multi-step answer-guided expansion where intermediate answers condition subsequent local transitions.
- vs IRCoT / ChainRAG: Iterative text-based systems adapt queries or reasoning traces across hops but lack explicit structural provenance; HyperProve anchors each hop's frontier in grounded atomic-fact hyperedges, achieving much higher recall (+14.89% Recall@10 on MuSiQue).
Rating¶
- Novelty: โญโญโญโญโญ Elegant integration of atomic-fact hyperedge modeling with answer-conditioned structural frontier tracking.
- Experimental Thoroughness: โญโญโญโญโญ Comprehensive cross-dataset evaluations, detailed depth-wise ablations, faithfulness recall analysis, and insightful failure case dissections.
- Writing Quality: โญโญโญโญโญ Mathematically rigorous formulations, clear algorithmic exposition, and informative visuals.
- Value: โญโญโญโญโญ Establishes a compelling blueprint for uniting graph-structured knowledge representations with stateful iterative LLM reasoning.