IVF — the clustering index
IVF (inverted file index) takes the "pick your neighbourhood first" approach. It groups vectors into clusters and, at search time, only looks inside the clusters closest to the query. It is simple, memory-efficient, and the foundation of many billion-scale systems — especially when combined with quantization.
Building an IVF index
- Train: run a clustering algorithm (usually k-means) on a sample of your vectors to find
nlistcluster centres, called centroids. - Assign: put every vector into the list (the "inverted list") of its nearest centroid.
The result is like a filing cabinet with nlist drawers, each holding vectors that are close to that drawer's centroid.
Searching an IVF index
- Compare the query with all
nlistcentroids — cheap, because there are far fewer centroids than vectors. - Pick the
nprobeclosest clusters. - Compare the query with every vector in those clusters only.
- Return the top k.
If you have a million vectors in 1,000 clusters and search nprobe = 10, you compare against roughly 1% of the data.
Why results can be missed
A vector sitting near the edge of a cluster may be assigned to the neighbouring cluster. If the query lands near that border and nprobe is too small, the search never opens that cluster and misses it. Raising nprobe fixes this at the cost of speed.
The parameters
| Parameter | Meaning | Trade-off |
|---|---|---|
nlist |
Number of clusters, fixed at build time | More clusters → smaller lists, faster scans, but more centroids to compare and more border effects |
nprobe |
Clusters searched per query, set at query time | Higher → better recall, slower queries |
A common starting point for nlist is on the order of the square root of the number of vectors, then tune against real recall measurements. As with HNSW, the query-time knob (nprobe) is your main tuning lever.
IVF needs training data that looks like your real data. Training on a small or unrepresentative sample produces poor clusters — some overfull, some empty — and poor recall. If your data changes a lot over time, plan to retrain.
IVF vs HNSW
| IVF | HNSW | |
|---|---|---|
| Memory | Lower — no graph links | Higher — graph links per vector |
| Recall at low latency | Good | Usually better |
| Inserts | Easy (assign to nearest cluster), but clusters can drift | Easy, no retraining |
| Needs training | Yes | No |
| Combines with compression | Very well (IVF-PQ is a classic for huge datasets) | Also possible |
| Typical home | Very large, memory-constrained collections | Most general-purpose workloads |
IVF narrows the search to a few "drawers" before looking closely. Paired with product quantization, it is one of the standard ways to search billions of vectors on modest hardware.
Senior Full-Stack Engineer · AI & AWS. I build production search, RAG and AI systems on AWS and Postgres.