The ANN families and their build cost

What do IVF, HNSW and PQ each trade, and why can ANN structures not be merged?

The three ANN families as three orthogonal levers

IVF, HNSW and PQ are usually presented as competing index types. They are not competitors. They answer three different questions and compose freely.

IVF partitions

IVF (Inverted File index): cluster the corpus into k cells (using an algorithm such as k-means, which finds k representative centre points, called centroids). Store each vector with its cell. At query time, probe only the nprobe cells nearest the query. Candidates drop by roughly k / nprobe.

Structurally this is partition pruning with learned, data-dependent boundaries instead of declared ones. It inherits partition pruning's failure mode exactly: a true neighbour sitting just across a cell boundary is invisible unless its cell is probed. So nprobe is the recall knob, a straight purchase of recall with scan volume. (How many cells to build, nlist ≈ √(N·nprobe), falls out of the index's own pay-off arithmetic.)

It also inherits partitioning's other failure: real data clusters, so cells are unbalanced, and a query landing in a dense region probes far more vectors than one landing in a sparse one. Variance costs more than volume again: the latency distribution is set by the data's density distribution.

HNSW navigates

HNSW (Hierarchical Navigable Small World graph): build a proximity graph where each vector is linked to nearby vectors and a few far ones (long-range links), then greedily walk from an entry point toward the query, always moving to the neighbour closest to the query. Hops scale roughly logarithmically with corpus size.

But each hop is a data-dependent pointer dereference: you cannot know the next address until you have read the current node. That is the structural break from the overview, appearing inside vector search: no prefetch, no vectorization, no batching by address.

This gives the real distinction between the two, and it is not accuracy:

IVF is scan-shaped and therefore survives a storage hierarchy. HNSW is latency-shaped and effectively demands RAM. That is the choice, and it is bandwidth versus latency, not quality.

PQ compresses

PQ (Product Quantization): split each vector into m subvectors; quantize each subvector against a 256-entry codebook (a dictionary of 256 representative subvectors); store one byte per subvector. With d = 768 floats (3,072 bytes) and, say, m = 96, each vector becomes 96 bytes: a 32x reduction.

Distances are computed by precomputing a small query-to-codebook table once per query, and then summing m table lookups per candidate. A d-dimensional multiply-add chain becomes m byte-indexed lookups.

# once per query: table[j][c] = distance between query subvector j and codeword c
table = [[dist(q_sub[j], codebook[j][c]) for c in range(256)] for j in range(m)]

# per candidate: code is m bytes, one codeword index per subvector
def approx_distance(code):
    return sum(table[j][code[j]] for j in range(m))

This is dictionary encoding doing double duty as a compute mechanism: the operator runs directly on the encoded representation and never decodes. The cost is that the distances are now estimates. So the usual arrangement is a quantized scan for candidates, followed by exact distance on the survivors: filter-and-refine again. Scalar quantization (reducing each number to 8 or fewer bits) and binary quantization (1 bit per dimension) with exact rerank are architecturally identical to PQ with a very different cost profile, and are the currently moving part of the field.

They compose

The three levers answer different questions: which candidates (IVF), how to reach them (HNSW), what each one costs to evaluate (PQ). Every production system picks a point in that product space rather than an index type. (One variant changes the cost model by an order of magnitude: multi-vector, late-interaction retrieval, where each document is many vectors, for example one per word.)

One line: partition, navigate, compress. Three independent levers, and IVF-versus-HNSW is a bandwidth-versus-latency decision, not an accuracy one.

Build cost, mutability, and why merging does not work

HNSW construction inserts each vector by searching for its neighbours, so build cost is roughly N × query cost: hours for large corpora. IVF centroids are fitted to a sample of the distribution. Both are global structures fitted to the whole dataset, which is what makes them different from every index met so far.

Deletes cannot remove a node from a navigable graph without risking disconnection, so deletes are tombstones: the node remains, is traversed, and is discarded at collection time. Insertions degrade graph quality gradually, because the long-range links were chosen for a distribution that has since moved. So vector indexes are quasi-static and follow the familiar shape: immutable segments, search-all-and-merge, background rebuild.

Here the LSM pattern breaks

Two HNSW graphs do not merge into an HNSW graph. Two sets of k-means centroids do not merge into valid centroids. The only "merge" available is a rebuild from the underlying vectors.

Mergeability is an algebraic property of the structure, not a storage convention. Sorted runs, Bloom filters (small structures that answer "is this item probably in the set?"), HyperLogLog sketches (which estimate the count of distinct items) and monoidal aggregates (aggregates with a combining operation, like sum) all merge. Graphs, trees fitted to distributions and learned structures generally do not. When you meet a new index anywhere, ask: "does it merge, or must it rebuild?" The answer predicts its entire maintenance story.

The practical consequence: vector index maintenance is a periodic full rebuild rather than continuous compaction. It is a scheduled, expensive, all-or-nothing operation. That makes freshness much more expensive than in text, where a one-second flush is genuinely cheap.

One line: ANN structures are fitted globally, so they tombstone rather than delete and rebuild rather than merge. Mergeability is algebra, not policy.