IVF Index: Clustering-Based Vector Search & Partitioning › Probe Count: The Accuracy-Speed Tradeoff

The $\texttt{nprobe}$ parameter is the primary knob for controlling the tradeoff between search accuracy (recall) and search speed. To build clear intuition for how this parameter works, it helps to consider the two extreme settings and then reason about what happens in between.

When $\texttt{nprobe} = 1$, you search only the single closest cell. This is the fastest setting but also the least accurate because any nearest neighbor that happens to sit in an adjacent cell will be missed. When $\texttt{nprobe} = k$ (all cells), you search every vector in the dataset, which is equivalent to brute-force search with perfect recall but no speed benefit.

where:

• $\texttt{nprobe}$: the number of cells (clusters) searched at query time, ranging from 1 (fastest, least accurate) to $k$ (slowest, perfect accuracy)
• $k$: the total number of centroids (cells) in the IVF index

These extremes illustrate the basic tradeoff: $\texttt{nprobe}$ interpolates between a single-cell approximation and exhaustive search. Every value in between is a different point on the accuracy-speed curve, and using IVF well means finding the right balance for your application.

In practice, you typically want $\texttt{nprobe}$ values that give you high recall (say, 90-99%) while searching only a small fraction of the data. The sweet spot depends on several factors:

• How well the data clusters: If the data forms tight, well-separated clusters, even $\texttt{nprobe} = 1$ can reach high recall. If the data is uniformly distributed with no natural clusters, you need more probes.
• The number of centroids: More centroids means smaller cells, which means more probes are needed for the same recall level. But more centroids also means each cell is smaller, so each probe is cheaper.
• The dimensionality of the vectors: Higher-dimensional spaces exhibit the "curse of dimensionality," where distances become more uniform and cluster boundaries become less real, generally requiring more probes.

A useful mental model is to think of recall as a function of the fraction of data searched. If you have $k = 1000$ centroids and set $\texttt{nprobe} = 10$, you search roughly:

$$\begin{aligned} \frac{\texttt{nprobe}}{k} &= \frac{10}{1000} && \text{(substitute example values)} \\ &= 0.01 && \text{(compute fraction)} \\ &= 1\% \text{ of the data} && \text{(express as percentage)} \end{aligned}$$

where:

• $k = 1000$: the number of centroids in this example
• $\texttt{nprobe} = 10$: the number of cells we choose to search
• $\texttt{nprobe}/k$: the fraction of cells searched, which approximates the fraction of the dataset examined (exact if cells are perfectly balanced)

In practice, this often yields 80-95% recall depending on the dataset, because nearby cells tend to contain the true nearest neighbors. The reason recall is much higher than the fraction of data searched is precisely because IVF's clustering is not random: it groups similar vectors together, so the closest cells to the query are disproportionately likely to contain the nearest neighbors.

Now that we understand the qualitative tradeoff, let us make it precise by analyzing the computational cost step by step. This analysis will reveal exactly where the savings come from and how the different parameters interact. For a dataset of $n$ vectors in $d$ dimensions partitioned into $k$ centroids, a query requires:

Step 1: Find nearest centroids

We compare the query vector to all $k$ centroids. Each comparison computes the distance between two $d$-dimensional vectors. For Euclidean distance, this requires computing $d$ squared differences and summing them plus a square root (which we ignore in big-O notation). Therefore, this step costs:

$$O(k \cdot d)$$

where:

• $k$: the number of centroids in the IVF index
• $d$: the dimensionality of each vector (and each centroid)
• $k \cdot d$: the total number of operations needed to compare the query against all centroids

This cost is fixed regardless of dataset size $n$. Whether you have one million or one billion vectors, comparing against $k$ centroids costs the same. This is one of the elegant properties of IVF: the coarse filtering step is completely independent of the number of data vectors.

Step 2: Scan inverted lists

We scan the vectors in the $\texttt{nprobe}$ selected cells. Assuming roughly equal-sized cells, each cell contains approximately $n/k$ vectors. Thus, we scan $\texttt{nprobe} \cdot n/k$ vectors total. Each distance computation again requires $d$ operations, giving:

$$O\left(\texttt{nprobe} \cdot \frac{n}{k} \cdot d\right)$$

where:

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

This is typically the dominant cost, since $\texttt{nprobe} \cdot n/k$ is usually much larger than $k$. The key observation is that this cost scales linearly with $\texttt{nprobe}$. Doubling the number of probed cells exactly doubles the number of vectors we must examine, which is why query time grows linearly with $\texttt{nprobe}$ as we observed in the experiments.

Total query cost

Combining both steps gives us the complete picture of what a single query costs:

$$O\left(k \cdot d + \frac{\texttt{nprobe} \cdot n \cdot d}{k}\right)$$

where:

• $k \cdot d$: cost of comparing the query to all $k$ centroids (Step 1)
• $\texttt{nprobe} \cdot n \cdot d / k$: cost of scanning vectors in the selected cells (Step 2)
• $k$: the number of centroids
• $\texttt{nprobe}$: the number of cells searched
• $n$: the total number of vectors
• $d$: the dimensionality of each vector

The two terms in this expression correspond to the two phases of the search. In most practical settings, the second term dominates because the number of vectors scanned in the inverted lists far exceeds the number of centroids. However, when $k$ is very large (for instance, at billion scale with tens of thousands of centroids), the first term can become significant and may itself require acceleration, for example by using an HNSW index over the centroids.

Speedup over brute-force

Brute-force search requires $O(n \cdot d)$ operations. The speedup factor compares this to IVF's cost. Since the dimensionality $d$ appears in both numerator and denominator, it cancels out:

$$\begin{aligned} \text{Speedup} &\approx \frac{n \cdot d}{\texttt{nprobe} \cdot n \cdot d / k + k \cdot d} && \text{(brute-force cost divided by IVF cost)} \\ &= \frac{n}{\texttt{nprobe} \cdot n / k + k} && \text{(cancel } d \text{ from numerator and denominator)} \\ && \text{(simplify by factoring)} \\ &= \frac{n \cdot k}{\texttt{nprobe} \cdot n + k^2} && \text{(multiply numerator and denominator by } k\text{)} \end{aligned}$$

where:

• $n$: total number of vectors in the dataset
• $k$: number of centroids (cells) in the IVF index
• $\texttt{nprobe}$: number of cells searched at query time
• $d$: dimensionality of each vector, which cancels out in the speedup ratio

This speedup formula reveals several insights that are worth examining individually. First, as $\texttt{nprobe}$ increases, the speedup decreases because we search more cells. This makes intuitive sense: the more of the dataset we examine, the closer we get to brute-force cost. Second, increasing $k$ (more centroids, finer partitioning) improves speedup. However, there are diminishing returns due to the $k^2$ term in the denominator, which grows faster than the $k$ in the numerator. Third, and perhaps most surprisingly, the dimensionality $d$ cancels out entirely, meaning the speedup is independent of vector dimension. Whether your vectors are 64-dimensional or 1024-dimensional, the fraction of vectors you avoid examining remains the same.

For typical values (say $n = 10^6$, $k = 1000$, $\texttt{nprobe} = 10$), the denominator is dominated by $\texttt{nprobe} \cdot n = 10 \times 10^6 = 10^7$, giving a speedup of about $k / \texttt{nprobe} = 1000/10 = 100\times$. This is a substantial improvement, and it scales well: doubling $n$ doubles the brute-force cost but leaves the IVF speedup ratio in effect unchanged (assuming you scale $k$ accordingly). This scaling property is what makes IVF practical at very large scales: the relative advantage over brute-force search is preserved as the dataset grows.