@_avichawla: 研究人员将KMeans提速200倍。这一新技术也超越了cuML和FAISS等方法。Flash-KMeans是一种…

研究人员将KMeans提速了200倍。

这项新技术也超越了cuML和FAISS等方法。

Flash-KMeans是对精确KMeans的一种IO感知实现，它围绕现代GPU的瓶颈重新设计了算法。

通过直接攻破内存瓶颈，Flash-KMeans实现了：

• 相比cuML提速33倍
• 相比FAISS提速200倍

这一加速效果得益于它在GPU内存中的数据移动方式。

标准的KMeans分两步运行，而这两步都受限于对GPU内存的读写：

1. 第一步是将每个点匹配到最近的质心。

标准KMeans会计算完整的点到质心距离矩阵，将其写出到GPU内存，然后再读回来找到每个点的最近质心。这个先写后读的往返过程就是瓶颈所在。

Flash-KMeans将距离计算与最近质心步骤合并，结果在片上计算完成，完整的矩阵从不写出。

2. 第二步是通过对分配到每个质心的点求平均来重新计算质心。

标准KMeans有成千上万个线程同时写入同一个质心槽位，导致它们需要等待轮流写入。

Flash-KMeans首先按簇对点进行排序，将散乱的写入转变为顺序规约，从而在一次高效扫描中完成内存读写。

利用这两项优化，在百万级数据规模下，Flash-KMeans能够在几毫秒内完成一个标准KMeans迭代。

下面的视频展示了实际运行效果。

以下是这一成果重要的几个原因：

KMeans历来是一种离线原语——一次性用于预处理数据，然后继续下一步。

而这样的提速使其在多个运行时关键系统中变得可行。

↳ 像FAISS这样的向量索引使用KMeans来构建搜索索引。更快的KMeans意味着你可以在数据变化时动态重建索引。

↳ LLM量化方法需要KMeans来逐层反复寻找最优权重码本。原本需要数小时的任务现在可以缩短到几分钟。

↳ MoE模型在推理时需要进行快速的令牌路由。Flash-KMeans使得在推理循环内运行这一操作成为可能，而不仅限于预处理阶段。

论文链接已分享在回复中。

也就是说，内存是Flash-KMeans真正解决的问题，而这个问题并不仅限于聚类。RAG系统在索引后存储的向量也会造成类似瓶颈。

我最近写了一篇详细指南，介绍如何通过二进制量化将向量内存占用缩减32倍，并在几毫秒内查询超过3600万个向量。

请往下阅读。

Flash-KMeans GitHub仓库 → http://github.com/svg-project/flash-kmeans…

（别忘了给星星⭐）

大多数生产系统都遵循类似的策略。

和FlashAttention的故事如出一辙。我之前在这里介绍过：

@_avichawla 哇，200倍？太猛了。好奇这对实时数据处理有什么影响。看来GPU有了新朋友！