HNSW, From the Ground Up

How Hierarchical Navigable Small World graphs find nearest neighbours in microseconds: the two ideas they combine, how the graph is built, what M, efConstruction and efSearch really cost, and measured numbers from a 200,000-vector index.

HNSW (Hierarchical Navigable Small World graphs) is one of the most widely used indexes for finding similar vectors. Qdrant, Weaviate, pgvector and Elasticsearch all offer it, and several use it by default. It earns that place. On the index measured in this piece it returns 93% of the true top 10 in 0.085 ms, where checking every vector takes 1.39 ms, and the gap widens with every vector you add.

It is also an algorithm most people use as a black box with three knobs. This piece opens the box. HNSW is two older ideas glued together, and once you see both, every parameter stops being magic and becomes a trade you can reason about.

The problem: exact search does not scale#

Given a query vector, find the $k$ stored vectors closest to it. The exact answer means computing the distance to every one of the $N$ stored vectors, and each distance touches all $d$ coordinates: $O(N \cdot d)$ work per query. At 200,000 vectors of 128 dimensions that is 25.6 million coordinates to compare for every single query (for Euclidean distance, a subtract, a multiply and an add each). At 100 million vectors it is hopeless for anything interactive.

Approximate nearest-neighbour (ANN) search gives up a little accuracy for a lot of speed. Its quality is measured as recall@k: of the true $k$ nearest neighbours, what fraction did the index return? Recall 0.95 at $k = 10$ means that, on average, 9.5 of the 10 results are the true top 10.

ANN methods come in a few families:

These families solve different problems and are often combined. Partitioning decides which vectors to look at; quantisation makes looking at each one cheaper. Faiss's popular IVF-PQ index is both: IVF picks the clusters, PQ compresses the vectors inside them. HNSW is also frequently paired with quantisation, as the memory section below explains.

Trees break down in high dimensions and hashing needs many tables to reach high recall. Graphs have led public ANN benchmarks for years, and HNSW is the graph method most systems ship.

A detour through sorted data#

Before vectors, start with something easier: a sorted list of numbers.

3   5   7   11   14   19   21

How fast can we find 19, and how cheaply can we insert 13? Three data structures give three different answers.

A sorted array supports binary search. Look at the middle element (11). 19 is bigger, so throw away the left half and repeat on 14 19 21. The middle of that is 19: found. Each step halves what is left, so a search takes $O(\log n)$ steps. A million sorted numbers need about 20 comparisons.

But inserting into an array is slow. To put 13 between 11 and 14, every element after it has to shift one place to the right. That is $O(n)$ work per insert.

A linked list is the opposite. Each element points to the next, so inserting 13 means changing two pointers: 11 now points to 13, and 13 points to 14. That is $O(1)$, once you know where to insert. The catch is finding that place: a linked list has no middle you can jump to, so you walk from the start, one element at a time. Search is $O(n)$.

So if your data is sorted and rarely changes, a plain array with binary search is hard to beat. The skip list exists for data that is both searched and changed often: it keeps the cheap pointer updates of a linked list and adds a way to jump.

Idea 1: the skip list#

A skip list (William Pugh, 1990) is a sorted linked list with express lanes. The bottom level holds every element in order. Each level above holds a random subset of the level below (typically half), so the top levels have few elements and links that jump far.

To find a key, start at the top-left and move right while the next key is not past your target. When it would overshoot, drop one level and continue. The top levels cover most of the distance in a few long jumps; the bottom level does the final precise steps. Search and insertion both take $O(\log N)$ expected time, and nothing is ever rebalanced: each element's height is decided once, by a coin flip, when it is inserted.

Keep two properties in mind, because HNSW copies both: long links on sparse upper levels, short links on the dense bottom level, and a random height per element.

Is a skip list only for sorted data?#

