AI & ML / RAG & embeddings / 14_ann_indexes_and_hnsw.md

ANN indexes and how HNSW works

Updated 6 interview angles 7 min read source
On this page7
  1. Why approximate at all
  2. The mechanism: HNSW
  3. The alternatives
  4. Where it breaks in production
  5. The trade not taken
  6. Related
  7. Interview angle

ANN indexes and how HNSW works

Article.

Every vector database is a wrapper around an approximate nearest-neighbour index, and almost all of them are wrapping the same one. Knowing how HNSW actually works is what lets you answer the questions that follow from it — why recall is a dial, why memory is the binding constraint, and why a filter can quietly destroy your results.

Why approximate at all

Exact nearest-neighbour means computing the distance to every vector. At a million vectors of 768 dimensions that is 768 million multiply-adds per query, and it does not get better with a cleverer loop — the curse of dimensionality means the tree structures that make this fast in 2D degenerate to a full scan by a few dozen dimensions.

So production systems accept approximation: find 95-99% of the true nearest neighbours in milliseconds instead of 100% in seconds. That percentage is recall, and it is a dial you set, not a property you discover.

The mechanism: HNSW

Hierarchical Navigable Small World is two ideas stacked.

Idea one: a navigable small world

Build a graph where each vector is a node connected to some of its near neighbours. To search, start anywhere and greedily walk downhill: look at the current node’s neighbours, move to whichever is closest to the query, and repeat until no neighbour is closer.

text 
query: *

  a ---- b ---- c
         |      |
         d ---- e ---- f *

From a, the walk goes b -> c -> e -> f and stops. No global scan — each step only inspects one node’s neighbours.

The catch is that a purely local graph gets stuck in local minima, and the walk from a distant start is long.

Idea two: layers, like a skip list

HNSW stacks several graphs. The top layer holds a tiny random subset with long-range links; each layer down holds more nodes with shorter links; the bottom layer holds everything.

text 
L2   a ---------------- f            sparse, long hops
L1   a ------ c ------- f            
L0   a - b - c - d - e - f           dense, everything

Search enters at the top, greedily walks to the closest node in that layer, drops to the layer below using that node as the entry point, and repeats.

The top layers cover distance cheaply; the bottom layer does the fine positioning. That is the same trick a skip list plays on a linked list, and it buys the same thing: roughly logarithmic search instead of linear.

The three parameters

Everything you tune is one of these:

Parameter Controls Raising it
M neighbours per node better recall, more memory
ef_construction candidates while building better graph, slower build
ef_search candidates while querying better recall, slower query

M and ef_construction are build-time and immutable — changing them means rebuilding the index. ef_search is per-query, which makes it the useful one:

python 
# Same index, two different points on the recall/latency curve.
fast   = index.search(q, k=10, ef_search=40)    # lower recall, ~1ms
better = index.search(q, k=10, ef_search=200)   # higher recall, ~4ms

This is the single most useful thing to know operationally. If recall is poor you do not necessarily need a bigger model or a rebuilt index — you may just need a larger ef_search, at a latency cost you can measure. And it lets you serve different recall to different callers from one index.

ef_search must be at least k; setting it equal to k gives the worst recall the index can produce.

The alternatives

Index Character
Flat exact, O(N), correct below ~100k
IVF cluster, search nearest clusters; fast build
HNSW graph walk; best recall/latency, memory-hungry
PQ compress vectors to codes; pairs with IVF
DiskANN disk-resident graph; billions of vectors

IVF partitions vectors into clusters and searches only the nprobe closest ones. It builds far faster than HNSW and uses less memory, and its failure mode is specific: a query near a cluster boundary misses neighbours sitting just across it. Raising nprobe fixes recall and costs latency, exactly as ef_search does.

Product quantisation splits each vector into sub-vectors and replaces each with a centroid id, cutting memory dramatically at some accuracy cost. Usually IVF+PQ for very large collections, with a rescoring pass over full vectors for the final ranking.

Most production systems run HNSW, and most defaults you inherit are HNSW.

Where it breaks in production

Memory is the constraint, and it is not the graph

The graph is small. The vectors are not, and HNSW keeps them in RAM.

