Voronoi Cell

A Voronoi cell is a convex polytope—a geometric shape defined by the intersection of half-spaces. Each face of the cell is a perpendicular bisector between the cell's centroid and a neighboring centroid. This convexity guarantees that the straight-line path between any two points inside the cell remains entirely within the cell, a property exploited by search algorithms to ensure deterministic local traversal without escaping the partition.

The primary failure mode in IVF search occurs when a query vector lies near the cell boundary. While the true nearest neighbor is inside the cell, other close neighbors may reside just across the boundary in an adjacent cell. This is why single-probe IVF often misses results. The solution is multi-probe search, which expands the search to adjacent cells whose centroids are nearly as close as the primary centroid, trading a small amount of speed for a significant recall increase.

The distribution of centroids directly dictates cell volume. In dense regions of the vector space, centroids are packed tightly, creating small, high-resolution cells. In sparse regions, cells become large and coarse. This adaptive sizing is a double-edged sword:

• Benefit: Natural compression of empty space.
• Risk: Large cells contain many vectors, causing unbalanced search times if a query lands there. Techniques like hierarchical k-means mitigate this by subdividing oversized cells.

Once a query is assigned to a Voronoi cell, the coarse centroid is subtracted to compute a residual vector. This residual represents the fine-grained local offset within the cell. Because residuals have a much smaller magnitude and variance than the original vectors, they can be compressed more aggressively using Product Quantization (PQ) with lower reconstruction error. This two-level encoding—coarse centroid ID plus compressed residual—is the core of the IVFPQ index.

The partition itself is created by k-means clustering during index training. The algorithm iteratively refines centroid positions to minimize the sum of squared distances within each cell. The resulting Voronoi tessellation is optimal with respect to the L2 distance metric. For other metrics like cosine similarity, the partition boundaries shift, and the cells are no longer strict Voronoi partitions in the Euclidean sense, requiring spherical clustering or normalized vectors to maintain geometric validity.

In high-dimensional spaces, the curse of dimensionality distorts Voronoi geometry. Cells can appear empty if no database vectors fall within their boundaries, wasting index capacity. Conversely, the concept of 'overlap' is an illusion—true Voronoi cells are a strict partition with no overlap. However, the soft assignment used in multi-probe search creates an effective overlap by assigning a query to multiple cells probabilistically, simulating a fuzzy boundary to recover neighbors lost to hard partitioning.