CS Paper Radar

Modular and Efficient Approximate Nearest Neighbors Search with Vectorium and kANNolo

Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini

cs.IR cs.DB ·submitted 2026-11-02 20:30 UTC · v1
code/data

Abstract

Approximate Nearest Neighbors (ANN) search over neural embeddings powers modern retrieval systems such as Retrieval-Augmented Generation. Embeddings come in three representations (dense, sparse and multi-vector), and efficient search combines an index structure, a similarity function and a quantization scheme. Existing libraries fix one combination, hard-code each one separately, or factor only one side of the problem, and none covers all three representations. We present Vectorium and kANNolo, two open-source Rust libraries that split this design space into a data-management layer and an indexing layer. Vectorium abstracts the vector, the distance function, the quantizer and the dataset independently, and provides 11 encoders, from 32-bit floats to sub-bit codes. On top of it, kANNolo implements Hierarchical Navigable Small-World (HNSW) graph and Inverted Vector File (IVF) indexes that are generic over representation, encoder and metric, and a two-stage index that composes any first-stage index with any rescoring dataset. Since every combination is specialized at compile time, this modularity adds no run-time overhead, and the resulting indexes reach state-of-the-art performance: our Product Quantization matches Faiss in accuracy at competitive speed, our RaBitQ and HNSW match or outperform their reference implementations, and our IVF outperforms Faiss. Against six dense and five sparse systems on seven public collections, our indexes give the best memory-throughput trade-off on dense data in 9 of 12 collection-accuracy pairs and perform well on out-of-distribution queries. On sparse data, the systems built on Vectorium lead on all three collections, with Seismic and SeismicWave the fastest and kANNolo's indexes the most compact.

Comment
39 pages, 11 figures, 17 tables. Submitted to Information Systems. Code and data: https://github.com/TusKANNy/papers_reproducibility/tree/main/information-systems-vectorium-kannolo

Closest papers

Nearest neighbours by meaning across the whole index.

GINGER: Spicing Up Graph-Based Vector Search

cs.IR cs.DC ·2026-11-05 ·Daniel Salwasser, Lars Gottesbüren, Laxman Dhulipala, Jakub Łącki, Guy Blelloch +5 more
code/data similarity 0.74
Abstract

We present \textsc{Ginger}, a state-of-the-art open-source C++ library for graph-based approximate nearest neighbor search (ANNS). We developed \textsc{Ginger} at Google to push the speed and memory efficiency of graph search on large and high-dimensional embedding datasets. \textsc{Ginger} surpasses existing ANNS libraries with regards to query throughput and indexing time while matching the memory footprint of the most space-efficient competitors. \textsc{Ginger} builds upon recent advances in proximity graph construction (PiPNN) and vector quantization (TurboQuant). We introduce Nested TurboQuant (NTQ), a two-level quantizer which supports low precision graph navigation and high precision reranking in a single code. This representation achieves near floating point precision with $2.6\times$ less memory. We also compress the size of our proximity graphs by up to $2.5\times$ without impacting query throughput. We combine graph reordering with a new lossless compression codec called AdaptiveGap, which builds upon StreamVByte. At $95\%$ recall, \textsc{Ginger} speeds up query throughput by an average of $1.8\times$ over each dataset's fastest competitor and by at least $2.3\times$ over any single library. This lead grows to $2.9\times$ over compact libraries on high-dimensional embeddings.

0.26

A Comprehensive Empirical Evaluation of Vector Database Systems for Approximate Nearest Neighbor Search: Performance, Quality, and Resource Trade-offs

cs.IR ·2026-08-13 ·Ashen Rashmiks, Tiroshan Madushanka
code/data similarity 0.69
Abstract

Vector databases have emerged as critical infrastructure for modern artificial intelligence applications, particularly retrieval-augmented generation (RAG), semantic search, and recommendation systems. Despite their growing importance, there remains a significant gap in comprehensive, reproducible benchmarks that jointly evaluate retrieval quality, query latency, throughput, and resource utilization. We present a systematic empirical evaluation of seven prominent vector database systems: FAISS, Qdrant, Milvus, Weaviate, Chroma, pgvector, and LanceDB. Our methodology spans six diverse datasets, from classical computer-vision descriptors (SIFT, GIST) to transformer-based text embeddings (MS MARCO, GloVe), encompassing over 4 million vectors at dimensionalities from 96 to 960. We measure 15 metrics spanning retrieval quality (Recall@K, Precision@K, MRR, NDCG@K, Hit Rate@K), query performance (latency percentiles, QPS, cold-start latency), and resource consumption (index build time, memory, storage). On SIFT1M, FAISS achieves the highest single-node throughput (866 QPS) but lacks database operational features; Weaviate provides the best out-of-the-box recall (> 99%); Qdrant offers the best latency among full databases (4.55~ms median); and LanceDB trades retrieval quality for substantially faster index construction. We derive system-selection guidelines for practitioners and release our benchmarking framework as open-source software.

