about
The hierarchy in HNSW is not necessary in high dimensions (arxiv.org)
5 points by blaise-muhirwa on Feb 15, 2025 | hide | past | pdf | 1 comment on HN

In plain words: They tested whether the layered shortcut graph for similarity search is needed, and found a no-layer graph matches its speed and accuracy on high-dimensional data with less memory. The layers help little because a few heavily connected hub points form a highway that guides searches.

Abstract · Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs"

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 of the benefits of HNSW on high-dimensional datasets, with latency and recall performance essentially \emph{identical} to the original algorithm but with less memory overhead. Furthermore, we go a step further and study \emph{why} the hierarchy of HNSW provides no benefit in high dimensions, hypothesizing that navigable small world graphs contain a well-connected, frequently traversed ``highway" of hub nodes that maintain the same purported function as the hierarchical layers. We present compelling empirical evidence that the \emph{Hub Highway Hypothesis} holds for real datasets and investigate the mechanisms by which the highway forms. The implications of this hypothesis may also provide future research directions in developing enhancements to graph-based ANN search.

Blaise Munyampirwa, Vihan Lakshman, Benjamin Coleman
arXiv:2412.01940 · cs.LG, cs.DB, cs.IR · submitted Dec 2, 2024 · updated Jul 3, 2025
abstract · pdf · html · 17 pages

add comment on HN
Also discussed: Jul 2026 (2 points, 0 comments)

I am a co-author on the paper. Here is the link to the codebase: https://github.com/BlaiseMuhirwa/flatnav. I'm happy to discuss our work further and answer any questions.