CS Paper Radar

COMPASS: 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

cs.DB cs.DC ·submitted 2026-09-11 19:13 UTC · v1

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 COMPASS, a framework that uses a knowledge graph (KG) to determine data placement and query-time shard selection. COMPASS 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.6x more multi-hop evidence than an embedding-based baseline. On 15 HPC nodes, COMPASS sustains 7.9x 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Semord: Learned Semantic-Preserving Placement and Low-Fanout Routing for Distributed Vector Search

cs.NI ·2026-09-22 ·Shengze Wang, Yi Liu, Yifan Hua, Xiaoxue Zhang, Chen Qian
similarity 0.73
Abstract · 19 pages, 14 figures, 4 tables. Includes appendix

Vector databases are increasingly deployed in distributed settings where different users, sites, or domains maintain vector data. Existing vector databases rely on a coordinator to record which shards store which parts of the vector space and to route each query to those shards. In a decentralized setting, peers may join, leave, or move data without a trusted node tracking every change, and outdated routing information can therefore send queries to the wrong peers or require contacting many peers, reducing vector retrieval recall and increasing network latency. We present Semord, a decentralized vector search overlay system that achieves high recall by routing each ANN query to a small set of relevant peers, without relying on a centralized coordinator. Semord addresses this problem by making semantic locality routable: 1) We propose VHash to place semantically related vectors near each other in the overlay key space while avoiding load imbalance, so that each query only needs to contact a small neighborhood of peers for distributed local ANN ranking. 2) We design VecDHT, a communication protocol that maintains decentralized routing, region metadata, churn resilience, and VHash updates under membership and workload changes. Our extensive experiments on a real testbed show that Semord improves recall by more than 15% and reduces contacted peers by over 60% compared with decentralized baselines. Semord also approaches the recall and latency of a centralized oracle baseline while reducing peak peer-local ANN index memory by more than 2X. Controlled large-scale simulations further show that Semord scales across real-world embedding workloads and remains robust under churn for scoped vector retrieval as a decentralized overlay.

0.11

Graph-free Retrieval with Graph-Modified Embeddings

cs.IR cs.AI ·2026-10-13 ·Federica Santi, Vasilije Marković, Daniel Scott, Lazar Obradović
benchmark similarity 0.68
Abstract · 28 pages, 10 figures, including appendices

Dense vector retrieval can miss evidence connected through intermediate entities, while direct graph retrieval requires access to the graph at query time. We compare five offline graph-based embedding transformations and strategies for using the resulting graph-modified embeddings alongside the originals, without query-time graph access. On a synthetic professional-network benchmark with complete supporting-evidence sets, direct replacement of the original embeddings reduces evidence recovery. Multi-stage strategies improve recovery by using graph-modified embeddings to guide the search while retaining the originals for semantic relevance. On questions requiring linked facts or comparisons among candidates, the strongest configuration improves recovery by up to 25.9% relative to plain vector retrieval. It also matches baseline recovery with 40% fewer returned nodes. Controls confirm that graph information contributes beyond multi-stage retrieval alone. Across the tested methods, retrieval performance depends more on how graph-modified embeddings are used than on how they are produced.

0.15

SIMQ: A Single Graph-based Index for Multi-Vector Query

cs.IR cs.DB ·2026-11-17 ·Yifan Lu, Jiabao Jin, Xiaoyao Zhong, Peng Cheng, Xiangyu Wang +5 more
publishedcode/data similarity 0.67
Abstract · under ICDE 2027 review, 13 pages

Multi-vector retrieval models such as ColBERT achieve state-of-the-art effectiveness by representing documents as sets of token-level vectors and scoring via MaxSim, but their high computational cost limits scalability to large corpora. Existing approximate methods face fundamental bottlenecks: centroid interaction matrix approaches require computing a full matrix at every query and rely on GPU-accelerated clustering, while data-oblivious compression methods yield unstable recall that requires repeated compensation. We propose SIMQ (Single graph Index for Multi-vector Query), a framework that bridges single-vector graph indices and multi-vector retrieval through data-aware sampling-based clustering and per-token graph navigation, simultaneously bypassing all aforementioned bottlenecks. SIMQ organizes all token vectors into fine-grained clusters via data-aware sampling, builds a single graph index over cluster centroids independently of PLAID's residual representation, and approximates the MaxSim score through per-token graph search without materializing any interaction matrix or relying on GPU acceleration. We provide theoretical analysis showing that, under a manifold assumption and successful cell retrieval, data-aware partitioning has a smaller expected approximation error than a data-oblivious partition. Building on this foundation, SIMQ+ further introduces count-based scoring and a dynamic candidate set to improve robustness across varying query conditions. Experiments on five benchmarks compare recall, throughput, and construction time against several baselines, primarily on CPU; large-scale PLAID k-means centroids are built on a separate GPU machine. SIMQ has been integrated into VSAG, an Ant Group's open-source vector search library.

