10x Faster Than Classic K-Means? Unpacking Meta's e-means

Table of Contents
In large-scale semantic product search, both catalog items and user queries are encoded as high-dimensional vectors. Take 10 million products represented by 768-dimensional float32 vectors—roughly 30.7 GB of raw vectors. Answering a query like “low-maintenance outdoor furniture for a summer patio” with brute-force distance checks means scanning all 30+ GB on every request. That is feasible for an occasional offline job, but prohibitive in an online service targeting millisecond latency at hundreds or thousands of queries per second.
Most production systems use approximate nearest neighbor (ANN) search instead, commonly an Inverted File Index (IVF): K-Means learns a set of cluster centroids, partitions the catalog vectors into buckets, and limits each query to a few nearby buckets. Probing 32 out of 65,536 buckets cuts the scan to roughly 0.05% of the catalog.
The cost shows up when the index must be rebuilt. Routine new arrivals can be inserted into existing buckets, but once the item distribution drifts—or an embedding model upgrade recomputes every vector in the catalog—a full index rebuild is unavoidable. In many large-scale search stacks, training cluster centroids is one of the costliest steps in an index refresh.
On November 6, 2026, Meta FAIR submitted “e-means: outperforming k-means (in one-tenth the epochs)"[1]. The authors leave the K-Means objective untouched and rebuild only the solver: exponential moving average (EMA) mini-batch updates paired with dead-cluster revival and empirical scaling laws. Across high-dimensional vector benchmarks, e-means takes only 1.4–2.6 epochs to match the held-out test mean squared error (MSE) of the GPU baseline Flash-KMeans[2] at 25 epochs[1].
Before translating that headline into production savings, separate four distinct quantities: epoch count, actual runtime, online recall, and end-to-end index rebuild cost.
Bottom line: e-means accelerates centroid training by cutting data scans to roughly one-tenth, while real runtime speedups depend on scale, hardware, and the baseline implementation. Whether that turns into meaningful system savings depends on how large a share centroid training takes in your full rebuild pipeline.
1. Where Do Classic Lloyd and Mini-Batch K-Means Get Stuck? #
1.1 Lloyd’s Algorithm: Heavy Full Scans and Local Traps #
Given \(n\) vectors \(X=\{x_1,\ldots,x_n\}\) in \(d\) dimensions, K-Means seeks \(k\) centroids \(C=\{c_1,\ldots,c_k\}\) that minimize the average squared distance from each vector to its nearest centroid:
\[ J(C)=\frac{1}{n}\sum_{i=1}^{n}\min_{1\le j\le k}\|x_i-c_j\|_2^2 \]This objective minimizes within-cluster squared error, not cluster-size balance; on skewed real data, small and large clusters coexisting is completely normal. Classic Lloyd’s algorithm alternates between two steps[3]:
- Assignment: find the nearest centroid for every vector, \(a_i=\arg\min_j\|x_i-c_j\|_2^2\).
- Update: set each centroid to the mean of its assigned vectors, \(c_j=\bigl(\sum_{i:a_i=j}x_i\bigr)/|\{i:a_i=j\}|\).
Under brute-force distance calculation, one full pass costs roughly \(O(nkd)\), so \(T\) epochs cost \(O(Tnkd)\). Matrix multiplication, tiling, and GPU parallelism reduce the constant factors, but every iteration still scans the entire dataset. In the full-rebuild scenarios from the opening, scanning the entire corpus on every epoch quickly makes frequent retraining expensive.
Lloyd is not just slow—it also gets stuck easily. With exact assignment and exact means, the training objective never increases. That monotonicity guarantees local improvement, not a good global layout. Picture five Gaussian blobs arranged along a line in 2D, with five centroids to place. A poor random start can place two centroids in one blob and leave another blob empty. Lloyd can then remain locked in that suboptimal layout indefinitely.
The official e-means project page illustrates this 2D five-blob demo across 200 random starts: Lloyd gets stuck on 46% of runs, while e-means fails on 0%. Readers can inspect centroid trajectories and Voronoi partitions directly in the interactive e-means Playground[4]. This 2D demo shows e-means escaping poor local layouts in low dimensions (we unpack the mechanism in Section 2), though actual convergence still depends on data geometry and initialization. On high-dimensional real embeddings, the paper uses 40 random seeds to compare fully converged Lloyd—including greedy k-means++ initialization—with randomly initialized e-means. Even in that comparison, e-means reaches lower training and test MSE[1].

