e-means: k-means in a tenth of the passes

One Meta FAIR paper, explained · 100 level · November 2026

What the paper is about

k-means is one of the oldest clustering methods still in daily use. You give it a pile of vectors and a number k, and it finds k centre points, called centroids, so that every vector sits close to its nearest one. The score is the mean squared distance from each vector to its centroid, and lower is better. Vector databases use k-means to split an index into buckets, compression schemes use it to build codebooks, and data teams use it to sort and deduplicate training sets.

The standard method is Lloyd's algorithm from 1982. Each round, it reads every vector, assigns each one to its nearest centroid, and moves every centroid to the exact average of its vectors. One round is one pass over the data, or one epoch. Faiss, Meta's vector search library, runs 25 by default. On a billion vectors, each pass is expensive.

The e-means paper keeps the k-means goal and changes how the centroids move. It updates them from small batches of vectors, using a running average that forgets old batches. With a few extra pieces and two formulas that pick the settings, it beats Lloyd's 25-pass result in about two passes.

Lloyd's k-means

Reads all the data every round and sets each centroid to the exact mean of its points. Reliable, slow on large data, and it can settle into a poor layout and never leave.

Mini-batch k-means

Updates centroids from small batches. Prior versions got fast early progress and ended with a worse score than Lloyd, and each new dataset needed its settings tuned by hand.

e-means

Mini-batches with a forgetting running average, a shrinking step size, a better fix for empty clusters, and formulas that set the batch size and step. It ends with a lower score than Lloyd and needs no tuning.

Status: arXiv preprint 2611.09501, posted 6 November 2026, by seven authors from FAIR at Meta and École Nationale des Ponts et Chaussées, including Matthijs Douze and Hervé Jégou of Faiss. The code ships inside Faiss as faiss/contrib/e_means. All results below come from the authors' own runs.

The core idea: a running average that forgets

For each cluster, e-means keeps two numbers: a running count of the vectors assigned to it, and a running sum of those vectors. The centroid is the sum divided by the count. When a batch arrives, e-means assigns each of its vectors to the nearest centroid, then blends each cluster's count and sum toward what this batch contributed:

count_j  ←  (1 - α) · count_j  +  α · (vectors in this batch assigned to j)
sum_j    ←  (1 - α) · sum_j    +  α · (their sum)
centroid_j  =  sum_j / count_j

The step size α sets how far each batch pulls the centroid. Every batch shrinks the weight of all earlier batches by a factor of (1 - α), so a centroid follows recent assignments and lets go of ones made back when the centroids sat somewhere else. Lloyd's method is the special case where the batch is the whole dataset and α is 1.

The rule itself is not new. Image and audio models that learn a codebook (VQ-VAEs and neural audio codecs) have used it since 2017, with α treated as a fixed constant inherited from earlier work. Those models cluster a moving target, so nobody had compared the rule against Lloyd on a fixed dataset. The paper's contribution is to aim this rule at plain k-means, add the pieces that make it beat Lloyd there, and work out how to set it.

Lloyd's k-means 25 passes over the data Read all n vectors the whole dataset, every round Assign each vector to its nearest centroid Exact mean centroid jumps to its points' average e-means 1.4 to 2.6 passes to match Lloyd at 25 Take a batch B vectors, set by formula Assign batch vectors only Blend by α old batches fade out Revive every 5 batches α shrinks on a cosine curve, to a tenth of its start by the last batch
Both loops spend most of their compute on the assign step, so one pass costs about the same in each. e-means wins by needing fewer passes: it moves the centroids after every batch, so it moves them many times per pass where Lloyd moves them once.

The pieces that make it work

The plain running average is not enough to beat Lloyd. The paper adds five pieces and measures each one by removing it (Table 1: the DEEP dataset, 1 million vectors, 16,384 clusters, 3 passes, median of 30 seeds).

