What Is e-means? Meta's Faster k-means Explained

e-means is a new clustering algorithm from Meta FAIR that solves exactly the same problem as k-means (find k centroids that minimize the squared distance from each point to its nearest centroid) but gets there in far fewer passes over the data. Instead of Lloyd's classic full pass per update, it updates centroids after every small batch using exponential moving averages, and it picks its own batch size and step size from scaling laws, so the only settings you give it are the same ones you give k-means: the dimension, the number of clusters and how many passes to run. The code lives in the Faiss repository under the MIT license.

The authors report that e-means beats the loss Lloyd reaches after 25 passes in roughly 1.4 to 2.6 passes, which they measure as a 10 to 45 times wall clock speedup on GPU and 8 to 15 times on CPU. The paper (arXiv 2611.09501) and project page reached the Hacker News front page on November 9, 2026 with more than 400 points. Below: how it works, how to install it now (the PyPI wheel lacks it), our own small CPU test, and when to switch.

What e-means is, in plain terms

k-means is everywhere in machine learning: grouping embeddings, building vector index cells, training quantization codebooks, curating datasets and, per the paper, compressing the attention cache in LLM stacks. The standard solver is Lloyd's algorithm. Each iteration assigns every point to its nearest centroid, then moves each centroid to the mean of its points. One iteration is one full pass, and Faiss runs 25 of them by default.

e-means keeps the objective and the output (k centroids plus a label per point) and changes the optimizer. The team behind it includes Matthijs Douze and Hervé Jégou, two of the Faiss authors, and Hugo Touvron. Lead author Swann Bessa described it on Hacker News as a drop in replacement: in Faiss you call Emeans(d, k).train(x) where you would have called Kmeans(d, k).train(x).

How e-means works

Every method keeps, for each cluster, a running count of points and a running sum of those points, and the centroid is the sum divided by the count. The difference is how those two numbers change.

• Lloyd throws the old values away each pass and recomputes them from the full dataset.
• MacQueen style mini batch k-means (the 1967 rule most mini batch methods still use) keeps adding to them forever, so early, poorly placed assignments never fade out.
• e-means blends each batch in with a step size alpha: the new count is (1 minus alpha) times the old count plus alpha times the batch count, and the same for the sum. Old assignments fade at rate alpha, so a centroid tracks where its points are now.

On top of that rule the project adds four pieces, according to the paper and the e-means README:

1. Scaling laws for the settings. Two fitted power laws set the batch size and the starting step from the number of points n, the number of clusters k and the pass budget T. The authors report that following the laws costs about 0.07 percent extra loss compared with the best setting found by a full sweep on held out datasets.
2. A cosine schedule. The step shrinks along a cosine curve to a tenth of its starting value, the way a learning rate decays when training a neural network.
3. Dead cluster revival. Every five batches, any cluster whose count has dropped below a tenth of the average is rebuilt by splitting a busy cluster in two, the trick Faiss already uses. In the paper's ablation this was the most important component.
4. A closing mean. At the end of the last pass, each centroid is set to the exact mean of the points that pass assigned to it, which lowers training loss at almost no cost.

With the whole dataset as one batch and a step of 1, an e-means step is exactly a Lloyd iteration. The authors' sweep found that corner is far from the best setting.

Why it beats Lloyd on loss, not just speed

Lloyd only ever lowers the loss, so once it settles into a poor arrangement it stays there. Mini batch updates are noisy, and that noise helps e-means climb out. On the project page's toy example with two blobs of very different sizes and eight clusters, Lloyd stayed stuck on 26 percent of 200 random starts and e-means on 3.5 percent. In another toy layout (five blobs on a line), Lloyd stayed stuck on 46 percent of starts and e-means on none.

On real embedding datasets, the paper reports that e-means ends below Lloyd on both training and held out error, and below Lloyd started from k-means++ seeding. It also partitioned DINO10B, a new set of 10 billion image patch embeddings, into about 16 million clusters in 2.5 passes.

e-means vs k-means: the published numbers

These are the authors' figures, not ours. Treat them as vendor benchmarks until more independent results appear.

One independent report exists so far. In the Hacker News thread, a developer of the Infino retrieval engine tested it on 500,000 LAION embeddings (768 dimensions, 4,096 cells) on a Mac. With the same 5 passes as their Lloyd setup, they saw about 4 times faster training, slightly better recall (0.9518 vs 0.9473 at 32 probes) and no empty cells instead of 7. With 2 passes it was about 10 times faster with recall close to before, per their benchmark issue.

Our quick CPU test

We ran the NumPy version on an 8 vCPU Xeon box: 200,000 random Gaussian vectors in 64 dimensions, 1,024 clusters, one seed, scored on 20,000 held out vectors. Faiss Kmeans ran 25 iterations on the full data (subsampling turned off).

Three passes matched Lloyd's held out error about five times faster, and five passes beat it on both errors. Random Gaussian data has no real clusters, so the gaps are small, and one seed proves little. Rerun on your own data before switching a production index build.

How to install e-means today

The README says e-means ships inside Faiss, and pip install faiss-cpu is enough for CPU runs. There is a catch as of November 10, 2026: the newest wheel on PyPI is 1.15.1 from September 16, and the e-means code only landed on the Faiss main branch from November 2. We checked the 1.15.1 wheel, and it has no contrib/e_means folder. Until the next Faiss release, you have three options:

