HNSW

HNSW (Hierarchical Navigable Small World) is an Approximate Nearest Neighbour (ANN) algorithm and data structure introduced by Yury Malkov and Dmitry Yashunin in their 2016 paper “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”. HNSW is a graph-based ANN structure: it represents the dataset as a multi-layer graph in which each node is a data vector and edges connect similar vectors, with a hierarchy of layers (top layers containing few nodes with long-range edges; bottom layers containing all nodes with short-range edges) that enables efficient navigation. Search proceeds top-down through the layers, finding a local minimum at each layer and using it as the entry point for the next layer down. HNSW achieves logarithmic search complexity (in dataset size) with high recall, making it the dominant graph-based ANN algorithm in production vector databases. Most modern vector databases (Pinecone, Weaviate, Qdrant, Milvus) and ANN libraries (FAISS, hnswlib, scann) include HNSW as a core index type. In recommender systems, HNSW is the standard index used to make Two-Tower Retrieval Model tractable at billion-item scale.

1. The Approximate Nearest Neighbour Problem

The exact nearest-neighbour problem: given a query vector q ∈ ℝ^d and a dataset of n vectors D = {v_1, ..., v_n}, find the vector v_i ∈ D minimizing some distance ||q − v_i|| (typically Euclidean) or maximizing similarity (typically dot product or cosine).

Naive exact search is O(n · d) per query — linear in dataset size. For n = 10⁹ (billion-vector catalogs) and d = 256 (typical embedding dimension), this is 2.5 × 10¹¹ operations per query — far too slow.

The approximate version trades a small amount of recall (occasionally missing the true nearest neighbour) for orders-of-magnitude speedup. Modern ANN methods achieve >95% recall with sub-linear (often O(log n)) query complexity. HNSW is one of the leading methods.

2. The Navigable Small World Concept

A navigable small world graph is a graph in which:

• Each node has connections to nearby nodes (local clustering).
• A few nodes have connections to distant nodes (long-range links).
• The result: any two nodes can be reached in O(log n) hops via greedy navigation.

The classical example is the social-network “six degrees of separation” phenomenon: most of your friends are local but a few are globally distant, and you can reach anyone via a short chain of acquaintances. This structure (mathematically, the Watts-Strogatz small-world model) supports efficient greedy routing.

For ANN search, the navigable-small-world property means: given a graph where nodes are data vectors and edges connect similar vectors, you can find the nearest neighbour to a query by starting at any node and greedily moving to neighbors closer to the query. Each greedy step gets closer; the chain converges in O(log n) steps if the graph has the navigable-small-world property.

The naive single-layer navigable small world graph (the NSW algorithm, Malkov 2014) was the predecessor to HNSW. NSW achieved sub-linear search but had two issues: (1) the entry point for greedy search was random, leading to long initial chains; (2) the routing degraded for very large datasets.

HNSW addresses both with a hierarchical structure.

3. The Hierarchical Structure

HNSW builds a multi-layer graph:

• Layer 0 (bottom): contains all n nodes, with edges to local neighbors.
• Layer 1: contains a random subset (probability p) of layer-0 nodes, with edges among them.
• Layer 2: contains a random subset of layer-1 nodes (probability p²).
• …
• Top layer: contains a few nodes with long-range edges spanning the whole dataset.

The probability p is typically around 1/e ≈ 0.37, giving an exponential decay of node count across layers. The maximum layer for each new node is sampled from a geometric distribution.

flowchart TD
  L3["Layer 3 (few nodes,<br/>long-range edges)"]
  L2["Layer 2"]
  L1["Layer 1"]
  L0["Layer 0 (all nodes,<br/>local edges)"]
  L3 -.entry point.-> L2
  L2 -.entry point.-> L1
  L1 -.entry point.-> L0
  L0 -->|return| KNN[Top-K nearest neighbours]

What this diagram shows. The four layers of an HNSW index, with the top layer having the fewest nodes and the longest-range edges. Search starts at the top layer, finds the local minimum (the node closest to the query), and uses it as the entry point for the next layer down. This continues until layer 0, where the final top-K nearest neighbours are returned. The key insight from this diagram is the staged refinement — top layers do coarse navigation (long jumps across the dataset); bottom layer does fine refinement (short jumps to the precise nearest neighbours). This is structurally similar to a skip list, where the upper levels enable fast traversal and the bottom level provides precision.

4. Search

The search procedure:

1. Start at the entry point of the top layer.
2. For each layer from top to bottom:
     Greedy search: from the current node, repeatedly move to the neighbour with smallest distance to query, until no neighbour is closer.
     Use the resulting local minimum as the entry point for the next layer down.
3. At the bottom layer, perform a more thorough search (typically priority-queue-based beam search) to find the top-K nearest neighbours.

The total search complexity is O(log n) for the upper-layer navigation plus O(ef_search) for the bottom-layer refinement, where ef_search is a tunable beam-width parameter (typically 50–200). Larger ef_search improves recall at the cost of search time.

5. Construction

The HNSW graph is built by inserting nodes one at a time:

For each new node v:
    Sample its maximum layer L_v from geometric distribution.
    For layer = top down to L_v:
        Search from current entry point to find the closest node to v in this layer.
    For layer = L_v down to 0:
        Find the M nearest existing nodes in this layer (using greedy search).
        Connect v to those M nodes (bidirectional edges).
        For each connected node, optionally prune its neighbour list to maintain the per-layer max-degree budget.

Where M is a tunable parameter (typically 16–48) controlling the per-layer connectivity. Larger M improves recall but increases memory.

The construction is O(n · log n) total — feasible for billion-vector datasets given a few hours of build time.

6. Hyperparameters

Hyperparameter	Typical range	Effect
M (max neighbors per node per layer)	16 to 48	Larger improves recall, increases memory.
ef_construction (build-time beam width)	100 to 500	Larger improves graph quality; slower build.
ef_search (query-time beam width)	50 to 500	Larger improves recall, slower query.
Number of layers	log₂(n) typical	Determined automatically by geometric layer sampling.

The classic HNSW recall-vs-latency curve is tunable via ef_search at query time, allowing per-query trade-offs.

7. When to Use HNSW

HNSW is appropriate when:

• You need approximate nearest-neighbor search with high recall (>95%).
• The dataset is large (millions to billions of vectors).
• You can afford the build time (a few hours for billion-vector indexes).
• Memory is available for the graph structure (graph adds significant overhead beyond just the vectors).

HNSW is the modern default for graph-based ANN. It is included in FAISS alongside other index types, and is the primary algorithm in dedicated libraries like hnswlib.

8. Strengths

• Logarithmic search complexity.
• High recall at fast query speeds.
• No training required — purely structural index.
• Tunable recall-speed trade-off at query time via ef_search.

9. Weaknesses

• Memory overhead — the graph structure adds substantial bytes per node (~M · 4 bytes per layer per node).
• Slow construction for very large datasets (build is O(n · log n) with non-trivial constants).
• No vector compression — uses full-precision vectors. Combined with Product Quantization for compressed variants.

10. See Also

• FAISS — Meta’s ANN library, includes HNSW as one index type
• ScaNN — Google’s alternative ANN library
• Product Quantization — vector compression often combined with HNSW
• Inverted File Index — alternative ANN approach (cluster-based)
• Locality-Sensitive Hashing — alternative ANN approach (hash-based)
• Two-Tower Retrieval Model — primary recommender use case for HNSW
• Recommender Algorithms Catalog
• Recommender Systems