CacheRAG: A Semantic Caching System for Retrieval-Augmented Generation in Knowledge Graph Question Answering

1. Probleemstelling

Het artikel adresseert kritieke beperkingen in huidige Large Language Model (LLM)-gedreven Knowledge Graph Question Answering (KGQA) systemen, specifiek die Retrieval-Augmented Generation (RAG) gebruiken. Bestaande systemen lijden onder twee fundamentele gebreken:

• Stateless Planning & Schema Hallucinatie: Huidige LLM's fungeren als "stateless planners" en genereren voor elke nieuwe vraag losstaande ophaalplannen (bijv. SPARQL-query's of API-oproepen) zonder gebruik te maken van historische querypatronen. Dit leidt tot schema hallucinaties, waarbij de LLM niet-bestaande predicaten of attributen verzonnet (bijv. het opvragen van een "magisch" predikaat dat niet in het schema bestaat) omdat het geen gronding heeft in het specifieke lokale schema.
• Beperkte Ophaaldekking: Zero-shot planning resulteert vaak in ondiepe, onvolledige querystructuren. Als de initiële ophaalactie faalt of lege resultaten oplevert, geeft het systeem zich vaak op in plaats van alternatieve paden te verkennen (multi-hop redenering), wat leidt tot hoge "miss rates".
• Inefficiëntie van Traditionele Caching: Het naïef toepassen van traditionele database plan-caching (geoptimaliseerd voor frequentie, bijv. LRU/LFU) faalt in LLM-contexten. LLM's profiteren meer van diversiteit in hun contextvenster dan van repetitieve frequentie; het ophalen van structureel identieke, in het cache opgeslagen plannen verspillen tokens en veroorzaken "mode collapse" (repetitief redeneren).

2. Methodologie: De CacheRAG Architectuur

CacheRAG stelt een stateful, cache-verrijkte architectuur voor die LLM-planners transformeert in "continual learners". Het introduceert een pijplijn met vier componenten die is ontworpen om schema-trouw te waarborgen, ophaaldekking te maximaliseren en context-diversiteit te optimaliseren.

A. Schema-Agnostische Gebruikersinterface (Twee-staps Compilatie)

Om schema hallucinaties te voorkomen, ontkoppelt het systeem het begrijpen van natuurlijke taal van de fysieke query-uitvoering:

1. Logische Laag (ISR Extractie): Een LLM fungeert als syntactische parser om een Intermediate Semantic Representation (ISR) te extraheren. Dit omvat de ruwe entiteit, semantische beperkingen en een domeinhint, zonder specifieke KG-predicaten te genereren.
2. Fysieke Laag (Backend Adapter): Een deterministische adapter haalt het lokale schema (geldige 1-hop relaties) op voor de geïdentificeerde entiteit. Vervolgens vraagt het de LLM om de logische ISR te compileren naar een uitvoerbare fysieke query (SPARQL/API) met uitsluitend gebruik van de verstrekte geldige predicaten. Dit zorgt voor een compilatiesucces van 98,9% en elimineert gehallucineerde attributen.

B. Diversiteitsbewuste Semantische Caching

In plaats van ruwe tekst op te slaan, slaat de cache succesvolle historische Query-Plan-Answer tuples op. Om het contextvenster van de LLM te optimaliseren:

• Hiërarchische Indexering: Een twee-laags index (Domein $\to$ Aspect) routeert queries naar specifieke buckets (bijv. films $\to$ prijs), wat kruisbesmetting tussen domeinen voorkomt en de zoekruimte snoeit.
• Maximale Marginale Relevantie (MMR): Binnen een bucket gebruikt het systeem MMR om in het cache opgeslagen voorbeelden te selecteren. Dit balanceert semantische relevantie voor de huidige query met structurele diversiteit ten opzichte van reeds geselecteerde voorbeelden. Dit zorgt ervoor dat de LLM een diverse set redeneerpatronen ontvangt (bijv. verschillende multi-hop paden) in plaats van redundante kopieën, waardoor de informatiewinst wordt gemaximaliseerd.

C. Gebounde Heuristische Expansie

Wanneer het initiële queryplan onvoldoende resultaten oplevert, activeert het systeem dynamische expansie-operatoren met strikte complexiteitsgaranties om oneindige lussen of OOM-fouten te voorkomen:

• Gebounde Diepte Expansie ($\sigma_{depth}$): Een Index Nested Loop Join die relaties koppelt (bijv. Entiteit $\to$ Regisseur $\to$ Andere Films) tot een vaste dieptelimiet ($K_{depth} \le 3$).
• Gebounde Breedte Expansie ($\sigma_{breadth}$): Een Star-Pattern Scan die Top-$K$ buren van knelpunt-entiteiten ophaalt om alternatieve schema-takken te verkennen (bijv. het controleren van zowel genre als stijl predicaten).
• Heuristische Dispatcher: Een lichtgewicht beoordelaar evalueert de volledigheid van het opgehaalde subgraf en beslist of moet worden beëindigd of expansie moet worden geactiveerd.

