PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zicheng Zhao, Linhao Luo, Junnan Dong, Haoran Luo, Xiaoli Li, Shirui Pan, Chen Gong

arXiv:2609.32327v1cs.AI

TL;DR

Existing hypergraph retrievers may miss query-dependent interactions needed to find complementary evidence, while leaving connections among retrieved documents implicit. HyperReCo learns structural relevance over document hyperedges and decodes explicit hyper-paths; it reports strong retrieval and QA performance across six benchmarks.

  • Problem

    Existing hypergraph retrievers often rely on predefined expansion or diffusion that may miss query-dependent interactions needed to identify relevant, complementary evidence.

    Source: §1 · p. 2

  • Method

    HyperReCo uses a query-conditioned HyperGNN with joint document and entity supervision to retrieve evidence, then applies gradient-guided decoding and a query-conditioned forest objective to produce explicit hyper-paths.

    Source: §1 · p. 2, §4 · p. 4, §4.1 · p. 5

  • Results

    HyperReCo achieves the strongest retrieval and downstream QA performance on all three multi-hop QA benchmarks and shows strong retrieval and QA performance across six benchmarks.

    Source: §5.2 · p. 8, §6 · p. 10

  • Takeaways & Limitations

    The paper concludes that multi-hop reasoning requires not only retrieving relevant evidence but also exposing how that evidence is connected.

    Source: §6 · p. 10

Abstract

from arXiv · show

Large language models (LLMs) have shown strong capabilities, with retrieval-augmented generation (RAG) supporting complex multi-hop reasoning by retrieving evidence distributed across documents. Graph-based approaches exploit connections among evidence, and hypergraph-based retrieval further preserves higher-order entity associations within documents and connects documents through shared entities. However, existing hypergraph retrievers often rely on predefined structural expansion or diffusion, which may miss query-dependent interactions needed to identify relevant evidence. They also leave connections among retrieved evidence implicit, requiring LLMs to reconstruct these connections before reasoning. Therefore, we propose HyperReCo, a framework for retrieving and connecting evidence with a hypergraph neural network (HyperGNN). We represent each document as a hyperedge over its extracted entities, with shared entities connecting the hyperedges. Through hypergraph message passing with joint supervision over documents and entities, the HyperGNN learns query-dependent interactions to retrieve complementary evidence. We further introduce Gradient-Guided Hyper-Path Decoding (GGHD), which uses gradient attribution to interpret the learned interactions and translate them into explicit hyper-paths that help LLMs combine complementary facts for multi-hop reasoning. Experiments on six benchmarks show that HyperReCo achieves the best retrieval performance among the compared methods on all three multi-hop QA datasets, together with strong downstream QA performance. Case studies and further analyses demonstrate the utility of decoded hyper-paths for connecting retrieved evidence.

1 INTRODUCTION

HyperReCo targets the challenge of retrieving and connecting complementary evidence across documents for LLM multi-hop reasoning. It learns query-dependent structural relevance and decodes explicit hyper-paths, with strong benchmark results reported.

1 INTRODUCTION

  • Existing hypergraph retrievers use predefined expansion or diffusion, which may miss query-dependent interactions and complementary evidence (Song et al., 2026; Feng et al., 2026; Luo et al., 2025a; Wang et al., 2026).Graph-based approaches can also incur the cost of extracting relational triples, while triples encode only binary relations (Edge et al., 2024; Wen et al., 2016).Source: §1 · pp. 1–2
  • HyperReCo models each document as a hyperedge over extracted entities and learns query-conditioned interactions through hypergraph message passing and joint document-entity supervision.GGHD attributes document predictions to entity-mediated messages, then uses a query-conditioned prize-collecting Steiner forest objective to serialize explicit paths linking retrieved evidence.Source: §1 · p. 2
  • HyperReCo achieves state-of-the-art performance across three widely used QA datasets, with analyses showing decoded paths provide explicit evidence connections for downstream question answering.The framework represents documents as entity hyperedges, learns query-dependent interactions, and uses GGHD to turn those interactions into grouped hyper-paths.Source: §1 · p. 3

