Pith. sign in

REVIEW 6 major objections 5 minor 19 references

Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization

T0 review · 6 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read HNSW++ outperforms the original HNSW on both accuracy and speed: recall rises by 18% on NLP tasks and up to 30% on CV tasks, construction time drops by up to 20%, and inference speed is maintained.

desk verdict Plausible incremental improvement over HNSW with two genuinely new mechanisms, but the headline 'no trade-offs' claim is undercut by the omitted LID precomputation cost and an unjustified spatial-splitting assumption. read the letter →

arxiv 2501.13992 v2 pith:NQBXOB7S submitted 2025-01-23 cs.LG cs.AI

Hy Nguyen , Nguyen Hung Nguyen , Nguyen Linh Bao Nguyen , Srikanth Thudumu , Hung Du , Rajesh Vasa , Kon Mouzakis This is my paper · ORCID
classification cs.LGcs.AI
keywords approximatenearestneighborsearchHNSWlocalintrinsicdimensionalitydual-branchgraphskipbridgesconstructionhigh-dimensionalrecalloptimization
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

The paper sets out to show that two known weaknesses of Hierarchical Navigable Small World graphs—greedy search falling into local optima and per-layer traversal that fails to reach logarithmic complexity—can be fixed together rather than traded off. It proposes HNSW++, which builds two parallel branches, inserts high-LID outlier nodes into upper layers, and adds skip bridges that jump to the base layer when a LID-distance condition holds. Across six datasets the authors report recall improvements of 18% on NLP data and up to 30% on vision data, construction time reductions up to 20%, and inference speed essentially unchanged. The paper concludes that HNSW++ is a drop-in replacement for HNSW with no observed trade-offs.

What carries the argument

The central mechanism is a modified HNSW graph with three components: two parallel branches created by alternating node insertion by index, insertion guided by normalized Local Intrinsic Dimensionality (LID), and LID-threshold skip bridges. LID estimates local sparsity via the maximum-likelihood formula over k-nearest-neighbor distances; high-LID nodes are assigned to upper layers to improve inter-cluster connectivity. Skip bridges implement a Jump function that sends the search directly to layer 0 when the entry point's LID exceeds T and its distance to the query is below epsilon. These components together are what the paper credits for reducing local minima, cutting construction work roughly in half, and making layer traversal cheaper.

What would settle it

Build HNSW++ on the same dataset twice, once with the original insertion order and once with randomly shuffled order, comparing recall and the overlap between the neighbor sets returned by the two branches. If shuffling preserves the gains and the two branches return nearly identical sets, the claimed spatial division by insertion index is not the operative mechanism.

Watch

Extended reading notes

Core claim

The central claim is that HNSW++ dominates the original HNSW on both accuracy and speed. The dual-branch structure lets the search start from two entry points and explore two distinct regions, reducing the chance of being trapped in a local minimum; LID-based insertion places high-LID points in upper layers to bridge clusters; and skip bridges, triggered when a node's normalized LID exceeds a threshold and the distance to the query is small, bypass intermediate layers. In experiments on GLOVE, SIFT, RANDOM, DEEP, GIST, and GAUSSIAN, the authors report that HNSW++ outperforms the original HNSW and several established ANN libraries, with recall improving 18% in NLP tasks and up to 30% in CV tasks, construction time reduced by up to 20%, and inference time maintained. Ablation results rank LID-based insertion as the largest contributor, followed by the dual-branch structure and the skip bridges. The authors state that they observed no trade-offs.

Load-bearing premise

The load-bearing premise is that splitting the dataset into two branches by insertion index actually separates spatial regions, so the two greedy searches explore genuinely different parts of the graph; if insertion order carries no geometric meaning, the dual-branch mechanism may just be two correlated restarts.

Editorial extensions

If this is right

  • Practitioners using HNSW could switch to HNSW++ and expect better recall at the same query speed, with faster graph construction.
  • Because LID is computed offline, the LID-based insertion rule can be layered onto other graph-based ANN indexes without changing their online search step.
  • The dual-branch construction suggests that per-insertion search cost should scale with half the dataset, which matters more as datasets grow.
  • The skip-bridge threshold gives a single knob that mainly trades inference latency against number of skips, with accuracy largely unaffected across tested datasets.