Yes. Every step of the search is a comparison: "is the next key bigger than my target?" If it is, moving right would overshoot, so you drop down. That question only makes sense when the keys have an order, $3 < 5 < 7 < 11 < \dots$. Binary search needs the same thing.

Vectors have no such order. Take three embeddings:

A = [0.12, 0.91, ..., 0.32]
B = [0.88, 0.04, ..., 0.51]
C = [0.42, 0.72, ..., 0.18]

There is no useful way to say $A < B < C$. You could sort them by their first coordinate, or by their length, but two vectors that end up side by side in that order can still point in completely different directions in the other 127 dimensions. What vectors do have is distance: $\text{dist}(A, C) = 0.2$ is small, $\text{dist}(A, B) = 0.8$ is large. Nearest-neighbour search asks "which stored vectors are closest to my query?", not "which key is bigger or smaller?"

That is why binary search and skip lists cannot be used on vectors directly. HNSW keeps the skip list's layers, and replaces its comparison with a distance:

The next idea supplies the missing piece: a structure where "move closer" works the way "move right" does in a skip list.

Idea 2: navigable small world graphs#

A skip list works for one-dimensional keys, which have an order. Vectors have no order, only distances. The graph answer is a proximity graph: every vector is a vertex, linked to a handful of vectors near it (its friends). To search, walk it greedily:

1. Start at an entry vertex.
2. Look at the current vertex's friends. Move to whichever one is closest to the query.
3. Stop when no friend is closer than where you are. That vertex is your answer.

The graph is navigable when this greedy walk reaches the right place in few hops. What makes that possible is a mix of short links, which make the final approach precise, and long-range links, which cross the space quickly. In the figure the walk from A jumps across the graph on a long link to F in one hop, then closes in through I to J with short ones. Without long links, the same walk would crawl through every vertex in between.

Why short links alone get stuck#

The obvious graph links every vector to its few nearest neighbours and nothing else. Greedy search on that graph fails in a specific way: it can walk into a dead end, a vertex whose neighbours are all farther from the query than it is, even though the true answer is somewhere else.

Greedy search only ever moves closer, so it never takes the step away from the query that the route through c needs. The fix is not a smarter walk; it is a better graph. A single long link from b towards N removes the dead end. Long links across the space are what make a graph navigable.

Navigable Small World (NSW) graphs, introduced by Yury Malkov and colleagues in the early 2010s, get those long links for free: vectors are inserted one at a time, each linked to its nearest neighbours among the vectors already inserted. Early vectors are linked when the graph is sparse, so their links are long; later vectors are linked when it is dense, so theirs are short.

NSW has two weaknesses:

• Local minima still happen. Fewer, but they do: more friends per vertex lowers the risk but makes every hop more expensive.
• Hubs. The early vertices collect huge friend lists, and the walk spends much of its time scanning them. Search cost grows polylogarithmically instead of logarithmically.

HNSW: a skip list made of graphs#

HNSW (Malkov and Yashunin, 2016) fixes both by applying the skip-list idea to NSW. Instead of one graph that mixes long and short links, it builds a stack of graphs:

• Layer 0 holds every vector, linked to its close neighbours: short links, precise.
• Each layer above holds an exponentially smaller random subset, so its links, measured between far fewer vectors, are long.
• The entry point is a vector on the top layer.

Search walks the stack top down. On each upper layer it runs the greedy walk to a local minimum using only the closest vertex (a beam of width 1), then drops that vertex down one layer and starts again from it. On layer 0 it widens the beam to efSearch candidates and returns the best $k$.

The top layers do the long-distance travel in a few hops over very few vertices; layer 0 does the local refinement. Because the number of vertices shrinks geometrically going up, the number of hops grows slowly with $N$, close to logarithmically in practice on well-behaved data. Each vector also has a capped number of links per layer, and upper-layer links are chosen among vectors at that layer's scale, so HNSW avoids the uncontrolled high-degree hubs that plain NSW grows.

Searching one layer#