2 RELATED WORK

Related work extends retrieval with graph structure, higher-order hypergraph associations, and path-based interpretation. HyperReCo learns query-conditioned relevance over evidence-bearing hyperedges and decodes explicit connections for LLM reasoning.

2 RELATED WORK

3 PRELIMINARY

The paper represents a corpus as documents linked through shared entities, then defines hyper-paths as explicit sequences of connected document hyperedges.

3 PRELIMINARY

  • Each document induces its own hyperedge over canonical entities extracted with LLM-based named entity recognition, and shared entities connect the corresponding document hyperedges.The representation retains a separate hyperedge for each document, including when two documents have identical entity sets, and avoids extracting relational triples.Source: §3 · pp. 3–4
  • A hyper-path is a sequence of distinct document hyperedges connected through nonempty shared entity sets, making entity-mediated transitions explicit for reasoning.The path uses selected shared entities at each transition and spans one or more document-to-document transitions.Source: §3 · p. 4

4 APPROACH

HyperReCo pairs a query-conditioned HyperGNN retriever with Gradient-Guided Hyper-Path Decoding (GGHD) to retrieve relevant evidence and make its connections explicit for LLM reasoning.

4.1 HYPERGRAPH NEURAL NETWORK RETRIEVER

  • Each document becomes a hyperedge over extracted entities, and shared entities link hyperedges in a hypergraph.A query-conditioned HyperGNN alternates information between hyperedges and entities to learn how shared entities contribute to evidence relevance.Source: §4 · p. 4, §4.1 · pp. 4–5
  • Joint supervision of hyperedges and entities trains the HyperGNN to rank evidence units and return documents from the top-K hyperedges.Document labels supervise hyperedge relevance, while entities in supporting documents provide weak entity supervision; semantic distillation also contributes to optimization.Source: §4.1 · p. 5, §4.3 · p. 6

4.2 GRADIENT-GUIDED HYPER-PATH DECODING

  • GGHD uses gradient attribution on entity-mediated messages to expose learned relevance as explicit connections among retrieved documents.A query-conditioned prize-collecting Steiner forest balances attributed connection costs against relevance-dependent connectivity demands; routes may use intermediate retrieved documents, and demands may remain unmet when connection costs outweigh avoided penalties.Source: §4.2 · pp. 5–6

4.3 OPTIMIZATION AND ANSWER GENERATION

  • After training, GGHD decodes the learned relevance without updating the model, and the resulting hyper-paths accompany retrieved documents for answer generation.The paths guide cross-document evidence composition, while factual claims remain grounded in retrieved content.Source: §4.3 · p. 6

5 EXPERIMENT

The experiments assess HyperReCo across multi-hop and domain-specific QA, component ablations, hyper-path analyses, and efficiency. The reported results cover retrieval, downstream QA, and the role of explicit evidence connections.

5.1 EXPERIMENTAL SETUP

  • The evaluation covers three multi-hop QA datasets and three domain-specific GraphRAG datasets, with comparisons against non-structure and graph-enhanced baselines.QA and retrieval are evaluated using EM/F1 or ACC and recall metrics, respectively.Source: §5.1 · p. 7

5.2 MAIN RESULTS (RQ1 & RQ2)

  • HyperReCo achieves the strongest performance on all three multi-hop QA benchmarks for retrieval and downstream QA, and the best QA performance on the medical benchmark while remaining competitive across domains.The domain-specific evaluations use no domain-specific training.Source: §5.2 · p. 8, Table 2 · p. 8

5.3 ABLATION STUDY (RQ3)

  • Removing HyperGNN, message passing, or query-dependent modeling consistently degrades R@5 across the three multi-hop QA datasets.The ablation compares the full model with NV-Embed-v2 retrieval and variants that remove structural propagation or query conditioning.Source: §5.3 · p. 8, Figure 3 · p. 9

