====== Hierarchical Navigable Small World Graphs ======

Hierarchical Navigable Small World (HNSW) graphs are a graph-based data structure for approximate nearest neighbor search that builds a multi-layer navigable small world network. Introduced by [[https://arxiv.org/abs/1603.09320|Malkov and Yashunin, 2016]], HNSW achieves logarithmic search complexity by constructing a hierarchy of proximity graphs where upper layers contain long-range links for coarse navigation and lower layers provide fine-grained local connectivity. HNSW has become the dominant indexing method in modern vector databases due to its excellent balance of speed, recall, and support for dynamic insertions.

===== Small World Graph Properties =====

HNSW builds on the theory of navigable small world networks, where any node can be reached from any other in a small number of hops (logarithmic in network size). This property emerges from combining two types of connections: short-range edges connecting nearby nodes for local precision, and long-range edges connecting distant nodes for global navigability. The "small world" phenomenon, formalized by Watts and Strogatz (1998), explains why greedy routing works efficiently in such networks.

The key insight of HNSW is that a single flat graph struggles to maintain both short-range and long-range connections optimally. By separating these into a hierarchy of layers, each layer can specialize: upper layers maintain sparse, long-range shortcuts for coarse navigation, while lower layers provide dense, local connections for precise nearest neighbor identification.

===== Hierarchical Layer Construction =====

Each vector $\mathbf{x}_i$ is assigned a maximum layer $l(\mathbf{x}_i)$ drawn from a geometric distribution with expected $O(\ln N)$ levels for $N$ nodes. The vector appears in all layers from 0 (the base layer, which contains all nodes) up to layer $l(\mathbf{x}_i)$. The parameter $M$ controls the maximum number of connections per node, balancing memory usage against graph navigability.

**Insertion Algorithm.** To insert a new vector: (1) start from the entry point at the top layer, (2) perform greedy search ($ef=1$) descending through layers to find the nearest neighbor at each level, (3) at the target layer and below, use beam search with $ef_{\text{Construction}}$ beam width to find the $M$ closest neighbors, and (4) connect the new node bidirectionally to these neighbors. The construction supports incremental and parallel builds.

**Neighbor Selection Heuristic.** HNSW uses a diversity-aware heuristic inspired by Delaunay graphs: when selecting neighbors, it prefers candidates that are closer to the new node than to any already-selected neighbor. This produces well-distributed connections that improve graph navigability, especially in clustered data.

===== Greedy Search and Beam Search =====

**Query Algorithm.** To search for the $k$ nearest neighbors of a query $\mathbf{q}$: (1) start from the entry point at the top layer, (2) greedily descend through upper layers, moving to the closest neighbor at each step until reaching a local minimum, (3) at the base layer (layer 0), perform best-first beam search with $ef_{\text{Search}}$ beam width, maintaining a candidate heap and a results heap. The search expands candidates until the closest unvisited candidate is farther than the farthest result.

**Complexity.** Both construction (per insertion) and search have expected $O(\log N)$ complexity due to the hierarchical shortcuts, analogous to skip lists. The $ef_{\text{Search}}$ parameter controls the speed-recall tradeoff: higher values improve recall at the cost of visiting more nodes. Typical values range from 50 (fast, ~95% recall) to 500+ (slower, ~99.5% recall).

===== Python Example with hnswlib =====

<code python>
import hnswlib
import numpy as np

# Parameters
dimension = 128
num_elements = 10000
num_queries = 5

# Generate random data
np.random.seed(42)
data = np.random.random((num_elements, dimension)).astype("float32")
queries = np.random.random((num_queries, dimension)).astype("float32")

# Initialize the HNSW index
index = hnswlib.Index(space="l2", dim=dimension)
index.init_index(max_elements=num_elements, ef_construction=200, M=16)

# Add items to the index (supports integer labels)
index.add_items(data, ids=np.arange(num_elements))

# Set ef parameter for search (controls speed vs recall tradeoff)
index.set_ef(50)

# Query the index for k nearest neighbors
labels, distances = index.knn_query(queries, k=5)
print(f"Nearest neighbor labels:\n{labels}")
print(f"L2 distances:\n{distances}")

# Increase ef for higher recall at the cost of speed
index.set_ef(300)
labels_hr, distances_hr = index.knn_query(queries, k=5)
print(f"High-recall labels:\n{labels_hr}")

# Save and reload the index
index.save_index("hnsw_index.bin")
index_loaded = hnswlib.Index(space="l2", dim=dimension)
index_loaded.load_index("hnsw_index.bin", max_elements=num_elements)
</code>

===== Performance Characteristics and Benchmarks =====

HNSW consistently achieves top speed-recall tradeoffs across standard ANN benchmarks (SIFT1M, GIST1M, Deep1B). Key characteristics:

  * **Recall**: Tunable from 90% to 99.9%+ via $ef_{\text{Search}}$ parameter
  * **Latency**: Sub-millisecond queries on million-scale datasets
  * **Memory**: Higher than quantization-based methods ([[faiss|FAISS]] IVF+PQ, [[scann|ScaNN]]) due to graph edge storage (~10-100 neighbors per node)
  * **Dynamic Updates**: Supports online insertions without full reindexing, a major advantage over tree and hash-based methods
  * **Build Time**: Slower than IVF or LSH due to graph construction, but supports incremental building

**2025 Benchmark Results.** On SIFT1M, merging algorithms (IGTM/CGTM by Ponomarenko, May 2025) reduce distance computations by 70% versus naive approaches. HNSW++ (2025) introduces dual-branch graphs with LID (Local Intrinsic Dimensionality)-guided insertion and skip-bridges, improving recall and efficiency across 12 CV/NLP/recommendation datasets. LID-ordered insertion is the most impactful single improvement; skip-bridges reduce per-layer costs by 20-50% with less than 2% recall drop.

**Flat Graph Insight.** Recent analysis (2025) shows that flat (single-layer) HNSW graphs save 38% memory at negligible accuracy loss in high-dimensional spaces, because high-dimensional data naturally creates "hub highways" that serve the function of upper layers.

===== Recent Improvements (Post-2016) =====

  * **LID-Guided Insertion** (Nguyen et al., January 2025): Sorts nodes by local intrinsic dimensionality before insertion, creating better bridge connections between clusters
  * **HNSW++**: Dual-branch graphs with skip-bridges for high-dimensional efficiency
  * **IGTM/CGTM Merging** (Ponomarenko, May 2025): Algorithms for merging independently built HNSW indexes for distributed scalability
  * **SHINE**: Disaggregated memory HNSW for cloud-native vector search
  * **Adaptive $ef$ Tuning**: Dynamic adjustment of search beam width based on query characteristics

===== Integration in Vector Databases =====

HNSW is the default or primary index in virtually all modern vector databases:

  * **hnswlib**: The reference C++ library with Python bindings, focused purely on HNSW with tunable $M$, $ef_{\text{Construction}}$, and $ef_{\text{Search}}$ parameters
  * **[[faiss|FAISS]]**: Includes HNSW as IndexHNSWFlat, combinable with quantization; optimized for batch operations
  * **[[pinecone|Pinecone]]**: Uses HNSW internally for its managed vector database service
  * **[[weaviate|Weaviate]]**: HNSW as the primary index with dynamic updates and filtering support
  * **Redis Vector Search**: HNSW with configurable $ef_{\text{Construction}}$ for indexing speed control
  * **Vespa**: HNSW with greedy layer-by-layer routing optimized for serving workloads
  * **[[milvus|Milvus]]**: Multiple HNSW variants including GPU-accelerated versions
  * **[[qdrant|Qdrant]]**: HNSW with payload filtering and quantization options

===== See Also =====

  * [[hnsw_indexing|HNSW Indexing]]
  * [[hnsw_vs_ivfflat|HNSW vs IVFFlat]]
  * [[neo4j|Neo4j]]

===== References =====