Note: Screenshot from the official e-means Playground[4] (Meta logo, \(n=100{,}000\), \(k=500\), seed 0): after just 5 epochs, e-means reaches lower train and test MSE (3.99e-4 / 4.10e-4) than Lloyd after 25 epochs (4.14e-4 / 4.24e-4).
1.2 Traditional Mini-Batch: Cumulative Totals Lock In Early Errors #
Avoiding full scans and deterministic convergence traps led researchers toward stochastic mini-batches early. Mini-batch K-Means has a long history: MacQueen studied incremental updates in 1967[5], and Sculley scaled mini-batch K-Means to web datasets in 2010[6].
The discussion below focuses on classic cumulative-mean mini-batch K-Means (streaming variants with forgetting factors require separate decay tuning). These methods track a running count \(N_j\) and vector sum \(S_j\) for each cluster. Given the count \(n_j\) and sum \(s_j\) assigned to cluster \(j\) in the current batch, they update via:
\[ N_j\leftarrow N_j+n_j,\qquad S_j\leftarrow S_j+s_j,\qquad c_j=\frac{S_j}{N_j}. \]The bottleneck comes from cumulative averaging. Early in training, centroids are still inaccurate and assign many vectors to the wrong clusters. Although the relative weight of early points shrinks as \(1/N_j\) as \(N_j\) grows, that decay is far too slow—running more iterations still leaves heavy inertia from stale assignments.
Stochastic mini-batch noise gives centroids a chance to move out of their current local basin, while the solver still needs to fade old assignments and tighten late-stage variance. e-means addresses both directly: historical statistics decay exponentially, and the step size shrinks during the later stage of training.
2. How Does e-means Change Centroid Updates? #
2.1 EMA Fades Early Errors and Preserves the Convex Hull #
Drawing on the EMA codebook update used in VQ-VAE[7], e-means maintains \(N_j\) and \(S_j\) for every cluster, but decays both exponentially rather than accumulating them forever (the paper writes decay \(\gamma_t = 1-\alpha_t\); here we express the same rule directly in step size \(\alpha_t\)):
\[ \begin{aligned} N_j^{(t+1)}&=(1-\alpha_t)N_j^{(t)}+\alpha_t n_j^{(t)},\\ S_j^{(t+1)}&=(1-\alpha_t)S_j^{(t)}+\alpha_t s_j^{(t)},\\ c_j^{(t+1)}&=\frac{S_j^{(t+1)}}{N_j^{(t+1)}}. \end{aligned} \]Here \(\alpha_t\) controls the weight of the current batch. With a fixed \(\alpha\), information from \(m\) steps ago carries weight proportional to \((1-\alpha)^m\), decaying exponentially.
One structural detail matters: e-means smooths the count and vector sum jointly, so each cluster’s effective step adapts to the number of new points it receives. When cluster \(j\) receives samples in the current batch, defining the batch mean \(\bar{x}_j=s_j/n_j\) yields:
\[ \begin{aligned} c_j^{(t+1)} &=c_j^{(t)}+\eta_j^{(t)}\bigl(\bar{x}_j^{(t)}-c_j^{(t)}\bigr),\\ \eta_j^{(t)} &=\frac{\alpha_t n_j^{(t)}}{(1-\alpha_t)N_j^{(t)}+\alpha_t n_j^{(t)}}. \end{aligned} \]The effective step \(\eta_j^{(t)}\) adapts to the ratio between the current batch count and the cluster’s historical mass. If a batch assigns no vectors to cluster \(j\) (\(n_j=s_j=0\)), both \(N_j\) and \(S_j\) decay by the same factor, so \(c_j\) stays fixed until the cluster receives points again or triggers revival. When the batch covers the full dataset (\(B=n\)) and \(\alpha=1\), one update reduces exactly to a single Lloyd iteration—Lloyd is simply a special case of this rule.
Why not optimize centroids with standard deep-learning optimizers such as SGD or Adam? In Appendix E, the authors compare EMA with SGD, Adam, and SparseAdam. At small batch sizes, the methods perform similarly. When the batch size grows enough to saturate modern GPUs, SGD and Adam become less accurate or unstable[1]. The reason is geometric: EMA computes a weighted average of assigned points, so every updated centroid stays inside their convex hull. SGD and Adam use gradient steps, which carry no such constraint and can move a centroid outside the convex hull.
2.2 Reviving Dead Clusters via Donor Splitting #
In high-dimensional spaces, centroids can stop receiving vectors and turn into dead clusters that waste capacity without reducing error.
Following Faiss’s donor-splitting heuristic[8], e-means checks for dead clusters every 5 mini-batches (Faiss checks once per epoch by default)[1]. Any cluster whose EMA count drops below 10% of the average count becomes a revival candidate:
\[ N_j<0.1\cdot\frac{1}{k}\sum_{\ell=1}^{k}N_\ell. \]Revival works in two steps. First, the algorithm samples an active donor cluster with probability proportional to its count. Next, it multiplies the donor centroid’s coordinates alternately by \(1\pm\delta\) and \(1\mp\delta\) to create two symmetric, nearby child centroids, halves the donor’s count, and writes back \(S_j=c_j N_j\)[1]. Geometrically, the split places a hyperplane through the original centroid. Subsequent mini-batches pull the two children apart. Setting \(\delta\) at BF16 machine precision keeps the children distinct even during low-precision GPU distance search (see Section 4.1). The split updates only the centroid vector and statistics, so its cost depends on dimension \(d\), not cluster size; it does not rescan cluster members[1].
In a DEEP ablation (1 million vectors, 16,384 clusters), the authors define dead clusters as those with fewer than 10 final vectors. Without revival, 26.3% remain dead; resetting from random points in the current batch leaves 14.3%; donor splitting cuts the share to 0.3% and achieves the lowest test MSE[1]. The official library also adds a low-dimensional guard: for \(d\le 2\), it disables revival by default because splitting can degrade quality in very low dimensions[9].
In anomaly detection, rare-item search, or high-margin long-tail catalogs, tiny clusters are often the exact segments the business cares about. A cluster-count threshold serves only to lower global MSE, so production teams should evaluate minority-group recall separately.
2.3 Cosine Annealing and Near-Zero-Cost Finalization #
Once early exploration and dead-cluster revival are working, the second half of training needs to settle smoothly. Keeping \(\alpha\) large throughout training makes centroids jitter across mini-batches even after they reach good positions. e-means therefore anneals \(\alpha\) with a cosine schedule over \(M=T\lfloor n/B\rfloor\) updates, from \(\alpha_0\) down to \(0.1\alpha_0\):
\[ \alpha(t)=\alpha_0\left[\varepsilon+\frac{1-\varepsilon}{2} \left(1+\cos\frac{\pi t}{M}\right)\right],\qquad\varepsilon=0.1. \]Early updates move centroids rapidly across the space; late updates tighten the step to settle near a low-error minimum. The schedule borrows the intuition of learning-rate decay in deep learning, applied here to the EMA step size.
At the end of training, e-means adds two near-zero-overhead finalization strategies[1]: Last-Epoch Mean reuses the final pass’s assignments to compute exact means, while Slow-EMA tracks a shadow set of slower-decaying EMA statistics that smooth centroids without driving training (most helpful when \(n/k\) is small). The table below summarizes when to choose each:
| Strategy | Best For | Extra Pass | Error Focus | Exact Labels |
|---|---|---|---|---|
| Last-Epoch Mean | Static clustering (default) | No | Train MSE | Approx; run assign |
| Slow-EMA | Generalizing to new vectors | No | Test MSE | Needs assign |
Because centroids still shift during the last pass, the labels returned at the end of training do not always match each vector’s exact nearest final centroid. Downstream pipelines that require exact final assignments must run an extra assign pass. Still, the official documentation notes a practical trade-off: under a fixed budget of \(T\) epochs, running e-means for all \(T\) epochs and keeping the last-pass labels usually beats running \(T-1\) epochs and spending the final epoch’s FLOPs on exact reassignment[9].
3. How Do Empirical Scaling Laws Remove Manual Tuning? #
EMA fixes the update rule, but two sensitive hyperparameters remain: batch size \(B\) and peak step size \(\alpha_0\). Requiring a grid search for every new dataset would erase much of the training speedup. The two formulas below recommend \(B\) and \(\alpha_0\) from problem scale alone; practitioners still choose cluster count \(k\), epoch budget \(T\), preprocessing, and the distance metric, and should validate performance on their own data.
Using roughly 75,000 optimization runs on DEEP (spanning 1,399 base configurations, sweeping 8–31 step sizes or 13–20 batch sizes per configuration across 3 seeds each), the authors fit two log-linear power laws from dataset size \(n\), cluster count \(k\), and epoch budget \(T\)[1]:
\[ B\approx 0.035\,k^{0.13}n^{0.88}T^{0.81} \]\[ \alpha_0\approx\min\bigl(0.824\,k^{-0.46}B^{0.90}n^{-0.45}T^{-0.11},1\bigr) \]The predicted \(B\) is rounded to the nearest power of two and capped at the dataset size (tightened to roughly \(n/2\) in the official library). The paper and library distinguish two batch regimes: the default 0.035 coefficient (throughput) is used for \(n\le 2\times 10^6\), whereas larger datasets (\(n>2\times 10^6\)) or low-dimensional inputs (\(d\le 16\)) divide the batch size by 8 (coefficient \(\approx 0.0044\), quality mode). Smaller batches mean more updates per epoch, which can reduce throughput on small datasets; at \(n>2\times 10^6\), however, throughput stays virtually unchanged while out-of-distribution (OOD) MSE regret drops from 0.19% to 0.07%[1][9].
Plugging in the opening retail catalog illustrates the scale immediately. Take \(n=10^7\) product vectors, \(k=65,536\) clusters, and a budget of \(T=3\) epochs. Because \(n>2\times 10^6\), applying the 0.0044 quality-mode coefficient gives:
Substituting \(B=65,536\) into the step law yields \(\alpha_0\approx 0.068\). Across 3 epochs—roughly 152 updates per epoch, or 456 updates total—the step anneals smoothly from 0.068 to 0.0068 without any hyperparameter sweep.
Unlike LLM scaling laws that predict capability ceilings from model scale, these formulas estimate optimizer hyperparameters from problem size and compute budget[1].
4. What Does the 45.5× Speedup Actually Measure? #
4.1 Equal-Error Epochs, CPU Time, and GPU Time #
The paper benchmarks against the test MSE of Flash-KMeans after 25 iterations, measuring how many epochs e-means needs to match or beat that error—comparing time-to-target-quality at a fixed error threshold.
On nested subsets of DINO10B, Table 4 of the paper reports[1]:
| Vectors | Clusters | Epochs | Epoch Cut | GPU Speedup |
|---|---|---|---|---|
| 1M | 16,384 | 2.0 | 12.5× | 12.7× |
| 10M | 65,536 | 1.4 | 17.9× | 23.3× |
| 100M | 262,144 | 1.6 | 15.6× | 31.3× |
| 1B | 1,048,576 | 1.6 | 15.6× | 45.5× |
Note: Source [1], Table 4, measured against Flash-KMeans test MSE at 25 epochs; Epoch Cut is \(25 / \text{Epochs}\). Scales 1M–100M use 1 H100 (10-seed median); 1B uses 8 H100s (single run). The 45.5× figure comes from the 1B subset, not the full 10B run.

