How HNSW Finds the Nearest Vector

The last post said that a vector database's real job is finding the nearest vectors quickly, and that most of them do it with an index called HNSW. pgvector, Qdrant, Chroma, Weaviate and Milvus all offer it.

This post opens that box: how the index is built, how a query walks it, what the three settings you will see in every product actually change, and why the answer is approximate.

The idea: walk a graph instead of scanning a list

Exact search compares the query with every stored vector. HNSW avoids that by turning the vectors into a graph. Each vector keeps links to a handful of its nearest neighbours. To answer a query, you start somewhere, look at the current vector's neighbours, move to whichever one is closer to the query, and repeat until none of them is closer.

That greedy walk is the whole trick. Most of the data is never touched, because the walk only measures the neighbours of the vectors it passes through.

One graph on its own has a problem, though. If every link is short, crossing from one side of the data to the other takes many small hops. HNSW fixes that with layers.

Layers are express lanes

Every vector is on layer 0, the full graph with short links. A random few are also on layer 1, where the links are longer because there are fewer vectors to link to. A random few of those are on layer 2, and so on.

Which vectors climb is decided by a coin flip at insert time, weighted so that each layer up keeps about 1 in M of the vectors below it, where M is the number of links per vector. The demo in the video below has 300 vectors and M = 6: 300 on layer 0, 55 on layer 1 and 9 on layer 2.

A search starts at the top, where a few long hops cross the whole space, then drops to denser layers for the finer steps. It works like a road trip: motorway first, then main roads, then the street you want. In the demo, the query finds its true nearest neighbour after 68 distance checks instead of 300.

Inserting a vector

Building the index is mostly searching. Each new vector looks for its own neighbours using the graph that already exists, then links itself in.

Three details matter here:

• The links go both ways. The new vector links to its neighbours, and they link back to it, which is what lets later searches find it.
• Each vector has a cap on its links, M on the upper layers and usually 2M on layer 0. When a new link pushes a neighbour over its cap, the neighbour drops its farthest links.
• Real implementations do not simply keep the M nearest. They prefer a spread of directions, so a vector in a tight cluster still keeps a link that leads out of it.

The width of the search during insertion is the first setting, ef_construction. A wider search finds better neighbours and builds a better graph, at the cost of slower inserts.

Answering a query

A query runs the same walk, with one change at the bottom.

On the upper layers the walk keeps a single best vector, because those layers only need to get it close. On layer 0 it keeps a shortlist instead: the best ef_search vectors seen so far. It repeatedly takes the closest candidate it has not expanded yet, measures that candidate's neighbours, and adds any that beat the worst entry on the shortlist. When no candidate left can beat the worst entry, it stops and returns the top k.

That is why ef_search has to be at least k. A shortlist of 10 cannot return 20 results.

Why it is approximate

A greedy walk stops as soon as no neighbour is closer. In two dimensions, as in the video, that almost always means it has arrived. Real embeddings have hundreds of dimensions, where the neighbours of a vector do not always point towards the query, and the walk can stop one step short of the true answer.

The shortlist is the safety margin. With more candidates in play, the search is more likely to step around a dead end and keep going. That is the trade you make with ef_search: a longer shortlist means fewer misses and slower queries. Recall, the share of true nearest neighbours the index returns, stops being 100% and becomes a number you measure and tune.

The three settings

Every product exposes the same three, sometimes under other names:

• M (pgvector m, Chroma max_neighbors) is the number of links per vector. More links make a better-connected graph and better recall, and use more memory. Defaults are around 16.
• ef_construction is the search width while building. Higher builds a better graph and slows down inserts. pgvector defaults to 64, Chroma to 100.
• ef_search is the shortlist size at query time, and the setting you tune most. pgvector defaults to 40, Chroma to 100. Raise it until recall stops improving, then stop.

M and ef_construction are fixed when the index is built; changing them means rebuilding. ef_search can change per query or per session, which makes it the one to experiment with.

What it costs

HNSW is fast at query time, and you pay for it elsewhere:

• Memory: the links live next to the vectors. At M = 16, layer 0 allows 32 links of 4 bytes each, about 128 bytes per vector, next to roughly 3 KB for a 768-dimension vector of floats. Small, but it all wants to be in memory.
• Build time: every insert is a search, so building an index over millions of vectors takes a while, and a bulk load is usually faster than inserting one by one.
• Deletes: removing a vector would leave holes in its neighbours' link lists, so libraries such as hnswlib mark it deleted rather than removing it from the graph. Many deletes and updates slowly degrade the graph until it is rebuilt.
• Filters: the walk does not know about your filters, so many implementations apply them afterwards, which is the "too few results" trap from the last post.

The short version

• HNSW links each vector to its nearest neighbours and answers a query with a greedy walk.
• Layers are express lanes: each layer up keeps about 1 in M vectors, so a search crosses the space in a few long hops and then refines.
• On layer 0 the search keeps a shortlist of ef_search candidates, which is what keeps it from stopping one step short.
• M and ef_construction shape the graph at build time. ef_search is the query-time dial between recall and speed.
• It is approximate, so measure recall on your own data before you trust the defaults.