Note that BBD-tree is orthogonal to e-means, they can combined very straightforwardly just like it is combined with k-means. The 10x speedup should remain compared to BBD-tree k-means.

So it's not that e-means is better than BBD-tree, it's that you can combine them to make e-means even better, but only at low dimensions and on CPU.

"e-means wins by needing fewer passes over a huge dataset": the improvements of e-means are shown on datasets from 10k up to 10B points (you can try e-means against Lloyd at low problem sizes at https://e-means.github.io/playground.html) so I would not say huge datasets only. It depends on what you call huge obviously, and that's relative.

"It has the same objective and the same optimum, so at best it matches Lloyd." I strongly disagree with that. e-means has the same objective and the optimal clustering is set by the problem, but Lloyd doesn't find this optimal clustering in the vast majority of cases. Lloyd gets stuck in a local minimum, and what we find is that e-means reliably finds better clusterings than Lloyd in terms of MSE, but also other clustering metrics.

Regarding your usecase : I'd be curious to know what settings you used for e-means and a reproduction code. Don't hesitate to send me your code at swann@meta.com, I'm down to have a check because we're confident about e-means' performance against Lloyd.

Edit: in fact you might end up going faster by moving the other way, set alpha = -0.1 and see what happens!

On the topic of these meshes, I'm currently exploring if we can come up with better meshing strategies in data-driven weather models (https://tcumulus.dev/blog/thesis/).

Thank you for trying e-means and detailing your results. This kind of results of e-means at 2 epochs compared with Lloyd is the typical kind of acceleration we want people to know about.

If you have any questions, I’ll be happy to answer.

"People have been doing minibatch k-means for a while, including with an EMA update" : EMA updates are indeed used in clustering, but to our knowledge there is no paper that uses pure EMA updates for k-means clustering on a static dataset. EMA updates are typically used for moving distributions because of their ability to forget the past (as in VQ-VAEs), but their advantage for static datasets had not been empirically demonstrated. If you take a look at appendix E of the paper, we compare EMA to other gradient descent methods and show that EMA is much more stable and has better quality, especially at large batches. Our method also integrates EMA updates in an optimization framework that reliably outperforms Lloyd and previous mini-batch methods.

"the contribution here is that they tried to measure how much better it is": The contribution here is to integrate EMA updates in an optimization framework to provide a method as robust and performant as we could. If you look at previous mini-batch k-means papers, the speedups and the performance is nowhere nearly as good as e-means, which beats Lloyd at 25 epochs in 2 to 3 epochs. In fact, mini-batch k-means is known in the literature as a fast method but with lesser convergence than Lloyd, and we compare to them in Figure 3. The e-means framework allows to be both faster and have better convergence than Lloyd, without the user having to tune the batch or the step.

"How your algorithm scales as more data is present": In the first figure of the paper, we show that e-means scales up to 10 billion points and 16 million clusters.

On communication: workers only exchange per-update statistics (K×d numbers with replicated centroids). You argue that bigger batches have diminishing returns, so that extra local work doesn't cut the number of updates. But that's precisely what our batch law addresses: it returns the largest batch whose loss stays within ~0.2% of the best loss at a fixed number of epochs. In other words, we carefully scale the batch size to avoid that our speedups are driven down by the diminishing returns you mention.

The multi-node regime is in the paper: the 10B run used 32 machines, so synchronization went over the inter-node network, and the bottleneck was still the distance computation, not communication. That's also why an IVF variant, which cuts distance computations, does it in ~23 GPU-hours.

The fact that the update rule keeps the centroid within the convex hull is indeed very important. If you look at Appendix E, the gradient descent methods don't have this property and are less stable than EMA updates.

Regarding simulated annealing, I agree with the parallel. You can see mini-batches as introducing noise in the beginning of the optimization to espace local minima and the step size decreasing through the training acts like a temperature in simulated annealing. Simulated annealing was already used for k-means with theoretical proof that you can reach the global minimum in enough epochs, but in practice, those methods are really slow. A paper that comes to mind is "A simulated annealing algorithm for the clustering problem" (https://www.sciencedirect.com/science/article/pii/0031320391...).

The parallel with expectation maximization is also coherent, though less straightforward to me. K-means can be viewed as a hard-assignment, special case of the Expectation-Maximization algorithm applied to Gaussian Mixture Models (GMMs).

If you have any other questions, I'll be happy to answer.

There's still not one particularly great way to pick k for this type of clustering. There kind of can't be as clustering is sort of inherently subjective.

Other methods like HDBSCAN can find the number of clusters themselves. There's still a 'one key parameter' you have to pick yourself, but it can be more intuitive and less sensitive for some datasets, when you don't know how many clusters there are / how many you want.

Sometimes, picking k exactly is useful for practical reasons too. Like fixing the size of your codebook. Or partitioning a dataset into k equal-ish pieces, say to spread across a pool of servers of a known/fixed size.

[1] https://en.wikipedia.org/wiki/Elbow_method_(clustering)

When I was just starting out, client-server was still a bit of a specialty, mostly reserved for gaming and large institutions. Most of my education was in single task computing. If the university hadn’t offered a class in distributed computing I wouldn’t have gotten much in that direction except in independent study.

In the time since then, we seem to have focused much less on seconds per task and more on tasks per second, which results in more concern about statistical spreads, and queuing mechanisms to manage the variability between a hit and a miss. It would be better if this sort of computation were more organized into a discipline.

If you look at our paper on arxiv (https://arxiv.org/abs/2611.09501), Table 2, the hyperparameters laws have been validated on 4 datasets outside of the fit, but also on scales outside of the fit. There the hyperparameters they picked made the loss only 0.07% worse than the best hyperparameters possible on average. The robust results in the paper, which are on 26 different datasets where e-means beats Lloyd by a wide margin, are also a proof of the generalization of our scaling laws.

You want to assign things to a set of clusters so that things that share similar properties are grouped closely together. But, we also want those clusters to be as big as possible. We don't want to leave little islands that only have a few things in them.

Take, for example, classification of email messages. Let's say you have a billion email messages and you want to find a way to cluster them automatically into 10 categories. You don't know what the categories are ahead of time. You just have a way of making sure that an email can be represented by a vector of numbers such that two emails that are close together in their meaning and characteristics will have similar numbers.

K-Means clustering solves that problem but is intractable to calculate for large datasets having high dimensionality (such as the email example). My understanding is that E-Means is away to achieve this spectacularly more efficiently than the best alternative previously known.

Impressive results ...

If you want, you can also play with it now in your browser at : https://e-means.github.io/playground.html

Feel free to ask any questions, I'll be happy to answer.

The goal of e-means is to be a drop-in replacement for k-means. It solves the exact same problem, with the exact same inputs and delivers better centroids and quality in a fraction of the time. So I'm not sure what we get wrong by working on a problem that hundreds of papers also worked on. Is the whole k-means literature getting it wrong then ?

Picking the k is a separate problem, on which also a body of literature has worked too. e-means is a drop-in replacement for k-means so you can use any method you would use for choosing the k but with e-means instead of k-means.

e-means performs better on a very wide array of datasets, definitely not degenerate cases, don't hesitate to check out our paper at https://arxiv.org/abs/2611.09501.

If you have any question or objection, I'll be happy to answer.