Nearest Neighbour

How k-means places the centroids you probe

A cluster index can’t accept a single vector until it has centroids, and the centroids come from k-means. That training step is the one part of the pipeline people treat as a black box — you pass nlist and a sample and wait. It’s worth opening, because the algorithm optimises something that is not your recall, and most of the ways a cluster index disappoints trace back to that gap.

The naive approach

You want nlist representative points so that every vector can be assigned to the nearest one and queries can be routed by comparing against those representatives only.

The obvious method: pick nlist vectors at random from the collection and call them the centroids.

How it fails: random points do not represent a distribution. Sampled uniformly, they land in proportion to density, so dense regions get many centroids that sit almost on top of each other and sparse regions get none. Some cells end up holding almost nothing and some hold a large fraction of the collection. Since probing a cell costs time proportional to its size, and recall depends on the wanted vector being in a probed cell, both halves of the trade-off are damaged: your probe cost becomes unpredictable and dominated by the giant cells, and the vectors in them are the ones you most often fail to reach.

What we want instead is centroids placed so that no vector is far from its centroid. That is a statement we can turn into an objective.

The objective, and what it is not

Define the cost of a set of centroids as the total squared distance from every vector to whichever centroid is nearest it:

cost(C) = Σ over vectors v of  min over c in C of  d(v, c)²

This is the within-cluster sum of squares, and k-means is the algorithm that tries to minimise it. Geometrically: pick positions so the point cloud is covered by nlist small blobs rather than a few large ones.

Now the part that explains most of the family’s behaviour. This objective is a proxy for what you want, and the gap between them is real. The objective cares about the average vector being near its centroid. Search cares about a query’s nearest neighbour being in a cell the query probes. Those come apart in specific ways:

  • The objective is happy with a cell that is compact but sits so close to another cell that the boundary between them cuts through a dense region. That boundary costs recall on every query near it, and the objective cannot see it.
  • Squared distance means outliers dominate. A handful of distant vectors can pull a centroid away from the mass of points it is meant to represent, because moving towards the outlier reduces a large squared term more than it increases many small ones.
  • The objective is defined over the training sample only. Recall is over queries, which are drawn from a different distribution than documents. Nothing in the training step knows about queries at all.

None of this makes k-means the wrong choice — it is cheap, it is well understood, and it produces sensible partitions. But it explains why cluster-index recall is not a quantity you can compute from the training loss, and why the training loss going down does not reliably mean recall goes up.

The algorithm

Lloyd’s algorithm alternates two steps, each of which can only reduce the cost:

kmeans(sample, nlist):
    C ← initialise(sample, nlist)
    repeat:
        # assignment step
        for v in sample: a[v] ← argmin over c in C of d(v, c)
        # update step
        for c in C:      c ← mean of { v : a[v] = c }
    until assignments stop changing

Both steps are simple and both are worth a sentence of intuition.

Assignment freezes the centroids and gives every point to its nearest one. This is optimal given those centroids — it is exactly the Voronoi partition they induce.

Update freezes the assignment and moves each centroid to the mean of its members. This is optimal given that assignment, because the mean is the point minimising total squared distance to a set. That identity is why the objective is squared distance rather than distance: it makes the update step a closed-form average instead of a search. Using plain distance gives a different and arguably better objective whose update step requires an iterative solve, which is why it is not the default.

Alternating two locally optimal steps converges, and it converges to a local minimum. There is no guarantee about the global one, and different starting positions give different, genuinely different, answers.

Initialisation decides the outcome

Because the algorithm only descends, where it starts determines where it stops. This is the most consequential and least visible part of the training step.

Random initialisation has the density problem described above, and it also produces a specific failure mode: two centroids landing in the same tight cluster split it between them and neither is available for a region elsewhere, which then gets absorbed into a distant cell. The iteration cannot repair this, because moving a centroid out of the cluster increases the cost before it decreases it.

The standard remedy is k-means++: choose initial centroids one at a time, each drawn with probability proportional to its squared distance from the nearest already-chosen centroid.

init_pp(sample, nlist):
    C ← { a uniformly random point }
    while |C| < nlist:
        for v in sample: w[v] ← (distance from v to nearest c in C)²
        pick next centroid from sample with probability proportional to w
        add it to C

Read that geometrically: each new centroid is drawn preferentially from wherever the current centroids cover least well. It spreads them out, in proportion to how badly a region is served, while staying random enough to avoid being dragged to outliers deterministically. It costs one pass over the sample per centroid, and it reliably produces better partitions than random starts. It is worth knowing whether your engine uses it, because “we trained the index and recall is poor at a probe fraction that should be plenty” is a symptom with initialisation as a candidate cause.

The sample, and how much of it you need

Training on ten million vectors is wasteful; the centroids are a coarse summary and a sample determines them nearly as well. So implementations train on a subset — and the subset size has a floor set by a counting argument rather than by taste.

Each centroid’s position is the mean of the sample points assigned to it. A mean computed from a handful of points is noise. With nlist cells, a sample of S points gives on average S / nlist points per cell, and if that number is small, you are fitting centroid positions to sampling noise: the partition they induce is arbitrary, and its cell boundaries have no relationship to the real density structure.

This is why guidance for these indexes always pairs a training-sample size with nlist — some multiple of nlist points, with the multiplier in the tens or higher. And it is why asking for a large nlist on a small collection is self-defeating: there isn’t enough data to place that many centroids meaningfully, and the resulting index performs worse than a coarser one would have.

The other requirement is that the sample be representative, and this is the trap that catches real systems. Training on the first S vectors ingested is convenient and usually wrong, because ingestion order correlates with everything: source, date, category, language. Centroids fitted to the first source describe that source’s region of the space, and everything from later sources gets assigned to whichever of those poorly-placed centroids is least inappropriate. Sample randomly across the collection.

Why the partition ages

Two properties of the algorithm combine into the family’s characteristic long-run behaviour.

Centroids are fixed after training. Insertion is “find the nearest centroid, append to its list.” Nothing moves the centroid, and nothing reassigns existing vectors.

The objective was evaluated against a distribution. It was the best available partition for the data that existed at training time.

So as the collection grows and its distribution shifts — new topics, new document types, a new language — the partition drifts out of alignment with the data. Concretely, the effects are: cells become unbalanced, so probe cost varies wildly by query; new regions of the space have no nearby centroid, so their vectors pile into a few cells at large distances; and the effective recall at a fixed probe fraction declines, because the cells no longer group things that belong together.

The symptom is a slow degradation in result quality with nothing in the infrastructure having changed, and the only real remedy is retraining — which means recomputing centroids and reassigning every vector. That the partition has an expiry date is a property of the algorithm, not of any implementation, and it is the main structural cost a graph index doesn’t carry.

What this means for the parameters

  • nlist is bounded below by your data volume, not just by your latency target. Too many cells for the sample you can train on produces noise-fitted centroids.
  • The training sample is a quality parameter, and a cheap one — it costs build time only, like build breadth in a graph index.
  • The partition is a hypothesis about your data’s shape. When the data’s shape changes, the hypothesis is stale, and no query-time parameter compensates for it.
cluster-indextheory