10x faster k-means? I re-ran it and got 1.5x

e-means promises 10x faster k-means at equal loss. My reimplementation, built from their published update rule, got 1.5x faster and 1.4% worse loss — and the code their blog links to returns a 404.

What e-means claims

The post went up on Hacker News today (251 points): e-means, from Meta FAIR researchers, replaces Lloyd's full-batch updates with mini-batch exponential moving averages. The headline numbers are big: 10–45x wall-clock reduction on GPU against Flash-KMeans, 8–15x on CPU against Faiss, and 1.6 to 2.4 epochs to reach the test loss Lloyd's algorithm reaches in 25. The paper is arXiv:2611.09501, and the blog is unusually specific about the method — it prints the exact update rule and the fitted scaling laws for batch size and step size. That specificity is what made it testable.

One problem first: the blog's code link points to faiss/contrib/e_means. As of today that path 404s on GitHub, and faiss-cpu 1.15.1 — the latest pip release — has no e_means module. The code is not shippable yet. So I reimplemented the published rule myself in NumPy, using their scaling-law constants verbatim:

# the e-means update, from the blog S_j <- (1-a) * S_j + a * s_j N_j <- (1-a) * N_j + a * n_j c_j = S_j / N_j # scaling laws, default law (blog table) B = 0.035 * k**0.13 * n**0.88 * T**0.81 a0 = min(0.824 * k**-0.46 * B**0.90 * n**-0.45 * T**-0.11, 1) 

Plus cosine decay of a from a0 down to 0.1*a0, and the finalization step the blog describes: end on each cluster's exact last-epoch mean. That is the whole algorithm as published. The baseline is Faiss Kmeans (Lloyd), 25 iterations, same data, same random-point initialization, same machine: a 4-vCPU VM.

Experiment 1: 100,000 points, 128 dims, 1,024 clusters

Synthetic Gaussian blobs — 64 clusters of structure, the kind of data where Lloyd converges fast and there is little room to beat it.

Lloyd 25 iters: 18.7s final MSE=121.7232 e-means (my impl) 5 epochs: 12.4s B=7972 a0=0.5197 per-epoch MSE: [124.6628, 124.4564, 123.9563, 123.604, 123.5087, 123.4541] final MSE=123.4541 vs Lloyd 121.7232 (+1.42%) wall-clock speedup vs Lloyd-25: 1.51x e-means did NOT beat Lloyd-25 MSE within 5 epochs 

1.5x, not 10x — and 1.4% worse loss, not equal. Two things cut against the headline here. First, my data is Lloyd-friendly: well-separated blobs, where 25 full Lloyd passes are cheap (Faiss does them in 18.7 seconds). The paper's 8–15x CPU number is measured on real embedding datasets (DEEP, SIFT, VIBE) at 1M–100M points with k up to 65,536, where a full Lloyd pass is the expensive part. Second, my implementation is NumPy plus a Faiss index rebuilt per mini-batch — no fused kernels, which is where the paper says the epoch savings turn into wall-clock savings.

Experiment 2: structureless embeddings, where Lloyd should suffer

Random normalized vectors, n=50,000, d=256, k=1,024 — no cluster structure at all.

Lloyd 25 iters: 10.7s MSE=0.9248 e-means T=5: 10.4s B=4331 a0=0.410 per-epoch MSE=[0.9396, 0.9417, 0.9387, 0.936, 0.9352, 0.9347] final 0.9347 vs Lloyd 0.9248 (+1.07%) speedup 1.03x e-means T=10: 16.8s B=7594 a0=0.630 final 0.9380 vs Lloyd 0.9248 (+1.43%) speedup 0.64x 

No structure, no win: 1.03x at 5 epochs, and giving it 10 epochs made it slower and worse (0.64x, +1.43%). The scaling law grows the batch with T, so the 10-epoch run takes fewer, larger steps — and on structureless data the EMA just smears. This is the regime the paper never claims: its datasets are real embeddings with real cluster structure.

Experiment 3: the toy local-minima test — where I first got it wrong

The blog's most checkable claim is a toy: two blobs of very different sizes (900 vs 100 points), k=8, 200 random starts. Lloyd stays stuck in the pathological configuration — two centroids on the small blob, the large blob short — on 26% of starts; e-means on 3.5%.

My first attempt reproduced nothing: Lloyd stuck 0%, e-means stuck 72%. The bug was mine, twice over. I had initialized from random data points (which puts every centroid on a real blob, so Lloyd almost never gets trapped) and I had skipped the dead-cluster revival the paper explicitly calls out. Fixing both — random-vector initialization, as the paper's figures use, plus revival by proportional split (sample a live cluster with probability proportional to its size, split it in two) — flipped the result:

revive=False: Lloyd stuck 12.0%, e-means stuck 49.0%, mean MSE Lloyd 0.5934 vs e-means 0.6271 (+5.68%) revive=True: Lloyd stuck 25.5%, e-means stuck 14.0%, mean MSE Lloyd 0.5934 vs e-means 0.5909 (-0.43%) blog claimed: Lloyd stuck 26%, e-means 3.5% 

Lloyd's 25.5% against the claimed 26% is a clean reproduction. My e-means stuck rate (14.0%) is the same direction as the claimed 3.5% but weaker — fair warning on my side: my revival is a rough approximation of theirs, and my "stuck" is a proxy (more than 1% worse than the better of the two runs for that seed), not their exact pathological-configuration definition. Even so, the mean MSE flips sign once revival is in: e-means goes from +5.68% worse to -0.43% better.

What I actually learned

The headline 10x is a regime claim, not a universal one. It holds where Lloyd's full passes are the bottleneck — large k, real embeddings, GPU kernels — and it depends on the components the paper flags as essential. The toy experiment is the proof of that dependence: the same EMA update rule, without dead-cluster revival, is worse than Lloyd on the authors' own toy (49% stuck vs 12%). With revival, it beats Lloyd. The update rule is not the algorithm. The initialization, the revival, and the finalization are load-bearing, and a reimplementation that skips them measures a different method.

Two honest caveats. First, this is my reimplementation of a published rule, not the authors' code — which is not publicly available yet, despite the blog's link. Second, my datasets are synthetic and small; the paper's numbers come from 24 datasets up to 100M points. The 10x may well be real at that scale. But at the scale most of us actually cluster at — 100k points, k in the low thousands, on a CPU — what I measured is 1.5x and slightly worse loss, and the toy result only reproduces once you implement the parts that are easy to skip.

Sources: e-means blog, e-means.github.io (Hacker News, November 9, 2026); arXiv:2611.09501, "e-means: outperforming k-means (in one-tenth the epochs)"; GitHub API check on facebookresearch/faiss faiss/contrib/e_means (404, November 9, 2026); faiss-cpu 1.15.1. All timings measured on this machine (4 vCPU VM): Faiss Kmeans vs my NumPy reimplementation, same initialization, same data.