ANN indexing: HNSW and IVF

Two ideas. IVF clusters the vectors and searches only the nearest few clusters. HNSW builds a layered graph — sparse at the top for long hops, dense at the bottom for precision — and walks greedily downwards. Both skip most of the corpus; they differ in how they choose what to skip.

Overview

Two ideas.

In this guide
  1. HNSW: skip lists, in vector space
  2. The parameters worth naming
  3. How each one fails
  4. Product quantization, and when memory is the constraint
  5. Choosing between them, and what to measure
  6. Why exact search stops working
  7. IVF: search only nearby clusters
  8. HNSW: a navigable graph
  9. Building an IVF index and gauging what it misses
  10. Things to try with ANN indexing
  11. What to recall
  12. Compression: product quantisation
  13. Choosing an index by scale
  14. Gauging recall
  15. Questions people ask about ANN indexing
  16. ANN indexing: recap in one screen

Parameters

Visualisation

—

Readout

What to watch

  • The top layer covers distance; the bottom layer covers precision.
  • Search is greedy — it can settle in a local minimum and miss.
  • efSearch widens the beam: better recall, more time.

ANN indexing: HNSW and IVF: A Practical Guide

How does approximate nearest neighbour search actually work? Explain HNSW.

HNSW: skip lists, in vector space

Take a proximity graph — each vector linked to its nearest neighbours — and stack a few, each a random sample of the one below. Search enters at the sparse top layer and greedily moves to whichever neighbour is closer to the query, until no neighbour improves. Then it drops a layer and repeats.

The top layers have long edges, so a few hops cross most of the space; the bottom layer has short edges. So the final steps are precise. It is the skip-list idea applied to geometry. And it is the reason HNSW rules: excellent recall at low latency. IVF (Inverted File Index) takes a different approach. Partition the vector space into clusters (often using k-means), assign each vector to its nearest cluster centroid. And at query time search only the vectors in the nearest nprobe clusters. IVF trades recall for speed linearly: more probes give better recall at higher cost. HNSW is faster at high recall but uses more memory (the graph structure). IVF is more memory-fast but slower at the same recall level. Product Quantization (PQ) compresses vectors by splitting each one into subvectors and quantizing each subvector to the nearest codebook entry. This reduces memory by 4-8x at a small precision cost. IVF + PQ (IVFPQ) is the standard combination for billion-scale search: IVF narrows the candidates, PQ compresses the stored vectors. Libraries like FAISS, Annoy, and ScaNN implement these structures; vector stores like Pinecone, Weaviate, and Milvus wrap them with persistence and APIs. This page builds both an HNSW graph and an IVF index on the same vectors, runs the same query against each, and compares recall, latency, and memory.

The parameters worth naming

M — edges per node, fixed at build time. Higher means a better-connected graph, better recall, more memory. The graph itself is a real memory cost on top of the vectors. This is HNSW's main drawback.

efConstruction — how hard the builder works to find good neighbours. Build-time only: slower indexing, better graph for good.

efSearch — the size of the candidate list during a query. The runtime knob: raise it for recall, lower it for latency, per query if you like. This is the one to mention, because it is the one you really tune in production.

How each one fails

HNSW's search is greedy, so it can settle in a local minimum and return a neighbourhood that is good but not the best. A wider efSearch makes that less likely without removing it. Deletion is also awkward. Removing a node can disconnect the graph. So most implementations tombstone and rebuild at times.

IVF's failure is cleaner: a true neighbour sitting just across a cluster edge is missed unless that cluster is probed. More probes fixes it and costs latency. IVF is cheaper to build and to update, which is why it survives alongside HNSW. And combined with product quantization it is what runs when memory, not latency, is the binding constraint.

Product quantization, and when memory is the constraint

HNSW keeps each vector in memory plus the graph, so a million 768-dimensional float32 vectors is about 3 GB before the graph. Past some scale that, not latency, is what stops you.

Product quantization splits each vector into subvectors, clusters each subspace, and stores the cluster ids instead of the values — often a 10–30× reduction. Distances are then computed against the codes using a precomputed lookup table, which is also faster.

The cost is precision: distances turn approximate on top of the search now being approximate, so recall drops. The standard mitigation is rerank with the real vectors. Retrieve a generous candidate set from the compressed index. Then rescore the top few hundred against the originals held on disk. IVF-PQ with reranking is what most billion-scale deployments really run.

Choosing between them, and what to measure

