比传统 K-Means 快十倍?拆解 Meta e-means 的加速真相

目录
做大规模商品语义检索时,商品和用户的查询都会被编码成高维向量。以 1,000 万件商品、768 维 float32 向量为例,光向量本身就约 30.7 GB;用户搜一次“适合夏天庭院使用、好打理的户外家具”,如果全库逐条算距离,每次查询都得把这 30 多 GB 扫一遍。离线跑几次没问题,但放到要求毫秒级响应、每秒成百上千次查询的线上服务里,成本和显存都很难承受。
工程上常见的做法是建近似最近邻(Approximate Nearest Neighbor,ANN)索引,最常见的一种是倒排文件索引(Inverted File Index,IVF):先用 K-Means 训出一批聚类中心,把商品向量分桶;查询时只挑最近的几个桶去扫。比如 65,536 个桶里只扫 32 个,扫描量就降到约 0.05%(千分之一以下)。
真正推高成本的环节在于全量重建索引。常规商品上新可以直接归入已有的桶,但一旦商品分布明显漂移,或者升级了 Embedding 模型导致全库向量重算,就必须全量重建索引;在不少大规模检索场景里,训练这批聚类中心是重建索引时最贵的一环之一。
2026 年 11 月 6 日,Meta FAIR 提交了论文《e-means: outperforming k-means (in one-tenth the epochs)》[1]。他们没动 K-Means 的目标函数,只把求解器重做了一遍:用指数移动平均(Exponential Moving Average,EMA)做小批量更新,再配上死簇复活和经验缩放定律。论文在多种高维向量基准上报告,e-means 只需 1.4–2.6 轮(epoch),就能追平 GPU 强基线 Flash-KMeans[2] 跑 25 轮的测试均方误差(MSE)[1]。
不过,把加速数字放进真实业务前,还得先算清楚四本账:算法轮次、实际计算耗时、线上召回率和整套索引的重建成本。
先说结论:e-means 省的是聚类训练这一环,数据扫描大约降到原来的十分之一,实际耗时能快多少取决于数据规模、硬件和基线实现;至于能不能变成你系统里的真收益,取决于聚类训练在整条重建流水线里占了多大比重。
一、经典 Lloyd 与传统小批量卡在哪里? #
1.1 Lloyd 算法:全量扫描太重,单调下降也会卡死 #
给定 \(n\) 个 \(d\) 维向量 \(X=\{x_1,\ldots,x_n\}\),K-Means 要找 \(k\) 个中心 \(C=\{c_1,\ldots,c_k\}\),把每个样本到最近中心的平方距离均值压到最低:
\[ J(C)=\frac{1}{n}\sum_{i=1}^{n}\min_{1\le j\le k}\|x_i-c_j\|_2^2 \]这个目标只管簇内平方误差,不管各个簇的人数均不均匀。真实数据本身就偏斜,大簇和小簇并存很正常。经典 Lloyd 算法就两步来回倒腾[3]:
- 样本分配:给每个向量找最近的中心,\(a_i=\arg\min_j\|x_i-c_j\|_2^2\)。
- 中心更新:把分到同一个簇的向量取平均,\(c_j=\bigl(\sum_{i:a_i=j}x_i\bigr)/|\{i:a_i=j\}|\)。
直接逐对算距离时,扫完一轮全量数据的计算量是 \(O(nkd)\),跑 \(T\) 轮就是 \(O(Tnkd)\)。矩阵乘法、分块和 GPU 并行可以把单轮常数压得很低,可每一轮都得把全量数据重新过一遍。到了开头提到的全量重建场景,这种每轮全扫的开销就会把重训周期拖得很长。
更麻烦的是,Lloyd 并不只是慢。只要每轮严格执行精确分配和均值更新,训练误差确实不会往上涨,但“不往上涨”只保证能走到某个局部最优,最终落到哪一个解取决于初始中心的位置。想象二维平面上排成一排的五个点团,手头正好有五个中心:如果开局运气不好,两个中心扎进了同一个点团,另一个点团没有中心落进去,Lloyd 会按当前划分反复求均值,很可能一直卡在这个次优划分里。
e-means 官方主页专门放了这个二维五团演示:运行 200 次随机初始化后,Lloyd 有 46% 的概率卡在次优划分里,e-means 为 0%;有兴趣的话,可以直接去官方 e-means Playground 拖动参数,在浏览器里观察两种算法在多种二维分布上的质心轨迹和 Voronoi 划分[4]。这组二维演示直观展示了 e-means 跳出次优划分的效果(具体机制见下一章),实际收敛表现仍取决于数据分布与初始化。换到高维真实数据,论文使用 40 个随机种子进行比较:即使给 Lloyd 配上贪心版 k-means++(greedy k-means++)初始化并运行到完全收敛,仅靠随机初始化的 e-means 在训练和测试 MSE 上仍然更低[1]。

