認識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的顯著加速，為需要頻繁聚類的新興應用提供了實用工具。