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.