Boosting Accuracy and Efficiency for Vector Retrieval with Local Scaling Graph

Vector database systems have been gaining more and more attention in recent years with the prevalence of Large Language Models. As the most important algorithmic component behind vector database systems, nearest neighbor search has been studied for decades and various approaches are proposed for efficient vector retrieval. Among these proposals, the graph-based search paradigm is able to achieve desirable accuracy-efficiency tradeoff, and thus has been widely used in many industrial vector retrieval engines. In this paper, however, we claim that its efficiency is largely handicapped by two unnoticed performance issues - accuracy saturation and long-tail queries, especially when the number of links is limited. Through both empirical and theoretical analysis, we identify that the existence of antihubs is the root cause of these performance limitations. To mitigates the negative impact of antihubs, we propose a highly efficient graph-based vector retrieval framework named Local Scaling Graph (LSG) by introducing more incident edges for them in a systematic way. We conduct comprehensive experiments using four state-of-the-art algorithms, i.e., HNSW, NSG, DiskANN and HNSWPQ, over a collection of 12 real-world datasets to validate the effectiveness and broad applicability of LSG. Empirical results show a speedup of up to two orders of magnitude over the state-of-the-art algorithms for approximate nearest neighbor search.