HyperProve: Answer-Guided Hypergraph Expansion for Multi-Hop Question Answering

An Nguyen Phu; Dung Nguyen Quang; Luu Hieu An; Linh Ngo Van; Trung Le; Thien Huu Nguyen

cs.CLSep 12, 2026

HyperProve: Answer-Guided Hypergraph Expansion for Multi-Hop Question Answering

Authors: An Nguyen Phu, Dung Nguyen Quang, Luu Hieu An, Linh Ngo Van, Trung Le, Thien Huu Nguyen

Organizations: Hanoi University of Science and Technology · Monash University · University of Oregon

Abstract

Multi-hop question answering often fails when retrieval treats evidence as isolated matches to the original question, since the facts needed to answer a complex question are usually connected through intermediate entities, relations, and constraints. We propose HyperProve, a retrieval-augmented QA framework that addresses this challenge by coupling question decomposition with answer-conditioned expansion over a hypergraph of atomic facts. HyperProve does not use atomic facts, hypergraphs, or iterative retrieval in isolation; instead, it carries intermediate answers and supporting hyperedges as retrieval state, then uses that state to bias the next local hypergraph expansion. This design enables HyperProve to construct coherent evidence chains for final answer generation while making the retrieval process stateful and fact-centered. Across multi-hop QA benchmarks, HyperProve achieves the best overall performance in our evaluation, outperforming the strongest baselines by an average relative improvement of 6.2% in answer accuracy and 4.9% in F1.

Figures & tables

Figure 1: Case study of a 4-hop question: PropRAG fails to connect Last Supper to Peter and drifts to the distractor chain Venice $\rightarrow$ Republic of Venice ; HyperProve succeeds because atomic-fact hyperedges explicitly preserve the bridge entities and correct path.

Figure 2: Overall HyperProve pipeline. The system builds an offline synonym-aware atomic-fact hypergraph from corpus passages, then performs online answer-guided multi-hop reasoning by decomposing a question into sub-queries, carrying intermediate answers as bridge entities, expanding over local hypergraph neighborhoods, and integrating the resulting evidence chain into a final answer.

	MuSiQue			HotpotQA			2Wiki
Method	Acc.	EM	F1	Acc.	EM	F1	Acc.	EM	F1
Dense Retrieval
Contriever	47.80 $\,\pm\,$ 0.28	22.30 $\,\pm\,$ 0.30	32.10 $\,\pm\,$ 0.26	55.55 $\,\pm\,$ 0.21	44.40 $\,\pm\,$ 0.24	57.50 $\,\pm\,$ 0.21	69.60 $\,\pm\,$ 0.20	38.50 $\,\pm\,$ 0.24	43.70 $\,\pm\,$ 0.21
BGE-M3	51.50 $\,\pm\,$ 0.25	27.80 $\,\pm\,$ 0.27	39.70 $\,\pm\,$ 0.24	68.12 $\,\pm\,$ 0.19	47.80 $\,\pm\,$ 0.22	61.80 $\,\pm\,$ 0.19	72.18 $\,\pm\,$ 0.18	48.20 $\,\pm\,$ 0.22	54.50 $\,\pm\,$ 0.19
Structured Retrieval
HippoRAG2	52.00 $\,\pm\,$ 0.36	37.20 $\,\pm\,$ 0.40	48.60 $\,\pm\,$ 0.34	81.70 $\,\pm\,$ 0.29	62.70 $\,\pm\,$ 0.33	75.50 $\,\pm\,$ 0.29	86.40 $\,\pm\,$ 0.28	65.00 $\,\pm\,$ 0.34	71.00 $\,\pm\,$ 0.29

Table 1: Mean

\pm

standard deviation over three runs on multi-hop QA benchmarks. We report LLM-as-a-judge answer accuracy, Exact Match (EM), and token-level F1. Best means are in bold ; second-best means are underlined .

Variant	Overall	2-hop	3-hop	4-hop
HyperProve	71.60	78.00	72.96	49.40
w/o bridge entity	64.50	69.11	67.41	44.58
w/o fresh dense seed	61.30	71.24	59.18	34.34
w/o decomposition	51.28	58.11	49.05	33.73
w/o $T_{s}$	62.13	67.02	64.65	42.06
w/o query transition	58.17	65.20	58.60	35.40

