e-means 把 k-means 收敛压到十分之一轮次：100 亿嵌入聚类在 GPU 上快 9.5 到 45.5 倍
核心概要
e-means 把 k-means 的质心更新换成小批量指数移动平均，并用拟合出的缩放律从问题规模直接定出批大小与步长，不再需要超参数扫描。在多个嵌入数据集上，它用 1.4 到 2.6 个 epoch 就达到 Lloyd k-means 跑 25 个 epoch 的损失，对应相对 Flash-KMeans 的 9.5 到 45.5 倍实际耗时加速，并在收敛后损失更低。在 100 亿向量的 DINO10B 上，精确分配版本用 2.5 个 epoch 把向量分成 1600 万个簇，损失低于 Lloyd 跑 25 个 epoch 的结果。
深度剖析
聚类算法 e-means 在达到 Lloyd k-means 跑满 25 个 epoch 的损失时，只需要 1.4 到 2.6 个 epoch，而此前小批量 k-means 虽然收敛更快，却停在更高的近似误差上，静态数据集上的默认选择仍是全批量的 Lloyd。 小批量 k-means 与 Lloyd 相比通常近似误差更高，Lloyd 在迭代足够多或配合 k-means++ 初始化时能达到最低均方误差，因此文献中静态固定数据集仍以 Lloyd 为默认。 在 DEEP、DINO10B、SPACEV、SimSearchNet++ 四个数据集、100 万到 10 亿规模、簇数 16384 到 1048576 的配置上，e-means 达到 Flash-KMeans 第 25 轮损失所需 epoch 为 1.4 到 2.6，对应 9.5 到 45.5 倍实际耗时加速，且收敛损失更低。
质心不再存成坐标，而是每个簇维护一个计数和一个求和，两者按指数移动平均随小批量更新，质心取二者之比读出。 指数移动平均更新此前用于 VQ-VAE 跟踪移动的嵌入分布，衰减率通常当作继承来的常数，从未与 Lloyd 的全批量 k-means 直接比较。 方法在 100 万到 10 亿向量的图像与文本嵌入数据集上评估，簇数从 16384 到 1048576，所有实验都不调超参数，批大小与衰减由在 DEEP 上拟合的缩放律给出。
衰减率与批大小由两条在 log 空间线性的缩放律从数据点数、簇数和 epoch 预算直接算出，使用者不必为陌生数据集猜步长。 此前的小批量方法没有给出按问题配置调整批大小与步长的办法，面对不熟悉的数据集只能靠猜，降低了实用性。 两条律用 7.5 万次优化运行拟合，在留出数据集上中位超额均方误差接近 1% 的目标，并在比拟合规模高数个数量级的设置上仍然可用。
启示与展望
演示范围是图像与文本嵌入数据集上的离线聚类，规模从 100 万到 100 亿向量，簇数从 16384 到 16777216，GPU 实验在 H100 80GB 上完成，CPU 对照使用 Faiss。100 亿向量的 DINO10B 结果中，精确分配版本需要 32 台机器，改用 IVF 近似分配后可在单机 23 GPU 小时内达到同一测试损失。
缩放律针对较高维数据集调优，在极低维和极小数据集上并非最优；作者指出一般不知道数据的局部内在维度，而这正是需要的那一个。批大小律在留出数据集上的中位超额均方误差接近 1% 的目标，并非精确命中。在 10 亿向量规模上，作者把批大小律除以 2，因为该规模下更小的批大小吞吐相当。