e-means: 10x Faster K-Means Clustering via Exponential Moving Averages

Core Innovation: Exponential Moving Averages for K-Means

e-means is a modern optimization approach for the K-means problem that replaces the traditional Lloyd's algorithm update rule with mini-batch updates based on exponential moving averages (EMA). By tracking recent assignments rather than the full historical mean, e-means reaches test loss targets in 1.2 to 3 epochs, compared to the 25+ epochs typically required by Lloyd's algorithm. This results in a 10–45x wall-clock speedup on GPU and 8–15x on CPU.

Why EMA Outperforms Traditional Updates

Traditional K-means (Lloyd's) uses full-batch updates, which are computationally expensive and prone to getting stuck in local minima. While mini-batch variants like MacQueen's update exist, they often suffer from instability or poor convergence. e-means uses an EMA update rule:

  • $S_j \leftarrow (1-\alpha)S_j + \alpha s_j$
  • $N_j \leftarrow (1-\alpha)N_j + \alpha n_j$

This approach ensures that centroids track recent data distributions while forgetting stale assignments. Unlike gradient descent-based updates, which can overshoot the convex hull of the assigned points, EMA updates are inherently stable. This stability allows for higher learning rates and faster convergence without the need for manual hyperparameter tuning.

Automatic Hyperparameter Scaling

A primary advantage of e-means is the elimination of manual hyperparameter tuning. The researchers derived scaling laws that automatically determine the optimal batch size ($B$) and step size ($\alpha_0$) based on the dataset size ($n$), number of clusters ($k$), and target epochs ($T$). These laws allow the algorithm to generalize effectively across different problem scales without requiring users to perform grid searches.

Improved Robustness and Dead-Cluster Revival

e-means demonstrates superior ability to escape local minima compared to Lloyd's algorithm. By utilizing noisy mini-batch updates, the algorithm explores the optimization landscape more effectively. Additionally, e-means implements a "proportional split" strategy for dead-cluster revival, where clusters with insufficient points are revived by splitting large, active clusters. This approach significantly outperforms simple resampling methods, ensuring the full capacity of the codebook is utilized.

Practical Considerations and Limitations

While e-means provides significant speedups for large-scale clustering tasks, its performance depends on the specific use case. Community feedback highlights that the algorithm is best suited for scenarios involving large datasets where mini-batch sampling provides a representative approximation of the global distribution. For geometric tasks—such as relaxing meshes on a sphere where centroids can be computed analytically—the overhead of mini-batch sampling may not provide a benefit over direct geometric computation.

"e-means wins by needing fewer passes over a huge dataset, but relaxing a mesh on a sphere has no dataset: each Voronoi cell’s centroid can be computed directly from its geometry. Mini-batches just swap that for a noisy sampled estimate of the same thing." — Hacker News user jlhawn

Furthermore, critics note that at extreme scales, communication overhead for parallel updates can become a bottleneck. The effectiveness of the algorithm relies on balancing local computation with the cost of synchronizing partial updates across workers.

Implementation

The e-means implementation is available as a contribution to the Faiss library. It provides both NumPy and PyTorch-based interfaces, allowing for seamless integration into existing machine learning workflows.

Sources

Related

  • Dispatch
    Qwen Global-Batch Load Balance for MoE LLM Training

    Qwen introduces a global-batch load balancing loss that improves MoE model performance and enables expert specialization by calculating balance across the entire global batch rather than individual micro-batches.

  • Project
    RobertTLange/evosax

    evosax is a JAX‑based library that implements 30+ Evolution Strategies (e.g., CMA‑ES, OpenAI‑ES, ARS, SimpleGA) with a vectorised `ask‑eval‑tell` API, enabling fast, hardware‑accelerated black‑box optimisation for neuro‑evolution, RL, and hyper‑parameter search.

  • Dispatch
    Evolution Strategies as a Scalable Alternative to Reinforcement Learning

    OpenAI researchers demonstrate that Evolution Strategies (ES) can rival the performance of standard reinforcement learning on Atari and MuJoCo benchmarks while offering superior scalability and simpler implementation.

  • Dispatch
    Mixture of Experts (MoE) Explained

    Mixture of Experts (MoE) allows transformer models to scale parameters while maintaining efficient pretraining and faster inference by activating only a subset of neural network experts per token.

  • Dispatch
    DeepSeek-V4.1-Flash-1017: Benchmarks, Prompt Encoding, and What Hacker News Users Reported

    DeepSeek-V4.1-Flash-1017 is a minor update to DeepSeek-V4.1-Flash that posts large gains on reasoning, coding, agentic, and vision benchmarks while cutting execution time and output length, and it ships without a Jinja chat template in favor of a Python reference encoder and the Rust-based deepseek-recipe toolkit.