ANN Indexes Explained: HNSW, IVF and Product Quantization

Imagine one hundred million embeddings, each with seven hundred sixty eight numbers, and a user waiting for an answer. Comparing the query to every single vector would take far too long and far too much memory. Yet real systems answer in milliseconds. The secret is that they cheat, a little, on purpose.

• Exact search does not scale
• Answer in milliseconds

In the last episode we covered cosine versus dot product, and exact nearest neighbour search, the brute force scan. It is perfectly correct, but its cost grows linearly with the number of vectors. Today we fix that with approximate nearest neighbour indexes: HNSW, IVF, and product quantization.

• Episode 12: exact search
• Cost grows linearly

The core idea is a trade. We accept that the index might occasionally miss one of the true top ten neighbours, and in return we get searches that are orders of magnitude faster. We measure the damage with recall at k: of the true top k neighbours, what fraction did the index return?

• Recall@k measures quality
• Give up a little, gain a lot

Here is the plan. First, HNSW, a layered graph you can walk through. Second, IVF, which splits space into cells. Third, product quantization, which compresses vectors into tiny codes. Then we combine them, run real code in FAISS, compare the trade-offs, and look at the mistakes that bite people in production.

• HNSW graphs
• IVF clustering
• Product quantization
• FAISS code

Think of how a letter can reach a stranger through a few acquaintances. That is a small-world network: mostly local friendships, plus a few long-range links, so any two nodes are only a handful of hops apart. If we connect each vector to some of its near neighbours, we get a graph that we can navigate toward a query.

• Short paths between any nodes
• Few long-range links

Greedy search is simple. Start at some node, look at its neighbours, and move to whichever is closest to the query. Repeat until no neighbour is closer than where you stand. The danger is getting stuck in a local minimum, and on a flat graph, a long walk from a poor starting point is slow.

• Hop to the closest neighbour
• Stop at a local minimum

HNSW, hierarchical navigable small world, adds layers, like a highway system. The top layer has very few nodes and long links, the next has more, and the bottom layer contains every vector. Each vector is assigned a maximum layer at random with an exponentially decaying probability, so higher layers are sparse automatically.

• Top layers: few nodes, long jumps
• Bottom layer: all nodes

A query enters at the top layer's entry point and greedily walks to the closest node it can find. That node becomes the starting point on the layer below, and we repeat. Long hops first, fine hops last. At layer zero we switch from pure greedy to a beam search that keeps a list of the best candidates, and returns the top k.

• Enter at top layer
• Greedy descend each layer
• Beam search at layer 0

Three parameters matter. M is how many links each node keeps; more links mean better recall and more memory. EfConstruction is the candidate list size while building the graph; larger values give a better graph but a slower build. EfSearch is the candidate list size at query time, and it is your main knob: bigger means higher recall and slower queries.

• M: links per node
• efConstruction: build beam width
• efSearch: query beam width

Let us walk a tiny search with efSearch equal to two. Seven nodes, A through G, and the query. We enter at A, whose distance to the query is nine. Its neighbours are B at six and C at seven. We expand B, whose neighbours include D at three and E at four. The candidate list keeps the best two, D and E.

• Query q, entry node A
• Track candidates, keep best 2

Next we expand D. Its neighbour G has distance five, which is worse than both of our two candidates, so it is not kept. We then expand E, finding nothing better. The nearest unexplored candidate is now farther than the worst in our list, so we stop. We visited only a handful of nodes, not the whole graph, and returned D and E.

• Expand best unexplored candidate
• Stop when none can improve

On realistic data, HNSW search cost grows roughly logarithmically with the number of vectors, which is why it is so popular. The price is memory. The full vectors stay in RAM, plus links. With M equal to sixteen, the bottom layer keeps up to about thirty two links per node at four bytes each, roughly one hundred twenty eight bytes of graph overhead per vector. Inserting new vectors is natural, but deletions are awkward.

• Roughly logarithmic search
• Memory for links
• Inserts are supported

IVF takes a completely different approach. Instead of a graph, it partitions space. Imagine a library: rather than checking every book, you walk to the right shelf. If we group similar vectors together, then for a query we only need to look inside the groups closest to it.

• Cluster the vectors
• Search only nearby cells

We run k-means, as in the ML course's clustering lesson, on a sample of the data, producing nlist centroids. Every vector is assigned to its nearest centroid, and each cell stores a list of the vector ids it owns. That list is the inverted file. A common rule of thumb sets nlist near the square root of the number of vectors, though you should tune it.

• nlist centroids
• Assign each vector to nearest
• Inverted lists per cell

