KGCache: Amortized Subgraph Retrieval for KG Reasoning with LLMs

# KGCache: Amortized Subgraph Retrieval for KG Reasoning with LLMs
Source: [https://arxiv.org/html/2608.07954](https://arxiv.org/html/2608.07954)
Ariful Azad Texas A&M University College Station, TX, USA stanic@tamu\.edu,ericycc@tamu\.edu,sabuj\.laskar@tamu\.edu,ariful@tamu\.edu

###### 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 to1\.91×1\.91\\times, while semantic\-context caching achieves up to1\.06×1\.06\\timesfull\-system speedup in the evaluated WebQSP configurations, with each hit being up to3\.73×3\.73\\timesfaster\.

## 1Introduction

Large language models \(LLMs\) have remarkable capabilities across a broad range of natural language understanding and generation tasks, yet they remain fundamentally constrained by their reliance on static parametric knowledge acquired during pretraining\[KGclaim2\]\. This limitation manifests most acutely in knowledge\-intensive question answering, where models are prone to hallucination, generating fluent but factually incorrect responses, particularly when questions require up\-to\-date or multi\-hop reasoning over structured knowledge\[KGclaim\]\. Knowledge graphs \(KGs\) offer an elegant solution to this challenge\. By encoding facts as structured \(subject, relation, object\) triples over large entity sets, KGs provide a verifiable, traversable, and updatable external memory that can ground LLM reasoning in factual evidence\[KGclaim\]\.

Recent work combines LLMs with KGs through Knowledge Graph Question Answering \(KGQA\)\[TOG\_01\]\. In this setting, an LLM\-guided system retrieves KG evidence and uses it to answer a question\. Think\-on\-Graph \(ToG\)\[TOG\_01\]performs this process iteratively, leveraging the LLM at each hop to choose relations and entities that expand the search frontier\. ToG and its successors show that such KG retrieval can improve answer grounding on standard benchmarks\[TOG\_02,TOG\_03\]\. This design, however, invokes the LLM and queries the KG several times per question\. Reasoning\-on\-Graph \(RoG\) instead generates a relation\-path plan before KG execution, reducing planning\-stage LLM invocations while maintaining competitive answer quality\[rog\]\. RoG still executes structured KG queries, and different questions can revisit the same graph regions\.

A source of avoidable work in this pipeline isredundant subgraph retrieval\. KGQA benchmark workloads can repeatedly access the same entities, such as people, countries, and institutions\. For example, 75\.9% and 44\.7% of entities recur across CWQ\[CQW\]and WebQSP\[WebQSP\]benchmarks, respectively, indicating that accesses are highly concentrated among a small subset of entities\. Redundant lookups in the backend KG store incur significant overhead, as each neighborhood query involves structured query execution \(e\.g\.,SPARQL\), data transfer, and result serialization\[KGclaim\]\. Prior GraphRAG research has emphasized retrievalquality, including subgraph selection, relation selection, and evidence construction\[query\_aware\_gnn,cai2025simgrag\], but cross\-query amortization of KG access has received comparatively less attention\. The opportunity is most direct in ToG\-style workloads because they issue multiple neighborhood requests per question, although RoG path execution can also revisit entities across questions\.

We presentKGCache, anentity\-level cachinglayer for KG\-augmented LLM reasoning that amortizes repeated subgraph retrieval\. KGCache is placed between the reasoning engine and the KG backend and maps entity identifiers to one\-hop neighborhoods\. For a fixed KG snapshot, a repeated request can be served from memory without querying the backend\. This entity\-level caching accelerates KG lookups but leaves the LLM call sequence unchanged, since each traversal step still invokes the reasoning engine\. To also reduce LLM calls, we develop a complementarysemantic\-context cachethat operates one level above entity caching\. When an incoming query is sufficiently similar to a previously seen query, measured by embedding similarity, the semantic cache returns the associated KG context directly, skipping both backend invocation and the KG traversal steps\.

We evaluate several cache management policies, including Least Recently Used \(LRU\), Least Frequently Used \(LFU\), and a trace\-aware Oracle\. We integrate this caching system with multiple KG backends and LLM frontends and show that it substantially reduces both KG traversals and LLM calls across two KGQA benchmarks\. In particular, entity\-level caching reduces backend queries by up to38%38\\%, yielding a1\.9×1\.9\\timesspeedup in KG retrieval steps\.

The main contributions of this paper are as follows:

- •Workload Characterization:We quantified the entity and semantic reuse rates in KGQA workloads, motivating caching as a first\-class optimization for KG\-augmented LLM systems\.
- •KGCache Design:We developed a comprehensive KG caching framework that supports iterative ToG\[TOG\_01\]and one\-shot RoG\-style execution\[rog\]\. KGCache works seamlessly with multiple KG backends and any frontend LLM\.
- •Evaluation:We evaluated KGCache with three caching policies, two LLMS, two KG backends, and two KGQA benchmarks, and show that KGCache achieves up to1\.9×1\.9\\timesspeedup in KG retrieval steps\.

## 2Background and Motivation

### 2\.1KGQA Task and Execution Paradigms

A knowledge graph isG=\(ℰ,ℛ,𝒯\)G=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\), where𝒯⊆ℰ×ℛ×ℰ\\mathcal\{T\}\\subseteq\\mathcal\{E\}\\times\\mathcal\{R\}\\times\\mathcal\{E\}is a set of \(subject, relation, object\) triples over entity setℰ\\mathcal\{E\}and relation setℛ\\mathcal\{R\}\. Given a questionqqwith topic entitiesℰq⊂ℰ\\mathcal\{E\}\_\{q\}\\subset\\mathcal\{E\}, a KGQA system retrieves a contextCqC\_\{q\}, a verbalized subset of𝒯\\mathcal\{T\}relevant toqq, and generates an answeraq=LLM​\(q,Cq\)a\_\{q\}=\\mathrm\{LLM\}\(q,C\_\{q\}\)\. RetrievingCqC\_\{q\}requires one or more accesses to the KG backend\.

