Voronoi Partitioning and the Inverted-File Index

Overview & motivation

The quantization track — Lloyd’s codebook, its product factorization, and the rotation that optimizes it — made a single distance cheap to estimate. None of it made search non-exhaustive: every method still compares the query against all $n$ database codes. The inverted-file index is the other half. A coarse quantizer partitions the space into $n_{\text{list}}$ Voronoi cells, files each vector under its nearest centroid, and lets a query touch only the vectors in the few cells nearest to it. The art is entirely in the trade — how few cells can you probe before you start missing neighbors?

The index has two movements. The first is the partition: build the cells, define the inverted lists, and quantify the candidate-set reduction and the recall it costs. The second is the residual: having spent a coarse centroid on each vector, product-quantize what the centroid leaves behind, which is cheaper to encode than the vector itself. The laboratory below lets you drag the number of probed cells and watch a true neighbor get found or missed, trace the recall-versus-scan frontier, and see the residual’s variance collapse.

nprobe = 1

cells probed

1 of 6

candidates scanned

9 of 60

true neighbor

missed ✗

The query (◆) is compared only against the points in its 1 nearest cell. Its true nearest neighbor (ringed) lives in the query's 3rd-nearest cell, so it is missed at this nprobe — the boundary effect. Raise nprobe to 3 and the ring turns green.

The first panel is the partition and its honest catch: the query’s true nearest neighbor sits in its third-nearest cell, so it is missed until you probe three. The second panel is the payoff — recall against the fraction of the database scanned. The third is IVFADC: the coarse quantizer removes most of the variance, so the residual product quantizer reaches higher recall at the same bit budget.

Movement 1 — the partition

Let $X = \{x_1, \dots, x_n\} \subset \mathbb{R}^d$ be the database. Train a coarse quantizer of $n_{\text{list}}$ centroids $\{\mu_1, \dots, \mu_{n_{\text{list}}}\}$ by Lloyd’s k-means on $X$ . Each centroid owns a Voronoi cell and an inverted list of the vectors assigned to it.

Definition 1 (Coarse quantizer and inverted lists).

The coarse quantizer assigns $x$ to its nearest centroid, $i(x) = \arg\min_j \lVert x - \mu_j \rVert$ , partitioning $\mathbb{R}^d$ into the Voronoi cells $V_j = \{z : i(z) = j\}$ . The inverted list $L_j = \{\,i : i(x_i) = j\,\}$ holds the indices of the database vectors in cell $j$ . To search, the query $q$ probes its $n_{\text{probe}}$ nearest centroids and ranks only the vectors in those cells:

\mathrm{cand}(q) \;=\; \bigcup_{j \in \mathcal{N}_{n_{\text{probe}}}(q)} L_j, \qquad \mathcal{N}_{n_{\text{probe}}}(q) = \text{the } n_{\text{probe}} \text{ centroids nearest } q .

Theorem 1 (Candidate-set reduction).

Probing $n_{\text{probe}}$ cells scans exactly the total occupancy $\sum_{j \in \mathcal{N}_{n_{\text{probe}}}(q)} |L_j|$ of those cells. If the cells are balanced, $|L_j| \approx n / n_{\text{list}}$ , the expected scan is

\mathbb{E}\,|\mathrm{cand}(q)| \;\approx\; \frac{n_{\text{probe}}}{n_{\text{list}}}\, n,

so with $n_{\text{list}} \approx \sqrt{n}$ and small $n_{\text{probe}}$ the index scans on the order of $\sqrt{n}$ vectors per query, against $n$ for the exhaustive scan. Probing all $n_{\text{list}}$ cells recovers the exhaustive scan, hence exact search.

The reduction is real — on the finance cloud with $n_{\text{list}} = 32$ , a single probe scans under $4\%$ of the database — but the $\sqrt{n}$ figure rides on the balanced-cell assumption, which a k-means partition of real data only approximates. That is the first honest caveat; the second is sharper.

Theorem 2 (The boundary effect).

The vectors a query actually ranks are those in its probed cells, so the recall at $n_{\text{probe}}$ is the probability that a true neighbor lies in one of the query’s $n_{\text{probe}}$ nearest cells. At $n_{\text{probe}} = 1$ this is the probability that the neighbor shares the query’s single nearest centroid — strictly below $1$ , because a query near a Voronoi boundary has neighbors on the far side, in a cell whose centroid is not the query’s nearest. Recall is non-decreasing in $n_{\text{probe}}$ and reaches $1$ at $n_{\text{probe}} = n_{\text{list}}$ .

Proof.

A vector $x_i$ can be returned for query $q$ only if $i \in \mathrm{cand}(q)$ , i.e. $i(x_i) \in \mathcal{N}_{n_{\text{probe}}}(q)$ . So recall $@k$ equals the fraction of true top- $k$ neighbors whose cell is among the query’s $n_{\text{probe}}$ nearest. Adding a cell to the probe set only enlarges $\mathrm{cand}(q)$ , so recall cannot decrease in $n_{\text{probe}}$ ; at $n_{\text{probe}} = n_{\text{list}}$ the candidate set is all of $X$ and the exact distance recovers every neighbor. At $n_{\text{probe}} = 1$ , any neighbor $x_i$ with $i(x_i) \ne i(q)$ — a neighbor across the Voronoi boundary separating its cell from the query’s — is missed, and such neighbors exist whenever $q$ is closer to a boundary than to its nearest in-cell neighbor, which has positive probability. $\blacksquare$

