C OMPASS: Steering Distributed Vector Search with Scientific Knowledge Graphs Song Young Oh∗ , Amal Gueroudji† , Seth Ockerman‡ , Rob Latham† , Orcun Yildiz† , Ian Foster§∗ , Kyle Chard∗§ , Robert Ross† ∗ Department of Computer Science, University of Chicago, Chicago, IL, USA † Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL, USA ‡ Department of Computer Science, University of Wisconsin–Madison, Madison, WI, USA
arXiv:2609.13452v1 [cs.DB] 11 Sep 2026
§ Data Science and Learning Division, Argonne National Laboratory, Lemont, IL, USA
Abstract—Vector databases use hashing to partition data across “shards,” logical units for distributed execution. This placement, however, destroys semantic locality, forcing each query into scatter– gather limited by the slowest shard. Vector-space clustering can help, but scientific evidence is often connected by factual relations that do not align with embedding distance. We present C OMPASS, a framework that uses a knowledge graph (KG) to determine data placement and query-time shard selection. C OMPASS detects communities, splits oversized communities, inserts embeddings by subject entity, and routes queries to a small set of shards. Across four biomedical KGs, our method searches only 13–18% of the corpus while preserving broadcast recall and recovering up to 2.6× more multi-hop evidence than an embedding-based baseline. On 15 HPC nodes, C OMPASS sustains 7.9× higher throughput with lower tail latency than hash-based broadcast. These results show that KG structure provides a compact complement to embedding geometry for scalable vector search. Index Terms—Data Management, Distributed Storage, Vector Databases, Knowledge Graphs, Performance Analysis.
I. I NTRODUCTION Vector search has become an essential data service for artificial intelligence (AI) agents in scientific research [1]– [3]. As collections grow, vector databases divide their data across shards to increase capacity [4]–[6]. Most systems use hash-based methods to split data into shards because hashing is computationally inexpensive and provides balanced data Fig. 1: C OMPASS overview. C OMPASS detects graph complacement [7], [8]. The resulting layout, however, provides no munities and splits oversized communities to balance shard semantic locality: evidence relevant to one question may be sizes. It assigns new vectors to shards based on their graph scattered across different shards. Each query must therefore neighborhoods and searches only m ≪ B shards per query. search every shard and wait for a full scatter–gather to complete. Adding shards thus increases coordination overhead and total a result, embedding-based placement may scatter evidence per-query cost [9]. needed for the same queries across too many shards. An alternative to scatter–gather is selective search, which routes each query to only a subset of shards. Inverted File (IVF) Knowledge graphs (KGs) provide a complementary placeindexes utilize selective search by partitioning vectors into k- ment signal by explicitly encoding domain-specific relationmeans clusters and limiting search to only the nP robe “closest” ships that embeddings may miss [16]. Using this signal clusters, defined by distance between each cluster’s centroid for sharding requires deciding how to partition the graph and the query [10], [11]. A distributed vector database can while preserving useful relationships. Graph systems typically similarly co-locate related vectors and search only the most address this with edge-cut methods that balance vertices, while relevant shards. In scientific workloads, however, relevance vertex-cut and replication schemes further handle high-degree often depends on structured relationships that embedding vertices and load skew [17]–[20]. For semantic search, KG similarity does not reliably preserve [12]–[14]. For example, a communities—densely connected groups of entities—offer a drug, its target protein, and a disease mechanism can be linked natural basis for co-locating associated vectors likely to support by typed relations despite distant textual embeddings [15]. As related or multi-hop queries [21]. However, community sizes
can vary substantially [22], so placement must balance graph locality against shard load. We present C OMPASS (COMmunity-guided Placement And Shard Selection), a data placement and routing layer for distributed vector databases (Fig. 1). During the initial upload phase, C OMPASS detects KG communities, splits only those too large for balanced placement, and assigns the resulting pieces to shards. Embeddings are stored with their subject entities: those for known entities follow the existing entity-to-shard map, while those for unseen entities are placed based on their graph neighborhoods. At query time, personalized PageRank (PPR) [23] scores shards from entities named in the query, and shard-local approximate nearest-neighbor (ANN) indexes search only the highest-ranked shards [24]. Our evaluation separates the system’s benefit of selective search from the quality benefit of graph-guided insertion. With the same two-shard search, C OMPASS and k-means achieve similar query throughput and latency, but C OMPASS preserves broadcast recall and retrieves up to 2.6× as much multi-hop evidence. It raises throughput from 9.0k to 71.8k queries/s and reduces p95 latency from 8.1 to 1.0 ms over broadcast on 15 HPC nodes. Further analysis shows that these gains come from co-locating related data rather than exploiting answer-specific graph links during routing. This work makes the following three contributions: 1) We formulate distributed vector search as a joint locality and load-balance problem, demonstrating that embedding proximity alone may not preserve relational evidence. 2) We design and implement C OMPASS, which combines bounded KG communities, graph-based online placement, and selective shard search. 3) We evaluate C OMPASS on four biomedical KGs, measuring retrieval quality, system performance, and the conditions under which graph-aware placement is most effective.
Graph-guided retrieval. Graph RAG methods use graph links to retrieve connected evidence [31]–[34], traverse reasoning paths [35], [36], or build lightweight entity–relation indexes [37]. This literature mostly focuses on which evidence to return, while treating the vector store layout as fixed [38]. Closer to our distributed setting, DGRAG [39] builds local KGs at edge devices, summarizes their subgraphs, and uses a cloud coordinator to route queries to relevant devices. However, its partitions are determined by data ownership, whereas C OMPASS derives shard boundaries from knowledge graph structure. To form these boundaries, C OMPASS builds on community detection, which identifies densely connected regions of a graph [40]. Louvain [41] and Leiden [21] optimize modularity, which favors partitions containing more within-group edges than expected under a null model [42], while alternatives include label propagation, spectral clustering, and stochastic block models [43]–[46]. Because these methods do not enforce size constraints and can yield highly uneven communities [47], C OMPASS treats their outputs as candidate placement units and recursively splits only those that exceed a bound. III. M ETHODOLOGY A. Overview Let G = (V, E) be a knowledge graph, F a corpus of embedded facts, and B the number of vector database shards. Each fact f ∈ F has a subject entity s(f ) ∈ V . Given a query q, the router selects m shards, searches their local ANN indexes, and merges the resulting top-k candidates. Facts and entities share an embedding space; ex denotes the embedding associated with entity x, eq the query embedding, and µb the centroid of shard b’s fact embeddings. Selective search is effective only when relevant facts concentrate on a small number of shards and shard sizes stay balanced. C OMPASS addresses both through a shared entity-toshard map β : V → {1, . . . , B}, which records where facts are stored and how graph evidence becomes shard-level routing decisions. Query work is therefore proportional to the facts on the selected shards, X W (q) = |Fb |, (1)
II. R ELATED W ORK Distributed vector and graph systems. Sharding, a standard technique in distributed databases, partitions storage and computation across machines to improve scalability and availability [5], [6], [8]. Vector databases adopt this design: each b∈S(q) shard stores a subset of the vectors in one or more segments, with each segment maintaining its own index [25]. Widely used and latency is determined by routing, the slowest selected shard, systems, such as Qdrant [26] and Milvus [7], assign vectors and result merging. to shards by hashing their identifiers, often through consistent C OMPASS maintains this mapping across three phases: offline hashing [27]. Because this approach does not preserve semantic data placement, online insertion of new facts, and query-time relationships, queries generally follow a scatter–gather model: routing to m shards. Algorithm 1 summarizes these phases they search every shard and merge the local results [9], [28]. and the rest of this section presents the details. Distributed graph processing systems also divide vertices and edges while preserving locality. Classical edge-cut methods B. Data placement map vertices to balanced partitions and minimize cross-partition We construct the initial layout from a bootstrap graph edges [17]–[19]. For graphs with skewed degree distributions, Gbulk = (Vbulk , Ebulk ). C OMPASS applies Louvain community vertex-cut systems such as PowerGraph [20] instead partition detection [22], which greedily groups neighboring vertices to edges and replicate vertices whose incident edges span mul- increase modularity, a measure of how strongly vertices connect tiple partitions, particularly high-degree vertices [29], [30]. within communities relative to across them. It then collapses C OMPASS adopts this locality–balance objective for vector each community into a supernode and repeats until modularity placement. no longer improves. A large community can overload one shard,
Algorithm 1 C OMPASS data placement and query routing Require: bootstrap graph Gbulk , facts F , shards B Offline placement (place: Eq. 2) 1: Gu ← U NDIRECTED(Gbulk ) 2: C ← L OUVAIN(Gu ) 3: split each C ∈ C with |C| > Cmax = ⌈ρ|Vbulk |/B⌉ 4: for C ∈ C in decreasing order of |C| do 5: b⋆ ← empty shard if any; otherwise, arg maxb place(C, b) 6: β(v) ← b⋆ ∀v ∈ C; update Lb⋆ , hb⋆ 7: end for 8: store each fact f ∈ F on shard β(s(f )) Online routing (score: PPR mass per shard, Eq. 3) 9: insert unseen x: shard arg maxb score(N (x), b); otherwise, nearest µb 10: query q: top-m shards by score(Aq , b); otherwise, by cos(eq , µb )
so we bound each piece by Cmax = ⌈ρ |Vbulk |/B⌉, where ρ controls the maximum piece size relative to the average shard load. Communities above the bound are recursively repartitioned by Louvain on their induced subgraphs, and smaller ones remain intact. Let C denote the resulting pieces. For piece C, hC is its normalized entity-type histogram and |C| its size; for shard b, hb and Lb denote its type histogram and entity load. Pieces are processed largest first: the first B seed empty shards, and each remaining piece is assigned to the shard maximizing
TABLE I: Biomedical knowledge graph datasets. KG PriKG HipKG PhaKG GoKG
Edges (facts)
Nodes (entities)
Questions
298k 190k 91k 44k
54k 17k 43k 44k
1044 909 961 926
named in q as anchors Aq . C OMPASS runs PPR, searches the m highest-scoring shards, and merges their top-k results. If no entity is linked, shards are instead ranked by similarity between the query embedding eq and shard centroids µb . The router stores only the entity-to-shard map, truncated graph adjacency, and one centroid per shard. It operates outside the vector database and requires no changes to local ANN indexing or the query interface. IV. E XPERIMENTAL S ETUP A. Datasets and metrics
We evaluate C OMPASS on four biomedical KGs (Table I) used in SciCUEval [48]: PrimeKG [49] (PriKG), HIPPIE [50] (HipKG), PharmKG [51] (PhaKG), and Gene Ontology [52] (GoKG). For each KG, we deduplicate and combine groundtruth facts with distractors so all methods search the same corpus. SciCUEval classifies questions as (i) relevant information identification, (ii) information integration, or (iii) context-aware inference. We group the latter two as multi-hop because both Lb place(C, b) = cos(hC , hb ) − λ, , (2) require combining evidence across entities. |Vbulk |/B Facts and questions are embedded with the 768-dimensional where λ balances type compatibility against shard load. All S-PubMedBert-MS-MARCO encoder. We primarily report entities in a piece share its shard assignment, and each fact fact recall@10, the fraction of a question’s ground-truth facts is stored with its subject entity. Thus, the KG determines returned in the top 10; “recall” denotes this throughout. It placement across shards, while each local ANN index ranks scores which facts answer a question (semantic ground-truth), not which vectors are nearest to it (ANN ground-truth). We also facts by embedding similarity. report gold-shard coverage, whether the selected shards hold the C. Online insertion evidence before local ranking; corpus fraction searched, which New entities subsequently arrive as an insertion stream. A accounts for unequal shard sizes; shard-load Gini, the imbalance fact whose subject is already known is sent directly to β(s(f )). of facts across shards (0 uniform, 1 maximally skewed); query Both insertion and query routing use personalized PageRank throughput and p50/p95/p99 latency; and router memory. Held(PPR) [23]: from an anchor set A, PPR yields a distribution out edge recovery and RAG answer accuracy provide additional πA over entities, and each shard is scored by the mass on its measures of embedding quality and end-to-end utility. assigned entities, B. Baselines and system X score(A, b) = πA (v). (3) We compare C OMPASS against two baselines. (1) ID-hash v:β(v)=b (broadcast) assigns facts to shards by identifier and searches all PPR uses restart probability α and sparse power iteration, shards for every query. (2) k-means clusters fact embeddings, keeping mass near the anchors while allowing propagation assigns each cluster to a shard, and routes queries to the nearest cluster centroids. It uses the same shard budget as C OMPASS but through indirect relationships. For an unseen entity x, C OMPASS uses its known neighbors relies only on embedding similarity rather than graph structure. We further evaluate two alternative placement strategies N (x) as anchors and assigns x to the shard maximizing score(N (x), b); later facts about x inherit this assignment. to isolate the effect of bounded community splitting. (1) No If x has no known neighbor, it is placed at the nearest shard community split keeps each Louvain community intact and assigns it to a single shard, preserving graph locality but centroid µb . allowing oversized communities to create load imbalance. D. Query routing (2) Fully scattered distributes the members of each community At query time, C OMPASS uses the same graph-based shard across shards, improving load balance while eliminating scoring. A conservative entity linker extracts only entities community locality.
Experiments use Qdrant v1.16 [26] with a Rust gRPC client on Aurora supercomputer at Argonne Leadership Computing Facility. Each shard uses a local HNSW index with m=16 and ef=128, stored in node-local tmpfs. C. Protocol
TABLE II: Recall@10 with 2 of 16 shards selected for search. KG PriKG HipKG PhaKG GoKG
Overall recall@10
Corpus searched
Multi-hop recall@10
C OMPASS k-means Broadcast
Fraction
C OMPASS k-means Broadcast
0.496 0.434 0.587 0.571
0.335 0.338 0.396 0.523
0.469 0.393 0.567 0.601
17.4% 12.8% 14.8% 18.5%
0.324 0.217 0.176 0.372
0.124 0.121 0.086 0.347
0.246 0.163 0.165 0.439
We evaluate retrieval quality on all four KGs using 16 shards, with selective methods probing two shards by default. TABLE III: Placement at 128 shards on PriKG. Community C OMPASS uses ρ = 1.5, λ = 0.5, α = 0.5, 7 PPR iterations, span is the average number of shards occupied by a community. and at most 128 outgoing neighbors per entity unless specified Comm. span Gini Corpus searched Recall@10 QPS otherwise. For system-level experiments, we use PriKG, the Strategy No community split 1.00 0.95 44.6% 0.465 15.0k largest corpus, varying the shard count from 32 to 128, scaling C OMPASS 1.02 0.37 2.9% 0.511 18.6k a 60-shard deployment from 1 to 15 nodes, and varying HNSW Fully scattered 1.78 0.19 3.1% 0.488 16.2k segments and Qdrant workers. B. Bounded splitting balances load while retaining locality D. Answer-leakage controls Fig. 3 isolates the effect of community splitting on PriKG. Because the indexed facts and routing graph come from Keeping Louvain communities intact leaves the shard-load Gini the same KGs, we use three mechanisms to prevent answer near 0.95 because the largest community dominates one shard. information from influencing routing. (1) Initial placement Full scatter improves balance but fragments communities across uses a 70% bootstrap graph; all remaining entities are inserted shards, weakening selective retrieval. C OMPASS instead splits online. (2) At query time, the router uses only entities explicitly only communities that exceed the shard-size bound. mentioned in the question, excluding answer entities and At 128 shards (Table III), no community split searches 44.6% intermediate entities. (3) After placement is fixed, we remove of the corpus with two shards. Full scatter reduces this to 3.1% the ground-truth evidence edges for each query before running but lowers recall, whereas C OMPASS searches 2.9%, achieves PPR. These controls test whether improvements come from the the highest recall, and delivers the highest throughput. It lowers persistent data layout rather than the direct traversal of answer Gini to 0.37, while each original community spans only 1.02 edges (Section V-A). shards on average. As the shard count increases from 32 to 128, the searched fraction falls from 7.4% to 2.9%, while related V. R ESULTS entities remain largely co-located. A. Selective search preserves recall C. Shard selection enables scale-out Fig. 2 compares recall@10 with the corpus fraction searched Fig. 4 fixes the database at 60 shards and scales Qdrant from at 16 shards. Across all four KGs, C OMPASS reaches a given 1 to 15 nodes. Broadcast throughput increases with node count recall while searching no more data than k-means. With but remains 7–8× below C OMPASS and k-means, while its p95 two probed shards (Table II), it searches 12.8–18.5% of the latency stays near 8–10 ms. At 15 nodes, C OMPASS reaches corpus, matches or exceeds broadcast recall on PriKG, HipKG, 71.8k QPS at 1.03 ms, compared with 9.0k QPS at 8.09 ms and PhaKG, and on GoKG reaches 0.571, within 0.03 of for broadcast (Table IV). k-means achieves similar system broadcast’s 0.601. The smaller gain on GoKG is consistent performance (70.2k QPS at 0.99 ms), confirming that selective with its embeddings already placing many graph-connected search drives the speedup. However, placement determines entities close together (Section V-E). retrieval quality: C OMPASS achieves 0.511 recall, compared The largest gains occur on multi-hop questions, for which with 0.306 for k-means (Fig. 4(b)). C OMPASS retrieves 2.6×, 1.8×, and 2.0× more relevant Resource measurements further explain these scaling results. evidence than k-means on PriKG, HipKG, and PhaKG, Broadcast sends every query to all 60 shards and reaches 15.4% respectively. For these questions, relevant facts may be linked in peak CPU utilization, yet delivers only 9.0k QPS. By searching the graph yet distant in embedding space. As a result, k-means two small shards, C OMPASS and k-means serve nearly 8× may place them on different shards, whereas C OMPASS tends more queries while keeping peak CPU utilization below 8%. In to co-locate them. Our selective search occasionally exceeds contrast, no-community-split selects only two shards, but they broadcast because it filters out high-scoring but irrelevant contain about 45% of the corpus. It therefore preserves 0.464 results; we treat these cases as preserving, rather than improving recall but reaches only 49.6k QPS with 1.73 ms p95 latency. upon, broadcast quality. Its largest-shard nodes reach 17.7% CPU utilization, exposing To rule out answer-edge leakage, we fix the placement and substantial load imbalance. Effective scale-out thus requires remove each query’s ground-truth edges before running PPR. both selective routing and balanced shards. We observe that gold-shard coverage changes by at most 0.028, and routing from question entities alone selects nearly the same D. Overheads and configuration effects shards. The gains therefore come from persistent co-location, C OMPASS adds modest setup cost (Table V). Community not direct traversal of answer edges. detection, bounded splitting, and shard assignment take at most
Fig. 2: Recall@10 versus corpus fraction searched at 16 shards. Each curve varies the number of probed shards; the dotted line marks broadcast recall. C OMPASS consistently reaches higher recall than k-means at the same search cost and matches broadcast’s performance while searching less than 20% of the corpus.
Fig. 3: Effect of community splitting on PriKG. Bounded splitting in C OMPASS reduces imbalance caused by oversized communities without scattering all across many shards. TABLE IV: Query performance and peak resource use with 15 nodes and 60 shards. CPU is the busiest node’s utilization, sampled every 5 s; memory is the largest per-node footprint, including Qdrant and in-memory shard data. Plan ID-hash (broadcast) k-means No community split C OMPASS
QPS (k)
p95 (ms)
Recall@10
CPU (%)
Memory (GB)
9.0 70.2 49.6 71.8
8.09 0.99 1.73 1.03
0.473 0.306 0.464 0.511
15.4 7.5 17.7 5.6
5.1 5.2 6.1 5.4
Fig. 4: Scaling on PriKG. (a) Selective methods benefit more from additional nodes than broadcast. No community splitting scales less effectively because its selected shards remain large. (b) At 15 nodes, C OMPASS and k-means provide similar throughput, but C OMPASS achieves much higher recall. TABLE V: C OMPASS construction-time breakdown in seconds.
Stage Bulk placement Community detection Bounded splitting Shard assignment New data routing Insertion (Qdrant) HNSW indexing
PriKG HipKG PhaKG GoKG 1.21 0.15 0.80 0.26 20.2 1.1 7.1
0.74 0.10 0.61 0.03 5.4 0.8 4.0
0.24 0.06 0.05 0.13 8.5 0.5 4.0
0.25 0.07 0.04 0.14 1.4 0.3 4.0
1.21 s. Routing new data takes 1.4–20.2 s, and insertion plus HNSW indexing adds 4.3–8.2 s. Total construction time ranges from 6.0 to 29.6 s across the four KGs. At run time, C OMPASS places each new entity in 105 µs– 29.6 10.9 13.2 6.0 1.24 ms and routes each query in 72 µs–1.46 ms. In terms End-to-end of memory, the router holds only the entity-to-shard map, the truncated adjacency, and one centroid per shard: 4.6–13.1 MB than graph routing (Table VI). As the number of Qdrant in total, 29–79× smaller than the whole fact embeddings it segments per shard increases, recall remains flat, but each steers. The centroids come from a one-time scan of the vectors query must search more local indexes. C OMPASS throughput (9.5–38.5 s on PriKG, depending on cache state): a cost the k- falls by about half, while broadcast drops from 8.5k to 1.8k means baseline pays for its core routing rather than a fallback. QPS and reaches 16.4 ms p95 latency. By contrast, increasing Including this scan, the full PriKG build cost is amortized after workers from 8 to 16 raises throughput from 28.9k to 54.9k QPS, with unchanged recall and peak node memory near 3%. about 0.75 million queries on 15 nodes. Local index configuration has a larger effect on performance Balanced shards therefore benefit from added concurrency,
TABLE VI: Effect of segments per shard (PriKG, 16 shards; C OMPASS probes two shards). More segments leave recall flat but add a local search on every contacted shard; the effect compounds for broadcast, which contacts every shard.
VI. D ISCUSSION AND L IMITATIONS
Data placement and routing are closely linked. Selective search reduces work by probing only a few shards, but its performance depends on both the number and size of the selected shards. The probe count affects total work, while C OMPASS Broadcast Seg./shard QPS (k) p95 (ms) R@10 QPS (k) p95 (ms) R@10 the largest selected shard often shapes latency because the query must wait for all selected shards to finish. Simple 2 16.0 1.4 0.491 8.5 2.3 0.471 layouts tend to favor one factor over the other. Keeping 4 14.7 1.6 0.496 6.6 3.2 0.472 8 12.1 1.9 0.498 3.3 8.3 0.477 communities intact preserves locality and limits the probe set, 16 8.9 2.9 0.496 1.8 16.4 0.480 but large communities can create oversized shards. Spreading communities more evenly improves balance but may scatter related evidence across many shards. C OMPASS seeks a middle ground by splitting oversized communities into bounded groups and routing queries over the resulting entity-to-shard map. The search schedule determines speed; placement determines recall. With the same two-shard budget, C OMPASS and k-means have nearly identical throughput and tail latency because they search the same number of similarly sized shards. However, their recall differs significantly because k-means groups facts only by embedding similarity, while C OMPASS keeps graph-related facts close when those relations are poorly captured by the embeddings. In other words, speed comes from balanced shards and a fixed probe count, while recall depends on which relationships the placement preserves. C OMPASS Fig. 5: Answer accuracy under the SciCUEval protocol, changes data insertion and query routing rather than the ANN averaged across three language models. Improvements in index itself, so it can be combined with better index structures or vector-compression methods. retrieval quality carry through to downstream answers. Graph structure is most useful when it complements whereas excessive segmentation adds unnecessary search work. embeddings. KG-guided insertion helps most when embedding similarity does not preserve the relations needed by the workload. Held-out edge recovery provides a simple way to estimate this complementarity before deployment: poor E. When graph structure adds value recovery suggests that the graph offers an independent signal for co-locating evidence, whereas strong recovery leaves less Graph-based placement is most useful when embedding room for improvement. Our gold-edge ablation further suggests similarity does not reflect KG links. To evaluate this, we remove that the gain arises from persistent data organization rather graph edges and ask whether an entity embedding can retrieve than direct graph traversal at query time. The downstream the entity at the other end of each removed edge among its RAG results also show that better placement improves LLM top-10 nearest neighbors. Hits@10 is only 1–2% on PriKG, accuracy across the evaluated models. HipKG, and PhaKG, indicating that their embeddings rarely Limitations. Our evaluation covers modest-scale biomedical place linked entities close together. On these KGs, C OMPASS KGs, one embedding model, one vector database, and corpora improves recall over k-means by 0.161, 0.096, and 0.191, of 44k–298k facts. Billion-scale, cross-domain, and storagerespectively. On GoKG, the embeddings recover about 50% backed deployments remain untested. C OMPASS also benefits of the removed links, and the recall gain falls to 0.048. queries that can be reliably linked to the KG; unanchored We next measure end-to-end RAG accuracy using Qwen2.5- queries fall back to centroid routing and receive no graph-based 7B, Llama-3.1-8B, and Gemma-2-9B (Fig. 5). Averaged across locality benefit. Finally, the bootstrap split and ground-truth the three readers, C OMPASS outperforms k-means on every KG, edge ablation reduce leakage concerns but do not establish improving accuracy from 0.293 to 0.331 on PriKG, 0.130 to performance when relevant evidence is missing from the graph. 0.178 on HipKG, and 0.315 to 0.396 on PhaKG. On these KGs, VII. C ONCLUSION where embeddings poorly preserve graph links, C OMPASS also matches or exceeds broadcast; the largest gain is on HipKG C OMPASS reframes distributed vector search around how (0.178 versus 0.143). On GoKG, where embedding similarity scientific data is organized before queries arrive. Rather than already captures much of the graph structure, all methods relying on embedding geometry alone, it uses the KG to perform similarly, with broadcast marginally ahead. These group structurally connected facts, while subdividing only the results indicate that improved placement translates into higher largest groups to avoid uneven shard utilization. The result answer accuracy without changing the reader. is a layout that supports selective search without dispersing
the evidence needed for relational questions. Our evaluation also clarifies that efficiency and retrieval quality arise from different parts of the design. Searching fewer shards reduces system cost, but remains effective only when the underlying layout concentrates relevant data within those shards. C OMPASS provides this concentration through KG-informed organization while preserving the existing ANN indexes within each shard. More broadly, our work shows that compact domain-specific structure can help distributed vector stores scale without making every query involve the entire database. ACKNOWLEDGMENT This work was supported by the U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research, through the TIDES project, and by NSF grant 2411188. This research used resources of the Argonne Leadership Computing Facility at Argonne National Laboratory, under Contract No. DE-AC02-06CH11357. R EFERENCES [1] K. Echihabi, T. Palpanas, and K. Zoumpatianos, “New trends in high-d vector similarity search: Ai-driven, progressive, and distributed.” Proc. VLDB Endow., vol. 14, no. 12, pp. 3198–3201, 2021. [2] A. Gueroudji, A. Kamatar, S. Chaouche, R. Ross, K. Chard, and I. Foster, “Beyond centralized labs: Federating the co-scientist,” in Supercomputing Asia and International Conference on High Performance Computing in Asia Pacific Region Workshops, 2026, pp. 443–449. [3] S. Y. Oh, A. Khan, I. Foster, and K. Chard, “Smurf: Federated multimodal retrieval for scientific data via embedding alignment,” in 2025 IEEE International Conference on eScience (eScience). IEEE, 2025, pp. 452–459. [4] S. Ockerman, A. Gueroudji, S. Y. Oh, R. Underwood, N. Chia, K. Chard, R. Ross, and S. Venkataraman, “Exploring distributed vector databases performance on HPC platforms: A study with Qdrant,” in SC’25 Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2025, pp. 575–581. [5] B. M. Abdelhafiz, “Distributed database using sharding database architecture,” in IEEE Asia-Pacific Conference on Computer Science and Data Engineering. IEEE, 2020, pp. 1–17. [6] A. S. Shethiya, “Load balancing and database sharding strategies in SQL Server for large-scale web applications,” Journal of Selected Topics in Academic Research, vol. 1, no. 1, 2025. [7] J. Wang, X. Yi, R. Guo, H. Jin, P. Xu, S. Li, X. Wang, X. Guo, C. Li, X. Xu, K. Yu, Y. Yuan, Y. Zou, J. Long, Y. Cai, Z. Li, Z. Zhang, Y. Mo, J. Gu, R. Jiang, Y. Wei, and C. Xie, “Milvus: A purpose-built vector data management system,” in International Conference on Management of Data, 2021, pp. 2614–2627. [8] S. Solat, “Sharding distributed databases: A critical review,” arXiv preprint arXiv:2404.04384, 2024. [9] S. Ockerman, S. Y. Oh, A. Gueroudji, R. Chaturvedi, P. Carns, N. Chia, M. Dorier, R. Latham, T. Mallick, S. Perarnau, R. Underwood, K. Chard, I. Foster, R. Ross, and S. Venkataraman, “When more cores hurts: The vector database scaling paradox in HPC,” arXiv preprint arXiv:2606.08950, 2026. [10] J. Zobel and A. Moffat, “Inverted files for text search engines,” ACM Computing Surveys, vol. 38, no. 2, pp. 6–es, 2006. [11] H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. 33, no. 01, pp. 117–128, 2011. [12] S. Auer, V. Kovtun, M. Prinz, A. Kasprzik, M. Stocker, and M. E. Vidal, “Towards a knowledge graph for science,” in 8th International Conference on Web Intelligence, Nining and Semantics, 2018, pp. 1–6. [13] C. Peng, F. Xia, M. Naseriparsa, and F. Osborne, “Knowledge graphs: Opportunities and challenges: C. peng et al.” Artificial Intelligence Review, vol. 56, no. 11, pp. 13 071–13 102, 2023. [14] S. K. Mohamed, A. Nounu, and V. Nováček, “Biological applications of knowledge graph embedding models,” Briefings in Bioinformatics, vol. 22, no. 2, pp. 1679–1693, 2021.
[15] L. Vittor, A. Noori, I. Arango, J. Polonuer, S. Rodriques, A. White, D. A. Clifton, and M. Zitnik, “Optimuskg: Unifying biomedical knowledge in a modern multimodal graph,” arXiv preprint arXiv:2604.27269, 2026. [16] S. M. Mohamed, K. S. Farah, A. M. Lotfy, K. A. Rizk, A. Y. Saeed, S. H. Mohamed, G. Khoriba, and T. Arafa, “Knowledge graphs: The future of data integration and insightful discovery,” in Advanced Research Trends in Sustainable Solutions, Data Analytics, and Security. IGI Global Scientific Publishing, 2025, pp. 99–146. [17] G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 359–392, 1998. [18] I. Stanton and G. Kliot, “Streaming graph partitioning for large distributed graphs,” in 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012, pp. 1222–1230. [19] C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic, “Fennel: Streaming graph partitioning for massive scale graphs,” in 7th ACM International Conference on Web Search and Data Mining, 2014, pp. 333–342. [20] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, “PowerGraph: Distributed graph-parallel computation on natural graphs,” in 10th USENIX Symposium on Operating Systems Design and Implementation, 2012, pp. 17–30. [21] V. A. Traag, L. Waltman, and N. J. Van Eck, “From Louvain to Leiden: Guaranteeing well-connected communities,” Scientific Reports, vol. 9, no. 1, p. 5233, 2019. [22] P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti, “Generalized louvain method for community detection in large networks,” in 11th International Conference on Intelligent Systems Design and Applications. IEEE, 2011, pp. 88–93. [23] T. Haveliwala, S. Kamvar, and G. Jeh, “An analytical comparison of approaches to personalizing PageRank,” Technical report, Stanford University, Tech. Rep., 2003. [24] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, “An optimal algorithm for approximate nearest neighbor searching fixed dimensions,” Journal of the ACM, vol. 45, no. 6, pp. 891–923, 1998. [25] L. Ma, R. Zhang, Y. Han, S. Yu, Z. Wang, Z. Ning, J. Zhang, P. Xu, P. Li, W. Ju et al., “A comprehensive survey on vector database: Storage and retrieval technique, challenge,” arXiv preprint arXiv:2310.11703, 2023. [26] Qdrant Team, “Qdrant,” 2026. [Online]. Available: https://qdrant.tech/ [27] D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin, “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web,” in 29th Annual ACM symposium on Theory of Computing, 1997, pp. 654–663. [28] J. J. Pan, J. Wang, and G. Li, “Survey of vector database management systems: J. jie et al.” The VLDB Journal, vol. 33, no. 5, pp. 1591–1615, 2024. [29] M. T. Özsu, “A survey of rdf data management systems,” Frontiers of Computer Science, vol. 10, no. 3, pp. 418–432, 2016. [30] J. Huang, D. J. Abadi, and K. Ren, “Scalable sparql querying of large rdf graphs.” Proc. VLDB Endow., vol. 4, no. 11, pp. 1123–1134, 2011. [31] B. J. Gutiérrez, Y. Shu, Y. Gu, M. Yasunaga, and Y. Su, “HippoRAG: Neurobiologically inspired long-term memory for large language models,” Advances in Neural Information Processing Systems, vol. 37, pp. 59 532– 59 569, 2024. [32] J. Wu, J. Zhu, Y. Qi, J. Chen, M. Xu, F. Menolascina, and V. Grau, “Medical graph RAG: Towards safe medical large language model via graph retrieval-augmented generation,” arXiv preprint arXiv:2408.04187, 2024. [33] H. Han, Y. Wang, H. Shomer, K. Guo, J. Ding, Y. Lei, M. Halappanavar, R. A. Rossi, S. Mukherjee, X. Tang et al., “Retrieval-augmented generation with graphs (GraphRAG),” arXiv preprint arXiv:2501.00309, 2024. [34] M. Li, S. Miao, and P. Li, “Simple is effective: The roles of graphs and large language models in knowledge-graph-based retrieval-augmented generation,” 2025. [35] J. Sun, C. Xu, L. Tang, S. Wang, C. Lin, Y. Gong, L. Ni, H.-Y. Shum, and J. Guo, “Think-on-Graph: Deep and responsible reasoning of large language model on knowledge graph,” in 12th International Conference on Learning Representations, 2023. [36] L. Luo, Y.-F. Li, R. Haffari, and S. Pan, “Reasoning on graphs: Faithful and interpretable large language model reasoning,” in International Conference on Learning Representations, vol. 2024, 2024, pp. 14 400– 14 423.
[37] Z. Guo, L. Xia, Y. Yu, T. Ao, and C. Huang, “Lightrag: Simple and fast retrieval-augmented generation,” arXiv preprint arXiv:2410.05779, 2024. [38] B. Peng, Y. Zhu, Y. Liu, X. Bo, H. Shi, C. Hong, Y. Zhang, and S. Tang, “Graph retrieval-augmented generation: A survey,” ACM Transactions on Information Systems, vol. 44, no. 2, pp. 1–52, 2025. [39] W. Zhou, Y. Yan, and Q. Yang, “Dgrag: Distributed graph-based retrieval-augmented generation in edge-cloud systems,” arXiv preprint arXiv:2505.19847, 2025. [40] M. E. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, vol. 69, no. 2, p. 026113, 2004. [41] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, 2008. [42] M. E. Newman, “Modularity and community structure in networks,” National academy of sciences, vol. 103, no. 23, pp. 8577–8582, 2006. [43] U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, vol. 76, no. 3, p. 036106, 2007. [44] M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proceedings of the national academy of sciences, vol. 105, no. 4, pp. 1118–1123, 2008. [45] U. Von Luxburg, “A tutorial on spectral clustering,” Statistics and computing, vol. 17, no. 4, pp. 395–416, 2007.
[46] B. Karrer and M. E. Newman, “Stochastic blockmodels and community structure in networks,” Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, vol. 83, no. 1, p. 016107, 2011. [47] S. Fortunato and D. Hric, “Community detection in networks: A user guide,” Physics reports, vol. 659, pp. 1–44, 2016. [48] J. Yu, Y. Tang, K. Feng, L. Liang, Q. Zhang, K. Ding, and H. Chen, “SciCUEval: A comprehensive dataset for evaluating scientific context understanding in large language models,” Scientific Data, vol. 13, no. 260, 2026. [49] P. Chandak, K. Huang, and M. Zitnik, “Building a knowledge graph to enable precision medicine,” Scientific Data, vol. 10, no. 1, p. 67, 2023. [50] G. Alanis-Lobato, M. A. Andrade-Navarro, and M. H. Schaefer, “HIPPIE v2.0: Enhancing meaningfulness and reliability of protein–protein interaction networks,” Nucleic Acids Research, p. gkw985, 2016. [51] S. Zheng, J. Rao, Y. Song, J. Zhang, X. Xiao, E. F. Fang, Y. Yang, and Z. Niu, “PharmKG: a dedicated knowledge graph benchmark for bomedical data mining,” Briefings in Bioinformatics, vol. 22, no. 4, p. bbaa344, 2021. [52] M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein, H. Butler, J. M. Cherry, A. P. Davis, K. Dolinski, S. S. Dwight, J. T. Eppig, M. A. Harris, D. P. Hill, L. Issel-Tarver, A. Kasarskis, S. Lewis, J. C. Matese, J. E. Richardson, M. Ringwald, G. M. Rubin, and G. Sherlock, “Gene Ontology: Tool for the unification of biology,” Nature Genetics, vol. 25, no. 1, pp. 25–29, 2000.