This work proposes KGCache, an in-memory cache for one-hop knowledge graph neighborhoods, which is designed to be compatible with both iterative traversal (ToG) and one shot planning (RoG) KGQA paradigms and shows substantial entity reuse among starting entities and entities reached during traversal.
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.
This work proposes MARS, a scalable knowledge graph question answering (KGQA) approach that requires no model fine-tuning, and performs a structured retrieval procedure that links question entities to the KG and iteratively retrieves relevant next-hop information.
Nikit Srivastava, Daniel Vollmers, René Speck et al.· arXiv.org· 0 citations
Integrating Knowledge Graphs (KGs) into Retrieval-Augmented Generation (RAG) can substantially improve LLM performance on complex question answering (QA) by reducing hallucinations and supplying structured context. However, building high-quality KGs over large corpora for edge scenarios is challenging: cloud-based processing introduces latency and dependency on remote services, while exhaustive on-device construction with LLMs is often computationally infeasible under limited hardware budgets. We observe that traditional non-LLM methods can efficiently capture explicit knowledge, and that real-world queries typically touch only a small, highly concentrated portion of the graph. As a result, static and exhaustive KG construction is redundant and inefficient. We propose Edge-AdaptiveKG, a resource-aware framework that combines an offline Seed KG (S-KG) with an online Query-driven KG (Q-KG). Lightweight non-LLM methods build the S-KG, while the LLM is invoked on demand during question answering to incrementally expand the Q-KG only when complex relations are needed. Experiments show that Edge-AdaptiveKG reduces computational overhead and inference latency, enabling KG-enhanced RAG on resource-constrained devices while maintaining competitive QA accuracy.
Yuyu Du, Juxin Niu, Chun Jason Xue et al.· IEEE International Conferenc...· 0 citations
Knowledge Graph Question Answering (KGQA) over RDF graphs remains challenging in domain-specific settings, where formal ontologies and curated text-SPARQL pairs are often unavailable. We present KGVoyager, a KG-agnostic agentic architecture that generates SPARQL queries from natural language questions by dynamically discovering graph structure and semantics, requiring only a query endpoint of the underlying graph. Using a think-act-observe loop with search, exploration, and execution tools, KGVoyager maps terms to graph IRIs, uncovers structure, and refines queries through execution feedback - all without pre-existing ontologies or examples. Unlike the prior state of the art, KGVoyager requires only a lightweight class index which renders it applicable for far more real-world endpoints. Across four benchmarks, KGVoyager improves F1 by ~8 points while cutting cost and runtime by ~22% each.
We present EXYGEN (EXplore Your Graphs ENgine), a framework for knowledge graph (KG) understanding that enables conversational access to KGs at scale. We address two questions in sequence. First, how effectively can LLMs perform text-to-SPARQL generation given only automatically derived structured metadata and small graph samples, rather than task-specific fine-tuning? We integrate VoID descriptions and ShEx schemas into a retrieval-augmented generation (RAG) pipeline and ablate KG-derived context on the SciQA benchmark. Our best configuration -- combining ShEx schemas, retrieved triples, and example question-query pairs -- reaches an exact match of 0.419 on execution results without any LLM fine-tuning. We further find that lexical metrics such as F1 poorly predict query correctness, and that larger general-purpose LLMs can outperform smaller code-specialized ones once given sufficient context. Second, we ask how to generate the structured metadata that this method relies on from very large KGs, where KG metadata generation becomes computationally intractable. We introduce a predicate-coverage-aware parallel graph sampling strategy that preserves structural diversity while remaining computationally tractable. On OpenCitations Meta and GESIS, it retains high predicate coverage with minimal triple loss and reduces runtime by over 80x; on ORKG, sampling is not just faster but the only tractable path to obtain complete metadata. Together, these results show that structured schema context and lightweight prompting can substantially reduce reliance on fine-tuning for scalable conversational access to KGs, though closing the remaining gap to fully fine-tuned approaches will likely require reducing dependence on curated question-query exemplars -- whether through synthetic generation or an execution-feedback-driven approach -- and validating these findings beyond a single benchmark.
Harshdeep Singh, Yu-Rui Zhu, Giovanni Colavizza et al.· 0 citations
Retrieval-Augmented Generation over Knowledge Graphs (GraphRAG) enhances Large Language Models (LLMs) with structured, multi-hop evidence. However, existing GraphRAG systems predominantly linearize retrieved subgraphs into long textual prompts, forcing LLMs to recompute identical schema-level reasoning across queries repeatedly. This text-centric design incurs substantial prefilling latency, memory overhead, and severely limited cache reuse under entity-level variations. We observe that although retrieved entities differ across queries, their underlying logical schemas (meta-structures) recur with high frequency, indicating that most computational cost is spent on repeatedly encoding invariant structural logic. In this paper, we propose MetaKV, the first structure-aware KV caching mechanism that explicitly decouples static structural logic from dynamic entity semantics in GraphRAG inference. In a preparation phase, MetaKV mines frequent meta-structures and pre-computes their Key-Value (KV) caches as reusable Skeleton KVs. During inference, query-specific entity representations are injected into reserved structural slots to assemble the context without recomputing graph topology. To further enforce faithfulness to graph reasoning, MetaKV introduces a Topological Mask that constrains attention to valid graph edges. Extensive experiments conducted on HotpotQA and MetaQA datasets demonstrate that MetaKV achieves up to 6.4× prefilling speedup and a 73% effective cache-hit rate while maintaining competitive reasoning accuracy, enabling high-throughput, low-latency GraphRAG without sacrificing adherence to graph topology.
Ruikun Luo, C. Gu, Jing Yang et al.· Proceedings of the 32nd ACM...· 0 citations
PYTHIA is presented, a training-free, plug-and-play solution for KGQA over any RDF KG which consists of an LLM agent guided by a relation-centric conceptual model of the KGQA task which is acted upon through a suite of tools for entity linking, graph exploration and query execution.
Sergios-Anestis Kefalidis, Konstantinos Plas, Manolis Koubarakis· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
