Fill in the IVF nlist rule of thumb.

IVF is one of the two main families of approximate nearest neighbor indexes (the other being graph-based, like HNSW). The idea: split the corpus into clusters using k-means, and at query time only search the clusters most relevant to the query. There are two numbers you need to set. nlist is the number of clusters - a build-time choice. nprobe is how many of those clusters you actually search at query time - a runtime knob that trades recall for latency. For nlist, the standard rule of thumb is sqrt(N), where N is the number of vectors. So for 1 million vectors, you would start at nlist ~ 1000 clusters. For 100 million vectors, ~10,000 clusters. Why that number? Each query does two pieces of work: comparing against all nlist centroids to pick which clusters to search, then scanning the vectors inside those chosen clusters. If you set nlist too small (say 10), each cluster has N/10 vectors and scanning even one of them is slow. If you set nlist too large (say N/10), there are so many centroids that comparing against all of them dominates the query. The balance point - where the two costs are roughly equal - happens when the number of centroids equals the expected size of each cluster. That is exactly sqrt(N). This is just a starting point. FAISS often recommends 4*sqrt(N) for production indexes where you want a bit higher recall (more clusters = smaller, more precise partitions). Always run a sweep on your data: try sqrt(N), 4*sqrt(N), maybe 16*sqrt(N), and pick the value that gives you the best recall-latency tradeoff at your target nprobe.

nlist ~ sqrt(N). IVF query cost is nlist (centroid scan) + nprobe * N/nlist (partition scan). Differentiating with respect to nlist and setting to zero (for fixed nprobe) gives a minimum around sqrt(nprobe * N), which is sqrt(N) when nprobe is small. At nlist > sqrt(N) centroid comparison dominates; at nlist < sqrt(N) each partition is too large. FAISS recommends sqrt(N) to 4*sqrt(N) depending on recall target.