Understanding HNSW Vector Index Traversal

Introduction

Hierarchical Navigable Small World (HNSW) is the dominant algorithm for approximate nearest neighbor (ANN) search in production vector databases, used by Pinecone, Weaviate, Qdrant, pgvector, and Chroma. It offers sub-linear query time — O(log N) — compared to the O(N) brute-force linear scan, while achieving 95-99% recall at typical settings. The algorithm combines two key insights from graph theory: small world graphs (any two nodes can be connected in O(log N) hops) and navigable graphs (greedy search always makes progress toward the target). By arranging these in a hierarchical multi-layer structure, HNSW creates a graph that can “zoom in” from coarse long-range connections to fine-grained nearest neighbors in a controlled traversal.

The practical implication is significant: a collection of 10 million 1536-dimensional vectors (typical for OpenAI text-embedding-3-small output) can be queried in under 5ms with >99% recall using HNSW, where brute-force cosine similarity over all 10M vectors would take several seconds. This speed-recall trade-off is controlled by two parameters — ef_construction (index build quality) and ef_search (query-time recall/speed trade-off) — making HNSW tunable for different production workloads.

Step-by-Step: HNSW Construction and Traversal

flowchart TD
    A["1. Small World Graph Theory Foundation"]
    B["2. Multi-Layer Hierarchy Construction"]
    C["3. Entry Point at Top Layer"]
    D["4. Greedy Neighbor Selection and Pruning"]
    E["5. ef_construction vs ef_search Parameters"]
    F["6. Cosine vs Euclidean Distance Operators"]
    G["7. Recall-Speed Trade-off in Practice"]
    A --> B
    B --> C
    C --> D
    D --> E
    E --> F
    F --> G

Step 1: Small World Graph Theory Foundation

A small world graph has two properties: high clustering coefficient (nearby nodes are densely connected) and short average path length between any pair of nodes (O(log N)). This is the same structure observed in social networks — you can reach any person in the world in ~6 hops. For ANN search, this means a greedy search that always moves to the neighbor closest to the query vector will reach the approximate nearest neighbor in O(log N) steps rather than visiting all N nodes.

The “navigable” property specifically refers to the guarantee that greedy search (always moving to the closest neighbor) converges to the correct region, not a local minimum — achieved by the particular graph construction algorithm.

Step 2: Multi-Layer Hierarchy Construction

HNSW extends the base small-world graph with a hierarchical layer structure:

Layer 0: Contains ALL vectors, with dense local connections (each node has M neighbors, typically M=16-64)
Layer 1: A random subset of vectors (~1/e ≈ 37% of layer 0), with long-range connections
Layer 2: Another 37% of layer 1 (~14% of total)
Higher layers: Continue until only a handful of nodes remain

Each vector is assigned a maximum layer ℓ sampled from a geometric distribution: ℓ = floor(-ln(uniform(0,1)) * mL), where mL = 1/ln(M) is the layer multiplier. This ensures the higher layers are exponentially sparser, creating the “hierarchy” effect.

import numpy as np
import heapq
from typing import List, Tuple, Dict, Set

class HNSWIndex:
    def __init__(self, dim: int, M: int = 16, ef_construction: int = 200):
        self.dim = dim
        self.M = M                          # Max neighbors per layer
        self.M_max0 = M * 2                # Max neighbors at layer 0
        self.ef_construction = ef_construction  # Dynamic candidate list size
        self.mL = 1.0 / np.log(M)          # Layer multiplier
        self.graphs: List[Dict[int, List[int]]] = []  # Adjacency lists per layer
        self.vectors: List[np.ndarray] = []
        self.entry_point: int = -1
        self.max_layer: int = -1

    def _get_random_level(self) -> int:
        """Sample insertion layer from geometric distribution."""
        return int(-np.log(np.random.uniform()) * self.mL)

    def _distance(self, a: np.ndarray, b: np.ndarray) -> float:
        """Cosine distance (1 - cosine_similarity)."""
        return 1.0 - np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))

Step 3: Entry Point at Top Layer

When inserting a new vector q into the index, the algorithm starts traversal at the global entry point at the highest layer. The entry point is the first vector ever inserted (or updated if the new vector’s level exceeds the current maximum level).

The traversal begins with a greedy search from the top layer downward:

