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
nprobechosen clusters - example: and
nprobemeans only of the collection is scanned
Trade-off
- a true neighbour that sits just across a cluster border is missed
- raising
nprobebuys the recall back, at the cost of speed
More clusters probed means better recall but slower search
Tune
nprobeon 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:
IndexIVFFlatneedstrainbeforeadd, because the cluster centres must be learned first- the first argument is the quantizer, an exact index used to find the closest centres
ivf.nprobecan 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).