An inverted file index clusters the vectors first, then searches only the nearest few clusters.
Each cluster has a centroid, and a query is compared against those centroids rather than every vector.
Searching four clusters out of a thousand cuts the work by roughly the same factor.
The parameter that matters is how many clusters to probe: more means better recall and more time.
Vectors near a boundary can be missed, which is the recall cost you accept for the speed.
Exact nearest-neighbour search compares the query with every stored vector, and that does not scale.
An inverted file index, universally shortened to IVF, buys speed by partitioning the space first.
Building it runs k-means over a sample of the vectors to find a set of centroids.
Every vector is then assigned to its nearest centroid, forming one list per cluster.
The name comes from text search, where an inverted file maps a term to the documents containing it.
At query time the vector is compared against the centroids alone, which is a much smaller set.
The closest few clusters are selected and only the vectors inside them are scanned.
Two parameters control everything: the number of clusters and the number probed per query.
A common starting point is roughly the square root of the collection size for the cluster count.
Probing more clusters raises recall and costs time in an almost linear trade.
The failure mode is inherent to partitioning: a true neighbour may sit just across a cluster boundary.
If its centroid is not among those probed, that neighbour is never even considered.
IVF is usually paired with product quantization so the scanned vectors are also compressed.
That combination is what makes billion-scale search fit on a single machine.
Compared with HNSW it builds faster and uses less memory, while HNSW generally wins on recall at a given latency.
The corpus is clustered once, and every vector is assigned to its nearest centroid. Those clusters are the inverted lists.
A query is compared against the centroids first, which is cheap, and then only against the vectors inside the closest few clusters.
That fraction is the share of the corpus actually examined. With 4,096 lists and 16 probed, a query touches 0.4 percent of the vectors.
The usual rule sets the number of clusters near the square root of the corpus size, which balances the cost of scanning centroids against the cost of scanning lists.
Both terms are in that expression. Too few clusters and each list is enormous. Too many and finding the right ones becomes its own scan.
The probe count is the query-time dial: 1 is fast and misses a lot, 64 approaches a brute-force scan, and the recall curve between them is steep at first and then flat.
A query near the edge of a cluster has its true nearest neighbour in the adjacent cluster, which is not probed unless is large enough to include it.
That is the structural weakness of partitioning, and it is why recall at is usually poor even though the partition is good.
Probing several neighbouring clusters fixes it statistically rather than exactly, which is the honest description of what any IVF index guarantees.
Training on a sample is standard and safe, since the centroids only have to describe the shape of the distribution rather than every point.
Only the centroids and the current lists need to be resident, so a billion-vector index runs on a machine that could not hold a tenth of it as a graph.
Combined with product quantisation, each vector inside a list is stored compressed, which cuts memory by an order of magnitude and makes the scan faster still.
Insertion is cheap because a new vector joins one list, and deletion simply removes it, which is a real operational advantage over a graph index.
The cost is recall per millisecond. HNSW is faster at the same recall for anything that fits in memory, and IVF wins the moment it does not.
One question on this card. Every option explains itself once you pick, right or wrong.
17 concepts in this module, then a graded test with every answer explained.