IVF (inverted file index) groups all vectors into clusters with K-Means Clustering. At query time it searches only the nprobe clusters whose centres are closest to the question.

How it works

  • first compare the question with the cluster centres, which is cheap because is much smaller than
  • then compare it only with the vectors inside the nprobe chosen clusters
  • example: and nprobe means only of the collection is scanned

Trade-off

  • a true neighbour that sits just across a cluster border is missed
  • raising nprobe buys the recall back, at the cost of speed

More clusters probed means better recall but slower search

Tune nprobe on your own data by measuring recall@k and the time per query.

Code

import time
import numpy as np
import faiss
 
d, N_vec, n_queries = 64, 100_000, 200
rng = np.random.default_rng(0)
centres = rng.standard_normal((500, d)) * 3                 # 500 topic centres
xb = (centres[rng.integers(0, 500, N_vec)] + rng.standard_normal((N_vec, d))).astype("float32")
xq = (centres[rng.integers(0, 500, n_queries)] + rng.standard_normal((n_queries, d))).astype("float32")
 
# exact search is the ground truth
flat = faiss.IndexFlatL2(d); flat.add(xb)
_, true_nn = flat.search(xq, 10)
 
# IVF: k-means into 1024 clusters, then search only the nprobe closest clusters
ivf = faiss.IndexIVFFlat(faiss.IndexFlatL2(d), d, 1024)
ivf.train(xb)        # learns the cluster centres
ivf.add(xb)
 
for nprobe in [1, 4, 16, 64]:
    ivf.nprobe = nprobe
    t0 = time.time()
    _, found = ivf.search(xq, 10)
    t = time.time() - t0
    recall = np.mean([len(set(found[i]) & set(true_nn[i])) / 10 for i in range(n_queries)])
    print(f"nprobe={nprobe:<3} recall@10={recall:.3f}  ms/query={1000 * t / n_queries:.3f}")

Notes:

  • IndexIVFFlat needs train before add, because the cluster centres must be learned first
  • the first argument is the quantizer, an exact index used to find the closest centres
  • ivf.nprobe can be changed after building, with no retraining
  • searching a handful of clusters already finds almost all true neighbours, far faster than exact search

IVF cuts the search time, and compressing the vectors cuts the memory, see Product Quantisation (PQ).