源自 Meta FAIR 研究员 Hugo Touvron 和 Hervé Jégou 前期工作的现代 k-means 优化算法 e-means 正式公开，配套论文（arXiv:2611.09501）于 2026 年 11 月 6 日提交，核心代码已合入开源向量检索库 Faiss 的 contrib/e_means 目录。面对大模型数据去重和十亿级向量检索的算力瓶颈，e-means 仅需 1.2 至 3 个 epoch，就能达到传统 Lloyd 算法遍历全量数据 25 次后的保留集测试损失；在 NVIDIA H100 GPU 上比当前最快的精确实现 Flash-KMeans 提速 10 至 45 倍，在 64 核 Xeon Platinum 8462Y+ CPU 上比 Faiss 基准实现快 8 至 15 倍。这套方案的实质，是用现代深度学习的优化工具箱重写了停留在 1960 年代的数据基础设施底层。
不过，把博客标题里的“等损失下提速 10–45 倍且免调参”直接当成无条件替换指南，在工程落地时一定会踩坑。拆解论文与 Faiss 提交记录可以看到，45.5 倍的峰值加速来自单随机种子的 10 亿向量实验与 FP8/INT8 定制内核，而所谓免超参数调优依赖一套经验拟合的缩放定律，在低维或微小数据集上并不成立。
借动态码本的指数遗忘，破 1967 年的历史包袱
长期以来，k-means 是机器学习里极少数还在广泛使用全批量（full-batch）优化的角落。1957 年提出的 Lloyd 算法每次更新都要把全量数据扫一遍，通常得跑 20 到 50 轮；而业界现有的小批量（mini-batch）方案大多沿用 1967 年的 MacQueen 规则，把每次迭代分配给某个簇的样本总和与计数无差别累加。这种做法的致命伤是历史陈旧性：训练早期质心位置很差，当时分错的样本会永久留在分母和分子里拖累后续收敛，逼着工程师在速度和聚类质量之间做妥协。
e-means 的破局点，是把原本用于 VQ-VAE 等动态分布码本学习的指数移动平均（EMA）搬到了静态数据集上。它在小批量更新时按步长比例 α 遗忘旧统计量，只追踪近期分配的样本，并直接舍弃了繁重的 k-means++ 初始化，改用随机数据点开局；在 8 个测试配置上跑完 5 个 epoch 后，其测试均方误差（MSE）反而比采用贪婪 k-means++ 初始化的 Flash-KMeans 低 0.06% 至 0.33%。研究团队早先尝试过按 Meta FAIR 的思路用梯度下降（SGD）更新质心，却发现在大步长下极易失稳，原因是 SGD 会把质心推向当前样本点凸包之外，而 EMA 在数学上保证了新质心永远落在已分配样本的凸包内部。
靠小批量的适度噪声跳出局部最优，比全量死算更懂全局。
更反直觉的是，全量计算的 Lloyd 算法恰恰是 e-means 将批量设为全量数据、步长固定为 1 时的极端特例。由于全量更新每一步都单调降低损失，一旦掉进局部极小值就再也爬不出来；反倒是 e-means 的小批量更新自带随机噪声，配合从初始步长衰减到 10% 的余弦退火调度，在 200 次不同随机种子的多簇分布测试中，把卡在局部劣质解的概率从 Lloyd 的 15.5%–46% 压到了 0%–4%。为了解决小批量聚类常见的死簇（即没有任何样本分入的空质心）问题，e-means 没有像音频模型 EnCodec 那样从当前批次随便抽点充数，而是借鉴 Faiss 按簇大小比例挑出大簇一分为二；在 DEEP 数据集 1.6 万簇的测试中，这一改动把死簇比例从 EnCodec 策略的 14.3% 砍到了 0.3%。
撕开 45 倍加速的基准标签，看清四个工程边界
很多开发者看完官方博客，容易以为只要拉下代码就能白捡几十倍的加速比且彻底告别调参。但细查论文实验设置与代码实现，有四个直接影响生产环境决策的边界条件必须拎出来。
第一，免调参的底子是两道经验拟合公式，而非普适定理。研究团队根据数据量 n、簇数 k 和总轮数 T，拟合出了默认批量公式 B = 0.035 k^0.13 n^0.88 T^0.81（追求极致质量时将常数换为 0.0044）以及初始步长公式 α_0 = min(0.824 k^-0.46 B^0.90 n^-0.45 * T^-0.11, 1)，在 SIFT、SPACEV 等保留数据集上的中位遗憾值（regret）仅 0.07% 到 0.19%。但论文明确承认，这套缩放定律在微小数据集或极低维度数据上并非最优，拿去跑几千条低维业务表格数据很可能会翻车。
第二，45 倍的峰值数字有严苛的限定条件。在百万至一亿（1M–100M）向量的常规主力区间内，基于 10 个随机种子的中位数结果，e-means 用 1.4 至 2.6 个 epoch 达标，实际 GPU 挂钟加速比是 9.5 至 35.9 倍；而宣传中最抢眼的 21.2 至 45.5 倍加速，仅来自单随机种子的 10 亿（1B）向量实验。至于 100 亿个字节量化 DINOv3 图像块描述符（DINO10B）的极限测试，底层其实混入了近似倒排文件（IVF）分配，并从三种 IVF 配置里挑了最快的一组，不能和精确分配（exact-assignment）混为一谈。
| 评估维度 | 百万至亿级常规实验 (1M–100M) | 十亿级峰值实验 (1B) | 百亿级极限实验 (DINO10B) |
|---|---|---|---|
| 统计口径 | 10 个随机种子中位数 | 单一随机种子 (1 seed) | 挑选最快的一组配置 |
| 分配精度 | 精确最近邻分配 | 精确最近邻分配 | 近似 IVF 倒排分配 |
| 达标轮数 | 1.4–2.6 epochs | 1.2–3 epochs 区间内 | 依赖近似检索预筛选 |
| GPU 加速比 | 9.5–35.9 倍 | 21.2–45.5 倍 | 不与精确分配直接对比 |
第三，被当成靶子打的 Flash-KMeans（arXiv:2603.09229）其实和 e-means 走在两条正交的技术路线上。Flash-KMeans 是纯粹的算子级工程优化，靠融合分配与减少显存争用把“精确的 Lloyd 算法”压榨到极致；e-means 则是把底层数学规则改成了小批量近似更新，再叠加上支持 BF16、FP8 和 INT8 精度的 H100 定制融合内核。你的业务如果严格要求每一轮都算全量精确均值，e-means 并不是平替。
- 风险.GPU 后端存在特定软硬件依赖与首次运行编译开销（first-run compilation overhead），且算法的收尾阶段（finalization）必须根据业务目标是降低训练集损失还是优化保留集泛化做不同设置；目前社区尚无非 H100 显卡上的第三方独立复现报告。
对于 Milvus、Qdrant 等向量数据库团队以及大模型预训练数据清洗团队来说，构建十亿级 IVF 索引、训练乘积量化（PQ）码本或对百亿多模态嵌入做聚类去重，原本是最烧 GPU 时间的苦力活。2026 年 11 月 5 日合入的 Faiss PR #5833 已经将默认遍历次数设为 5 并通过了单卡与三卡 H100 内部测试。当下最务实的动作，是在上亿规模的高维嵌入管线里拉取 benchs/e_means 跑通自家数据分布的基准测试；至于它能否彻底取代 Lloyd 算法，要看 Faiss 社区接下来是否会把它从 contrib 实验目录提拔为构建 IVF 索引的默认标准组件，以及它在 A100 等存量主力卡上的真实编译与吞吐表现。