Note: Official benchmark figure from the Meta FAIR Faiss repository (MIT license)[9], showing how epoch reduction on DEEP 1M (left) translates into 64-core CPU wall-clock speedup (top right, including SuperKMeans) and single-H100 GPU speedup (bottom right, vs. Flash-KMeans).
Comparing the last two columns separates fewer epochs from faster per-epoch execution. At 1M vectors, the epoch cut (12.5×) and GPU speedup (12.7×) are nearly 1:1. By 1B vectors, the ratio widens to roughly 2.9×—so out of the headline 45.5×, roughly 15.6× comes from fewer passes while the rest comes from per-epoch efficiency (fused kernels, low-precision search, and multi-GPU scaling; this is a rough split because baseline per-epoch cost also varies with scale).
Even without custom GPU kernels, epoch reduction delivers substantial gains: on a 64-core CPU across 11 VIBE datasets, e-means runs 9.0–15.0× faster than Faiss[1], and 11.8× faster than both Faiss and the distance-pruning baseline SuperKMeans on DEEP 1M[1][9]. Separately, e-means eliminates initialization cost—with plain random initialization it beats Lloyd initialized with greedy k-means++, whereas on the 64-core CPU at 1M vectors and 16,384 clusters, k-means++ initialization alone takes 2,852–6,080 seconds, two orders of magnitude slower than e-means training itself (22–72 seconds)[1].
On GPU, frequent mini-batch updates can easily lose speed if intermediate distance matrices thrash memory bandwidth. The authors rely on fused CuTe kernels on H100/H200 GPUs (and Triton kernels on other modern GPUs), combining distance calculation, block-wise top-1 reduction, reduced-precision distance search (BF16, FP8, INT8), and the Euclidean identity:
\[ \|x-c\|_2^2=\|x\|_2^2+\|c\|_2^2-2x^\top c, \]while keeping centroid accumulators and updates in FP32[1][9]. EMA cuts the number of passes over the data; fused kernels convert those saved passes into wall-clock speed. A naive Python loop will not reproduce the paper’s timings.
4.2 Ten Billion Vectors: Exact vs. Approximate Assignment #
The paper scales further to the full DINO10B dataset (10 billion vectors, \(2^{24}\approx 16.77\) million centroids). Under exact nearest-centroid assignment[1]:
| Method | Epochs | GPU-hours | Nodes | Test MSE (×10⁴) |
|---|---|---|---|---|
| Lloyd | 25 | 6,784 | 64 | 12.987 |
| e-means | 2.5 | 779 | 32 | 12.985 |
Note: Source [1], Appendix M, Table 21. Each node has 8 H100 GPUs; lower test MSE is better.
Under exact assignment, e-means consumes roughly 11.5% of Lloyd’s aggregate GPU-hours (an 88.5% reduction, or about 8.7×), which is a resource-consumption ratio. Because the cluster size was simultaneously halved from 64 nodes (512 GPUs) to 32 nodes (256 GPUs), assuming full utilization gives roughly 13.3 hours for Lloyd and 3.0 hours for e-means—a wall-clock speedup of about 4.4×.
With 16.7 million centroids, brute-force assignment dominates runtime. By indexing centroids with an IVF structure during training and streaming vectors from local SSD, e-means matches Lloyd’s test MSE on a single 8×H100 node in 3 epochs and 23.2 GPU-hours (about 3 hours wall-clock)[1]. In Appendix M.4, the authors hypothesize that noise from approximate IVF assignment may act as a regularizer, improving test MSE. Matching Lloyd’s 25-epoch training MSE at 10B scale requires 4 epochs and 43.8 GPU-hours—roughly 1/155 of Lloyd’s 6,784 GPU-hours[1].
Three caveats for the 10B numbers: 8.7× measures aggregate GPU-hours (resource consumption); the 4.4× wall-clock gap assumes cluster size is halved at the same time (64 vs. 32 nodes); and approximate assignment (23.2 / 43.8 GPU-hours) alters the search path, so it should be evaluated separately from exact-assignment speedups.
5. Should You Adopt e-means in Production? #
5.1 Two Engineering Audits: Online Recall and End-to-End Bottlenecks #
The previous section broke down the first two quantities—epoch count and actual compute time. Production adoption depends on the remaining two.
First is online recall. On 11 VIBE retrieval benchmarks, e-means consistently reaches higher Recall@10 for the same training time and matches converged baseline recall in far less build time[1]. Still, production teams must separate clustering MSE (squared distance to the nearest centroid) from retrieval Recall@K (whether queries recover true nearest neighbors). They correlate, yet list imbalance, query distribution shift, PQ/SQ quantization error, and nprobe budgets all sit in between. Compare full Recall–Latency curves on target hardware rather than offline MSE alone.
Second is end-to-end rebuild cost. If an IVF search stack spends most of its rebuild budget on periodic centroid training, e-means offers a clear gain. A complete rebuild pipeline also includes embedding generation, data cleaning, full-corpus assignment, compression encoding, inverted-list writes, and traffic cutover. e-means accelerates only centroid training. By Amdahl’s law, \(\mathrm{Speedup}_{\mathrm{total}} = 1 / \bigl((1-p) + p/s\bigr)\), where \(p\) is the accelerated stage’s share of total runtime and \(s\) is its speedup factor. If centroid training accounts for \(p=30\%\) of rebuild time and all other stages take \(1-p=70\%\), a \(s=10\times\) clustering speedup reduces total runtime from \(1\) to \(0.7 + 0.3/10 = 0.73\)—cutting total rebuild time by just 27% (an overall 1.37× speedup):
\[ \mathrm{Speedup}_{\mathrm{total}}=\frac{1}{0.7+0.3/10}=\frac{1}{0.73}\approx 1.37. \]This is a hypothetical illustration, not a result measured in the paper. Profile every stage before changing solvers. The same boundary applies to RAG systems: with IVF retrieval, e-means can reduce coarse-quantizer training cost; with graph indexes such as HNSW that do not train K-Means centroids, it does not apply. Even with IVF, answer quality still depends mainly on the embedding model, chunking, hybrid retrieval, reranking, and generator model.
5.2 Adoption Path, Validation Checklist, and Open Limits #
e-means ships in the Faiss repository under faiss.contrib.e_means[9]. On CPU, a recent faiss-cpu build runs NumpyEmeans; on GPU, Emeans accepts PyTorch CUDA tensors directly (without requiring a Faiss GPU build), selecting CuTe kernels on H100/H200 GPUs and Triton kernels on A100/B200/RTX 30–40 cards, with spherical=True available for cosine similarity on unit-normalized vectors[9]. Adapted from the official README, this snippet checks the CPU API:
import numpy as np
from faiss.contrib.e_means import NumpyEmeans
rng = np.random.default_rng(42)
X = rng.standard_normal((200_000, 64)).astype("float32")
model = NumpyEmeans(d=64, k=500, nepochs=5) # default 5 epochs; typically matches/beats converged Lloyd on benchmarks, verify on your data
centroids, labels = model.train(X)
print("centroids:", centroids.shape)
print("labels:", labels.shape)
Note: This snippet demonstrates the CPU API and does not reflect fused-GPU-kernel throughput. On GPU, Emeans skips NaN/Inf checks by default; one non-finite value can silently corrupt the centroids. Validate inputs with assert torch.isfinite(xg).all() before training[9].
Before adopting e-means in production, run three controlled checks on your own data:
- Core high-dimensional embeddings: benchmark Lloyd, traditional mini-batch K-Means, and e-means across multiple seeds to verify time-to-target-MSE and run-to-run variance.
- Skewed and long-tail categories: inspect whether small but high-value segments (such as low-volume, high-margin specialty items in retail search) lose centroid coverage under donor splitting—global MSE cannot substitute for minority-group recall checks.
- End-to-end IVF evaluation: hold precision, hardware, initialization timing, and exact vs. approximate assignment constant, then compare Recall@K, P95 query latency, and full index rebuild time.
Two boundaries remain open in the paper:
- Static offline datasets: all evaluations use static offline corpora. Although EMA decays older statistics exponentially, handling continuously shifting streaming data and concept drift still requires explicit sliding windows, resampling, and index version cutovers.
- Empirical scaling-law bounds: the two scaling laws are empirical fits on high-dimensional embeddings. For very low-dimensional vectors, unusual intrinsic dimensionality, extreme cluster imbalance, or non-Euclidean metrics, validate directly on held-out data rather than relying on defaults.
Conclusion #
K-Means is old enough that many engineers treat Lloyd’s algorithm as the standard answer. The lesson from e-means is not a new objective, but a solver rebuilt for modern mini-batch optimization and GPU hardware: EMA fades stale assignments, donor splitting revives dead clusters, and empirical scaling laws remove manual tuning. Together, these changes cut training-stage data scans to roughly one-tenth.
Stepping back, this shift carries distinct implications for engineering teams and researchers:
- For enterprises and engineering teams: full index rebuilds that were once deferred due to compute cost can now keep pace more easily with embedding model upgrades and shifting item distributions. Paired with approximate assignment and SSD streaming, massive-scale clustering also moves down from dozens of GPU nodes to a single multi-GPU server. Even so, adoption comes down to one practical question: is centroid training the slowest, costliest stage in your rebuild pipeline? If it is, run the three checks from the previous section on your own embeddings (or explore the e-means Playground to build geometric intuition, or watch the video walkthrough below); if it is not, impressive single-stage speedups will not translate into proportional system savings.
- For researchers: e-means highlights an underexplored direction—rebuilding classic unsupervised primitives with modern deep-learning tools (stochastic mini-batches, EMA, cosine annealing, fused hardware kernels, and empirical scaling laws) can still unlock order-of-magnitude gains without changing the objective. Natural next steps include extending offline EMA solvers to continuously drifting streaming data, and generalizing tuning-free scaling laws to non-Euclidean metrics, product quantization (PQ), and large-scale training-data deduplication and curation.
References #
[1] Bessa, S., Mazaré, P.-E., Szilvasy, G., Touvron, H., Picard, D., Douze, M., & Jégou, H. (2026). e-means: outperforming k-means (in one-tenth the epochs). arXiv:2611.09501. https://arxiv.org/abs/2611.09501
[2] Yang, S., Xi, H., Zhao, Y., et al. (2026). Flash-KMeans: Fast and memory-efficient exact K-means. arXiv:2603.09229. https://arxiv.org/abs/2603.09229
[3] Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137. https://doi.org/10.1109/TIT.1982.1056489
[4] Meta FAIR. e-means Project Page & Interactive Playground. https://e-means.github.io/ · https://e-means.github.io/playground.html
[5] MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
[6] Sculley, D. (2010). Web-scale K-means clustering. Proceedings of the 19th International Conference on World Wide Web, 1177–1178. https://doi.org/10.1145/1772690.1772862
[7] van den Oord, A., Vinyals, O., & Kavukcuoglu, K. (2017). Neural discrete representation learning. Advances in Neural Information Processing Systems, 30. https://arxiv.org/abs/1711.00937
[8] Douze, M., Guzhva, A., Deng, C., et al. (2024). The Faiss Library. IEEE Transactions on Big Data, 12, 346–361. https://arxiv.org/abs/2401.08281
[9] Meta FAIR. (2026). e-means Reference Implementation & README (faiss/contrib/e_means). GitHub. https://github.com/facebookresearch/faiss/tree/main/contrib/e_means
Further viewing: Video walkthrough (Meta Rewrites K-Means, Cutting Training Epochs to One-Tenth, in Chinese).