Meta FAIR researchers have released e-means, a drop-in replacement for Lloyd's k-means algorithm. The e-means clustering algorithm reaches the loss Lloyd's k-means gets in 25 epochs in just 1.4 to 2.6 epochs. It ships in FAISS 1.16.0 under faiss.contrib.e_means. For anyone building vector indexes, quantizers, or data-curation pipelines, clustering is often the slowest offline step. e-means targets exactly that step.
TL;DR
- Size: It is an algorithm, tested from 100K to 10 billion points, with up to 16.7M clusters.
- Runs on: CPU or GPU, with PyTorch tensors or NumPy. Paper GPU runs use H100s.
- Performance: Lower loss than Lloyd's k-means in roughly one-tenth the epochs, across 24 dataset configurations (self-reported).
- Best case: 10–45x GPU wall-clock speedup over Flash-KMeans at equal loss.
- Worst case: 16M-centroid runs need 64 GiB of float32 accumulators, so centroids must be sharded across GPUs.
What Is e-means?
e-means is a mini-batch k-means algorithm from Meta FAIR that updates centroids using exponential moving averages. In the 2026 landscape of large-scale vector search and embedding pipelines—where datasets routinely reach billions of embeddings—efficient clustering has become a critical infrastructure concern, and e-means addresses it directly.
How Does e-means Work?
Every k-means variant keeps a sum S and a count N per cluster; the centroid is S divided by N. Methods differ only in how S and N are updated.
- Lloyd: Recomputes S and N from the full dataset each iteration.
- e-means: (Content truncated in source—see the full article for remaining details.)
via MarkTechPost