IVF Index: Clustering-Based Vector Search & Partitioning › The Clustering Approach

IVF works in two phases: an offline indexing phase that partitions the vector space, and an online query phase that searches only the relevant partitions. The advantage of this two-phase design is that the expensive work of organizing the data happens once during indexing so that every subsequent query can exploit that precomputed structure to avoid scanning the full dataset. Let us examine each phase in detail, starting with how the index is built.

The indexing phase uses k-means clustering to divide the vector space into $k$ distinct regions, called Voronoi cells. Each cell is defined by its centroid, a representative point at the center of the cluster. The process proceeds through three steps: first we discover where the natural groupings in the data lie, then we assign every vector to its closest grouping, and finally we build the data structure that makes retrieval efficient. Here is how the process works:

1. Train centroids: We begin by discovering natural groupings in the data. The basic question at this stage is: if we had to summarize the entire dataset using only $k$ representative points, where should those points be placed so that every vector in the collection is as close as possible to at least one of them? K-means clustering answers precisely this question. It identifies $k$ centroids $\{c_1, c_2, \ldots, c_k\}$ that serve as representative points for different regions of the vector space.

K-means clustering finds $k$ representative points (centroids) by grouping vectors so that vectors within each group are as close as possible to their group's center. This minimizes the total "within-cluster" distance across all groups. The algorithm accomplishes this iteratively: it starts with an initial guess for where the centroids should be, then repeatedly refines those positions by reassigning vectors and recalculating centers until the arrangement stabilizes.

Formally, k-means seeks to minimize the objective function:

$$\sum_{i=1}^{k} \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - c_i\|^2$$

where:

• $k$: the number of clusters (centroids) we want to create, controlling how finely we partition the space
• $c_i$: the $i$-th centroid, a $d$-dimensional vector representing the center of cluster $i$
• $C_i$: the set of all vectors assigned to cluster $i$
• $\mathbf{x}$: a vector in the dataset
• $\|\mathbf{x} - c_i\|^2$: the squared Euclidean distance between vector $\mathbf{x}$ and centroid $c_i$, measuring how far the vector is from its assigned centroid
• $d$: the dimensionality of each vector in the dataset

This objective function captures the total within-cluster variance, which is a single number summarizing how well the centroids stand for their assigned vectors. A lower value means tighter, more compact clusters where vectors are close to their centroids, exactly the property we want for IVF to work well. The inner sum $\sum_{\mathbf{x} \in C_i}$ accumulates distances for all vectors in cluster $i$, measuring the spread of that individual cluster. The outer sum $\sum_{i=1}^{k}$ then combines these individual cluster costs across all $k$ clusters, yielding the total cost of the entire partitioning.

Why does the objective use squared distance rather than plain distance? The squared distance grows quadratically with separation, so vectors far from their centroid contribute disproportionately to the objective. This property encourages the algorithm to prioritize reducing large errors, naturally resulting in tight, compact clusters. A single outlier vector that is very far from its centroid will dominate the sum, pushing the algorithm to adjust the centroid positions to bring such outliers closer. The algorithm alternates between two steps: (1) assigning each vector to its nearest centroid, and (2) recomputing each centroid as the mean of all vectors assigned to it. This process repeats until the assignments stabilize (convergence). Each iteration is guaranteed to decrease (or at least not increase) the objective, which ensures that the algorithm converges, though it may settle on a local minimum rather than the global optimum.

1. Assign vectors: Once centroids are established, we move to the partitioning step, where the goal is to divide the entire dataset into non-overlapping groups. Each vector $\mathbf{x}$ is assigned to its nearest centroid, meaning the centroid to which it has the smallest Euclidean distance. This assignment is deterministic: given a fixed set of centroids, every vector maps to exactly one cluster. Formally, we assign each vector to cluster $C_i$ where:

$$i = \arg\min_{j=1,\ldots,k} \|\mathbf{x} - c_j\|$$

where:

• $\mathbf{x}$: a vector in the dataset that we're assigning to a cluster based on minimum distance to centroids
• $i$: the index of the cluster (centroid) to which $\mathbf{x}$ is assigned
• $\arg\min$: the operator that returns the index $j$ that minimizes the expression
• $k$: the total number of centroids
• $c_j$: the $j$-th centroid
• $\|\mathbf{x} - c_j\|$: the Euclidean distance between vector $\mathbf{x}$ and centroid $c_j$

