SuperEMeans:当两种聚类优化相遇,3×加速没有质量妥协

原创
alex 3小时前 阅读数 3 #头条

SuperEMeans:当两种聚类优化相遇,3×加速没有质量妥协

背景:e-means 凭什么成为聚类领域的“当红炸子鸡”

做向量搜索的人大概都听过这句话:在你发出相似性查询之前,必须先等聚类跑完。聚类是 IVF 和 ScANN 这类大规模向量索引的关键构建块,它决定了索引建好后能不能快速响应,也决定了建索引要花多久。这个瓶颈在最近一年被反复冲击:EVōC、SuperKMeans、QGKmeans,再到上周的 e-means、o-means、s-means,一批方法冒出来,目标都是把聚类变快。来源:HH

e-means 的卖点很直接:传统上,向量嵌入的聚类标准化为 10 个 epoch,而 e-means 承诺用 2 个 epoch 就达到 Lloyd 算法同样的聚类质量。这个数字让人没法不盯着看。它意味着聚类等待时间理论上可以砍掉五分之四,而且不牺牲质量。来源:HH e-means 的作者还专门做了展示网站,把原理、实验和结果都摊开给人看,链接在论文里,也在我写这篇博客时反复翻过的那个站点上。来源:HH

一年前我们发布了 SuperKMeans。它走的是另一条路:通过避免扫描向量维度来加速 Lloyd 的 k-means,加速比是 2 到 10 倍,同样不牺牲聚类质量。这个办法已经被工业界迅速采纳,ParadeDB、Zilliz、FAISS 都在用,说明改进高维向量聚类性能确实正当时。来源:HH 我常想,一个算法能不能被广泛接受,往往不在于它多花哨,而在于它是否真的解决了别人手头的痛。SuperKMeans 被这么快采用,大概就是因为它解决了实实在在的瓶颈。

有趣的是,e-means 的作者在他们的论文里明确写了这样一句:SuperKMeans 的维度剪枝思想与 e-means 是正交的。我们读了之后深表赞同,这两种想法之间没有任何对立之处。一个从维度上省力,一个从 epoch 上省力,方向不同,却指向同一个目标——更快地把聚类做完,且不牺牲质量。来源:HH 于是我们自然而然地动了手。

实验:当剪枝维度遇上减少 epoch,3× 加速如何达成

我们扩展了自己的聚类库,把 e-means 和融合版本 SuperEMeans 都实现了进去,代码已经开源在 GitHub 仓库 cwida/SuperKMeans。实验用的数据集有两个:一个是 VectorDBBench 基准里的 5M 个 1536 维 OpenAI 嵌入向量,27GB;另一个是 MS MARCO 的前 10M 个段落,用 Cohere Embed V3 模型嵌成 1024 维向量,40GB。来源:HH 索引方面,我们建 IVF,点与簇的比例是 1:256,OpenAI 数据集大约 20,000 个质心,Cohere 数据集大约 40,000 个质心。硬件是一台 Zen 5 机器,具体配置没有在博客里细说,但实验的复现脚本都放在仓库里,想验证的人可以自己跑。来源:HH

结果就是 TL;DR 里那句话:融合后的 SuperEMeans 让高维向量的聚类速度提升 3 倍,且没有质量权衡。来源:HH 我们分别独立实现了两个算法,各自测了贡献,再把它们合而为一。分开测的时候,SuperKMeans 的维度剪枝有它自己的加速幅度,e-means 的减少 epoch 策略也有它自己的加速幅度,合起来并不是简单相加,但确实达到了 3 倍的整体加速。来源:HH

这 3 倍不是拍脑袋出来的。我们做了完整的基准,在 5M OpenAI 嵌入和 10M MS MARCO 段落上都测了。质量方面,聚类质量没有下降,具体来说就是聚类结果与 Lloyd 基准的质量相当。我没有在博客里看到逐点对比的细表,但作者明确写了“没有质量权衡”。这个说法我倾向于相信,因为如果质量有损,一个标榜“无妥协”的工作不会这么写。当然,如果你要复现,仓库里的代码可以自己跑。来源:HH

交叉验证:多源观点如何共同指向“正交融合”这一结论

这个工作最让我觉得有意思的地方,是它直接回应了 e-means 作者关于正交性的建议。e-means 的作者说 SuperKMeans 的剪枝与 e-means 正交,我们同意,然后就把这个同意变成了代码和可复现的实验。来源:HH 在学术圈里,这种“你提个建议,我接过来做成实验”的链条并不常见,更多时候是各说各话,或者等到综述里才被拼在一起。这里不是,这里是真的把两个想法融合了,然后测出了结果。

e-means 作者的官网强调,只需 2 个 epoch 即可达到传统 Lloyd 的质量,这与 SuperKMeans 的作者从维度剪枝切入形成互补。来源:EMEANS 两个算法都旨在加速 k-means,但通过完全不同的路径实现。这个判断具有某种反直觉性:通常我们会以为,两个加速同一个算法的方法,要么是竞争关系,要么一个包含了另一个。但这里它们互不排斥,甚至可以说互相成就。来源:HH 我不确定这种正交性在更复杂的场景下是否依然成立,比如当维度更高、簇数更多、或者数据分布更不均匀的时候,但至少在这两个数据集和这个索引配置下,实验证实了这一预判。

工业界的采纳也提供了外部佐证。ParadeDB、Zilliz、FAISS 都在用 SuperKMeans 的维度剪枝,说明这个方向是有效且可落地的。来源:HH 而 e-means 的 2 epoch 承诺,如果同样被证明可落地,那么两者的融合就是自然且必要的下一步。我写这篇博客的时候,e-means 的展示网站上还放着一句“用 2 个 epoch 达到 Lloyd 的质量”,我没有看到他们更新过关于融合版本的声明,但这不影响这里的判断:既然两个思想正交,将它们融合是自然且必要的下一步。来源:HH 至于融合之后能不能在更多数据集上保持 3 倍,我不确定,但仓库里的代码已经准备好了,跑一下就知道。


原文:

SuperEMeans: Making e-means 3× faster · 来源:Hacker News

作者:itfan123 值班编辑 · 发布于 2026年11月19日

版权声明

所有资源都来源于爬虫采集,如有侵权请联系我们,我们将立即删除