1. Build Faiss from the main branch, following the Faiss install docs.
2. Copy the folder. The CPU path is plain Python on top of Faiss and NumPy. For our test we installed faiss-cpu 1.15.1 and copied __init__.py, e_means.py and base.py from contrib/e_means on main into the installed faiss/contrib/e_means/ folder. That is a workaround, not an official install.
3. Wait for the next Faiss release, then pip install faiss-cpu will carry it.

A Rust port called emeans also appeared on PyPI on November 10 from a community developer. It is not a Meta package.

For GPU runs the README says the CPU build of Faiss is still enough, because e-means runs on GPU through PyTorch and never calls Faiss there. Install CUDA enabled PyTorch (its Linux CUDA builds bring Triton). For the fastest CuTe kernels on H100 or H200 you also need nvidia-cutlass-dsl[cu13] 4.7.1 or later and quack-kernels[cu13] 0.6.5 or later.

How to use e-means in Python

On a CPU, with NumPy arrays:

import numpy as np
from faiss.contrib.e_means import NumpyEmeans

x = np.random.rand(200_000, 64).astype("float32")
em = NumpyEmeans(64, 500)          # d, k; 5 passes by default
centroids, labels = em.train(x)
distances, new_labels = em.assign(np.random.rand(1000, 64).astype("float32"))

On a GPU, pass a PyTorch tensor that is already on the device:

import torch
from faiss.contrib.e_means import Emeans

xg = torch.from_numpy(x).cuda().to(torch.bfloat16)
assert torch.isfinite(xg).all()    # the GPU path does not check for NaN or inf
em = Emeans(64, 1024, nepochs=3)
centroids, labels = em.train(xg)
print(em.recipe["assignment_backend"], em.recipe["batch_size"])

Settings worth knowing from the README:

• nepochs (default 5) is the number of passes and can be fractional, such as 2.5. The README says 5 is typically enough to beat Lloyd at convergence.
• batch_law="quality" uses batches about 8 times smaller for lower final error. At 16 dimensions or fewer it is picked automatically.
• spherical=True clusters normalized vectors by cosine similarity, useful for text embeddings such as those from EmbeddingGemma 2.
• The labels train returns come from the last pass, so a few may not match the final nearest centroid. Call assign on the training vectors if you need exact labels.

Hardware support

Per the README, CuTe runs on H100 and H200, Triton on A100 or newer and on recent cards such as the RTX 30 and 40 series, L40S and A10. Older GPUs like V100 and T4 only get the slower PyTorch path with native FP32 input. AMD GPUs work through PyTorch with native FP32 (QuantizedEmeans(d, k, quantizer=None)). float64 is not supported on GPU. The authors suggest a GPU once points times clusters goes above 10 billion; below that, the CPU path is fine.

Who should use e-means

• Use it if you rebuild IVF index cells, train vector quantization codebooks or cluster large embedding sets often. Fewer passes means real savings at that scale.
• Try it if you already use faiss.Kmeans and can test on a copy of your data. The call is nearly the same.
• Stay with scikit-learn for small tabular clustering inside a scikit-learn pipeline, where KMeans runs in seconds anyway. See TensorFlow vs scikit-learn for where classical tools fit.
• Be careful with very low dimensional or tiny datasets. The paper says its scaling laws were tuned on higher dimensional data and are not optimal there.

For the wider Python toolbox, see our best ML frameworks for Python roundup.

Pros

• Same inputs and outputs as k-means, nothing extra to tune
• Large reported speedups on CPU and GPU, plus lower final loss
• MIT licensed, inside a library many teams already use

Cons

• Not in a Faiss release on PyPI yet
• Speed figures come almost entirely from the authors so far
• GPU input is not checked for NaN or infinity
• Fastest kernels need recent NVIDIA hardware

FAQ

Is e-means better than k-means?

e-means is a different solver for the same k-means objective. In the authors' tests on many embedding datasets it reached lower loss than Lloyd's algorithm in a tenth of the passes. In our single CPU run it matched Lloyd's held out error about five times faster. Test it on your own data before switching.

Is e-means in scikit-learn?

No. As of November 10, 2026 it lives only in the Faiss repository under faiss.contrib.e_means. scikit-learn 1.9.1 offers KMeans and MiniBatchKMeans, which use the older update rules.

Can I pip install e-means?

Not from an official package yet. The current faiss-cpu wheel, 1.15.1, predates the code. Build Faiss from the main branch, copy the contrib/e_means folder, or wait for the next Faiss release. The emeans package on PyPI is an unofficial Rust port.

Does e-means need a GPU?

No. The NumPy version runs on any CPU with Faiss installed, and the README calls the CPU fine for problems where points times clusters stays below about 10 billion. GPUs are much faster for larger jobs.

How many epochs should I run?

The default is 5, which the README says is typically enough to beat Lloyd at convergence. The paper's experiments match Lloyd's 25 pass loss in about 1.4 to 2.6 passes, so 2 to 3 is a reasonable starting point when speed matters.

Who made e-means?

Researchers at Meta FAIR and École des Ponts: Swann Bessa, Pierre-Emmanuel Mazaré, Gergely Szilvasy, Hugo Touvron, David Picard, Matthijs Douze and Hervé Jégou.