5.4 ANALYSIS OF HYPER-PATH EFFECTIVENESS (RQ4)

  • GGHD achieves the highest mean EM among the decoding strategies, which vary path provision, global forest optimization, and connection-construction strategy.The comparison keeps the retrieved documents, downstream reader, and answer-generation procedure unchanged.Source: §5.4 · pp. 8–9, Figure 4 · p. 9
  • With the same top-five documents and perfect supporting-document recall, only hyper-path guidance enables the LLM to connect the two facts and answer correctly.GGHD exposes the connection from D1 through William Montagu Douglas Scott, 6th Duke of Buccleuch, to D3.Source: §5.4 · p. 9, Table 3 · p. 9

5.5 EFFICIENCY ANALYSIS (RQ5)

  • Index construction uses 3.3M LLM tokens per 10K documents, while online inference takes 3.55 seconds per query and remains comparable to GFM-RAG and HGRAG.The reported latency is macro-averaged over HotpotQA, MuSiQue, and 2Wiki.Source: §5.5 · p. 9, Table 4 · p. 9

6 CONCLUSION

HyperReCo combines query-conditioned structural relevance learning with explicit hyper-paths to retrieve and connect evidence for multi-hop reasoning. The paper reports strong retrieval and QA performance across six benchmarks and concludes that reasoning requires exposing how retrieved evidence is connected.

6 CONCLUSION

  • HyperReCo combines a query-conditioned HyperGNN for retrieving complementary evidence with GGHD, which turns learned interactions into explicit paths for cross-document evidence composition.Ablations and qualitative analyses support the effectiveness of structural relevance learning and hyper-path guidance.Source: §6 · p. 10

DECLARATION OF LARGE LANGUAGE MODEL USAGE

The authors report using generative AI tools for proofreading, language polishing, code implementation and debugging, and experimental components.

DECLARATION OF LARGE LANGUAGE MODEL USAGE

  • Generative AI assisted with proofreading, language polishing, code implementation and debugging, and LLM-based entity extraction, answer generation, and hyper-path evaluation.The authors state that they reviewed the text and inspected, tested, and verified the code.Source: DECLARATION OF LARGE LANGUAGE MODEL… · p. 10

ETHICS STATEMENT

The authors report that the research involved no human subjects, animals, or environmentally sensitive materials and that they anticipate no significant ethical risks or conflicts of interest.

ETHICS STATEMENT

  • The authors report no human subjects, animals, or environmentally sensitive materials and anticipate no significant ethical risks or conflicts of interest.They state a commitment to scientific integrity, reliability, and transparency.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The paper documents its experimental procedures and settings, identifies the resources used, and states that code and configurations will be made available for reproducing the main experiments.

REPRODUCIBILITY STATEMENT

  • Experimental settings, implementation details, hyperparameters, and data processing procedures are provided in the main text and Appendix B.The authors state that the settings and baselines were rigorously verified for fair comparison.Source: REPRODUCIBILITY STATEMENT · p. 10
  • The paper specifies the datasets, backbone models, retrieval settings, and language models used throughout the evaluation.Source: REPRODUCIBILITY STATEMENT · p. 10
  • Code and configurations for reproducing the main experiments will be made available.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 DATASET STATISTICS

This material reports the training and evaluation datasets, then details query-conditioned HyperGNN initialization and propagation and the exact Q-PCSF decoding procedure.

A.1 DATASET STATISTICS

  • The training corpus uses 6,000 questions from HotpotQA, MuSiQue, and 2Wiki, while evaluation covers those three benchmarks plus G-bench Novel, Medical, and CS.The training corpus contains 53,573 documents and 326,286 extracted entities.Source: §A.1 · p. 13

B.1.1 QUERY-DEPENDENT REPRESENTATION INITIALIZATION

  • The retriever selects top-K documents by query-document cosine similarity and injects query information into hyperedge states; entity initialization also uses query-linking and corpus-level features.Query-document relevance controls the strength of query conditioning on seed hyperedges, while entity initialization includes a query-entity similarity gate.Source: §B.1.1 · pp. 13–14

B.1.2 QUERY-CONDITIONED HYPERGRAPH MESSAGE PASSING

  • HyperGNN message passing alternates hyperedge-to-entity and entity-to-hyperedge updates, using query-conditioned membership roles and attention to aggregate information.The entity update can incorporate information from its source hyperedges, including information transferred through shared entities.Source: §B.1.2 · pp. 14–15