0.31

EAGR: Evidence-Guided Adaptive Graph Retrieval

cs.IR ·2026-11-01 ·Sonam Gupta, Vignesh P, Vishwajeet Kumar, Adnan Qidwai, Anand Eswaran +2 more
similarity 0.67
Abstract

Retrieval-Augmented Generation (RAG) for multi-hop reasoning requires retrieval to adapt as intermediate evidence reveals new information needs. Existing approaches support such retrieval through explicit graph structures or iterative query reformulation, introducing graph-construction or query-time overhead. We present Evidence-Guided Adaptive Graph Retrieval (EAGR), a framework in which accumulated evidence dynamically determines which semantic directions to explore next, and which requires no dedicated graph database and no explicit graph materialization. EAGR operates over an implicit semantic graph induced by compact passage metadata pre-ingested into a standard VectorDB. Starting from dense-retrieval seed passages, an LLM iteratively assesses accumulated evidence, identifies promising semantic directions, expands the retrieval frontier through metadata-based neighborhood lookup, and terminates once sufficient evidence has been collected. By precomputing semantic metadata, EAGR enables evidence-conditioned graph exploration without materializing an explicit graph, maintaining a dedicated GraphDB, or iteratively rewriting the query. Across three widely used multi-hop QA benchmarks, EAGR achieves the highest LLM-based answer accuracy among evaluated methods, outperforming the vanilla RAG by 17\% and strongest graph-aware baseline by 4\% percentage points averaged across three popular benchmarks HotPotQA, 2WikiMultiHopQA, and MuSiQue.

0.18

HorizANN: Elastically Scaling Vector Search with Ghost Edges

cs.DB ·2026-11-14 ·Talika Gupta, Yunqi Li, Aditya Kunte, Claire Lin, Supawit Chockchowwat +3 more
similarity 0.66
Abstract · 14 pages, 11 figures

Approximate nearest neighbor search (ANNS) is fundamental to modern data-intensive AI applications such as retrieval-augmented generation, recommendation systems, and semantic search. Among existing indexing methods, graph-based indexes emerge as the state of the art due to their superior recall-throughput tradeoffs. Scaling these indexes to multiple machines requires partitioning the data and building indexes on each. However, when new machines are added or removed, the data must be repartitioned and the indexes reconstructed from scratch, making horizontal scaling costly at billion scale. In this work, we present HorizANN, a distributed graph-based ANNS system that scales horizontally without requiring full index reconstruction. To achieve this, we introduce ghost edges, a mechanism for preserving cross-partition connectivity as partition boundaries change during repartitioning. By reusing the structural information that would otherwise be discarded during repartitioning, HorizANN avoids costly full index reconstruction. As the index grows from 100M vectors on one worker to 1B vectors on ten workers, HorizANN inserts each 100M vectors within 2.5 hours and sustains 3.4--3.5K queries per second at 0.998 Recall@10.

0.16

Federated Vector Retrieval across Heterogeneous VectorDBs

cs.DB cs.IR ·2026-11-01 ·Mintaek Lim, Sieun Hyeon, Geon Chio, Jaeyoung Do
top venuebenchmark similarity 0.66
Abstract · Accepted for publication at VLDB 2027. The manuscript contains 13 figures

