PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yushi Sun, Lei Chen

arXiv:2604.26176v4cs.DBcs.CL

TL;DR

LLM-driven KGQA planners generate plans without using historical query patterns, despite the need for schema-aligned retrieval. CacheRAG combines schema-grounded parsing, diverse semantic-plan caching, and bounded graph expansion. It outperforms state-of-the-art baselines, including on CRAG, while the paper notes a modest increase in answer-content hallucination metrics.

  • Problem

    LLM-driven KGQA planners generate retrieval plans from the current question alone, and plans must remain aligned with KG schemas to avoid hallucinations and incomplete retrieval.

    Source: §1 · p. 1

  • Method

    CacheRAG combines ISR-based schema-grounded parsing, diversity-aware hierarchical semantic-plan caching, and bounded depth/breadth graph expansion.

    Source: §1 · pp. 2–3

  • Results

    CacheRAG outperforms state-of-the-art baselines on CRAG by 13.2% in accuracy and 17.5% in truthfulness.

    Source: §6 · p. 12

  • Takeaways & Limitations

    CacheRAG provides a history-aware KGQA architecture that combines reusable plans with bounded traversal across schema-constrained retrieval.

    Source: §1 · p. 3, §6 · p. 12

    CacheRAG shows a modest increase in answer-content hallucination metrics, attributed to the more complex synthesis task from broader retrieved context.

    Source: §5.5 · p. 10

Abstract

from arXiv · show

The integration of Large Language Models (LLMs) with Retrieval-Augmented Generation (RAG) has significantly advanced Knowledge Graph Question Answering (KGQA). However, existing LLM-driven KGQA systems act as stateless planners, generating retrieval plans in isolation without exploiting historical query patterns: analogous to a database system that optimizes every query from scratch without a plan cache. This fundamental design flaw leads to schema hallucinations and limited retrieval coverage. We propose CacheRAG, a systematic cache-augmented architecture for LLM-based KGQA that transforms stateless planners into continual learners. Unlike traditional database plan caching (which optimizes for frequency), CacheRAG introduces three novel design principles tailored for LLM contexts: (1) Schema-agnostic user interface: A two-stage semantic parsing framework via Intermediate Semantic Representation (ISR) enables non-expert users to interact purely in natural language, while a Backend Adapter grounds the LLM with local schema context to compile executable physical queries safely. (2) Diversity-optimized cache retrieval: A two-layer hierarchical index (Domain $\rightarrow$ Aspect) coupled with Maximal Marginal Relevance (MMR) maximizes structural variety in cached examples, effectively mitigating reasoning homogeneity. (3) Bounded heuristic expansion: Deterministic depth and breadth subgraph operators with strict complexity guarantees significantly enhance retrieval recall without risking unbounded API execution. Extensive experiments on multiple benchmarks demonstrate that CacheRAG significantly outperforms state-of-the-art baselines (e.g., +13.2% accuracy and +17.5% truthfulness on the CRAG dataset).

1 Introduction

LLM-driven KGQA planners often work statelessly, risking schema hallucinations and incomplete retrieval. CacheRAG combines schema-grounded parsing, historical-plan reuse, and bounded expansion to address these problems.

1 Introduction

  • Stateless LLM planners ignore historical query patterns, while KGQA also requires schema-aligned plans to prevent hallucinations.Such systems can retrieve the wrong entity or omit multi-hop paths and alternative schema branches.Source: §1 · p. 1
  • CacheRAG’s cache reuses historical retrieval plans to guide multi-hop reasoning, and bounded expansion explores alternative schema paths when initial retrieval is insufficient.The system is designed to preserve execution bounds while addressing retrieval gaps.Source: §1 · pp. 2–3
  • A two-stage parser converts natural-language intent into an Intermediate Semantic Representation, then grounds it in local schema for physical-query compilation.This decouples user-facing language from KG-specific predicates and SPARQL.Source: §1 · pp. 2–3
  • A hierarchical Domain-to-Aspect cache with MMR retrieves structurally diverse plans, while bounded depth and breadth expansion adjusts insufficient retrieval.Offline auto-generation also seeds the cache with query-plan-answer tuples for initial use.Source: §1 · p. 3
  • CacheRAG outperforms state-of-the-art baselines on CRAG by 13.2% in accuracy and 17.5% in truthfulness.The paper also reports new state-of-the-art results on three SPARQL-based benchmarks without fine-tuning.Source: §1 · p. 3