While there are several approaches for KGQA systems, we study two popular paradigms\. RoG is a planning\-retrieval\-reasoning framework\[rog\]\. The LLM first generates a relation\-path planPqP\_\{q\}grounded inℛ\\mathcal\{R\}, without accessing the KG\. The plan is then executed against the KG in a single pass to retrieveCqC\_\{q\}, and the LLM reasons overCqC\_\{q\}to produce the answer\. ToG instead retrievesCqC\_\{q\}iteratively\[TOG\_01\]\. Starting from a frontierF0⊂ℰF\_\{0\}\\subset\\mathcal\{E\}, at each hopttthe system queries the backend for the neighborhoods ofFt−1F\_\{t\-1\}, and the LLM prunes the result to a smaller frontierFtF\_\{t\}\. This repeats up to a fixed depth, andCqC\_\{q\}is formed from the triples visited along the way\. Because each pruning step is explicit, ToG offers knowledge traceability and correctability that one\-shot planning does not\.

Both paradigms access KG by requesting the one\-hop neighborhood of an entity, issued repeatedly across hops \(ToG\) or path executions \(RoG\)\. If the same entity is requested more than once, or if different questions retrieve overlapping context, this access is redundant and can potentially be served from a cache instead of the backend\. This offers two optimization opportunities:

- •Entity Reuse:How often do entity\-level KG requests repeat, within and across questions?
- •Semantic Reuse:Do semantically similar queries retrieve overlapping KG contexts?

### 2\.2Evidence for Entity\-Level Reuse

