Skip to content
AI360XpertBeta

Hierarchical Navigable Small World (HNSW)

HNSW stacks your vectors into layers of graphs: almost empty on top for long jumps, crowded at the bottom for close inspection, so each query skips far before it looks closely.

A query hops to its closest neighbor in the sparse top layer, then drops to the dense base layer where D wins at 1.41 over C at 2.00
A query hops to its closest neighbor in the sparse top layer, then drops to the dense base layer where D wins at 1.41 over C at 2.00

Why Does This Exist?

Checking every vector against your query is the honest approach, and it has a name: exact search. Say you hold NN vectors (NN is your collection size) with dd numbers each (dd is the embedding dimension). One query then costs on the order of N×dN \times d operations. You will not feel that at ten thousand vectors. You will feel it at ten million, inside a chat answer that must arrive now, which is exactly where retrieval usually sits.

So production systems accept a bargain with a name too: approximate nearest neighbor (ANN) search. Skip most of the collection, still land on the right answer almost every time. The parent page spells out that bargain in approximate nearest neighbor search. What you compare still matters, so if distance feels fuzzy, read similarity metrics first. And if you have never turned text into vectors, start with embeddings.

This page covers the layered graph behind many fast searches: how a query walks it, and the two knobs that set its recall. The system around the index, with its filters, tenants, and restarts, lives in vector databases. The compression-first rival lives in IVF and product quantization.

Think of It Like This

Express highways, then local streets

You are driving to one house in a faraway city. You do not crawl street by street from your driveway. You join the interstate, skip hundreds of exits at speed, leave it near your destination, and only then crawl the local grid.

HNSW keeps the same rhythm. The top layer is the interstate: few nodes, long links, big skips. The base layer is the local grid: every vector, short links, close inspection. You enter at the top, hop toward your query, and drop down to finish on foot.

Where it stops: highways are fixed pavement, but HNSW links are rebuilt on every insert, upper layers are drawn at random, and distance means vector distance, not miles. Nothing about the drive explains the two knobs, MM and efSearch\text{efSearch}, and those knobs are where the real tuning happens.

How It Actually Works

Each stored item is a vector xix_i (xix_i is the ii-th embedding in the collection) and your request is a query vector qq. Closeness is some distance d(q,x)d(q, x), Euclidean or cosine, fixed when you build the index.

Layer 00 holds all NN vectors. Each layer above holds fewer, thinning out fast because every insert draws a random top level and most draws stay low. A node that reaches a high layer is rare, so high layers form a sparse net of long jumps over the same points.

Each node keeps up to MM links per layer (MM is the most neighbors one node may hold on one layer). A larger MM connects the graph better and eats more RAM. Two more knobs finish the picture: efConstruction\text{efConstruction} (the candidate list size used while inserting) decides how hard the build tries to wire each newcomer well, and efSearch\text{efSearch} (the candidate list size used while querying) decides how many runners-up a query keeps. You can raise efSearch\text{efSearch} at query time without rebuilding anything. efConstruction\text{efConstruction} is baked in the day you build.

How a query walks down

The walk has two gears. Up high it is pure greed: stand on a node, look at its neighbors, step to the one closest to qq, repeat until nobody nearby beats you. Then drop to the next layer using that winner as the entry and do it again.

At the base layer the query widens into a shortlist. Keep the efSearch\text{efSearch} closest points seen so far, always expand the closest one you have not visited, and admit a newcomer only if it beats the worst name on the list. Stop when the list stops changing and return the top kk (kk is how many neighbors you asked for). A bigger efSearch\text{efSearch} checks more runners-up, so recall climbs and latency climbs with it. That is the whole trade: recall for RAM at build time through MM and efConstruction\text{efConstruction}, recall for latency at query time through efSearch\text{efSearch}.

The method assumes your distance tracks meaning and the graph stays connected. It fails when MM is too small and greed gets stuck in a dead end, when the metric at query time differs from build time, or when a filter rejects most candidates so the walk starves. Skip HNSW when RAM is capped at huge scale, when answers must be exact, or when the collection churns constantly. A compressed index fits the first case and an exact scan fits the second.

Worked example: six points, one query

Take six 2D points and a query q=(4,4)q = (4, 4):

  • A=(1,1)A = (1, 1), B=(2,3)B = (2, 3), C=(4,2)C = (4, 2), D=(5,5)D = (5, 5), E=(3,6)E = (3, 6), F=(6,1)F = (6, 1)