The core routine is a best-first search that keeps two heaps: candidates still to expand (closest first) and the results found so far (worst first, capped at ef).

import heapq

def search_layer(q, entry_points, ef, graph, dist):
    """Best-first search on one layer. Returns up to ef (distance, node) pairs, closest first."""
    visited = set(entry_points)
    candidates = [(dist(q, e), e) for e in entry_points]  # min-heap: closest first
    heapq.heapify(candidates)
    results = [(-d, e) for d, e in candidates]            # max-heap: farthest first
    heapq.heapify(results)

    while candidates:
        d, c = heapq.heappop(candidates)
        if d > -results[0][0]:        # the best unexpanded candidate is worse than our worst result:
            break                     # nothing left can improve the answer
        for n in graph[c]:            # c's neighbour list on this layer
            if n in visited:
                continue
            visited.add(n)
            dn = dist(q, n)
            if len(results) < ef or dn < -results[0][0]:
                heapq.heappush(candidates, (dn, n))
                heapq.heappush(results, (-dn, n))
                if len(results) > ef:
                    heapq.heappop(results)  # drop the current worst
    return sorted((-d, n) for d, n in results)


def search(q, index, k, ef_search):
    ep = [index.entry_point]
    for layer in range(index.max_layer, 0, -1):   # upper layers: beam of 1, just descend
        ep = [search_layer(q, ep, 1, index.graphs[layer], index.dist)[0][1]]
    hits = search_layer(q, ep, max(ef_search, k), index.graphs[0], index.dist)
    return hits[:k]

ef is the beam width. With ef = 1 this is exactly the greedy walk from the figure. A larger ef keeps more alternatives alive, so the search can escape a local minimum through a slightly worse vertex that leads somewhere better. That single number is the recall knob you turn at query time.

Building the graph#

Vectors are inserted one at a time. Each insertion does three things.

1. Pick the vector's top layer at random. Like the coin flips in a skip list, the level is drawn from an exponentially decaying distribution:

The vector then lives on layer $\ell$ and every layer below it. This gives $P(\ell \ge l) = e^{-l / m_L}$. The paper's recommended normalisation is $m_L = 1 / \ln M$, which makes each layer hold $1/M$ of the layer below. With $M = 32$, only 1 vector in 32 reaches layer 1, 1 in 1,024 reaches layer 2, and so on.

It really is that simple. Here is the level distribution Faiss produced when building a 200,000-vector index with $M = 32$, next to what the formula predicts:

The single vector on layer 4 is the entry point. Five layers are enough for 200,000 vectors, and a billion would need only about seven: the top layer index grows as $\ln N / \ln M$.

2. Find the insertion point. Starting from the entry point, descend through the layers above $\ell$ with a beam of 1, exactly like a search. From layer $\ell$ down to layer 0, switch to a beam of efConstruction to collect a good list of candidate neighbours on each layer.

3. Choose the neighbours and link both ways. From the candidates, pick up to M neighbours and add bidirectional links. If a neighbour now has too many links (more than $M_{max} = M$ on upper layers, or $M_{max0} = 2M$ on layer 0), prune its list back down.

Layer 0 gets twice the links because it is where the precise search happens and where every vector lives.

The neighbour-selection heuristic#

Picking the $M$ closest candidates sounds right and works badly on clustered data: all $M$ links land inside the same tight cluster, and the graph loses the links that lead out of it. HNSW uses a diversity rule instead. Keep a candidate only if it is closer to the new vector than to every neighbour already kept:

def select_neighbors(q, candidates, M, dist):
    """candidates: (distance to q, node) pairs. Prefer neighbours in different directions."""
    kept = []
    for d_q, c in sorted(candidates):
        if all(d_q < dist(c, other) for other in kept):
            kept.append(c)
        if len(kept) == M:
            break
    return kept

A candidate that sits behind an already-kept neighbour is reachable through that neighbour anyway, so a link to it is wasted. Skipping it spends the link budget on other directions, including the bridges between clusters that greedy search depends on.

