Pith. sign in

REVIEW 4 major objections 7 minor 1 cited by

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

T0 review · 4 major / 7 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims HNSW's layered hierarchy can be removed for high-dimensional vector search without loss of latency or recall, while saving memory.

desk verdict Solid large-scale evidence that flat NSW matches HNSW on high-dimensional data, but the 'hierarchy is useless' claim needs a within-implementation ablation to rule out a search-engineering confound. read the letter →

arxiv 2412.01940 v3 pith:BV5GX5H3 submitted 2024-12-02 cs.LG cs.DBcs.IR

Blaise Munyampirwa , Vihan Lakshman , Benjamin Coleman This is my paper · ORCID
classification cs.LGcs.DBcs.IR
keywords approximatenearestneighborsearchHNSWnavigablesmallworldgraphshubnesshubhighwayhypothesishigh-dimensionalembeddingsgraph-basedvectordatabase
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether the layered hierarchy in Hierarchical Navigable Small World (HNSW) search is actually load-bearing. Across 13 benchmark datasets ranging from 1M to 100M vectors, the authors find that a flat navigable small-world graph, built and searched without any hierarchy, matches HNSW's median and 99th-percentile latency at equal recall while using substantially less construction memory. The paper then offers an explanation: in high dimensions, hubness makes a small set of heavily traversed "hub" nodes form a well-connected highway that routes queries to the right neighborhood, doing the work the hierarchy was designed to do. If true, vector database designs could drop the hierarchy for high-dimensional workloads with no quality loss, yielding simpler and smaller indexes.

What carries the argument

The load-bearing object is the Hub Highway Hypothesis, defined as the claim that in high-dimensional metric spaces, $k$-NN proximity graphs form a highway routing structure in which a small subset of nodes are well-connected and heavily traversed, especially early in greedy search. The paper supports it with three measurements: the node-access distribution $P_m(x_i)$ is right-skewed for $\ell^2$ distances and becomes more skewed with dimension, but not for the anti-hub cosine distance; hub nodes, identified by top-5% and top-1% access counts, form significantly denser hub-to-hub connections than non-hubs on both a two-sample t-test and the Mann-Whitney U-test; and beam-search traces show queries concentrate in hub nodes during the first 5 to 10 percent of search steps before settling into local neighborhoods. This mechanism is what carries the argument that the flat graph retains the hierarchy's function.

What would settle it

Run both algorithms on a 100M-vector, 96-plus dimensional dataset using identical construction and search code with matched SIMD and thread counts; if the flat graph's p99 latency at recall 0.95 is consistently above the hierarchical graph's beyond run-to-run noise, the central parity claim fails.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the hierarchy of HNSW is unnecessary for high-dimensional vector workloads: a flat navigable small-world graph attains essentially identical p50 and p99 latency-versus-recall curves on high-dimensional datasets, and removing the hierarchy cuts peak index construction memory by roughly 18 to 39 percent on the reported 100M-vector comparisons. This holds whether the flat graph is extracted from the HNSW base layer or constructed from scratch with no hierarchy at all. The paper attributes the redundancy of the hierarchy to the Hub Highway Hypothesis: in high-dimensional metric spaces, hubness concentrates near-neighbor co-occurrence so that a small subset of nodes becomes heavily connected and frequently visited early in search, forming an implicit routing network that replaces the explicit layered routing.

Load-bearing premise

The benchmark rests on an assumption of engineering parity between the mature hierarchical implementation and the new flat-graph reimplementation; if the two codebases differ in optimization level, the observed latency parity could reflect implementation details rather than the uselessness of the hierarchy.

Editorial extensions

If this is right

  • For high-dimensional embedding workloads, HNSW indexes can be flattened without quality loss: the paper reports essentially identical p50 and p99 latency-versus-recall curves, with 18 to 39 percent lower peak construction memory on three 100M-vector datasets.
  • Flat graphs built from scratch, with no hierarchy in construction or search, match hierarchical HNSW on the latency-recall tradeoff, so the hierarchy is not load-bearing in either phase.
  • On low-dimensional synthetic data ($d<32$), the hierarchy does provide a speedup, matching earlier studies; the paper proposes dimensionality as the practical decision criterion for choosing a flat versus hierarchical index.
  • The Hub Highway Hypothesis explains why sophisticated search initialization schemes no longer dominate: high-dimensional graphs already form fast routing through hub nodes, so the largest gains should come from link pruning and traversal design in the base graph.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not test whether the flat advantage survives on distance measures engineered against hubness, such as locally scaled distances; its own highway mechanism predicts the flat graph's edge should shrink under those measures.
  • The memory numbers suggest a practical scaling test the paper leaves open: a billion-scale flat index may fit in RAM where the paper notes a hierarchical HNSW index would need over 1.5 TB, so the natural next benchmark is whether parity persists at true billion scale.
  • The highway picture also implies that query distribution matters: if queries are drawn from a different distribution than the indexed vectors, the hub nodes that formed during construction may not be the right routing nodes, potentially restoring the value of a hierarchy; the paper does not evaluate out-of-distribution queries.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 7 minor