HNSW when the index fits in memory and query latency matters most. Best recall-for-latency, worst memory, awkward deletes.

IVF when builds and updates need to be cheap, or as the base for quantization. Simpler to reason about; recall depends on probing enough clusters.

IVF-PQ when memory is binding. Accept lower raw recall and recover it with a rerank pass.

Flat when the corpus is small or a miss is a correctness bug. Under a hundred thousand vectors, a brute-force scan is often a few milliseconds and needs no tuning at all —. This is worth checking before adopting a thing else.

Measure on your own data. Recall/latency curves depend on the intrinsic dimensionality and clustering of your embeddings, and published benchmarks on academic datasets transfer poorly.

Why exact search stops working

Finding the nearest vectors just means comparing the query against each stored vector. With a million 768-dimensional vectors that is 768 million times-adds per query. Fine in a batch job, too slow for an interactive request, and hopeless at ten million.

Approximate nearest neighbour indexes trade a small amount of recall for orders of size of speed. "Approximate" means they may miss a true nearest neighbour sometimes; in practice, well-tuned indexes return 95–99% of them. And the misses rarely change what a user sees.

IndexStructureBuild costQuery speedMemory
FlatNone — brute forceZeroSlowVectors only
IVFClustersModerate, needs trainingFastVectors + centroids
HNSWLayered graphHighVery fastVectors + graph links
IVF+PQClusters + compressionHighFastMuch smaller

IVF: search only nearby clusters

The idea is a library organised into sections.

Build: run k-means over the vectors to find, say, 4,096 centroids. Assign each vector to its nearest centroid, giving an inverted list per cluster.

Query: compare the query against the 4,096 centroids, pick the closest nprobe of them, and search only the vectors in those lists.

With nprobe = 8 out of 4,096 clusters, roughly 0.2% of the vectors are checked. The speed-up is tied to.

The tunable is nprobe, and it is a direct recall-versus-latency dial:

nprobeRecallLatency
1Low — misses vectors near cluster edgesFastest
8–16GoodFast
64+Approaching exactSlower

The failure mode is inherent: a vector just across a cluster edge from the query is missed unless that cluster is probed. Higher nprobe reduces it.

IVF needs a training step on a representative sample before vectors can be added. This is the main operational gap from HNSW.

HNSW: a navigable graph

HNSW builds a multi-layer graph where each vector links to its nearest neighbours. Upper layers are sparse and connect distant regions; lower layers are dense and local.

Query: start at an entry point in the top layer, greedily move to the neighbour closest to the query. And when no neighbour is closer, drop to the next layer down and repeat. The top layers cover distance quickly; the bottom layer refines.

The result is search time growing logarithmically rather than linearly with the number of vectors, and recall that is often higher than IVF at the same latency.

Three parameters:

ParameterControlsTypical
MLinks per node16–48
ef_constructionSearch breadth while building100–400
ef_searchSearch breadth at query time50–200

M and ef_construction are build-time and fix the index's grade ceiling; raising them costs build time and memory. ef_search is the query-time dial, adjustable per request. Higher for better recall, lower for lower latency.

The cost is memory. The graph links themselves consume roughly M × 2 × 4 bytes per vector on top of the vectors. So an HNSW index is often 1.5–2× the size of the raw vectors.

Building an IVF index and gauging what it misses

The sections above describe how IVF partitions the space and why exact search stops scaling. Here it is built and measured. A real index over real vectors, with the recall it loses and the work it saves at each setting of nprobe.

example_01.pyNumPy
Output

Exact search checks each vector. An IVF index partitions vectors into clusters so that a query scans only a few of them.

example_02.pyNumPy
Output

Recall is not spread evenly. Queries near a cluster edge lose neighbours sitting in the un-probed cluster next door.

example_03.pyNumPy
Output

Memory is a separate constraint. Product quantisation compresses each vector to a short code. This trades precision for a smaller footprint.

example_04.pyNumPy
Output

Things to try with ANN indexing

  1. Sweep efSearch from 8 to 512. Recall and latency both climb — this is the knob you tune in production. And it can differ per query.
  2. Drop M to 4. Recall is capped no matter how large efSearch gets: build-time damage cannot be repaired at query time.
  3. Raise M to 48 and watch the index memory. The graph is stored alongside the vectors, which is HNSW's main cost.

What to recall