2 Related Work

Related work spans semantic parsing, LLM-driven KG retrieval, and caching or agentic workflows. CacheRAG positions its contribution as history-aware KG traversal with schema constraints and bounded expansion.

2.1 Semantic Parsing and Natural Language Interfaces

  • Semantic-parsing KGQA maps natural language to logical forms, but strict schema dependence and parsing errors limit tolerance for ambiguity in complex questions.The approaches described include multi-step search and seq2seq generation.Source: §2.1 · p. 3

2.2 KG-based RAG and LLM-driven Execution

  • LLM-driven KGQA includes tool-calling and iterative graph exploration, while CacheRAG emphasizes history-based planning and bounded depth/breadth expansion.The related work also describes approaches combining KG and text reasoning.Source: §2.2 · pp. 3–4

2.3 Semantic Caching and Agentic Workflows

  • Infrastructure caches retain KV states or retrieved text, whereas CacheRAG stores semantic plans to guide multi-hop planning.The paper distinguishes KGQA-specific experience replay from general thought-template buffers and workflows.Source: §2.3 · p. 4
  • CacheRAG combines unsupervised template generation, a two-layer MMR retrieval index, and bounded graph expansion for schema-constrained KGQA.Its positioning describes these as system-level contributions built from existing primitives.Source: §2.3 · p. 4

3 Problem Formalization

CacheRAG formalizes KGQA as a pipeline that extracts a schema-agnostic representation, retrieves historical plans, executes and adjusts queries, then returns answers and updates its cache. Its objectives include accuracy, efficiency, diversity, schema fidelity, and bounded execution.

3.1 Core Definitions

  • A knowledge graph is defined as K = (E, R, T), with entities, predicate-linked triples, and optional temporal annotations.Predicates come from schema S; temporal annotations apply to time-sensitive graphs.Source: §3.1 · p. 4
  • The ISR represents a question with its raw topic entity, semantic constraints, and domain hint.The constraints are extracted from the natural-language question.Source: §3.1 · p. 4
  • A query plan is a sequence of retrieval operations whose execution on the graph yields a subgraph.Source: §3.1 · p. 4
  • The semantic cache stores successful retrieval histories, indexed by domain and aspect attribute.Source: §3.1 · p. 4

3.2 Problem Statement

  • CacheRAG’s objective is to extract an ISR, retrieve diverse historical plans, generate an executable plan, expand insufficient retrieval, return an answer, and update the cache.The system also targets accuracy, query efficiency, and diversity while requiring schema-valid predicates and bounded depth and breadth.Source: §3.2 · pp. 4–5
  • Figure 2 illustrates the running example’s progression from direct prompting to cache-guided planning and bounded depth and breadth expansion.Source: Figure 2 · p. 5
  • CacheRAG addresses schema hallucination, cache redundancy, incomplete retrieval, and cold-start degradation through an end-to-end pipeline.Source: §3.2 · p. 5

4 Methodology

CacheRAG combines schema-constrained parsing, diverse hierarchical plan caching, bounded graph expansion, and offline cache pre-warming in a stateful KGQA pipeline. Its components route natural-language questions into executable queries and adjust retrieval when the initial subgraph is incomplete.

4 Methodology

  • CacheRAG’s pipeline uses an ISR to route cache retrieval and compile an initial physical plan, then expands incomplete subgraphs before answer generation.The design integrates schema-constrained parsing, diversity-optimized caching, bounded operators, and offline auto-generation.Source: §4 · pp. 5–6

4.1 Schema-Constrained Semantic Parsing via Adapter Pattern

  • The two-stage parser extracts schema-agnostic entities and constraints, then grounds them against local schema to compile executable queries; on CRAG, entity extraction accuracy is 98% and physical compilation executable rate is 98.9%.If constraint mapping fails, the system triggers breadth expansion.Source: §4.1 · pp. 6–7