PieceWhat it doesTest score without it
Empty-cluster revivalEvery five batches, any cluster whose count falls below a tenth of the average gets refilled. e-means picks a large cluster at random, weighted by size, and splits its centroid into two nudged copies that share its count.2.24% worse with no revival. 1.15% worse when the empty slot gets a random batch vector instead, the fix most VQ-VAEs use
Cosine scheduleThe step α starts high so centroids move fast, then falls along a cosine curve to a tenth of its starting value, so they settle.Train score 0.26% worse, test score 0.06% better in this setting. The appendix shows it helps both on most datasets
Last-pass meane-means records each vector's assignment in the final pass and sets each centroid to the exact mean of those vectors. It reuses work already done, so it costs almost nothing.0.02% worse. It matters most when each cluster has few vectors
Slow running averageAn optional second set of running averages with a much slower fade. Use it instead of the last-pass mean when new vectors matter more than the training set.Used in place of the last-pass mean, it cut the test score by 0.08% and raised the train score by 0.14%
Two settings formulasSet the batch size and starting step from the dataset size, the cluster count and the pass budget. Covered in the next section.Without them you are back to tuning by hand

Empty clusters are the biggest single cost. A cluster that stops winning vectors keeps its centroid and never gets another assignment, so one of your k slots goes to waste. With revival off, 26.3% of the 16,384 clusters on DEEP ended up empty. Refilling from a random batch vector left 14.3% empty. The split rule left 0.3%.

Seeding the centroids with k-means++, the standard careful start, improved the 3-pass test score by 0.11%. k-means++ picks seeds one at a time, so it is slow to run, and the authors found it cheaper to start from random vectors and train a little longer.

No tuning: two formulas set the knobs

Earlier mini-batch methods stalled on one question: what batch size and step size should you use on a new dataset? Pick a step too small and the centroids barely move. Pick one too large and they bounce around. A batch that is too big throws away the speed advantage, and past a threshold the score drops fast.

The authors ran 75,000 training runs on one dataset (DEEP, image descriptors), across 100,000 to 100 million vectors and 256 to 65,536 clusters. They fitted two power laws to the best settings:

batch size   B  = 0.035 · k^0.13 · n^0.88 · T^0.81          (rounded to a power of 2, at most n)
first step   α0 = min(0.824 · k^-0.46 · B^0.90 · n^-0.45 · T^-0.11, 1)

n = number of vectors,  k = number of clusters,  T = number of passes

Above 2 million vectors, e-means divides B by 8, because smaller batches gave the same speed there. The batch formula targets the largest batch whose score stays within 0.2% of the best, since larger batches run faster on a GPU.

The laws read as common sense. More clusters means each one sees fewer vectors per batch, so take smaller steps. A bigger batch averages more vectors, so you can trust it with a bigger step. More passes buys room for bigger batches. As a worked example, which I computed from the paper's coefficients: 1 million vectors, 16,384 clusters and 5 passes give a batch of 65,536 and a first step of about 0.34.

The laws carried over to datasets they never saw. On SIFT, SPACEV and two text-embedding datasets, following the laws instead of the best settings from a full sweep cost a median of 0.07% (step law) and 0.19% (batch law) in score.

What happened

The main yardstick is Lloyd's score after 25 passes, the Faiss default. The question is how many passes e-means needs to beat it, and how much wall-clock time that saves on an H100 GPU against Flash-KMeans, the fastest GPU k-means the authors found.

VectorsClustersPasses to beat Flash-KMeans at 25Wall-clock speedup
1 million16,3841.4 to 2.49.5× to 12.9×
10 million65,5361.4 to 2.019.2× to 27.8×
100 million262,1441.4 to 2.619.9× to 35.9×
1 billion1,048,5761.4 to 2.021.2× to 45.5×

Ranges across four datasets (DEEP, DINO10B, SPACEV, SimSearchNet++), from the paper's Table 4. One GPU up to 100 million vectors, eight GPUs at 1 billion.