Reading between the lines

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

  • Editorial inference: a shuffle test of insertion order would isolate whether the dual-branch gain comes from spatial separation or simply from running two independent greedy searches; the paper does not report such a test.
  • Editorial inference: since the ablation shows LID-based insertion contributes most, a single-branch HNSW with only LID-aware insertion may capture most of the recall improvement with less engineering complexity.
  • Editorial inference: the skip-bridge rule combines sparsity (LID) and proximity (epsilon), so a natural testable extension is an adaptive threshold that depends on local layer density or query difficulty rather than a fixed T.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

6 major / 5 minor

Summary. The paper proposes HNSW++, a modification of the Hierarchical Navigable Small World (HNSW) algorithm that adds a dual-branch graph structure, LID-based node insertion, and LID-threshold skip bridges. The authors claim that HNSW++ improves recall by 18% on NLP tasks and up to 30% on CV tasks, reduces construction time by up to 20%, maintains inference speed, and exhibits no trade-offs relative to the original HNSW. The method is evaluated on six datasets of 10,000 points each with 1,000 queries, comparing against FAISS, NMSLIB, PyNNDescent, and Annoy, and is accompanied by an ablation study separating the effects of the multi-branch structure, LID-based insertion, and skip-layer mechanism.

Significance. If the stated results hold, HNSW++ would be a practically valuable drop-in improvement to a widely used ANN method, and the LID-driven insertion idea is a plausible direction for improving cluster connectivity. The ablation study is a useful decomposition of the proposed components, and the use of ground-truth nearest neighbors for recall avoids circularity in the accuracy evaluation. However, the current evidence is not sufficient to support the headline no-trade-off claim: the construction-time comparison omits the mandatory LID precomputation cost, the central geometric justification for the dual-branch split is unsupported, and the complexity analysis is asserted rather than derived. The empirical scale and lack of error bars further limit confidence in the claimed improvements.

major comments (6)
  1. [§3.5.2, §4.1, Abstract] The construction-time comparison excludes the cost of computing LID values, despite LID being a required input to HNSW++. Section 3.5.2 states 'Assuming the LID values are provided beforehand,' and Section 4.1 reports that LID was computed via MLE over exact k-NN with efConstruction=128. For a 10,000-point index this is a substantial preprocessing step, so the up-to-20% construction-time reduction in Section 4.3 is not an end-to-end claim. The authors should report total wall-clock construction time including LID computation, or explicitly restrict the claim to graph-construction time after LID preprocessing; otherwise the abstract's 'construction time reduced by up to 20%' and 'no trade-offs' statements are not supported.
  2. [§3.2, Eq. (1)] The claim that partitioning nodes by insertion index divides the data into spatially distinct regions is unsupported. Section 3.2 states that splitting by 'the index of the inserted nodes' means 'spatial regions are divided into different branches,' but insertion order has no inherent geometric meaning. Without a geometric separation, the dual-branch search is simply running two searches over two arbitrary halves of the dataset, and the proposed mechanism for mitigating local minima is not established. The authors should provide evidence of spatial separation (e.g., overlap statistics or per-branch recall) or modify the algorithm and its justification.
  3. [§3.5.1, Eq. (4)] The complexity reduction to L_total·(1−P_skip) is asserted rather than derived. P_skip is controlled by thresholds T and epsilon and is not shown to be independent of layer or query; the analysis does not establish that expected traversal is indeed L_total·(1−P_skip). A concrete derivation or empirical layer-traversal counts are needed before the O(log N) claim can be considered credible.
  4. [§3.3, Algorithm 3] The skip condition in the pseudocode disagrees with Eq. (4). Algorithm 3 (lines 25–31) triggers a skip whenever the LID of the nearest neighbor exceeds the threshold, with no distance check, whereas Eq. (4) requires both LID(ep) > T and d(ep,q) < epsilon. This discrepancy means the reported query-time results do not identify which skip condition was actually used, and the experimental evaluation of the skip mechanism is ambiguous.
  5. [§4.2, Figure 9] The text states that cross-language timing comparisons are unfair because HNSW++ is implemented in Python while other methods use faster compiled languages, yet the same section reports construction-time comparisons against PyNNDescent and NMSLIB in Figure 9 and claims HNSW++ 'significantly surpasses' them. The authors should either remove the cross-language timing comparisons or provide a same-language or compiled baseline, and clarify which implementation (C++ or Python) produced each timing result.
  6. [§4, §4.3] The experimental evaluation uses only 10,000 construction points and 1,000 queries, with no error bars or variance reporting despite the claim of '100 independent runs.' The 1–2% query-time differences and the no-trade-off conclusion require confidence intervals or per-run distributions. In addition, the hyperparameter selection procedure ('the best performance results for each algorithm were chosen based on recall across varying thresholds') should be specified precisely, because selecting parameters for best recall can bias the comparison in favor of the proposed method.
