KGCache: Amortized Subgraph Retrieval for KG Reasoning with LLMs
Uros Stanic, Changcheng Yuan, Sabuj Laskar, Ariful Azad
cs.AI
Submitted: 2026-08-08
Updated: 2026-08-11
Comments: 11 pages, 5 figures
Code: https://github.com/oxigraph/oxigraph
License: http://creativecommons.org/licenses/by/4.0/
The gist: Large language models can answer knowledge-intensive questions more reliably when they are grounded with knowledge graphs, but systems such as Think-on-Graph and Reasoning-on-Graph repeatedly query
Terminology
Abstract
Large language models can answer knowledge-intensive questions more reliably when they are grounded with knowledge graphs, but systems such as Think-on-Graph and Reasoning-on-Graph repeatedly query the same graph neighborhoods across different questions. In this work, we study this repeated retrieval in Knowledge Graph Question Answering (KGQA) workloads and propose KGCache, an in-memory cache for one-hop knowledge graph neighborhoods. KGCache is designed to be compatible with both iterative traversal (ToG) and one shot planning (RoG) KGQA paradigms. KGCache is placed between the KGQA engine and the backend serving the KG, so repeated entity requests can be served from cache instead of issuing new KG queries. We evaluate KGCache on WebQSP and CWQ using LRU, LFU, and a trace-aware Oracle policy. Our analysis shows that both datasets contain substantial entity reuse among starting entities and entities reached during traversal. We also explore semantic caching for similar queries, which shows additional hit-rate gains on WebQSP and needs further accuracy testing on CWQ. Entity caching accelerates KG retrieval by up to 1.91 times, while semantic-context caching achieves up to 1.06 times full-system speedup in the evaluated WebQSP configurations, with each hit being up to 3.73 times faster.
Sources
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
- Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation
- Think-on-Graph 3.0: Efficient and Adaptive LLM Reasoning on Heterogeneous Graphs via Multi-Agent Dual-Evolving Context Retrieval
- Query-Aware Graph Neural Networks for Enhanced Retrieval-Augmented Generation
- Non-Determinism of "Deterministic" LLM Settings
- Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs
- ReasoningLM: Enabling Structural Subgraph Reasoning in Pre-trained Language Models for Question Answering over Knowledge Graph
- Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation
Related papers
- MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
- Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
- Agents' Last Exam
- The Clinician's Veto: Navigating Trust, Liability, and Uncertainty in Autonomous AI Prescribing
- MindHelper: Closed-Loop Embodied Mental-State Reasoning for Precision Intervention
- Incumbent Advantage: Brand Bias and Cognitive Manipulation Dynamics in LLM Recommendation Systems