Blog

e-means fits k-means several times faster on high-dimensional data and the choice did not change search results

If you build a vector index, a product-quantization codebook or a colour palette, you probably fit it with Lloyd's k-means. e-means, a variant from Meta FAIR (arXiv 2611.09501) that ships with faiss, promises the same clusters in a fraction of the work. Claude Code on the web tested that on 61 clustering problems and on a compressed search index, all on a four-core CPU. On data with 32 or more dimensions and at least 25 points per cluster, e-means usually finished two and a half to five times sooner and made clusters at least as tight. On three-dimensional data such as pixel colours it was often slower. In the search index, good cluster centres improved results, but centres from e-means and from plain k-means scored almost the same.

Bar chart from the explainer: time for 25 Lloyd rounds divided by time for 2 e-means passes, median with at least 25 points per cluster, by dimension: 0.96 at 3, 2.65 at 32, 4.91 at 128, 4.42 at 768; at 32 or more dimensions e-means ended within 1% of Lloyd's error or below it

Oskar Austegard asked for this on 2026-11-13, after reading LookAtMyQuant 2, a write-up on compressing language models that fits its codebooks with e-means. His question was whether e-means would help the compressed search index from the previous post. Claude Code built the narrated explainer above from the measurements as a Kinescript scene, voiced by Kokoro in my voice.

e-means nudges the centres after every small batch instead of after every full pass

Lloyd's algorithm looks at every point, assigns each one to its nearest centre, and only then moves every centre to the middle of its points. It repeats that, often 20 or 25 times, and each round reads the whole dataset.

e-means reads a small batch of points and nudges the centres those points belong to a little way toward them, then moves on to the next batch. The nudges get smaller as the run goes on. Every few batches it moves any centre that no points have chosen next to a crowded one, which splits the crowded cluster in two. scikit-learn's MiniBatchKMeans also works in batches; what the e-means paper adds are rules, fitted to the authors' own runs, for how big the batches and the first nudges should be. MiniBatchKMeans was not part of this test.

e-means finished first on all 35 problems with 32 or more dimensions and 25 or more points per cluster

Both algorithms got a fixed budget and started from the same random centres: Lloyd ran 25 full rounds, and e-means ran two passes. Then the time each took and the tightness of the resulting clusters were compared.

On the 35 problems with 32 or more dimensions and at least 25 points per cluster, e-means finished first every time. The typical problem ran two and a half to five times faster, and the best case twelve times. Its clusters were as tight as Lloyd's, within 1%, and on 14 of the problems more than 3% tighter.

Two caveats apply to these speeds. Lloyd used every point in every round, while faiss by default trains on a sample of at most 256 points per centre; that would have sped Lloyd up on most of these problems and was not tested. The PyTorch version of e-means ran faster still, up to 52 times sooner than Lloyd, but part of that speed comes from PyTorch's search code rather than from the algorithm.

e-means needed about 25 points per cluster on synthetic data

When the synthetic test data had fewer than about 25 points per cluster, e-means stopped with clusters up to 38% looser than Lloyd's. On the real search data, with only 18 points per cluster, it matched Lloyd. Small clusters are a reason to check, and the threshold is not exact.

On pixel colours faiss's plain k-means was usually faster

With three numbers per point, comparing a point to every centre is so cheap that faiss's all-at-once pass is extremely efficient. e-means works in small batches, and at three dimensions faiss handles each batch about fifty times less efficiently per comparison than one big pass. With a thousand or more colours in the palette, e-means took two to ten times longer than Lloyd. With 64 colours or fewer it was still faster, by up to three times. These timings are for faiss; a palette tool with its own assignment loop might behave differently.

Nearby reference points made one bit score like two in the search index

Oskar's question was about the LateOn search index. It stores one vector for each word-piece of every document, and to save space it keeps each vector at one or two bits per number, as an offset from a reference point. Until now that reference was one average of everything.

Giving each vector a nearby reference instead, the nearest of thousands of cluster centres, makes the offset smaller, so it loses less when squeezed into one bit. At one bit, search quality rose about as much as adding a second bit would have. On SciFact it went from 0.730 to 0.751 nDCG@10, where two bits on the single average score 0.746; NFCorpus moved by a similar amount.

The centres have to be stored with the index, and so does each vector's choice of centre, about two bytes. In these test collections of four to five thousand documents, the table of centres took about as much space as the bit it saved. In a collection of millions of documents the table would hardly count, and the same quality would take about a third less space. That estimate includes the two-byte choice; it is arithmetic, and no collection that large was measured.

Which algorithm fitted the centres changed search quality by under half a point

e-means did not make centres that searched better. Centres from two rounds of Lloyd, 25 rounds of Lloyd and e-means gave search quality within 0.005 nDCG@10 of each other in almost every comparison. Where a difference did show, 25 rounds of Lloyd were slightly ahead. Two rounds of Lloyd took 25 seconds, e-means 26, and 25 rounds of Lloyd 321.

e-means paid off on data with 32 or more dimensions and 25 or more points per cluster

In these tests e-means was the faster way to tight clusters when the data had 32 or more dimensions and each cluster had 25 points or more, and its PyTorch version was the fastest option on the CPU. On three-dimensional data fitted with faiss, and on very small clusters, plain k-means did as well or better. For this search index, two quick rounds of plain k-means were enough.

The data, scripts and every number behind these statements are in oaustegard/experiments, emeans-pooled-residual.