e-means Is 10x Faster. The Comments Are Better Than the Paper

A first-year PhD student at Meta FAIR shipped a drop-in replacement for k-means into FAISS, then spent two days answering every person who called it overhyped. That is the part of this story i keep coming back to.

The algorithm is called e-means. It hit Hacker News at 495 points and 78 comments. The paper claims it reaches the loss that Lloyd's k-means needs 25 epochs for in 1.4 to 2.6 epochs.

Faster on GPU by 10x to 45x against Flash-KMeans. Faster on CPU by 8x to 15x against the old FAISS implementation. And you tune nothing except k.

I have a clustering job in a side project that takes about forty minutes on a rented GPU. Forty minutes where i stare at a terminal and pretend to do other work. So yes, i clicked.

But the comments were better than the paper. Half the thread was praise. The other half was people who clearly run this stuff in production, poking holes.

And the author was down there in the replies, taking every punch.

That mix is the actual story. Not the speedup. The argument about whether the speedup means anything.

What the update rule actually changes

Every k-means variant stores two numbers per cluster: a sum S and a count N. The centroid is just S / N. All the variants differ in how they change those two numbers.

Lloyd throws them away each pass and rebuilds from the whole dataset. MacQueen's rule from 1967 keeps adding to them forever, so stale points never leave. e-means multiplies the old value by (1 - alpha) and adds the new batch scaled by alpha.

S = (1 - alpha) * S + alpha * s
N = (1 - alpha) * N + alpha * n

That is it. That is the algorithm. An exponential moving average on the statistics instead of a full recompute.

I used to think mini-batch k-means was the fast, sloppy option and full-batch was the careful one. Then i read the local minima section and had to sit with it for a minute.

The sloppiness was the point. Noisy updates wander out of bad starting positions. Lloyd's loss only goes down, so it gets comfortable in whatever ditch it lands in first.

The toy examples in the blog post are brutal about this. Five blobs in a line, k=5. Lloyd leaves a whole blob with no centroid and gives an end blob two.

Across 200 random starts it stayed stuck 46% of the time. e-means, same starts, stuck 0% of the time.

Lloyd doesn't find the optimum. It finds a local minimum and stops.

That one line reframed the whole thing for me. Everything i had read about k-means treated it as a solved problem with a quality ceiling. It has a quality ceiling, and nobody was measuring how low it sits.

The hyperparameter thing is the real flex

Here's a question people always ask about mini-batch methods: how do you pick the batch size?

The honest answer used to be "sweep it and pray." Batch too small and the gradients are noise. Batch too big and you waste a pass. Most teams pick 1024 because a tutorial said 1024.

e-means fits two equations to set batch size and starting step from n, k, and T. The paper reports median regret of 0.07% on datasets held out from the fit, and one left-out problem size predicted at 0.07% and 0.06%. Then alpha decays on a cosine schedule from its starting value down to a tenth of it.

So the honest pitch is not "faster." It's "same API surface as the thing you already use."

And that is why it landed in faiss.contrib.e_means with a two-line call instead of a research repo with a broken README.

Dead clusters are the boring problem nobody blogs about

The problem isn't what you think. The hard part of large-codebook clustering isn't speed. It's clusters that die.

A centroid drifts away from every point, gets nothing assigned in the next batch, and becomes a permanent zombie. Your codebook says 16,384 entries. Reality says 12,000, and the rest are decorative.

On the DEEP dataset at k=16,384, the paper measured 26.3% dead clusters with revival turned off. Random resampling from the batch, the trick EnCodec uses, got that to 14.3%. Splitting a large cluster in two, borrowed from FAISS itself, got it to 0.3%.

Forty-seven dead clusters instead of 4,313. Same data, same epochs.

That detail matters more to me than the wall-clock numbers. Dead clusters silently wreck the recall of any IVF index built on top of them, and you find out months later when a search returns something obviously wrong.

A short detour about naming

"e-means" is a bad name and i mean that with affection.

It sounds like email. Or e-commerce. Or one of those 1999 startups that raised 40 million to sell pet food online.

The e stands for exponential moving average, which is a fine thing to name a variable after. It is a strange thing to name a decade of work after.

Compare it to the competition. Lloyd's algorithm is named after a person. So is MacQueen's rule, Elkan's algorithm, Hartigan-Wong, Sculley.

Entire careers reduced to a possessive.

Then along comes a letter. It's like naming your kid "Q."

And yet it's growing on me. It's short, it types fast, and it makes the pip install obvious.

Maybe the era of naming algorithms after people is ending. Everything now ships with a landing page and a playground, so the name has to work as a domain.

e-means.github.io is a nicer URL than bessa-2026-emeans.github.io. So the letter wins.

Where this does not help you

Most people don't need this.

If your dataset is under a few hundred thousand points, Lloyd in scikit-learn finishes before you can alt-tab. The speedup is real and it is also irrelevant to you. Don't migrate anything.

If your k is small, like ten or twenty, the mini-batch machinery buys you very little. One commenter in the thread tried e-means for relaxing a mesh on a sphere and found it slower and noisier than Lloyd, because there was no dataset to sample, just geometry.

And if your pipeline is seeded with k-means++ and run five times to pick the best of five, you have a different bottleneck than the one this fixes. One person asked about that in the thread and i don't think got a clean answer.

The other caveat is duller. The authors wrote the baselines, the authors ran the benchmarks, and the authors are FAISS contributors.

That doesn't make the numbers wrong. It makes them unverified by anyone with an incentive to find the flaw.

What i actually took from it

The 45x number will get quoted everywhere and it will be wrong for most readers. That is fine. Numbers always are.

What stuck with me is a 1967 update rule still sitting inside the mini-batch clustering code that half the vector search world depends on. Nobody replaced it for fifty-nine years because it was good enough and because clustering was never the interesting part of the pipeline.

Then someone looked at it properly, wrote down two equations, and made the old thing obsolete in a weekend.

I still have that forty-minute job. I'm going to try the two-line swap and see if it gets shorter. And if it doesn't, i'll know why, which is more than i knew before i read the thread.