The $\arg\min$ operator finds which centroid index yields the smallest distance, making this a hard assignment: each vector belongs to exactly one cluster. This is a necessary property for the IVF data structure because it means every vector appears in exactly one inverted list, avoiding duplication and keeping the index size manageable.

This assignment process creates Voronoi cells where all vectors in a cell share the same nearest centroid. Geometrically, you can think of each centroid as claiming the region of space that is closer to it than to any other centroid, and every vector falling within that region is added to that centroid's list.

1. Build inverted lists: The final step of index construction is to create the data structure that makes search efficient. We build an "inverted file" where each centroid points to the list of all vectors assigned to its cell. This is the structure that query processing will use: given a centroid, we can immediately look up every vector that belongs to its cell without scanning the entire dataset.

The term "inverted file" comes from the same concept behind inverted indexes in information retrieval, which we encountered in Part II when discussing TF-IDF. In a text inverted index, each term points to its list of documents; here, each centroid points to its list of vectors. The analogy is precise: just as a text search engine uses a term to quickly locate all documents containing that term, an IVF index uses a centroid to quickly locate all vectors belonging to that region of space.

With the index structure in place, the question naturally arises: how many centroids should we use? The number of centroids $k$ is a necessary hyperparameter that balances cell granularity against centroid comparison cost. Too few centroids means each cell is large and expensive to scan; too many centroids means the coarse comparison step itself becomes a bottleneck. A common rule of thumb is to set:

$$k \approx \sqrt{n}$$

where:

• $k$: the number of centroids (clusters) in the IVF index
• $n$: the total number of vectors in the dataset
• $\sqrt{n}$: the square root of $n$, serving as a baseline for centroid count

This square root relationship balances two competing costs: the cost of comparing the query to all $k$ centroids (grows with $k$), and the cost of scanning vectors within cells (decreases as $k$ increases because each cell becomes smaller). The square root gives a reasonable middle ground. To see why, consider that the total work is proportional to $k + n/k$. Minimizing this expression with respect to $k$ (taking the derivative and setting it to zero) yields $k = \sqrt{n}$, which is exactly the balancing point where the two costs are equal.

In practice, values between $4\sqrt{n}$ and $16\sqrt{n}$ are commonly used.

The square root relationship emerges from balancing two costs: too few centroids means large cells (expensive to scan), while too many centroids means expensive centroid comparison. For a collection of 1 million vectors, this means roughly 1,000 to 4,000 centroids. Each centroid's inverted list then contains on average $n/k$ vectors. This average list size is an important quantity because it determines how much work each probe requires during the query phase.

The way k-means is initialized has a significant effect on the quality of the final centroids, and therefore on IVF recall. The algorithm is not guaranteed to find the global minimum of the objective function. It converges to a local minimum that depends on the starting positions of the centroids. A bad initialization can produce poorly separated clusters, uneven cell sizes, and degraded search quality.

The naive approach, called random initialization, picks $k$ vectors from the dataset uniformly at random as starting centroids. This is simple but fragile: two initial centroids may be placed very close together, causing them to compete for the same region of space and leaving other regions underrepresented. The resulting clustering is uneven, and the IVF index will have some very large cells (slow to probe) and some very small cells (wasted capacity).

K-Means++ initialization addresses this problem by placing the initial centroids far apart from each other. The algorithm works as follows. The first centroid is chosen uniformly at random from the dataset. Each subsequent centroid is chosen with probability proportional to the squared distance from the nearest already-chosen centroid. Formally, each data point $\mathbf{x}$ is selected as the next centroid with probability:

$$P(\mathbf{x}) = \frac{D(\mathbf{x})^2}{\sum_{\mathbf{y} \in \text{data}} D(\mathbf{y})^2}$$

where:

• $D(\mathbf{x})$: the distance from point $\mathbf{x}$ to its nearest already-selected centroid
• $D(\mathbf{x})^2$: the squared distance, which amplifies the preference for points far from existing centroids
• The denominator normalizes the probabilities so they sum to 1 across all data points

