On November 10, Meta FAIR researcher Swann Bessa announced e-means on X, a clustering algorithm that replaces classic Lloyd k-means and is open-sourced in FAISS 1.16.0. It swaps full-batch iterations for mini-batch updates with exponential moving averages, and fitted scaling laws set the batch size and step size automatically, so k is the only setting. The paper says that on a range of embedding datasets e-means beats the loss Lloyd reaches after 25 epochs in 1.4 to 2.6 epochs, running 10-45x faster than Flash-KMeans on GPU and 8-15x faster than FAISS k-means on CPU (authors' figures). Teams building vector indexes, RAG pipelines, or dedup jobs can speed up this step directly.
Key Takeaways
- ✓Epochs: on a range of embedding datasets it beats Lloyd's 25-epoch test loss in 1.4-2.6 epochs; each of the 11 VIBE datasets needs only 1.6-2.4 epochs (paper/authors' figures)
- ✓Speed: 10-45x faster than Flash-KMeans on GPU and 8-15x faster than FAISS k-means on CPU; on one H100 with 10M vectors and 65,536 clusters, 25 Flash-KMeans epochs take 14-22 seconds
- ✓Scale: it splits 10 billion DINO embeddings into 16 million clusters in 2.5 epochs, below Lloyd's loss at 25 epochs
- ✓Dead clusters: with 1M vectors and k=16,384, reviving by proportionally splitting large clusters keeps dead clusters at 0.1%-0.3%, versus 4.6%-14.3% for EnCodec-style resampling
- ✓Getting started:
from faiss.contrib.e_means import Emeans, 5 epochs by default, PyTorch and NumPy supported; paper arXiv:2611.09501
Key Decision Metrics at a Glance
Turn your technical choice into a development budget
Compare 40 dev plans & simulate token costs vs $20/mo subscriptions
Project Links & Resources
Direct AccessIn-Depth Technical Analysis
Core Background and Industry Pain Points
k-means is a basic step in vector search, RAG, quantization, and data cleaning: building a FAISS IVF index or clustering a corpus for dedup starts with it. The standard Lloyd algorithm must scan the whole dataset before each centroid update and usually runs 20 to 50 iterations, which gets slow at hundreds of millions of vectors. Most existing mini-batch methods still use MacQueen's 1967 rule and often leave "dead" clusters.
Architecture Highlights and Underlying Mechanisms
e-means updates every cluster's count and vector sum on each mini-batch, using an exponential moving average to fade out old assignments, and takes the centroid as their ratio. Scaling laws fitted in the paper compute the batch size and initial step size from the data size, cluster count, and epochs, and the step follows a cosine schedule. It also improves initialization, revives dead clusters by splitting large ones in proportion to size, finishes on each cluster's exact mean, and ships fused GPU kernels.
Authoritative Benchmarks and Measured Comparisons
These are the paper's and authors' figures. On a range of embedding datasets, e-means beats Lloyd's 25-epoch loss in 1.4 to 2.6 epochs, runs 10-45x faster than Flash-KMeans on GPU and 8-15x faster than FAISS k-means on CPU, and splits 10 billion DINO embeddings into 16 million clusters in 2.5 epochs. In toy experiments over 200 random starts, Lloyd got stuck in a bad local minimum 15.5% to 46% of the time, versus 0% to 4% for e-means. No independent replication has been published yet.
Developer Adoption and Getting Started
e-means is open source in faiss/contrib/e_means as part of FAISS 1.16.0. Create it with Emeans(d, k, nepochs=T) and call train(x) to get centroids and labels; NumPy users can use NumpyEmeans. Compare test loss and runtime against Lloyd on your own embeddings before swapping it into an IVF training pipeline. The project page also has an interactive in-browser demo.
Benchmark side-by-side against alternatives, or calculate monthly token cost vs subscription break-even.
Discussion & Comments
0Sign in to join the discussion
Connect with AI developers to exchange benchmark insights.