e-means: A Faster k-means Variant and the Jevons Paradox of Cheaper Clustering

e-means is a new k-means variant that updates centroids continuously within each pass using mini-batches and exponential moving averages, reaching the test loss of full-batch k-means in 2.5 epochs instead of 25 on 10 billion DINO embeddings clustered into roughly 16.7 million clusters. It keeps the same objective and convex nearest-centroid geometry, with fitted scaling laws setting batch size and update rate automatically. The author argues cheaper runs mean trying more values of k rather than lower compute bills.