e-means：把 k-means 的 Lloyd 迭代換成小批次指數移動平均

向量檢索建倒排檔索引（inverted file，IVF）時，要先用 k-means 把幾百萬到幾十億個向量分成幾千到上百萬群，查詢時只比對最近的幾群；向量量化的碼本（codebook）、大型資料集的整理（data curation），也常靠 k-means 分群。最常用的 Lloyd 演算法每次迭代都把全部資料指派給最近的質心（centroid），再把每個質心改成它那群的平均，所以一次迭代就要讀完整個資料集一遍。Faiss 預設跑 25 次迭代，也就是 25 輪（epoch，讀完整個資料集一遍算一輪）。資料到十億筆、群數到百萬時，這 25 輪就是主要成本。

e-means 每讀一小批資料就更新一次質心。每一群的點數和向量和用指數移動平均（exponential moving average，EMA）累積，步長照餘弦曲線遞減，批次大小和起始步長由作者擬合的縮放定律（scaling law，從大量訓練結果擬合出的冪次公式）依資料量 n、群數 k、輪數 T 算出，使用者不必調參。e-means 和 Lloyd 最小化同一個目標，也就是 k-means 的均方誤差，兩者的差別在更新規則和步長排程；把批次設成整個資料集、步長設成 1、不用餘弦排程，e-means 就退回 Lloyd。

這篇論文是〈e-means: outperforming k-means (in one-tenth the epochs)〉，2026 年 11 月 6 日上傳到 arXiv。作者七人：Swann Bessa、Pierre-Emmanuel Mazaré、Gergely Szilvasy、Hugo Touvron、Matthijs Douze、Hervé Jégou 在 Meta FAIR，David Picard 在法國國立路橋學校（École Nationale des Ponts et Chaussées），Bessa 也同時標了這所學校。Douze、Mazaré、Szilvasy 和 Jégou 也是 Faiss 函式庫論文的作者，程式碼就放在 Faiss 的 contrib/e_means，採 MIT 授權。Bessa 另外寫了一篇有互動示範的專案部落格。論文是預印本，還沒經過同儕審查，下文的數字都是作者自己測的，目前沒有第三方重現。

作者在多個嵌入向量資料集上，用 1.4 到 2.6 輪就讓測試誤差低於 Lloyd 跑 25 輪的結果。測試誤差是把沒參與訓練的點指派給最近的質心後，這些點到質心的平均平方距離；用訓練資料算的叫訓練誤差。e-means 在 GPU 上比 Flash-KMeans（論文稱為目前最先進的 GPU 實作）快 10 到 45 倍，最後的誤差也比較低，但差距在 1% 以內，e-means 的優勢主要在速度。以下我先說明它怎麼更新質心、怎麼決定批次與步長，再整理結果、用法和限制。

質心怎麼更新？

k-means 要找 k 個質心，讓每個點到最近質心的平均平方距離最小。e-means 替每一群 j 記兩個量：質量 $N_j$ （加權累積的點數，舊的點會隨更新衰減）和向量和 $S_j$ ，質心就是兩者的比值。一批資料進來後，先把每個點指派給目前最近的質心，算出這批資料落在第 j 群的點數 $n_j$ 和向量和 $s_j$ ，再用衰減率 $\gamma$ 更新：

N_j \leftarrow \gamma N_j + (1-\gamma)\,n_j,\qquad S_j \leftarrow \gamma S_j + (1-\gamma)\,s_j,\qquad c_j = \frac{S_j}{N_j}

論文把 $\alpha = 1-\gamma$ 叫做步長。程式碼用等價的寫法直接存質心：

