Hi, I'm Swann Bessa, the author of e-means. Thanks for trying e-means. If I may I'd like to come back on a few of the points you made.

"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.

Since it's basically a linear interpolation between Lloyd's algorithm and not moving any points it will be at least as good but gains might be limited without careful tuning.

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

Your website looks incredibly interesting! Very exited to read it when I have time. When you mentioned icosahedral meshes, I immediately thought it would be related to weather/climate modeling :D.

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/).

Hi, I’m the author of the paper.

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.

BBD-tree is only for low dimensions because it suffers from the curse of dimensionality.

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.

Thank you for trying e-means, let me know if you have any questions !

https://XNotMe.com/swann_bessa/status/2120200714630594911?a=...

Hi saagarjha, I'm Swann Bessa, the author of the paper. Thank you for your message on the work. If I may I'd like to address a few points.

"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.

Yeah most of these tricks are already well established. And their own ablations show that combining them doesn’t bring any special synergy - it’s just putting together a lot of common techniques. The baselines also are tough to believe fully. Comparing against faiss is fair since many authors are faiss contributors so they know how to run it. But they don’t and should include a comparison to a well tuned mini batch kmeans like the one in scikit.

The automatic hyperparameter laws don't seem intuitive to me yet. Do you have any intuition for it?

Hi shiandow, I'm Swann Bessa, the author of the paper.

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.

The 'Elbow method' [1], yeah. Sweep a bunch of different k values and pick the one where your target metric starts having diminishing returns. There are a lot of heuristics you could use.

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)

You could use X-means instead (https://www.cs.cmu.edu/~dpelleg/download/xmeans.pdf). The idea is to use an information criterion that trades the number of parameters against the reduction in within-cluster variance. The approach essentially splits a cluster when the BIC of the split is larger than without. I’d use this to select k and still run normal k-means though.

There isn’t a well defined correct or ideal answer. It depends on what you’re doing with the clusters. Sometimes the raw data are too numerous to properly deal with and you just want a smaller set of points to reason about. In that case pick the number of points that are convenient to reason about. Sometimes you have a fixed budget for the cluster representation and that defines k. Sometimes just pick sqrt(N) so the average cluster size is k.

The best class of algorithms in this category are those where you know for certain that one answer is impossible and the other is highly probable. Like Bloom Filters, and if you squint, consistent hashing. I wish we had more algorithms of this sort and books about them. If I were a professor I’d be tempted to propose teaching a class.

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.

The entire field of operations research is essentially founded on the premise that NP hard is just a starting place.

If anything, NP hard problems are usually the ones worth tackling.

It's not a new kind of clustering. It solves exactly the same problem as k-means (minimize the mean squared distance to k centroids), returns the same thing (k centroids and an assignment), and has the same inputs (k and a number of epochs). The batch size and step size are set automatically, so there's nothing extra to tune. So it is a drop-in replacement for k-means specifically: in Faiss it's Emeans(d, k).train(x) where you'd call Kmeans(d, k).train(x). The code is in faiss at https://github.com/facebookresearch/faiss/tree/main/contrib/...

Hi, I'm the author of e-means. If you can send them, I would love to hear about the results you got !

Hi bashhq_r, I'm Swann Bessa, the author of the e-means paper.

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.

Let's say you have a way of encoding the properties of something using a vector of numbers. But two things might be very similar and yet still produce vectors that are not identical to each other. Indeed, the vectors are nearly guaranteed to always be at least slightly different. Also, assume there are a large number of dimensions.

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.

It's clustering. You have a bunch of data points and you want to group them into k clusters such that all the data points in a cluster are similar. Like dividing customers into high/medium/low spenders, or whatever (usually you'd have more dimensions than 1D though).

Faster vector calculations. What help for example, helps with ivfflat or prism index building. It cut CPU (or GPU) usage, and time needed to build. Seen index build times drop by 50 to 80%, and at the same time CPU usage drop by 50%.

Impressive results ...

Minimizing Mean Squared Error between a dataset and a given number of centroids. In practice it can be used in deduplication, data curation, compression, Vector Search, and many others. It remains one of the most used Machine Learning algorithms in the world.

Hi, I'm Swann Bessa, the author of the paper.

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.

Hi, I'm Swann Bessa, the author of the e-means paper. FYI, we get very good results on ARI and NMI on ImageNet and also synthetic data. We will release them in a later revision. If you have another distribution you have in mind for us to test, I would be glad to run it as well.

I feel like they cover that, a bit, with both explicit examples and the quality curves, right?

Hi Thomashuet, I'm Swann Bessa, the author of e-means.

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.