Down With The Hierarchy: The 'H' In HNSW Stands For "hubs"

Abstract

Driven by recent breakthrough advances in neural representation learning, approximate near-neighbor (ANN) search over vector embeddings has emerged as a critical computational workload. With the introduction of the seminal Hierarchical Navigable Small World (HNSW) algorithm, graph-based indexes have established themselves as the overwhelmingly dominant paradigm for efficient and scalable ANN search. As the name suggests, HNSW searches a layered hierarchical graph to quickly identify neighborhoods of similar points to a given query vector. But is this hierarchy even necessary? A rigorous experimental analysis to answer this question would provide valuable insights into the nature of algorithm design for ANN search and motivate directions for future work in this increasingly crucial domain. We conduct an extensive benchmarking study covering more large-scale datasets than prior investigations of this question. We ultimately find that a flat navigable small world graph graph retains all o

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keymunyampirwa2024down

Related papers

• The Impacts Of Data, Ordering, And Intrinsic Dimensionality On Recall In Hierarchical Navigable Small Worlds (2024)5.24
• Efficient And Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016)22.99
• Enhancing HNSW Index For Real-time Updates: Addressing Unreachable Points And Performance Degradation (2024)1.56
• From HNSW To Information-theoretic Binarization: Rethinking The Architecture Of Scalable Vector Search (2025)0.00
• Frequency-aware Graph Construction And Search For Dynamic Vector Databases (2025)0.00
• Practice With Graph-based ANN Algorithms On Sparse Data: Chi-square Two-tower Model, HNSW, Sign Cauchy Projections (2023)0.00
• High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
• HQANN: Efficient And Robust Similarity Search For Hybrid Queries With Structured And Unstructured Constraints (2022)9.76