Figure[1](https://arxiv.org/html/2608.07954#S2.F1)a characterizes entity reuse at two levels: initial query entities and traversal\-level entities\. We label an occurrence as*reused*when its entity identifier appears more than once in the corresponding analyzed trace\. This aggregate metric does not distinguish within\-question from cross\-question recurrence\. All other occurrences are labeled*unique*\. The first plot considers only the initial entities extracted from each question\. In WebQSP,44\.7%44\.7\\%of initial\-entity occurrences correspond to reused entities, while in CWQ this fraction is75\.9%75\.9\\%\. The second plot extends the analysis to all entities reached during iterative ToG traversal\. For WebQSP, reused entities account for62\.0%62\.0\\%of traversal\-level entity occurrences, while for CWQ they account for67\.0%67\.0\\%\. These results show that reuse remains strong both for the initial entities explicitly mentioned in the question and for the entities explored along the reasoning path\. Such reuse creates a natural opportunity for caching, since the one\-hop neighborhoods retrieved for these entities are likely to be requested again\.

Figure[1](https://arxiv.org/html/2608.07954#S2.F1)b further examines whether entity reuse is concentrated among a small set of frequently accessed entities\. The first plot considers only the initial entities extracted from each question\. For WebQSP, the top\-10, top\-50, and top\-100 initial entities cover7\.2%7\.2\\%,20\.3%20\.3\\%, and28\.7%28\.7\\%of all starting entity occurrences, respectively\. The second plot extends this analysis to all entities reached during iterative ToG traversal\. For WebQSP, the top\-10, top\-50, and top\-100 traversal entities cover5\.4%5\.4\\%,17\.7%17\.7\\%, and28\.6%28\.6\\%of all iterative entity occurrences, respectively\. CWQ also shows similar trends\. These results show that entity access is skewed toward a relatively small set of entities rather than being uniformly distributed across the workload\.

![Refer to caption](https://arxiv.org/html/2608.07954v1/x1.png)Figure 1:Entity reuse and frequent\-entity coverage in KGQA workloads: \(a\) Unique vs\. reused entities in initial/iterative ToG traversal\. \(b\) Coverage of top\-KKmost accessed entities\.
### 2\.3Evidence for Semantic\-Level Reuse

In this section, we analyze queries judged similar by their embedding score to determine whether they can reuse KG context and how closely the reused and normally retrieved contexts overlap at the entity level\. Embedding similarity is only a retrieval signal and does not by itself establish that two questions have identical intent\. Unlike the approach of Dominic et al\.\[other\_caching\], we cache the KG context provided to the LLM rather than the LLM’s full response\. For an incoming query, the cache selects an existing element with the highest cosine similarity\. A semantic hit occurs if this score meets the thresholdτ∈\[0,1\]\\tau\\in\[0,1\]\. Semantic caching can increase hit rates by allowing similar, rather than only identical, queries to reuse cached contexts, but it adds embedding metadata and similarity\-search overhead\. Loweringτ\\tauadmits more hits but increases the risk that the reused context differs from the context produced by normal retrieval\. For each semantic hit, we compare the entity identifiers in the cached context with those in the normal context for the incoming query and average the resulting overlap score over hits\.

Figure[2](https://arxiv.org/html/2608.07954#S2.F2)a shows the average overlap for each cache size and threshold\. For WebQSP, overlap below100%100\\%first appears atτ=0\.90\\tau=0\.90among configurations with hits, whereas CWQ exhibits incomplete overlap at every evaluated threshold\. Figure[2](https://arxiv.org/html/2608.07954#S2.F2)b shows the percentage\-point gain compared to exact matches for the same cache size\. Atτ=0\.90\\tau=0\.90, WebQSP’s gain is4%4\\%on a 500\-entry cache\. However, this does not establish thatτ=0\.90\\tau=0\.90is F1\-neutral\. Because CWQ exhibits incomplete overlap at every evaluated threshold with semantic hits, it requires separate F1 validation\.

![Refer to caption](https://arxiv.org/html/2608.07954v1/x2.png)Figure 2:Effectiveness of semantic caching in KGQA workloads\. \(a\) Average entity\-set overlap for hits;0%0\\%indicates configurations with no semantic hits\. \(b\) Hit\-rate gain over exact query matching\.

## 3Methods

### 3\.1Cache Design

To minimize redundant graph traversals, we position an in\-memory cache between the KGQA engine and KG backend\. The cache stores one\-hop KG neighborhoods at entity granularity under the assumption of a static KG snapshot\. We implement the cache as a hash map keyed by entity identifieree\. Its valueN​\(e\)N\(e\)holds the complete, unpruned one\-hop neighborhood, including all incoming and outgoing\(subject,relation,object\)\(\\text\{subject\},\\text\{relation\},\\text\{object\}\)triples required for traversal\. BecauseN​\(e\)N\(e\)is cached before question\-specific LLM pruning, repeated requests foreereuse the same cached graph structure\.

Access Policy & Operations\.When the KGQA engine requestsN​\(e\)N\(e\), the cache executes the following policy:

1. 1\.Lookup & Hit: The system queries the hash map for keyee\. On a hit, it returns the one\-hop neighborsN​\(e\)N\(e\)immediately, bypassing the KG backend\.
2. 2\.Miss & Insertion: On a miss, the system fetchesN​\(e\)N\(e\)from the backend \(e\.g\., a graph database\), materializes the neighborhood object, and inserts\(e,N​\(e\)\)\(e,N\(e\)\)into the hash according to the replacement policy discussed next\.
3. 3\.Eviction: If the cache exceeds its capacity ofCCentity entries, an eviction policy selects and removes an entry based on the replacement policy\.

Complexity & Overhead\.LetCCbe the number of cached entities and\|N​\(e\)\|\|N\(e\)\|the number of triples in an entry\. Key lookup and insertion takeO​\(1\)O\(1\)average time\. Returning a cached reference takesO​\(1\)O\(1\)time, while copying or serializing a neighborhood requiresO​\(\|N​\(e\)\|\)O\(\|\{\}N\(e\)\|\{\}\)time\. A miss additionally incurs backend query latency\. Metadata and keys requireO​\(C\)O\(C\)memory, while payload storage consumesO​\(∑e∈cache\|N​\(e\)\|\)O\(\\sum\_\{e\\in\\mathrm\{cache\}\}\|\{\}N\(e\)\|\{\}\)space\. In our experiments, the capacity is bounded by the entity countCC\(counting each neighborhood as one entry\) to isolate the dynamics of reuse at the entity\-level, although the byte sizes vary with\|N​\(e\)\|\|\{\}N\(e\)\|\{\}\.

### 3\.2Cache Management Policies

The following policies determine which entry is evicted when a miss occurs and the cache is full\. Figure[3](https://arxiv.org/html/2608.07954#S3.F3)illustrates the lookup and replacement process\. We evaluate three cache\-management policies\. The first policy is*Least Recently Used*\(LRU\), which exploits temporal locality\. A standard hash table with a recency list allows a hit to move its entry to the most\-recent position and a full\-cache miss to evict the least\-recent entry inO​\(1\)O\(1\)average time\.

The second policy is*Least Frequently Used*\(LFU\), which exploits frequency locality\. LFU maintains an access counter for each cached entity, increments it on a hit, and evicts an entry with the minimum count when a miss requires space\. Here, counter updates takeO​\(1\)O\(1\)average time, while selecting a victim by a direct scan takesO​\(C\)O\(C\)time\.

Finally, we evaluate a*trace\-aware static\-frequency*reference policy, labeled*Oracle*in the results for brevity\. Given the complete request trace offline, it pre\-populates the cache with theCCmost frequently requested entities and does not update entries during evaluation\. This policy assumes global\-frequency knowledge and is therefore used for hit\-rate comparison rather than the runtime experiments\. It is not a theoretical upper bound since LRU can outperform it when reuse is concentrated in short temporal windows \(Section[5\.3](https://arxiv.org/html/2608.07954#S5.SS3)\)\.

![Refer to caption](https://arxiv.org/html/2608.07954v1/x3.png)Figure 3:Overview of KG neighborhood cache policies: LRU uses temporal locality, moving hits to the front and evicting least\-recently\-used entries\. LFU uses frequency locality, incrementing access counts on hits and evicting least\-frequently\-used entries\. Trace\-aware static\-frequency leverages the full request trace for global popularity but isn’t a theoretical upper bound\.
### 3\.3Semantic Caching Management

Semantic caching extends the entity\-level framework to the query\-context level, operating in four steps\.

1. 1\.Encoding: Each cache entry stores a query embedding together with the verbalized KG context constructed for that query\. Embeddings are computed withall\-MiniLM\-L6\-v2and L2\-normalized, so cosine similarity reduces to a dot product: sim​\(di,dj\)=𝐮⋅𝐯=∑k=1384uk​vk\\text\{sim\}\(d\_\{i\},d\_\{j\}\)=\\mathbf\{u\}\\cdot\\mathbf\{v\}=\\sum\_\{k=1\}^\{384\}u\_\{k\}v\_\{k\}\(1\)
2. 2\.Retrieval: For an incoming query, the cache computes its embedding and searches allCCstored embeddings of dimensiond=384d=384for the maximum similarity score\. This exhaustive comparison costsO​\(C​d\)O\(Cd\)time, excluding computation of the query embedding itself\.
3. 3\.Hit/miss decision: A semantic hit is triggered when the maximum score meets a tunable thresholdτ∈\[0,1\]\\tau\\in\[0,1\]\. On a hit, the cache reuses the associated context, skipping KG traversal and its intermediate context\-construction steps\. The answer\-generation LLM is still invoked for the incoming query\. On a miss, the configured KGQA pipeline runs in full\.
4. 4\.Insertion and eviction: A miss inserts the query embedding and resulting context as a new cache entry\. Under the online policies, LRU and LFU operate on these query\-context entries as described in Section[3\.2](https://arxiv.org/html/2608.07954#S3.SS2)\.

Semantic caching is complementary to entity\-neighborhood caching\. While entity caching reduces backend work at each reasoning hop, semantic caching reuses a previously constructed context across similar queries\. On a semantic miss, entity caching can still reduce KG retrieval during traversal\.

## 4Implementation

We integrate the entity\-neighborhood cache with ToG and use a RoG\-style plan\-then\-execute baseline in the semantic\-cache experiments\. Virtuoso\[openlink\_virtuoso\]and Oxigraph\[oxigraph\_db\]serve as interchangeable KG backends\. Before loading Freebase\[freebase\], we retain entity\-to\-entity triples, English textual triples, and typed literal triples while removing non\-English textual triples\. For each dataset, we then collect the Freebase entity identifiers associated with its questions and retain every triple whose subject or object references one of those identifiers\. The result is a dataset\-specific collection of incident triples rather than a vertex\-induced subgraph or the full Freebase graph\. This construction reduces loading and query cost, so the reported KG latency should be interpreted for these evaluation\-specific subgraphs\.

The reported experiments useGemini 3\.1 flash\-liteandClaude Haiku 4\.5\. A ToG query may trigger multiple calls because each traversed hop can include relation pruning, entity pruning, and an answer\-sufficiency check, followed by answer generation\. The exact count is path\-dependent, but evaluated queries required five to seven calls in our experiments\. We use WebQSP and CWQ because the workload characterization in Section[2](https://arxiv.org/html/2608.07954#S2)shows different reuse concentration across their initial and traversal\-level entity accesses\.

We evaluate LRU, LFU, and the trace\-aware static\-frequency reference labeled Oracle\. For the exact entity\-cache hit\-rate experiments, we vary cache capacity and report both the original question order and a randomized order for each policy\. Separate runtime experiments execute the configured pipeline with and without caching, while the semantic answer\-quality experiment uses the full WebQSP test set as described in Section[5\.5](https://arxiv.org/html/2608.07954#S5.SS5)\.

## 5Results

### 5\.1Experimental Setup

DatasetsWe use the dataset\-specific Freebase collections described in Section[4](https://arxiv.org/html/2608.07954#S4)\. Entity\-cache hit\-rate and runtime experiments use WebQSP and CWQ, while engine quality and semantic\-cache answer quality are evaluated on the WebQSP test set\.

LLMsThe LLMs used for these experiments areGemini 3\.1 flash\-liteandClaude Haiku 4\.5, accessed through a university\-provided API platform\. The LLMs are instructed to answer only from information obtained from the KG and not to fall back on parametric knowledge\. Otherwise, a model could mask degradation in cached KG context by answering from parametric knowledge\. External grounding is disabled for the same reason\.

Performance MetricsThe primary performance metric for entity caching is KG retrieval speedup, defined as no\-cache KG time divided by cached KG time\. We also report cache hit rate and KGQA answer quality\. For semantic\-context caching, which can skip intermediate LLM calls, we report full\-system speedup\. KGQA metrics are calculated using the scripts provided by the dataset authors\[WebQSP\]\.

### 5\.2Accuracy Results

We first evaluate our Think\-on\-Graph and Reasoning\-on\-Graph implementations\. Table[1](https://arxiv.org/html/2608.07954#S5.T1)reports Exact Match, precision, recall, F1, and Hits@1 on WebQSP\. The best Exact Match score is71\.51%71\.51\\%using ToG and79\.04%79\.04\\%using RoG\. We note that our focus is primarily on reducing graph traversal overhead via caching rather than improving the accuracy of KGQA\. These results simply establish the answer quality of the evaluated engines\.

Table 1:Engine Evaluation Results\. EM: exact match, P: precision, R: recall, F1: F1\-score, H@1: Hits@1, vir: Virtuoso, oxi: Oxigraph, gem: Gemini 3\.1 flash\-lite, hu: Haiku 4\.5RoG

ToG

### 5\.3Cache Hit Rate

Figures[4](https://arxiv.org/html/2608.07954#S5.F4)a and[4](https://arxiv.org/html/2608.07954#S5.F4)b show the cache hit rate of ToG on WebQSP and CWQ, respectively\. Thexx\-axis shows the cache size, measured as the number of entity neighborhoods that can be stored in the cache\. Theyy\-axis shows the cache hit rate, defined as the fraction of KG neighborhood requests served directly from the cache\. We evaluate three cache policies: LRU, LFU, and the trace\-aware static Oracle\. We report results under both sequential access, where questions are processed in their original dataset order, and shuffled access, where the question order is randomized\.

Figure[4](https://arxiv.org/html/2608.07954#S5.F4)a shows that WebQSP exhibits meaningful reuse even with small cache sizes\. Under sequential access, LRU achieves a16\.6%16\.6\\%hit rate with only 10 cached entities and improves to30\.7%30\.7\\%with 50 cached entities\. Increasing the cache beyond 50 entities provides smaller gains for LRU, which reaches31\.0%31\.0\\%,32\.9%32\.9\\%, and34\.6%34\.6\\%at cache sizes 100, 500, and 1000, respectively\. LFU is less effective at small cache sizes, achieving only7\.3%7\.3\\%,10\.4%10\.4\\%, and14\.1%14\.1\\%hit rate at cache sizes 10, 50, and 100\. This indicates that small\-cache performance in WebQSP is driven more by temporal locality than by long\-term frequency alone\.

The Oracle performs poorly at small cache sizes on WebQSP, with only2\.9%2\.9\\%hitrate at size 10 and14\.8%14\.8\\%at cache size 100\. However, as cache capacity increases, Oracle improves substantially, reaching37\.4%37\.4\\%at 500 and54\.4%54\.4\\%at 1000, showing that globally frequent entities become useful only when the cache is large enough\. At small cache sizes, LRU outperforms Oracle because it does not adapt to short\-term bursts of reuse\. Shuffled\-access results follow the same trend as sequential access, showing that reuse in WebQSP is not only an artifact of the original question ordering\.

Figure[4](https://arxiv.org/html/2608.07954#S5.F4)b shows that CWQ follows the same overall pattern as WebQSP, but with stronger gains at larger cache sizes\. Under sequential access, LRU improves from13\.8%13\.8\\%at cache size 10 to37\.2%37\.2\\%at cache size 1000, showing that CWQ also contains substantial temporal reuse\. LFU starts lower, achieving only6\.9%6\.9\\%at cache size 10, but becomes competitive as the cache grows and slightly exceeds LRU at cache size 1000 with a38\.6%38\.6\\%hit rate\. The trace\-aware static Oracle is also weak at small cache sizes, reaching only5\.6%5\.6\\%at cache size 10, but improves sharply to47\.2%47\.2\\%and62\.3%62\.3\\%at cache sizes 500 and 1000, respectively\. This shows that CWQ contains both short\-term temporal locality and strong global frequency skew\. LRU captures the former effectively at small cache sizes, while LFU and Oracle benefit more as the cache becomes large enough to retain frequently reused entities\. The shuffled\-access results closely match the sequential\-access results across all policies, suggesting that CWQ cacheability is not an artifact of the original question order\.

Overall, these results show that both WebQSP and CWQ provide non\-trivial opportunities for KG neighborhood caching\. LRU is the strongest online policy at small cache sizes because it captures short\-term temporal locality\. LFU is weaker at small capacities but becomes competitive as the cache grows, especially on CWQ\. The trace\-aware static Oracle performs poorly at small cache sizes but improves sharply at larger capacities, showing that many repeated accesses are associated with globally frequent entities\. The similarity between sequential and shuffled access further suggests that the measured cache benefits are not merely artifacts of dataset ordering\.

![Refer to caption](https://arxiv.org/html/2608.07954v1/x4.png)Figure 4:Cache hit rates for sequential and shuffled access orders in KGQA\. \(a\) WebQSP\. \(b\) CWQ\.
### 5\.4KG Retrieval Impact of Entity Caching

We evaluate KG one\-hop neighborhood caching at cache size 1000 and compare the no\-cache baseline with LRU and LFU on WebQSP and CWQ\. The reported times are cumulative over 400 inputs from each dataset\. Oracle is excluded because it requires the complete request trace in advance\.

Caching reduces KG retrieval time for both datasets, but the magnitude of the speedup differs even though the cache hit rates are similar\. The results are shown in Table[2](https://arxiv.org/html/2608.07954#S5.T2)\. On WebQSP, LFU achieves a34\.8%34\.8\\%hit rate and reduces KG time from57\.0​s57\.0\\,\\mathrm\{s\}to42\.3​s42\.3\\,\\mathrm\{s\}, saving14\.7​s14\.7\\,\\mathrm\{s\}and providing a1\.35×1\.35\\timesKG speedup\. On CWQ, LFU achieves a comparable hit rate of38\.6%38\.6\\%, but reduces KG time from57\.6​s57\.6\\,\\mathrm\{s\}to30\.2​s30\.2\\,\\mathrm\{s\}, saving approximately27\.5​s27\.5\\,\\mathrm\{s\}and providing a larger1\.91×1\.91\\timesKG speedup\. This gap shows that runtime improvement depends both on cache hit rate and the cost of the avoided KG requests\.

Table 2:KG Time and Speedup by Cache Policy \(sequential access, cache capacity 1000\)We note that entity\-neighborhood caching accelerates KG lookups but does not change the LLM call sequence\. Hence, we report KG\-component speedups in this section\. Semantic\-context caching, evaluated next, can reuse a completed context and skip graph traversal and its intermediate LLM calls\. We therefore report full\-system speedup for semantic caching\.

### 5\.5Semantic Context Cache Results

In this section, the results of Semantic Context Cache are analyzed\. The results are analyzed on the same cache replacement policies mentioned in the previous section \(LRU, LFU, Oracle\)\. Unlike Dominic et al\.\[other\_caching\], who cache complete responses on a custom dataset, we cache retrieved KG context and still invoke the answer\-generation LLM on the WebQSP dataset\. Table[3](https://arxiv.org/html/2608.07954#S5.T3)reports cold\-cache, first\-pass hit rates on WebQSP\. Exact query matching produces no hits because no question string repeats, whereas the semantic policies reach up to13\.5%13\.5\\%\.

Table 3:Cold\-cache semantic\-context hit rate on WebQSP\(%\)\. G/H: Gemini/Haiku; O/V: Oxigraph/Virtuoso\.SysPolicyG\(O\)G\(V\)H\(O\)H\(V\)RoGLRU7\.77\.70\.012\.3LFU12\.60\.07\.77\.7Oracle9\.96\.89\.312\.2
SysPolicyG\(O\)G\(V\)H\(O\)H\(V\)ToGLRU8\.213\.58\.28\.2LFU8\.28\.28\.28\.2Oracle7\.37\.37\.37\.3

The KG backends run in local Virtuoso/Oxigraph containers, while the cache is an in\-memory dictionary\. Figure[5\(a\)](https://arxiv.org/html/2608.07954#S5.F5.sf1)reports cold\-cache full\-system and per\-hit speedups on WebQSP for eight configurations: each combines a KGQA engine \(RoG or ToG\), an LLM \(Gemini or Haiku\), and a KG backend \(Virtuoso or Oxigraph\)\. Exact matching remains at1\.00×1\.00\\timesbecause it has no hits, while the semantic policies reach up to1\.06×1\.06\\times\. Each cache hit is up to3\.73×3\.73\\timesfaster then a miss, but low overall speedup is a sysmptom of low cache hit rate as shown in Table[3](https://arxiv.org/html/2608.07954#S5.T3)\. Oracle is an offline reference because it requires the request trace in advance\. Because entity overlap is imperfect atτ=0\.90\\tau=0\.90, we evaluate F1 on the full WebQSP test set using Gemini 3\.1 flash\-lite\. Figure[5\(b\)](https://arxiv.org/html/2608.07954#S5.F5.sf2)compares cache sizes 128, 512, and an unbounded cache with the no\-cache baseline\. The F1 scores differ from their respective baselines by at most 1\.7 percentage points and show no monotonic trend with cache size\. Without repeated trials, we cannot distinguish a cache effect from LLM nondeterminism\[non\_determinism\]\. These results show no large F1 degradation in this setting, but they do not establish thatτ=0\.90\\tau=0\.90is generally safe; CWQ remains untested\.

![Refer to caption](https://arxiv.org/html/2608.07954v1/x5.png)\(a\)Cold\-cache speedup of semantic\-context caching on WebQSP\.
![Refer to caption](https://arxiv.org/html/2608.07954v1/x6.png)\(b\)WebQSP F1 atτ=0\.90\\tau=0\.90with Gemini 3\.1 flash\-lite across cache sizes; size 0 is the no\-cache baseline\.

Figure 5:Semantic caching results

## 6Related Work

Iterative TraversalA prominent line of work has an LLM traverse the KG hop by hop, using beam search to control the candidate set\.Think\-on\-Graph\(ToG\)\[TOG\_01\]uses an LLM to score and prune graph traversals until an answer is reached or a depth limit is hit; its LLM calls grow with traversal depth and per\-hop relation and entity pruning\.Think\-on\-Graph 2\.0\(ToG\-2\.0\)\[TOG\_02\]adds a pre\-traversal reasoning stage intended to reduce exploration of irrelevant branches\.Search\-on\-Graph\(SoG\)\[sog\]simplifies the beam formulation to aSearch\(\)function for adaptive one\-hop expansion, reducing LLM calls while remaining competitive on Freebase and Wikidata benchmarks\.Plan\-on\-Graph\(PoG\)\[pog\]first generates a relation\-oriented plan and then uses it to guide iterative beam traversal\. Without explicit cross\-query caching, these methods process questions independently, so questions sharing topic or intermediate entities may repeatedly retrieve the same neighborhoods\.

One\-Shot PlanningA second family avoids iterative planning calls by having the LLM generate a relation\-path plan before KG execution\.Reasoning on Graphs\(RoG\)\[rog\]fine\-tunes an LLM to generate relation paths, retrieves valid paths from the KG, and verbalizes them for a separate reader LLM to produce the final answer\.KARPA\[karpa\]removes this fine\-tuning requirement by using a training\-free LLM for global path planning over relation embeddings and matching generated paths to KG structure through embedding similarity rather than exact string matching\. One\-shot planning reduces planning\-stage LLM calls, but KG execution can still revisit entities or relation paths across questions unless results are cached\.

Subgraph RetrievalA third paradigm separates KG access from downstream LLM reasoning: a retriever extracts a subgraph around the question’s topic entities, and the LLM reads its verbalization without further KG access\.Subgraph Retrieval Enhanced Model\(SR\)\[subgraph\_retrieval\_enhanced\]introduced a trainable dual\-encoder retriever decoupled from the downstream reasoner, with weakly supervised pre\-training on shortest paths between topic and answer entities\.ReasoningLM\[reasoning\_lm\]adapts a PLM to perform GNN\-style subgraph reasoning through structural self\-attention, tuned on synthesized subgraph–question pairs\.SubgraphRAG\[subgraphrag\]uses a lightweight parallel MLP triple scorer to produce flexibly sized subgraphs for an unmodified LLM reader\. Questions sharing topic entities or relation chains may retrieve overlapping subgraphs\. Existing KG\-RAG work emphasizes subgraph selection, whereas our work studies application\-level reuse of already retrieved entity neighborhoods\.

Semantic and KG\-Augmented CachingA complementary line of work caches LLM responses rather than underlying KG retrieval\. The KG\-Enhanced Semantic Cache embeds queries, reuses responses for sufficiently similar queries, and organizes them using KG structure\[other\_caching\]\. KGCache instead primarily caches exact entity neighborhoods at the KG backend boundary; its semantic cache reuses retrieved KG context while retaining per\-query answer generation\.

## 7Conclusion

In this work, we show that KGQA workloads exhibit substantial and skewed entity reuse during iterative Think\-on\-Graph traversal\. Motivated by this reuse, we implement entity\-neighborhood caching with LRU, LFU, and a trace\-aware static Oracle policy\. We proposed 2 approaches: caching of one\-hop neighbourhood, and semantic\-context cache\. We proved that both work on both iterative and one\-shot planning approaches\.

Our study leaves several opportunities for future work\. First, our cache is implemented as an in\-memory dictionary and stores one\-hop neighborhoods at entity granularity\. This design is useful for isolating reuse behavior, but it does not model the full complexity of a production cache\. Second, we evaluate only simple online policies, LRU and LFU\. More adaptive policies may capture both short\-term temporal locality and long\-term frequency skew more effectively\. Finally, because our KG backend is already fast due to indexed access, KG retrieval accounts for only a small fraction of total runtime\. As a result, even large KG\-side speedups translate to limited end\-to\-end gains\.

Building on these observations, one promising extension is to cache multi\-hop neighborhoods rather than only one\-hop neighborhoods\. However, this introduces a pruning challenge: different questions starting from the same entity may require different paths beyond the first hop, so the cache must preserve reusable structure without materializing irrelevant graph context\. Future systems should also consider hybrid KG and text\-based RAG pipelines, which are becoming increasingly common\. In such settings, caching could span both structured graph neighborhoods and unstructured retrieved passages, enabling broader reuse across LLM\-driven external\-memory reasoning\.

## References

## 8Appendix

### 8\.1AI disclosure

In this work, we used generative AI tools for spell checking, grammar correction, vocabulary correction, language editing, and basic coding assistance such as style alignment of plots and comments/readme files\. LLM\-generated code was verified and tested for correctness by the authors\. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI\.

### 8\.2Result Reproduction

The code is available in an anonymous[Github repository](https://anonymous.4open.science/r/KG_cache-1BA5/README.md)\. The repository has readme files that explain most of functionalities\. In order to run the experiments, the user needs to provide their own API Key to some LLM endpoint\. Current system is using OpenAI API compatible endpoints\. Minor changes might be needed to use some vendor not supported by this project\. Current publicly available vendors are Google and OpenAI\. After the results are run, the readme files provide instructions on how to reproduce charts and their output locations\. Certain discrepancies between the presented results and reproduced results are expected, especially if the dataset is run partially, or a different LLM than the ones mentioned in the paper is used\.