How HNSW works?

HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest neighbor (ANN) search algorithm used in LanceDB. It organizes high-dimensional vectors into a multi-layered graph, enabling fast search with logarithmic complexity. Let’s break down how HNSW works step by step.

Step 1: What is HNSW?

HNSW is a graph-based algorithm designed for efficient nearest neighbor search in high-dimensional spaces. Instead of scanning all vectors, it builds a multi-layered graph where:

• Nodes represent stored vectors.
• Edges connect similar vectors.
• Higher layers contain fewer, more representative nodes (coarse search).
• Lower layers contain dense, fine-grained connections (fine search).

Key Idea

The algorithm works by:

1. Starting at a high-level node (coarse search).
2. Moving toward more similar nodes (greedy search).
3. Descending to lower layers (fine search).
4. Stopping when the best neighbor is found.

Step 2: Constructing the HNSW Graph

2.1 Nodes and Edge Connections

Basic Definition

Suppose we store $N$ vectors in a dataset. Each vector $v_i$ is a node in the graph. HNSW connects nodes based on similarity using a nearest neighbor selection rule.

Mathematical Construction

For each new vector $v_i$ added to the graph:

1. Select nearest neighbors: Find $M$ nearest neighbors among existing nodes using cosine similarity:$$\text{similarity}(v_i,v_j)=\frac{v_i\cdot v_j}{\parallel v_i\parallel \parallel v_j\parallel }.$$
2. Form connections: Connect $v_i$ to the top-$M$ most similar vectors.
3. Use layers for scalability: Assign each node to multiple layers using a probability function:$$P(\text{layer})=\frac{1}{C^{\text{layer}}},$$where $C$ is a constant controlling how many vectors appear at high levels.

Layered Structure

• Layer 0 (Base layer): Contains all vectors with fine-grained connections.
• Layer 1, 2, …: Contains a subset of vectors, each linking to important “hub” nodes.

Step 3: Searching in the HNSW Graph

Once the multi-layered graph is built, HNSW finds the closest vector to a query using a graph traversal strategy.

3.1 Search Algorithm

Given a query vector $q$, HNSW performs the following steps:

1. Start at the top layer:
   • Pick a random entry node at the highest layer.
   • Compute cosine similarity between $q$ and that node.
2. Greedy Search at Each Layer:
   • Move to the most similar neighbor.
   • Repeat until no closer neighbor is found.
3. Descend to the Next Layer:
   • Once the best node at the current layer is found, descend to the next lower layer and continue searching.
4. Refine the Search at the Base Layer:
   • When reaching Layer 0, HNSW expands the search locally using exact nearest-neighbor search.

Step 4: Mathematical Example of HNSW Search

Let’s consider a dataset with 4 stored vectors in 2D:

A query vector is:

Graph Structure

Assume the following edges exist (based on cosine similarity):

• $v_1$ is connected to $v_2$ and $v_4$.
• $v_2$ is connected to $v_1$ and $v_3$.
• $v_3$ is connected to $v_2$ and $v_4$.
• $v_4$ is connected to $v_1$ and $v_3$.

Search Process

1. Start at the top layer:
   • Suppose we start at $v_1$.
2. Greedy Search:
   • Compute cosine similarity between $q$ and $v_1$: $\cos \mathrm{\_}sim(q,v_1)=0.8$.
   • Compare with neighbors $v_2$ and $v_4$:
     • $\cos \mathrm{\_}sim(q,v_2)=0.6$.
     • $\cos \mathrm{\_}sim(q,v_4)=-0.6$.
   • Since $v_1$ is closer than its neighbors, we stay at $v_1$.
3. Descend and Expand Search:
   • At Layer 0, check more neighbors:
     • Compare $q$ to $v_2$ and $v_4$.
     • If no closer node is found, return $v_1$ as the best match.

Step 5: Why HNSW is Fast

HNSW prunes the search space by:

1. Using hierarchical layers: Higher layers reduce the number of comparisons.
2. Greedy traversal: Instead of scanning all $N$ vectors, it only checks a small subset.
3. Efficient refinement: The base layer (Layer 0) ensures that the final result is highly accurate.

Computational Complexity

• Brute-force search: $O(N)$.
• HNSW search: $O(\log N)$.

HNSW is exponentially faster because it follows precomputed graph links instead of scanning everything.

Final Takeaways

• HNSW builds a graph where similar vectors are connected.
• At search time, it follows the best similarity path instead of scanning all vectors.
• The result is found in $O(\log N)$ time, making it much faster than brute-force search.