minor comments (5)
  1. [References] The reference list contains formatting errors, including an extra parenthesis in '(Zhang et al., 2022))' and an unconventional entry for 'Cole Foster (2023)'; these should be corrected to match the journal style.
  2. [Figure 9 caption] The caption for Figure 9 reads 'Illustration of recall of all algorithms on Random dataset,' but the surrounding text describes construction-time comparisons; the caption appears to be a copy-paste error and should be fixed.
  3. [§3.4 and Appendix A.1] The threshold-analysis figures (Figures 14, 15a, 15b) are described in the appendix but referenced in the main text without clear cross-referencing; please add explicit calls to the appendix and ensure figure numbering is consistent.
  4. [Algorithm 4] The layer assignment in Algorithm 4 still relies on a random scaling factor via −log(random()) in line 6, even though the surrounding text emphasizes LID-based insertion; the exact role of randomness in the layer assignment should be clarified.
  5. [§4.2] The sentence 'In terms of accuracy and recall, as depicted in Figures 15a and 15b, most datasets have minimal changes given different LID threshold' contains a grammatical error and should be rewritten for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: HNSW++'s accuracy and speed results are empirical benchmarks against external baselines and ground truth; the LID-threshold tuning and omitted LID-precomputation cost are fairness or reporting issues, not derivation collapses.

full rationale

The paper's central recall and accuracy results are measured against exact k-NN ground truth (e.g., Scikit-learn's NearestNeighbors) and against independent baselines such as FAISS, NMSLIB, PyNNDescent, and Annoy, so those claims are not self-definitional. LID values are computed by a standard MLE formula (Eq. 2) and are not defined in terms of HNSW++'s outputs. The LID threshold T is tuned in Section 3.4 through 'multiple experiments on LID threshold' and then used to control skip frequency; this is ordinary hyperparameter selection, and the resulting query-time and recall figures are reported as measured outcomes rather than as predictions forced by the chosen T. The statement in Section 3.5.2 that 'Assuming the LID values are provided beforehand, HNSW++ does not add significant computational overhead' is a scoping assumption that excludes a real preprocessing cost; it makes the 20% construction-time reduction an incomplete end-to-end comparison, but it is a missing-cost fairness gap, not a circular derivation. The paper contains no self-citations by the present authors and invokes no uniqueness theorem from its own prior work. Although some claims, such as index-based branches dividing spatial regions, are weakly justified, that is a correctness or evidence concern rather than circularity. Overall, no load-bearing step reduces by construction to its own input.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim of improved recall and speed rests on tuned thresholds (LID threshold, distance threshold) and on three unproven modeling assumptions: index-based branch partition yields spatial separation, high-LID/close nodes can safely skip layers, and skip probability is layer-independent. These assumptions are not backed by theory or independent measurements.

free parameters (3)
  • LID threshold T = not reported (tuned per dataset)
    Controls the skip-bridge trigger; Section 3.4 describes multiple experiments to choose the threshold for optimal performance.
  • Distance threshold epsilon = dataset average distance
    Used in Jump condition (Eq. 4) and Algorithm 3; set by hand to the dataset's average distance without theoretical justification.
  • k for LID estimation (efConstruction) = 128
    LID values are computed with k equal to efConstruction (Section 4.1); sensitivity to this choice is not reported.