This sampling rule ensures that the initial centroids spread out across the space. Points that are far from all current centroids have the highest probability of being selected next, naturally placing the initial seeds in different regions. The theoretical guarantee is that K-means++ reaches an expected objective value within $O(\log k)$ of the global optimum, a substantial improvement over random initialization.

In practice, K-means++ produces noticeably more balanced cell sizes, which translates directly to more predictable query latency. FAISS uses its own optimized k-means variant with K-means++ style initialization by default. When using scikit-learn's KMeans, the init='k-means++' parameter (the default) lets this initialization.

Training data requirements are another practical consideration. K-means clustering requires a representative sample of the data to produce good centroids. If you train on too few vectors, the centroids will not capture the full distribution of the embedding space, and the cells will not reflect the actual data structure. As a rule of thumb, FAISS recommends training on at least $39 \times k$ vectors (about 39 vectors per centroid). For a dataset with $k = 4{,}096$ centroids, this means training on at least roughly 160,000 vectors.

For very large datasets where running k-means on the full dataset would be prohibitively slow, it is common practice to subsample the training data. Since k-means is looking for structural patterns in the vector space rather than memorizing individual points, a representative subsample of 1-10 million vectors is sufficient even for billion-scale collections. The key is that the subsample must cover the full range of topics or domains present in the dataset; a non-representative sample produces centroids biased toward the overrepresented regions.

With the index built and all vectors neatly organized into their respective inverted lists, we can now examine how search works. The key idea is to exploit the structure we built during indexing: instead of comparing the query against every vector in the dataset, we first identify which regions of space are most promising, and then restrict our search to only those regions. This turns an exhaustive scan into a targeted one. When a query vector $\mathbf{q}$ arrives, IVF performs these steps:

1. Find nearest centroids: The first step is coarse filtering, where we identify which regions of space are worth examining in detail. We compute the distance from $\mathbf{q}$ to all $k$ centroids which is the $\texttt{nprobe}$ closest ones. This step is fast because $k \ll n$; we only need to perform $k$ distance computations rather than $n$.

The intuition behind this step is straightforward. If a vector is close to the query, its centroid is likely also close to the query. Centroids stand for the center of mass of their respective clusters, so the nearest centroid to the query is a strong indicator of where the nearest vectors reside. By comparing only to centroids first, we quickly narrow down which regions of space are worth examining in detail. Formally, we compute the distance from the query to each centroid:

$$d(\mathbf{q}, c_i) = \|\mathbf{q} - c_i\|$$

where:

• $\mathbf{q}$: the query vector for which we're searching for nearest neighbors
• $c_i$: the $i$-th centroid
• $d(\mathbf{q}, c_i)$: the distance between the query and centroid $c_i$
• $k$: the total number of centroids (clusters) in the IVF index
• $\texttt{nprobe}$: the number of closest centroids whose cells we will search

We then select the $\texttt{nprobe}$ centroids with the smallest distances, controlling the accuracy-speed tradeoff. The selected centroids define a search neighborhood around the query. We trust that these closest regions of space contain most, if not all, of the true nearest neighbors.

1. Search inverted lists: Having identified the most promising cells, we now scan all vectors in the inverted lists of those $\texttt{nprobe}$ centroids. This is an exhaustive comparison within the selected cells, where every vector in the chosen lists is compared against the query. The important efficiency gain is that we examine only a small subset of the total dataset rather than the entire collection.

2. Return top results: From all scanned vectors, return the top-$k$ nearest neighbors based on their distances to the query. This is the fine-grained ranking step, where we take the candidate pool gathered from the selected cells and identify which candidates are truly closest to the query. We compute the distance from the query to each candidate vector:

$$d(\mathbf{q}, \mathbf{x}_j) = \|\mathbf{q} - \mathbf{x}_j\|$$

where:

• $\mathbf{q}$: the query vector
• $\mathbf{x}_j$: the $j$-th candidate vector from the scanned cells
• $d(\mathbf{q}, \mathbf{x}_j)$: the distance between the query and candidate vector $\mathbf{x}_j$
• $k$: the number of nearest neighbors to return (note: this reuses the symbol $k$ but refers to result count, not centroid count)

