HNSW++: A Dual-Branch Hierarchical Navigable Small World Graph with LID-Guided Skip Bridge Optimization

The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor (ANN) search but suffers from local optima, frequently fails to achieve logarithmic complexity and inefficiencies in high-dimensional spaces. We propose a novel algorithm that enhances search accuracy and speed. Our approach introduces a dual-branch HNSW structure with LID-based insertion, improving cluster connectivity and mitigating local minima. Additionally, we incorporate skip-bridge connections, bypassing redundant layers to accelerate inference. Experiments on 12 datasets across Computer Vision (CV), Natural Language Processing (NLP), Recommender Systems (RecSys), and Synthetic data demonstrate superior recall and efficiency. Our method achieves up to 35% recall improvement in Recommender Systems, 30.3% in CV, 23.3% in NLP, and 10.1% in Synthetic data, while reducing inference time by 45% (CV), 42% (Synthetic), 20% (NLP), and 25% (Recommender Systems). Ablation studies confirm that LID-based insertion has the most impact, followed by dual-branch search and skip-bridging.