B.2 EXACT Q-PCSF SOLVER

  • The exact Q-PCSF solver enumerates candidate edge subsets, discards cyclic forests, scores valid forests by edge costs and unsatisfied-demand penalties, and returns the minimum-objective forest.Connectivity demands are assessed over the whole forest, including paths through intermediate retrieved documents.Source: §B.2 · pp. 15–16

B.3 TRAINING OBJECTIVES

This block covers the training objectives and implementation, then reports robustness, inference efficiency, and analyses of hyper-path decoding.

B.3 TRAINING OBJECTIVES

  • Training supervises document relevance with binary cross-entropy and a ranking loss, and entity relevance with pointwise and listwise objectives.Semantic distillation also regularizes document relevance predictions toward the frozen text encoder's semantic relevance scores.Source: §B.3 · p. 16

B.4 IMPLEMENTATION DETAILS

  • Implementation uses frozen NV-Embed-v2 representations and a two-layer HyperGNN, trained on 6,000 questions from HotpotQA, MuSiQue, and 2Wiki.The model uses five dense seed documents and trains for at most 30 epochs with early stopping.Source: §B.4 · p. 17

B.5 DETAILED PROMPTS FOR INFERENCE

  • For HyperReCo inference, decoded hyper-paths accompany retrieved documents as cross-document navigation cues, while document contents remain the factual evidence for generation.The complete inference prompt is shown in Figure 5.Source: §B.5 · p. 17, Figure 5 · p. 18

B.6 DETAILED DESCRIPTIONS OF BASELINE METHODS

  • The baselines span non-structural lexical or semantic retrieval and graph-enhanced methods that model dependencies beyond independent document similarity.The listed approaches include sparse and dense retrievers, graph systems, and hypergraph methods.Source: §B.6 · pp. 17–19

C.1 ROBUSTNESS TO DIFFERENT EMBEDDING MODELS

  • Across four embedding models, HyperReCo maintains strong retrieval performance and consistently outperforms HGRAG; 2Wiki R@5 stays at or above 97%.On HotpotQA, R@5 remains above 91% even with the 0.6B encoder.Source: Table 7 · p. 19, §C.1 · p. 19

C.2 DETAILED INFERENCE EFFICIENCY

  • HyperReCo achieves the highest EM on all three multi-hop QA datasets, improving macro-average EM by 4.2 points over HGRAG and 5.5 points over GFM-RAG.Average end-to-end latency is 3.55 seconds per query, close to HGRAG (3.08 s) and GFM-RAG (3.36 s).Source: Table 8 · p. 19, §C.2 · p. 20

C.3 ADDITIONAL ANALYSIS OF HYPER-PATH DECODING

  • Removing explicit hyper-paths lowers mean EM from 57.6 to 55.0, while G-paths and S-forest also remain below full GGHD.The authors conclude that query-dependent connection scoring and global forest optimization both contribute to final performance.Source: Table 9 · p. 20, §C.3 · p. 20

C.4 LLM-AS-A-JUDGE EVALUATION OF HYPER-PATHS

The paper evaluates decoded hyper-path utility with an LLM judge and illustrates how a shared-entity path can make a cross-document dependency explicit.

C.4 LLM-AS-A-JUDGE EVALUATION OF HYPER-PATHS

  • GGHD achieves a 59.2% helpful-path ratio with 1.68 paths per question, the highest ratio and fewest paths among the evaluated strategies.The judge assesses paths jointly for complementary evidence before labeling each path helpful.Source: Table 10 · p. 21, §C.4 · p. 21

C.5 QUALITATIVE ANALYSIS OF DECODED HYPER-PATHS

  • In the Lord George Scott example, a shared-entity path connects the document identifying his father to the document giving the father's death date, enabling the correct answer.Both settings retrieve all supporting documents, but only the hyper-path-guided setting answers correctly.Source: Table 11 · p. 22, §C.5 · p. 22

Related papers

Loading 2609.32327v1…