HNSW stacks proximity graphs: sparse upper layers with long edges to cross the space, a dense bottom layer to refine. Search is greedy with a candidate list of width efSearch. This is the runtime recall/latency knob. M and efConstruction are fixed at build time. IVF is the simpler other — cluster then probe — cheaper to build and update. And it misses neighbours across cluster edges.

Compression: product quantisation

Both index types can be combined with compression, which is what makes very large collections affordable.

Product quantisation splits each vector into sub-vectors, clusters each sub-space apart, and stores only the cluster ids. A 768-dimensional float32 vector (3,072 bytes) split into 96 sub-vectors with 256 centroids each turns 96 bytes — a 32-fold reduction.

Distances are then computed about from precomputed lookup tables, without decompressing.

The cost is precision: the stored form is lossy. The standard mitigation is re-ranking — use the compressed index to find 100 candidates cheaply. Then rescore those against their full-precision vectors. This are fetched from disk.

 Memory per vectorRecall
Flat float323,072 bytes100%
Flat float161,536 bytes~100%
PQ, 96 bytes96 bytes85–95% alone
PQ + full-precision rerank96 bytes in RAM95–99%

Choosing an index by scale

VectorsReasonable choice
Under 100kFlat — exact, simple, fast enough
100k–10MHNSW — best quality per millisecond
10M–100MIVF, or HNSW with compression
Over 100MIVF+PQ, sharded across machines

The first row is worth stating plainly because it saves a great deal of unneeded infrastructure: below about 100,000 vectors, a NumPy array and a dot product is truly adequate. A million-vector brute-force search takes tens of milliseconds on a modern CPU with a good BLAS.

Operational gaps that matter as much as the benchmarks:

Insertions. HNSW backs incremental additions well. IVF needs its centroids trained first, and grade degrades if the distribution shifts away from the training sample.

Deletions. Both handle them poorly — often via tombstones, with periodic rebuilds to reclaim space and grade.

Sifted search. Applying a metadata filter can defeat the index structure. Since the graph or clusters were built over all of it. Modern vector stores implement filter-aware traversal; where unavailable, over-retrieve and filter afterwards.

Gauging recall

Approximate means you should know how approximate. The measurement is straightforward:

# ground truth from exact search on a sample of queries
exact = brute_force_top_k(queries, vectors, k=10)
approx = index.search(queries, k=10)

recall = sum(len(set(a) & set(e)) for a, e in zip(approx, exact)) / (10 * len(queries))

Run that for a few settings of ef_search or nprobe and plot recall against latency. The coming curve is what the parameter should be chosen from. And the shape is often a sharp rise followed by a long flat region. So there is a clear point past which extra latency buys nothing.

Questions people ask about ANN indexing

HNSW or IVF? HNSW for grade per millisecond and easy insertions; IVF when memory is tight or the collection is very large.

What recall should I target? 95–99% for most uses. The gap is rarely visible to users, and the latency saving is large.

Does approximate search hurt RAG grade? Marginally, and far less than poor chunking or a missing reranker. It is not where the grade problems are.

How much memory will I need? Roughly vectors × dimensions × bytes_per_value, times 1.5–2 for HNSW's graph. Compression reduces the first term much.

Can I change parameters after building? ef_search and nprobe yes, per query. M and the cluster count need a rebuild.

Do I need a vector store? For under 100k vectors, no. Above that, one earns its place — as much for sifting, persistence and updates as for the index itself.

ANN indexing: recap in one screen

  • Exact search is linear and stops being interactive past a few hundred thousand vectors.
  • IVF clusters the space and searches only the nearest clusters; nprobe trades recall for speed.
  • HNSW walks a layered neighbour graph. This gives logarithmic search and high recall at 1.5–2× the memory.
  • Product quantisation compresses vectors 30-fold, with a full-precision rerank to recover precision.
  • Measure recall against exact search and pick parameters from the recall-latency curve.

Recall check

0 of 3

Say the answer out loud before you reveal it — recalling it is what makes it stick, and rereading it is not.

  1. What does this module say about “HNSW: skip lists, in vector space”?

  2. What does this module say about “The parameters worth naming”?

  3. What does this module say about “How each one fails”?

Cheat sheet

ANN indexing: HNSW and IVF

Build an HNSW graph and an IVF index from the same vectors, run a nearest-neighbour query on each, and compare the recall-speed tradeoff.

GEN AI · vizlearn.in/gen_ai/ann_indexing_hnsw_and_ivf.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.