HNSW Math

The problem: approximate nearest neighbor search

Embeddings turn text, images, or users into vectors in R^d (commonly d = 384 to 1536). ‘Similar’ means ‘close’ under a metric — Euclidean distance or, after normalization, cosine. k-nearest-neighbor search asks for the k stored vectors closest to a query q.

Exact search compares q against all N vectors: O(N·d) per query. At N = 10^9 that is a billion distance computations per lookup — far too slow. The escape is to accept approximate answers. We measure quality by recall@k: of the true k neighbors, what fraction did we return? Recall of 0.95 means 19 of the true top 20. An ANN index buys a large latency reduction for a small, tunable recall loss. HNSW is the graph-based approach that sits at the best point of that trade for most workloads, which is why it is the default index in FAISS, pgvector, Qdrant, and Milvus.

A proximity graph you can walk

The core idea predates the hierarchy: build a graph where each node is a vector and each edge links a vector to some of its near neighbors. To answer a query, do greedy routing — stand at some node, look at its neighbors, step to whichever is closest to q, and repeat until no neighbor is closer. You have descended a distance landscape toward q without ever touching most of the dataset.

The catch is what kind of graph makes this walk both fast and accurate. Only short local edges is accurate but slow: reaching a far region takes many small hops. Random long edges traverse fast but greedy routing gets stuck in local minima. The answer is a navigable small-world (NSW) graph, which mixes both: dense short-range links that pin down the local neighborhood, plus a few long-range links that act as highways across the space. That mixture is what makes greedy hops scale like log N instead of N — the same small-world property as six-degrees-of-separation in social networks, where mostly-local ties plus a few far-flung ones collapse the graph diameter to logarithmic. The flat NSW graph delivers this on average, but greedy routing can still stall in a local minimum and the entry point is arbitrary, so worst-case paths run long. The hierarchy in HNSW exists to make the long-range structure explicit and the descent reliable rather than lucky.

The hierarchy: a skip list over the graph

HNSW stacks several NSW graphs into layers, exactly like a skip list generalizes a linked list. Layer 0 at the bottom contains every vector with the densest connectivity. Each layer above holds an exponentially thinning random subset, connected by longer-range edges, until the top layer holds a handful of nodes or one.

A vector present in layer ℓ also appears in every layer below it, so the layers are nested. Search starts at the single entry point in the top layer, where a few nodes span the whole space, and greedily routes to the closest node there. That node becomes the entry point for the next layer down, denser and finer, and so on to layer 0. The upper layers are highways that carry you into the right region in a few coarse hops; layer 0 is the local street map where the actual k neighbors are resolved. The hierarchy turns ‘get lucky with long edges’ into a deterministic coarse-to-fine funnel.

Probabilistic layer assignment

Which layers does a new vector join? Not by design but by a coin flip. On insertion, each element is assigned a maximum level ℓ drawn from an exponentially decaying distribution:

ℓ = floor( −ln(U) · mL ),   U ~ Uniform(0,1]

mL = 1 / ln(M)      (the level-generation constant)

P(node reaches layer ℓ)  ∝  exp(−ℓ / mL)  =  M^(−ℓ)

The element is then inserted into layers 0 through ℓ. Because the level is geometric with ratio 1/M, each layer up holds about 1/M of the layer below it — the same thinning a skip list uses. The choice mL = 1/ln(M) is not arbitrary: the paper shows it minimizes expected hops by making the expected work per layer roughly constant, so the layers overlap just enough for a smooth descent. Most vectors get ℓ = 0 and live only at the bottom; a vanishing fraction float up to become the highways. No global rebuild is ever needed — the structure is a statistical consequence of the draw.

The search procedure

Search has two phases. From the top layer down to layer 1, it runs a greedy single-best walk (dynamic list size ef = 1): find the closest node here, drop to the next. At layer 0 it switches to a beam search with a candidate list of size ef (efSearch), keeping the ef best-so-far and exploring their neighbors until no improvement remains — the routine SEARCH-LAYER:

