e-means hits Lloyd's 25-epoch loss in 1.2 to 3 epochs, 10-45x faster on GPU
- Across a wide range of scales and datasets, e-means reaches the test loss Lloyd hits at 25 epochs within 1.2 to 3 epochs, which works out to a 10-45x wall-clock reduction on GPU against Flash-KMeans and 8-15x on CPU against Faiss.
- The core change is the centroid update: instead of recomputing sums from scratch over the full dataset as Lloyd does, e-means keeps an exponential moving average over mini-batches, S_j = (1-alpha)S_j + alphas_j, with the step annealed on a **cosine schedule from alpha0 to 0.1alpha0**.
- Batch size and step size are set automatically from scaling laws on log n, log k and log T, so the method needs no hyperparameter tuning, unlike earlier mini-batch k-means built on MacQueen's 1967 update rule.
- The project adds novel initialization, dead-cluster revival that splits an oversized cluster when another falls below a size threshold, a finalization stage that ends each run on the cluster's exact last-epoch mean, and fused GPU kernels that turn epoch savings into wall-clock savings.
- Hacker News commenters report mixed results: one adapted it to an IVF index for a 146x GPU speedup, while another found it slower and noisier on icosahedral mesh relaxation, where each Voronoi centroid is computed directly from geometry and there is no dataset to subsample.
Hacker News 의견들
This looks awesome, and obvious in hindsight. The viz really sells it. I hope scipy picks it up, it's way easier to get than faiss in most environments.
The automatic hyperparameter laws don't feel intuitive to me yet. Do you have any intuition for where they come from?
I adapted the method to my IVF index and got a 146x speedup on the GPU. That's wild for what amounts to a drop-in change.
Great example of why P=NP is sometimes the wrong question. For this NP-hard problem approximate answers are good enough, and 45x faster approximate answers are even better.
The best algorithms in that class are the ones where you know for certain one answer is impossible and the other is highly probable, like Bloom filters. I wish there were more of them, and more courses teaching them.
Operations research has been built on the premise that NP-hard is just a starting place for decades now.
The epoch reduction is cool, but the hyperparameter laws feel like they were fit post-hoc to me.
Tried it on my hobby project that relaxes an icosahedral mesh on a sphere. Definitely not better there. e-means wins by needing fewer passes over a huge dataset, but a sphere mesh has no dataset, each Voronoi cell centroid comes straight from its geometry. Mini-batches just swap that for a noisy sampled estimate, and in practice it was slower, left the grid noisy, and tangled the mesh at small sample budgets.
It's basically a linear interpolation between Lloyd and not moving any points, so at best it matches. Try alpha = -0.1 and see what happens.
These algorithms usually have an equivalent description as expectation maximisation or simulated annealing. Probably EM with a friction term, since the update is S_j = s_j - a(s_j - S_j). They do note the centroid stays inside the convex hull, which matters.
Layman question: what is this actually used for in practice?
Faster vector index builds. It cuts CPU and GPU time for IVF-style indexes, I've seen build times drop 50 to 80% with CPU use down by half.
Clustering. You have a pile of points and you group them into k groups so similar points land together. Customer segments, email categories, that kind of thing.
The one hyperparameter left is k. Is the elbow method still the answer, or is there something better now?
Still elbow sweeps and heuristics. There's no great way to pick k because clustering is inherently subjective. HDBSCAN finds the count itself, and sometimes you want a fixed k anyway, for a codebook or for sharding across a fixed pool of servers.
What impresses me is that it doesn't split one blob into two centroids or merge two blobs into one. The noisy mini-batch updates explore more and escape local minima, which makes sense and shows this isn't settled.