IVF Index: Clustering-Based Vector Search & Partitioning › Choosing the Number of Centroids

The number of centroids $k$ affects both the granularity of the partitioning and the overhead of the centroid comparison step. To develop intuition for what happens when $k$ is set poorly, it helps to examine the two extremes. The choice involves several considerations.

Too few centroids (e.g., $k = 10$ for 1 million vectors):

When the number of centroids is much too small relative to the dataset size, each cell becomes enormous. Each cell contains approximately:

$$\frac{n}{k} = \frac{1{,}000{,}000}{10} = 100{,}000 \text{ vectors per cell}$$

where:

• $n = 1{,}000{,}000$: the total number of vectors in the dataset
• $k = 10$: the number of centroids (cells)
• $n/k$: the average number of vectors per cell

With such large cells, even a single probe requires scanning 100,000 vectors, which offers minimal speedup over brute force. The cell is too large to narrow the search space enough to help.

Even with $\texttt{nprobe} = 1$ (searching just one cell), you scan:

$$\frac{1}{k} = \frac{1}{10} = 10\% \text{ of the dataset}$$

where:

• $1/k$: the fraction of cells searched when $\texttt{nprobe} = 1$, approximating the fraction of the dataset examined
• $k = 10$: the number of centroids in this example

The centroid comparison step requires only $k = 10$ distance computations, which is cheap. However, the list scanning step dominates since you must compute distances to 100,000 vectors. The problem is clear: the savings from coarse filtering are negligible because the cells are too coarse to filter effectively.

Too many centroids (e.g., $k = 100{,}000$ for 1 million vectors):

At the opposite extreme, when we create far too many centroids, the cells become tiny and the overhead of simply finding the right cells becomes a bottleneck. Each cell contains approximately:

$$\frac{n}{k} = \frac{1{,}000{,}000}{100{,}000} = 10 \text{ vectors per cell}$$

where:

• $n = 1{,}000{,}000$: the total number of vectors
• $k = 100{,}000$: the number of centroids, an excessive number for this dataset
• $n/k = 10$: the average number of vectors per cell, too small for efficient search

With cells this small, the true nearest neighbors are likely scattered across many cells, requiring a large $\texttt{nprobe}$ to reach good recall. The reason is geometric: when cells are very small, even a slight offset between the query and the nearest neighbor can place them in different cells. Additionally, comparing the query to 100,000 centroids itself becomes a bottleneck.

The centroid comparison step itself becomes expensive, and you need a very large $\texttt{nprobe}$ to avoid missing nearby cells that contain true neighbors. The cost of Step 1 (finding nearest centroids) may even exceed the savings from Step 2 (scanning smaller lists) and defeat the purpose of the index entirely.

The right choice of $k$ lies between these extremes, at a point where both the centroid comparison cost and the list scanning cost are manageable. In practice, the guidelines for choosing $k$ are:

• Small datasets ($n < 100{,}000$): $k = 256$ to $1{,}024$
• Medium datasets ($n \approx 10^6$): $k = 1{,}024$ to $4{,}096$
• Large datasets ($n \approx 10^8$ to $10^9$): $k = 16{,}384$ to $65{,}536$

FAISS documentation recommends starting with $k$ between $4\sqrt{n}$ and $16\sqrt{n}$ and tuning from there based on your recall and latency requirements.