assumptions (5)
  • standard math HNSW layer structure and greedy search behave as described in Malkov and Yashunin (2020).
    The paper builds on HNSW primitives without re-deriving their properties.
  • domain assumption MLE LID estimates with k=128 reliably capture local sparsity and are stable for insertion ordering.
    Used for layer assignment and skip decisions; no sensitivity analysis is provided.
  • ad hoc to paper Splitting nodes by insertion index divides the data into spatially distinct regions.
    Section 3.2 asserts this linkage without evidence; index order is arbitrary.
  • ad hoc to paper A high-LID, close-to-query node is a safe place to jump straight to layer 0.
    The Jump condition (Eq. 4) assumes these criteria prevent recall loss; no proof or analysis is given.
  • ad hoc to paper Skip probability Pskip is independent of layer and stationary, so expected traversal is Ltotal times (1 minus Pskip).
    Section 3.5.1 uses this to claim O(log N) complexity without deriving Pskip.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization." pith.science (2026). https://pith.science/paper/NQBXOB7S

@misc{pith2026250113992,
  author       = {Pith},
  title        = {Pith review of: Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NQBXOB7S}},
  note         = {Machine review of arXiv:2501.13992}
}
read the original abstract

The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor (ANN) search, leveraging the principles of navigable small-world graphs. However, it faces some limitations. The first is the local optima problem, which arises from the algorithm's greedy search strategy, selecting neighbors based solely on proximity at each step. This often leads to cluster disconnections. The second limitation is that HNSW frequently fails to achieve logarithmic complexity, particularly in high-dimensional datasets, due to the exhaustive traversal through each layer. To address these limitations, we propose a novel algorithm that mitigates local optima and cluster disconnections while enhancing the construction speed, maintaining inference speed. The first component is a dual-branch HNSW structure with LID-based insertion mechanisms, enabling traversal from multiple directions. This improves outlier node capture, enhances cluster connectivity, accelerates construction speed and reduces the risk of local minima. The second component incorporates a bridge-building technique that bypasses redundant intermediate layers, maintaining inference and making up the additional computational overhead introduced by the dual-branch structure. Experiments on various benchmarks and datasets showed that our algorithm outperforms the original HNSW in both accuracy and speed. We evaluated six datasets across Computer Vision (CV), and Natural Language Processing (NLP), showing recall improvements of 18\% in NLP, and up to 30\% in CV tasks while reducing the construction time by up to 20\% and maintaining the inference speed. We did not observe any trade-offs in our algorithm. Ablation studies revealed that LID-based insertion had the greatest impact on performance, followed by the dual-branch structure and bridge-building components.

Figures

Figures reproduced from arXiv: 2501.13992 by the authors.

