So I'll be honest the reason I said this is that I know there are people who are using it and I just assumed it was common :P I will ask if any of them are relying on published work or what for where they got this from.
> In the first figure of the paper, we show that e-means scales up to 10 billion points and 16 million clusters.
Sorry, I should have clarified. I actually think this is what is saving you: with that many clusters, your arithmetic intensity is inherently really high, so you are truly super compute limited. In this case introducing a bit of comms is cheap relative to the bazillion matmuls you're doing for distance calculation. However if you have fewer centroids then the amount of work you do is much lower between updates. As an extreme example, if you're doing hierarchical k-means you might have as few as 2 centroids, which means you barely do any work, and adding any sort of comms just kills you. Of course you are doing very little math but even if you're just looking at memory bandwidth at that point (because your intensity is like 5 FLOPs/byte or something) it will be done too fast.
(I don't actually know how to solve this, which is why I was super excited to see someone else working on this. I agree that your thing works for more centroids, in fact I know it works because I just assumed it was what you were supposed to do, I just couldn't make it work in this situation.)
I'd be very interested if they have a reference. If you feel like it, you can always send me an e-mail at swann@meta.com with the references. I'll add them to my benchmarks.
The fewer centroids case is super interesting. Because we found in our experiments that basically if your n/k ratio (n is the dataset size, k the number of clusters) is high, running the clustering as is on your n points is a waste of resource. You should subsample your dataset such that there is about 250 points per cluster and you will get very similar loss at a fraction of the compute. This is why faiss k-means, by default, subsamples datasets to 256 points per cluster if n/k > 256. So I fully agree with your computational remarks, but I think it's a case that should never happen in practice because subsampling your dataset is the solution in those cases.