HNSW, IVF, and Quantization

Every approximate index is built on one of two ideas, and knowing which you are using explains its behaviour.

Partitioning divides the space into regions, and a query searches only the regions likely to contain neighbours. You skip most of the data by deciding, cheaply, that it cannot be relevant. IVF is the canonical example.

Graph traversal connects each vector to a set of neighbours and walks the graph greedily toward the query. You never consider most of the data because you never reach it. HNSW is the canonical example.

The two have different characters. Partitioning has a hard failure mode at boundaries: a true neighbour sitting in an unprobed partition is simply never seen, and no amount of care within the probed partitions recovers it. Graph traversal degrades more gracefully, because the greedy walk can route around a poor local decision, but it costs far more memory for the edges.

A third idea, quantization, is orthogonal to both. It compresses the vectors themselves so each distance computation is cheaper and the whole index fits in less memory. It composes with either strategy, which is why production indexes are usually named as combinations.

The rest of this lesson takes each in turn, then shows how they compose.

Hierarchical Navigable Small World graphs, introduced by Malkov and Yashunin, are the default index in most vector databases, and the construction is elegant.

Start with the small-world idea. Connect each vector to its nearby neighbours, plus a few long-range links. Greedy search then works: from any starting point, repeatedly move to whichever neighbour is closer to the query, and stop when no neighbour improves. The long-range links prevent the walk getting stuck in a distant region.

The hierarchical part adds layers. The top layer contains a small random subset with long edges; each layer down is denser, and the bottom contains everything. A search enters at the top, greedily descends to the closest point in that sparse layer, drops to the next layer using that point as the entry, and repeats. The upper layers do coarse navigation cheaply, the bottom layer does fine search.

The analogy that makes it stick: navigating by taking a long flight to the right country, then a train to the right city, then walking. Each layer covers distance at its own scale.

The properties that matter in production. Recall is high, typically the best available at a given latency. Memory is substantial because every node stores its edges. Build is slow, since inserting a vector means searching the graph to find its neighbours. And deletion is awkward, which is the subject of a later step.

HNSW exposes three knobs, and knowing which does what is most of tuning it.

M is the number of bidirectional edges per node in the lower layers. Higher M means a denser graph, better recall, more memory, and slower builds. Typical values run from 16 to 64. This is fixed at build time and changing it means rebuilding.

efConstruction is how wide the search is when inserting a vector to find its neighbours. Higher means better edge choices, so better recall for the same M, at the cost of build time only. It does not affect query time or memory, which makes it the cheapest quality lever: raise it until build time hurts.

ef, or efSearch, is how many candidates the search keeps while traversing at query time. This is the runtime recall-latency dial, adjustable per query without rebuilding. It must be at least k, and raising it raises both recall and latency smoothly.

The practical division: M and efConstruction are build-time capacity decisions, ef is the runtime control. Tune ef first because it is free to change, and only revisit M if ef alone cannot reach your recall target.

Inverted File indexes take the partitioning route, and they are simpler to reason about than graphs.

Build runs k-means over the vectors to produce a set of centroids, conventionally called nlist. Each vector is assigned to its nearest centroid, producing lists. That is the whole structure.

Search computes the distance from the query to every centroid, picks the nprobe closest, and scans only the vectors in those lists. If nlist is 4096 and nprobe is 32, you compute 4096 cheap centroid distances and then scan roughly 32 divided by 4096, under one percent, of the data.

The parameters. nlist sets partition granularity, with a common heuristic of roughly the square root of the number of vectors. Too few means each list is large and you scan a lot; too many means centroid comparison itself becomes expensive and lists get sparse. nprobe is the runtime recall-latency dial, the direct analogue of HNSW's ef.

IVF's characteristic weakness is the boundary problem. A true neighbour in an unprobed partition is invisible, and since query points frequently sit near a boundary between cells, this is common rather than exceptional. Raising nprobe mitigates it at proportional cost.

Its advantages are real: much lower memory than a graph, much faster builds, and it requires a training step on a representative sample, which is a genuine operational difference from HNSW.

Quantization compresses the vectors themselves, and it is where the largest memory savings live.

Scalar quantization reduces the precision of each component, typically from 32-bit floats to 8-bit integers. A straightforward four times reduction, and for most embedding models the quality loss is small, because the extra precision was carrying little information. This is the first thing to try and it is frequently sufficient.

