A Density-Aware Hybrid Routing Architecture for Scalable Vector Databases

Abstract

Approximate Nearest Neighbor (ANN) search at scale exposes a structural trade-off between routing accuracy, memory footprint, and query latency. Graph-based indices such as HNSW provide high recall but incur significant memory overhead due to full-dataset connectivity, while centroid-based IVF variants remain memory-efficient yet degrade under highdimensional, non-convex cluster manifolds. This trade-off forces system designers to choose between recall and storage cost, and no existing single-index design resolves both simultaneously at scale. The need for an index that delivers graph-level recall at IVF-level memory cost therefore motivates this work. We present a density-aware hybrid indexing architecture that explicitly decouples routing from storage. The system extracts manifold representatives via a robust Lloyd refinement and constructs a lightweight HNSW graph over this reduced set, preserving topological routing precision while avoiding fullgraph memory costs. Candidate selection is performed through a dual-path routing mechanism combining geometric centroids and density-aware graph traversal. The search pipeline then diverges into two execution regimes: (1) an uncompressed, SIMD-optimized L2 path achieving hardware-bound latency, and (2) a compressed OPQ-based residual reconstruction path for memory-constrained deployment. On SIFT1M, the uncompressed configuration achieves 0.09 ms/query with 0.974 Recall@10, while the 32-byte/vector OPQ configuration attains 0.341 ms/query with 0.997 Recall@10. Integrated into a gRPC scatter-gather framework, the distributed system sustains 0.9975 Recall@10 across sharded partitions. These results demonstrate that density-aware routing enables graph-level recall with IVF-level storage cost, providing a scalable foundation for high-dimensional vector retrieval.