Adaptive index traversal for multi-vector top-K search

Abstract

With the rapid advancement of deep learning and large language models, modern applications increasingly require sophisticated vector similarity search capabilities across multiple vectors of different dimensions. Database requirements have evolved beyond simple single-vector storage and retrieval to support complex multi-vector queries that combine similarities from multiple vector embeddings with numerous scalar filters. However, many existing databases either lack support for multi-vector top-K queries or rely on inefficient or best-effort methods, making them unsuitable for large-scale applications that demand both low latency and high recall.

Driven by this challenge, we present an adaptive index traversal framework specifically designed to efficiently handle multi-vector search through a traversal scheduler and asynchronous processing pipeline. Building upon this framework, we further implement RoXDB, a vector database optimized for multi-vector search that utilizes RocksDB as its storage backend and combines data parallelism and task parallelism for efficient processing. Using RoXDB as a platform, we compare our adaptive index traversal framework against other popular multi-vector index search strategies. Our evaluation shows that our framework outperforms these baselines, delivering lower latency while maintaining higher recall rates.