Table 2: Accuracy breakdown of HyperProve ablations on MuSiQue by reasoning depth. Accuracy is computed using judge verdicts over 1000 questions: 518 2-hop, 316 3-hop, and 166 4-hop examples.

Method	Recall@10			Avg Gain
	MuSiQue	HotpotQA	2Wiki	After Hop 1
HyperProve	82.31	96.20	98.15	+41.24
ChainRAG	67.42	89.45	75.85	+26.35
HopRAG	66.63	82.82	84.17	+25.98

Table 3: Evidence chain faithfulness across multi-hop benchmarks. Dataset columns report Recall@10, computed as the average fraction of gold passages retrieved in the top 10 results. Avg Gain after Hop 1 measures the average increase in cumulative gold-passage coverage after the first hop.

Figure 3: Hop-wise cumulative support coverage. Cumulative gold-passage coverage increases across hops, showing that later sub-queries progressively recover missing support evidence.

System	Top-10 Coverage	Retrieval / Reasoning Behavior	Final Answer
HyperProve	4 / 4	Separately resolves Pathology $\rightarrow$ San Diego and Still Swingin’ $\rightarrow$ Papa Roach $\rightarrow$ California , then applies the rank query to San Diego under the California urban-area constraint.	third-largest
ChainRAG	2 / 4	Retrieves evidence for Pathology $\rightarrow$ San Diego and Still Swingin’ $\rightarrow$ Papa Roach , but misses the facts needed to bind Papa Roach $\rightarrow$ Vacaville, California and San Diego urban area $\rightarrow$ third-largest in California . Its reader is then pulled to a nearby city-rank answer.	2nd

Table 4: Qualitative comparison on a multi-entity MuSiQue example. HyperProve retrieves the complete evidence chain and preserves the urban-area constraint, while ChainRAG retrieves only partial evidence and confuses city population rank with urban-area rank.

Method	Extraction	Calls	Tokens	Cost source
HyperGraphRAG	Facts+entities	11,656	20.9M	Normalized est.
PropRAG	Entities+props.	23,312	21.1M	Reported measure
HGRAG	Entities	11,656	5.7M	Normalized est.
HyperProve	Entities+facts	23,312	20.8M	Measured artifacts

Table 5: Offline and online efficiency on MuSiQue. Panel (a) explicitly separates measured or reported costs from estimates normalized to the 11,656-passage corpus and the same token accounting. Panel (b) reports measured inference over 1,000 questions. All token and latency values exclude answer-judge cost.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Category	Retrieval Unit	Multi-step	Main Role
Contriever	Dense Retrieval	Passage	No	Unsupervised dense retrieval baseline
BGE-M3	Dense Retrieval	Passage	No	Strong dense retriever and HyperProve seed retriever
HippoRAG2	Structured RAG	Passage + Triples	Yes	Associative graph retrieval baseline
PropRAG	Structured RAG	Propositions	Yes	Structured fact retrieval baseline
HyperGraphRAG	Structured RAG	Propositions	Yes	Hypergraph-structured retrieval baseline
HGRAG	Structured RAG	Propositions	Yes	Entity–passage hypergraph baseline

Appendix

Table 9: Summary of baseline methods and retrieval units. HyperProve differs from prior methods by combining atomic-fact hyperedges with answer-guided, stateful expansion over local hypergraph neighborhoods.

Depth	Fallbacks	Questions	Rate
2-hop	41	518	7.92%
3-hop	38	316	12.03%
4-hop	44	166	26.51%
Overall	123	1,000	12.30%

Appendix

Table 6: Reader-fallback frequency by annotated reasoning depth on MuSiQue.

$\alpha$	$\theta$	Recall	EM	F1	Acc.
0.50	0.40	82.31	42.83	59.23	71.60
0.25	0.40	81.18	42.41	58.76	70.80
0.75	0.40	83.06	43.12	59.61	71.40
0.50	0.30	83.45	41.97	58.49	70.30
0.50	0.50	81.72	43.05	59.40	71.90

Appendix

Table 7: MuSiQue sensitivity to structural-transition weight

\alpha