What the three knobs cost#

HNSW has three parameters. Two are fixed when you build the index; one you choose per query. In plain words: M is how many roads each vector gets, efConstruction is how carefully those roads are planned, and efSearch is how many routes a search keeps open at once.

To see the trade-offs as numbers, I built Faiss IndexHNSWFlat indexes over 200,000 vectors of 128 dimensions and searched them with 1,000 held-out queries, measuring recall@10 against exact brute-force results. The vectors are synthetic but shaped like real embeddings: points on a 24-dimensional subspace embedded in 128 dimensions, plus a little noise. Build times use 8 threads; query times use a single thread on an Apple M5 Pro. Your data will give different absolute numbers; the shapes are what transfer.

efSearch: the query-time dial#

Recall@10, and milliseconds per query, with efConstruction = 128:

Three things to read off this table:

• Latency is roughly linear in efSearch. Doubling the beam roughly doubles the work, at every M.
• Recall saturates. At M = 16, going from 64 to 128 buys 5 points; going from 128 to 256 buys under 2 for twice the cost.
• Compare at equal latency, not equal efSearch. Higher M looks far better per efSearch value, but each hop scans more links. Around 0.08 ms, M = 16 at efSearch 64 (0.926) and M = 64 at efSearch 32 (0.927) are the same. Higher M earns its keep at the high-recall end, and M = 8 never catches up at all: the graph is too sparse to escape local minima.

For scale: exact search over the same 200,000 vectors, one query at a time on one thread, took 1.39 ms. HNSW at M = 16, efSearch = 64 took 0.085 ms at 0.93 recall, 16 times faster. The gap widens with size: brute force scales linearly with $N$, while a well-tuned HNSW index typically shows close to logarithmic growth in practice (how close depends on the data, M, efSearch and the recall target).

efConstruction: pay once, at build time#

With M = 16 and efSearch fixed at 32:

A better-built graph gives better recall at the same query cost: 18 points between 16 and 128, with no change in query time. So efConstruction is not only a build-time setting: it decides how good the graph is, and therefore how much recall every later query can get. Then it plateaus. Doubling efConstruction from 128 to 256 doubled the build time for less than half a point. Around 100 to 200 is where most production defaults sit, and this curve shows why.

Memory: the vectors, not the graph#

Measured index size, against 102.4 MB of raw float32 vectors:

The pattern is exact enough to use as a formula. Per vector, an HNSW index stores

With 128 dimensions and M = 16 the links are a fifth of the index. With the 1,536-dimensional embeddings typical of modern embedding models, the vector alone is 6,144 bytes and the M = 16 links are 128: about 2% of the total. At that point M barely matters for memory. What matters is storing the vectors themselves compactly, which is why production systems pair HNSW with scalar or product quantisation, or keep the full vectors on disk and only the graph in RAM.

A tuning recipe#

1. Start at M = 16, efConstruction = 128. It is a strong default for most embedding workloads.
2. Build a ground-truth set. Take about 1,000 real queries and compute their exact top-k once with brute force. Without this you are tuning blind.
3. Sweep efSearch upwards from $k$ and pick the smallest value that meets your recall target. This needs no rebuild, so it is cheap to revisit.
4. If the target needs efSearch in the hundreds, rebuild with a higher M (32, then 48 or 64) and sweep again at equal latency, not equal efSearch.
5. Raise efConstruction only until recall stops moving. It is paid at build time and for every re-index, so there is no point overshooting the plateau.
6. Plan memory from the formula, and quantise the vectors if $4d$ dominates.

Where HNSW bites#