Summary. The paper investigates whether the hierarchical layered structure of HNSW is necessary for high-dimensional approximate nearest neighbor search. It compares hnswlib's full hierarchical search against FlatNav, a flat single-layer navigable small-world graph search implemented by the authors, across 13 benchmark datasets ranging up to 100M vectors. The reported results show essentially identical median and tail latency at matched recall, lower peak memory for FlatNav on three large datasets, and a proposed Hub Highway Hypothesis which attributes the redundancy of the hierarchy to a naturally formed subgraph of hub nodes that enables fast greedy traversal. The paper also reproduces earlier low-dimensional studies showing that the hierarchy helps only for d < 32, and includes an appendix variant where the flat graph is constructed from scratch rather than extracted from hnswlib.

Significance. If the central parity claim is correct, the paper would provide a practically important simplification of HNSW, reducing memory and engineering complexity for high-dimensional workloads, and it would challenge a widely held design assumption. The Hub Highway Hypothesis further offers a mechanistic explanation that could guide future graph-construction and traversal research. The paper's strengths include the breadth of datasets (including four 100M-scale BigANN benchmarks), the public release of the FlatNav implementation, the explicit effort to control for graph-construction differences in Appendix E, and the use of nonparametric statistical tests in the hub-connectivity analysis. The main correctness risk is that the central comparison is between two different search implementations, so the observed parity could reflect implementation optimization rather than the irrelevance of the hierarchy; this issue is load-bearing because the paper's headline conclusion is that the hierarchy provides no benefit.

major comments (4)
  1. [Section 3.2, Figures 2-6] The central claim that FlatNav and hnswlib have 'essentially identical' latency-recall performance is based on visual inspection of single runs; no error bars, repeated trials, or significance testing are reported. For p99 latency, which is known to be noisy, this level of evidence is insufficient to establish parity. Please report multiple runs with error bars or a statistical comparison of the latency distributions at matched recall.
  2. [Section 3 and Appendix E] The parity claim is established by comparing two different search implementations: hnswlib's full hierarchical search and flatnav's reimplemented flat-graph search. While the authors state in Section 3 that the same code is used to construct the indexes, the search code is not shared, and the assertion of 'engineering parity' in Appendix B is not backed by a controlled measurement. Without a within-implementation ablation—for example, running hnswlib with all nodes in layer 0 and comparing against the same hnswlib with the full hierarchy—the result cannot distinguish 'the hierarchy provides no benefit' from 'flatnav's search is better optimized.' This is the load-bearing comparison for the paper's central claim.
  3. [Section 4.3-4.4, Figure 8] Hub nodes are identified as the top 1% or 5% of the node access count distribution Pm(xi) computed from the same 10,000-query workload that is then used in Section 4.4 to show that queries visit hub nodes early in search. This selection is partly circular: the nodes are definitionally the most frequently visited overall, which biases the early-visit analysis in Figure 8. The highway-utilization claim should be tested with hubs defined by an independent source of hubness (e.g., k-occurrence computed on a held-out sample of data points or on a separate query set) and evaluated on queries not used for hub identification.
  4. [Section F.2, Table 6] The reported memory savings (38-39% on BigANN and Yandex DEEP, 18% on Microsoft SpaceV) compare two different codebases, hnswlib and flatnav. The authors acknowledge that 'differences in code may account for a significant part of the peak memory usage differences,' which means the memory-savings component of the central contribution is not established by the presented measurements. A same-codebase comparison of full hnswlib versus a layer-0-only hnswlib, or a direct measurement of the hierarchy's incremental memory within hnswlib, would quantitatively isolate the memory cost of the hierarchy.
