k-means Reads Your Data 25 Times. Two Would Do.

Four kinds of source. The paper (arXiv 2611.09501, Nov 6, 2026; FAIR at Meta) supplies the headline numbers; the project page supplies the CPU range and the ablation; the faiss source and its 1.16.0 release supply the defaults and the shipping status; one GitHub issue supplies the 19–229 iteration range, and it is community data, not the paper. The 3.1 GB / 77 GB arithmetic and the Figure 2 simulation are ours. We did not rerun the paper's experiments.

The bill you already paid

You are deduplicating a corpus, or building RAG (retrieval-augmented generation: search your own documents, then put the hits in the prompt). Files arrive, get chunked, get embedded. Then a scheduled job clusters the vectors and writes an index; only after that can queries run.

That last step is usually the slowest part of a rebuild, and it still runs the 1957 algorithm: by default, 25 passes over your data. Meta FAIR's e-means matches the same loss in about two, and it ships in faiss.

It speeds up the build, not the query, and it has a size threshold. This essay draws those lines, and ends with three things you can measure tomorrow.

It hides inside the build

k-means is not exotic. It is the layer under all of this:

The common shape: it runs offline, off the query path.

Figure 1 shows the life of an index. The left half is the build; the right half is the query. A query reads the index once. The build sweeps the vectors many times. The latency you feel every day is on the right; the time that actually disappears is on the left.

Some arithmetic. Take 1M vectors, 768 dimensions, fp32, k = 4,096: one pass is about 3.1 GB. Faiss's default 25 passes is roughly 77 GB of reads, before distance arithmetic and index writes. The numbers move with dimension, dtype and nredo (Faiss can rerun clustering and keep the best run), but the order of magnitude does not.

Still Lloyd's 1957 algorithm

Lloyd's loop is two steps: assign each point to its nearest centroid; move each centroid to the mean of its points. Repeat until nothing moves.

It converges, to a local minimum rather than a global one. That guarantee comes from a 1957 Bell Labs memo, formally published in 1982.

The objective:

Faiss's Kmeans defaults to niter = 25, and each iteration is a full assignment pass — one epoch in the usual sense: the data is seen once. This essay uses pass and epoch interchangeably. One more default gets less attention: max_points_per_centroid = 256. When n is much larger than k, Faiss subsamples to at most 256 points per centroid. The 1M-point, 4,096-centroid example sits just inside that threshold (256 × 4,096 ≈ 1.05M), so all of it is scanned.

Each pass costs O(n · k · d) and is memory-bound, random-access. Twenty-five passes are not a metaphor; they are 25 full sweeps of the array.

Why has it survived? Mini-batch versions date back to 1967 (MacQueen), and Sculley's web-scale version has been around since 2010. They read one batch per update, which is much faster, at the cost of a higher error and two knobs you must tune. For most teams, "slow but no decisions" is a reasonable default.

What e-means changed

The paper's algorithm is e-means, from Meta FAIR. The title says it outright: "one-tenth the epochs". The author list includes Matthijs Douze and Hervé Jégou, the authors of faiss; Hugo Touvron is on it too. This is a team arguing against its own default.

It does not invent a new loss. The objective is the MSE above; what changes is how a centroid moves.

One: the statistics become an exponential moving average.

n_j and s_j are the count and sum the current batch contributes to cluster j. α sets how fast to forget: a large α listens to recent batches, a small one averages history. Old assignments are not deleted; they are discounted.

MacQueen's rule is S ← S + s, and it never forgets. Early in training the centroids are bad, so the labels are mostly wrong, and those wrong labels keep a full vote forever, dragging the centroid. e-means gives them a decay factor: slowly forget the early mistakes.

Two: α is not constant. It starts larger and follows a cosine schedule down to a tenth of its initial value. Fast at first, slow at the end.

Three: dead clusters must be revived. Mini-batch updates easily produce centroids with no points assigned. The cluster count says k; the usable count is lower. Every five batches, e-means reassigns clusters below 10% of the mean count by splitting a large donor cluster in two. Faiss already had this trick. The paper's ablation (turn one component off, see what the loss does) is unusually clean:

1M vectors, k = 16,384, 5 epochs, averaged over 5 seeds; SIFT behaves the same way. With revival off, a quarter of the codebook is empty. The other components (initialization, cosine, finalization) move the loss by a fraction of a percent. The four changes are not equal; this is the one that matters.

Four: you do not tune the parameters. Batch size and initial step come from scaling laws fitted on (n, k, T); the reported regret is about 0.07%. There is a trap in "no hyperparameters": it means no new knobs relative to Lloyd. You still pick k and the number of epochs T (5 by default). The two hardest internal parameters are handled by a formula.

A design note: they do not use gradient descent. The project page says large learning rates make gradient updates overshoot. EMA keeps the centroid inside the convex hull of the points ever assigned to that cluster — not the current batch, the history.

Lloyd is a special case of e-means: set the batch to all n and α to 1, and one e-means update equals one Lloyd update. The two are ends of one formula, and the paper finds that end is the worst parameter setting.