注:截图来自官方 e-means Playground[4](Meta logo 分布,\(n=100{,}000\),\(k=500\),Seed=0):e-means 仅跑 5 轮,训练与测试 MSE(3.99e-4 / 4.10e-4)就低于 Lloyd 跑 25 轮的结果(4.14e-4 / 4.24e-4)。
1.2 传统小批量:永久累计把早期错账背在身上 #
为了避免全量扫描,又减少确定性更新陷入局部最优的概率,小批量随机更新很早就有人尝试:MacQueen 在 1967 年提出增量更新[5],Sculley 在 2010 年把它用于 Web 规模数据上[6]。
下面讨论的是经典的累计均值式 Mini-Batch(带遗忘因子的流式变体另需单独调衰减率)。这类做法会给每个簇记两个累加值:累计样本数 \(N_j\) 和累计向量和 \(S_j\)。当前批次里有 \(n_j\) 个样本分给簇 \(j\)、向量和是 \(s_j\),直接往上加:
\[ N_j\leftarrow N_j+n_j,\qquad S_j\leftarrow S_j+s_j,\qquad c_j=\frac{S_j}{N_j}. \]问题出在累计均值本身。训练刚开始时,中心位置还歪得很厉害,大批样本会被分错桶,而这些错账会一直留在 \(N_j\) 和 \(S_j\) 里。虽然随着 \(N_j\) 增大,早期样本的相对权重会按 \(1/N_j\) 慢慢稀释,但稀释速度太慢,多跑几轮也很难把中心迅速拉回正轨。
小批量抽样带来的随机波动,原本有机会把中心移出当前局部最优区域;但算法既要淡化旧分配的影响,又要在后期收紧波动。e-means 的解法很直接:让历史统计量按指数衰减,并在后期缩小更新步长。
二、e-means 如何改写聚类中心更新? #
2.1 EMA 淡化旧账,并把中心锁在凸包内 #
顺着 VQ-VAE 用指数移动平均维护码本的思路[7],e-means 同样维护 \(N_j\) 和 \(S_j\),只是不再一直累加,而是同步做指数衰减(原论文用衰减率 \(\gamma_t = 1-\alpha_t\) 书写,这里直接用步长 \(\alpha_t\) 会更直观):
\[ \begin{aligned} N_j^{(t+1)}&=(1-\alpha_t)N_j^{(t)}+\alpha_t n_j^{(t)},\\ S_j^{(t+1)}&=(1-\alpha_t)S_j^{(t)}+\alpha_t s_j^{(t)},\\ c_j^{(t+1)}&=\frac{S_j^{(t+1)}}{N_j^{(t+1)}}. \end{aligned} \]\(\alpha_t\) 控制当前批次的权重。如果先把 \(\alpha\) 当成常数看,\(m\) 步之前的历史信息权重会按 \((1-\alpha)^m\) 指数衰减,早期的错分配很快就被稀释掉了。
这里有个很讲究的细节:e-means 同时平滑样本数和向量和,让每个簇的实际步长随当前批次样本数动态调节。假设这一批有样本落进簇 \(j\),记当前批次均值为 \(\bar{x}_j=s_j/n_j\),把上面的式子整理一下,就能看到中心的实际移动量:
\[ \begin{aligned} c_j^{(t+1)} &=c_j^{(t)}+\eta_j^{(t)}\bigl(\bar{x}_j^{(t)}-c_j^{(t)}\bigr),\\ \eta_j^{(t)} &=\frac{\alpha_t n_j^{(t)}}{(1-\alpha_t)N_j^{(t)}+\alpha_t n_j^{(t)}}. \end{aligned} \]也就是说,每个簇的实际步长 \(\eta_j^{(t)}\) 会按“这批来了多少样本”和“历史上攒了多少样本”的比例自动伸缩。要是这批一个点也没分给簇 \(j\)(\(n_j=s_j=0\)),分子分母同比例衰减,中心停在原地不动,直到后续再来样本或触发复活。另外,一旦批次放大到全量数据(\(B=n\))且取 \(\alpha=1\),这组式子就精确退化成一轮 Lloyd 更新——Lloyd 其实就是它的一个特例。
读到这里,很多人会问:既然改成小批量优化了,为什么不直接使用深度学习里常见的 SGD 或 Adam?论文在 Appendix E 中比较了 EMA、SGD、Adam 和 SparseAdam:批次较小时,各方法表现相近;一旦批次扩大到足以充分利用现代 GPU,SGD 和 Adam 的误差会明显上升,甚至出现训练不稳定[1]。原因是:EMA 算出的中心始终是已分配样本的加权平均,因此不会离开这些样本围成的凸包(Convex Hull);而 SGD 和 Adam 使用梯度步长,批次扩大且学习率较高时,中心可能一次跨到凸包之外并引发发散。
2.2 拆大簇救活死簇 #
高维空间里,经常会有中心长期分不到样本,占着名额却不参与划分,也就是所谓死簇(Dead Cluster)。
e-means 借用了 Faiss 拆分活跃簇的做法[8],并把检查频率加密到每 5 个小批量一次(Faiss 默认按轮次检查)[1]。只要某个簇的 EMA 计数掉到所有簇均值的 10% 以下,就会被标记为待复活的死簇:
\[ N_j<0.1\cdot\frac{1}{k}\sum_{\ell=1}^{k}N_\ell. \]复活分两步完成:首先按簇大小加权挑出一个样本较多的供体簇(Donor Cluster);随后在原中心的各个维度上分别交替乘以微小的 \(1\pm\delta\) 和 \(1\mp\delta\),生成两个对称且相邻的新中心,同时将原簇计数一分为二并按 \(S_j=c_j N_j\) 写回向量和[1]。这个微小扰动相当于用一个穿过原中心的超平面把大簇一分为二,随后分到两个簇中的样本会自然把两个新中心拉开;\(\delta\) 取接近 BF16 的机器精度量级,因此即使在 GPU 端用低精度计算距离(见 4.1 节),两个新中心也不会因舍入而重合。算法只更新中心向量和统计量,计算量只与向量维度 \(d\) 有关,与簇内样本数无关,无需重读簇内样本进行二分聚类[1]。
在 DEEP 100 万向量、16,384 个中心的消融实验里,作者把最终不足 10 个样本的簇算作死簇:不开复活时,死簇比例高达 26.3%;使用当前批次中的随机样本重新初始化后降到 14.3%;改用拆分大簇后进一步降至 0.3%,并取得最低测试 MSE[1]。官方实现还增加了低维保护:当 \(d\le 2\) 时默认关闭复活机制,因为在极低维场景下强行拆分大簇反而可能降低效果[9]。
在异常检测、稀有商品或高客单价长尾品类里,样本极少的簇往往正是业务关注的重点;按样本数设阈值仅服务于降低全局 MSE,落地时需结合细分群体召回单独评估。
2.3 余弦退火与近零开销收尾 #
解决了前期探索和死簇问题后,训练后半段还需要让中心稳定收敛。如果 \(\alpha\) 从头到尾都很大,中心即使已经到达较好位置,也会被每批随机样本左右拉动。e-means 因此使用余弦退火(Cosine Annealing),在总更新步数 \(M=T\lfloor n/B\rfloor\) 内,将步长从 \(\alpha_0\) 平滑降低到 \(0.1\alpha_0\):
\[ \alpha(t)=\alpha_0\left[\varepsilon+\frac{1-\varepsilon}{2} \left(1+\cos\frac{\pi t}{M}\right)\right],\qquad\varepsilon=0.1. \]前期步子大,方便中心快速找对位置;后期步子小,慢慢落定减少震荡。思路和深度学习调学习率一模一样,只不过这里调的是 EMA 步长。
到了训练尾声,e-means 还提供了两种几乎不增加额外算力的收尾策略(Finalization)[1]:Last-Epoch Mean 直接复用最后一轮记下的样本归属求精确均值;Slow-EMA 则另外维护一组衰减更慢的 EMA 统计量,只跟着累计数据、不参与训练分配,相当于给中心加一层正则平滑(\(n/k\) 偏小时泛化收益更明显)。具体取舍看下表:
| 策略 | 适用场景 | 额外扫描 | 误差侧重 | 精确归属 |
|---|---|---|---|---|
| Last-Epoch Mean | 静态离线聚类(默认) | 否 | 降训练 MSE | 近似,需补 assign |
| Slow-EMA | 新向量与测试泛化 | 否 | 降测试 MSE | 需另跑 assign |
由于最后一轮里中心还在微微移动,训练结束直接返回的标签未必每个都严格对应最终中心的最近邻;如果下游强依赖精确归属,还得补跑一次 assign。但官方 README 算过一笔账:在固定总算力 \(T\) 轮的前提下,直接跑满 \(T\) 轮并用最后一轮标签,通常比跑 \(T-1\) 轮再花 1 轮算力重做全量分配效果更好[9]。
三、经验缩放定律如何免去人工调参? #
更新规则确定后,还有两个难以绕开的超参数:Batch Size \(B\) 和初始步长 \(\alpha_0\)。如果更换一份业务数据就要重新进行网格搜索,算法节省的训练时间可能又被调参耗掉。下面两条经验公式只按数据规模给出推荐的 \(B\) 和 \(\alpha_0\),中心数 \(k\)、轮数预算 \(T\)、向量归一化和距离度量仍由业务决定,具体数据集上的效果也需实测验证。
研究团队在 DEEP 数据集上跑了约 7.5 万次训练实验(覆盖 1,399 组基础配置,在每组上扫描 8–31 个步长或 13–20 个批次,并各跑 3 个随机种子),按数据量 \(n\)、中心数 \(k\) 和轮数预算 \(T\),在对数空间里拟合出两组幂律公式[1]:
\[ B\approx 0.035\,k^{0.13}n^{0.88}T^{0.81} \]\[ \alpha_0\approx\min\bigl(0.824\,k^{-0.46}B^{0.90}n^{-0.45}T^{-0.11},1\bigr) \]算出来的 \(B\) 取整到最近的 2 的幂次,最高不超过数据总量(官方实现里上限进一步收紧到约 \(n/2\))。论文和官方库还把批次法则分成了两档:系数 0.035 是默认吞吐档(throughput),用在 \(n\le 2\times 10^6\);到了更大规模(\(n>2\times 10^6\))或者低维数据(\(d\le 16\)),直接把批次除以 8(系数约 0.0044,即 quality 档)。批次缩小意味着每轮更新步数增加,在小数据集上可能降低吞吐;但在 \(n>2\times 10^6\) 时吞吐基本持平,同时能把新数据集(OOD)上偏离最优超参的 MSE 损失从 0.19% 进一步压到 0.07%[1][9]。
拿开头零售平台的规模代进去算一遍,马上能看出量级:假设 \(n=10^7\) 件商品、\(k=65,536\) 个中心、预算 \(T=3\) 轮。因为 \(n>2\times 10^6\),走质量档系数 0.0044:
把 \(B=65,536\) 再代进步长公式,得到 \(\alpha_0\approx 0.068\)。整场训练每轮约 152 步、3 轮一共 456 步,步长从 0.068 余弦退火到 0.0068,全程不用手动扫参。
和常用来预测大模型能力上限的 Scaling Laws 不同,这两条公式本质上是一套按问题规模和轮数预算自动估算超参数的经验律[1]。
四、45.5 倍加速到底比较了什么? #
4.1 同等误差下的轮次、CPU 与 GPU 耗时 #
先看评测口径。论文以 Flash-KMeans 运行 25 轮后的测试 MSE 为基准,测量 e-means 首次达到或低于该误差需要多少轮,比较的是固定目标误差下的实际耗时。
以 DINO10B 的不同规模子集为例,论文 Table 4 的数据及对应的轮次缩减倍数如下[1]:
| 向量数 | 中心数 | 达标轮次 | 轮次缩减 | GPU 加速 |
|---|---|---|---|---|
| 100 万 | 16,384 | 2.0 | 12.5× | 12.7× |
| 1,000 万 | 65,536 | 1.4 | 17.9× | 23.3× |
| 1 亿 | 262,144 | 1.6 | 15.6× | 31.3× |
| 10 亿 | 1,048,576 | 1.6 | 15.6× | 45.5× |
注:数据来自[1] Table 4,基线为 Flash-KMeans 25 轮测试 MSE;轮次缩减按 \(25 / \text{达标轮次}\) 折算。100 万至 1 亿规模用单张 H100(10 种子中位数),10 亿规模用 8 张 H100(单次运行),45.5× 属于 10 亿子集而非完整百亿实验。