At query time we compare the query to the nlist centroids, pick the nprobe closest cells, and scan only the vectors inside them. With one million vectors and nlist of one thousand, each cell holds about one thousand vectors. Probing ten cells scans around ten thousand vectors, about one percent of the data, plus one thousand cheap centroid comparisons.

• Find nprobe closest centroids
• Scan only those lists

Here is where recall is lost. If the query sits near a cell boundary, its true nearest neighbour may live in the neighbouring cell. With nprobe equal to one, we never look there and we miss it. Raising nprobe to two or three catches it. In high dimensions, many boundaries are close by, so you often need to probe several cells.

• True neighbour in adjacent cell
• Higher nprobe recovers it

Suppose nlist is one hundred, so each cell has about one percent of the data. Nprobe of one scans one percent, five scans five percent, twenty scans twenty percent, and one hundred scans everything, which equals exact search. Recall climbs steeply at first and then flattens. The exact recall numbers depend on your data, so you must measure them. The shape of the curve is what to expect.

• Scan fraction = nprobe / nlist
• Recall rises, then plateaus

IVF adds very little memory beyond the vectors themselves, just centroids and ids. It requires a training step, and if your data distribution shifts, the centroids become stale and cells become unbalanced. Adding vectors is easy, since you just assign them to a cell, but quality slowly degrades until you retrain. Queries are usually slower than HNSW at equal recall, but builds are faster.

• Cheap memory overhead
• Needs training step
• Drift hurts clusters

Both HNSW and IVF still store the full vectors. A seven hundred sixty eight dimension float32 vector takes seven hundred sixty eight times four, which is three thousand seventy two bytes. One hundred million of them need about three hundred seven gigabytes of RAM. We need to compress vectors, while still being able to estimate distances. That is what product quantization does.

• 768 floats × 4 bytes
• = 3072 bytes each
• 100M vectors ≈ 307 GB

Could we just cluster whole vectors and store the centroid id? To get decent accuracy we would need an astronomically large number of centroids, and k-means could never train that. With only 256 centroids, an id fits in one byte, but 256 prototypes for a whole space is far too coarse. Product quantization escapes this by splitting the vector first.

• Full codebook is impossible
• 256 codes need only 1 byte

Split the vector into m equal pieces. With m equal to ninety six, each subvector has seven hundred sixty eight divided by ninety six, which is eight dimensions. Now we treat each of the ninety six subspaces independently, and run k-means with 256 centroids in each one. Each subspace gets its own small codebook.

• 768 dims into m = 96 pieces
• Each piece: 8 dims

To encode a vector, for each subvector we find the nearest of the 256 centroids in that subspace and store its index, a number from zero to two fifty five, which is one byte. Ninety six subvectors give ninety six bytes. The original three thousand seventy two bytes shrink to ninety six, a compression of thirty two times.

• Nearest centroid per piece
• Store 96 ids of 1 byte

Let us derive it generally. With k equal to 256 centroids, each code needs log base two of 256, which is eight bits. So a vector costs m bytes. The original costs four times d bytes. The ratio is four d over m. For d of 768 and m of 96, that is 3072 over 96, or 32. Codebooks cost m times 256 times d over m floats, which is 256 times 768 floats, under one megabyte. That is negligible.

• Bits per code = log2(256) = 8
• Bytes = m
• Ratio = 4d / m

Now, how do we compute distances to compressed vectors? With asymmetric distance computation, the query stays uncompressed. For each of the ninety six subspaces, we precompute the squared distance from the query's subvector to all 256 centroids. That yields a lookup table of ninety six by 256 entries, built once per query.

• Query stays full precision
• Build lookup table per query
• Sum table entries per vector

To score a stored vector with code 17, 203, 5 and so on, we simply read table entry row one column 17, row two column 203, row three column 5, and add them up. Ninety six lookups and additions replace seven hundred sixty eight subtractions and multiplications. The result approximates the true squared distance, and the error comes from replacing each subvector with its centroid.

• Distance ≈ sum of m lookups
• No float math on stored vectors

Compression is lossy. Fewer bytes per vector mean more error and lower recall. A common fix is reranking: use compressed codes to find, say, a few hundred candidates, then fetch the original vectors and compute exact distances to pick the final top ten. This recovers much of the accuracy while keeping the bulk of the work cheap.

• Distances are approximate
• Quality depends on m and codebooks
• Rerank to recover

IVF-PQ combines the two ideas. IVF decides which cells to visit, and PQ stores the vectors in those cells as tiny codes. So we scan only a small fraction of the data, and each scanned vector is just ninety six bytes. This is how billion scale collections fit on a single machine's memory.

• IVF prunes the search
• PQ compresses the lists