4.2 Diversity-Aware Plan Caching and Retrieval Optimization

  • A domain-and-aspect index prunes cache search before MMR selects relevant, structurally diverse examples for the compiler context.The localized bucket bounds retrieval complexity to O(b log b); when it is too small, the procedure can fall back to the domain-level bucket.Source: §4.2 · p. 7

4.3 Dynamic Plan Adjustment via Bounded Subgraph Operators

  • A dispatcher evaluates subgraph completeness and invokes depth joins or breadth neighborhood scans, feeding expanded results back until completion or a hard bound.Depth is limited to K_depth ≤ 3, while top-K degree pruning bounds traversal space to O(K_depth · K_degree).Source: §4.3 · p. 8

4.4 Cache Pre-Warming via Auto-Generation

  • Offline pre-warming samples local star schemas, synthesizes questions, filters invalid pairs, compiles surviving plans, and inserts them into the cache.Generated questions include compositional queries requiring multi-triple reasoning.Source: §4.4 · p. 9
  • Random pre-warming cannot guarantee coverage of every intent; near-zero-similarity queries receive empty cache context and fall back to local-schema zero-shot execution and bounded graph exploration.Successfully discovered paths are added to the cache for online growth.Source: §4.4 · p. 9

5 Experiments

Across CRAG and three SPARQL-based datasets, CacheRAG is evaluated against established baselines, with ablations and robustness, efficiency, and scalability tests. It outperforms the reported state-of-the-art comparisons, while results also quantify component effects and operational trade-offs.

5 Experiments; 5.1 Experimental Datasets; 5.2 Metrics and Evaluation Scheme; 5.3 Baselines

  • Experiments cover CRAG, QALD-10-en, WebQSP, and CWQ against LLM, tool-calling, KDD Cup, and SPARQL baselines; CRAG uses answer correctness categories, while SPARQL datasets use Hit@1.The CRAG scheme distinguishes correct, missing, and incorrect answers.Source: §5.1 · p. 9, §5.2 · p. 9, §5.3 · p. 10

5.5 Main Results

  • 13.2% higher accuracy and 17.5% higher truthfulness than state-of-the-art on CRAG; miss rate is over 38% lower than StructGPT variants.The reported hallucination metric is 3–6.5% higher than some baselines, reflecting answer-content hallucination rather than schema hallucination.Source: Table 1 · p. 10, §5.5 · p. 10

5.6 Generalizability

  • CacheRAG outperforms state-of-the-art solutions on QALD-10-en, WebQSP, and CWQ, with reported gains of 4.6%, 1.9%, and 3.2%, respectively.The comparison includes ToG-2, which additionally uses external Wikipedia pages, and prior fine-tuning SOTAs.Source: §5.6 · p. 11, Table 2 · p. 11

5.7 Ablation Study

  • Removing depth and breadth expansion causes the largest ablation drops: truthfulness falls by 22% and 18.1%, and miss rate rises by 26.1% and 19%.Removing caching reduces accuracy and truthfulness by 4.3% and 5.5%; removing MMR, the layered index, and auto-generation lowers truthfulness by 2.9%, 2.8%, and 1.8%.Source: §5.7 · p. 11, Table 3 · p. 11

5.8 LLM Model Robustness; 5.9 Indexing Consistency and Robustness

  • Performance changes by up to 5% across tested LLM backbones, while repeated indexing yields a 1.1% inconsistent indexing rate and falls back to domain-level retrieval for empty aspect buckets.The tested backbones are Llama-3.1-70B-Instruct, GPT-4o, and Claude-3.5-Sonnet.Source: §5.8 · p. 11, §5.9 · pp. 11–12, Table 4 · p. 11

5.10 Efficiency

  • CacheRAG’s mean CRAG inference time is 9.44s versus 5.96s for Apex, a trade-off the authors describe as effectiveness for additional depth and breadth expansion.Logical parsing and KG routing, cache retrieval, compilation, graph expansion, dispatching, and summarization take 2.75s, 0.02s, 0.49s, 3.93s, 0.47s, and 1.78s, respectively.Source: §5.10 · p. 12