text 
1M vectors x 768 dims x 4 bytes    ~3.0 GB
graph: 1M x ~16 links x 4 bytes    ~0.1 GB
                                   -------
                                   ~3.1 GB

Ten million vectors is 30 GB and an instance decision. Which is why the first lever is quantisation, not a smaller model — int8 cuts that 3 GB to 750 MB for a small recall loss, and you keep the embedding model you already evaluated.

Filtering fights the graph

The failure that surprises people, and it follows directly from the mechanism.

The greedy walk moves through neighbours. Apply a restrictive filter and most neighbours are excluded, so the walk has nowhere to step — the graph is effectively disconnected and the search returns far fewer than k results, or poor ones, with no error.

text 
unfiltered:  a - b - c - d - e      walk reaches e
tenant=42:   a - x - x - x - e      walk stalls at a

Approaches differ, and this is a real selection criterion:

  • Post-filter — search then discard. Simple, and you may get 3 results from a top-50 search.
  • Pre-filter with a filterable index — the filter participates in traversal rather than fighting it. Qdrant builds this in deliberately.
  • Brute force the subset — when the filter is selective enough, skip the index. At 400 rows a full scan beats any graph, and this is the right answer far more often than people expect.

Deletes are tombstones

You cannot cleanly remove a node from a navigable graph — its neighbours route through it. Implementations mark deleted and filter at query time, so a collection with heavy churn accumulates dead nodes that still cost traversal time and memory. Periodic rebuilds are maintenance, not an optimisation, and a rebuild is a full index build.

Build time is not free

ef_construction high enough for good recall on ten million vectors is hours of CPU. That matters because an index rebuild is a migration: build alongside, verify recall against a held-out set, then swap. Rebuilding in place leaves you serving from a half-built index.

The trade not taken

Below roughly a hundred thousand vectors, use flat search. A brute-force scan is exact, has no parameters, no build step, no rebuild, no tombstones, and at that scale it is fast enough — numpy does a million 768-dimension dot products in tens of milliseconds.

Adopting HNSW at 20,000 vectors buys tuning parameters, a memory bill and a rebuild story in exchange for latency you were not short of. The index earns its complexity at scale, and knowing where that line sits is more useful than knowing the algorithm.

Interview angle 6

  • “Why is vector search approximate?” — exact nearest neighbour is a full scan, and the tree structures that avoid that in low dimensions degenerate to a scan within a few dozen dimensions. So you accept 95-99% recall in milliseconds instead of 100% in seconds.
  • “How does HNSW work?” — a graph where each vector links to near neighbours, searched by greedily walking toward the query, stacked into layers like a skip list. Upper layers are sparse with long links to cover distance cheaply; the bottom layer has everything for fine positioning. That gives roughly logarithmic search.
    • Follow-up: “Which parameter would you change if recall is poor?” — ef_search first, because it is per-query and needs no rebuild. M and ef_construction are build-time, so changing them means rebuilding the index.
  • “What actually limits how many vectors you can hold?” — memory, and it is the vectors rather than the graph. A million 768-dimension float32 vectors is about 3 GB with the graph adding roughly a tenth of that. Quantise to int8 before reaching for a smaller embedding model.
  • “You filter by tenant and get three results instead of fifty.” — the greedy walk traverses neighbours, and a restrictive filter excludes most of them, so the graph is effectively disconnected and the walk stalls. Post-filtering discards after the fact; a filterable index makes the filter part of traversal; and on a selective filter a brute-force scan of the subset beats the index outright.
    • Follow-up: “When is brute force actually right?” — below roughly 100k vectors overall, or whenever a filter cuts the candidate set to a few thousand. It is exact, has no parameters and nothing to rebuild.
  • “How do deletes work?” — as tombstones, because a node’s neighbours route through it and it cannot be cleanly removed. Heavy churn accumulates dead nodes that still cost traversal and memory, so periodic rebuilds are maintenance rather than optimisation.
  • “IVF or HNSW?” — HNSW for the best recall-latency curve at the cost of memory and build time; IVF when build speed and memory matter more, accepting that queries near a cluster boundary miss neighbours just across it. Both expose the same shape of dial: ef_search and nprobe.
Previous
Milvus in production