Flash-KMeans: Fast and Memory-Efficient Exact K-Means
https://arxiv.org/abs/2603.09229They created this in service of their video generation model which "clusters and reorders tokens based on semantic similarity using k-means.":
Nice one. K-Means is one of those neat little powertools that once you get the hang of it you find more and more applications for, but it can be a bit slow for larger data sets. So this is very nice to have, thank you matt_d for posting.
Do they mean deterministic k-means, k-means++ ... ? Global optimal k-means is NP-Hard, so linear speedups aren't terribly helpful. It's nice, until you add more input. Standard k-means would be nice, or the k-means++ seed algorithm.
loading story #47455737
Does this have corresponding speed ups or memory gains for normal CPUs too? Just thinking about all the cups of coffee that have been made and drunk while scikit-learn kmeans chugs through a notebook :)
For CPU with bigger K you would put the centroids in a search tree, so take advantage of the sparsity, while a GPU would calculate the full NxK distance matrix. So from my understanding the bottleneck they are fixing doesn't show up on CPU.
loading story #47453530
loading story #47453806
looks like flash attention concepts applied to kmeans, nice speedup results
[dead]