and query-transition threshold

\theta

. The first row is the default configuration.

Dataset	Questions	Passages	Entities	Hyperedges
2WikiMultiHopQA	1,000	6,119	57,906	55,032
HotpotQA	1,000	9,812	112,308	99,394
MuSiQue	1,000	11,656	117,894	105,542

Appendix

Table 8: Dataset statistics for the 1,000-question evaluation subsets.

Figure 4: Qualitative comparison on a hidden-bridge MuSiQue example. HyperProve carries intermediate answers as bridge entities, enabling retrieval around Stanton Moore , New Orleans , and the Battle of New Orleans . In contrast, HippoRAG2 over-emphasizes broad surface terms from the original question and misses the hidden evidence chain.

Explore similar work

Hi-Q: Hierarchical Evidence-guided Query Refinement for Multi-Hop Question Answering
Aug 31, 2026Jueun Kim, Sungho Park, Wook-Shin HanMulti-Hop QA Question Decomposition
Department of Computer Science and Engineering, POSTECH · Graduate School of Artificial Intelligence, POSTECH
Beyond One-Shot Expansion: Contrastive Evidence Exploration for Multi-Hop Retrieval
Sep 7, 2026JungMin Yun, YoungBin KimEvidence Retrieval Information Retrieval
Chung-Ang University Seoul, Republic of Korea
HyperReCo: Retrieving and Connecting Evidence with Hypergraph Neural Networks for LLM Multi-hop Reasoning
Sep 26, 2026Zicheng Zhao, Linhao Luo, Junnan Dong +4Graph Retrieval-Augmented Generation Multi-Hop QA
Shanghai Jiao Tong University · Singapore University of Technology and Design · Monash University +3

Aug 31, 2026J/K move · Enter open · S save

Hi-Q: Hierarchical Evidence-guided Query Refinement for Multi-Hop Question Answering

Jueun Kim, Sungho Park, Wook-Shin Han

Department of Computer Science and Engineering, POSTECH · Graduate School of Artificial Intelligence, POSTECH

Multi-Hop QA Question Decomposition Multi-Hop Reasoning Evidence Retrieval

Open paper AskPDF arXiv

A central bottleneck in multi-hop Question Answering (QA) is that the granularity at which a question is expressed often differs from the granularity at which corpus evidence is retrievable. Existing methods address this mismatch by imposing fixed graph structures over the corpus, by iteratively reformulating the query, or by executing a generated program over it, but these strategies do not explicitly decide when a query unit is already supported by evidence and when it should be refined. We formulate this bottleneck as retrievable granularity discovery and introduce Hi-Q, an evidence-conditioned framework for hierarchical query refinement. At each query node, a resolution operator tests whether retrieved evidence supports the current query unit; resolved nodes terminate, while unresolved nodes are expanded by a dependency-preserving binary operator and checked by a semantic coverage verifier. Hi-Q therefore grows a query tree whose topology is determined by corpus support signals rather than by a fixed decomposition template or a pre-built graph. We evaluate Hi-Q on three multi-hop QA benchmarks, primarily under full-corpus retrieval, where dependent evidence must be located among open-domain distractors rather than within a small annotated pool. In this setting Hi-Q reaches 52.3 EM and 64.0 F1 averaged over the three benchmarks, ahead of the iterative retrieval baseline IRCoT by 15.1 EM / 18.2 F1 on that same average, and ahead of the graph-based RAG baseline PropRAG by 11.5 EM / 12.0 F1 on MuSiQue-full, without corpus-wide graph construction. In the restricted supporting/distractor setting used by prior work, Hi-Q likewise attains the best accuracy, with 57.9 EM and 69.3 F1 on average, ahead of PropRAG by 5.6 EM / 3.9 F1 and IRCoT by 13.7 EM / 15.8 F1. The project page is available at https://hi-q-project.github.io/.

Abstract

Explore similar work

Hi-Q: Hierarchical Evidence-guided Query Refinement for Multi-Hop Question Answering

Beyond One-Shot Expansion: Contrastive Evidence Exploration for Multi-Hop Retrieval

HyperReCo: Retrieving and Connecting Evidence with Hypergraph Neural Networks for LLM Multi-hop Reasoning