E-means speeds up clustering in tests on image and text vectors

The same goal, a different update rule

Clustering sorts numerical data points into groups around representative centers, called centroids. In k-means, the goal is to minimize the average squared distance between each point and its nearest centroid. This measure, mean squared error, describes how closely the centers represent the data.

The standard Lloyd algorithm alternates between assigning every point to its closest center and moving each center to the average of its assigned points. Each such iteration requires a full pass over the dataset. The method reaches a local minimum, rather than necessarily finding the best possible grouping.

In a preprint posted on November 6, 2026, Swann Bessa and colleagues at Meta’s FAIR and École Nationale des Ponts et Chaussées describe an alternative called e-means. It tackles the same clustering objective but updates centers repeatedly within each pass, using smaller batches of points.

Remembering recent batches

E-means maintains a running count and coordinate sum for each cluster. These statistics use an exponential moving average: older contributions gradually lose weight as new batches arrive. Dividing the sum by the count gives the cluster center.

The researchers combine that familiar technique with several changes. Updates become more conservative during a run, helping centers settle. Every five batches, the algorithm checks for clusters receiving very little data and revives them by splitting a populated donor cluster. Tests removing individual components identified this revival strategy as particularly important.

A final step averages the points assigned to each cluster during the last pass. This targets training error at little additional computational cost. The paper also explores a separate, slower moving average that can improve performance on previously unseen points, trading some training accuracy for better generalization.

To avoid requiring users to search manually for suitable batch sizes and update settings, the authors fit formulas using roughly 75,000 optimization runs on one image-descriptor dataset, DEEP. The formulas depend on dataset size, cluster count and the planned number of passes. They then tested how well those rules transferred to other datasets.

Fewer passes, shorter runtimes

The evaluation covered image and text vectors, including SIFT, SPACEV, SimSearchNet++ and DINO10B. The main scoring measure was error on held-out vectors, not just the points used to fit the centers.

In the paper’s main speedup table, e-means took 1.4–2.6 passes to drop below the held-out error reached by Flash-KMeans after 25 iterations. Measured runtime improvements ranged from 9.5-fold to 45.5-fold on H100 GPUs. Results through 100 million points used ten random seeds; the billion-point results used one.

The advantage was not limited to reaching a fixed target sooner. In eight reported configurations, five passes of randomly initialized e-means produced lower median test error than 25 iterations of Flash-KMeans using greedy k-means++ initialization. Those quality improvements were relatively small: approximately 0.06%–0.33%.

At the largest scale, the team grouped 10 billion DINO image-patch vectors into 16,777,216 clusters. With exhaustive centroid comparisons, e-means beat the 25-pass Lloyd test-error benchmark in 2.5 passes. An approximate-search variant reached that target on one eight-GPU machine in about three hours. That variant avoids comparing every point with every centroid, adding a separate acceleration beyond the update rule itself.

Where the evidence stops

These are preprint findings, not a universal guarantee that e-means will outperform other clustering methods. The automatic parameter rules were developed for relatively high-dimensional vectors; the authors explicitly say they are not optimal for very low-dimensional or tiny datasets.

The benchmark target also matters. Matching Lloyd after 25 passes is a defined comparison, not proof of finding the globally best clustering. Separate convergence experiments support lower final errors on selected datasets, but cannot establish that result for every distribution.

Likewise, approximate assignment affects training and test error differently. Its headline large-scale savings use held-out error as the target; matching the baseline’s training error requires more work. Some synthetic experiments also showed test error rising with longer training despite improving training error.

Finally, the measured GPU speedups reflect particular hardware, numerical precision and implementations. The evidence supports a faster route to low clustering error in the tested vector datasets—not an equivalent improvement in every downstream application.