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.3\%$ 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.3\%$ 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 is the first index here that gives up exactness for speed, and it does so with a single coarse partition. The next index structures keep the goal — touch few vectors, miss few neighbors — but replace the flat partition with a navigable graph, where search is a walk rather than a cell lookup. That is where the small-world topics go.

Voronoi Partitioning and the Inverted-File Index

Overview & motivation

Movement 1 — the partition

Movement 2 — the residual (IVFADC)

Honest accounting

Connections

References & Further Reading