5.11 Time and Memory Complexity and Scalability

  • With bounded parameters treated as system constants, CacheRAG has a stated overall online complexity of O(b log b + K_depth log n + K_depth·K_degree + L·K_depth); synthetic-KG retrieval latency grows logarithmically.The synthetic graphs range from 40,000 to 1.28 million triples; Figure 5 reports results for point and star queries.Source: §5.11 · p. 12, Figure 5 · p. 12

5.12 LRU Cache Design

  • The LRU variant caps each bucket at 10 examples, saves 64% of CRAG cache space, and reduces performance by less than 2%.This variant is presented for scenarios with limited caching storage space.Source: §5.12 · p. 12, Table 5 · p. 12

6 Conclusion

CacheRAG combines a schema-constrained semantic parser, diversity-aware hierarchical cache, and bounded graph operators to make LLM planners history-aware for KGQA. On CRAG, it reports 13.2% higher accuracy and 17.5% higher truthfulness, and reports generalization to SPARQL-based KGs and logarithmic scaling.

6 Conclusion

  • 13.2% higher accuracy and 17.5% higher truthfulness on CRAG are reported for CacheRAG against state-of-the-art baselines.The conclusion also reports robust generalization to SPARQL-based KGs and logarithmic scaling.Source: §6 · p. 12
  • CacheRAG integrates a schema-constrained semantic parser, diversity-aware hierarchical cache, and deterministically bounded graph operators.The conclusion presents these components as a systematic architecture for transforming stateless LLM planners into continual learners for KGQA.Source: §6 · p. 12
  • The paper presents CacheRAG as a foundation for history-aware, verifiable continual learning in future LLM-augmented database systems.It states that the architecture addresses schema hallucination and combinatorial explosion.Source: §6 · p. 12

A.1 Dataset Details

The evaluation uses CRAG questions spanning five knowledge graphs and domains, with head, torso, and tail splits; it also includes three SPARQL-based datasets.

A.1 Dataset Details

  • CRAG evaluation covers questions from five knowledge graphs across five domains, accessed through API functions.The paper uses the KG questions in CRAG for experiments.Source: §A.1 · p. 14
  • CRAG questions are split into head, torso, and tail groups containing 187, 203, and 188 questions, respectively.The dataset also categorizes questions by domain, question type, and timeliness.Source: §A.1 · p. 14
  • Additional evaluation datasets are QALD-10-en, WebQSP, and CWQ [27], all SPARQL-based.These datasets are included alongside CRAG to evaluate CacheRAG.Source: §A.1 · p. 14

A.2 Metric and Evaluation Scheme Details

The appendix identifies Table 7 as reporting the auto-evaluation accuracy of the Llama-3.1 70B Instruct Model.

A.2 Metric and Evaluation Scheme Details

  • The evaluation scheme includes an auto-evaluation critic whose reliability is discussed in the appendix.The cited discussion directs readers to Table 7.Source: §A.2 · p. 14
  • Table 7 reports auto-evaluation accuracy for the Llama-3.1 70B Instruct Model.The text points readers to the table for details on the reliability of the auto-evaluation critic.Source: Table 7 · p. 14, §A.2 · p. 14
  • The supplied table caption identifies the reported measure as accuracy rather than another evaluation metric.No accuracy values are stated in the supplied passages.Source: Table 7 · p. 14

A.3 Baseline Details

The paper compares CacheRAG with baselines grouped into four categories: LLM base models, LLM tool-calling models, KDD Cup-winning solutions, and SPARQL-based state-of-the-art solutions.

A.3 Baseline Details

  • The baselines span LLM base models, LLM tool-calling models, KDD Cup-winning solutions, and SPARQL-based state-of-the-art solutions.The paper states that it compares CacheRAG against these four baseline categories.Source: §A.3 · p. 14
  • Two baseline categories are LLM base models and LLM tool-calling models.These are listed among the comparison groups.Source: §A.3 · p. 14
  • The comparison also includes KDD Cup-winning and SPARQL-based state-of-the-art solutions.These are listed as the other baseline categories.Source: §A.3 · p. 14

