What is HNSW, and how does an HNSW index search vectors?

HNSW, short for Hierarchical Navigable Small World, is a vector index: pgvector and the Faiss library both offer it. It finds the stored vectors nearest to a query without comparing the query with every one of them.

The problem it solves

A vector databaseVector DatabaseA database built to store embeddings and quickly find the ones closest to a query, which is how AI apps search by meaning. answers one question over and over: which of my stored embeddingsEmbeddingA list of numbers that stands for the meaning of a piece of text, an image or other data. Things with similar meaning get similar numbers, so a computer can find them. are closest to this one? Comparing the query with every stored vector always gives the right answer. pgvector does exactly that until you add an index. But with millions of vectors of a thousand or more numbers each, every query does millions of long sums.

HNSW trades a little accuracy for a lot of speed. It is one way to do approximate nearest neighbour searchApproximate Nearest Neighbor SearchFinding the stored vectors closest to a query without comparing it with every one, by using an index that may now and then miss the true closest in exchange for far faster searches..

How the graph is built

Every vector becomes a point in a graph, linked to a few of its nearest neighbours. Then a few points are also put in a second, smaller graph above, and fewer still in a third. In the original paper by Malkov and Yashunin, each point's top layer is drawn at random, with the odds falling sharply for each layer up. So the bottom layer holds every point, and the top holds a handful.

The upper layers have few points, so their links are long jumps across the map. The bottom layer has every point, so its links are short steps between close neighbours. The paper likens it to a skip list, the same idea used to search sorted lists quickly.

How a search runs

1. Start at the entry point on the top layer.
2. Step to whichever linked point is closer to the query. Repeat until no neighbour is closer.
3. Drop to the layer below, starting from that point, and do the same.
4. On the bottom layer, keep a short list of the best candidates found so far, ef of them, and keep widening from the closest until no closer point turns up. Return the best.

Try it below. With a list of 1, the search sometimes stops at a point that only looks closest from where it stands. A longer list costs more distance sums but finds the true nearest more often.

The settings that matter

ef_search can be changed per query, so you can tune recall against speed without rebuilding. Measure recall on your own queries against an exact search, then set it.

What it costs

pgvector notes that HNSW gives a better balance of speed and recall than its other index, IVFFlat, but takes longer to build and uses more memory. The links are stored on top of the vectors: the Faiss documentation gives each vector's size as the full vector plus its links. HNSW also needs no training step, so you can create the index on an empty table and add rows as they come.

A trap with filters

In pgvector, a WHERE filter is applied after the index has found its candidates. With the default ef_search of 40 and a filter that matches 10% of rows, only about 4 rows come back on average. Raise ef_search, or turn on iterative index scans (pgvector 0.8.0 and later), when you filter.

Why it matters

Retrieval quality in RAGRAGA way to answer from your own documents. A search finds the passages that match the question, and they are added to the prompt before the model writes. depends on finding the right passages. An HNSW index set too lean quietly skips some of them, and the model answers from the next-best text. Check recall when you tune it.