Some recommenders justify each suggestion with a chain of facts drawn from a product knowledge graph, for example "you bought this jacket, which shares a brand with that coat." To find these chains, the system runs a learned, user-specific search over the graph. At a busy moment, thousands of users request recommendations at once, and their searches walk through the same popular brands, categories, and features. Today each search runs in isolation. Meanwhile the catalog keeps changing: items go out of stock, new purchases arrive, products are delisted. This note proposes a serving engine that does three things. It shares the user-independent part of these searches across concurrent users. It keeps the shared intermediate state correct as the graph changes. And it guarantees that every user gets exactly the explanation path that an isolated search on the current graph would have produced, with no path ever routing through a deleted product.
The opportunity has two sides. Database work on batched path queries shows that sharing intermediate traversal state across overlapping queries pays off by large factors on static, untyped graphs. Explainable recommenders have never used it. The obvious ways of transplanting that idea into recommendation either change the explanations or go stale when the graph moves. Merging contexts across users changes what each user is told. Caching without maintenance serves explanations built from facts that no longer hold. The core claim is that the expensive work in policy-guided path search can be split into two parts: a shared, cacheable component tied to graph entities, and a cheap user-specific scoring step. If so, the engine can be both faster and exactly faithful, and the shared state can be maintained incrementally under deletions.
What exists and what is missing
The recommendation side supplies the method being accelerated. PGPR treats explanation as a reinforcement-learning walk over an Amazon product graph with users, items, brands, categories, and features. At each step, user-conditional pruning keeps the top-scoring candidate edges, using translational (TransE-style) embeddings. A policy-guided beam search then returns paths of at most three hops as rationales. It reports a 64.73% NDCG improvement over its best baseline on Clothing and finds valid paths for roughly half of its top recommendations. TPRec adds time by clustering interaction timestamps into temporal relations offline, and reports consistent gains over PGPR. Both run one independent search per user. TPRec handles time only through offline bucketing, not through live graph updates. We keep their models unchanged and change only how their inference is executed and kept fresh.
The query-execution side motivates the approach and supplies part of the mechanism. BatchEnum clusters hop-constrained path queries by their reachable neighborhoods and caches shared intermediate search states. It reports up to 7.7x speedup (6.4x on average) over sequential processing, and finds that reading cached sub-paths is nearly three orders of magnitude faster than re-traversal. Its graphs are untyped and static, it has no notion of personalized scoring, and its authors leave dynamic graphs as future work. SubGCache clusters graph-RAG queries (queries that retrieve a subgraph and feed it to a language model) by their retrieved subgraphs. It merges each cluster into one representative subgraph and reuses that subgraph's precomputed attention key-value cache, cutting time-to-first-token by up to 6.68x.
SubGCache constrains our design. Merging is acceptable for prompt grounding, but an explanation must be the chain that actually produced the user's recommendation, so a merged cluster-level context would be unfaithful. We therefore require the shared plan to be exactly equivalent to isolated search, not an approximation of it. GraphCache answers subgraph queries from cached containing or contained matches, which is a related reuse principle. Like the others, it assumes a fixed graph.
The maintenance side supplies a cautionary contrast. DiskANN's FreshVamana keeps search recall above 95% over 50 churn cycles by leaving deleted nodes in place as routing waypoints until a batched cleanup. That is the right choice for geometric vector search. It is the wrong choice here, because a waypoint in an explanation is shown to the user: "recommended via a product that no longer exists" is a visible error. UNIFY and iRangeGraph keep updates local to index segments rather than rebuilding the whole index. That locality principle is what we borrow, applied to symbolic typed edges rather than vector neighborhoods. Analyses of fully dynamic reachability warn that single edge changes can cascade. This is why our maintenance relies on the hop bound and on explicit dependency tracking rather than general reachability maintenance.
Core Claim
In PGPR-style search, the costly per-step work for a user sitting at entity $e$ has two parts. The first is gathering $e$'s typed outgoing edges and their embeddings. The second is scoring them against the user. The first part does not depend on the user. When the scoring is a dot product, as with translational embeddings and the policy's action layer, all users whose beams currently sit at $e$ can be scored in one matrix product:
$$S_e = Q_e A_e^{\top},$$
where $A_e$ is the cached matrix of embeddings for the actions (typed edges) leaving $e$, $Q_e$ stacks one query vector per (user, beam) currently at $e$, and $S_e$ holds every user's scores. Top-$\alpha$ pruning and policy probabilities are then applied row by row.
Because each row of $S_e$ equals what the isolated search would have computed, the selected paths are identical, up to floating-point ties that we resolve deterministically. The savings come from three sources. Each high-degree feature or brand node is gathered once per batch instead of once per user. Small scoring operations become one dense product. And the action matrices for frequently visited entities persist across batches. This mirrors BatchEnum's shared intermediate states, but the shared object is "candidate edges plus embeddings at an entity," not "enumerated sub-paths," and that is what makes exact personalized scoring possible on top of it.
The dynamic half of the claim is that this shared state can be maintained precisely. Each cached $A_e$ depends only on $e$'s outgoing edges and the embeddings of their targets. A reverse index from each entity and edge to the cached matrices that contain it lets a deletion or insertion invalidate or patch exactly the affected rows. Since paths have at most three hops, the work for any single update is bounded by local degree, not by global reachability.
Research Program
We will build the engine on top of the released PGPR and TPRec inference procedures. The trained policies and embeddings stay frozen, so every difference we measure comes from execution, not modeling.
The first component is an entity-grouped beam scheduler. A batching window collects concurrent requests. At each hop the scheduler groups live beams by their current entity and issues one gather and one scoring product per group. The window length is a tunable trade-off between queueing delay and sharing, and we will study it explicitly because accumulating queries adds latency, a problem the research file flags for this line of work.
The second component is a versioned cache of action matrices, with admission based on expected reuse. Entity visit frequency is heavily skewed toward popular brands and categories. Admission can be framed as a knapsack choice under a memory budget, in the spirit of Carra et al..
The third component is the maintenance layer. Its edge deletions and entity removals are eager: they remove rows from every dependent matrix before the next batch is scored, which enforces the invariant that no returned path touches a deleted entity or edge. Insertions from new purchases are patched in place. New items are added with an embedding initialized from their neighbors' embeddings, and the policy itself is not retrained.
The analysis we owe the reader has two parts. The first is a proof that the shared plan returns exactly the isolated plan's paths on the current snapshot. The second is a characterization of when sharing pays off, as a function of how concentrated beam visits are on high-degree entities. We will estimate that concentration directly from the Amazon request traces.
Baselines
The naive reference point is isolated PGPR (and isolated TPRec) inference. It runs one beam search per request on the current graph snapshot and is reloaded after every update window. It defines the correct output by construction, and every other system is scored against it for path agreement. We found no reported result on Lacuna for PGPR or TPRec inference latency or throughput, so we will measure this baseline ourselves on the same hardware.
The strongest systems competitor is a GPU-batched isolated beam search. Requests in the same window are padded and vectorized together, but each user still gathers its own candidate edges, so there is no sharing by entity. This is the baseline a practitioner would actually write. It captures most of the gain that comes simply from batching on a GPU, so beating it isolates the contribution of sharing. It will receive the same batching window, the same GPU, and the same tuning budget, with the batch size and window sweep given to every system.
The strongest existing sharing method is BatchEnum's approach of caching intermediate paths, adapted to typed edges. Its published reference is up to 7.7x and 6.4x average speedup over sequential processing on static untyped graphs (BatchEnum). Because its cached paths are not user-scored, our adaptation enumerates hop-bounded paths and filters them per user. We expect it to be exact but memory-heavy, owing to the huge fan-out of feature nodes.
For the dynamic setting, the comparisons are as follows. The first is our engine with a full cache flush on any update, which is the coarse invalidation the research file describes as current practice. The second is periodic rebuilding of the cache at fixed intervals with stale serving in between. The third is FreshVamana-style lazy tombstoning, where deleted entities stay traversable until a batched cleanup (DiskANN).
The ablations remove one ingredient at a time. One keeps entity grouping but drops cross-batch caching, which separates within-batch sharing from reuse across batches. Another keeps caching but replaces precise dependency tracking with time-to-live expiry.
We will count our engine as beating these baselines if it meets three conditions. Throughput at matched 99th-percentile latency must clearly exceed the GPU-batched isolated search. Path agreement with the isolated oracle must be 100% up to ties. And the stale-explanation rate must be zero, whereas tombstoning and periodic rebuilding are expected to produce nonzero rates.
Why not just…?
Why not just cache finished recommendations and explanations per user in a key-value store? Whole requests rarely repeat: the key is a user plus their current history, and every new interaction changes it. BatchEnum's observation that whole queries rarely coincide while their intermediate structure overlaps heavily is exactly why it caches sub-structures. We will measure the hit rate of a least-recently-used result cache on the replayed Amazon traces. We also report that cache's stale-explanation rate, since a cached rationale built before a deletion is precisely the failure we target.
Why not just batch the independent searches on a GPU and stop there? This is the real threat. If beam visits are spread out rather than concentrated on hubs, entity grouping saves little beyond what padding and vectorization already give. The head-to-head comparison against GPU-batched isolated search settles this, and we will report the advantage as a function of measured visit concentration. If the advantage is small on these datasets, the honest conclusion is that sharing matters only for traffic skewed toward popular entities. In that case the contribution narrows to exact, fresh maintenance of the cached action matrices.
Why not just rebuild offline every hour, or keep deleted items as tombstones the way FreshVamana does? Both are cheap, and both are wrong in a way users can see. Rebuilding leaves a window in which explanations cite delisted products. Tombstoning keeps deleted entities as stepping stones, which suits vector recall but not explanations a user reads. Our metrics count explanations that touch a deleted entity or edge. We will also report maintenance cost per update against rebuild cost, so the price of correctness is explicit rather than hidden.
Why not just have a language model write explanations from the user's history? Free-form generation does not guarantee that the stated reason is the one that produced the ranking. That is why ARES adds formal argumentation to enforce faithfulness. Such generation also adds heavy serving cost per request, the bottleneck SubGCache exists to reduce. This proposal is about systems whose explanations are checkable graph paths, so this alternative falls outside its scope rather than competing with it on the same terms.
Proposed Experiments
We use the Amazon Clothing, Cell Phones, Beauty, and CDs & Vinyl graphs with PGPR's five entity types and seven relations, as in PGPR and TPRec. We turn them into streams by replaying reviews in timestamp order. Each review triggers a recommendation request from its author, followed by the insertion of the purchase edge. Catalog churn is simulated in two ways: deleting items once their final review timestamp has passed, and injecting random brand or category edge deletions at controlled rates. Load is varied by compressing time to reach target request rates.
The first experiment is profiling, and it gates everything else. We break down isolated PGPR inference time into gathering, scoring, and policy evaluation, and we measure how concentrated beam visits are. If gathering at high-degree entities is not a meaningful share of the time, we stop and report that sharing is unwarranted.
The main experiment compares all baselines on throughput, 50th- and 99th-percentile latency, memory, path agreement with the isolated oracle on the current snapshot, stale-explanation rate, update-processing cost, and NDCG and Recall. The ranking metrics confirm that recommendation quality is unchanged and that the fraction of recommendations with valid paths stays near the roughly 50% PGPR reports.
We repeat the comparison on TPRec to show the mechanism carries over to a temporal relation schema.
The decisive checks are two. On the correctness side, the system must show exact path agreement and zero stale explanations under every churn rate while flush, rebuild, and tombstone baselines do not. On the efficiency side, it must show a throughput gain over GPU-batched isolated search that grows with visit concentration and survives the latency cost of the batching window. If the correctness check holds but the efficiency check fails, the paper still reports a negative result about where shared execution helps path-based explainers.
References
- Reinforcement Knowledge Graph Reasoning for Explainable Recommendation
- Time-aware Path Reasoning on Knowledge Graph for Recommendation
- Batch Hop-Constrained s-t Simple Path Query Processing in Large Graphs
- SubGCache: Accelerating Graph-based RAG with Subgraph-level KV Cache
- GraphCache: A Caching System for Graph Queries
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search
- UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search
- iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search
- Average Case Analysis of Fully Dynamic Reachability for Directed Graphs
- In-memory Caching for Multi-query Optimization of Data-intensive Scalable Computing Workloads