Approximate Nearest Neighbor Search: How HNSW Graphs Work

Semantic search, recommendations and retrieval all end with the same question: which stored vectors are closest to this one? Comparing against all of them is correct and, at scale, far too slow. The most widely used answer is a graph index, best known as HNSW, short for Hierarchical Navigable Small World. This article shows how such a graph is searched, where the "approximate" comes from, and the dial that trades it against speed.

The problem it solves

Exact nearest neighbour search scores the query against every stored vector: n vectors of d numbers cost n × d multiplications per query. Fine for ten thousand vectors, hopeless for a billion at hundreds of queries a second.

An approximate nearest neighbour (ANN) index looks at a small fraction of the collection and accepts occasionally missing the true best match. The vector database article builds the other common family, the inverted file, which scans only the closest few cells. A graph index has no cells, just links.

The intuition

Link every vector to a handful of its nearest neighbours. To search, enter at a fixed node, measure the query's distance to each neighbour, and hop to the closest. Repeat until no neighbour improves. That is a greedy walk, and since each hop moves strictly closer, it is short.

The catch is the stopping rule. "No neighbour is closer" means a local minimum, not necessarily the global one: a closer vector can sit behind a node the walk measured but never stepped onto. The fix is breadth. Keep the ef best candidates found so far, and keep expanding them while any could still improve. A bigger ef, the search breadth, finds more true neighbours and computes more distances: an explicit recall-versus-speed dial.

HNSW adds layers. Each vector gets a random top layer, so each layer up holds only a small fraction of the vectors (from memory: drawn from an exponentially decaying distribution). The sparse top layers have long links. A search crosses them greedily in a few hops, dropping down each time, and reaches the dense bottom layer already near the answer.

Quality is measured as recall@k: of the true k nearest, found by exact search on sample queries, what fraction did the index return?

Watch it run

The animation opens on the cost being avoided: exact search compares the query with every stored vector, and at a billion vectors that is the whole cost. Instead, each vector is linked to a few near neighbours, and that graph is the index. A search enters at a fixed node and measures only its neighbours: v1 at distance 0.61, v2 at 0.44. It hops to v2 and asks again: v3 at 0.31, v4 at 0.52. Every hop strictly improves, so the walk is short: v3, then v5 at 0.22. No neighbour of v5 is closer, so the walk returns v5 after seven distance computations out of a billion. Except v9, at 0.18, was closer. It hangs off v1, which the walk measured but never visited: that is the approximate. Widen the search and more candidates stay alive, so fewer true neighbours are lost, for more comparisons. The upper layers repeat the idea: sparse long links to cross the space, then the dense layer to finish.

The code

A toy model, not a production index: 2,000 random points in two dimensions, each linked to its six nearest neighbours, found by brute force. The search keeps the ef best candidates in a heap and counts every distance it computes; ef = 1 is the plain greedy walk:

import heapq
import math
import random

def dist(a, b):
    return math.dist(a, b)

def knn_graph(points, m):
    """Link every point to its m nearest others (found by brute force), both ways."""
    links = {i: set() for i in range(len(points))}
    for i, p in enumerate(points):
        near = sorted((j for j in range(len(points)) if j != i), key=lambda j: dist(p, points[j]))[:m]
        for j in near:
            links[i].add(j)
            links[j].add(i)
    return links

def search(points, links, q, entry, ef):
    """Best-first walk keeping the ef closest candidates found so far. ef=1 is plain greedy."""
    seen = {entry: dist(q, points[entry])}
    frontier = [(seen[entry], entry)]                  # min-heap: next node to expand
    best = [(-seen[entry], entry)]                     # max-heap of the ef best so far
    while frontier:
        d, node = heapq.heappop(frontier)
        if d > -best[0][0]:                            # nothing left that could improve
            break
        for nb in links[node]:
            if nb in seen:
                continue
            seen[nb] = dist(q, points[nb])             # one distance computation
            if len(best) < ef or seen[nb] < -best[0][0]:
                heapq.heappush(frontier, (seen[nb], nb))
                heapq.heappush(best, (-seen[nb], nb))
                if len(best) > ef:
                    heapq.heappop(best)
    return sorted((-d, i) for d, i in best), len(seen)

rng = random.Random(38)
points = [(rng.random(), rng.random()) for _ in range(2000)]
links = knn_graph(points, 6)
queries = [(rng.random(), rng.random()) for _ in range(200)]

def exact(q):
    return min(range(len(points)), key=lambda i: dist(q, points[i]))

