HNSW Internals — How the Index Is Built and Queried

Every vector database you'll touch — Pinecone, Qdrant, Weaviate, Milvus, pgvector — defaults to HNSW for ANN search. Once you understand it, you can tune it instead of guessing.

Skip-list intuition

Imagine you have a sorted linked list of one million items. Finding an item is O(N). A skip list adds shortcut layers: roughly half the items also live on layer 1, a quarter on layer 2, an eighth on layer 3, and so on. To search, you start at the top layer (small, sparse) and walk forward until you'd overshoot, then drop down a layer and repeat. Search becomes O(log N).

HNSW (Malkov & Yashunin 2018, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs") is a skip-list for vectors — except the layers aren't sorted lists, they're proximity graphs.

The data structure

• L+1 layers, indexed 0 (bottom, contains all points) to L (top, contains very few).
• Each point exists on layer 0 and on layers 1..ℓ where ℓ is randomly chosen at insertion (more on that below).
• On every layer a point is in, it has up to M undirected edges to other points on that layer. Edges encode "you are one of my approximate nearest neighbours".
• One designated entry point at the top layer is where every search starts.

Insertion algorithm

Pseudo-code (close to the paper):

insert(q):
  ℓ = floor(-ln(uniform(0, 1)) * mL)         # random level, geometric distribution
  ep = entry_point
  L_top = current_top_layer

  # Phase 1: greedy descend from L_top to ℓ+1.
  # Each layer: do a ef=1 greedy search to find the single closest neighbour, hop down.
  for layer in range(L_top, ℓ, -1):
      ep = greedy_search_layer(q, ep, ef=1, layer=layer)

  # Phase 2: at every layer from ℓ down to 0, find ef_construction candidates
  # and connect q to M of them.
  for layer in range(min(ℓ, L_top), -1, -1):
      W = greedy_search_layer(q, ep, ef=ef_construction, layer=layer)
      neighbors = select_neighbors_heuristic(q, W, M, layer)
      add_bidirectional_edges(q, neighbors)
      # prune over-connected neighbours back to M (or M_max0 on layer 0)
      for n in neighbors:
          if degree(n, layer) > M_layer:
              shrink_to_M(n, layer)
      ep = W

  if ℓ > L_top:
      entry_point = q
      L_top = ℓ

A few pieces deserve unpacking:

Why ℓ = floor(-ln(uniform()) * mL)?

This is the inverse CDF of the geometric distribution with parameter p = 1 - exp(-1/mL). With mL ≈ 1 / ln(M) (the paper's recommendation), each higher layer has roughly 1/M the points of the layer below — exactly the skip-list shape.

select_neighbors_heuristic — the trick that separates HNSW from a naive proximity graph

The naive choice of "M nearest" produces clusters: points near each other cluster, the graph develops bridges only by accident. The heuristic instead picks M neighbours that are not just close, but diverse in direction — preferring neighbours that aren't dominated by another, already-selected neighbour. This produces a graph with good navigability (short paths from anywhere to anywhere).

Pseudo-code:

select_neighbors_heuristic(q, candidates, M):
  R = []
  W = sorted(candidates, by=d(q, .))
  while W and len(R) < M:
      e = W.pop_smallest()
      if all(d(e, r) >= d(q, e) for r in R):
          R.append(e)         # e is closer to q than to any already-selected r
      # else discard — e is dominated by some r already in R
  return R

This is why HNSW recall is high even at small ef.

Pruning

When a neighbour's degree on a given layer exceeds the cap (M for layers > 0, M_max0 = 2 * M for layer 0), shrink it back using the same heuristic. Keeps the graph bounded.

Query algorithm

search(q, k):
  ep = entry_point
  for layer in range(L_top, 0, -1):
      ep = greedy_search_layer(q, ep, ef=1, layer=layer)
  W = greedy_search_layer(q, ep, ef=ef_search, layer=0)
  return top_k(W, k)

greedy_search_layer(q, ep, ef, layer):
  visited = {ep}
  candidates = MinHeap([(d(q, ep), ep)])
  W = MaxHeap([(d(q, ep), ep)])         # bounded to size ef
  while candidates:
      c = candidates.pop_min()
      if d(q, c) > W.peek_max() and len(W) >= ef:
          break                          # all remaining candidates farther than worst in W
      for e in neighbors(c, layer):
          if e in visited: continue
          visited.add(e)
          if d(q, e) < W.peek_max() or len(W) < ef:
              candidates.push(e)
              W.push(e)
              if len(W) > ef: W.pop_max()
  return W

The two heaps + ef cap are the dynamic candidate list. Larger ef_search = more neighbours explored = higher recall, more latency.

The three knobs

Production recipe: start with M=16, ef_construction=200, ef_search=100. Plot recall vs latency by sweeping ef_search from 32 to 512 on your eval set. Pick the inflection point.

Memory cost

Per node, layer 0: stores M up-edges + M down-edges + the vector. Total memory roughly:

bytes ≈ N × (vector_bytes + (M + M_max0) × 4)
       + sum over layers > 0 of (n_layer × M × 4)

For 10M float32 768-dim vectors with M=16:

• Vectors: 10M × 768 × 4 = ~30 GB.
• Edges: roughly 10M × 32 × 4 ≈ 1.3 GB.

Vectors dominate. If memory is the constraint, use smaller embeddings (Matryoshka truncation, or a 384-dim model) before tuning M.

Worked example — 8 vectors, 2D

Insert order: A, B, C, D, E, F, G, H. Random levels via the formula say A→2, B→0, C→1, D→0, E→0, F→1, G→0, H→0. So:

• Layer 2: {A}.
• Layer 1: {A, C, F}.
• Layer 0: {all 8}.

A is the entry point. When you query a new point Q:

1. Layer 2: only A. Hop down with A as ep.
2. Layer 1: greedy search from A. Suppose we find F is closer; ep = F.
3. Layer 0: ef_search candidates around F, return top-k.

Two hops in the upper layers, one fanout at layer 0. Sub-linear in N.

The IVF-PQ contrast

HNSW stores raw vectors and uses graph traversal. IVF-PQ does the opposite — it compresses vectors and uses a flat scan within partitions:

1. Coarse quantizer — k-means cluster all vectors into nlist centroids (e.g. nlist = sqrt(N)). Each vector is assigned to its nearest centroid.
2. PQ — split each (residual) vector into m sub-vectors, each quantised to one of 256 codewords (an 8-bit byte). A 768-dim float32 vector (3072 bytes raw) becomes m bytes — typically 16–96. 20–200× compression.
3. Query — find the nprobe nearest centroids, scan vectors only in those partitions, decode PQ on the fly to compute approximate distance.

Pinecone serverless uses DiskANN, which is a single-graph index designed to live on SSD, combining HNSW-style navigation with on-disk layout. ScaNN (Google Vertex) uses anisotropic PQ. They're all variations on the same two ideas: graph navigation, or partition + compress.