Rank them with squared distance, which orders the same as distance and keeps every number an integer:

  • DD: (4−5)2+(4−5)2=1+1=2(4 - 5)^2 + (4 - 5)^2 = 1 + 1 = 2
  • CC: (4−4)2+(4−2)2=0+4=4(4 - 4)^2 + (4 - 2)^2 = 0 + 4 = 4
  • BB: (4−2)2+(4−3)2=4+1=5(4 - 2)^2 + (4 - 3)^2 = 4 + 1 = 5
  • EE: (4−3)2+(4−6)2=1+4=5(4 - 3)^2 + (4 - 6)^2 = 1 + 4 = 5
  • FF: (4−6)2+(4−1)2=4+9=13(4 - 6)^2 + (4 - 1)^2 = 4 + 9 = 13
  • AA: (4−1)2+(4−1)2=9+9=18(4 - 1)^2 + (4 - 1)^2 = 9 + 9 = 18

True order: DD, then CC, then BB and EE tied, then FF, then AA. As distances that is 2≈1.41\sqrt{2} \approx 1.41, 2.002.00, 5≈2.24\sqrt{5} \approx 2.24, 13≈3.61\sqrt{13} \approx 3.61, 18≈4.24\sqrt{18} \approx 4.24.

Now give it HNSW layers. The top layer holds {A,D}\{A, D\} with one link between them. The base layer holds all six, chained AA to BB to EE to CC to DD to FF. Enter at AA up top (4.244.24). Its only neighbor DD (1.411.41) wins, nothing up there beats DD, so descend with DD as entry.

At the base with efSearch=3\text{efSearch} = 3, the board opens at [D][D], expands DD to admit CC (2.002.00) and EE (2.242.24), expands CC to check BB (2.242.24) and FF (3.613.61) without changing the board, then expands EE and stops. Ask for k=2k = 2 and you get DD and CC. The diagram draws exactly this walk: the mint path runs AA to DD to CC, with 1.411.41 and 2.002.00 printed under the two winners.

Code

The point of this snippet is the check you should run before trusting any index: rank the fixture by hand, then confirm the order in code.

import math

def sq_dist(a: tuple[float, float], b: tuple[float, float]) -> float:    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

pts: dict[str, tuple[float, float]] = {    "A": (1.0, 1.0),    "B": (2.0, 3.0),    "C": (4.0, 2.0),    "D": (5.0, 5.0),    "E": (3.0, 6.0),    "F": (6.0, 1.0),}q: tuple[float, float] = (4.0, 4.0)
ranked = sorted(pts.items(), key=lambda kv: sq_dist(kv[1], q))print([(k, sq_dist(v, q)) for k, v in ranked])  # -> [('D', 2.0), ('C', 4.0), ('B', 5.0), ('E', 5.0), ('F', 13.0), ('A', 18.0)]print(round(math.sqrt(2), 2))  # -> 1.41

The ranking matches the hand computation point for point: DD at squared distance 22, CC at 44, and the winner at true distance 1.411.41. Compare any index against this exact order on a sample before you believe its recall number.

Watch Out For

efSearch left low while recall quietly drops

Easy queries look perfect and latency looks great, so nobody touches the settings. Then harder queries and larger kk start missing: measured against an exact brute force check on a sample, recall sags while every dashboard stays green. It reads as a model problem, but it is an index setting.

Sweep efSearch\text{efSearch} upward at query time and plot recall against latency until the curve bends. Never lower it to fix latency without remeasuring recall. And remember the split: efSearch\text{efSearch} changes take effect at once, but a too small efConstruction\text{efConstruction} needs a full rebuild to fix.

Deletes pile up while RAM runs the show

HNSW lives in memory: every vector plus every link list stays resident, so the index is far bigger than the raw data. Deletes make it worse. Most engines mark deleted vectors as tombstones instead of rewiring the graph, so after heavy churn the walk keeps visiting dead nodes. Symptom: latency climbs and recall sags weeks after launch, with no config change in between.

Batch deletes, rebuild on a schedule, and spot check recall against brute force after each rebuild. If RAM is the binding constraint from day one, reach for IVF and product quantization instead of squeezing MM until the graph falls apart.

The Quick Version

  • HNSW files every vector into stacked graph layers: sparse long links above, dense short links at the base.
  • A query hops greedily to its closest neighbor up top, descends with that winner, then runs a shortlist of size efSearch at the base.
  • M and efConstruction are set at build time and cost RAM; efSearch is set per query and buys recall for latency.
  • The method assumes distance means relevance and the graph stays connected; tiny M, a mismatched metric, or heavy deletes break it.
  • Skip HNSW when RAM is capped, answers must be exact, or churn is constant; a compressed index or an exact scan fits better there.