tl;dr: E-means replaces Lloyd's full-batch k-means updates with mini-batch exponential moving average updates (borrowed from VQ-VAE training), reaching Lloyd's 25-epoch loss in 1.2–3 epochs, yielding 10–45× GPU and 8–15× CPU wall-clock speedups. It requires no hyperparameter tuning—batch size and step size are set via fitted scaling laws—and adds cosine-decayed step sizes, improved dead-cluster revival via splitting large clusters, and a finalization stage. The authors attribute the quality gains to noisier mini-batch updates better escaping local minima; code ships in Faiss as `faiss.contrib.e_means`.