Start here: the problem it solves#
TL;DRthe 30-second version
- An embedding turns a piece of text, an image, or a product into a vector of numbers, positioned so that similar things sit close together. Search becomes: find the stored vectors nearest to the query vector.
- The exact way is a brute-force scan: measure the distance from the query to every stored vector and keep the smallest. Correct, but it does one distance computation per vector, so its cost grows straight in line with the collection.
- HNSW replaces the scan with a layered graph. Sparse upper layers are express lanes over a dense bottom layer that holds every vector. A search enters at the top, greedily hops to the closest neighbour, and drops a layer at a time — roughly log(n) hops instead of n.
- The speed-up is bought with approximation: the greedy walk can settle on a near-neighbour and miss the true nearest. Two knobs, ef and M, trade recall for latency and memory. It is the most popular graph index — the default in Qdrant and Weaviate, and available in FAISS, pgvector, and Milvus.
Start with what an embedding is. A model reads a sentence and outputs a list of numbers — a vector — chosen so that sentences with similar meaning land close together in that space. "How do I reset my password?" and "I forgot my login" end up near each other, even though they share almost no words. Search over meaning then becomes geometry: embed the query, and look for the stored vectors that sit nearest to it.
The straightforward way to find the nearest is to check everyone. Measure the distance from the query to every stored vector, remember the smallest, and return it. This is called a flat or brute-force index, and it is exactly correct — it always returns the true nearest neighbour.
The trouble is the arithmetic. Real embeddings are big: a common size is 1536 numbers per vector. One distance is about 1536 multiply-and-add operations. With ten million vectors, a single query is roughly fifteen billion operations. That lands in the hundreds of milliseconds to seconds per query on a CPU, and it repeats for every query. A search box that answers in two seconds and melts under load is not a search box you can ship.
The mechanism: a layered navigable graph#
The first idea is a navigable graph. Link each vector to a handful of its nearest neighbours. Now you can search by walking: start somewhere, look at the current point's neighbours, step to whichever one is closest to the query, and repeat. Because near points are linked, each step moves you closer, and you home in on the query's neighbourhood without checking everyone. A graph where short paths exist between any two points is called a small world.
A flat graph has one weakness: from far away, you can only inch toward the query one short link at a time, because every link connects near neighbours. HNSW fixes this by stacking graphs in layers. Layer 0 holds every vector and its short links. Each layer above holds a thinning random subset of the points, with longer links between them. The top layers are the express lanes; the bottom layer is the local streets.
a point's height is a coin-flip; higher layers are geometrically rarer, like a skip list's towers
How tall is a point's tower? When a vector is inserted, HNSW draws its top layer from an exponential distribution: the chance of reaching layer one is modest, layer two much smaller, and so on. In the paper's terms the level is floor(-ln(U) times mL), where U is a uniform random number and mL is 1 over ln(M). The effect is the same geometric thinning a skip list gets from repeated coin flips — most points live only at the bottom, a few reach high.
The letter M is the second control. It is the number of neighbours each point links to per layer — the degree of the graph. A larger M builds a denser, better-connected graph that is easier to navigate accurately, at the cost of more memory and slower builds. Layer 0 usually gets twice as many links as the upper layers, because that is where the final, precise search happens.
Searching: enter high, hop greedily, drop low#
A search starts at the single entry point on the top layer. It looks at that point's neighbours in this layer, measures each one's distance to the query, and hops to the closest — as long as that neighbour is nearer than where it stands. It keeps hopping until no neighbour is closer, which means it has reached a local best for this layer. Then it drops to the layer below and continues from the same point.
- Enter at the top layer's entry point, the one point that reaches the highest layer.
- In the current layer, hop to the neighbour closest to the query, repeating until no neighbour is closer (a local minimum for this layer).
- Drop down one layer and continue the greedy walk from where you stopped — the links here are shorter, so the steps are finer.
- At layer 0, run a wider search that keeps the ef best candidates in play, then return the closest of them.
The top layers do the coarse work. Because they are sparse and their links are long, a single hop can cross a large part of the space. As the search descends, the layers get denser and the links get shorter, so the hops shrink into fine adjustments right around the query. A handful of big hops up top, then a few small ones at the bottom, and the search arrives — without ever measuring most of the vectors.
Layer 0 is where recall is won or lost. Instead of moving to one best neighbour and stopping, the search there keeps a small working set of the ef closest candidates found so far and explores their neighbours too. A larger ef means a wider frontier, which is more likely to escape a dead end and reach the genuine nearest — at the price of measuring more points. That single number is the main recall-versus-latency dial you turn in production.
PredictIn a million-vector HNSW index, a query hops a few times per layer and there are about log(n) layers. Roughly how many distance computations is that, and why is it not a million?
Hint: Compare the number of hops across all layers to the size of the collection.
It is on the order of a few hundred distance computations, not a million. There are about log(n) layers, and the search does a bounded number of hops (scaled by ef) in each, so total work grows like ef times log(n). Each hop only measures the current point's handful of neighbours, and the sparse upper layers let those few hops cover enormous distance — so the search skips the overwhelming majority of the vectors entirely. Exact would measure all million; HNSW measures a tiny slice of them.
Approximate on purpose: recall and its knobs#
HNSW is approximate because the walk is greedy, and greedy walks can get stuck. The search always steps to a closer neighbour, so if it reaches a point whose neighbours are all farther from the query than it is — even though a genuinely nearer vector exists elsewhere — it stops. That is a local minimum, and settling there means returning a near-neighbour instead of the true nearest. In the simulator's miss scenario you can watch exactly this: the greedy walk lands on a point about thirty units away when the real nearest is barely five units off.
Recall is the honest name for how often this goes right: the fraction of queries for which the search returns the true nearest (or, for a top-k query, the fraction of the true top-k it recovers). An exact scan has recall of one by definition. A well-tuned HNSW index typically runs at recall somewhere from the mid-nineties to over ninety-nine percent, which is more than enough for search and recommendation, at a fraction of the cost.
- ef (search width): how many candidates layer 0 keeps in play at query time. Raise it and recall climbs while latency rises roughly in step, because each extra candidate is another distance computation. This is the knob you tune per query load, without rebuilding.
- M (graph degree): how many neighbours each point links to. A higher M builds a richer graph with fewer dead ends, raising recall, but uses more memory and builds more slowly. It is fixed when you build the index.
- ef_construction (build effort): how hard the builder searches for good neighbours when inserting each point. Higher values build a better graph — higher recall later — at the cost of a slower build. It too is a build-time choice.
How the index gets built
The graph is built one vector at a time, and insertion reuses the search. When a new vector arrives, HNSW draws its top layer, then runs the same descend-and-hop search from the current entry point down to the new vector's top layer. From there down, it looks for the ef_construction closest existing points in each layer and links the newcomer to M of them, adding the reverse links so neighbours point back.
Choosing which M neighbours to keep is subtler than picking the M nearest. The paper uses a heuristic that prefers a spread of neighbours in different directions over a tight cluster of the very closest ones. This keeps the graph navigable: a point wants links that reach into different regions, so a search can always find a direction that makes progress rather than circling inside one dense pocket.
If the new vector reaches higher than any existing point, it becomes the new entry point. Because tall points are exponentially rare, this happens seldom, and the entry point stays stable — a single, consistent place for every search to begin.
Cost: time, memory, and the shape of the win
| Exact (flat) | HNSW | |
|---|---|---|
| Query time | O(n · d) — every vector | O(ef · log n · d) — a slice |
| Recall | 1.0 (always exact) | Tunable, typically 0.95–0.99+ |
| Build time | None (just store them) | O(n · log n) graph construction |
| Memory | The vectors | The vectors plus the graph links |
| Best when | Small or exactness required | Large collections, low latency |
The query-time win is the whole point. Exact does one distance per vector, so its cost climbs straight in line with n. HNSW does a bounded number of hops per layer across about log(n) layers, so its cost climbs like log(n). At ten thousand vectors the two are close and exact may even be simpler. At ten million the gap is enormous: exact measures ten million vectors, HNSW a few hundred. The bigger the collection, the more HNSW wins.
The bill shows up as memory. HNSW keeps the full vectors and the graph's links in RAM for speed, and the links add real overhead — roughly M references per point per layer. For a large index this can be tens of gigabytes, which is why HNSW is often paired with quantization (storing compressed vectors) to fit more of the index in memory.
Other ways to index vectors
HNSW is the most popular approximate index, but it is not the only one, and real systems mix them.
- Flat (brute force): measure every vector. Perfect recall, linear cost. Still the right choice for small collections or when exactness is required — and it is the ground truth you measure recall against.
- IVF (inverted file): cluster the vectors, and at query time search only the few clusters nearest the query. Cheaper memory than HNSW and fast to build, but recall depends on how many clusters you probe. Often combined with HNSW to route between clusters.
- Product quantization (PQ): compress each vector into a short code so many more fit in memory, and compute approximate distances on the codes. Trades a little accuracy for a large memory saving; frequently layered under IVF or HNSW.
- LSH (locality-sensitive hashing): hash vectors so that near ones collide, then search within a bucket. Simple and streaming-friendly, but usually needs more memory for the same recall as HNSW, so it has faded for dense embeddings.
Where it strains
Recall degrades as the collection grows if you hold the knobs fixed. A graph tuned for a million vectors will quietly return worse neighbours at a hundred million, because the search budget that used to cover the space no longer does. The fix is to raise ef (and sometimes M) as you scale — recall is not a set-and-forget setting.
Deletes are genuinely awkward. Removing a point can strand its neighbours or tear a hole in the graph's connectivity, so most implementations mark a point as deleted and skip it during search rather than truly unlinking it, then rebuild periodically to reclaim the space. A workload of constant deletions is the case HNSW handles worst.
High dimensionality is a headwind for every method here, HNSW included. As dimensions grow into the hundreds, distances between points concentrate — far and near become harder to tell apart — which is the curse of dimensionality. HNSW copes better than most, but it is why recall and tuning matter more for a 1536-dimensional embedding than for the 2D map in the simulator.
Where HNSW runs in the wild
- FAISS (Meta) — the widely used similarity-search library; its HNSW index is a common baseline, often combined with IVF and product quantization for scale.
- pgvector — the Postgres extension that adds a vector column and an HNSW index, so a normal SQL database can serve nearest-neighbour queries. Its ef_search knob is the query-time recall dial.
- Qdrant, Weaviate, Milvus — purpose-built vector databases whose default index is HNSW, exposing M, ef_construction, and ef as tunables.
- Retrieval-augmented generation (RAG) — the pattern behind most "chat with your documents" features: embed the corpus, index it with HNSW, and at query time fetch the nearest chunks to feed a language model. Recommendations, image search, and near-duplicate detection use the same index.
Common misconceptions & gotchas
Does HNSW always return the true nearest neighbour?
No. It is approximate: the greedy walk can settle in a local minimum and return a near-neighbour instead. In practice a well-tuned index gets it right well over ninety-five percent of the time, and you raise ef to push that higher when you need to.
What is the difference between ef and ef_construction?
ef_construction is a build-time effort setting that shapes how good the graph is; ef (sometimes ef_search) is a query-time setting that controls how hard each search works on that graph. You can change ef per query without rebuilding, but changing ef_construction or M means rebuilding the index.
Why does it use so much memory?
HNSW keeps both the full vectors and all the graph links in RAM to stay fast. The links alone cost roughly M references per point per layer. For large indexes this is why teams reach for product quantization to store compressed vectors and fit more of the index in memory.
Is the sim's 2D space realistic?
The space is not — real embeddings have hundreds or thousands of dimensions, where distances behave less intuitively. The mechanism is exactly realistic: the layered graph, the greedy descent, the entry point, and the ef and M knobs all work the same regardless of dimension. 2D just lets you see the descent.
QuizYour RAG system's answer quality has slowly dropped as your document collection grew from one million to fifty million chunks, with all index settings unchanged. What is the most likely cause?
- The embeddings became less accurate as the corpus grew
- Recall fell because the fixed search budget no longer covers the larger graph
- HNSW stopped being deterministic at scale
- Postgres ran out of disk for the vectors
Show answer
Recall fell because the fixed search budget no longer covers the larger graph — Recall in HNSW depends on the search budget relative to the graph's size. An ef tuned for a million vectors explores a smaller fraction of a fifty-million-vector graph, so the greedy walk misses the true nearest more often and retrieval quality slips. Raising ef (and often M, which needs a rebuild) restores recall. The embeddings and determinism are unchanged; this is a tuning problem, not a data or storage one.
In an interview
Lead with the problem and the trade. Semantic search needs the vectors nearest a query; an exact scan is O(n) per query and too slow at scale, so you use an approximate index that gives up a little recall for a large speed-up. Name HNSW as the default, and describe it in one breath: a layered graph, sparse express lanes over a dense base, that a search descends greedily from a top entry point.
Be ready for the knobs. ef controls query-time search width and trades recall for latency; M controls graph degree and trades recall for memory and build time; ef_construction controls build effort. Mention that recall must rise with scale, that deletes are awkward and usually handled with tombstones plus periodic rebuilds, and that memory is the real cost, which is why HNSW is often paired with quantization. Naming FAISS, pgvector, and a vector database like Qdrant or Weaviate shows you know where it runs.
Then open the simulator. Run the greedy descent and watch the big hops on the top layer give way to fine hops at the bottom. Run exact against HNSW on the same query to see the comparison count collapse from every point to a handful. Then run the miss scenario, where a lean search returns a near-neighbour instead of the true nearest — the recall cost, shown honestly, and the reason ef exists.
References & further reading
- Malkov & Yashunin — Efficient and robust approximate nearest neighbor search using HNSW graphs (2016/2020) — the original paper: the layered structure, exponential layer assignment, greedy search, and the M / ef parameters
- FAISS — the similarity search library (Meta) — HNSW, IVF, and product-quantization indexes, and how they are combined at scale
- pgvector — vector similarity search for Postgres — adds a vector column and an HNSW index to Postgres; ef_search is the query-time recall knob
- Qdrant — indexing and HNSW configuration — a vector database's take on M, ef_construction, and ef, with tuning guidance
- Weaviate — vector index concepts — how a production vector database exposes and defaults the HNSW parameters
- Pinecone — Hierarchical Navigable Small Worlds (HNSW) — a visual walkthrough of the graph, the layers, and the greedy search
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.