Approximate Search: IVF and HNSW

Skip most of the data on purpose

For millions of vectors, scanning everything is too slow, so approximate nearest neighbour (ANN) indexes avoid looking at most of the data. IVF (inverted file) clusters the vectors into nlist cells with k-means; a query looks only in the nprobe closest cells. HNSW (hierarchical navigable small world) builds a layered graph in which each vector links to near neighbours; a query walks the graph greedily toward the target, and efSearch controls how many candidates it keeps while walking. Both give recall below 100%: the true nearest neighbour is sometimes missed. Increasing nprobe or efSearch raises recall and latency together, so you tune on your data to the recall you need. IVF needs a training step and uses less memory; HNSW has no training, is very fast and accurate, but uses more memory and supports updates less cheaply.

Recall versus search effort, run

I ran this in a Python virtual environment with numpy 2.5.3, scikit-learn 1.9.1 and faiss-cpu 1.15.1, with fixed random seeds so the numbers repeat. On 20,000 clustered 64-dimension vectors, IVF with 100 cells reaches 0.743 recall@10 when probing 1 cell, 0.998 with 4 and 1.000 with 16. HNSW goes from 0.643 at efSearch=4 to 0.932 at 16 and 1.000 at 64. Recall is measured against the exact flat-index answers. Latency is not shown because timings vary by machine.

import numpy as np, faiss
rng = np.random.default_rng(0)
d, n, nq = 64, 20000, 200
centers = rng.normal(size=(50, d)) * 3
xb = (centers[rng.integers(0, 50, n)] + rng.normal(size=(n, d))).astype("float32")
xq = (centers[rng.integers(0, 50, nq)] + rng.normal(size=(nq, d))).astype("float32")

flat = faiss.IndexFlatL2(d); flat.add(xb)
_, truth = flat.search(xq, 10)                                   # exact answers

def recall(found): return float(np.mean([len(set(f) & set(t)) / 10 for f, t in zip(found, truth)]))

ivf = faiss.IndexIVFFlat(faiss.IndexFlatL2(d), d, 100); ivf.train(xb); ivf.add(xb)
for nprobe in (1, 4, 16):
    ivf.nprobe = nprobe
    print(f"IVF  nprobe={nprobe:2d} recall@10 = {recall(ivf.search(xq, 10)[1]):.3f}")

hnsw = faiss.IndexHNSWFlat(d, 16); hnsw.hnsw.efConstruction = 100; hnsw.add(xb)
for ef in (4, 16, 64):
    hnsw.hnsw.efSearch = ef
    print(f"HNSW efSearch={ef:2d} recall@10 = {recall(hnsw.search(xq, 10)[1]):.3f}")

Output:

IVF  nprobe= 1 recall@10 = 0.743
IVF  nprobe= 4 recall@10 = 0.998
IVF  nprobe=16 recall@10 = 1.000
HNSW efSearch= 4 recall@10 = 0.643
HNSW efSearch=16 recall@10 = 0.932
HNSW efSearch=64 recall@10 = 1.000

Tune against exact answers

Compute recall@k of your ANN index against a flat index on a sample of real queries. Pick the cheapest setting that meets your target.

Quick check: What does raising nprobe (IVF) or efSearch (HNSW) do?

• Raises recall and also latency
• Lowers both recall and latency
• Changes the embedding model
• Deletes vectors