SEARCH-LAYER(q, entry_points, ef, layer):
  visited  = set(entry_points)
  candidates = min-heap by dist(·, q)   # frontier to expand
  found      = max-heap by dist(·, q)   # ef best so far
  push entry_points into both
  while candidates not empty:
    c = pop nearest from candidates
    f = farthest in found
    if dist(c,q) > dist(f,q): break        # can't improve
    for e in neighbors(c, layer):
      if e not in visited:
        visited.add(e)
        if dist(e,q) < dist(f,q) or |found| < ef:
          push e into candidates and found
          if |found| > ef: pop farthest from found
  return found

Returning the top k of found gives the answer. The one query-time knob is ef: larger widens the beam, raising recall and latency together (it must be at least k).

Why search is O(log N)

The cost has two factors: how many layers the descent crosses, and the work per layer. The number of layers is the expected top level, O(log_M N) — because each layer thins by 1/M, the tower height is proportional to log N. Within a layer, greedy routing on a navigable small-world graph reaches its local target in an expected constant number of hops, each hop examining at most the node’s degree (bounded by M) neighbors:

layers          ≈  log_M(N)
work per layer   ≈  O(M)          (bounded degree, ~constant hops)
total search     ≈  O(M · log N)  =  O(log N)   for fixed M

State this honestly as an expected scaling under the small-world assumption, not a proven worst-case bound — adversarial data can degrade it. But in practice the logarithmic curve holds across many orders of magnitude of N, which is why HNSW scales to billions of vectors. Construction follows: inserting N elements, each a search plus linking, is O(N log N).

Insertion and neighbor selection

Inserting a vector reuses the search machinery. Draw its level ℓ. From the top entry point, greedily descend with ef = 1 to layer ℓ+1. Then, in each layer from ℓ down to 0, run SEARCH-LAYER with the wider list efConstruction to gather candidates, select up to M of them, and add bidirectional edges; if a neighbor now exceeds its degree cap it is pruned back.

Which M neighbors to keep is the subtle part. Taking simply the M closest tends to cluster all edges on one side of a dense blob, leaving regions disconnected. HNSW instead uses a diversity heuristic: it keeps a candidate only if it is closer to the new node than to any already-selected neighbor, spreading edges in different directions. This preserves the long-range links that make the graph navigable and prevents dead-end clusters. efConstruction controls how many candidates this selection sees: larger means a better-connected graph and higher recall, at the cost of slower builds. It does not affect query latency once the index exists.

The parameters and the trade-off surface

Three numbers place you on the recall–latency–memory surface:

The clean separation is the point: M and efConstruction are baked in at build time, while ef is dialed at query time, so you trade recall for latency per request without rebuilding. Memory is the third axis and is dominated by edges. Layer 0 gives each node up to Mmax0 = 2M links; upper layers use Mmax = M. Since almost all nodes live only in layer 0, total link storage is roughly N · 2M edges — the graph overhead HNSW adds on top of the raw vectors. Typical defaults: M = 16, efConstruction = 200.

A worked example

Take N = 1,000,000 vectors of dimension d = 768 (float32) with M = 16. The level constant is mL = 1/ln(16) ≈ 0.36. Expected number of layers is about log_16(10^6) = ln(10^6)/ln(16) ≈ 5, and layer populations decay by roughly 1/M: about 10^6 at layer 0, ~62,500 at layer 1, ~3,900 at layer 2, and so on to a tiny top. A search touches on the order of a few hundred nodes total — five layers, a few greedy hops each, then an ef-wide sweep at the bottom — versus a million distance computations for brute force.

Memory: the vectors are N · d · 4 = 10^6 × 768 × 4 ≈ 2.9 GB. The graph adds about N · 2M links; at 4 bytes per neighbor id that is 10^6 × 32 × 4 ≈ 128 MB — a small surcharge over the vectors for roughly 10^4× fewer distance computations per query. That ratio is why HNSW won.

Practical notes and pitfalls

Memory, not compute, is usually the ceiling. HNSW keeps the full graph and vectors resident and does not page to disk gracefully, so it pairs with quantization — storing compressed vectors (product quantization or int8) to shrink the dominant vector footprint while keeping the graph for navigation. Deletions are awkward: removing a node can strand its neighbors, so implementations soft-delete (tombstone) and rebuild periodically. Recall is workload-dependent: the same ef gives different recall on clustered versus uniform data, so tune it against a labeled query set. And don’t over-set M: beyond ~32–48 the recall gains flatten while memory and build time keep climbing. Start at M = 16, efConstruction = 200, then raise ef until recall meets your target.