• Recall decays as the index grows. Settings that give 0.95 at a million vectors can give less at a hundred million. Re-measure after large ingests, not just at launch.
• Filters fragment the graph. A restrictive metadata filter removes most vertices from the walk, and the remaining ones may not be connected. Engines handle this with filter-aware traversal, payload indexes or a fallback to exact search for small candidate sets; know which one yours uses.
• Deletes are tombstones. Removing a vector from a graph is hard, so most implementations mark it deleted and skip it. Heavy churn slowly degrades the graph until you rebuild or compact.
• efSearch must be at least k. Most libraries silently raise it, but a beam narrower than the number of results you want cannot return them.
• It wants fast random access. A graph walk jumps to unpredictable places in memory, so HNSW is fastest when the graph and the vectors it touches are in RAM, and that is expensive at scale. Engines soften this with quantised vectors in memory, memory-mapped or on-disk storage for the full vectors, or both. Expect some latency cost when data comes from disk.

Summary#

HNSW is a skip list whose levels are proximity graphs: it keeps the skip list's coarse-to-fine layers and swaps "move right while the key is smaller" for "move to the neighbour closer to the query". Sparse upper layers with long links get the search to the right neighbourhood in a few hops; the dense bottom layer, with a wider beam, finds the precise answer. Each vector's height is a single random draw, and each vector's links are chosen for diversity rather than raw closeness.

That structure explains the knobs. M is graph density: recall per hop against memory and time per hop. efConstruction is graph quality, paid once and plateauing quickly. efSearch is the beam you trade for latency on every query, and the one you should tune against a ground-truth set.

For HNSW implemented from scratch in Python, with parameter sweeps, recall degradation and filtered search measured, see Chapter 22 of the RAG book.

References#

1. Y. Malkov, D. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018 (arXiv:1603.09320).
2. W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 1990.
3. Y. Malkov, A. Ponomarenko, A. Logvinov, V. Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45, 2014.
4. M. Aumüller, E. Bernhardsson, A. Faithfull. ANN-Benchmarks: a benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87, 2020 (ann-benchmarks.com).
5. Faiss, the library used for the measurements above.

"""HNSW measurements: recall@10 and latency over M, efSearch and efConstruction."""
import time
import numpy as np
import faiss

rng = np.random.default_rng(7)
N, NQ, D, LATENT, K = 200_000, 1_000, 128, 24, 10

# Synthetic vectors with low intrinsic dimension, like real embeddings.
proj = rng.standard_normal((LATENT, D)).astype("float32")
def sample(n):
    z = rng.standard_normal((n, LATENT)).astype("float32")
    return z @ proj + 0.1 * rng.standard_normal((n, D)).astype("float32")

xb, xq = sample(N), sample(NQ)
flat = faiss.IndexFlatL2(D)
flat.add(xb)
_, gt = flat.search(xq, K)                     # exact ground truth

def recall(I):
    return np.mean([len(set(I[i]) & set(gt[i])) / K for i in range(NQ)])

def build(M, ef_construction):
    faiss.omp_set_num_threads(8)
    index = faiss.IndexHNSWFlat(D, M)
    index.hnsw.efConstruction = ef_construction
    t = time.perf_counter(); index.add(xb)
    return index, time.perf_counter() - t

def search(index, ef_search):
    faiss.omp_set_num_threads(1)
    index.hnsw.efSearch = ef_search
    t = time.perf_counter(); _, I = index.search(xq, K)
    return recall(I), (time.perf_counter() - t) * 1000 / NQ   # recall, ms per query

for M in (8, 16, 32, 64):
    index, secs = build(M, 128)
    size_mb = len(faiss.serialize_index(index)) / 1e6
    print(f"M={M}: built in {secs:.1f}s, {size_mb:.1f} MB")
    for ef in (10, 16, 32, 64, 128, 256):
        r, ms = search(index, ef)
        print(f"  efSearch={ef:<4} recall@10={r:.3f}  {ms:.3f} ms/query")

levels = faiss.vector_to_array(index.hnsw.levels) - 1   # Faiss stores level + 1
print("vectors per layer:", np.bincount(levels))