HNSW (Hierarchical Navigable Small World) Algorithm Internals for Vector Search¶
A staff-engineer-level deep dive into how HNSW actually works under the hood -- covering multi-layer graph construction, greedy search, parameter tuning, neighbor selection heuristics, complexity analysis, memory overhead, skip list theory, and real-world performance tradeoffs. Includes ASCII diagrams, pseudocode, mathematical formulas, and production guidance.
Table of Contents¶
- Theoretical Foundations
- Multi-Layer Graph Architecture
- Insertion Algorithm
- Level Selection via Exponential Distribution
- Search Algorithm: Greedy Layered Traversal
- Neighbor Selection Heuristics
- Key Parameters: M, efConstruction, efSearch
- Time Complexity Analysis
- Memory Overhead Analysis
- Why HNSW Outperforms Other ANN Approaches
- Real-World Performance Numbers
- Production Tuning Guide
1. Theoretical Foundations¶
1.1 Small World Networks (Milgram, Watts-Strogatz)¶
HNSW builds on decades of network science research. Stanley Milgram's 1967 "six degrees of separation" experiment demonstrated that social networks exhibit the small-world property: any two nodes can be connected through a surprisingly short chain of intermediaries.
Watts and Strogatz (1998) formalized this by showing that graphs with both high clustering (neighbors of a node are likely neighbors of each other) and short average path length (O(log N) hops between any pair) arise naturally when a small fraction of random "long-range" edges are added to a regular lattice.
Regular Lattice Small World Random Graph
(high clustering, (high clustering, (low clustering,
long paths) short paths) short paths)
o─o─o─o─o─o o─o─o─o─o─o o o─o o─o
│ │ │ ╲ │ │ ╲ │ ╱
o─o─o─o─o─o o─o─o╲o─o─o o──o o──o o
│ │ │ ╳ │ ╲ │╱ │
o─o─o─o─o─o o─o─o╱o─o─o o──o──o o──o
│ │ │ ╱ │ │ ╲│
o─o─o─o─o─o o─o─o─o─o─o o──o o──o─o
Rewiring probability: p ≈ 0.01 p ≈ 1.0
SWEET SPOT
1.2 Navigable Small Worlds (Kleinberg)¶
Jon Kleinberg (2000) asked the crucial question: when can a decentralized algorithm actually find short paths using only local information (i.e., a node only knows its own neighbors)?
He proved that greedy routing succeeds in O(log^2 N) expected steps if and only if long-range connections follow a specific power-law distribution tied to the metric dimension of the space. If long-range edge probability decays as d(u,v)^{-r} where r equals the metric dimension, greedy search finds polylogarithmic paths.
This is the theoretical foundation for why NSW/HNSW graphs are navigable: the structure of connections at different distance scales allows greedy algorithms to efficiently zero in on targets.
1.3 Navigable Small World (NSW) Graphs¶
Malkov and Yashunin's precursor to HNSW was the Navigable Small World graph (2014). NSW is a proximity graph built incrementally:
- Nodes are inserted one at a time.
- For each new node, greedy search finds its approximate nearest neighbors in the existing graph.
- Bidirectional edges connect the new node to those neighbors.
Early-inserted nodes naturally form long-range links (because fewer nodes existed when they were inserted, so their "nearest" neighbors span greater distances). Later-inserted nodes form short-range links. This organic combination yields navigability.
Problem: A flat NSW requires O(N^{1/d} * log(N)) hops for search in d-dimensional space for moderate recall. The routing is dominated by the initial coarse traversal phase, where the algorithm must traverse many long-range links before converging.
1.4 Skip Lists (Pugh, 1990)¶
Skip lists are probabilistic data structures that achieve O(log N) search in sorted linked lists by maintaining multiple levels of "express lanes":
Level 3: HEAD ─────────────────────────────────────── 47 ──────── NIL
│ │
Level 2: HEAD ────── 12 ──────────────── 35 ───── 47 ──────── NIL
│ │ │ │
Level 1: HEAD ── 6 ── 12 ────── 25 ── 35 ── 42 ── 47 ── 53 ── NIL
│ │ │ │ │ │ │ │
Level 0: HEAD ─ 3 ─ 6 ─ 12 ─ 19 ─ 25 ─ 35 ─ 42 ─ 47 ─ 53 ─ 61 ─ NIL
Properties:
- Level 0 contains ALL elements
- Each higher level contains a random subset (probability p = 1/2 typically)
- Expected number of levels: O(log N)
- Search: start at top level, move right until overshoot, drop down one level, repeat
- Expected search time: O(log N)
Each element is promoted to level k with probability p^k. This creates a hierarchy where: - Top levels have few elements spaced far apart (coarse navigation) - Bottom levels have many elements spaced close together (fine navigation)
1.5 The Key Insight: NSW + Skip List = HNSW¶
HNSW is the synthesis of NSW graphs and skip lists:
Skip List HNSW
───────── ────
Sorted linked list at each level → Proximity graph (NSW) at each level
Elements promoted probabilistically → Nodes promoted probabilistically
Higher levels = wider jumps → Higher levels = longer-range links in metric space
Greedy sequential search → Greedy graph traversal in vector space
O(log N) levels → O(log N) layers
Instead of maintaining sorted linked lists at each level, HNSW maintains proximity graphs at each level. The hierarchical structure separates links by characteristic distance scale, just as skip list levels separate elements by stride length.
2. Multi-Layer Graph Architecture¶
2.1 Layer Structure¶
HNSW constructs a multi-layer directed graph G = (V, E) where each layer l contains a subset of all nodes:
Layer L (top): Fewest nodes, longest-range connections
┌──────────────────────────────────────────────┐
│ [A] ──────────────────────────── [Q] │
│ │ │
└──────────────────────────────────────────────┘
│ │
Layer L-1: More nodes, medium-range connections
┌──────────────────────────────────────────────┐
│ [A] ──── [F] ──────── [M] ────── [Q] │
│ │╲ │ │╲ │ │
│ │ ╲ │ │ ╲ │ │
│ [C] ╲ [H] [O] ╲ [S] │
│ ╲ ╲ │
└──────────────────────────────────────────────┘
│ │ │ │ │ │ │ │
Layer 0 (bottom): ALL nodes, short-range connections (densest graph)
┌──────────────────────────────────────────────┐
│ [A]─[B]─[C]─[D]─[E]─[F]─[G]─[H]─[I]─[J] │
│ │╲ │╲ │ │╲ │╲ │ │╲ │ │╲ │ │
│ [K]─[L]─[M]─[N]─[O]─[P]─[Q]─[R]─[S]─[T] │
│ │ │╲ │ │ │╲ │ │╲ │ │ │ │
│ [U]─[V]─[W]─[X]─[Y]─[Z]─[α]─[β]─[γ]─[δ] │
└──────────────────────────────────────────────┘
Key Properties:
- V(Layer L) ⊂ V(Layer L-1) ⊂ ... ⊂ V(Layer 0)
- Layer 0 contains ALL N nodes
- Layer l contains ~N * exp(-l / mL) nodes
- The entry point is a node present at the highest layer
- Edges at higher layers connect nodes that are farther apart in vector space
- Edges at layer 0 connect nearby nodes in vector space
2.2 Node Representation¶
Each node in the graph stores:
struct HNSWNode {
vector: float[d] // d-dimensional feature vector
max_layer: int // highest layer this node appears in
neighbors: List<List<NodeID>> // neighbors[l] = neighbor IDs at layer l
// Layer 0: up to M_max0 neighbors (typically 2*M)
// Layer l > 0: up to M_max neighbors (typically M)
}
2.3 Why Two Different M Values?¶
Layer 0 is special because it contains all nodes and carries the most graph-search traffic during queries. The original paper recommends:
M_max0 = 2 * M (maximum connections at layer 0)
M_max = M (maximum connections at layers > 0)
Rationale:
- Layer 0 has the highest node density, so more connections
are needed to maintain good graph connectivity
- Higher layers are sparser, so M connections suffice
- Doubling M at layer 0 improves recall with modest memory cost
because most distance computations happen at layer 0 anyway
3. Insertion Algorithm¶
3.1 Complete Pseudocode: INSERT(hnsw, q, M, M_max, efConstruction, mL)¶
Algorithm 1: INSERT(hnsw, q, M, M_max, efConstruction, mL)
Input: hnsw -- the HNSW graph structure
q -- new element to insert
M -- number of established connections
M_max -- maximum number of connections per element per layer
efConstruction -- size of dynamic candidate list
mL -- normalization factor for level generation
1: W ← ∅ // list for currently found nearest elements
2: ep ← get entry point for hnsw
3: L ← level of ep // top layer of the graph
4: l ← ⌊-ln(unif(0..1)) · mL⌋ // new element's random layer ★
// ─── PHASE 1: Greedy descent from top to insertion layer (ef = 1) ───
5: for lc = L ... l+1 do // traverse from top layer down to layer l+1
6: W ← SEARCH-LAYER(q, ep, ef=1, lc)
7: ep ← get nearest element from W to q
8: end for
// ─── PHASE 2: Search + connect at layers l down to 0 (ef = efConstruction) ───
9: for lc = min(L, l) ... 0 do
10: W ← SEARCH-LAYER(q, ep, efConstruction, lc)
11: neighbors ← SELECT-NEIGHBORS(q, W, M, lc) // Algorithm 3 or 4
12: add bidirectional connections from q to neighbors at layer lc
// ─── Shrink neighbor lists if they exceed M_max ───
13: for each e ∈ neighbors do
14: eConn ← get neighborhood of e at layer lc
15: if |eConn| > M_max then // shrink if needed
16: eNewConn ← SELECT-NEIGHBORS(e, eConn, M_max, lc)
17: set neighborhood of e at layer lc to eNewConn
18: end if
19: end for
20: ep ← get nearest element from W to q
21: end for
// ─── Update entry point if new element has a higher layer ───
22: if l > L then
23: set entry point for hnsw to q
24: end if
3.2 Walkthrough of Insertion¶
Consider inserting a new vector q into an HNSW graph with 3 layers (L=2):
Step 1: Generate random level for q
l = ⌊-ln(0.73) · (1/ln(16))⌋ = ⌊0.314 · 0.361⌋ = ⌊0.113⌋ = 0
→ q will be inserted ONLY at layer 0
Step 2: Phase 1 -- Greedy descent (ef=1)
Start at entry point (top of layer 2)
Layer 2: ep=[A] → search with ef=1 → nearest=[A]
│
Layer 1: ep=[A] → search with ef=1 → nearest=[F]
│
Now at layer l+1 = 1, stop phase 1
Step 3: Phase 2 -- Full search + connect (ef=efConstruction)
Layer 0: ep=[F] → search with ef=efConstruction=200
→ finds W = {F, G, E, H, D, ...} (top 200 nearest candidates)
→ SELECT-NEIGHBORS(q, W, M=16, layer=0) → {F, G, E, H, ...} (16 neighbors)
→ Create bidirectional edges: q↔F, q↔G, q↔E, q↔H, ...
→ Check if any neighbor now exceeds M_max0=32; if so, prune
Step 4 (alternate): If q got level l=2 (rare):
Layer 2: No phase 1 (l >= L), go straight to phase 2
SEARCH-LAYER(q, ep, efConstruction, layer=2)
SELECT-NEIGHBORS → connect q to neighbors at layer 2
│
Layer 1: SEARCH-LAYER(q, nearest_from_layer2, efConstruction, layer=1)
SELECT-NEIGHBORS → connect q to neighbors at layer 1
│
Layer 0: SEARCH-LAYER(q, nearest_from_layer1, efConstruction, layer=0)
SELECT-NEIGHBORS → connect q to neighbors at layer 0
Update entry point to q (since l=2 > L_old=2 is false; but if l=3 > L=2, yes)
3.3 SEARCH-LAYER Pseudocode¶
This is the core beam search within a single layer:
Algorithm 2: SEARCH-LAYER(q, ep, ef, lc)
Input: q -- query element
ep -- entry point(s)
ef -- number of nearest to q elements to return (beam width)
lc -- layer number
Output: ef closest neighbors to q
1: v ← {ep} // set of visited elements
2: C ← {ep} // set of candidates (min-heap by distance to q)
3: W ← {ep} // dynamic list of found nearest neighbors (max-heap)
4: while |C| > 0 do
5: c ← extract nearest element from C to q
6: f ← get furthest element from W to q
7: if distance(c, q) > distance(f, q) then
8: break // all candidates are further than the worst result
9: end if
10: for each e ∈ neighborhood(c) at layer lc do
11: if e ∉ v then
12: v ← v ∪ {e}
13: f ← get furthest element from W to q
14: if distance(e, q) < distance(f, q) OR |W| < ef then
15: C ← C ∪ {e}
16: W ← W ∪ {e}
17: if |W| > ef then
18: remove furthest element from W
19: end if
20: end if
21: end if
22: end for
23: end while
24: return W
Key insight: This is a bounded beam search. The candidate set C drives exploration, while the result set W (capped at size ef) tracks the best results. The search terminates when the closest unexplored candidate is farther than the worst element in the result set -- a greedy stopping condition.
4. Level Selection via Exponential Distribution¶
4.1 The Formula¶
When inserting a new element, its maximum layer is drawn from:
l = ⌊ -ln(unif(0, 1)) · mL ⌋
where:
unif(0, 1) = uniform random number in (0, 1)
mL = 1 / ln(M) (normalization factor)
M = max connections per node per layer
⌊·⌋ = floor function
This produces a geometric distribution (discrete analog of exponential) where:
P(l = 0) = 1 - 1/M ≈ most nodes
P(l = 1) = (1/M)(1 - 1/M)
P(l = 2) = (1/M²)(1 - 1/M)
P(l = k) = (1/M^k)(1 - 1/M)
4.2 Why mL = 1/ln(M)?¶
The choice of mL = 1/ln(M) is not arbitrary. It ensures that adjacent layers have an overlap factor of approximately 1/M.
Derivation:
Given: l = ⌊ -ln(U) · mL ⌋ where U ~ Uniform(0,1)
The probability that l ≥ k is:
P(l ≥ k) = P(-ln(U) · mL ≥ k)
= P(ln(U) ≤ -k/mL)
= P(U ≤ exp(-k/mL))
= exp(-k/mL)
With mL = 1/ln(M):
P(l ≥ k) = exp(-k · ln(M))
= exp(ln(M^{-k}))
= M^{-k}
= 1/M^k
So:
P(node appears at layer k) = 1/M^k
Expected fraction of nodes at layer k:
Layer 0: N nodes (100%)
Layer 1: N/M nodes (1/M of all)
Layer 2: N/M² nodes (1/M² of all)
Layer k: N/M^k nodes
Expected number of layers: L = ⌊log_M(N)⌋
4.3 Concrete Examples¶
With M = 16, N = 1,000,000 nodes:
mL = 1/ln(16) = 1/2.773 ≈ 0.361
Layer 0: 1,000,000 nodes (100%)
Layer 1: 62,500 nodes (6.25%) ← 1/16 of total
Layer 2: 3,906 nodes (0.39%) ← 1/256 of total
Layer 3: 244 nodes (0.024%) ← 1/4096 of total
Layer 4: 15 nodes (0.0015%) ← 1/65536 of total
Layer 5: 1 node (entry point) ← 1/1048576
Expected layers: ⌊log_16(1,000,000)⌋ = ⌊4.98⌋ = 4-5 layers
┌──────────┬──────────────┬──────────────────────────────┐
│ Layer │ # Nodes │ Visualization │
├──────────┼──────────────┼──────────────────────────────┤
│ 5 │ ~1 │ * │
│ 4 │ ~15 │ *** │
│ 3 │ ~244 │ ******* │
│ 2 │ ~3906 │ **************** │
│ 1 │ ~62500 │ ************************ │
│ 0 │ 1000000 │ ******************************│
└──────────┴──────────────┴──────────────────────────────┘
With M = 32, N = 1,000,000 nodes:
mL = 1/ln(32) = 1/3.466 ≈ 0.289
Layer 0: 1,000,000 nodes
Layer 1: 31,250 nodes (1/32)
Layer 2: 977 nodes (1/1024)
Layer 3: 31 nodes (1/32768)
Layer 4: 1 node (1/1048576)
Expected layers: ⌊log_32(1,000,000)⌋ = ⌊3.98⌋ = 3-4 layers
→ Fewer layers but each layer is denser relative to the one below
4.4 Effect of mL on Graph Structure¶
mL too small (mL << 1/ln(M)):
→ Very few nodes promoted to higher layers
→ Top layers too sparse → poor coarse navigation
→ Falls back toward flat NSW behavior → O(N^{1/d} log N) search
mL too large (mL >> 1/ln(M)):
→ Too many nodes promoted to higher layers
→ Top layers too dense → waste computation at top
→ Extra memory for unnecessary upper-layer connections
→ Construction becomes slower
mL = 0:
→ All nodes at layer 0 only → degenerates to flat NSW
→ Search complexity degrades to O(N^{1/d} log N)
mL = 1/ln(M) (optimal):
→ 1/M fraction promoted per layer → skip list analogy holds
→ O(log N) layers → O(log N) total search complexity
→ Minimizes total work: each layer contributes O(1) expected steps
5. Search Algorithm: Greedy Layered Traversal¶
5.1 K-NN-SEARCH Pseudocode¶
Algorithm 5: K-NN-SEARCH(hnsw, q, K, ef)
Input: hnsw -- the HNSW graph
q -- query vector
K -- number of nearest neighbors to return
ef -- size of dynamic candidate list (efSearch)
Output: K nearest elements to q
1: W ← ∅ // set for current nearest elements
2: ep ← get entry point for hnsw
3: L ← level of ep // top layer of the graph
// ─── PHASE 1: Greedy traversal from top to layer 1 (ef = 1) ───
4: for lc = L ... 1 do
5: W ← SEARCH-LAYER(q, ep, ef=1, lc)
6: ep ← get nearest element from W to q
7: end for
// ─── PHASE 2: ef-bounded search at layer 0 ───
8: W ← SEARCH-LAYER(q, ep, ef, lc=0)
// ─── Return top K from the ef candidates ───
9: return K nearest elements from W to q
5.2 Search Walkthrough¶
Query: Find 10 nearest neighbors to vector q, with efSearch = 64
HNSW with 1M nodes, M=16, 5 layers:
Layer 4 (1 node):
┌─────────────────────────────────────────────────────────────┐
│ Start at entry point [ep] │
│ ep is the single node at the top layer │
│ SEARCH-LAYER(q, ep, ef=1, layer=4) │
│ Result: ep4 = [A] (only node, trivially nearest) │
└─────────────────────────────────────────────────────────────┘
│
Layer 3 (244 nodes): ▼
┌─────────────────────────────────────────────────────────────┐
│ SEARCH-LAYER(q, ep=A, ef=1, layer=3) │
│ │
│ [A]─────[K] Start at A, check A's neighbors at L3 │
│ │╲ ╱ │ K is closer to q than A → move to K │
│ │ [P]─╱ │ Check K's neighbors: P is closer → P │
│ │ ╳ │ Check P's neighbors: none closer → stop │
│ [D]──╱╲──[R] Result: ep3 = [P] │
│ Distance computations: ~5-8 │
└─────────────────────────────────────────────────────────────┘
│
Layer 2 (3906 nodes): ▼
┌─────────────────────────────────────────────────────────────┐
│ SEARCH-LAYER(q, ep=P, ef=1, layer=2) │
│ Greedy descent: P → P's neighbors → closest → repeat │
│ Hops: P → T → W → W is local minimum at layer 2 │
│ Result: ep2 = [W] │
│ Distance computations: ~8-15 │
└─────────────────────────────────────────────────────────────┘
│
Layer 1 (62500 nodes): ▼
┌─────────────────────────────────────────────────────────────┐
│ SEARCH-LAYER(q, ep=W, ef=1, layer=1) │
│ Greedy descent through denser graph │
│ Hops: W → Z → β → δ → δ is local minimum │
│ Result: ep1 = [δ] │
│ Distance computations: ~15-25 │
└─────────────────────────────────────────────────────────────┘
│
Layer 0 (1000000 nodes): ▼
┌─────────────────────────────────────────────────────────────┐
│ SEARCH-LAYER(q, ep=δ, ef=64, layer=0) ← BEAM SEARCH │
│ │
│ Now using ef=64 (not 1!) → maintains 64 best candidates │
│ Explores much more broadly than upper layers │
│ Candidate set expands and contracts as search progresses │
│ │
│ .....[δ].... │
│ ...../│╲.... Starting from δ, expand to its 32 │
│ ..../ │ ╲... neighbors (M_max0=32), evaluate each │
│ ..[n1]│[n2]. Add closer ones to candidate set C │
│ ...╲ │ ╱.. Continue expanding best candidate in C │
│ ....╲ │ ╱... Until termination condition met │
│ .....[★q]... │
│ │
│ Distance computations at layer 0: ~300-600 │
│ (dominates total search cost) │
│ │
│ Result W: 64 nearest candidates found │
│ Return top K=10 from W │
└─────────────────────────────────────────────────────────────┘
Total distance computations: ~330-650 (out of 1,000,000 nodes!)
Total graph hops: ~35-55
5.3 Why ef=1 at Upper Layers?¶
Upper layers (L ... 1): ef = 1
→ Pure greedy search (always follow single closest neighbor)
→ Reason: upper layers serve ONLY as coarse navigation
→ The goal is to quickly zoom into the right "neighborhood"
→ A single greedy path is sufficient because:
a) The graph is sparse → high connectivity relative to node count
b) The navigable small-world property guarantees short paths
c) Even if we land in a suboptimal neighborhood, layer 0's
beam search (ef >> 1) compensates by exploring broadly
Layer 0: ef = efSearch (user-configurable, typically 64-512)
→ Beam search with wide exploration
→ This is where accuracy is determined
→ Higher ef → more distance computations → higher recall → slower
→ Lower ef → fewer computations → lower recall → faster
5.4 Termination Condition¶
The search terminates when the nearest unvisited candidate is farther from q than the furthest element in the result set:
distance(closest_candidate, q) > distance(furthest_result, q)
This means: "Even the best remaining candidate can't improve our results"
┌─────────────────────────────────────────────────┐
│ │
│ Result set W (max-heap, size ef): │
│ ┌─────────────────────────┐ │
│ │ f = furthest in W │ ← threshold │
│ │ ... │ │
│ │ nearest in W │ │
│ └─────────────────────────┘ │
│ │
│ Candidate set C (min-heap): │
│ ┌─────────────────────────┐ │
│ │ c = nearest in C │ │
│ │ ... │ │
│ └─────────────────────────┘ │
│ │
│ if dist(c, q) > dist(f, q) → STOP │
│ │
└─────────────────────────────────────────────────┘
6. Neighbor Selection Heuristics¶
6.1 Simple Selection (Algorithm 3)¶
The naive approach: just pick the M closest candidates.
Algorithm 3: SELECT-NEIGHBORS-SIMPLE(q, C, M)
Input: q -- base element
C -- candidate elements
M -- number of neighbors to return
Output: M nearest elements to q
1: return M nearest elements from C to q
This works well for uniformly distributed data but fails for clustered data.
6.2 Heuristic Selection (Algorithm 4)¶
The heuristic promotes diversity among selected neighbors, ensuring connections reach different regions of the space:
Algorithm 4: SELECT-NEIGHBORS-HEURISTIC(q, C, M, lc, extendCandidates, keepPruned)
Input: q -- base element
C -- candidate elements
M -- number of neighbors to return
lc -- layer number
extendCandidates -- flag to extend candidate list from neighbors
keepPruned -- flag to add discarded candidates back
Output: M (or fewer) diverse elements
1: R ← ∅ // result set
2: W ← C // working candidate queue (min-heap by dist to q)
// ─── Optional: extend candidates by neighbors of candidates ───
3: if extendCandidates then
4: for each e ∈ C do
5: for each e_adj ∈ neighborhood(e) at layer lc do
6: if e_adj ∉ W then
7: W ← W ∪ {e_adj}
8: end if
9: end for
10: end for
11: end if
// ─── Keep discarded items for potential re-add ───
12: W_d ← ∅ // queue for discarded candidates
// ─── Greedy heuristic selection ───
13: while |W| > 0 AND |R| < M do
14: e ← extract nearest element from W to q
15: if distance(e, q) < distance(e, any r ∈ R) then ★ KEY CONDITION
16: R ← R ∪ {e}
17: else
18: W_d ← W_d ∪ {e}
19: end if
20: end while
// ─── Optionally fill remaining slots with pruned candidates ───
21: if keepPruned then
22: while |W_d| > 0 AND |R| < M do
23: R ← R ∪ {extract nearest from W_d to q}
24: end while
25: end if
26: return R
6.3 The Key Condition Explained¶
Line 15 is the heart of the heuristic. A candidate e is selected ONLY if it is closer to q than to ANY already-selected neighbor:
Condition: dist(e, q) < min_{r ∈ R} dist(e, r)
Intuition: "Don't select e if there's already a selected neighbor r
that is closer to e than q is. Because r already 'covers'
the region where e lives."
Example with simple nearest-neighbor selection (Algorithm 3):
─────────────────────────────────────────────────────────────
Cluster A Cluster B
┌───────────┐ ┌───────────┐
│ a1 a2 │ │ b1 b2 │
│ a3 ★q │ │ b3 b4 │
│ a4 a5 │ │ b5 b6 │
└───────────┘ └───────────┘
Simple (M=4): selects a3, a2, a5, a1 (all from cluster A!)
→ No connection to cluster B → routing dead end
Example with heuristic selection (Algorithm 4):
───────────────────────────────────────────────
Step 1: e=a3 (nearest to q), R={}.
dist(a3, q) < dist(a3, any r ∈ ∅) → trivially true → R={a3}
Step 2: e=a2, R={a3}.
dist(a2, q)=2.1 vs dist(a2, a3)=1.5 → 2.1 > 1.5 → REJECT
(a3 already covers a2's region)
Step 3: e=a5, R={a3}.
dist(a5, q)=2.3 vs dist(a5, a3)=3.0 → 2.3 < 3.0 → ACCEPT → R={a3, a5}
Step 4: e=b1 (nearest in cluster B), R={a3, a5}.
dist(b1, q)=8.0 vs dist(b1, a3)=9.5 → 8.0 < 9.5 → ACCEPT → R={a3, a5, b1}
Step 5: e=b2, R={a3, a5, b1}.
dist(b2, q)=8.5 vs dist(b2, b1)=1.2 → 8.5 > 1.2 → REJECT
(b1 covers b2's region)
Result: R = {a3, a5, b1, ...} → connections to BOTH clusters!
6.4 Impact on Graph Connectivity¶
Simple Selection Heuristic Selection
┌─────────────────────┐ ┌─────────────────────┐
│ │ │ │
Cluster A: │ ★q ← a1,a2,a3,a4 │ │ ★q ← a3, a5 │
│ (all 4 neighbors │ │ ↕ │
│ from cluster A) │ │ b1, c2 │
Cluster B: │ (no connection!) │ │ (diverse coverage) │
│ │ │ │
└─────────────────────┘ └─────────────────────┘
Effect on search:
Simple: May get stuck in local cluster → lower recall for out-of-cluster queries
Heuristic: Can hop between clusters → higher recall, especially for clustered data
Performance difference (from paper):
- Low-dimensional data: Heuristic dramatically better
- Mid-dimensional data: Heuristic notably better at high recall (>0.99)
- High-dimensional data: Moderate improvement
- Highly clustered data: Heuristic is essential
6.5 extendCandidates and keepPruned Flags¶
extendCandidates = true:
→ Before selection, expand candidate set by including neighbors-of-candidates
→ Useful during construction to discover better connections
→ Increases construction time but can improve graph quality
→ Recommended: true for construction, not applicable for search
keepPruned = true:
→ After heuristic selection, if |R| < M, fill remaining slots with
pruned candidates (those rejected by the heuristic), sorted by distance
→ Ensures we always fill up to M connections even with aggressive pruning
→ Recommended: true (default in hnswlib reference implementation)
7. Key Parameters: M, efConstruction, efSearch¶
7.1 M (Maximum Connections Per Node)¶
Definition: Maximum number of bidirectional connections per node per layer
(except layer 0, which uses M_max0 = 2*M)
┌──────┬────────────────┬──────────────┬────────────────┬───────────────┐
│ M │ Memory/Node │ Build Time │ Search Recall │ Search Speed │
├──────┼────────────────┼──────────────┼────────────────┼───────────────┤
│ 4 │ Very low │ Fast │ Poor │ Very fast │
│ 8 │ Low │ Fast │ Moderate │ Fast │
│ 12 │ Moderate │ Moderate │ Good │ Good │
│ 16 │ Moderate │ Moderate │ Very good │ Good │
│ 32 │ High │ Slow │ Excellent │ Moderate │
│ 48 │ High │ Slow │ Excellent │ Moderate │
│ 64 │ Very high │ Very slow │ Near-perfect │ Slower │
│ 128 │ Extreme │ Very slow │ Diminishing │ Slow │
└──────┴────────────────┴──────────────┴────────────────┴───────────────┘
Effects of M:
M ↑ → More connections → better graph connectivity → higher recall
M ↑ → More distance computations per hop → slower search per hop
M ↑ → More memory for neighbor lists
M ↑ → More layers (expected = log_M(N)) wait, FEWER layers (log_M N decreases)
M ↑ → Slower construction (more candidates to evaluate per insertion)
Recommended:
- General purpose: M = 16
- High-recall requirement: M = 32-64
- Memory-constrained: M = 8-12
- Very high dimensional (d > 1000): M = 32-48
- Low dimensional (d < 10): M = 8-16
7.2 efConstruction (Build-Time Beam Width)¶
Definition: Size of the dynamic candidate list during index construction.
Controls how many candidates are evaluated when finding
neighbors for a newly inserted node.
MUST satisfy: efConstruction ≥ M (otherwise not enough candidates)
┌──────────────────┬──────────────┬──────────────┬────────────────────┐
│ efConstruction │ Build Time │ Index Quality│ Effect on Search │
├──────────────────┼──────────────┼──────────────┼────────────────────┤
│ 40 │ Fast │ Moderate │ Lower max recall │
│ 100 │ Moderate │ Good │ Good recall │
│ 200 │ Slow │ Very good │ High recall │
│ 400 │ Very slow │ Excellent │ Near-optimal │
│ 800 │ Extremely │ Diminishing │ Marginal gain │
│ │ slow │ returns │ │
└──────────────────┴──────────────┴──────────────┴────────────────────┘
Key insight: efConstruction is a BUILD-TIME-ONLY parameter.
→ Once the index is built, it's frozen into the graph structure
→ Higher efConstruction = better neighbors found during construction
→ This leads to better graph quality which improves ALL future searches
→ But you pay the cost once at build time, not per query
Recommended:
- Minimum: efConstruction = 2 * M (bare minimum)
- Good: efConstruction = 100-200
- High: efConstruction = 400 (for critical applications)
- Rule of thumb: efConstruction = 4 * M to 8 * M
7.3 efSearch (Query-Time Beam Width)¶
Definition: Size of the dynamic candidate list during search at layer 0.
Controls the accuracy vs speed tradeoff at query time.
MUST satisfy: efSearch ≥ K (where K is the number of results requested)
┌──────────┬────────────────┬──────────────┬──────────────────────────┐
│ efSearch │ Recall@10 │ Latency │ Distance Computations │
├──────────┼────────────────┼──────────────┼──────────────────────────┤
│ 10 │ ~70-80% │ ~0.1 ms │ ~100-200 │
│ 32 │ ~85-90% │ ~0.2 ms │ ~200-400 │
│ 64 │ ~92-95% │ ~0.4 ms │ ~400-800 │
│ 128 │ ~96-98% │ ~0.8 ms │ ~800-1500 │
│ 256 │ ~98-99% │ ~1.5 ms │ ~1500-3000 │
│ 512 │ ~99-99.5% │ ~3 ms │ ~3000-6000 │
│ 1024 │ ~99.9% │ ~6 ms │ ~6000-12000 │
└──────────┴────────────────┴──────────────┴──────────────────────────┘
(Numbers approximate, for SIFT1M dataset with M=16, d=128)
Key insight: efSearch is the PRIMARY knob for recall vs latency tradeoff.
→ Can be changed per query (unlike efConstruction)
→ Different queries can use different ef values
→ Example: recommendation system uses ef=64, safety-critical uses ef=512
The relationship between efSearch and recall is roughly logarithmic:
doubling ef gives diminishing recall improvement but linearly more latency
7.4 Parameter Interaction¶
┌─────────────────────────────────────────────────────┐
│ PARAMETER INTERACTION MAP │
│ │
│ efConstruction ──► Graph Quality ──┐ │
│ (build time) │ │ │
│ ▼ │ │
│ M ──────────────► Connectivity ──► Maximum │
│ (structural) + Memory │ Achievable │
│ │ │ Recall │
│ │ │ │ │
│ ▼ │ │ │
│ # Layers ───► Search Hops │ │ │
│ ⌊log_M(N)⌋ │ ▼ │
│ │ ┌────────────┐ │
│ efSearch ─────────────────────►│ │ ACTUAL │ │
│ (query time) └─►│ RECALL │ │
│ │ & LATENCY │ │
│ └────────────┘ │
│ │
│ CEILING: recall ≤ f(M, efConstruction) │
│ KNOB: recall = g(efSearch) up to the ceiling │
└─────────────────────────────────────────────────────┘
Important: No amount of efSearch can compensate for poor graph quality.
If M or efConstruction is too low, the graph has structural deficiencies
(missing connections, poor navigability) that beam search cannot overcome.
8. Time Complexity Analysis¶
8.1 Search Complexity¶
K-NN Search:
Phase 1 (layers L down to 1, ef=1):
- Number of layers: O(log_M(N)) = O(log N / log M) = O(log N)
- Work per layer: O(1) expected hops × M distance computations per hop
- Total Phase 1: O(M · log N)
Phase 2 (layer 0, ef=efSearch):
- Beam search with ef candidates
- Each candidate expansion evaluates up to M_max0 = 2M neighbors
- Total candidates explored: O(efSearch)
- Work: O(efSearch · M · d) where d = vector dimension
(each distance computation costs O(d) for L2/cosine distance)
Total Search: O(efSearch · M · d + M · d · log N)
= O(d · M · (efSearch + log N))
Since efSearch >> log N in practice:
≈ O(d · M · efSearch)
For fixed M, efSearch: O(d · log N) — the "headline" complexity
┌────────────────────────────────────────────────────┐
│ Compared to brute force: O(N · d) │
│ │
│ HNSW search: O(d · M · efSearch) │
│ Brute force: O(N · d) │
│ │
│ Speedup: N / (M · efSearch) │
│ For N=1M, M=16, ef=64: ~1000x speedup │
│ For N=1B, M=16, ef=128: ~500,000x speedup │
└────────────────────────────────────────────────────┘
8.2 Construction Complexity¶
INSERT one element:
Phase 1 (greedy descent): O(M · d · log N) (same as search phase 1)
Phase 2 (connect at each layer):
- At each layer: SEARCH-LAYER with ef=efConstruction
→ O(efConstruction · M · d)
- Node appears in expected 1 + 1/(M-1) ≈ 1 layers (for large M)
(most nodes appear only at layer 0)
- Plus neighbor pruning: O(M² · d) per layer (recomputing neighbor sets)
Per-insertion cost: O(efConstruction · M · d · layers_for_this_node)
≈ O(efConstruction · M · d) (since most nodes have 1 layer)
Total construction (N insertions):
O(N · efConstruction · M · d · log N / log M)
Simplified: O(N · efConstruction · M · d · log N)
┌──────────────────────────────────────────────────────────┐
│ Construction Time Examples (approximate): │
│ │
│ N=1M, d=128, M=16, efC=200: │
│ ~2-5 minutes on modern CPU (single-threaded) │
│ ~30-60 seconds with 8 threads │
│ │
│ N=10M, d=768, M=32, efC=200: │
│ ~2-4 hours single-threaded │
│ ~20-40 minutes with 8 threads │
│ │
│ N=1B, d=128, M=16, efC=100: │
│ ~days single-threaded │
│ ~hours with high parallelism │
└──────────────────────────────────────────────────────────┘
8.3 Complexity Comparison Table¶
┌────────────────────┬─────────────────┬──────────────┬────────────────┐
│ Operation │ Time │ Space │ Notes │
├────────────────────┼─────────────────┼──────────────┼────────────────┤
│ Insert 1 element │ O(efC·M·d·logN) │ O(M·layers) │ Amortized │
│ Build N elements │ O(N·efC·M·d· │ O(N·M·d) │ Parallelizable │
│ │ logN) │ │ │
│ K-NN Search │ O(d·M·(ef + │ O(ef) │ ef = efSearch │
│ │ logN)) │ │ │
│ Delete 1 element │ O(M²·d) │ -O(M·layers) │ Repair needed │
│ Brute Force │ O(N·d) │ O(1) │ Exact result │
└────────────────────┴─────────────────┴──────────────┴────────────────┘
9. Memory Overhead Analysis¶
9.1 Memory Components¶
Total memory = Vector storage + Graph structure + Metadata
1. Vector Storage (dominant for high-dimensional data):
────────────────────────────────────────────────
bytes_vectors = N × d × sizeof(float)
= N × d × 4 bytes (for float32)
Examples:
1M vectors × 128d × 4B = 512 MB
1M vectors × 768d × 4B = 3.0 GB
1M vectors × 1536d × 4B = 6.0 GB
10M vectors × 128d × 4B = 5.0 GB
2. Graph Structure (neighbor lists):
────────────────────────────────────────────────
Layer 0: N nodes × M_max0 neighbors × sizeof(node_id)
= N × 2M × 4 bytes
Layer l>0: (N/M^l) nodes × M neighbors × sizeof(node_id)
= (N/M^l) × M × 4 bytes
Total graph memory:
bytes_graph = N × 2M × 4 (layer 0)
+ N/M × M × 4 (layer 1)
+ N/M² × M × 4 (layer 2)
+ ...
= N × 4 × (2M + 1 + 1/M + 1/M² + ...)
= N × 4 × (2M + M/(M-1))
≈ N × 4 × (2M + 1) (for M >> 1)
≈ N × 8M bytes (dominated by layer 0)
Examples (graph overhead only):
N=1M, M=16: 1M × 8 × 16 = 128 MB
N=1M, M=32: 1M × 8 × 32 = 256 MB
N=1M, M=64: 1M × 8 × 64 = 512 MB
N=10M, M=16: 10M × 8 × 16 = 1.28 GB
3. Metadata (per node):
────────────────────────────────────────────────
- Node ID: 4-8 bytes
- Max layer: 1-4 bytes
- Lock/flags: 4-8 bytes (for concurrent access)
- Total: ~16-24 bytes per node
bytes_metadata ≈ N × 20 bytes
9.2 Total Memory Formula¶
Total Memory = N × (d × 4 + 8 × M + 20) bytes
───── ────── ────
vectors graph metadata
┌───────────────────────────────────────────────────────────────────────┐
│ Memory Breakdown for Common Configurations │
│ │
│ Config: N=1M, d=128, M=16 │
│ Vectors: 512 MB (78%) │
│ Graph: 128 MB (20%) │
│ Metadata: 20 MB ( 3%) │
│ TOTAL: 660 MB │
│ │
│ Config: N=1M, d=768, M=16 │
│ Vectors: 3072 MB (95%) │
│ Graph: 128 MB ( 4%) │
│ Metadata: 20 MB ( 1%) │
│ TOTAL: 3220 MB ≈ 3.1 GB │
│ │
│ Config: N=1M, d=1536, M=32 │
│ Vectors: 6144 MB (96%) │
│ Graph: 256 MB ( 4%) │
│ Metadata: 20 MB ( 0.3%) │
│ TOTAL: 6420 MB ≈ 6.3 GB │
│ │
│ Config: N=10M, d=128, M=16 │
│ Vectors: 5120 MB (78%) │
│ Graph: 1280 MB (20%) │
│ Metadata: 200 MB ( 3%) │
│ TOTAL: 6600 MB ≈ 6.4 GB │
│ │
│ Config: N=100M, d=128, M=16 │
│ Vectors: 51200 MB │
│ Graph: 12800 MB │
│ Metadata: 2000 MB │
│ TOTAL: 66000 MB ≈ 64.5 GB │
└───────────────────────────────────────────────────────────────────────┘
9.3 Graph Overhead as Percentage of Vectors¶
Overhead ratio = graph_bytes / vector_bytes
= (8 × M) / (d × 4)
= 2M / d
┌──────┬────────┬─────────────┬──────────────────────────────────────┐
│ M │ d=128 │ d=768 │ Note │
├──────┼────────┼─────────────┼──────────────────────────────────────┤
│ 8 │ 12.5% │ 2.1% │ Low overhead │
│ 16 │ 25.0% │ 4.2% │ Standard │
│ 32 │ 50.0% │ 8.3% │ High M │
│ 64 │ 100% │ 16.7% │ Graph = vectors in size for d=128 │
│ 128 │ 200% │ 33.3% │ Graph dominates for low d │
└──────┴────────┴─────────────┴──────────────────────────────────────┘
Key insight: For high-dimensional vectors (d ≥ 768, typical for
LLM embeddings), graph overhead is small relative to vector storage.
For low-dimensional vectors, graph overhead can dominate.
9.4 Comparison with Other ANN Index Memory¶
┌──────────────────────┬──────────────────────┬────────────────────────┐
│ Index Type │ Memory (N=1M,d=128) │ Notes │
├──────────────────────┼──────────────────────┼────────────────────────┤
│ Flat (brute force) │ 512 MB │ Vectors only │
│ HNSW (M=16) │ 660 MB (+29%) │ Vectors + graph │
│ HNSW (M=32) │ 788 MB (+54%) │ Vectors + graph │
│ IVF-Flat (nlist=1K) │ ~520 MB (+2%) │ Vectors + centroids │
│ IVF-PQ (nlist=1K, │ ~40 MB (-92%) │ Compressed vectors │
│ m=16, nbits=8) │ │ │
│ LSH (128 tables) │ ~600 MB (+17%) │ Hash tables │
│ HNSW + PQ │ ~170 MB (-67%) │ Compressed + graph │
│ NSG │ ~620 MB (+21%) │ Vectors + graph │
│ DiskANN │ ~50 MB in RAM │ Vectors on SSD │
│ │ + SSD storage │ │
└──────────────────────┴──────────────────────┴────────────────────────┘
HNSW trades memory for speed. When memory is the bottleneck,
combine HNSW with Product Quantization (PQ) or use DiskANN.
10. Why HNSW Outperforms Other ANN Approaches¶
10.1 Comparison Framework¶
┌─────────────────────────────────────────────────────────────────────────────┐
│ ANN ALGORITHM LANDSCAPE │
│ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ Tree-Based │ │ Hash-Based │ │ Quantization │ │ Graph-Based │ │
│ │ │ │ │ │ │ │ │ │
│ │ KD-Tree │ │ LSH │ │ PQ │ │ NSW │ │
│ │ Ball Tree │ │ Multi-probe │ │ OPQ │ │ HNSW ★ │ │
│ │ Annoy │ │ LSH │ │ ScaNN │ │ NSG │ │
│ │ VP-Tree │ │ SimHash │ │ IVFPQ │ │ DiskANN │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │ FANNG │ │
│ └──────────────┘ │
│ Curse of Data-oblivious Lossy compression Data-adaptive │
│ dimensionality (random hashing) (quantization (graph structure │
│ (fails d > 20) (needs many error) adapts to data) │
│ tables) │
└─────────────────────────────────────────────────────────────────────────────┘
10.2 Why HNSW Wins: Detailed Reasons¶
Reason 1: Adaptive to Data Distribution
LSH: Hashes are random projections → ignore data structure
→ Need many hash tables to cover the space → memory explosion
→ Same hash function regardless of whether data is clustered or uniform
HNSW: Graph structure adapts to the actual data distribution
→ Dense clusters get dense local connections
→ Sparse regions get long-range connections
→ The graph "learns" the data manifold through construction
┌──────────────────────────────┐ ┌──────────────────────────────┐
│ LSH on clustered data │ │ HNSW on clustered data │
│ │ │ │
│ Hash buckets split clusters │ │ Graph preserves clusters │
│ randomly — neighbors land │ │ — each cluster is densely │
│ in different buckets │ │ connected internally with │
│ │ │ bridge edges between them │
└──────────────────────────────┘ └──────────────────────────────┘
Reason 2: Polylogarithmic Search with Constant Factors
HNSW search complexity: O(d · M · log N) (for fixed ef)
→ Polylogarithmic in N
→ Each layer contributes O(1) expected greedy steps
Tree-based (KD-Tree): O(d · N^{1-1/d})
→ Degrades exponentially with dimension
→ For d=128: essentially brute force
LSH: O(d · N^{1/c²})
→ Sublinear but with large constants
→ c = approximation factor (typically 1.5-3)
→ Practical speed often slower than HNSW
IVF: O(d · nprobe · N/nlist)
→ Must scan nprobe clusters entirely
→ nprobe must be large for high recall → approaches brute force
Reason 3: No Curse of Dimensionality
KD-Tree performance vs dimension:
d=2: O(log N)
d=10: O(N^0.9)
d=50: O(N^0.98) ← basically brute force
d=128: O(N) ← IS brute force
HNSW performance vs dimension:
d=2: O(d · log N) = O(log N)
d=10: O(d · log N) = O(10 · log N)
d=50: O(d · log N) = O(50 · log N)
d=128: O(d · log N) = O(128 · log N) ← still logarithmic in N!
d=1536: O(d · log N) = O(1536 · log N) ← works for LLM embeddings
The hierarchical small-world property holds regardless of dimension.
Distance computations cost O(d) each, but the NUMBER of computations
remains O(log N), independent of dimension.
Reason 4: Incremental Construction
HNSW: Supports online insertion (add one vector at a time)
→ No need to rebuild when new data arrives
→ Critical for production systems with streaming data
IVF: Requires pre-trained centroids
→ Adding data may invalidate cluster structure
→ Need periodic retraining
LSH: Hash tables are static
→ Adding data is easy but quality degrades as distribution shifts
KD-Tree: Insertions cause tree imbalance
→ Need periodic rebalancing
Annoy: Index is immutable after construction
→ Must rebuild entirely for new data
Reason 5: Excellent Recall-Throughput Pareto Frontier
At 95% recall@10 on SIFT1M (d=128, 1M vectors):
┌──────────────┬───────────┬─────────────────────────────────────┐
│ Algorithm │ QPS │ ▊▊▊▊▊▊ Throughput Bar │
├──────────────┼───────────┼─────────────────────────────────────┤
│ HNSW │ ~5000 │ ▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊ │
│ NSG │ ~4000 │ ▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊▊ │
│ IVFPQ │ ~2000 │ ▊▊▊▊▊▊▊▊▊▊▊▊ │
│ Annoy │ ~800 │ ▊▊▊▊▊ │
│ LSH │ ~300 │ ▊▊ │
│ KD-Tree │ ~100 │ ▊ │
│ Brute Force │ ~50 │ │
└──────────────┴───────────┴─────────────────────────────────────┘
(Approximate values from ann-benchmarks.com and published literature)
At 99% recall@10:
HNSW: ~1000-2000 QPS
IVF: ~200-500 QPS
→ HNSW advantage grows at higher recall requirements
Reason 6: Robust Across Datasets
HNSW performance is remarkably consistent across different data distributions:
┌──────────────────┬───────────┬───────────┬──────────────────────────┐
│ Dataset │ Dim │ 95% R@10 │ Notes │
│ │ │ QPS │ │
├──────────────────┼───────────┼───────────┼──────────────────────────┤
│ SIFT1M │ 128 │ ~5000 │ Uniform, moderate dim │
│ GloVe-100 │ 100 │ ~3000 │ NLP, clustered │
│ GIST │ 960 │ ~500 │ High-dim, dense │
│ Fashion-MNIST │ 784 │ ~600 │ Image features │
│ DEEP1B (1M sub) │ 96 │ ~4500 │ Deep learning features │
│ Random-128 │ 128 │ ~6000 │ Uniform random │
└──────────────────┴───────────┴───────────┴──────────────────────────┘
Algorithms like LSH perform well on some datasets but poorly on others.
HNSW is consistently near the Pareto front across ALL standard benchmarks.
11. Real-World Performance Numbers¶
11.1 SIFT1M Benchmark (Standard Reference)¶
Dataset: SIFT1M — 1,000,000 vectors, d=128, L2 distance
Machine: Single core, modern x86 CPU (typical benchmark setup)
HNSW Parameters: M=16, efConstruction=200
┌───────────┬────────────┬────────────┬────────────┬───────────────────┐
│ efSearch │ Recall@10 │ QPS │ Latency │ Dist. Comps │
├───────────┼────────────┼────────────┼────────────┼───────────────────┤
│ 10 │ 72% │ ~15000 │ 0.07 ms │ ~120 │
│ 20 │ 84% │ ~10000 │ 0.10 ms │ ~220 │
│ 40 │ 92% │ ~6000 │ 0.17 ms │ ~420 │
│ 64 │ 95% │ ~4000 │ 0.25 ms │ ~650 │
│ 100 │ 97% │ ~2500 │ 0.40 ms │ ~1000 │
│ 200 │ 98.5% │ ~1300 │ 0.77 ms │ ~2000 │
│ 400 │ 99.3% │ ~700 │ 1.4 ms │ ~4000 │
│ 800 │ 99.8% │ ~350 │ 2.9 ms │ ~8000 │
│ 1600 │ 99.95% │ ~180 │ 5.6 ms │ ~16000 │
└───────────┴────────────┴────────────┴────────────┴───────────────────┘
Build time: ~3 minutes (single-threaded)
Index size: ~660 MB (vectors + graph, M=16)
11.2 High-Dimensional Benchmarks¶
Dataset: OpenAI ada-002 embeddings, 1M vectors, d=1536, cosine similarity
HNSW Parameters: M=32, efConstruction=200
┌───────────┬────────────┬────────────┬────────────┐
│ efSearch │ Recall@10 │ QPS │ Latency │
├───────────┼────────────┼────────────┼────────────┤
│ 32 │ 88% │ ~800 │ 1.25 ms │
│ 64 │ 93% │ ~450 │ 2.2 ms │
│ 128 │ 96% │ ~250 │ 4.0 ms │
│ 256 │ 98% │ ~130 │ 7.7 ms │
│ 512 │ 99% │ ~70 │ 14 ms │
└───────────┴────────────┴────────────┴────────────┘
Note: Higher dimension → each distance computation is more expensive
d=128: ~0.5 us per L2 computation
d=768: ~3 us per L2 computation
d=1536: ~6 us per L2 computation (with SIMD)
→ QPS drops proportionally with dimension
11.3 Billion-Scale Performance¶
Dataset: DEEP1B — 1,000,000,000 vectors, d=96
Approach: HNSW on compressed vectors (HNSW + PQ/OPQ)
Machine: Single server, 64GB RAM, NVMe SSD
┌──────────────────┬─────────────┬──────────┬──────────┬───────────────┐
│ Configuration │ RAM Usage │ R@10 │ QPS │ Latency(p99) │
├──────────────────┼─────────────┼──────────┼──────────┼───────────────┤
│ HNSW (in-mem) │ ~120 GB │ 95% │ ~2000 │ 3 ms │
│ HNSW+OPQ64 │ ~25 GB │ 85% │ ~3000 │ 2 ms │
│ IVF+HNSW+PQ │ ~12 GB │ 78% │ ~5000 │ 1.5 ms │
│ DiskANN │ ~8 GB RAM │ 92% │ ~800 │ 5 ms │
│ │ + 200GB SSD│ │ │ │
└──────────────────┴─────────────┴──────────┴──────────┴───────────────┘
Key finding at billion scale:
- Pure HNSW needs too much RAM (120+ GB)
- HNSW + PQ/OPQ is the practical sweet spot (25 GB, 85% recall)
- DiskANN wins on memory efficiency but sacrifices throughput
- IVF+HNSW+PQ provides best throughput with moderate recall
11.4 Multi-Threaded Scaling¶
HNSW search is embarrassingly parallel (each query independent):
┌─────────┬──────────────┬──────────────┬───────────────────────┐
│ Threads│ QPS (SIFT1M)│ Speedup │ Efficiency │
├─────────┼──────────────┼──────────────┼───────────────────────┤
│ 1 │ 4,000 │ 1.0x │ 100% │
│ 2 │ 7,800 │ 1.95x │ 97.5% │
│ 4 │ 15,200 │ 3.80x │ 95% │
│ 8 │ 28,800 │ 7.20x │ 90% │
│ 16 │ 52,000 │ 13.0x │ 81% │
│ 32 │ 85,000 │ 21.3x │ 66% │
│ 64 │ 110,000 │ 27.5x │ 43% (memory bound) │
└─────────┴──────────────┴──────────────┴───────────────────────┘
Scaling bottlenecks:
- L3 cache contention (graph + vectors don't fit in per-core cache)
- Memory bandwidth saturation (random access pattern)
- NUMA effects on multi-socket systems
- Efficiency drops after core count exceeds ~16-32 for in-memory workloads
11.5 Construction Performance¶
HNSW Build Times (single thread, M=16, efConstruction=200):
┌──────────────┬─────────┬────────────┬──────────────────────────┐
│ N │ Dim │ Build Time│ Throughput │
├──────────────┼─────────┼────────────┼──────────────────────────┤
│ 100K │ 128 │ 15 sec │ 6,700 vectors/sec │
│ 1M │ 128 │ 3 min │ 5,500 vectors/sec │
│ 10M │ 128 │ 45 min │ 3,700 vectors/sec │
│ 1M │ 768 │ 18 min │ 930 vectors/sec │
│ 1M │ 1536 │ 40 min │ 420 vectors/sec │
└──────────────┴─────────┴────────────┴──────────────────────────┘
With 8-thread parallel construction:
1M × d=128: ~35-45 seconds
1M × d=768: ~3-4 minutes
10M × d=128: ~6-8 minutes
12. Production Tuning Guide¶
12.1 Parameter Selection Decision Tree¶
START
│
├── What is your dimension (d)?
│ ├── d < 32: M = 8-12, efC = 100
│ ├── d = 32-256: M = 16-32, efC = 200
│ ├── d = 256-1024: M = 32, efC = 200-400
│ └── d > 1024: M = 32-48, efC = 200-400
│
├── What is your dataset size (N)?
│ ├── N < 100K: efC = 100-200 (fast builds, doesn't matter much)
│ ├── N = 100K-10M: efC = 200 (standard)
│ └── N > 10M: efC = 100-200 (build time becomes critical)
│
├── What is your recall target?
│ ├── 90%: efSearch = 40-64
│ ├── 95%: efSearch = 64-128
│ ├── 99%: efSearch = 200-400
│ └── 99.9%: efSearch = 800-1600
│
├── What is your latency budget?
│ ├── < 1ms: efSearch = 20-64, M = 16
│ ├── 1-5ms: efSearch = 64-256, M = 16-32
│ ├── 5-20ms: efSearch = 256-512, M = 32-48
│ └── > 20ms: efSearch = 512+, M = 48-64
│
└── What is your memory budget (per 1M vectors)?
├── < 1 GB: Use PQ compression + HNSW, M = 8-16
├── 1-4 GB: M = 16, standard (for d ≤ 256)
├── 4-8 GB: M = 32 or high-dim vectors
└── > 8 GB: M = 48-64, maximum recall
12.2 Common Production Configurations¶
RAG / Semantic Search (LLM embeddings, d=1536):
M = 32, efConstruction = 200, efSearch = 128
Memory: ~6.5 GB per 1M vectors
Expected: 96% recall@10, ~250 QPS, ~4ms latency
E-commerce Product Search (d=256):
M = 16, efConstruction = 200, efSearch = 64
Memory: ~1.2 GB per 1M vectors
Expected: 95% recall@10, ~3000 QPS, ~0.3ms latency
Image Similarity (d=512):
M = 32, efConstruction = 400, efSearch = 200
Memory: ~2.3 GB per 1M vectors
Expected: 98% recall@10, ~500 QPS, ~2ms latency
Recommendation System (d=64, low latency critical):
M = 12, efConstruction = 100, efSearch = 32
Memory: ~0.4 GB per 1M vectors
Expected: 90% recall@10, ~12000 QPS, ~0.08ms latency
Safety-Critical (maximum recall):
M = 64, efConstruction = 800, efSearch = 1024
Memory: ~7+ GB per 1M vectors (d=128)
Expected: 99.9% recall@10, ~180 QPS, ~5.5ms latency
12.3 Known Limitations and Mitigations¶
┌─────────────────────────┬─────────────────────────────────────────────┐
│ Limitation │ Mitigation │
├─────────────────────────┼─────────────────────────────────────────────┤
│ Requires all data in │ Use HNSW+PQ to compress vectors │
│ RAM (no native disk) │ Or use DiskANN for disk-resident index │
│ │ Or use memory-mapped files (mmap) │
├─────────────────────────┼─────────────────────────────────────────────┤
│ Deletion is expensive │ Use tombstone marking + periodic rebuild │
│ (leaves holes in graph)│ Some implementations support lazy delete │
│ │ with neighbor repair │
├─────────────────────────┼─────────────────────────────────────────────┤
│ Insertion order affects│ Randomize insertion order │
│ graph quality │ Or use batch insertion with shuffling │
├─────────────────────────┼─────────────────────────────────────────────┤
│ Filtered search is │ Pre-filter + HNSW, or HNSW + post-filter │
│ not natively supported │ Or use partitioned HNSW per filter value │
│ │ (active research area) │
├─────────────────────────┼─────────────────────────────────────────────┤
│ Build time can be long │ Use parallel construction │
│ for large datasets │ Batch insertions with thread pools │
│ │ Start with lower efC, rebuild periodically│
├─────────────────────────┼─────────────────────────────────────────────┤
│ No exact guarantees │ HNSW is approximate — if exact needed, │
│ │ use HNSW as first stage + rerank with │
│ │ exact distance on top-K candidates │
├─────────────────────────┼─────────────────────────────────────────────┤
│ Single entry point │ Can become bottleneck with updates; │
│ is a SPOF for quality │ some implementations use multiple entry │
│ │ points or random restarts │
└─────────────────────────┴─────────────────────────────────────────────┘
12.4 HNSW in Production Vector Databases¶
┌────────────────────┬──────────┬─────────────────────────────────────────┐
│ Database │ HNSW │ Implementation Notes │
│ │ Variant │ │
├────────────────────┼──────────┼─────────────────────────────────────────┤
│ Pinecone │ Custom │ Proprietary HNSW with PQ, SSD tiering │
│ Weaviate │ hnswlib │ HNSW+PQ, disk-backed, ACORN filtering │
│ Milvus/Zilliz │ Custom │ HNSW, IVF-HNSW, GPU-accelerated │
│ Qdrant │ Custom │ HNSW with payload filtering, on-disk │
│ pgvector │ Custom │ PostgreSQL extension, in-process HNSW │
│ Elasticsearch │ Lucene │ HNSW in Apache Lucene (Java) │
│ ChromaDB │ hnswlib │ Python wrapper around hnswlib │
│ Redis (RediSearch)│ Custom │ HNSW integrated in Redis module │
│ Vespa │ Custom │ HNSW with real-time updates │
│ LanceDB │ Custom │ Disk-native HNSW with Lance format │
│ Oracle 26c │ Custom │ HNSW in Oracle Database kernel │
└────────────────────┴──────────┴─────────────────────────────────────────┘
Nearly every major vector database uses HNSW as the default index type.
Summary: HNSW at a Glance¶
┌─────────────────────────────────────────────────────────────────────────────┐
│ HNSW QUICK REFERENCE CARD │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Theoretical Basis: Skip List + Navigable Small World + Kleinberg theory │
│ │
│ Structure: Multi-layer proximity graph with O(log_M N) layers │
│ Layer 0 has all N nodes; layer k has N/M^k nodes │
│ │
│ Level Formula: l = floor(-ln(U) * mL), mL = 1/ln(M), U ~ Uniform(0,1)│
│ P(node at layer k) = 1/M^k │
│ │
│ Insert: Greedy descent (ef=1) to target layer, then beam search │
│ (ef=efConstruction) + connect at each layer down to 0 │
│ │
│ Search: Greedy descent (ef=1) through upper layers, then beam search │
│ (ef=efSearch) at layer 0, return top-K from candidates │
│ │
│ Neighbors: Simple = M closest; Heuristic = M diverse (prefer far-apart) │
│ Heuristic is critical for clustered data │
│ │
│ Parameters: M = 16-32 (connections), efC = 200 (build), ef = 64-256 │
│ M_max0 = 2*M at layer 0 │
│ │
│ Complexity: Search = O(d * M * log N) Build = O(N * efC * M * d * logN│)
│ Memory = N * (4d + 8M + 20) bytes │
│ │
│ Performance: 95% recall@10 at ~4000-5000 QPS on SIFT1M (d=128) │
│ 99% recall@10 at ~700-1000 QPS on SIFT1M │
│ │
│ Strengths: Dimension-independent scaling, incremental insert, │
│ consistent across data distributions, simple to tune │
│ │
│ Weaknesses: Memory-hungry (all in RAM), deletion is complex, │
│ filtered search is hard, build time for large datasets │
│ │
│ Original Paper: Malkov & Yashunin (2016/2018), arXiv:1603.09320 │
│ Reference Impl: github.com/nmslib/hnswlib (C++ with Python bindings) │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
References¶
- Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE TPAMI. arXiv:1603.09320.
- Kleinberg, J. M. (2000). Navigation in a small world. Nature, 406(6798), 845.
- Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393(6684), 440-442.
- Pugh, W. (1990). Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676.
- Malkov, Y., Ponomarenko, A., Logvinov, A., & Krylov, V. (2014). Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45, 61-68.