The speedup grows with dataset size. Part of it comes from the authors' GPU kernels, which compute distances in low precision (BF16, FP8, INT8) and keep only the nearest centroid for each vector instead of the full distance table.

The result held on eleven embedding datasets from the VIBE benchmark, covering text, code, images and faces with 200 to 3,072 dimensions. e-means needed 1.6 to 2.6 passes to beat Lloyd at 25. That was 8× to 22.8× faster than Flash-KMeans on one GPU, and 9× to 15× faster than Faiss on a 64-core CPU (Table 11). The project page quotes the pass range as 1.6 to 2.4, but the table lists 2.6 for GooAQ.

Billions of vectors

The authors also built DINO10B, a new dataset of 10 billion image embeddings from DINO, each with 1,024 numbers. At that size, comparing every vector with millions of centroids gets too costly, so e-means can index the centroids themselves (an IVF index) and check only the nearest few buckets. Table 3 shows the GPU hours needed to reach Lloyd's 25-pass score:

VectorsClustersExact searchIndexed centroids
100 million262,1440.028 hours0.030 hours
1 billion2.1 million4.56 hours1.05 hours
10 billion16.8 million (224)779 hours22.8 hours

Splitting 10 billion vectors into 16.8 million clusters took less than one GPU-day.

Why it ends lower, not only faster

Run Lloyd to the end, until its score stops changing, and it still finishes above e-means. Over 40 seeds on three datasets (Figure 5), e-means after 25 passes from random seeds beat Lloyd from random seeds and Lloyd seeded with k-means++.

Lloyd only ever lowers its score, so once it settles into a poor layout it stays there. The project page shows this on four small 2D toy sets, each run from 200 random starts:

The authors' explanation is that small batches make noisier updates, and the noise shakes centroids out of poor layouts. In two of the toy sets, e-means starts in the same trap as Lloyd and climbs out of it during training.

Trying it

e-means ships inside Faiss. The CPU build of Faiss runs it on NumPy arrays, and the GPU path goes through PyTorch with Triton or CuTe kernels. You pass only the dimension and the cluster count, and the formulas pick the rest. The default budget is 5 passes.

from faiss.contrib.e_means import NumpyEmeans

em = NumpyEmeans(d, k)              # d dimensions, k clusters
centroids, labels = em.train(x)     # x: float32 array of shape (n, d)

# On a GPU, pass a PyTorch tensor to Emeans instead:
# from faiss.contrib.e_means import Emeans
# em = Emeans(d, k, nepochs=3)
# centroids, labels = em.train(x_gpu)

The Faiss README lists the install steps for each backend and the overrides for batch size and step, and the project page has a browser demo.

Where I expect it to land

This part is my reading, not a claim in the paper. Most vector search systems build their index by running k-means over a sample of the embeddings, and that step often decides how long a rebuild takes. A drop-in replacement that needs a tenth of the passes, with no new settings to tune, could shorten rebuilds and let teams train on far more of their data. Faiss is the library many of those systems already call.

Limits and what to check

Tuned for many dimensions

The authors fitted the formulas on 96-dimension data and say they are not optimal on very low-dimensional or tiny datasets. The Faiss code switches to smaller batches at 16 dimensions or fewer and turns revival off at 2.

One dataset for the fit

Both formulas come from DEEP alone. They held up on the other datasets tested, but a dataset with an odd shape could still need hand settings.

k-means++ narrows the gap

Against Flash-KMeans seeded with k-means++, 3 passes of e-means do not always win. At 5 passes e-means wins all 8 setups in Table 5, by 0.06% to 0.33%.

Scores, not end tasks

The paper measures clustering error on held-out vectors. It does not measure what a lower error does to search recall or to a downstream model.

The authors ran every baseline

The authors set up Faiss, Flash-KMeans, cuML and SuperKMeans themselves (Appendix C) and wrote the e-means GPU kernels. The reproduction scripts sit in Faiss under benchs/e_means.

Further reading