We ran Meta's e-means on SIFT1M: 25-iteration k-means quality in 3 epochs, 7× faster on CPU, and the same IVF recall

Meta FAIR's e-means is the rare k-means paper that ships as a one-line import. "e-means: outperforming k-means (in one-tenth the epochs)" (arXiv:2611.09501), by Swann Bessa, Pierre-Emmanuel Mazaré, Gergely Szilvasy, Hugo Touvron, David Picard, Matthijs Douze and Hervé Jégou, claims that a tuned mini-batch method beats the loss of 25 Lloyd iterations in 1.4 to 2.6 passes over the data, for 10–45× GPU speedups. The code is already in Faiss as faiss.contrib.e_means. We ran it on SIFT1M on an ordinary 8-core CPU and asked the question the paper mostly skips: does the better clustering make a vector index any better? The speedup held up. The index barely noticed.

What e-means changes

Mini-batch k-means is old. Sculley's 2010 version is what scikit-learn ships, and vector-quantized autoencoders have kept codebook centroids as exponential moving averages (EMA) since VQ-VAE in 2017. The usual knock on mini-batch methods is that they get fast early progress and then stall above Lloyd's final error, and that you have to guess the batch size and step size for every new dataset.

e-means keeps a running count and running sum per cluster, updated by EMA, and reads each centroid off as their ratio, so a centroid always stays inside the cloud of points that pulled it. On top of that come a cosine schedule on the step size, a Faiss-style split of a big "donor" cluster whenever a centroid stops receiving points, and a final pass that replaces each centroid with the plain mean of its last-epoch points. The authors' own ablation (Table 1) is candid about where the gain sits: turning off dead-cluster revival costs about 3% in training error, while the cosine schedule and the finalization step each move it by a fraction of a percent.

The part that makes it a drop-in replacement is the scaling laws. Batch size and starting step come from two power laws in the number of points, clusters and epochs, fitted on 75,000 runs over a single dataset (DEEP) and then checked on SIFT, SPACEV, arXiv and AG-News embeddings, where the paper reports a median regret of 0.07% against the best hand-picked step. You pass k and a number of epochs; nothing else.

What we ran

We installed faiss-cpu 1.16.0 from PyPI, which already contains the e-means code, and clustered the 1 million SIFT1M base vectors (128 dimensions) into k = 16,384 centroids, the same setting as one row of the paper's Table 5. e-means ran with its defaults at 1, 2, 3 and 5 epochs, two seeds each. The baseline was faiss.Kmeans (Lloyd, random initialization, no subsampling) at 5, 10 and 25 iterations. Faiss uses 25 iterations by default for plain clustering and 10 when it trains the coarse quantizer of an IVF index, so both defaults are in the table. Training error is the mean squared distance of all 1M points to their nearest final centroid; test error uses the 10,000 SIFT1M queries. Then each set of centroids became the coarse quantizer of an IndexIVFFlat, and we measured 1-recall@1 against the official ground truth.

e-means rows are means over two seeds; the Lloyd-25 reference is the mean of its two runs. Single machine, 8 threads, wall-clock time for training only.

What holds up

The headline claim does. Three epochs of e-means beat 25 Lloyd iterations on training error in 63 seconds against 441, about 7× faster; on held-out error it was already ahead after two epochs, a 10× gap. That lines up with the paper's own CPU figures (9–15× on eleven VIBE datasets in Table 11) and with its SIFT1M row, where three epochs land 0.35% below 25 random-init Lloyd iterations; we measured 0.29% on the test set. Against what a Faiss IVF index actually runs by default, 10 iterations, two epochs of e-means were about 4× faster and still slightly better on both errors.

Two seeds of each method also moved the errors in the same direction every time, so the ordering is not a lucky draw.

What the error numbers don't tell you

The improvements in mean squared error are fractions of a percent, and they mostly vanish once the centroids are used for search. At nprobe 16, three-epoch e-means gave 0.822 recall@1 against 0.815 and 0.822 for the two 25-iteration Lloyd runs. The spread between two Lloyd seeds is bigger than the gap between methods. e-means' lists were a little more balanced (an imbalance factor of 1.19 against 1.22), which in principle trims search cost, but made no visible difference in our search timings.

So for vector search, the honest summary is: same index, built several times faster. That is the useful part. The paper's framing, that e-means "converges to lower losses, frequently even beating k-means++", is true on the loss, but a 0.3% lower loss is not why anyone should switch.

A few other caveats are in the paper itself. When Flash-KMeans is given greedy k-means++ initialization instead of random, e-means' lead after five epochs shrinks to 0.06–0.33% (Table 5), and the authors argue, fairly, that k-means++ seeding costs orders of magnitude more time than the clustering. The scaling laws were tuned on relatively high-dimensional data and are, by the authors' account, not optimal for very low-dimensional or tiny datasets. And one epoch is not enough: our one-epoch runs left 31 and 41 of the 16,384 IVF lists empty, where every other configuration left at most two.

On Hacker News, where the release drew 513 points, the sharpest criticism was that the paper measures inertia rather than "the things that matter". Bessa replied there that results on cluster-quality metrics (ARI and NMI) on ImageNet and synthetic data will come "in a later revision". Our recall check covers one of those things for one dataset; it says nothing about deduplication or data curation, where the paper's 10-billion-vector DINO10B experiment is aimed.

Who should care

Anyone who rebuilds IVF indexes, shards or quantization codebooks regularly is paying for Lloyd iterations that e-means does in a fraction of the time, with no tuning and a familiar API (NumpyEmeans(d, k).train(x) on CPU, a PyTorch path with Triton and CuTe kernels on GPU). We did not test the GPU claims, the 10-billion-point run or the FP8 and INT8 assignment paths. On a CPU and a classic benchmark, though, the speedup is real and the quality is at least as good. Just don't expect your recall to go up.