Figure 1
Figure 1. Illustration of local minima and disconnected regions problems in Hierarchical Navigable [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Illustration of the method for inserting high-LID nodes into the top layers [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Illustration of the method for inserting high-LID nodes into the top layers, 2 branches and [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (11 more)
Figure 5
Figure 5. Figure 5: Illustration of recall of all algorithms [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Illustration of recall of all algorithms [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 8
Figure 8. Figure 8: Illustration of recall of all algorithms on Random dataset. [PITH_FULL_IMAGE:figures/full_fig_p009_8.png]
Figure 9
Figure 9. Figure 9: Illustration of recall of all algorithms on Random dataset. [PITH_FULL_IMAGE:figures/full_fig_p010_9.png]
Figure 10
Figure 10. Figure 10: Illustration of the average accuracy for each algorithm in ablation study [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]
Figure 12
Figure 12. Figure 12: Illustration of the average construc￾tion time for each algorithm in ablation study [PITH_FULL_IMAGE:figures/full_fig_p010_12.png]
Figure 14
Figure 14. Figure 14: Illustration the effect of varying the threshold on the number of layers bypassed by each [PITH_FULL_IMAGE:figures/full_fig_p012_14.png]
Figure 15
Figure 15. Figure 15: Illustration of impact of threshold on accuracy and recall of all algorithms across 6 [PITH_FULL_IMAGE:figures/full_fig_p013_15.png]
Figure 16
Figure 16. Figure 16: Illustration of accuracy of all algo￾rithms across 6 datasets in Python [PITH_FULL_IMAGE:figures/full_fig_p016_16.png]
Figure 18
Figure 18. Figure 18: LID distribution across different datasets. [PITH_FULL_IMAGE:figures/full_fig_p017_18.png]
Figure 19
Figure 19. Figure 19: Illustration of Workflow of Exclude set. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_19.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 12 canonical work pages

  1. [1]

    Estimating local intrinsic dimensionality

    Laurent Amsaleg, Oussama Chelly, Teddy Furon, Stéphane Girard, Michael E Houle, Ken-ichi Kawarabayashi, and Michael Nett. Estimating local intrinsic dimensionality. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.\ 29--38. ACM, 2015

    work page 2015

  2. [2]

    Babenko and V

    A. Babenko and V. Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016

    work page 2016

  3. [3]

    Learning to route in similarity graphs

    Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. Learning to route in similarity graphs. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp.\ 475--484. PMLR, 09--15 Jun 2019. URL https://proceedings.mlr...

    work page 2019

  4. [4]

    Computational enhancements of hnsw targeted to very large datasets

    Benjamin Kimia Cole Foster. Computational enhancements of hnsw targeted to very large datasets. Similarity Search and Applications. SISAP 2023. Lecture Notes in Computer Science, vol 14289. Springer, Cham, 2023

    work page 2023

  5. [5]

    O. P. Elliott and J. Clark. The impacts of data, ordering, and intrinsic dimensionality on recall in hierarchical navigable small worlds. In Proceedings of the 2024 ACM Conference on Recommender Systems, 2024. doi:10.1145/3664190.3672512

    arXiv 2024

  6. [6]

    Hand, Heikki Mannila, and Padhraic Smyth

    David J. Hand, Heikki Mannila, and Padhraic Smyth. Principles of Data Mining. MIT Press, 2001

    work page 2001

  7. [7]

    Houle, E

    M.E. Houle, E. Schubert, and A. Zimek. On the correlation between local intrinsic dimensionality and outlierness. In Similarity Search and Applications: Proceedings of the 11th International Conference on Similarity Search and Applications (SISAP). Springer, 2018

    work page 2018

  8. [8]

    Billion-scale similarity search with gpus

    Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 2019

    work page 2019

Show all 19 references
  1. [9]

    Jégou, M

    H. Jégou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011

    2011

  2. [10]

    Elizaveta Levina and Peter J. Bickel. Maximum likelihood estimation of intrinsic dimension. In Proceedings of the 17th International Conference on Neural Information Processing Systems, NIPS'04, pp.\ 777–784, Cambridge, MA, USA, 2004. MIT Press

    2004

  3. [11]

    Graph based nearest neighbor search: Promises and failures

    Peng-Cheng Lin and Wan-Lei Zhao. Graph based nearest neighbor search: Promises and failures. arXiv preprint arXiv:1904.02077, 2019

    1904 arXiv

  4. [12]

    Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020. doi:10.1109/TPAMI.2018.2889473

    2020

  5. [13]

    Pennington, R

    J. Pennington, R. Socher, and C. D. Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014

    2014

  6. [14]

    L. Wolf, T. Hassner, and I. Maoz. Face recognition in unconstrained videos with matched background similarity. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011

    2011

  7. [15]

    Connecting compression spaces with transformer for approximate nearest neighbor search

    Haokui Zhang, Buzhou Tang, Wenze Hu, and Xiaoyu Wang. Connecting compression spaces with transformer for approximate nearest neighbor search. Computer Vision – ECCV 2022. ECCV 2022. Lecture Notes in Computer Science, vol 13674. Springer, Cham, 2022

    2022

  8. [16]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

  9. [17]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  10. [18]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  11. [19]

    _ 8 BRS> <yvݵ?gm | XW ލ Zu x;ydk 8S] =`g xm c 05 ̫FXXpyתsz4a„&//4i233 ͭުDIReeٽ>RAA /ht<կ .o߾l޼9` ]w:봴4M4)5/ |]Mv >&Ol^޷o + UW`e?v[ D k0eʔ& 6h͚3gy]AAz꥙3gG mc5e ;ɻݮ]uVm޼Y۷o[8Tj]; @8

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

    2012

Pith tools

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