Vector databases are now core infrastructure for AI retrieval systems, yet many real deployments must serve queries over multiple independently constructed vectorDBs built with different embedding models. This creates a systems problem of federated retrieval over heterogeneous vectorDBs: vectors and similarity scores are not directly comparable across embedding spaces, while fully resolving this incompatibility through corpus-wide re-embedding and re-indexing is often operationally prohibitive. Existing methods therefore face a difficult trade-off between retrieval quality, construction cost, and query throughput. We present HVMap, a lightweight compatibility layer for federated retrieval across heterogeneous vectorDBs. Instead of rebuilding databases into a unified space, HVMap learns bidirectional mappings between embedding spaces using a fuzzy contrastive loss, enabling calibrated cross-database scoring without corpus migration or index reconstruction. HVMap is system-agnostic and further scales to multi-vectorDB settings while preserving ranking fidelity through a hub-based architecture. We evaluate HVMap in open-domain, cross-domain, and scale-out settings, and also construct a new benchmark for heterogeneous cross-domain federation. Across these settings, HVMap consistently achieves a better quality--cost--throughput trade-off than baselines, achieving up to 3.59X higher nDCG@10, up to 2.01X higher query throughput, and construction time as low as 0.3% of baseline methods. These results show that HVMap makes heterogeneous vectorDB federation practical at scale.

0.37

Efficient Dense Vector Search within Knowledge Graph Content Embeddings

cs.DB ·2026-09-21 ·Benedikt Kantz, Tobias Schreck, Gianmaria Silvello
benchmark similarity 0.66
Abstract · 17 pages, 7 figures, 9 tables, under review

Knowledge graphs are a core component of today's knowledge infrastructure, supporting reasoning and anchoring knowledge systems to verifiable facts. RDF stores and SPARQL engines fulfill this function, enabling a range of retrieval and inference tasks on structured knowledge. Coupling them with Language Models (LMs) extends RAG toward neurosymbolic reasoning, where structured queries gate or re-rank generative outputs. This line of reasoning requires that SPARQL evaluation natively support tensor operations on dense embeddings, enabling multimodal querying and learned similarity-based ranking to be expressed together with graph-structural constraints. This approach is feasible only if the engine can efficiently perform dense vector search. We present QLever-Unified Indexed Vector Embedding Retrieval (QUIVER), an extension to QLever that adds native support for dense vector retrieval within RDF knowledge graphs. It implements three optimizations: engine-level registration of tensor functions, vocabulary-time parsing of JSON-encoded vectors, and a virtual SERVICE that exposes a vector index inside the query. We propose two new benchmarks: an extension of Berlin Sparql Benchmark (BSBM) with text embeddings and an extension of DBpedia with image embeddings. Against the baselines, vocabulary-time parsing alone yields median speedups of up to 41.9x on BSBM and 20x on DBpedia for single-type ranking; adding an approximate nearest-neighbor index yields speedups of 355x on BSBM and 97.8x on DBpedia. The index further makes cross-modal vector joins on DBpedia feasible in seconds, whereas all non-indexed configurations time out.

0.10

Efficiently Linking Unstructured Data for Multi-step Reasoning

cs.DB cs.AI ·2026-09-16 ·Jiaming Liang, Haydn Jones, Jacob R. Gardner, Mark Yatskar, Zachary Ives
similarity 0.66
Abstract · 23 pages, 9 figures

Modern LLMs and AI agents increasingly support data engineering workflows that integrate evidence from unstructured sources. Such pipelines typically do data retrieval, integration, and ranking before proceeding to more complex agentic reasoning or actions, e.g., for scientific discovery. The core retrieval problem in these workflows jointly executes multi-attribute filtering, multi-vector search, exact relational joins, and thresholded embedding-similarity joins. Given a planned query and monotone scoring function, our DASE query engine constructs and ranks candidate evidence tuples. It comprises (i) a multi-step reasoning query model over structured predicates, multiple vectors, and relational links; (ii) SemJI, a sparse materialized embedding-similarity join index for rare near-neighbor pairs; and (iii) a co-designed execution layer that combines predicate-aware ANN traversal, batched access, and threshold-based score aggregation. On scientific-discovery workloads, DASE retrieves candidate evidence for multi-step reasoning queries 6x to 46x faster than strong RDBMS, rerank, and vector-database baselines at comparable recall; and for tasks that require semantic-operator post-processing, DASE acts as a high-recall prefilter that makes downstream LLM evaluation both cheaper and more accurate -- e.g., on SemBench E-Commerce it improves BigQuery quality from 0.67 to 0.80 while cutting cost from $2.42 to $0.54.

0.14