IVF Index: Clustering-Based Vector Search & Partitioning › Worked Example

Let's walk through a concrete 2D example to ground the abstract concepts in tangible calculations. Working in two dimensions lets us follow every computation by hand and verify our geometric intuition. Suppose we have 12 vectors and partition them into $k = 3$ clusters.

Training phase: K-means identifies three centroids. These are the points that minimize the within-cluster variance for their respective groups:

• $c_1 = (2, 3)$
• $c_2 = (8, 2)$
• $c_3 = (5, 8)$

Assignment phase: Each vector is assigned to its nearest centroid, creating three inverted lists. Notice how the vectors in each cell are geographically close to their centroid. This is exactly the grouping property that makes IVF effective:

| 1 | $(2, 3)$ | $\{(1,2), (3,4), (2,1), (1,3)\}$ | | 2 | $(8, 2)$ | $\{(7,1), (9,3), (8,1), (7,2)\}$ | | 3 | $(5, 8)$ | $\{(4,7), (6,9), (5,7), (4,9)\}$ |

: Vector assignments to IVF cells after k-means clustering. {#tbl-ivf-assignments}

Each cell contains exactly 4 vectors, giving us perfectly balanced inverted lists. In practice, cells are rarely this uniform; the balance here makes the example easier to follow.

Query phase: A query $\mathbf{q} = (6, 6)$ arrives, and we set $\texttt{nprobe} = 2$.

where $\mathbf{q} = (6, 6)$ is the query vector and $\texttt{nprobe} = 2$ means we will search the 2 cells whose centroids are closest to the query.

The first task is to determine which cells are most promising. We compute distances from the query to all centroids using Euclidean distance. The Euclidean distance between two 2D points $(x_1, y_1)$ and $(x_2, y_2)$ is:

$$\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$$

where:

• $(x_1, y_1)$: the coordinates of the first point
• $(x_2, y_2)$: the coordinates of the second point
• $(x_2-x_1)^2 + (y_2-y_1)^2$: the sum of squared differences in each dimension

Taking the square root of this sum gives us the actual straight-line geometric distance and ensures the distance obeys the triangle inequality.

Applying this formula to each centroid, we can determine which regions of space are closest to our query:

$$\begin{aligned} d(\mathbf{q}, c_1) &= \sqrt{(6-2)^2 + (6-3)^2} && \text{(substitute query and centroid coordinates)} \\ &= \sqrt{16 + 9} && \text{(compute squared differences)} \\ &= 5.0 && \text{(final distance)} \\ \\ d(\mathbf{q}, c_2) &= \sqrt{(6-8)^2 + (6-2)^2} && \text{(substitute coordinates)} \\ &= \sqrt{4 + 16} && \text{(compute squared differences)} \\ &\approx 4.47 && \text{(final distance)} \\ \\ d(\mathbf{q}, c_3) &= \sqrt{(6-5)^2 + (6-8)^2} && \text{(substitute coordinates)} \\ &= \sqrt{1 + 4} && \text{(compute squared differences)} \\ &\approx 2.24 && \text{(final distance)} \end{aligned}$$

where:

• $d(\mathbf{q}, c_i)$: the Euclidean distance between the query vector $\mathbf{q}$ and centroid $c_i$
• $\mathbf{q} = (6, 6)$: the query vector coordinates
• $c_1 = (2, 3)$: the first centroid coordinates
• $c_2 = (8, 2)$: the second centroid coordinates
• $c_3 = (5, 8)$: the third centroid coordinates

Ranking these distances from smallest to largest, centroid $c_3$ is closest at distance 2.24, followed by centroid $c_2$ at distance 4.47, and finally centroid $c_1$ at distance 5.0. The two closest centroids are $c_3$ (distance 2.24) and $c_2$ (distance 4.47). With $\texttt{nprobe} = 2$, we search the inverted lists for cells 3 and 2, scanning 8 of the 12 vectors. We skip cell 1 entirely, saving those 4 distance computations. In this small example, we save only 4 comparisons, but in a real dataset with millions of vectors and hundreds of centroids, this same principle eliminates the large majority of distance computations.

Among the 8 vectors searched, the closest to $\mathbf{q} = (6, 6)$ is $(6, 9)$ at distance 3.0 from cell 3:

$$\sqrt{(6-6)^2 + (6-9)^2} = \sqrt{0 + 9} = 3.0$$

where:

• $(6, 9)$: the vector from the scanned cells that is nearest to the query
• $\sqrt{(6-6)^2 + (6-9)^2}$: the Euclidean distance calculation between query and result vector
• distance 3.0: the final computed distance

The zero contribution from the x-dimension shows the vector is directly above the query, differing only in the y-coordinate.

Note that if the actual nearest neighbor had been in cell 1 (which it isn't in this case), we would have missed it. This is the approximation trade-off. The decision to skip cell 1 was made based solely on centroid distances. While centroids are good summaries of their cells, they are not perfect predictors of which cell contains the nearest neighbor. In this example the approximation worked perfectly, but in general there is always a chance that a skipped cell harbors a closer vector, which is why increasing $\texttt{nprobe}$ improves recall.