認識Flash-KMeans：一個IO感知的精確K-Means，在GPU上比FAISS快200倍以上

Flash-KMeans 是由加州大學伯克利分校和德克薩斯大學奧斯汀分校的研究團隊發佈的開源庫，旨在解決現代AI流水線中K-Means頻繁調用帶來的延遲瓶頸。傳統的K-Means通常作為離線工具使用，但如今在訓練和推理循環中頻繁調用，因此每次調用的延遲比理論FLOPs更重要。

Flash-KMeans 是標準Lloyd K-Means的IO感知實現，它不改變數學或近似，僅重構算法在GPU上的數據流。在NVIDIA H200上，研究團隊報告了高達17.9倍的端到端加速，對比NVIDIA cuML快33倍，對比FAISS快200倍以上。

Flash-KMeans 的核心創新包括兩個關鍵內核：FlashAssign 和 Sort-Inverse Update。FlashAssign 受FlashAttention啓發，將點和質心分塊從HBM流式傳輸到片上SRAM，融合距離計算與在線argmin，避免物化完整的N×K距離矩陣。這使分配階段的IO複雜度從O(NK)降至O(Nd+Kd)，分配內核速度提升高達21.2倍。

Sort-Inverse Update 針對質心更新階段的原子競爭問題，通過argsort將分配向量按簇ID排序，形成連續段。每個線程塊在片上規約一段，然後每段僅執行一次原子加操作。這使更新內核速度提升高達6.3倍。

基準測試在H200上進行，FP16數據，維度d=128，對比fast_pytorch_kmeans、fastkmeans、cuML和FAISS。端到端速度提升最高17.9倍（N=8M，K=1024），分配內核21.2倍，更新內核6.3倍。外核模式下，對10億個點（K=32768，d=128）每次迭代僅需41.4秒，而基線需261.8秒。

Flash-KMeans 還包含緩存感知編譯啓發式，將調優開銷降低175倍，同時保持接近最佳性能。該庫已開源，採用Apache 2.0許可，可通過 pip install flash-kmeans 安裝。

使用場景包括：向量搜索索引構建、稀疏注意力路由、KV緩存壓縮、低比特KV量化、擴散Transformer等。API與faiss和sklearn類似，支持批處理和多GPU。

總之，Flash-KMeans 通過GPU數據流優化實現了精確K-Means的顯著加速，為需要頻繁聚類的新興應用提供了實用工具。