ANN indexing: HNSW and IVF

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, which is HNSW's main drawback.

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

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 actually 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 eliminating it. Deletion is also awkward — removing a node can disconnect the graph — so most implementations tombstone and rebuild periodically.

IVF's failure is cleaner: a true neighbour sitting just across a cluster boundary 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 every 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 — typically 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 become approximate on top of the search already 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 actually 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 — which is worth checking before adopting anything 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 exactly means comparing the query against every stored vector. With a million 768-dimensional vectors that is 768 million multiply-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 magnitude of speed. "Approximate" means they may miss a true nearest neighbour occasionally; in practice, well-tuned indexes return 95–99% of them, and the misses rarely change what a user sees.

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 every vector to its nearest centroid, producing 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 examined. The speed-up is proportional.

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

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

IVF requires a training step on a representative sample before vectors can be added, which is the main operational difference 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 typically higher than IVF at the same latency.

Three parameters:

M and ef_construction are build-time and fix the index's quality 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 measuring 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 every setting of nprobe.

import numpy as np

rng = np.random.default_rng(11)
N, D, NLIST = 4000, 32, 64

# clustered data, because real embeddings are clustered and uniform
# random vectors would make IVF look better than it is
CENTRES = rng.normal(0, 1, (12, D))
labels = rng.integers(0, 12, N)
X = CENTRES[labels] + rng.normal(0, 0.55, (N, D))
X = X / np.linalg.norm(X, axis=1, keepdims=True)

Q = 200
qlab = rng.integers(0, 12, Q)
QY = CENTRES[qlab] + rng.normal(0, 0.55, (Q, D))
QY = QY / np.linalg.norm(QY, axis=1, keepdims=True)

print("%s vectors of %d dimensions, in %d natural clusters."
      % ("{:,}".format(N), D, len(CENTRES)))
print()
print("EXACT SEARCH first, so there is a truth to compare against:")
K = 10
sims = QY @ X.T
truth = np.argsort(-sims, axis=1)[:, :K]
print("   every query compared against every vector: %s dot products"
      % "{:,}".format(Q * N))
print("   this is the thing that does not scale. at %s vectors and 1000"
      % "{:,}".format(10 ** 8))
print("   queries a second it is %s dot products a second, which is not"
      % "{:,}".format(10 ** 11))
print("   an engineering problem you can optimise your way out of.")
print()

print("BUILD THE IVF INDEX. step 1: cluster the vectors, %d centroids."
      % NLIST)
cent = X[rng.choice(N, NLIST, replace=False)].copy()
for _ in range(12):                       # plain k-means
    assign = np.argmax(X @ cent.T, axis=1)
    for c in range(NLIST):
        m = assign == c
        if m.any():
            v = X[m].mean(axis=0)
            cent[c] = v / np.linalg.norm(v)
sizes = np.bincount(assign, minlength=NLIST)
print("   cluster sizes: min %d, median %d, max %d, mean %.1f"
      % (sizes.min(), int(np.median(sizes)), sizes.max(), sizes.mean()))
print("   step 2: store each vector in its nearest centroid's list. that")
print("   is the whole index -- %d lists, %s vectors, no graph and no"
      % (NLIST, "{:,}".format(N)))
print("   tree.")
print()

print("SEARCHING. compare the query to the %d centroids, pick the nprobe" % NLIST)
print("closest, and scan only those lists:")
print("%-10s %14s %16s %14s %16s"
      % ("nprobe", "recall@10", "vectors scanned", "% of index", "speedup"))
sweep = {}
for nprobe in (1, 2, 4, 8, 16, 32, 64):
    hits = 0
    scanned = 0
    for i in range(Q):
        cs = np.argsort(-(QY[i] @ cent.T))[:nprobe]
        mask = np.isin(assign, cs)
        idx = np.where(mask)[0]
        scanned += len(idx)
        if len(idx):
            local = idx[np.argsort(-(QY[i] @ X[idx].T))[:K]]
        else:
            local = np.array([], int)
        hits += len(set(local.tolist()) & set(truth[i].tolist()))
    rec = hits / float(Q * K)
    avg = scanned / float(Q)
    sweep[nprobe] = (rec, avg)
    print("%-10d %14.4f %16.0f %13.1f%% %15.1fx"
          % (nprobe, rec, avg, 100 * avg / N, N / max(avg, 1)))
print("   read the first row honestly: probing ONE cluster scans %.1f%% of"
      % (100 * sweep[1][1] / N))
print("   the index and recovers %.0f%% of the true neighbours. that is not"
      % (100 * sweep[1][0]))
print("   'nearly all' -- more than half the right answers are gone.")
print("   the interesting row is nprobe = 4: %.0f%% recall for %.1f%% of the"
      % (100 * sweep[4][0], 100 * sweep[4][1] / N))
print("   work, a %.0fx speedup. the curve is steep early and flat late,"
      % (N / sweep[4][1]))
