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.
They created this in service of their video generation model which "clusters and reorders tokens based on semantic similarity using k-means.":
http://arxiv.org/pdf/2505.18875
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.
search trees tend not to scale well to higher dimensions though, right?
from what I've seen I had the impression that Yinyang k-means was the best way to take advantage of the sparsity.
looks like flash attention concepts applied to kmeans, nice speedup results