Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· pp. 3492-3503· 0 citations· 22 references
TL;DR
MetaKV is proposed, the first structure-aware KV caching mechanism that explicitly decouples static structural logic from dynamic entity semantics in GraphRAG inference, enabling high-throughput, low-latency GraphRAG without sacrificing adherence to graph topology.
Abstract
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.
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.
Uros Stanic, Chang-He Yuan, Sabuj Laskar et al.· 0 citations
Existing retrieval-augmented generation (RAG) systems treat web pages as flat text, losing the structural and semantic signals encoded in HTML. We present PolyUQuest, a verifiable, structure-aware web RAG framework built on a heterogeneous graph that unifies hyperlink topology between pages, DOM hierarchy within pages, and entity-relation knowledge across pages. A two-tier router dispatches each query to one of three retrieval modes matched to its structural need, including direct block retrieval, cross-page graph traversal, and multi-hop entity reasoning. Each answer carries traceable provenance: every cited block records its source page, heading path, and entity links, so users can inspect the structural evidence behind a claim. We evaluate on the official websites of the Hong Kong Polytechnic University (PolyU), comprising 4,240 pages, 31,086 DOM blocks, 29,119 entities, and 37,680 relations, together with a multi-type evaluation benchmark. PolyUQuest improves correctness, coverage, and faithfulness over the evaluated baselines while maintaining query-time token consumption comparable to ChunkRAG and substantially below the graph-based RAG baselines. The demonstration provides an interactive interface for inspecting cited answers, comparing retrieval traces across routing modes, and exploring evidence graph paths. PolyUQuest is being prepared for deployment as a student-facing QA service at PolyU.
Ying Liu, Yingzi Ye, Quan Feng et al.· 0 citations
Agentic language models repeatedly encode tool and skill schemas that recur across requests in different combinations and orders, preventing standard prefix caching from reusing their key--value (KV) states. We introduce \textbf{ReCache}, a framework for independently caching resource representations while reducing their inference-time computational and memory overhead. Resource-wise attention removes cross-resource interactions and assigns resource-local positions, producing composition-invariant KV blocks. ReCache then restricts resource visibility to contribution-selected layer--KV-head-group routes and retains only invocation-critical fields through structural and semantic pruning. We evaluate ReCache on a benchmark assembled from seven public tool- and skill-use datasets, including resource-disjoint tests. Resource-wise attention matches dense invocation performance (82.3\% versus 82.4\% Inv-F1) while providing a 3.655$\times$ time-to-first-token speedup. The complete framework reduces allocated KV-tensor memory by 92.43\% and accelerates attention by 1.423$\times$. These results show that separating reusable schema encoding from selective resource access substantially reduces agentic inference costs with limited effectiveness loss. The code is available at https://github.com/EIT-NLP/ReCache.
Yichu Fang, Sitong Wei, Haozhe Hu et al.· 1 citation
Retrieval-Augmented Generation (RAG) grounds large language models in external knowledge and has become a key technique for knowledge-intensive tasks. As knowledge bases continue to scale, however, the retrieval stage increasingly dominates end-to-end latency, limiting the responsiveness of RAG systems. In this paper, we identify and empirically validate a previously underexplored property of RAG workloads: strong per-user query locality, where individual users' queries concentrate on a small subset of the knowledge space. Motivated by this observation, we propose Lever, a locality-aware collaborative retrieval framework that exploits query locality to accelerate graph-based RAG retrieval. Lever maintains compact, personalized subgraph indexes on user's local devices as auxiliary structures to guide retrieval toward semantically relevant regions of a global index, enabling more efficient graph traversal without sacrificing coverage. To sustain effectiveness over time, Lever further incorporates adaptive resampling mechanisms that align on-device indexes with evolving query patterns. Extensive experiments on multiple RAG benchmarks demonstrate that Lever significantly reduces retrieval latency and improves throughput while preserving retrieval quality, highlighting query locality as a powerful and complementary lever for scalable RAG retrieval.
Yongheng Deng, Tianyuan Jiang, Zhenya Ma et al.· Proceedings of the 32nd ACM...· 0 citations
OptGraph is the first optimization agentic workflow that introduces graph retrieval-augmented generation (GraphRAG) and first constructs reusable experience as a typed graph, capturing the relationships among modeling patterns, problem formalization, implementation details, and error corrections.
Xianchao Xiu, Jianhao Li, Huangyue Chen et al.· 1 citation
Knowledge graph question answering (KGQA) with large language models (LLMs) relies on retrieving a compact set of supporting triples under strict context budgets. However, structure-free or single-stage retrieval can return triples that are semantically relevant in isolation yet insufficiently coordinated as a compact evidence set, which hurts downstream multi-hop reasoning in the low-budget regime. We study this low-budget evidence selection problem under a fixed candidate-subgraph protocol, where the candidate graph is treated as a shared retrieval space for controlled comparison. Our focus is fine-stage triple reranking within this shared candidate space, rather than candidate-subgraph construction. We propose SPIMP-RAG, a coarse-to-fine triple retrieval approach whose key component is Structure-Prior Injected Message Passing (SPIMP), a fine-stage reranker that injects Directional Distance Encoding (DDE) into relation-aware message passing. Starting from a question-centered candidate subgraph, a lightweight DDE+MLP coarse retriever first constructs a compact high-recall candidate set, which is then refined by SPIMP through DDE-guided message routing and adaptive semantic-structural fusion. We further introduce a confidence-weighted weak-supervision scheme to train the coarse scorer and SPIMP reranker from question–answer pairs without requiring gold reasoning paths. Extensive experiments on WebQSP and ComplexWebQuestions show that SPIMP-RAG consistently improves low-budget evidence quality and downstream KGQA performance. In particular, SPIMP-RAG reaches 88.13 Hit@1 / 72.93 F1 on WebQSP and 59.43 Hit@1 / 51.82 F1 on CWQ, and delivers consistent gains under the same candidate-graph protocol. These results support the effectiveness of structure-aware fine reranking for compact evidence selection in LLM-based KGQA.
Jun Chen, Zhijun Xie, Rui Wang et al.· Journal of King Saud Univers...· 0 citations