D. Offline Auto-Generatie (Mitigatie van Cold-Start)

Om het "cold-start" probleem aan te pakken (lege cache bij initialisatie), gebruikt het systeem een offline module om KG-subgrafieken te bemonsteren en diverse vragen in natuurlijke taal en hun corresponderende plannen te synthetiseren. Dit vult de cache met fundamentele heuristieken voordat het systeem live gaat.

3. Belangrijkste Bijdragen

1. Nieuw Systeemparadigma: Eerste systematische toepassing van semantische caching om continual learning mogelijk te maken in LLM-gebaseerde KGQA, met een verschuiving van stateless naar stateful planning.
2. Schema-Agnostische Interface: Een twee-staps raamwerk (ISR + Backend Adapter) dat niet-expert gebruikers toelaat om in natuurlijke taal te queryen, terwijl schema-trouw wordt gegarandeerd (98,9% compilatiesucces).
3. Diversiteit-geoptimaliseerde Cache: Introductie van een hiërarchische index gekoppeld aan MMR om structurele diversiteit in opgehaalde voorbeelden te maximaliseren, waardoor redeneerhomogeniteit wordt voorkomen.
4. Wiskundig Gebounde Operatoren: Formalisering van diepte- en breedte-expansies met strikte complexiteitsgaranties ($O(K_{depth} \cdot K_{degree})$, waardoor productie-ready stabiliteit wordt gewaarborgd zonder in te leveren op recall.
5. Uitgebreide Validatie: Uitgebreide experimenten die significante verbeteringen tonen ten opzichte van state-of-the-art (SOTA) baselines.

4. Experimentele Resultaten

De auteurs evalueerden CacheRAG op meerdere benchmarks, waaronder CRAG (complex, multi-domein), QALD-10-en, WebQSP en CWQ.

• Prestaties op CRAG:
  • Nauwkeurigheid: Verbetering met +13,2% ten opzichte van de beste SOTA-baseline (bereikend 82,4%).
  • Waarheidsgetrouwheid: Verbetering met +17,5% (bereikend 71,1%), wat hallucinaties aanzienlijk reduceert.
  • Miss Rate: Dramatisch gereduceerd tot 6,4% (vergeleken met >38% voor sommige baselines), wat superieure ophaaldekking aantoont.
• Generaliseerbaarheid: Op SPARQL-gebaseerde datasets (QALD-10, WebQSP, CWQ) presteerde CacheRAG beter dan fijngetune SOTA-modellen en andere LLM-gebaseerde benaderingen (zoals ToG-2) zonder dat fijnafstemming vereist was.
• Ablatiestudies:
  • Het verwijderen van Diepte/Breedte expansie veroorzaakte een daling in waarheidsgetrouwheid van ongeveer 20%, wat de noodzaak van dynamische padverkenning bewijst.
  • Het verwijderen van de Semantische Cache veroorzaakte een daling in waarheidsgetrouwheid van ongeveer 5,5%, wat de waarde van continual learning valideert.
  • De MMR en Twee-laags Index waren cruciaal voor het handhaven van hoge prestaties.
• Efficiëntie & Schaalbaarheid: Hoewel de inferentietijd iets hoger is dan sommige baselines (door expansiestappen), blijft het binnen dezelfde orde van grootte (~9,4s vs ~6s). Het systeem schaalt logaritmisch met de grafgrootte ($O(\log n)$), wat bevestigt dat het geen bottleneck wordt op grote grafen.

5. Betekenis

CacheRAG vertegenwoordigt een paradigmaverschuiving in hoe LLM's interageren met gestructureerde data. Door de LLM niet alleen te behandelen als een generator maar als een continual learner die wordt geleid door een gestructureerde, diversiteitsbewuste cache, lost het systeem de "stateless" inefficiëntie op die huidige RAG-systemen teistert.

De betekenis hiervan ligt in:

• Het Overbruggen van de Kloof: Succesvolle aanpassing van databaseconcepten (plan-caching, gebounde uitvoering) aan de probabilistische aard van LLM's.
• Betrouwbaarheid: Het bieden van een raamwerk dat robuust is tegen schema hallucinaties en combinatorische explosie, waardoor LLM-gebaseerde KGQA levensvatbaar wordt voor real-world, productie-gegradeerde toepassingen.
• Toegankelijkheid: Het toelaten van niet-expert gebruikers om complexe Knowledge Graphs te queryen met natuurlijke taal zonder dat ze SPARQL of specifieke schema-predicaten hoeven te begrijpen.