print("   which is the shape that makes ANN worth using at all -- most of")
print("   the accuracy is available for a small fraction of the cost, and")
print("   the last few percent of recall costs almost everything.")
print("   it works because true neighbours mostly share a cluster with the")
print("   query, which is an assumption about the DATA: on uniformly")
print("   random points there are no clusters and IVF would buy nothing.")
print("   and read the last row: at nprobe = nlist you are scanning")
print("   everything, recall is 1.0, and you have reinvented exact search")
print("   with extra steps. every row between is the actual product.")
print()

print("WHERE THE MISSES COME FROM. a true neighbour is lost when it sits")
print("in a cluster the query did not probe -- which happens when the")
print("query lands near a boundary:")
d1 = []
for i in range(Q):
    s = np.sort(-(QY[i] @ cent.T))
    d1.append(-s[0] + s[1])              # gap between best and 2nd centroid
d1 = np.array(d1)
close = d1 < np.median(d1)
def recall_at(nprobe, subset):
    h = t = 0
    for i in np.where(subset)[0]:
        cs = np.argsort(-(QY[i] @ cent.T))[:nprobe]
        idx = np.where(np.isin(assign, cs))[0]
        local = idx[np.argsort(-(QY[i] @ X[idx].T))[:K]] if len(idx) else []
        h += len(set(np.asarray(local).tolist()) & set(truth[i].tolist()))
        t += K
    return h / float(t)
print("%-34s %16s %16s" % ("", "recall@10, np=1", "recall@10, np=4"))
print("%-34s %16.4f %16.4f"
      % ("queries near a cluster boundary", recall_at(1, close),
         recall_at(4, close)))
print("%-34s %16.4f %16.4f"
      % ("queries deep inside a cluster", recall_at(1, ~close),
         recall_at(4, ~close)))
print("   the loss is not spread evenly. queries that fall between")
print("   centroids lose far more, and raising nprobe helps them far more.")
print("   that is worth knowing because it means your average recall hides")
print("   a population of queries that fail much harder than the mean --")
print("   and those are the ones users complain about.")
print()

print("THE MEMORY SIDE, which is a different constraint entirely:")
print("%-30s %16s %16s" % ("", "bytes/vector", "%s vectors" % "{:,}".format(10 ** 8)))
for label, b in (("float32, %d dims" % D, D * 4),
                 ("float32, 768 dims", 768 * 4),
                 ("PQ, 96 subquantisers", 96),
                 ("PQ, 48 subquantisers", 48)):
    print("%-30s %16d %14.1f GB" % (label, b, 10 ** 8 * b / 1e9))
print("   product quantisation replaces each vector with a short code, so")
print("   %s 768-dimensional vectors go from %.0f GB -- which does not fit"
      % ("{:,}".format(10 ** 8), 10 ** 8 * 768 * 4 / 1e9))
print("   in any single machine's RAM -- to %.1f GB, which does. it costs"
      % (10 ** 8 * 96 / 1e9))
print("   accuracy, and it is usually combined with IVF rather than")
print("   chosen instead of it: IVF decides WHERE to look, PQ decides how")
print("   cheaply each comparison is done.")
print()
print("WHICH TO REACH FOR, by what is actually scarce:")
print("%-26s %s" % ("under ~10k vectors", "exact search -- IVF adds only risk"))
print("%-26s %s" % ("recall matters most", "HNSW, high ef_search"))
print("%-26s %s" % ("memory is the limit", "IVF + PQ"))
print("%-26s %s" % ("build time matters", "IVF -- HNSW is slow to build"))
print("%-26s %s" % ("frequent deletions", "IVF -- HNSW handles them poorly"))
print("   and whichever you pick, measure recall against exact search on")
print("   your own vectors, exactly as done above. it is the one number")
print("   that an ANN index cannot report about itself, and the default")
print("   parameters of every library were chosen on somebody else's data.")

Things to try

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 remember

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, which is the runtime recall/latency knob. M and efConstruction are fixed at build time. IVF is the simpler alternative — cluster then probe — cheaper to build and update, and it misses neighbours across cluster boundaries.

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 separately, and stores only the cluster ids. A 768-dimensional float32 vector (3,072 bytes) split into 96 sub-vectors with 256 centroids each becomes 96 bytes — a 32-fold reduction.

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

The cost is accuracy: the stored representation 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, which are fetched from disk.

Choosing an index by scale

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

Operational differences that matter as much as the benchmarks:

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

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

Filtered search. Applying a metadata filter can defeat the index structure, since the graph or clusters were built over everything. Modern vector databases implement filter-aware traversal; where unavailable, over-retrieve and filter afterwards.

Measuring 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 several settings of ef_search or nprobe and plot recall against latency. The resulting curve is what the parameter should be chosen from — and the shape is usually a sharp rise followed by a long flat region, so there is a clear point past which extra latency buys nothing.

Questions people ask

HNSW or IVF? HNSW for quality 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 applications. The difference is rarely visible to users, and the latency saving is large.

Does approximate search hurt RAG quality? Marginally, and far less than poor chunking or a missing reranker. It is not where the quality 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 substantially.

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

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

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, giving logarithmic search and high recall at 1.5–2× the memory.
• Product quantisation compresses vectors 30-fold, with a full-precision rerank to recover accuracy.
• Measure recall against exact search and pick parameters from the recall-latency curve.