Binary quantization goes to one bit per dimension, keeping only the sign. Thirty-two times smaller, and distance becomes a Hamming computation that hardware does extremely fast. Quality loss is real but recoverable through reranking, described below.

Product quantization is the more sophisticated scheme. Split the vector into m subvectors, run k-means on each subspace to learn a codebook of typically 256 centroids, and store each subvector as the one-byte index of its nearest centroid. A 768-dimension float32 vector at 3072 bytes becomes, with m of 96, just 96 bytes: a 32 times reduction. Distances are computed from precomputed lookup tables rather than arithmetic on the original values.

The pattern that makes aggressive quantization workable is rescoring. Search the compressed index to get a candidate set several times larger than k, then recompute exact distances for only those candidates using full-precision vectors held on disk or in a separate store, and rerank. You get compressed-index speed with close to full-precision recall, at the cost of keeping the originals somewhere.

Production indexes are combinations, and the naming convention in libraries such as FAISS reads left to right as a pipeline.

A flat index is exact search with no compression. Perfect recall, full memory.

IVF combined with flat storage partitions the space but stores vectors uncompressed: good recall, moderate memory, fast build.

IVF combined with product quantization partitions and compresses: the classic large-scale configuration, capable of holding billions of vectors in memory that would otherwise be impossible, with recall recovered by rescoring.

HNSW with flat storage is the default in most vector databases: best recall per unit latency, highest memory.

HNSW combined with scalar or product quantization compresses the vectors while keeping the graph, cutting memory substantially while retaining graph-quality navigation. Increasingly the default at scale.

And disk-based variants keep the bulk of the index on SSD with a compressed representation in memory, trading latency for capacity.

The selection logic is straightforward. Under a hundred thousand vectors, flat. Up to a few million with memory available, HNSW flat. Beyond that, or where memory is constrained, add quantization to HNSW. At very large scale with tight memory, IVF with product quantization and rescoring. And where writes dominate reads, prefer IVF, because HNSW builds are expensive.

Almost every real application needs to combine similarity with a filter: nearest neighbours where the tenant is this customer, the document is not archived, and the date is within range. This is the single most underestimated problem in vector search.

Three approaches, each with a failure mode.

Pre-filtering applies the predicate first, then searches within the surviving set. Correct by construction, and it defeats the index: an approximate structure built over the whole corpus cannot be traversed over an arbitrary subset, so you fall back to scanning the filtered set. Fine when the filter is highly selective, catastrophic when it leaves millions.

Post-filtering searches first, then discards non-matching results. Fast, and it silently returns too few. Ask for 10, retrieve 10, discard 8 that fail the filter, return 2. The usual patch is over-fetching, which works until a selective filter makes it fail unpredictably.

Filtered search integrates the predicate into traversal, checking it as the graph is walked or restricting probed partitions. This is what mature systems implement and it is the correct answer, though it degrades when the filter is very selective, because the graph's connectivity assumes the full node set.

The practical guidance: know which your database does, test with your real filter selectivity rather than benchmarks, and consider separate indexes per high-cardinality partition such as tenant, which sidesteps the problem entirely.

Vector indexes are built for reads, and mutation is where operational pain concentrates.

Insertion into HNSW means searching the graph to find neighbours and adding edges, which is comparatively expensive per vector and degrades graph quality over time as the structure drifts from what a fresh build would produce.

Deletion is worse. Removing a node from a navigable graph can disconnect regions that routed through it, so implementations almost universally use tombstones: mark deleted, filter from results, leave in the graph as a routing node. The consequences accumulate. Memory is not reclaimed. Search still traverses dead nodes. And a corpus with heavy churn eventually consists substantially of tombstones, at which point recall and latency both degrade.

The standard remedy is periodic rebuilding, which is a real operational cost that capacity planning must include and that teams routinely discover late.

IVF handles mutation better. Insertion assigns to the nearest centroid and appends, which is cheap. Deletion removes from a list. What degrades is the partitioning itself: centroids learned from the original distribution become poor as the data shifts, so lists grow uneven and recall drops, requiring periodic retraining.

The design consequence worth internalising: if your corpus changes constantly, factor rebuild cost into the choice up front, and prefer IVF or a segment-based architecture where immutable segments are merged in the background.