∎

On the finance cloud the frontier is steep in the index’s favor: recall@10 climbs from $47.5\%$ at a single probe to $98\%$ at eight probes, while the scanned fraction grows from under $4\%$ to about a quarter. The boundary effect is the price of the partition, and multi-probe is how you pay it down.

Movement 2 — the residual (IVFADC)

The coarse quantizer leaves a residual $r = x - \mu_{i(x)}$ : what the cell centroid fails to capture. Instead of throwing it away, encode it with product quantization. The reason this helps is a variance identity, and it is exact.

Theorem 3 (Residual variance reduction).

Let $C = i(X)$ be the cell assignment, a random variable over the database. Because the Lloyd centroid is the sample mean of its cell at convergence, $\mu_{i(x)} = \mathbb{E}[x \mid C]$ , the residual is the within-cell deviation $r = x - \mathbb{E}[x \mid C]$ . By the law of total variance,

\operatorname{Var}(x) \;=\; \underbrace{\mathbb{E}\big[\operatorname{Var}(x \mid C)\big]}_{\text{within-cell} \,=\, \operatorname{Var}(r)} \;+\; \underbrace{\operatorname{Var}\big(\mathbb{E}[x \mid C]\big)}_{\text{between-cell} \,\ge\, 0},

so $\operatorname{Var}(r) = \operatorname{Var}(x) - \operatorname{Var}(\mu_{i(x)}) \le \operatorname{Var}(x)$ , with strict inequality whenever the cells have distinct means. The coarse quantizer has absorbed the between-cell variance; product quantization then spends its bits on the smaller within-cell signal.

This is the whole of IVFADC. Build the inverted file, compute each vector’s residual against its own cell centroid, and product-quantize the residuals; at search time, for each probed cell $j$ , the query’s residual $q - \mu_j$ is matched against the stored residual codes by the asymmetric lookup of the previous topic. Because the residual carries less variance — on the finance cloud the coarse quantizer removes $74\%$ of it — the same product-quantization budget reconstructs it more faithfully, and recall rises.

Proposition 1 (IVFADC versus flat product quantization at equal bits).

At a fixed product-quantization budget of $m \log_2 k^\*$ bits, encoding the residual (IVFADC) attains reconstruction distortion at most that of encoding the raw vector (flat product quantization), because the residual has no greater variance in any subspace and product-quantization distortion is monotone in subspace variance. The lower distortion translates into higher retrieval recall.

On the finance cloud at $64$ -bit codes, flat product quantization reaches $75.25\%$ recall@10 and IVFADC reaches $77.1\%$ — the same bits, a smaller signal, more recall. The gain is a measured direction, not a universal constant; its size depends on the cloud, the cell count, and the budget.

§ Finance case study text

A production financial-retrieval index does not scan its corpus. The inverted file is what makes a query against millions of multimodal embeddings touch only the few thousand vectors in the nearest cells, and IVFADC — the IndexIVFPQ of Faiss — is the standard realization: a coarse k-means quantizer over the corpus, inverted lists of product-quantized residuals, and an nprobe knob that trades latency for recall. On the synthetic finance cloud the two halves compose exactly as the production index does: probing eight of thirty-two cells scans under a third of the database for $98\%$ recall, and residual encoding lifts the $64$ -bit recall from $75.25\%$ to $77.1\%$ . The boundary effect is the operational reality — raise nprobe when recall matters, lower it when latency does — and the cell imbalance is why a real deployment monitors list-length skew rather than assuming the clean $\sqrt{n}$ arithmetic.

Honest accounting

⚠ Rigor flag

The inverted file trades recall for speed, and the trade is governed by assumptions worth naming. The $\sqrt{n}$ speedup assumes balanced cells; a k-means partition of real data is imbalanced, so inverted-list lengths and query times vary and a query can land in an overfull cell. The index is approximate by construction — probing $n_{\text{probe}}$ cells misses any neighbor across a boundary in an unprobed cell (the boundary effect), so recall at $n_{\text{probe}} = 1$ is strictly below $1$ and recovers only with multi-probe; in high dimensions a cell has more neighbors and the effect worsens, so $n_{\text{probe}}$ must grow with dimension to hold recall. The residual-variance reduction is exact (the Lloyd centroid is the cell mean, so the law of total variance applies with no approximation), but the recall gain it produces is a measured direction on the synthetic finance cloud, not a guaranteed margin. Choosing $n_{\text{list}}$ and $n_{\text{probe}}$ is an empirical tuning problem; the $\sqrt{n}$ rule for $n_{\text{list}}$ is a starting point, not an optimum. Every recall, fraction-scanned, and variance figure is measured on the same synthetic cloud the previous quantization topics used.

The inverted file gives up exactness for speed with a single coarse partition. The navigable small-world graph of the previous topic pursued the same goal — touch few vectors, miss few neighbors — with a graph, where search is a walk rather than a cell lookup. The next topic layers that graph into a hierarchy and runs the two families head to head on one cloud.

Voronoi Partitioning and the Inverted-File Index

Overview & motivation

Movement 1 — the partition

Movement 2 — the residual (IVFADC)

Honest accounting

Connections

References & Further Reading