One practical detail: at the end of training, the last batch's assignments can be used to recompute an exact mean (last-epoch-mean), lowering the train loss a little more. If what you care about is unseen data, finish with a second, slower EMA. Both cost little, so one run can produce two sets of centroids.

Then the counterintuitive part: noise helps.

Lloyd's loss only decreases, so once it settles into a local minimum it has no reason to leave. A mini-batch sees a slice at a time, so its updates carry noise. The paper's explanation is that this noise pushes centroids out of configurations that look converged but are mispartitioned. Across 200 seeds on toy data, e-means lands in pathological configurations far less often.

Figure 2 is our own small simulation, not the paper's figure: three Gaussian blobs of 40 points each, fixed seed, k = 3, and the same deliberately bad initial centroids. e-means uses batch 12, an initial α of 0.35 with cosine decay, and 2.5 epochs; Lloyd is full-batch.

Lloyd stops moving by pass 8 and is still at MSE 5.39 after 33 passes: two centroids in one blob, one between the other two. e-means reaches 1.28 in 25 updates, one centroid per blob.

This example shows only that, from one initialization, two update rules end up in different places. It is not a guarantee. The paper's claim is probabilistic: not every run escapes.

What the "10×" compares

The comparison is the easiest thing to misread:

It is e-means at 1.4–2.6 epochs against Lloyd at 25 epochs. It is not Lloyd run to convergence. Lloyd would keep improving a little; the gap would narrow.

The last row is not an argument that 25 is too few. It says Lloyd's iteration count varies with the data. The point is not the number 25; it is that every pass is a full sweep. 25 is a default, not a law.

Another trap: epochs are not time. Counting data sweeps alone, 2.5 against 25 is about 10×. The measured wall-clock is 10–45×. My reading is that part of the gap is mini-batches saturating a GPU better; the paper does not break the 10–45× down to that level.

The conservative statement: about 10×. The 45× end is a specific setting, a specific GPU, against a specific reference implementation.

One detail worth separating: the abstract says 10–45× on GPU against Flash-KMeans. The project page reports 8–15× on CPU against Faiss. Different baselines; do not swap or add them.

It shipped: faiss 1.16.0 (Nov 10, 2026) includes faiss.contrib.e_means, and faiss-cpu on PyPI is 1.16.0. Four lines:

from faiss.contrib.e_means import Emeans

em = Emeans(d, k, nepochs=5)
centroids, labels = em.train(x)   # x is a PyTorch tensor (n, d)

What it does not have yet: independent replication. The paper is days old, with reproduction scripts and benchmark data, but only the authors' numbers.

It is also stochastic: different seeds land on different solutions. The reported numbers come from many datasets and settings, not a guarantee that every run finishes in 1.4 epochs.

Will your index get faster?

The headline: it speeds up index construction, not queries. If your problem is "search is slow," this is the wrong essay. That is HNSW (a graph index without clustering), quantization, or a smaller model.

Where it pays:

One prerequisite is easy to miss: the GPU path wants an H100 or H200 and matching CUDA and kernel builds; the CPU path is the one most readers can actually run. The CPU path needs only faiss itself, and the 8–15× number is exactly that path.

The costs: a new API to validate, recall to re-measure after changing initialization. An approximate solution does not guarantee a global optimum (Lloyd does not either). The 10× buys build time, not free quality.

To check it: keep a query set and compare recall@10 — the share of queries whose top 10 contain a true nearest neighbour — against exact (Flat) search. MSE alone will miss retrieval quality.

Three things to do tomorrow

First, measure one rebuild. Record five numbers: n, k, niter, wall-clock, final MSE. Without them, "switch or not" is a guess.

import numpy as np, faiss, time

x = np.ascontiguousarray(x, dtype='float32')
flat = faiss.IndexFlatL2(x.shape[1])   # only to score the final loss

t0 = time.perf_counter()
km = faiss.Kmeans(x.shape[1], k, niter=25)
km.train(x)
secs = time.perf_counter() - t0

flat.add(km.centroids)
D, _ = flat.search(x, 1)
print(f"{secs:.1f}s  MSE={D.mean():.3f}")

Second, lower niter and look. The cheapest experiment: the same data at niter 25, 10 and 5. If 10 is close enough, your default was paying 1.5× the scans for nothing.

for niter in (25, 10, 5):
    km = faiss.Kmeans(x.shape[1], k, niter=niter)
    km.train(x)
    flat.reset()
    flat.add(km.centroids)
    D, _ = flat.search(x, 1)
    print(niter, f"{D.mean():.3f}")

Third, switch only at scale. Use the same data and the same initialization; compare wall-clock, final MSE, and recall@10 if you have an index. The CPU path needs no GPU, so it is the right place to start.

The number 25 is not a physical constant. It is a default. The point is not to replace k-means; it is that 25 can be measured, tuned, or replaced -- and the people proposing to replace it are the authors of faiss.

Further reading

• A running model is not a finished job: the same kind of teardown, applied to "the model works"
• Quantization speed is often a kernel problem: another case where implementation choices decide a 10× gap