0.20

NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction

cs.DB cs.IRcs.LG ·2026-08-15 ·Xingqiao Wang, Zi Wang, Xiaowei Xu
code/data similarity 0.68
Abstract · 34 pages, 9 figures

Building approximate nearest neighbor (ANN) indexes at billion scale is often dominated by expensive global clustering or graph construction, making time-to-index a first-order systems concern. We present NeuRoute, a learned hashing index that turns short binary codes into an effective routing primitive for large-scale vector search. NeuRoute trains a lightweight neural network encoder with a selective similarity-preserving objective to produce well-balanced binary addresses. During construction, NeuRoute organizes vectors into buckets by their codes and performs bucket-local clustering in the encoder's low-dimensional space to form centroids. At query time, NeuRoute exploits the encoder logits as an uncertainty signal: it uses deviation-to-threshold scores to prioritize uncertain-bit perturbations for query-adaptive multi-bucket probing, scores bucket-local centroids by their distances to the query to form a compact candidate cluster set, and applies centroid-stage gating with heap-quality-driven early stopping to prune low-value clusters before exact refinement. On billion-scale benchmarks, NeuRoute achieves strong accuracy-throughput trade-offs with fast index construction: on BigANN-1B it reaches $90.3\%$ Recall@10 at 2,414 QPS and is $1.7\times$ faster than OPQ+IVF-PQ (refine) at comparable accuracy, while completing end-to-end training+construction in under an hour on both BigANN-1B and Deep1B-1B. These results show that logit-guided neural routing can make hashing competitive as a lightweight ANN indexing framework at billion scale. Source code and artifacts are available at https://github.com/XingqiaoWang/NeuRoute.

0.30

UBASE: An AI Search Engine for Trillion-Scale Vector Data Management at ByteDance

cs.DB ·2026-08-31 ·Yao Tian, Yuncheng Lu, Liyao Xiong, Yuming Xu, Hao Zhang +7 more
published similarity 0.67
Abstract · ATC26 UBASE with Appendix

Since 2016, UBASE has been the foundation of ByteDance's search infrastructure, scaling to more than 7,000 clusters and 300 PB of indexed data. Driven by the demands of AI workloads, UBASE has evolved from a text search engine into a unified AI search system supporting vector retrieval, lexical matching, and predicate filtering. Its largest deployment indexes nearly one trillion high-dimensional vectors. This scale exposes two central bottlenecks in AI-era retrieval: memory-intensive graph-index construction under sustained ingestion, and the prohibitive cost of keeping vector indexes entirely in memory. UBASE addresses these bottlenecks with two techniques. First, it introduces a quantization-aware vector kernel based on SymRaBitQ, a new symmetric quantization scheme with tight theoretical guarantees that allows index construction to run directly in the quantized space accurately and efficiently without retaining a copy of full-precision vectors. Second, it provides a hybrid storage engine that supports memory-resident, hybrid, and SSD-resident deployments, with fine-grained record-level caching to trade memory for latency under operational control. On large-scale benchmarks, UBASE improves throughput by up to 3x, reduces indexing memory by 80%, and lowers serving cost by up to 99.4% compared with prior systems, while supporting trillion-vector scale, write-heavy or latency-sensitive workloads in production.

0.31

Exploiting Residual Reachability for Cross-Model Migration of Graph-Based Indexes in Approximate Nearest Neighbor Search

cs.DB ·2026-09-19 ·Baoyuan Gu, Xiaoyao Zhong, Jiabao Jin, Peng Cheng, Wangze Ni +3 more
similarity 0.67
Abstract · VLDB 2027 under review