A.3.1 LLM Base Models.

The CRAG evaluation uses three LLM base models, spanning open-source and closed-source systems.

A.3.1 LLM Base Models.

  • The CRAG baselines include GPT-4o, Llama-3.1-70B-Instruct, and Deepseek-chat-V3-0324.The passage describes these as base models for the CRAG dataset.Source: §A.3.1 · p. 14
  • The selected models cover both state-of-the-art open-sourced and close-sourced LLMs.Source: §A.3.1 · p. 14
  • These models serve as baselines on CRAG.Source: §A.3.1 · p. 14

A.3.2 LLM Tool Calling Models.

The CRAG tool-calling baselines let three LLMs plan API use from function metadata and retrieve KG content.

A.3.2 LLM Tool Calling Models.

  • StructGPT [14] is evaluated on CRAG with GPT-4o, Llama-3.1-70B-Instruct, and Deepseek-chat-V3-0324 as base models.Source: §A.3.2 · p. 14
  • The models receive API function names, parameters, descriptions, and sample use cases as metadata.Source: §A.3.2 · p. 14
  • The LLMs can freely chain and call API functions to retrieve relevant KG content using their own planning and reasoning.Source: §A.3.2 · p. 14

A.3.3 KDD Cup Winning Solutions.

The appendix describes CRAG and SPARQL benchmark baselines, parameter sensitivity, scalability, performance across question-popularity splits, and multi-KG routing. Reported findings include stable head-to-tail performance, bounded online complexity, and an 8% routing advantage for the dynamic-description design.

A.3.3 KDD Cup Winning Solutions.

  • The KDD Cup 2024 winning-solution baselines are db3 and apex, adapted to KGQA by supplying “<EMPTY>” as web content and using Deepseek-chat-V3-0324.db3 jointly considers KG and web content; apex uses a router-based adaptive RAG pipeline for KG retrieval and answer generation.Source: §A.3.3 · p. 14

A.3.4 SPARQL-based State-of-the-art Solutions.

  • The SPARQL-based comparisons include ToG [26], ToG-2 [22], sparql-qa, Decaf [37], and CBR [6]; these methods use distinct KG reasoning, parsing, and case-reuse approaches.ToG-2 also uses external Wikipedia pages; the API-based CRAG dataset does not support SPARQL querying, so these methods run only on SPARQL-based datasets.Source: §A.3.4 · p. 15

A.4 Parameter Sensitivity

  • CacheRAG is relatively stable for λ values from 0.25 to 1, with up to 0.7% accuracy change and 1.5% truthfulness change; accuracy peaks at λ=0.5 and hallucination rate is lowest at λ=0.75.The authors consider λ=0.5 an intuitive choice balancing diversity and relevance of learning samples.Source: §A.4 · p. 15, Figure 6 · p. 15

A.5 Scalability Details

  • With bounded system parameters, CacheRAG’s online time complexity is O(log n + L) and its space complexity is O(N + K_depth·K_degree).The bounds include K_depth≤3 and K_degree≤30; cache retrieval uses O(1) hierarchical lookup and O(b log b) MMR ranking, while depth and breadth expansion have bounded work and memory.Source: §A.5 · pp. 15–16

A.6 Head Torso Tail Analysis

  • CacheRAG’s accuracy decreases by 4.2% and truthfulness by 3.6% from head to tail, versus base-model decreases of up to 14%, 17%, and 17%, respectively.The three base-model decreases correspond to GPT-4o, Llama-3.1-70B-Instruct, and Deepseek-chat-V3-0324; CacheRAG is described as relatively stable across head, torso, and tail.Source: Table 8 · p. 16, §A.6 · p. 16

A.7 Multi-KG Routing

  • 8%: the dynamic KG-description cache design outperforms the other multi-KG domain-routing designs.The design uses dynamic KG descriptions with Chain-of-Thought reasoning and updates descriptions following incorrect domain identification.Source: §A.7 · p. 16
Loading 2604.26176v4…