truth = [exact(q) for q in queries]
for ef in (1, 4, 16, 64):
    hits = computed = 0
    for q, t in zip(queries, truth):
        found, n = search(points, links, q, 0, ef)
        hits += found[0][1] == t
        computed += n
    print(ef, f"recall@1={hits / len(queries):.2f}", f"distances={computed / len(queries):.0f}")
# 1 recall@1=0.60 distances=54
# 4 recall@1=0.94 distances=83
# 16 recall@1=1.00 distances=98
# 64 recall@1=1.00 distances=148

Greedy finds the true nearest point 60% of the time. With ef = 16 it finds all 200, after about 98 distance computations instead of 2,000. Now one sparse layer on top, 60 random points with their own links, crossed greedily before the bottom-layer search starts where it landed:

upper_ids = sorted(rng.sample(range(len(points)), 60))
upper_pts = [points[i] for i in upper_ids]
upper_links = knn_graph(upper_pts, 4)

def layered(q, ef):
    top, n_top = search(upper_pts, upper_links, q, 0, 1)
    start = upper_ids[top[0][1]]
    found, n = search(points, links, q, start, ef)
    return found, n_top + n

for name, fn in (("flat", lambda q: search(points, links, q, 0, 4)), ("layered", lambda q: layered(q, 4))):
    hits = computed = 0
    for q, t in zip(queries, truth):
        found, n = fn(q)
        hits += found[0][1] == t
        computed += n
    print(name, f"recall@1={hits / len(queries):.2f}", f"distances={computed / len(queries):.0f}")
# flat recall@1=0.94 distances=83
# layered recall@1=0.95 distances=52

Same breadth, about the same recall, 37% fewer distance computations: the long hops did the travelling. The seeded check covers 300 random graphs. Returned distances must be real and sorted, greedy must stop at a genuine local minimum, and on a connected graph ef = n prunes nothing, so it must match brute force:

def connected(links):
    seen, stack = {0}, [0]
    while stack:
        for nb in links[stack.pop()]:
            if nb not in seen:
                seen.add(nb)
                stack.append(nb)
    return len(seen) == len(links)

ok, checked = True, 0
for seed in range(300):
    r = random.Random(seed)
    pts = [(r.random(), r.random()) for _ in range(r.randint(2, 60))]
    g = knn_graph(pts, r.randint(1, 4))
    q = (r.random(), r.random())
    ef = r.randint(1, 8)
    found, n = search(pts, g, q, r.randrange(len(pts)), ef)
    ok &= all(abs(d - dist(q, pts[i])) < 1e-12 for d, i in found) and found == sorted(found)
    ok &= len(found) <= ef and n <= len(pts)
    if ef == 1:                                        # greedy stops at a local minimum
        d0, i0 = found[0]
        ok &= all(dist(q, pts[j]) >= d0 for j in g[i0])
    if connected(g):
        checked += 1
        all_in, _ = search(pts, g, q, 0, len(pts))     # ef = n: nothing is ever pruned
        ok &= all_in[0][1] == min(range(len(pts)), key=lambda i: dist(q, pts[i]))
print(ok, checked)                                     # True 157

The complexity

• Exact search: O(n × d) per query.
• Graph search: roughly ef × links per node × hops distance computations; with layers, hops grow slowly with n in practice. There is no worst-case guarantee.
• Build: each insert is itself a search for the new vector's neighbours, so building is the slow, memory-hungry part. Links live in memory beside the vectors.

Where it goes wrong

• Never measuring recall. A miss returns a slightly worse answer, not an error. Track recall@k against exact answers for sample queries.
• Too small an ef. Greedy above misses 40% of the time.
• Deletes. Removing a node cuts paths through it; many implementations only mark it deleted and repair or rebuild later (from memory).
• Fresh inserts. A vector is invisible until it is linked in.
• Filters. Skipping filtered-out nodes can strand the walk where nothing is allowed.

When it shows up in interviews

In ML system design, as the retrieval layer of RAG or "find similar items among a billion products", and whenever someone says "use a vector database". Expect recall versus latency, memory, deletes and filtering. As of October 2026, layered graph indexes of the HNSW kind are a default in dedicated vector databases and in vector extensions for relational databases; the original paper dates from 2016 (from memory).

How to say it in an interview

"Exact search is linear, so I'd use a graph index like HNSW. Each vector links to a few near neighbours; a query enters at a fixed node and greedily hops to the closer neighbour until nothing improves. That can stop at a local minimum, so it's approximate. The search breadth, ef, keeps more candidates alive: higher recall, more distance computations. Sparse upper layers with long links get the walk close in a few hops. I'd tune ef against recall@k measured with exact search on sample queries, and plan for build time, memory and deletes."