A refinement is to encode residuals. Instead of quantizing the raw vector, we subtract its cell's centroid and quantize what remains. Residuals have a much smaller spread, so the same 256 centroids per subspace represent them more precisely. The FAISS IVFPQ index does this by default, and the lookup tables are adjusted per probed cell.

• Encode vector minus centroid
• Smaller range, less error

These pieces mix in other ways too. Some systems use an HNSW graph over the IVF centroids to pick cells faster when nlist is huge. Others store PQ codes inside an HNSW graph to cut its memory. The building blocks are the same: a way to find candidates quickly, and a way to represent vectors compactly.

• HNSW over centroids
• HNSW with PQ codes

Now the code. We generate data locally with numpy: say a hundred thousand random float32 vectors of dimension 128, plus a thousand queries. Real embeddings have more structure than random noise, so treat results as a method demonstration, not a benchmark. We build faiss IndexFlatL2, add the vectors, and search for the top ten. This exact result is our ground truth.

• Random normalized vectors
• IndexFlatL2 as exact baseline

We write a small helper: for each query, count how many of the returned ten ids appear in the true ten, then average and divide by ten. Next, build IndexHNSWFlat with M equal to sixteen, set hnsw dot efConstruction to 200, add the data, then loop efSearch over 16, 64, and 256, printing recall and query time. You will see recall rise with efSearch while time grows.

• recall@10 vs ground truth
• IndexHNSWFlat(d, M)

For IVF, create a flat quantizer, then IndexIVFFlat with nlist of 1024. You must call train on a sample before add. Then sweep nprobe over 1, 8, 32 and 128, and measure. For compression, build IndexIVFPQ with nlist 1024, m equal to sixteen, and eight bits per code. For dimension 128, that is sixteen bytes per vector versus 512, and you should see recall drop relative to IVF flat.

• Quantizer + train + add
• Sweep nprobe
• IVFPQ(d, nlist, m, 8 bits)

Run everything and plot recall against query time for each index and parameter setting. You get a Pareto frontier: curves that move up and left are better. Pick the cheapest setting that meets your recall target, say ninety five percent at k equal to ten. Do this on your own embeddings and your own queries, because the best parameters change with data.

• Plot recall vs latency
• Pick the knee of the curve
• Never trust defaults

Here is the comparison. Flat: perfect recall, no build, highest query cost. HNSW: excellent recall at low latency, but the highest memory and slowest build. IVF flat: modest overhead, fast build, needs training. IVF-PQ: lowest memory, lower recall ceiling unless you rerank. For updates, flat and HNSW take inserts easily, while IVF slowly drifts.

• Memory
• Build time
• Updates
• Recall

As a rough guide: for small collections, even exact search can be fine, so do not over-engineer. For up to millions of vectors with enough RAM, HNSW is a strong default. When memory is the bottleneck, reach for IVF-PQ, ideally with reranking. These are heuristics, not laws. Your recall target, latency budget and hardware decide.

• Under ~1M vectors: HNSW or flat
• Memory-bound: IVF-PQ
• Always validate recall

The first mistake is shipping default parameters. A low default efSearch or nprobe can give you quick queries and quietly poor recall, and nobody notices because the results still look plausible. The fix is a labeled evaluation: sample queries, compute exact neighbours offline, and track recall at k as you tune and as the data grows.

• Defaults suit nobody
• Tune efSearch and nprobe
• Measure recall@k

The second mistake is ignoring filters. Say you search for the top ten, then keep only results from one tenant. If that tenant owns two percent of the data, a post-filter may leave you with almost nothing. Filtering inside a graph can also break connectivity and hurt recall. Look for filter-aware search, partitioning by tenant, or larger candidate lists, and test with real filters.

• Metadata filters shrink candidates
• Post-filtering can return too few
• Pre-filter or filter-aware search

A few more traps. Make sure the index metric matches your embeddings: normalize vectors if you use inner product as cosine, as in the last episode. Retrain IVF and PQ when your data distribution changes. And remember deletes are often soft in HNSW, leaving tombstones until you rebuild. Plan periodic rebuilds into your operations.

• Metric must match training
• Normalize for cosine
• Retrain IVF after drift
• Deletes in HNSW

Let us recap. Approximate indexes trade a bit of recall for large speed gains. HNSW walks a layered graph, tuned with M, efConstruction and efSearch. IVF clusters into nlist cells and probes nprobe of them. Product quantization turns 3072 bytes into 96 with codebooks and lookup tables, and IVF-PQ combines it all. Always measure recall against exact search.

• HNSW: layered graph
• IVF: cells and nprobe
• PQ: bytes and lookups

These indexes are the engines. In the next episode, vector databases in practice, we will see how they wrap an index with storage, metadata filtering, persistence, replication and APIs, and how to choose between them.

• Indexes become products
• Filtering, persistence, scaling