This step performs the final ranking among the candidates that survived the coarse filtering stage, selecting the truly closest vectors from the subset we examined.

We then sort all candidates by distance and select the $k$ vectors with the smallest distances as our final results. This two-stage approach, coarse filtering followed by fine-grained ranking, is what gives IVF its efficiency: the expensive exact distance computations are restricted to a small, carefully chosen subset of vectors.

Let us now quantify the cost of each step to understand where the computational savings come from. The first step requires only $k$ distance computations (comparing the query to each centroid), which is fast since the number of centroids $k$ is much smaller than the number of vectors $n$ (written as $k \ll n$). For a dataset of one million vectors with one thousand centroids, this coarse step examines just 0.1% of the data.

The second step searches approximately $\texttt{nprobe} \times n/k$ vectors. Each cell contains on average $n/k$ vectors (assuming balanced clustering), so searching $\texttt{nprobe}$ cells means examining:

$$\text{Vectors scanned} = \texttt{nprobe} \times \frac{n}{k}$$

where:

• $\texttt{nprobe}$: the number of cells we search
• $n$: the total number of vectors in the dataset
• $k$: the number of centroids (clusters)
• $n/k$: the average number of vectors per cell, assuming balanced clustering

This is typically a small fraction of the total dataset because $\texttt{nprobe} \ll k$ in practice. To express this more concretely, the fraction of the total dataset that we examine is simply:

$$\frac{\texttt{nprobe}}{k}$$

where:

• $\texttt{nprobe}$: the number of cells searched
• $k$: the total number of centroids (cells) in the IVF index

This fraction directly controls the speedup versus brute-force search: smaller fractions mean faster queries but potentially lower recall. The relationship is intuitive: if we search half the cells, we examine roughly half the data and get roughly half the speedup.

For example, with 100 centroids and nprobe=10, we examine only about 10% of the data.

This gives us an approximate search because the true nearest neighbor might reside in a cell whose centroid was not among the $\texttt{nprobe}$ closest to the query. Vectors near the boundaries between cells are the most vulnerable to being missed, because their centroid may not be the closest centroid to the query even though the vectors themselves are very close. Increasing $\texttt{nprobe}$ reduces this risk at the cost of searching more vectors. This boundary effect is the basic source of approximation error in IVF, and understanding it is needed for choosing good parameter values.

To understand the boundary problem precisely, consider what happens geometrically. Each Voronoi cell covers a convex region of space, and any vector that falls within that region is assigned to it. When a query vector $\mathbf{q}$ arrives, we probe the cells whose centroids are nearest. But the centroid of a cell is the average position of all vectors in it, not necessarily the edge of the cell. A vector sitting near the border between two cells might be geometrically very close to $\mathbf{q}$, but it belongs to the cell on the far side of the boundary, whose centroid may be considerably farther from $\mathbf{q}$ than the centroid of the cell $\mathbf{q}$ itself falls into.

In low dimensions, boundary effects are limited because the geometry is simple: most vectors are far from any cell boundary. In high dimensions, the situation reverses. A well-known result from measure theory is that in high-dimensional hypercubes, almost all volume concentrates near the surface rather than the interior. Translated to IVF: in high-dimensional spaces, a large fraction of vectors sit close to the boundary between cells rather than comfortably in the interior. This means that for any given query, there is a substantial probability that the true nearest neighbor is in an adjacent cell rather than the same cell. The practical consequence is that high-dimensional data requires larger $\texttt{nprobe}$ values to reach the same recall as low-dimensional data.

There are two practical mitigations. The first is to simply increase $\texttt{nprobe}$, accepting higher latency in exchange for better recall. The second is to increase $k$, using more centroids to create finer-grained cells. Smaller cells mean that boundary vectors are still close to their centroid, so the centroid comparison step is a more reliable indicator of where the nearest neighbors are. The cost is that more centroids means a more expensive centroid comparison step and longer training time. In practice, for high-dimensional data (768 dimensions or more), it is common to use values of $k$ closer to the $16\sqrt{n}$ end of the recommended range, paired with $\texttt{nprobe}$ values of 20 to 100.