Approximate nearest neighbor search (ANNS) underpins large-scale vector retrieval in search, recommendation, and retrieval-augmented generation. Graph-based indexes have demonstrated state-of-the-art search performance for ANNS. They connect each corpus vector to a small set of nearby or navigationally useful vertices and answer queries by traversing the resulting graph. Because these edges are selected using construction-time distances, the graph index is tied to the embedding model. Re-encoding a corpus with a new model may change distances and neighborhoods of the vectors. Reconstructing the graph for the new embedding vectors incurs substantial construction cost and delays deployment. When the embedding model changes, we observe a phenomenon in the old graph index that we call residual reachability. Specifically, although derived from different models, the vectors describe the same underlying objects and often retain part of their similarity structure. These shared relations are reflected in the connectivity of the old graph index, leaving many exact new-model neighbors reachable within a few hops in the old graph index. Motivated by this observation, we develop an index-migration approach that utilize the residual reachability in the old graph index to faster construct the new graph index for the new embedding vectors. Our method, Drift-Guided Migration (DGM), provides two migration paths. DGM-Local performs parallel shallow expansion over the inherited graph index and screens second-hop candidates with packed position sign codes before exact evaluation. DGM-Search uses hop-bounded beam traversal to explore beyond shallow expansion. Across eight text and image migrations, our DGM methods can achieve up to 17.43 times speedup on constructing the new graph index than the fastest degree-matched reconstruction method while keeping competitive recalls.

0.06

KatoANN: Enabling Near-Exact Vector Search at the Speed of Lossy Scans with CPU Matrix Engines

cs.DB cs.AR ·2026-10-20 ·Soobin Cho, Gyuyeong Kim
similarity 0.66
Abstract

Distance scans in partition-family approximate nearest-neighbor (ANN) search are typically limited by memory bandwidth. Existing systems therefore improve throughput by reading fewer bytes per candidate, often at the cost of recall. We present KatoANN, a CPU ANN search system that removes this tradeoff by batching distance scans on Intel AMX, a CPU matrix engine. Batching allows multiple queries to reuse each fetched vector code, shifting the scan from memory-bound to compute-bound and enabling near-exact distances at the speed of a lossy scan. KatoANN stores each vector once as a 16-bit SQ16 code split into high- and low-byte planes. Its adaptive rank-then-refine scan first ranks all candidates using only the high byte, then refines a small survivor set using the full-byte code. Both stages use the same representation, avoiding a second copy of the raw vectors. Experiments across diverse high-dimensional workloads show that KatoANN is the fastest partition-family ANN search system in our evaluation throughout the high-recall range.

0.24

Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search

cs.IR ·2026-10-27 ·Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico +3 more
top venuecode/data similarity 0.66
Abstract · 7 pages, 5 figures, Accepted at CIKM 2026. Code: https://github.com/TusKANNy/kannolo. Reproducibility: https://github.com/tusKANNy/papers_re…

Graph-based Approximate Nearest Neighbor (ANN) indexes, such as HNSW, are the backbone of modern vector search. However, their massive memory footprint creates a severe infrastructure bottleneck. While vector quantization is widely adopted to reduce the memory required to store data vectors, the graph's edge structure increasingly dominates total memory usage. Compressing these adjacency lists for online search presents a critical system challenge: because decompression occurs during query processing, i.e., while navigating the graph, memory savings cannot come at the expense of query latency. In this paper, we present a compression technique explicitly tailored for live HNSW routing. By applying offline graph permutations to artificially induce structural locality, we enable the use of SIMD-accelerated integer compressors, such as Stream VByte, for rapid on-the-fly decompression. Evaluated across diverse real-world workloads, we significantly outperform the current state of the art in both compression ratio and query latency. Our experimental results show that we achieve compression ratios up to 52.7% with negligible penalties in latency compared to the uncompressed baseline. Furthermore, our technique has been effectively deployed in production at eBay, achieving up to 44.3% reduction in edge storage with no degradation in query latency.

0.73

RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search

cs.LG cs.IR ·2026-08-31 ·Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato, Jiri Isa, Igor Ginzburg
benchmark similarity 0.65
Abstract · 14 Pages, 3 Figures, Preprint

By introducing RSLM (Rotated Scaled Lloyd-Max), a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension, we reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system, while reducing its complexity and keeping or improving recall across multiple benchmark datasets. State-of-the-art systems filter candidates using coarse partitions, approximately score them to narrow the set, and then rescore the best with higher precision representations (often >=8 bits per dimension). Our relativized codecs can bring this down to 2--4 bits per dimension. We use the properties of the ANN system to encode residual vectors instead of full vectors, both for the approximate scoring phase and the rescoring phase. Since Maximum Inner Product Search (MIPS) is very sensitive to vector norms, we correct the $L_2$ norms of quantized vectors. Our major innovation is that we correct the $L_2$ norm of the final reconstructed vector rather than just the residual. Our rescaling replaces more complicated schemes, such as Anisotropic loss. The residualization scheme gives us a more favorable quality vs size trade-off than generic quantization methods. Our high-performance implementation leverages a block-wise cascaded Fast Walsh-Hadamard Transform (FWHT) with linear-like complexity, AVX SIMD-optimized codebooks, and a steganographic encoding of scaling factors for perfect cache-line alignment.

0.36