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

1. Problem Statement

The paper addresses critical limitations in current Large Language Model (LLM)-driven Knowledge Graph Question Answering (KGQA) systems, specifically those using Retrieval-Augmented Generation (RAG). Existing systems suffer from two fundamental flaws:

• Stateless Planning & Schema Hallucination: Current LLMs act as "stateless planners," generating retrieval plans (e.g., SPARQL queries or API calls) in isolation for every new question without leveraging historical query patterns. This leads to schema hallucinations, where the LLM invents non-existent predicates or attributes (e.g., querying a "magic" predicate that doesn't exist in the schema) because it lacks grounding in the specific local schema.
• Limited Retrieval Coverage: Zero-shot planning often results in shallow, incomplete query structures. If the initial retrieval fails or returns empty results, the system frequently gives up rather than exploring alternative paths (multi-hop reasoning), leading to high "miss rates."
• Inefficiency of Traditional Caching: Naively applying traditional database plan caching (optimized for frequency, e.g., LRU/LFU) fails in LLM contexts. LLMs benefit more from diversity in their context window than repetitive frequency; retrieving structurally identical cached plans wastes tokens and induces "mode collapse" (repetitive reasoning).

2. Methodology: The CacheRAG Architecture

CacheRAG proposes a stateful, cache-augmented architecture that transforms LLM planners into "continual learners." It introduces a four-component pipeline designed to ensure schema fidelity, maximize retrieval coverage, and optimize context diversity.

A. Schema-Agnostic User Interface (Two-Stage Compilation)

To prevent schema hallucinations, the system decouples natural language understanding from physical query execution:

1. Logical Layer (ISR Extraction): An LLM acts as a syntactic parser to extract an Intermediate Semantic Representation (ISR). This includes the raw entity, semantic constraints, and a domain hint, without generating specific KG predicates.
2. Physical Layer (Backend Adapter): A deterministic adapter fetches the local schema (valid 1-hop relations) for the identified entity. It then prompts the LLM to compile the logical ISR into an executable physical query (SPARQL/API) using only the provided valid predicates. This ensures 98.9% compilation success and eliminates hallucinated attributes.

B. Diversity-Aware Semantic Caching

Instead of storing raw text, the cache stores successful historical Query-Plan-Answer tuples. To optimize the LLM's context window:

• Hierarchical Indexing: A two-layer index (Domain $\to$ Aspect) routes queries to specific buckets (e.g., movies $\to$ award), preventing cross-domain contamination and pruning the search space.
• Maximal Marginal Relevance (MMR): Within a bucket, the system uses MMR to select cached examples. This balances semantic relevance to the current query with structural diversity against already selected examples. This ensures the LLM receives a diverse set of reasoning patterns (e.g., different multi-hop paths) rather than redundant copies, maximizing information gain.

C. Bounded Heuristic Expansion

When the initial query plan yields insufficient results, the system triggers dynamic expansion operators with strict complexity guarantees to avoid infinite loops or OOM errors:

• Bounded Depth Expansion ($\sigma_{depth}$): An Index Nested Loop Join that chains relations (e.g., Entity $\to$ Director $\to$ Other Films) up to a fixed depth limit ($K_{depth} \le 3$).
• Bounded Breadth Expansion ($\sigma_{breadth}$): A Star-Pattern Scan that retrieves Top-$K$ neighbors of bottleneck entities to explore alternative schema branches (e.g., checking both genre and style predicates).
• Heuristic Dispatcher: A lightweight judge evaluates the completeness of the retrieved subgraph and decides whether to terminate or trigger expansion.

D. Offline Auto-Generation (Cold-Start Mitigation)

To address the "cold-start" problem (empty cache at initialization), the system uses an offline module to sample KG subgraphs and synthesize diverse natural language questions and their corresponding plans. This populates the cache with foundational heuristics before the system goes live.

3. Key Contributions

1. Novel System Paradigm: First systematic application of semantic caching to enable continual learning in LLM-based KGQA, moving from stateless to stateful planning.
2. Schema-Agnostic Interface: A two-stage framework (ISR + Backend Adapter) that allows non-expert users to query in natural language while guaranteeing schema fidelity (98.9% compilation success).
3. Diversity-Optimized Cache: Introduction of a hierarchical index coupled with MMR to maximize structural diversity in retrieved examples, preventing reasoning homogeneity.
4. Provably Bounded Operators: Formalization of depth and breadth expansions with strict complexity guarantees ($O(K_{depth} \cdot K_{degree})$), ensuring production-ready stability without sacrificing recall.
5. Comprehensive Validation: Extensive experiments showing significant improvements over state-of-the-art (SOTA) baselines.

4. Experimental Results

The authors evaluated CacheRAG on multiple benchmarks, including CRAG (complex, multi-domain), QALD-10-en, WebQSP, and CWQ.

• Performance on CRAG:
  • Accuracy: Improved by +13.2% over the best SOTA baseline (reaching 82.4%).
  • Truthfulness: Improved by +17.5% (reaching 71.1%), significantly reducing hallucinations.
  • Miss Rate: Reduced dramatically to 6.4% (compared to >38% for some baselines), demonstrating superior retrieval coverage.
• Generalizability: On SPARQL-based datasets (QALD-10, WebQSP, CWQ), CacheRAG outperformed fine-tuned SOTA models and other LLM-based approaches (like ToG-2) without requiring fine-tuning.
• Ablation Studies:
  • Removing Depth/Breadth expansion caused a ~20% drop in truthfulness, proving the necessity of dynamic path exploration.
  • Removing the Semantic Cache caused a ~5.5% drop in truthfulness, validating the value of continual learning.
  • The MMR and Two-Layer Index were critical for maintaining high performance.
• Efficiency & Scalability: While inference time is slightly higher than some baselines (due to expansion steps), it remains in the same order of magnitude (~9.4s vs ~6s). The system scales logarithmically with graph size ($O(\log n)$), confirming it does not become a bottleneck on large graphs.

5. Significance

CacheRAG represents a paradigm shift in how LLMs interact with structured data. By treating the LLM not just as a generator but as a continual learner guided by a structured, diversity-aware cache, the system solves the "stateless" inefficiency that plagues current RAG systems.

Its significance lies in:

• Bridging the Gap: Successfully adapting database concepts (plan caching, bounded execution) to the probabilistic nature of LLMs.
• Reliability: Providing a framework that is robust against schema hallucinations and combinatorial explosion, making LLM-based KGQA viable for real-world, production-grade applications.
• Accessibility: Allowing non-expert users to query complex Knowledge Graphs using natural language without needing to understand SPARQL or specific schema predicates.