Start at entry point in layer L_max (the top layer)
Greedily find the single nearest neighbor to q in the current layer
Drop down to layer L_max - 1, using that nearest neighbor as the new entry point
Repeat until reaching layer ℓ + 1 (the level just above where q will be inserted)
From layer ℓ down to layer 0, search with ef_construction candidates (not just 1)

    def _search_layer(
        self, 
        query: np.ndarray, 
        entry_points: List[int], 
        ef: int, 
        layer: int
    ) -> List[Tuple[float, int]]:
        """Greedy search within a single layer, maintaining ef-size candidate list."""
        visited: Set[int] = set(entry_points)
        # Min-heap for candidates (closest first), Max-heap for results (farthest first)
        candidates = [(self._distance(query, self.vectors[ep]), ep) for ep in entry_points]
        heapq.heapify(candidates)
        
        # W: working set of ef nearest found neighbors
        W = [(-d, idx) for d, idx in candidates]
        heapq.heapify(W)
        
        while candidates:
            dist_c, c = heapq.heappop(candidates)
            # If nearest candidate is farther than worst result, stop
            worst_dist = -W[0][0]
            if dist_c > worst_dist:
                break
            # Explore neighbors of c at this layer
            for neighbor in self.graphs[layer].get(c, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    d = self._distance(query, self.vectors[neighbor])
                    if d < worst_dist or len(W) < ef:
                        heapq.heappush(candidates, (d, neighbor))
                        heapq.heappush(W, (-d, neighbor))
                        if len(W) > ef:
                            heapq.heappop(W)  # Remove farthest
        
        return sorted([(-d, idx) for d, idx in W])

Step 4: Greedy Neighbor Selection and Pruning

After collecting ef_construction candidates, HNSW uses a heuristic neighbor selection algorithm (rather than simply taking the M closest) that prefers neighbors that improve graph connectivity — specifically, candidates that are not already “covered” by a closer candidate. This is the key to maintaining the small-world property:

    def _select_neighbors_heuristic(
        self, 
        candidates: List[Tuple[float, int]], 
        M: int
    ) -> List[int]:
        """Select M diverse neighbors to maintain navigability."""
        result = []
        candidates_copy = list(candidates)  # Already sorted by distance
        
        for dist, idx in candidates_copy:
            if len(result) >= M:
                break
            # Only add if this candidate is closer to query than to all selected neighbors
            is_good = True
            for existing_idx in result:
                if self._distance(self.vectors[idx], self.vectors[existing_idx]) < dist:
                    is_good = False
                    break
            if is_good:
                result.append(idx)
        
        return result

Step 5: ef_construction vs ef_search Parameters

The two critical tuning parameters control the quality-speed trade-off:

ef_construction (index build time):

The size of the dynamic candidate list during index construction
Higher values → better graph quality → higher recall at query time
Also increases index build time proportionally
Typical range: 100-400; default 200
Rule of thumb: ef_construction >= M * 2

ef_search (query time):

The size of the dynamic candidate list during search (overrides ef_construction at query time)
Higher values → higher recall at query time → slower queries
Must be ≥ the requested top_k
Typical range: 50-500 for 95-99% recall

# Example: Configuring HNSW in pgvector
-- Create a vector column and HNSW index
CREATE TABLE embeddings (
    id BIGSERIAL PRIMARY KEY,
    content TEXT,
    embedding vector(1536)
);

-- Build HNSW index
CREATE INDEX ON embeddings USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 200);

-- At query time, set ef_search
SET hnsw.ef_search = 100;

-- Nearest neighbor query
SELECT id, content, 1 - (embedding <=> '[0.1, 0.2, ...]'::vector) AS similarity
FROM embeddings
ORDER BY embedding <=> '[0.1, 0.2, ...]'::vector
LIMIT 10;

Step 6: Cosine vs Euclidean Distance Operators

The choice of distance metric significantly affects both index quality and query relevance:

Cosine similarity (<=> in pgvector, cosine in Pinecone):

Measures angle between vectors, ignoring magnitude
Preferred for text embeddings where semantic direction matters more than vector length
Range: [-1, 1] for similarity, [0, 2] for distance
Requires normalization for optimal performance: embedding = embedding / ||embedding||

Euclidean distance (L2) (<-> in pgvector):

Measures geometric distance between vector tips
Preferred for image embeddings, coordinate data
Sensitive to vector magnitude — normalize if that’s undesirable

Inner product (<#> in pgvector):

Equivalent to cosine similarity for normalized vectors
Fastest to compute (no square root needed)

Step 7: Recall-Speed Trade-off in Practice

import time
import numpy as np

# Simulate recall measurement at different ef_search values
def benchmark_hnsw(index, queries, ground_truth, ef_values, top_k=10):
    results = {}
    for ef in ef_values:
        start = time.perf_counter()
        recalls = []
        for i, q in enumerate(queries):
            approx_results = index.search(q, top_k, ef=ef)
            approx_ids = set(idx for _, idx in approx_results)
            true_ids = set(ground_truth[i][:top_k])
            recalls.append(len(approx_ids & true_ids) / top_k)
        elapsed = time.perf_counter() - start
        results[ef] = {
            "recall": np.mean(recalls),
            "qps": len(queries) / elapsed
        }
        print(f"ef={ef:4d}: recall={results[ef]['recall']:.4f}, "
              f"QPS={results[ef]['qps']:.0f}")
    return results

# Typical output:
# ef=  20: recall=0.8934, QPS=12500
# ef=  50: recall=0.9621, QPS=7800
# ef= 100: recall=0.9891, QPS=4200
# ef= 200: recall=0.9972, QPS=2100
# ef= 400: recall=0.9998, QPS=1050

Key Takeaways

HNSW’s multi-layer structure provides O(log N) traversal: The sparse upper layers enable fast coarse navigation, while the dense layer 0 provides fine-grained nearest neighbor resolution — analogous to a highway system overlaid on local roads.
ef_construction governs index quality at build time: Higher values produce better-connected graphs with higher potential recall, at the cost of longer index build times; this cannot be changed without rebuilding the index.
ef_search is the primary runtime recall-speed dial: Increasing ef_search from 50 to 200 typically improves recall from ~96% to ~99.7% at roughly 2-3× the query latency — tune based on your SLA requirements.
Heuristic neighbor selection preserves graph navigability: Simply selecting the M closest candidates would create cliques rather than diverse long-range connections; HNSW’s diversity-aware selection is what maintains the small-world property.
Cosine distance requires pre-normalization for correctness: For text embeddings in particular, normalizing vectors to unit length before insertion ensures that cosine similarity searches correctly rank by semantic angle rather than being influenced by embedding magnitude.