Newshot

SuperEMeans:让 e-means 提速 3×

Translation(model translation, not the source's own text)
SuperEMeans: 让 e-means 提速 3 倍
SuperEMeans: 让 e-means 提速 3 倍
TL;DR:我们将 SuperKMeans 与 e-means 融合,实现了高维向量聚类的 3 倍加速,且无质量损失。现已在 https://github.com/cwida/SuperKMeans 提供。

最近,向量嵌入的聚类领域热闹非凡:EVōC、SuperKMeans、QGKmeans,以及就在上周出现的 e-means、o-means 和 s-means。其中,e-means 是件大事:它承诺只需 2 个 epoch 就能达到与 Lloyd's 相同的质量。为什么这对向量搜索来说是件大事?

嗯,聚类是大规模向量索引(例如 IVF、ScANN)的关键构建模块,而这恰恰是用户在发起相似性搜索查询之前不得不等待的瓶颈。

一年前,我们发布了 SuperKMeans。SuperKMeans 通过在聚类时避免扫描向量维度,将 Lloyd's k-means 加速 2—10 倍,且不以聚类质量为代价。SuperKMeans 已被业界迅速采用(ParadeDB、Zilliz、FAISS),这表明改进高维向量聚类性能是多么及时。然而,e-means 同样令人兴奋,因为它通过运行更少的 epoch 来减少计算量。传统上,向量嵌入的聚类被标准化为 10 个 epoch。而 e-means 承诺仅用 2 个 epoch 就能达到相同(或更好)的聚类质量。我推荐大家去看看 e-means 作者制作的精彩网站:https://e-means.github.io/

有趣的是,在他们的论文中,作者提出 SuperKMeans 的维度剪枝思路与 e-means 是正交的。我们同意:这两个想法之间没有任何相互对立之处。自然而然,这让我们开始动手了!

实验设置

我们扩展了聚类库,实现了 e-means 和 SuperEMeans(已在 https://github.com/cwida/SuperKMeans 开源),并测量了它们的收益。

数据集:我们将使用两个数据集:i) 来自 VectorDBBench 基准的 500 万条 1536 维 OpenAI 嵌入:https://huggingface.co/datasets/makneeee/openai_large_5m。(27 GB)。ii) 用 Cohere Embed V3 模型嵌入的前 1000 万条 MS MARCO 段落(1024 维向量):https://huggingface.co/datasets/Cohere/msmarco-v2.1-embed-english-v3(40 GB)。

索引:我们将构建一个点与簇的比例为 1:256 的 IVF 索引,因此 OpenAI 数据集约有 20,000 个质心,Cohere 数据集约有 40,000 个质心。

配置:本次实验,我将使用单台 Zen 5 机器,16 核、128 GB 内存(r8a.4xlarge | $1.278/hr)。不过,我们的 SuperKMeans 库可在任何 CPU 上运行(例如 Intel、Graviton、Zen)。

结果

下图比较了 Lloyd's(10 次迭代)、SuperKMeans(10 次迭代)、e-means(2 个 epoch)和 SuperEMeans(2 个 epoch)的端到端聚类运行时间。SuperEMeans 大幅加速了 e-means,最高快 1.8 倍。

但是……这是高质量的索引吗?

让我们比较各方法得到的质心在向量搜索任务上的表现。在本分析中,我们向 IVF 索引发出 1000 条查询。然后,我们测量在扫描 1% 可用簇的情况下,检索到的前 100 条结果中落在真实前 100 条结果里的比例(recall@100)。我们还通过统计扫描这些簇时执行的距離计算次数,比较了簇的均衡性。OpenAI 数据集的结果汇总在下表中:

算法运行时间(秒)探测 1% 质心时的平均 Recall@100探测 1% 质心时平均扫描向量数
Lloyd's k-means(10 次迭代)9850.96252 053
SuperKMeans(10 次迭代)2320.96251 993
e-means(2 个 epoch)2030.96758 184
SuperEMeans(2 个 epoch)1280.96758 198
e-means(2 个 epoch,作者实现)3330.96758 111

e-means 中的 Recall@100 略高。然而,我们最终在搜索过程中多扫描了约 10% 的向量。为了匹配扫描的向量数,我们必须在 e-means 中探测略少一些的簇,约为总簇数的 0.90%。这导致 recall@100 = 0.964,同时扫描 51,962 个向量,最终相比传统 k-means 是更好的权衡。

Cohere 的情况也一样:

算法运行时间(s)探测 1% 质心时的平均 Recall@100探测 1% 质心时的平均扫描向量数
Lloyds k-means(10 iters)2504.40.919112 714

| SuperKMeans(10 iters) | 623.3 | 0

另一种做法是对量化后的向量进行聚类。例如,在聚类前先把 32-bit 浮点数量化为 8-bit 整数,或量化为 1-bit RaBitQ 编码。我们在另一篇研究论文中对此进行了探索,并取得了显著的结果。

SuperKMeans 和 e-means 的详细技术报告可在 arXiv 上获取。

可复现性

用于复现本博客文章结果的源代码位于:https://github.com/lkuffo/reproducibility-superemeans

The translation is machine-generated and individual terms may be off. Nothing is rewritten or cut; the original is authoritative.

Published by Hacker News
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