minor comments (7)
  1. [Abstract] The phrase 'small world graph graph' contains a duplicated word and should be corrected.
  2. [Appendix B] The text refers to 'HSNW' in one place, which appears to be a typo for 'HNSW'.
  3. [Section D.2] The phrase 'hug-highway hypothesis' should read 'hub-highway hypothesis'.
  4. [Section F.1] The word 'sythetic' is misspelled and should be 'synthetic'.
  5. [Table 5] The table lists the IID Normal dataset rows twice with identical dimensionality entries; please remove the duplicate.
  6. [Table 4] DEEP1B is listed as 10M points, while the text discusses 100M-scale BigANN datasets; please clarify whether this is a 10M subset or a separate entry.
  7. [Section 3] The statement 'we fix the implementation in our experimental design such that the same code is used to construct the indexes' is potentially misleading because the search implementations differ; please clarify that construction is shared but search is compared across two different codebases.

Circularity Check

1 steps flagged · score 5.0 of 10

Hub Highway evidence is partly self-referential (hubs defined by query access counts, then shown to be visited by those same queries), while the main latency-parity benchmark is independently grounded.

  1. self definitional [Section 4.3-4.4 (Hub Highway Hypothesis, hub identification and traversal analysis)]
    "We identify hub nodes as those that fall into the top percentile of the empirical node access distribution Pm(xi). We use 95th and 99th percentile of node access counts as our threshold. ... We use the hub node assignment heuristic discussed in section 4.3 to label h(xi) each of these nodes as hubs / non-hubs. ... By averaging this value over all queries, we can plot the likelihood of visiting a hub as the search progresses."

    Hubs are defined by the empirical node access distribution Pm(xi) measured over the same query set that is later used to measure hub visitation. Therefore the finding that 'queries tend to concentrate in the highway structures early in search' is partly true by construction: the nodes selected as hubs are precisely those with the highest total access counts over those queries, so they will be over-represented in any per-bin visitation average regardless of the highway mechanism. The paper does not use its own formal metric-space hubness measure N(x) from Section 4.1 (which would require O(n^2) k-occurrence counts), nor a held-out query set, nor a base-rate comparison under the top-percentile selection rule.

full rationale

The central latency/recall claim that a flat navigable small-world graph matches HNSW is independently benchmarked against hnswlib, and Appendix E repeats the comparison with a flat graph built from scratch, so that claim does not reduce to a fit or a definition. The circularity concern is confined to the explanatory Hub Highway analysis: hub nodes are operationalized as the top percentiles of the query-access distribution, and then the same distribution is used as evidence that queries visit hubs, making part of the hypothesis self-referential. The paper also cites Coleman et al. 2022, a prior work by a co-author, as related work, but that citation is not load-bearing because the main benchmark is conducted in this paper. The cross-library search-implementation difference between hnswlib and flatnav is a real experimental confound and a correctness risk, but it is not a circularity. On balance, the paper's main ablation is sound, while one of its three supporting claims for the Hub Highway Hypothesis is partially true by construction, giving a moderate circularity score of 5.

Assumptions & free parameters 2 free parameters · 3 assumptions · 1 invented entities

The central parity claim rests on the benchmark setup and the engineering-parity assumption. The Hub Highway hypothesis rests on the access-count proxy for metric hubness, hand-chosen analysis thresholds (P95/P99, bin size 30), and the same query set used both for labeling hubs and for evaluating highway behavior.

free parameters (2)
  • hub_node_threshold = 95th and 99th percentiles of node access counts
    Hand-selected cutoffs define hub labels in Section 4.3; no sensitivity analysis or data-driven justification is provided.
  • traversal_bin_size = 30
    Fixed bin size in Section 4.4 used to compute hub prevalence over search progress; the choice is arbitrary and not varied.
assumptions (3)
  • ad hoc to paper Node access count distribution Pm(xi) is a valid proxy for metric-space hubness on real datasets.
    The paper cannot compute the k-occurrence distribution on real data due to O(n^2) cost (Appendix F.3) and only verifies the connection on synthetic data; it assumes the same relationship holds for real datasets.
  • domain assumption hnswlib and flatnav have performance engineering parity.
    The central parity conclusion rests on wall-clock latency comparisons between two separate implementations; the paper asserts parity in Section 3 and Appendix B but provides no step-level measurement or controlled implementation.
  • domain assumption HNSW as implemented in hnswlib is a faithful representative of the HNSW algorithm.
    All hierarchical results are obtained with hnswlib; the paper treats this library as canonical, which is reasonable but still an implementation-level assumption.