注:官方基准图来自 Meta FAIR Faiss 仓库(MIT 许可)[9],展示 DEEP 100 万向量、16,384 中心设置下,轮次缩减(左)如何分别转化为 64 核 CPU(右上,含 SuperKMeans)与单张 H100 GPU(右下,对比 Flash-KMeans)的实际运行加速。
把表里最后两列摆在一起看,提速的来源就很清楚了。100 万规模下,轮次缩减(12.5×)和 GPU 加速(12.7×)几乎 1:1;等到规模涨到 10 亿,两者之比拉大到约 2.9。也就是说,45.5× 里大约 15.6× 来自少扫轮次,其余部分来自融合 Kernel、低精度计算与多卡扩展带来的单轮效率提升——这只是粗估,因为基线单轮耗时随规模也在变化。
哪怕完全不碰定制 GPU Kernel,少扫轮次本身带来的加速依然很明显:在 64 核 CPU 上跑 11 个 VIBE 基准数据集,e-means 相对 Faiss CPU 快了 9.0–15.0 倍[1];在 DEEP 100 万规模上,相对 Faiss CPU 与距离剪枝基线 SuperKMeans 也快了 11.8 倍[1][9]。除此之外,它还省掉了一大笔初始化开销——只用随机初始化就能赢过配了贪心版 k-means++ 的 Lloyd,而在 64 核 CPU、100 万向量、16,384 个中心的测试中,光跑 k-means++ 初始化就要 2,852–6,080 秒,比 e-means 整场训练(22–72 秒)慢两个数量级[1]。
而在 GPU 端,小批量更新最怕频繁读写显存把速度拖垮。论文在 H100/H200 上写了 CuTe 融合 Kernel(其他新卡走 Triton Kernel),把距离计算、分块取最近中心和 BF16/FP8/INT8 低精度搜索融合在同一个 Kernel 里,利用展开式:
\[ \|x-c\|_2^2=\|x\|_2^2+\|c\|_2^2-2x^\top c, \]跑满矩阵计算单元,同时把统计量累计和中心更新留在 FP32 里保精度[1][9]。少扫轮次靠 EMA,把少扫的轮次变成更短的运行时间靠融合 Kernel;拿纯 Python 循环照着公式写一遍,肯定跑不出论文里的速度。
4.2 百亿向量:精确分配与近似分配的差距 #
论文把规模一路推到了完整的 DINO10B(约 100 亿向量、\(2^{24}\approx 1,677\) 万个中心)。在精确最近中心分配下[1]:
| 方法 | 轮次 | GPU-hours | 机器数 | 测试 MSE(×10⁴) |
|---|---|---|---|---|
| Lloyd | 25 | 6,784 | 64 | 12.987 |
| e-means | 2.5 | 779 | 32 | 12.985 |
注:数据来自[1] Appendix M Table 21,每台机器配备 8 张 H100;测试 MSE 越低越好。
精确分配下,e-means 消耗的总 GPU 卡时(GPU-hours)约为 Lloyd 的 11.5%(节省 88.5%,约 8.7 倍),这反映的是总资源消耗之比。由于实验同时把机器数从 64 台(512 卡)减半到 32 台(256 卡),按满卡并行折算实际运行时间,Lloyd 约 13.3 小时、e-means 约 3.0 小时,实际耗时约快 4.4 倍。
千万级中心做暴力精确搜索实在太慢,论文于是在训练期套了 IVF 近似分配,配合本地 SSD 流式读取数据:一台 8×H100 机器跑 3 轮、花 23.2 GPU-hours(实际运行约 3 小时),测试 MSE 就优于基线[1]。作者在 Appendix M.4 中推测,近似分配引入的噪声可能起到正则化作用,从而改善了测试 MSE;如果要按训练 MSE 精确追平 Lloyd 运行 25 轮的效果,百亿规模下仍需运行 4 轮、消耗 43.8 GPU-hours(约为精确分配基线 6,784 GPU-hours 的 1/155)[1]。
读百亿规模数字的三个口径:8.7 倍衡量总 GPU 卡时(资源消耗);4.4 倍的实际耗时差距建立在节点数减半(64 台 vs 32 台)的前提下;近似分配(23.2 / 43.8 GPU-hours)改变了搜索路径,需与精确分配分开评估。
五、放进生产系统,该不该换? #
5.1 先算两笔工程账:线上召回与端到端瓶颈 #
上一章拆完了算法轮次和实际计算耗时两本账;真要上线,还得接着算另外两本账。
第一本是线上召回。论文在 11 组 VIBE 检索基准上验过下游效果:同样训练时间下,e-means 的 Recall@10 普遍更高;要达到基线充分训练后的召回率,它建索引花的时间也短得多[1]。但上线前得把两个指标分开盯——聚类 MSE 量的是向量离最近中心有多近,检索 Recall@K 量的是查询能不能捞回真正的近邻。两者大体同向,中间还隔着倒排表均匀度、查询分布偏移、PQ/SQ 量化损失和 nprobe 预算。生产上做决策,直接拿目标机器跑 Recall–Latency 曲线比盯着离线 MSE 靠谱得多。
第二本是整套索引的重建成本。如果你的 IVF 检索系统周期性训练聚类中心,并且该环节占用了重建任务的大部分算力,换用 e-means 的收益会非常明显。但一条完整的索引重建流水线还包括 Embedding 推理、数据清洗、全量归桶、压缩编码、倒排表落盘和灰度切流,e-means 只能加速聚类训练这一环。套用 Amdahl 定律 \(\mathrm{Speedup}_{\mathrm{total}} = 1 / \bigl((1-p) + p/s\bigr)\)(其中 \(p\) 是被加速环节占总耗时的比例,\(s\) 是该环节的提速倍数):假如聚类训练只占重建总时间的 \(p=30\%\),其余环节占 \(1-p=70\%\),即使把聚类提速 \(s=10\) 倍,新总耗时也只从原来的 \(1\) 降到 \(0.7 + 0.3/10 = 0.73\)——也就是说,整条链路的总耗时仅缩短了 27%,整体速度变为原来的 1.37 倍:
\[ \mathrm{Speedup}_{\mathrm{total}}=\frac{1}{0.7+0.3/10}=\frac{1}{0.73}\approx 1.37. \]这只是一个估算示例,与论文实测无关。接入代码前,应先测量每个环节的耗时占比,从而避免投入后收益有限的优化。RAG 系统也是如此:底层使用 IVF 时,e-means 可以减少训练粗量化器(Coarse Quantizer)的成本;底层使用不依赖 K-Means 粗聚类的 HNSW 等图索引时,它则派不上用场。即使使用 IVF,RAG 最终答得好不好仍主要取决于 Embedding 模型、切块(Chunking)、混合检索、重排序(Reranking)和生成模型——不能指望更换聚类器就提升问答质量。
5.2 接入方式、验证清单与未解边界 #
e-means 已合入 Faiss 仓库的 faiss.contrib.e_means 模块[9]。CPU 上装新版 faiss-cpu 就能跑 NumpyEmeans;GPU 上用 Emeans 直接喂 PyTorch CUDA 张量(连 Faiss GPU 编译包都不用装),H100/H200 自动走 CuTe Kernel,A100/B200/RTX 30–40 走 Triton Kernel,余弦相似度场景还能直接开 spherical=True[9]。按官方 README 精简出的几行代码,可以直接在本地试跑 CPU 接口:
import numpy as np
from faiss.contrib.e_means import NumpyEmeans
rng = np.random.default_rng(42)
X = rng.standard_normal((200_000, 64)).astype("float32")
model = NumpyEmeans(d=64, k=500, nepochs=5) # 官方默认 5 轮;基准上常可接近或低于 Lloyd 收敛误差,业务数据需实测
centroids, labels = model.train(X)
print("centroids:", centroids.shape)
print("labels:", labels.shape)
注:这段代码只用来演示 CPU 接口,看不出 GPU 融合 Kernel 的速度。另外 GPU 路径上有一个容易踩的坑:Emeans 默认不查 NaN 和 Inf,混进一个异常值就会悄无声息地把中心算坏,训之前记得先过一遍 assert torch.isfinite(xg).all()[9]。
真要评估线上能不能切,拿自有数据跑完这三组对照就够下判断了:
- 常规高维分布:在真实业务 Embedding 上把 Lloyd、传统 Mini-Batch K-Means 和 e-means 拉到同一条起跑线,看同 MSE 下的耗时和多随机种子方差;
- 长尾与偏态类目:专门抽样检查小众但高价值的类目(比如零售库里销量低、客单价高的特殊商品),看拆大簇机制有没有挤掉它们的中心——全局 MSE 好看,替不了细分群体的召回验证;
- 端到端 IVF 压测:把数值精度、硬件、初始化时间口径和精确/近似分配全部对齐,直接比固定扫描预算下的 Recall@K、P95 延迟和全链路重建耗时。
最后还有两条边界,论文目前还没有解决:
- 静态数据假设:所有评测都基于静态离线数据集。EMA 虽具指数遗忘特性,面对持续变化的在线流式数据和概念漂移(Concept Drift),仍需额外设计滑动窗口、重采样和索引版本切换。
- 经验公式边界:那两条 Scaling Laws 是在高维 Embedding 上拟合出来的经验公式。碰到极低维数据、特殊内在维度、极端簇失衡或者非欧氏距离,还是拿验证集实测为准,别闭着眼睛照搬默认值。
结语 #
K-Means 实在太老了,老到大家默认 Lloyd 算法就是它的标准答案。e-means 没碰经典目标函数,只是按现代小批量优化和 GPU 硬件重做了一遍求解器——靠 EMA 淡化旧账、拆大簇救活死簇、缩放定律省掉调参,把训练阶段的数据扫描压到了约十分之一。
放宽视野看,这套思路对企业和研究者各自意味着不同的机会:
- 对企业与工程团队:过去受限于算力成本而被迫推迟的索引全量重训,现在更容易跟上 Embedding 模型升级和业务分布变化的节奏;配合近似分配与 SSD 流式训练,超大规模聚类的门槛也从动辄数十台集群下探到单机多卡。不过落到具体系统里,仍要先回答一个直接的问题:聚类训练是不是你这套重建流水线中最慢、最昂贵的环节?如果是,就按上一节的三组对照在自有数据上实测(也可以先到 e-means Playground 调整参数建立直觉,或观看文末的视频解读);如果不是,单环节的漂亮加速比也不会带来等比例的系统收益。
- 对研究者:e-means 证明了一个容易被忽视的方向——用现代深度学习工具箱(小批量随机优化、EMA、余弦退火、硬件融合 Kernel 和经验缩放定律)重写经典无监督算法,即便不动目标函数,依然有数量级的提效空间。沿着这条线往下走,如何把离线 EMA 求解器扩展到持续漂移的在线流式场景,以及把“免调参的经验缩放定律”推广到非欧氏度量、乘积量化(PQ)和大规模训练数据去重与配比,都是值得继续深挖的课题。
参考文献 #
[1] Bessa, S., Mazaré, P.-E., Szilvasy, G., Touvron, H., Picard, D., Douze, M., & Jégou, H. (2026). e-means: outperforming k-means (in one-tenth the epochs). arXiv:2611.09501. https://arxiv.org/abs/2611.09501
[2] Yang, S., Xi, H., Zhao, Y., et al. (2026). Flash-KMeans: Fast and memory-efficient exact K-means. arXiv:2603.09229. https://arxiv.org/abs/2603.09229
[3] Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137. https://doi.org/10.1109/TIT.1982.1056489
[4] Meta FAIR. e-means Project Page & Interactive Playground. https://e-means.github.io/ · https://e-means.github.io/playground.html
[5] MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
[6] Sculley, D. (2010). Web-scale K-means clustering. Proceedings of the 19th International Conference on World Wide Web, 1177–1178. https://doi.org/10.1145/1772690.1772862
[7] van den Oord, A., Vinyals, O., & Kavukcuoglu, K. (2017). Neural discrete representation learning. Advances in Neural Information Processing Systems, 30. https://arxiv.org/abs/1711.00937
[8] Douze, M., Guzhva, A., Deng, C., et al. (2024). The Faiss Library. IEEE Transactions on Big Data, 12, 346–361. https://arxiv.org/abs/2401.08281
[9] Meta FAIR. (2026). e-means Reference Implementation & README (faiss/contrib/e_means). GitHub. https://github.com/facebookresearch/faiss/tree/main/contrib/e_means
延伸资料:视频解读《Meta 改写 K-Means,训练轮次降到十分之一》。