e-means: Meta FAIR's EMA mini-batch k-means matches Lloyd's 25-epoch loss in 1.4–2.6 epochs — 10–45× faster, shipped in FAISS 1.16.0
EMA mini-batch updates plus fitted scaling laws land on a better corner of the batch-size × step landscape than Lloyd's full-batch setting — lower loss and an order-of-magnitude speedup, shipped in FAISS 1.16.0.
Meta FAIR's new e-means clustering algorithm beats the 25-epoch loss of Lloyd's k-means in 1.4–2.6 epochs — a claimed 10–45× GPU wall-clock speedup — by reframing k-means as a two-knob optimization problem and fitting scaling laws to set the knobs. The code ships MIT-licensed in FAISS 1.16.0, and the team released a new 10-billion-vector benchmark, DINO10B, to demonstrate it.
What shipped
e-means is a k-means variant from six Meta FAIR researchers (including LLAMA author Hugo Touvron and Faiss maintainers Matthijs Douze and Hervé Jégou) plus David Picard of École Nationale des Ponts et Chaussées; lead author Swann Bessa holds affiliations with both. Instead of Lloyd's full-dataset recompute, it updates centroids with an exponential moving average over mini-batches. It picks the batch size and step from fitted scaling laws rather than a hyperparameter sweep.
The core update is simple. Per cluster, e-means keeps a count N_j and a sum S_j and reads the centroid as c_j = S_j / N_j rather than storing it. On each mini-batch it applies N_j ← γN_j + (1−γ)n_j and S_j ← γS_j + (1−γ)s_j, where n_j and s_j are the batch's count and sum assigned to cluster j (paper, Eqs. 2–4). Lloyd's algorithm is a special case: set the batch to the full dataset and γ to 0, and one e-means iteration is exactly one Lloyd iteration.
The authors' central claim is that this full-batch corner is a bad place to be. On the DEEP dataset, Lloyd's setting sits about 1.8% above the best loss achievable on the batch-size × step landscape, and the low-loss optimum lies on a diagonal band where large batches pair with large steps (project page).
Mini-batch noise also helps the optimizer escape local minima. The authors report that on four toy problems, Lloyd stayed stuck more than 1% worse than the best on 26%, 43%, 15.5%, and 46% of 200 random starts, versus 3.5%, 4%, 0%, and 0% for e-means (project page).
Beyond the EMA rule, the recipe adds a cosine schedule of the step (from α₀ down to 0.1α₀), dead-cluster revival (every five updates, clusters below 10% of mean mass are split off a large donor cluster), and a finalization stage that ends on each cluster's exact last-epoch mean. On DEEP with 16,384 clusters, the authors report that turning revival off leaves 4,313 dead clusters (26.3%); with proportional splitting, 47 (0.3%) (MarkTechPost).
The scaling laws make this runnable without tuning. Fitted on 75,000 runs and validated on held-out datasets (alphaXiv), they give closed-form rules for batch size and starting step as functions of n (vectors), k (clusters), and T (passes) — for example the "throughput" batch law B = 0.035134 · k^0.134749 · n^0.876473 · T^0.813344, with an R² of 0.96 and held-out regret around 0.2% (FAISS README, project page).

Why it matters
The headline result is that you don't have to trade quality for speed. On a 1-billion-vector subset of DINO10B with 1,048,576 clusters, the authors report e-means reaching Flash-KMeans' 25-epoch test MSE in 1.6 epochs, a 45.5× wall-clock speedup on eight H100s. Across the paper's table, e-means needs 1.4–2.6 epochs and the speedups range from 9.5× to 45.5× (alphaXiv summary).
The flagship run is the full DINO10B: 10 billion DINOv3 embeddings, 1024-dimensional, clustered into 16 million centroids. The authors report reaching a test MSE of 12.985×10⁴ in 2.5 epochs — 0.014% below exact Lloyd@25's 12.987×10⁴ — in 779 GPU-hours across 32 machines, versus 6,784 GPU-hours across 64 machines for the Lloyd baseline. An approximate-assignment (IVF) variant reached a loss 0.033% below Lloyd@25 in 23.2 GPU-hours on a single machine.
For engineers building retrieval, quantization, and data-curation pipelines, the practical win is that e-means ships as a drop-in in FAISS 1.16.0 under faiss.contrib.e_means, with NumPy, PyTorch, Triton, and CuTe backends and fractional epochs (the default is 5, and 2.5 is valid). On GPU it runs through PyTorch with Triton/CuTe kernels and never calls faiss; on CPU it uses faiss.knn. The auto-scaling defaults pick the "quality" batch law for low-dimensional data (d ≤ 16) and "throughput" otherwise.
Caveats
Every headline number here is self-reported by the authors, and several are worth treating with care:
- The 45.5× figure rests on a single seed: the authors disclose that the 1-billion-vector speed comparison used one seed (alphaXiv).
- The baseline above 100M scale is their own k-means. Figure 1's caption discloses that Flash-KMeans is limited to one node, so the team used their own implementation of k-means to run it above 100M scale (paper).
- The comparison is against a fixed 25-epoch budget, not proven convergence. "Beats Lloyd at 25 epochs" is a budget reference; Lloyd's loss decreases monotonically, so this doesn't establish that e-means converges to a lower optimum in general.
- The scaling laws are tuned for relatively high-dimensional data and "are not optimal for very low-dimensional, tiny problems," per the authors.
- The low-k, multi-node regime is contested. On Hacker News, commenters argued that with few centroids the distributed allreduce of per-update stats becomes the bottleneck; the lead author responded that the batch law deliberately returns the largest batch whose loss stays within ~0.2% of the best, and that in high n/k (few-centroid) regimes you should subsample to ~250 points per cluster. This is disputed rather than resolved (HN thread).
- Novelty is disputed. Some commenters note mini-batch k-means with EMA-style updates is not new; the authors counter that they know of no paper using pure EMA updates for static-dataset k-means, and invited references.
- The dataset and baseline are the authors' own. DINO10B was created by the same team for this paper, and the Faiss baseline is their own library — worth keeping in mind for the "independent" framing.
The paper is a preprint with no peer review, and as of writing we found no independent reproduction of the headline numbers. Still, it is unusually audit-friendly: the code is MIT-licensed in the public FAISS repo, the dataset is documented and downloadable, and the authors engaged openly with criticism in the HN thread.