Voronoi cells and the cost of a query near a boundary

A cluster index assigns each vector to its nearest centroid and searches only the cells nearest the query. The shape of those cells is not an implementation detail — it determines exactly which errors the index makes, and the errors are concentrated in a way you can reason about geometrically.

The naive approach

Partition the collection into cells, work out which cell the query is in, scan that cell. If there are four thousand cells over ten million vectors, you compare against four thousand centroids and then about 2,500 vectors, instead of ten million. The saving is enormous and the logic seems airtight: the query is in this cell, so the things near the query are in this cell.

How it fails: that last sentence is false, and it’s worth seeing precisely how false. The cell containing the query contains the points closest to the centroid, not the points closest to the query. Those are different sets, and they differ most for queries that sit far from their centroid — which is to say, near an edge.

What the cells actually look like

Assignment by nearest centroid induces a specific partition with a name. Given a set of centroids, the region of space closer to centroid cᵢ than to any other is cᵢ’s Voronoi cell. Assigning every vector to its nearest centroid is exactly the statement that each vector is stored in the Voronoi cell it falls into.

The geometry follows from one observation: the set of points equidistant from two centroids is the perpendicular bisector of the segment joining them — a plane. A Voronoi cell is therefore the intersection of half-spaces, one per competing centroid: a convex polytope with flat faces, each face shared with a neighbouring cell.

Two properties of this partition matter.

It is a hard partition with no slack. The cells tile space exactly, they don’t overlap, and every point belongs to precisely one. There is no margin, no buffer, no notion of “this vector is nearly in both.” A vector a hair’s breadth from a face is stored on one side only.

Faces are shared, so “which cells are adjacent” is meaningful. A query’s true nearest neighbour, if it isn’t in the query’s own cell, is overwhelmingly likely to be in a cell sharing a face with it. That is what makes probing extra cells effective rather than a lottery: the error has a direction, and the direction is towards the nearest boundary.

Why almost every query is near a boundary

Here is the part that converts a rare-sounding edge case into the normal case.

In a high-dimensional space, a region is nearly all boundary. Shave a thin shell off every face of a cube and you remove essentially all of its volume. A Voronoi cell in 768 dimensions has a great many faces — as many as it has competing neighbours — and the interior, the part genuinely far from every face, is a vanishing fraction of the cell.

So the picture to hold is not “most queries land comfortably inside a cell and a few unlucky ones land near an edge.” It is: a typical query sits close to several faces at once, and the true nearest neighbour has a substantial chance of lying across one of them. The boundary problem in cluster indexes is generic, structural, and predicted by the geometry rather than by the data.

There is a second, compounding effect from how the cells are sized. K-means places centroids where the data is, so cells in dense regions are small and cells in sparse regions are large. A query in a dense region is in a small cell, therefore close to its faces in absolute terms — but the neighbours it wants are also close, so a boundary crossing costs little in distance. A query in a sparse region is in a huge cell, and the vector it wants may be far away in a different huge cell. The failures at each extreme have different characters, and the sparse-region ones are the ones that produce badly wrong results.

What probing more cells buys

The fix is nprobe: scan the nprobe cells whose centroids are nearest the query, not just the nearest one. Since misses are concentrated in face-adjacent cells, and the centroids of face-adjacent cells are the next-nearest centroids, the second cell you probe recovers a large share of the misses, the third rather less, and so on.

That is where the diminishing returns in a cluster index come from, and it’s a geometric statement rather than an empirical one. The cells are ordered by centroid distance; the probability that the true nearest neighbour lies in the n-th such cell falls off with n; the cost of probing it is roughly constant. Constant cost against falling benefit is a curve that flattens, which is the shape you see whenever you sweep this parameter.

Two things follow that are easy to get backwards.

More cells makes each probe cheaper and the boundary problem worse. Doubling nlist halves the average cell size, so a probe scans half as many vectors — but it also roughly doubles the amount of boundary in the partition, and every cell now has more neighbours to lose candidates to. You need a higher nprobe to hold recall steady. The two parameters are coupled: what actually governs recall is closer to the fraction of the collection scanned, nprobe / nlist, than to nprobe alone. A configuration tuned at one nlist does not transfer to another.

Probing everything is worse than not indexing. nprobe = nlist scans every vector, exactly like a flat index, plus the centroid comparisons you paid for on the way. If you find yourself needing a probe fraction near 1 to reach acceptable recall, the index isn’t helping and the honest options are a flat index or a different family.

Overlap: fixing the partition instead of the search

Probing more cells treats the symptom at query time, every query, forever. The alternative is to build a partition without the sharp edge, and it’s a genuinely different design.

Assign each vector to more than one cell. During construction, put a vector in its nearest centroid’s list and in the list of any other centroid that is nearly as close. Now the cells overlap: near a face, both sides hold the vectors from the boundary region.

The effect is to move the cost from query time to build time and storage. A vector stored in two cells takes twice the space for its posting entry, and the collection’s total assignment count grows. In exchange, a single probe now returns candidates that would have needed two, and the boundary misses that overlap covers are recovered without any extra scanning. Since a probe’s cost is dominated by scanning vectors, and the overlap adds exactly the vectors that were being missed, this is usually a better trade than raising nprobe — you scan the relevant boundary vectors rather than an entire extra cell to reach them.

Two variations on the same idea are worth recognising when you meet them:

• Bounded, adaptive replication. Rather than a fixed duplication factor, replicate a vector into additional cells only when the distance ratio to the runner-up centroid is within a threshold. Points deep inside a cell are stored once; points near a face are stored several times. The storage cost is paid only where it buys something. This is the mechanism behind the large disk-resident partitioned designs, where an extra sequential read is cheap but an extra random probe is not.
• Probing by a bound, not by centroid rank. Instead of “the nearest nprobe centroids”, probe every cell whose centroid is within some factor of the nearest one. Queries that land deep inside a cell probe one cell; queries near a face probe several. The work becomes query-adaptive, which is attractive precisely because the difficulty is query-dependent — at the cost of unpredictable latency, giving up the cost predictability that is one of the family’s main advantages.

The trade-off surface, summarised

Change	Recall	Query cost	Memory / build
Raise nprobe	Up, with diminishing returns	Up, roughly linearly	Unchanged
Raise nlist at fixed nprobe	Down — more boundary	Down — smaller cells	More centroids, longer training
Raise nlist at fixed nprobe/nlist	Roughly flat	Roughly flat	More centroids; cheaper first stage per vector scanned
Overlapping assignment	Up near boundaries	Unchanged	More storage, more build work
Adaptive probing by bound	Up where it’s needed	Variable per query	Unchanged

The single sentence to carry: a cluster index’s errors are boundary errors, boundary is nearly everything in high dimensions, and every remedy is a different answer to the question of who pays for the boundary — the query, the storage, or the build. Where those payments land on the overall recall-latency surface is the whole design space of the family.