invented entities (1)
  • Hub Highway
    purpose: Explains why flat NSW graphs match hierarchical HNSW in high dimensions: a small set of well-connected hub nodes routes queries early in search.
    The Hub Highway is defined operationally through node access counts from the same query set used to evaluate it; no out-of-sample prediction or independent measurement is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs"." pith.science (2026). https://pith.science/paper/BV5GX5H3

@misc{pith2026241201940,
  author       = {Pith},
  title        = {Pith review of: Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs"},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BV5GX5H3}},
  note         = {Machine review of arXiv:2412.01940}
}
read the original 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 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.

Figures

Figures reproduced from arXiv: 2412.01940 by the authors.

Figure 1
Figure 1. We hypothesize that, in high dimensions, graph-based ANN indexes naturally form a “highway-feeder” structure, where a small subset of nodes and edges are easily reached, well-connected, and heavily traversed. initial coarse graph layers allow for efficiently identifying the neighborhood of similar points in the collection through fewer overall comparisons. Despite its popularity, HNSW has notable scalability is￾sues… view at source ↗
Figure 2
Figure 2. p50 Latency vs. Recall. FlatNav performs nearly identi￾cally to HNSW [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. p99 Latency vs. Recall. FlatNav performs nearly identi￾cally to HNSW. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: p50 Latency vs. Recall. FlatNav performs nearly identi￾cally to HNSW [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: p99 Latency vs. Recall. FlatNav performs nearly identi￾cally to HNSW. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: p50 and p99 Latency vs. Recall for HNSW and FlatNav over GloVe datasets [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
Figure 7
Figure 7. Figure 7: Log-normalized Node access count distribution Pm(xi) for datasets using angular (left) and l2 (right) distances. part of our argument, we require a formal characteriza￾tion of hubness. Following (Radovanovic et al., 2010), let x, x1, . . . , xn be vectors drawn from th…
Figure 8
Figure 8. Figure 8: Highway nodes allow queries to traverse the graph faster. 4.5. Discussion Our sequence of experiments provide substantial evidence supporting the Hub Highway Hypothesis. Although it has long been established that the hubness phenomenon nega￾tively affect common applica…
Figure 9
Figure 9. Figure 9: Median Latency vs. Recall of HNSW and FlatNav across dimensions d = 4, 8, 16, 32. We observe that the hierarchical structure accelerates search only when d < 32, matching the find￾ings of (Lin & Zhao, 2019). Our results demonstrating a significant advantage with HNSW o…
Figure 12
Figure 12. Figure 12: Log-normalized node access count distribution Pm(xi) for ℓ2 datasets along with MSMARCO embeddings. generated by LLMs. These findings suggest that the routing behavior of hub nodes is not an artifact of synthetic data or benchmark con￾struction, but a general phenomen…
Figure 10
Figure 10. Figure 10: The p50 Latency vs Recall relationship between HNSW and FlatNav (constructed from scratch) is identical to the rela￾tionship between HNSW and FlatNav (base layer extracted from HNSW) shown in [PITH_FULL_IMAGE:figures/full_fig_p016_10.png]
Figure 11
Figure 11. Figure 11: The p50 Latency vs Recall relationship between HNSW and FlatNav (constructed from scratch) is identical to the rela￾tionship between HNSW and FlatNav (base layer extracted from HNSW) shown in [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Artifact Sharing for Information Retrieval Research

    cs.IR 2025-05 accept novelty 6.0 of 10

    A PyTerrier-integrated system that serializes IR artifacts into a portable file format and supports upload and download across multiple hosts, including HuggingFace, Zenodo, and CIFF Hub.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages · cited by 1 Pith paper

  1. [3]

    Data generation

    dataset, a widely-used retrieval benchmark compris- ing millions of real-world queries and documents. Data generation. We encode all training split queries in MSMARCO using the all-MiniLM-L6-v2 model from the SentenceTransformers (Reimers & Gurevych, 2019) library. This yields 384-dimensional vector representations. Using these embeddings, we construct a ...

    work page 2019

  2. [2016]

    and a subsequent 2019 paper from (Lin & Zhao,

    work page 2019

  3. [2019]

    small-world

    that found limitations with the hierarchical compo- nent of HNSW. As we discussed in the previous section, these prior works possess limitations in experimental de- sign, scope of benchmarking datasets, and a lack of analysis into understanding the results, which motivates our work in this paper. Nevertheless, we use these prior studies as a starting poin...

    work page 2016

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.