HNSW and approximate nearest neighbour search

What it is

HNSW builds a layered graph where each vector links to its neighbours. Search enters at a sparse top layer, greedily walks toward the query, then descends to denser layers to refine.

Why it is needed

Exact nearest-neighbour search compares the query to every vector. At 51,310 chunks that is tolerable; at ten million it is not. HNSW turns a linear scan into a graph walk.

How it works

Two knobs matter. m is how many links each node keeps, fixed at build time. ef_search is how many candidates the search keeps in flight, set per query — larger means more of the graph explored, better recall, more time.

Formula

recall@k = |ANN top-k  n  exact top-k| / k

Measured on this corpus, unrestricted:
  ef_search=40   -> 0.850
  ef_search=100  -> 0.942
  ef_search=200  -> 0.967
  ef_search=800  -> 0.975

m

links per node, fixed at build; higher is better recall and a larger index

ef_construction

candidate list size while building; higher is a better graph and a slower build

ef_search

candidate list size while querying; the runtime recall/latency dial

In this project

Built in PostgreSQL via pgvector 0.8.6 with m=16, ef_construction=64. On the real corpus the index builds in about 8 seconds. Measured here: at the default ef_search=40 an unrestricted role recovers 0.850 of what exact search returns — approximate means approximate, and 15% is lost before access control is even involved.

Trade-offs

Common mistakes

• Assuming ANN results equal exact results
• Benchmarking at ef_search=40 and reporting it as retrieval quality
• Filtering after the index has already chosen — see ANN post-filtering

When to use it

How it interacts with the rest of the system

Embeddings and dense retrievalANN post-filtering under access controlPostgreSQL Row-Level SecurityPartitioning by tenant