c_j \leftarrow c_j + \frac{\alpha\, n_j}{N_j'}\left(\frac{s_j}{n_j} - c_j\right)

其中 $N_j'$ 是更新後的質量，這條式子只用在這批有分到點的群。也就是說，質心朝這批資料在該群的平均移動一段距離，比例是這批點數在新質量裡占的份量。這一批沒有分到點的群， $N_j$ 和 $S_j$ 都乘上 $\gamma$ ，質心不動，質量照樣衰減；一直分不到點的群，質量會越來越小，後文判斷死群（一直分不到點的群）就用這個質量。初始化時質量設得極小（論文是 $10^{-10}$ ，程式是 $2^{-16}$ ），隨機挑出的初始質心幾乎沒有權重，前幾批資料進來後，質心就由實際資料決定。

和另外兩種更新規則對照：Lloyd 每次都用整個資料集重算， $S_j \leftarrow s_j$ 、 $N_j \leftarrow n_j$ ，質心就是目前指派到它的點的平均。MacQueen 在 1967 年提出、後來的小批次方法多半沿用的規則則一直累加， $S_j \leftarrow S_j + s_j$ ，早期質心還很差時的指派也一起留在平均裡。EMA 以 $\alpha$ 的速度忘掉舊的指派，質心主要反映新近幾批的指派。這條規則原本用在 VQ-VAE（用碼本把連續表示量化成離散代碼的自編碼器）的碼本學習，那裡的碼本要追蹤一直在移動的分佈；作者把它搬到固定資料集上，並加上後面幾個元件。

步長和批次大小怎麼決定？

步長照餘弦曲線遞減，從第一次更新的 $\alpha_0$ 降到最後一次的 $0.1\,\alpha_0$ ：

\alpha(t) = \alpha_0\left(\varepsilon + (1-\varepsilon)\cdot\tfrac{1}{2}\bigl(1+\cos(\pi t/M)\bigr)\right),\qquad \varepsilon = 0.1

$t$ 是第幾次更新， $M = T\lfloor n/B\rfloor$ 是總更新次數。作者拿它和在驗證集上挑出的最佳固定步長比，在 8 組設定上，訓練誤差都低 0.26% 到 1.29%，測試誤差多半也比較低。

批次大小 $B$ 和起始步長 $\alpha_0$ 由兩條縮放定律算出：

B = c_B\, k^{b_k}\, n^{b_n}\, T^{b_T},\qquad \alpha_0 = \min\left(c_\alpha\, k^{a_k}\, B^{a_B}\, n^{a_n}\, T^{a_T},\ 1\right)

批次的縮放定律有兩版：吞吐量版求每秒處理的資料量，品質版求較低的誤差，兩版只差常數。論文表 2 的係數如下（程式碼存了更多位數，四捨五入後相同）：

縮放定律	常數	k 的指數	B 的指數	n 的指數	T 的指數
起始步長 $\alpha_0$	0.824	−0.46	0.90	−0.45	−0.11
批次 $B$ ，吞吐量版（`throughput`）	0.035	0.13	—	0.88	0.81
批次 $B$ ，品質版（`quality`）	0.0044	0.13	—	0.88	0.81

$B$ 最後四捨五入到最近的 2 的冪次。批次的縮放定律擬合的目標是「膝點」：驗證誤差還在最低點 0.2% 以內的最大批次，批次再大，品質就掉得很快。從指數看，批次隨資料量和輪數增加，接近正比（指數 0.88、0.81）；起始步長則隨批次變大（指數 0.90）。兩條縮放定律只用 DEEP 一個資料集（96 維的影像嵌入）擬合，共約 7.5 萬次訓練，涵蓋 n 從 $10^5$ 到 $10^8$ 、k 從 256 到 65,536，且每群平均至少 8 個點。拿 SIFT、SPACEV 和 VIBE 的 arXiv、AG-News 四個沒參與擬合的資料集來測，照縮放定律設定比起逐一找出的最佳設定，誤差的中位數只多 0.07%（步長）和 0.19%（批次）。

品質版的常數是吞吐量版的八分之一，批次約小八倍，更新次數多八倍。論文的主要實驗在 n 超過 200 萬時改用品質版，理由是在那個規模下，批次小一點，吞吐量也差不多。程式碼的預設 batch_law="auto" 則依維度選：維度 d 不超過 16 時用品質版，否則用吞吐量版。程式註解說明了理由：在 3 萬組合成資料的設定裡跑 3 輪，d ≤ 16 時改用吞吐量版，e-means 贏過 Lloyd 跑 25 輪的比例會少 11 到 20 個百分點。論文也說明，這兩條縮放定律是為較高維的資料調的，用在維度很低又很小的資料集上不是最佳。

沒有點的群怎麼辦？

小批次 k-means 常見的毛病是死群（dead cluster）：某個質心分不到任何點，之後也一直分不到，等於浪費一個碼本位置。e-means 每 5 個批次檢查一次，質量低於平均質量 0.1 倍的群就算死群。處理方式沿用 Faiss 的 k-means：每個死群從活著的群裡分到一個「捐贈群」，捐贈群依質量比例、不重複地抽出；把它的質心乘上兩組正負交錯的微小擾動，變成兩個略有差異的質心，一個留給捐贈群、一個給死群，兩者各分到一半的質量。這樣做不必重新處理那一群的點，成本固定；兩個新質心對稱地落在原質心兩側，所以兩群的分界穿過原質心。擾動的大小，論文說是 BF16 的機器精度，程式碼用 $10^{-4}$ 。

維度 d ≤ 2 時，這項處理預設關掉。程式註解記錄的測試是：在 foursquare 和 geonames 兩個二維資料集上，關掉它讓測試誤差的中位數低了 7% 到 10%（36 組成對實驗，各跑 3 輪）；到 d = 3 和 d = 14 就沒有差別。

最後一輪怎麼收尾？

最後一輪訓練時，e-means 記下每個點被指派到哪一群，訓練結束後，把每個質心換成最後一輪指派給它的點的平均；最後一輪一個點都沒分到的質心留在原位。這一步重用已經算好的指派，幾乎不花時間，論文說它保證會降低訓練誤差，在消融實驗裡少了它，訓練誤差高 0.14%。論文另外提供「慢速 EMA」收尾，用更慢的衰減另外累積一份質心，訓練誤差稍差、測試誤差較低，適合在意模型對沒見過的資料表現如何的應用。

這些指派是在質心還在移動時做的，所以 train 回傳的標籤不一定是每個點最近的最終質心。README 說，要精確的最近質心，就對訓練資料再呼叫一次 assign；不過在固定的計算預算下，跑 T 輪直接用回傳的標籤，比跑 T−1 輪再花一輪的計算做 assign 好。

為什麼用 EMA，不用梯度下降？

Bessa 在部落格交代，這個專案的起點是 Touvron 和 Jégou 先前在 FAIR 的發現：用梯度下降做小批次 k-means，可以贏過 Lloyd。Bessa 重現了這個結果，但發現步長大時，梯度下降的更新不穩定，EMA 則沒有這個問題。部落格的實驗用大批次（DEEP 100 萬筆、SIFT 1,000 萬筆，16,384 群，5 輪），各自挑最佳步長，梯度下降最後的測試誤差仍比 EMA 高 1.6%（DEEP）和 0.4%（SIFT）。論文附錄拿 Adam、SparseAdam 和 SGD 比，結論類似：批次小時大家差不多，批次大時其他優化器都明顯變差；大批次在現代硬體上跑得比較快，所以作者選了 EMA。

原因 Bessa 只說是推測：EMA 的質心永遠落在指派給它的點的凸包（包住這些點的最小凸集合）裡，梯度下降的一步卻可能跑出凸包。

Lloyd 落在這族方法的哪裡？

把批次設成整個資料集（ $B = n$ ）、步長設成 $\alpha = 1$ 、不用餘弦排程，更新後的 $N_j$ 和 $S_j$ 就正好是整群的點數和向量和，一次 e-means 更新等於一次 Lloyd 迭代。

部落格放了一張超參數掃描圖：DEEP 100 萬筆、1,024 群、5 輪，步長固定不排程，好讓 Lloyd 剛好是其中一格。誤差最低的區域沿著一條對角帶分布，批次越大，需要的步長也越大；Lloyd 落在全批次、步長 1 的角落，離那條帶子很遠。Bessa 據此認為，在這組掃描裡，Lloyd 是很差的一組設定，e-means 的縮放定律就是要自動挑到帶子裡的設定。

作者測到什麼結果？

輪數的範圍在論文和部落格出現好幾次，條件各不相同，以下分開列。

摘要的「1.4 到 2.6 輪」來自論文表 4：DEEP、DINO10B、SPACEV、SimSearchNet++ 四個資料集，各在四種規模（100 萬筆 16,384 群、1,000 萬筆 65,536 群、1 億筆 262,144 群、10 億筆 1,048,576 群）下，e-means 每次多跑 0.2 輪，直到測試誤差低於 Flash-KMeans 跑 25 輪的結果。對應的實際時間加速是 9.5 到 45.5 倍，摘要寫成 10 到 45 倍。規模越大，倍數越高：100 萬筆時是 9.5 到 12.9 倍，10 億筆時是 21.2 到 45.5 倍。1 億筆以下用一張 H100、取 10 個隨機種子的中位數；10 億筆用 8 張 GPU，只跑一個種子。部落格的說法更寬，寫「在大範圍的規模與資料集上」需要 1.2 到 3 輪，CPU 上比 Faiss 快 8 到 15 倍。

VIBE 基準的 11 個資料集（文字、程式碼、影像和多模態嵌入，維度 200 到 3,072，群數 8,192 或 16,384，每個 20 萬到 148 萬筆）另外測過一次。部落格的圖說寫每個資料集需要 1.6 到 2.4 輪（5 個種子的中位數）；論文附錄表 11 用 20 個種子，範圍是 1.6 到 2.6 輪，GooAQ 需要 2.6 輪。同一張表裡，GPU 上對 Flash-KMeans 快 8.0 到 22.8 倍，CPU（64 個實體核心）上對 Faiss 快 9.0 到 15.0 倍。這些資料集不大，GPU 上 e-means 只花 0.03 到 0.16 秒，Flash-KMeans 是 0.49 到 1.77 秒；CPU 上則是 3.3 到 29.3 秒對 36.7 到 274.0 秒。

倍數也要看拿誰比：部落格說，在一張 H100 上分 1,000 萬筆、65,536 群，用單純的 PyTorch 寫 Lloyd（資料放在 GPU、BF16）跑 25 輪要 142 到 155 秒，Flash-KMeans 只要 14 到 22 秒。也就是說，Flash-KMeans 本身就比單純的實作快好幾倍，e-means 在這個規模對 Flash-KMeans 再快 19.2 到 27.8 倍（表 4）。

規模最大的實驗是作者新做的 DINO10B：100 億個 DINOv3 影像區塊嵌入（1,024 維，以位元組量化）。e-means 把它分成 $2^{24}$ （約 1,678 萬）群，2.5 輪就低於 Lloyd 跑 25 輪的測試誤差。這個規模下，作者把質心建成 IVF 索引，每個點只和最近的幾群裡的質心比對，不再和每個質心算距離。達到同樣誤差，精確指派要 779 GPU 小時，IVF 指派只要 22.8 GPU 小時，不到一個 GPU 天。

誤差本身的差距小得多。論文表 5 的 8 組設定裡，e-means 跑 3 輪就低於隨機初始化的 Flash-KMeans 跑 25 次迭代。以 DEEP 100 萬筆、16,384 群為例，e-means 跑 5 輪的測試誤差是 0.38692，Flash-KMeans 跑 25 次是 0.38926，低約 0.6%（表 5 的 DEEP 以 $10^{-1}$ 為單位，寫成 3.8692 和 3.8926）。對手改用 k-means++ 初始化時，e-means 跑 5 輪仍然比較低，但差距縮到 0.06% 到 0.33%。

各個元件裡，死群處理影響最大。在 DEEP 100 萬筆、16,384 群、3 輪的消融實驗裡，關掉它，訓練誤差高 2.97%、測試誤差高 2.24%；拿掉餘弦排程、收尾等其他元件，影響都不到 0.3%。論文附錄表 14 比了三種死群處理方式，部落格也轉載了這張表：e-means 的分割、從當前批次隨機抽一個向量填回死群（神經音訊編碼器 EnCodec 的做法），以及關閉。條件是 100 萬筆、16,384 群、5 輪，取 5 個種子的平均；最後分到不到 10 個點的群算死群。群大小不均度衡量各群大小有多不平均，1 表示每群一樣大。論文沒有寫計算方式；程式碼的訓練統計把它算成 $k\sum_j n_j^2 / n^2$ ，也就是各群點數平方和相對於平均分配時的倍數，表中的數字應該是同一個量。DEEP 的 e-means 列 0.38762 和前面表 5 的 0.38692 是同一組設定，差別來自種子數和統計方式（這裡是 5 個種子的平均，表 5 是 10 個種子的中位數）。

資料集	處理方式	死群數	占碼本	群大小不均度	測試誤差
DEEP	依質量比例分割（e-means）	47	0.3%	1.194	0.38762
DEEP	從批次重新抽樣	2,343	14.3%	1.423	0.39124
DEEP	關閉	4,313	26.3%	1.647	0.39448
SIFT	依質量比例分割（e-means）	10	0.1%	1.186	0.19623
SIFT	從批次重新抽樣	750	4.6%	1.233	0.19684
SIFT	關閉	2,080	12.7%	1.404	0.19797

最後，作者用四個玩具資料集比較兩者卡在局部極小值的機率，每個各跑 200 個起點，e-means 用 256 筆的小批次。部落格說的「卡住」，在第 1、3、4 例指最後停在它描述的錯誤配置；第 2 例改算最後誤差高出 1% 以上的起點，部落格沒有寫是和哪個解比：

兩團大小懸殊的點、8 群：錯誤配置是兩個質心擠在小團、大團分不夠。Lloyd 有 26% 的起點卡住，e-means 是 3.5%。
3×3 格點的九團、角落較重、10 群：Lloyd 常讓中央那團沒有質心、三個質心擠在一角。誤差高出 1% 以上的起點，Lloyd 有 43%，e-means 是 4%。
正方形四角加一團較重的中心、5 群：錯誤配置是兩個質心落在同一個角，另一個質心停在兩團之間、由兩團共用。Lloyd 卡住 15.5%，e-means 是 0%。
一直線上的五團、5 群：錯誤配置是中間較輕的一團沒有質心，一端的團分到兩個。Lloyd 卡住 46%，e-means 是 0%。

作者的解釋是，小批次的更新比較嘈雜，比較會四處探索，跳得出局部極小值；Lloyd 的誤差每一步都下降，找到一個局部極小值就待在那裡。這些結果都來自玩具資料集。

怎麼用？

部落格給的最短用法如下，x 是 PyTorch 張量；資料是 NumPy 陣列時改用 NumpyEmeans：

from faiss.contrib.e_means import Emeans # NumpyEmeans for NumPy
em = Emeans(d, k, nepochs=T) # T epochs (5 by default)
centroids, labels = em.train(x) # x: a PyTorch tensor (n, d)
# labels: each vector's cluster in the last epoch

除了輪數 nepochs（預設 5），其他超參數都有預設值，主要由前面的縮放定律算出。README 寫明了幾個執行條件：

CPU 上，NumPy 陣列用 Faiss 的 faiss.knn 找最近質心，PyTorch 的 CPU 張量用 PyTorch。README 建議 $n \times k > 10^{10}$ 時改用 GPU；100 萬筆分成 1 萬群，正好碰到這個門檻。
GPU 上，資料要先放到 GPU，e-means 不會替你搬。GPU 核心程式（kernel）依硬體自動選：H100、H200 上的 BF16 資料用 CuTe 寫的核心程式（另外要裝 CUTLASS DSL 等套件），其他較新的 NVIDIA GPU（A100 以上）用 Triton，都不行時退回比較慢的 PyTorch。
GPU 路徑不檢查 NaN 和無限大。README 說，在他們的測試裡，一個無限大的座標讓幾個質心壞掉，回報的誤差卻看起來正常，所以建議先跑 assert torch.isfinite(xg).all()。
資料放不進一張 GPU、質心放不下，或想用多張 GPU 加速時，README 另有逐批餵資料的寫法，以及 DistributedEmeans、EmeansShardedCentroids 兩個多 GPU 類別。

安裝要注意版本。e-means 在 2026 年 11 月 2 日才合進 Faiss 的 main 分支，PyPI 上最新的 faiss-cpu 是 9 月 16 日發布的 1.15.1，那個版本的原始碼裡還沒有 contrib/e_means。README 寫「pip install faiss-cpu 就夠了」，但在下一個版本發布前，要從 GitHub 的 main 分支取得這部分程式碼。

用之前要知道哪些限制？

兩條縮放定律只在 DEEP 上擬合，遷移到其他資料集的證據只有作者挑的四個保留資料集。
加速倍數取決於對手和設定。GPU 上的對手 Flash-KMeans 本身就比單純的 Lloyd 實作快好幾倍；VIBE 的 GPU 比較是 e-means 用 BF16、Flash-KMeans 用 FP16；論文圖 1 說明，Flash-KMeans 只能在單一節點上跑，所以 1 億筆以上作者改用自己的 k-means 實作當基準。CPU 上的 Faiss 則關掉了它預設的抽樣：Faiss 平常每群最多只拿 256 個點訓練，論文的實驗讓 Faiss 讀完全部資料。照預設用 Faiss 的人，實際的時間差會不一樣。
程式碼和論文有幾處細節不同。程式碼的縮放定律用了不同的資料重新擬合：批次的縮放定律用 10 萬到 1,000 萬筆的完整訓練擬合，步長的縮放定律另外納入 1 億筆，擬合時餘弦曲線降到 0，實際執行卻降到 $0.1\,\alpha_0$ 。但在表 2 印出的位數上，係數和論文相同。初始質量（ $2^{-16}$ 對 $10^{-10}$ ）、分割擾動（ $10^{-4}$ 對 BF16 機器精度）也不同。兩版批次縮放定律怎麼選，差得最多：論文在 n 超過 200 萬時改用八分之一的批次，程式碼的預設只看維度，高維資料不論多大都用吞吐量版，和論文大規模實驗的設定不一樣。
實驗都用固定資料集。VQ-VAE 碼本這種分佈會一直移動的情境，EMA 早就在用，這篇論文沒有拿來比。
低維資料要另外看。d ≤ 2 預設關掉死群處理，d ≤ 16 改用小批次；作者也說，影響縮放定律的其實是資料的局部本質維度（local intrinsic dimensionality），而這個量通常不知道。
「10 倍」指達到同樣誤差所需的時間。部落格的網頁標題寫「10x faster k-means at equal loss」，論文標題寫「one-tenth the epochs」，兩者都是在比達到 Lloyd 25 輪誤差所需的輪數和時間。

參考資料

Swann Bessa、Pierre-Emmanuel Mazaré、Gergely Szilvasy、Hugo Touvron、David Picard、Matthijs Douze、Hervé Jégou，〈e-means: outperforming k-means (in one-tenth the epochs)〉，arXiv
.09501（HTML 全文 v1），2026 年 11 月 6 日。
Swann Bessa，〈e-means: outperforming k-means in one-tenth the epochs〉，專案部落格：e-means.github.io。
程式碼：facebookresearch/faiss 的 contrib/e_means（MIT），本文依據 commit fc1095a 的 README.md、base.py 與 e_means.py。