HyperRAG: Reasoning N-ary Facts over Hypergraphs for Retrieval Augmented Generation

Probleemstelling

Bestaande Retrieval-Augmented Generation (RAG) systemen die op grafen gebaseerd zijn, opereren doorgaans op binair kennisgrafieken (Knowledge Graphs of KGs), waar relaties worden gemodelleerd als triples (onderwerp, relatie, object). Dit benadering heeft twee fundamentele beperkingen bij het hanteren van complexe feiten:

1. Semantische Fragmentatie: Complexe feiten die meerdere entiteiten en rollen omvatten, moeten worden opgesplitst in losstaande binaire triples. Hierdoor gaat de structurele integriteit en de semantische nuance van de oorspronkelijke informatie verloren.
2. Pad-Explosie (Path Explosion): Om een antwoord te vinden dat gebaseerd is op deze gefragmenteerde feiten, moet het systeem diepe traversies uitvoeren over de grafiek (meerdere hops). Dit leidt tot een enorme rekenkundige last, verhoogt het risico op foutpropagatie en veroorzaakt "retrieval drift" (het systeem raakt de juiste context kwijt).

Het paper stelt dat n-ary hypergrafieken (waarbij één hyperedge meerdere entiteiten en rollen tegelijk verbindt) een superieure topologie bieden. Ze behouden de hoge-orde relationele integriteit en maken het mogelijk om complexe redeneringen in minder stappen (shallower reasoning paths) uit te voeren.

Methodologie: HyperRAG Framework

HyperRAG is een nieuw framework dat specifiek is ontworpen om redenering over n-ary hypergrafieken mogelijk te maken. Het introduceert twee complementaire retrieval-paradigma's:

1. HyperRetriever (Leerbaar Structuur-Semantisch Redeneren)

Dit is een trainbaar module dat gebruikmaakt van een Multilayer Perceptron (MLP) om structurele en semantische signalen te fuseren.

• Topic Entity Extractie: Identificeert kernentiteiten in de vraag.
• Hyperedge Retrieval & Pseudo-triples: Haalt hyperedges op die met de entiteiten verbonden zijn en genereert gepseudode binaire triples voor redenering.
• Structuur Proximity Encoding: Gebruikt een Directional Distance Encoding (DDE) mechanisme om de structurele nabijheid tussen entiteiten in de hypergraaf te coderen (forward en backward propagatie).
• Contrastieve Plausibiliteitsscore: Een MLP-classificator schat de waarschijnlijkheid (plausibility) van een triple om irrelevante paden te filteren.
• Adaptieve Zoekstrategie: In plaats van een vaste drempelwaarde, past het systeem de drempel dynamisch aan op basis van de dichtheid van de hypergraaf. Dit voorkomt dat te weinig of te veel informatie wordt opgehaald.
• Context-gevoelige Generator: Organiseert de opgehaalde hyperedges, entiteiten en tekstfragmenten in een gestructureerde context, waarbij prioriteit wordt gegeven aan hyperedges (50% van het token-budget) omdat deze het meest waardevol zijn voor redenering.

2. HyperMemory (LLM-Gedreven Beam Search)

Deze variant gebruikt het parametrische geheugen van de Large Language Model (LLM) zelf om de zoektocht te sturen, zonder een aparte trainbare classifier.

• Memory-Guided Beam Search: Voert een beam search uit (breedte $w=3$, diepte $d=3$) waarbij de LLM hyperedges en entiteiten scoort op relevantie voor de vraag.
• Dynamische Score: De LLM beoordeelt hyperedges en de daaruit voortvloeiende entiteiten om de zoekpaden te prioriteren.
• Evidence Check: Op elk stapje wordt gecontroleerd of de geaccumuleerde informatie voldoende is om de vraag te beantwoorden.

Belangrijkste Bijdragen

1. Paradigmaverschuiving: HyperRAG verschuift het RAG-paradigma van binaire triples naar n-ary hypergrafieken, waardoor semantische fragmentatie en pad-explosie worden opgelost.
2. HyperRetriever: Een trainbare, MLP-gebaseerde module die structurele en semantische signalen combineert voor snelle, interpreteerbare en nauwkeurige evidentiële ketens.
3. HyperMemory: Een synergetische aanpak die het parametrische geheugen van de LM gebruikt om symbolische beam search over hypergrafieken te leiden voor adaptieve redenering.
4. Uitgebreide Evaluatie: Het framework is getest op zowel gesloten domeinen (WikiTopics met 11 verschillende onderwerpen) als open domeinen (HotpotQA, MuSiQue, 2WikiMultiHopQA), waarbij het consistent superieur presteert aan bestaande baselines.

Resultaten

De experimentele resultaten tonen aan dat HyperRAG, en met name de HyperRetriever-variant, aanzienlijk beter presteert dan state-of-the-art baselines (zoals RAPTOR, HippoRAG, ToG en HyperGraphRAG):

• Gesloten Domein (WikiTopics): HyperRetriever behaalde de hoogste algehele antwoordnauwkeurigheid. De gemiddelde verbetering ten opzichte van de sterkste baseline was 2,95% voor MRR (Mean Reciprocal Rank) en 1,23% voor Hits@10.
• Open Domein: Hoewel er variatie is per dataset (afhankelijk van de dichtheid van de kennisgrafiek), presteert HyperRetriever sterk, met name op datasets met complexe relationele contexten (zoals 2WikiMultiHopQA, waar een verbetering van 11,89% in F1 werd gezien).
• Ablatie Studies:
  • Het vervangen van de n-ary structuur door een binaire structuur resulteerde in een daling van de MRR van 36,45% naar 34,15%, wat het belang van de hogere-orde relaties bevestigt.
  • Hyperedges bleken de belangrijkste component voor contextvorming; het verwijderen hiervan leidde tot de grootste prestatiedalingen.
  • De adaptieve zoekstrategie verbeterde de rangschikking (MRR) aanzienlijk zonder de recall (Hits@10) te schaden.
• Efficiëntie: Door het gebruik van n-ary hyperedges kan HyperRAG redeneren met "shallow chains" (vlakke paden), wat leidt tot een constante overhead per query ($O(1)$) in vergelijking met de hogere kosten van binaire traversies ($O(n-k)$).

Betekenis en Impact

HyperRAG biedt een fundamentele verbetering in hoe RAG-systemen complexe kennis hanteren. Door de afhankelijkheid van binaire triples te doorbreken en over te stappen op n-ary hypergrafieken, lost het systeem de problemen van semantische fragmentatie en inefficiënte diepe traversies op.

De belangrijkste implicaties zijn:

• Betere Redenering: Het vermogen om complexe, multi-entiteit feiten in één stap te modelleren, leidt tot nauwkeurigere en meer interpreteerbare antwoorden.
• Efficiëntie: Minder stappen in de redeneringsketen betekenen minder latency en minder rekenkracht nodig voor het ophalen van informatie.
• Schaalbaarheid: Het adaptieve mechanisme maakt het framework robuust voor verschillende domeinen en grafiekdichtheden, wat het toepasbaar maakt voor zowel gespecialiseerde als open domein-toepassingen.

Kortom, HyperRAG bewijst dat het modelleren van hoge-orde afhankelijkheden via hypergrafieken essentieel is voor de volgende generatie nauwkeurige en betrouwbare RAG-systemen.