k-means 的 25 遍，可以只讀 2 遍

Faiss 的 k-means 預設跑 25 輪、每輪把訓練向量完整掃一遍；Meta FAIR 的 e-means 改用指數移動平均加小批次更新，1.4–2.6 輪就追平同樣的損失。這篇講它換掉了哪幾件事、10 到 45 倍是在比什麼，以及你的索引什麼時候才真的會有感。

發佈於 2026年11月14日15 分鐘Read in English

clusteringfaissvector-searchperformance

數字來自 arXiv 2611.09501v1（2026-11-06，FAIR at Meta）、官方專案頁與 faiss 原始碼。我們沒有獨立重跑論文實驗；文中那個 120 點的小模擬是我們自己跑的，設定寫在圖 2 前面。

先確認這筆錢你付過了

你在做 RAG，或做資料去重。文件進來、切成 chunk、算成向量，然後某一支排程把它們聚成叢集、寫成索引檔。

重建一次索引，最慢的往往就是這一步。它用的還是 1957 年的演算法，預設要你把資料掃 25 遍。這篇要講的是，同樣的損失，有沒有機會只掃 2 遍。

有，但只在某些條件下成立。FAIR 的 e-means 用 1.4–2.6 輪追平同樣的損失，也已經進了 faiss 正式版。它加速的是建置、不是查詢，而且有規模門檻。這篇會把條件畫清楚。

讀完你會多一個問題可以問：「那你們重建索引要多久？」

它藏在建置流程的中間

k-means 不是冷門演算法，它是這一堆東西的底層：

應用	k-means 在哪	你什麼時候付這筆錢
IVF 向量索引	粗量化：先分成大類，查詢時只進對應的桶	建索引、換模型、補資料
乘積量化（PQ）	把向量切段，每一段各自分群一次	同上
VQ-VAE、神經音訊編碼	碼簿學習（每個叢集配一個代表向量）	訓練、換資料集
資料去重、異常偵測	聚類找重複與離群	匯入、清洗
客戶分群、影像分群	就是它本身	每次分析

共同的形狀是：它在離線，不在查詢路徑上。

如圖 1，一支索引的壽命裡，左半是建置、右半是查詢。查詢只讀一次索引；建置要把向量掃過很多遍。你每天感覺到的延遲在右半，真正吃掉時間的在左半。

圖 1：左半是建置、右半是查詢；k-means 那格標著 25 遍掃描。

粗算一下：以 100 萬筆、768 維、k = 4,096 為例（fp32），一趟掃描大約 3.1 GB。Faiss 的 k-means 預設跑 25 輪，就是 77 GB 上下的讀取，還不含距離計算與寫入。這個數字會隨維度、資料型別變動，但量級就是這樣。

它還是 1957 年那支 Lloyd

Lloyd 的 k-means 只有兩步：把每個點分給最近的質心；把每個質心移到它那群點的平均位置。重複到不再變動。

它保證收斂——收到局部最小值，不是全域。這個保證從 1957 年貝爾實驗室的技術備忘錄一路用到現在，正式發表是 1982 年。

要最小化的東西長這樣：

\mathrm{MSE}(X, C) = \frac{1}{n} \sum_{i=1}^{n} \left\| x_i - c_{a(i)} \right\|^2, \qquad a(i) = \arg\min_j \left\| x_i - c_j \right\|^2

Faiss 的 Kmeans 預設 niter = 25，每一輪都是一次完整分配。原始碼裡還有一個常被忽略的角落：max_points_per_centroid = 256。當 n 遠大於 k 時，Faiss 會先抽樣到每個叢集最多 256 點。前面那個例子（100 萬點配 4,096 個叢集）剛好還在門檻內（256 × 4,096 ≈ 105 萬）。所以你掃的就是全部。

每一輪的成本是 O(n · k · d)，而且是隨機讀取。這是記憶體頻寬在吃時間，不是浮點運算。25 輪不是幻覺，是真的把資料從頭到尾走了 25 次。這裡的「輪」就是 epoch：資料完整跑過一遍。

那為什麼沒被換掉？小批次版本 1967 年就有（MacQueen）。2010 年 Sculley 的 web-scale 版本也在跑。它們每輪只讀一小批、快得多，代價是誤差偏高，而且你得自己調批次大小與學習率。對大部分場景，「慢，但不用想」是一個很合理的預設。

做法	每輪讀多少	統計量怎麼更新	代價
Lloyd（全量，Faiss 預設）	全部 n 點	每輪重算精確均值	慢；預設 25 輪
MacQueen、Sculley（小批次）	一小批	累加，從不忘記	快，但早期錯誤的分配會一直投票
e-means	一小批	指數移動平均，舊分配衰減	快；參數由標度律算

e-means 換掉的四件事

論文的做法叫 e-means，來自 Meta FAIR。論文標題直接寫著「one-tenth the epochs」。作者名單裡有 Matthijs Douze 與 Hervé Jégou，兩人是 Faiss 的作者；再加上 Hugo Touvron。這是同一個團隊在挑戰自己的預設值。

它沒有發明新的損失函數——目標還是上面那條 MSE，改的是「質心怎麼更新」。

第一件事，統計量改成指數移動平均。

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

n_j、s_j 是這一小批點裡分到第 j 叢集的數量與總和。α 決定「忘得多快」：α 大，最近幾批說話；α 小，歷史平均。舊的分配不是被刪掉，是被打折。

MacQueen 的更新是 S ← S + s，永不忘記。訓練早期質心位置很差，那時候分出來的標籤多半是錯的；但它們在後面每一輪都還有完整的一票，會把質心拖住。e-means 給它們一個衰減係數，等於「慢慢忘掉早期的錯誤判斷」。

第二件事，α 不是常數。 它從較大的值開始，沿著 cosine 曲線降到初始值的十分之一。先降快、後降慢，像一條降溫曲線，後期就越來越穩。

第三件事，死叢集要救。 小批次更新很容易出現「沒有任何點分給它」的質心。叢集數看起來是 k，實際能用的不到 k。e-means 每五批檢查一次。把低於平均計數 10% 的叢集重新指派：挑一顆大的，拆成兩顆，補上那個空位。Faiss 本來就有這個做法。影響有多大？論文自己的 ablation（一次關掉一個元件，看損失掉多少）拆得很細：

資料集	復活策略	死叢集	佔碼簿	測試 MSE
DEEP	按大小分裂	47	0.3%	0.3876
DEEP	從批次隨機抽點	2,343	14.3%	0.3912
DEEP	不救	4,313	26.3%	0.3945

100 萬個向量、k = 16,384、5 個 epoch、5 個種子平均；SIFT 上的差距類似。關掉復活，四分之一的叢集是空的。其他幾個元件（初始化、cosine、finalization）只差零點幾個百分點。四件事不是平權的，影響最大的是這一件。

第四件事，參數不要你猜。 批次大小與初始步長由 (n, k, T) 的標度律（用問題規模反推參數的經驗公式）算出來。論文量到的超參 regret 約 0.07%，你不用掃。

這裡要小心一個字面陷阱：「不用調參」指的是相對於 Lloyd 沒有多出新的旋鈕。k 還是你選的，epoch 數也是（預設 5），只是那兩個原本最難調的內部參數被公式接走了。

還有一個設計選擇值得講：他們不用梯度下降。專案頁的說法是，學習率一大，梯度更新會衝過頭。EMA 則保證質心一定落在「曾經被分配到這個叢集的點」的凸包裡面——不是當前那一批，是歷史。

而且 Lloyd 其實是 e-means 的特例。批次設成全部 n、α 設成 1，一次 e-means 更新就等於一次 Lloyd。所以兩者不是兩個世界，是同一條公式的兩端——論文發現，那一端剛好是最差的參數組合。

還有一個實務上的小設計。訓練結束時，最後一批的分配可以拿來重算一次精確均值（last-epoch-mean）。這會讓訓練集損失再降一點。如果你在意的是新資料上的表現，就用另一組慢速 EMA 收尾。兩者成本都可忽略，等於一次訓練能產兩組質心，看你拿質心去服務誰。

最後是這篇最反直覺的地方——雜訊有用。

Lloyd 每輪的損失只會下降，所以它一旦走進一個局部最小值，就沒有動力出來。小批次更新每次只看一小部分，梯度有雜訊。論文自己的解釋是：正是這個雜訊，會把質心推離那些「看起來收斂了、其實分錯了」的配置。他們用 200 個種子在玩具資料上重跑，e-means 掉進病態配置的機率明顯較低。

如圖 2，這是我們自己跑的小型模擬，不是論文原圖。設定是三個高斯團、每團 40 點、固定亂數種子、k = 3、同一組初始中心（刻意放壞）。e-means 用批次 12、初始 α = 0.35 加 cosine 衰減、2.5 個 epoch；Lloyd 則是每輪全量。

左邊的 Lloyd 第 8 輪就幾乎不動，再跑到 33 輪仍停在 MSE 5.39。兩顆質心擠在同一團，另一顆落在兩團中間。右邊的 e-means 用 25 次更新收到 1.28，一顆對一團。

圖 2：同一組資料、同一組初始中心。左邊的兩顆擠在同一團，右邊的三顆各對到一團（我們自己的模擬）。

這個例子只說明「同一組初始值下，兩種更新方式會走到不同的地方」，不是保證。論文的結論是機率，不是每次都能逃出來。

「快 10 倍」是在比什麼

先講對照條件，這是全文最容易被誤讀的地方：

基準是「e-means 跑 1.4–2.6 輪」對「Lloyd 跑 25 輪」的損失。 不是「Lloyd 跑到完全收斂」。

換句話說，基準是「大家平常就跑 25 輪」的那個點。Lloyd 再跑下去損失還會降一點，差距會縮小。

項目	數字	條件與出處
追平 Lloyd 跑 25 輪所需輪數	1.4–2.6	論文摘要；多個嵌入資料集
GPU 加速	10–45×	對 Flash-KMeans、H100；論文摘要
CPU 加速	8–15×	對 Faiss；官方專案頁
最大規模	100 億點、1,600 萬叢集，2.5 輪	DINO10B：論文的 100 億筆 DINO 特徵資料集
社群量到的 Lloyd 迭代次數	19–229 輪	scikit-learn issue #35383；社群實測，不是論文

最後一列不是在說「25 輪不夠」。它是在說，Lloyd 的收斂輪數本來就浮動——社群那邊量到 19 到 229 輪。所以重點不是 25 這個數字，是「每一輪都是一次全量掃描」。25 只是預設值，不是物理常數。

還有一個陷阱：輪數不等於時間。 如果只算資料掃過幾遍，2.5 輪對 25 輪大約是 10 倍。實際的 wall-clock 卻是 10–45 倍。我的理解是，差距有一部分來自小批次更容易吃滿 GPU；論文沒有把 10–45 倍拆到「哪一段省下來」這一層。

保守的講法：大約 10 倍。45 倍是特定設定、特定 GPU、對特定的對照實作。任何寫成「k-means 快 45 倍」的句子，都要帶著這三個條件。

順帶說明一個容易混掉的細節。摘要寫的是 GPU 10–45 倍（對 Flash-KMeans）。專案頁另外寫 CPU 8–15 倍（對 Faiss）。兩個數字量的對象不同，不要互換、也不要相加。

我認為 GPU 的倍數比 CPU 大，是因為差距有一部分來自「小批次能不能吃滿硬體」。GPU 核心多、記憶體頻寬高，同樣的批次更容易被排滿。CPU 那組（8–15 倍）反而對一般讀者更有參考價值——多數人手上沒有 H100。

它進正式版了嗎？進了。faiss 1.16.0（2026-11-10 發布）包含 faiss.contrib.e_means；PyPI 的 faiss-cpu 也已經是 1.16.0。用法五行：

from faiss.contrib.e_means import Emeans

em = Emeans(d, k, nepochs=5)
centroids, labels = em.train(x)   # x 是 PyTorch tensor (n, d)

還沒有的東西：獨立複現。論文很新（11 月 6 日），有釋出複現腳本與基準資料，但目前只有作者自己的數字。

另外它終究是隨機演算法：同一個資料集、不同的種子，收斂到的解會不一樣。論文的數字是多個資料集、多個設定的結果，不是每一次執行都會剛好落在 1.4 輪。

所以你的索引會變快嗎

先說結論：它加速的是索引建置，不是查詢。 如果你的問題是「檢索太慢」，這篇幫不上忙。那個要換 HNSW（一種不用先分群的圖索引）、量化，或換一顆更小的模型。

有感的條件大概長這樣：

你的情況	建議
幾千份文件的 RAG，重建只要幾秒	先別動，快 10 倍對你沒差
10 萬點以上、k 上千、每次重建要等	值得做一次 A/B
重建頻繁（每天或每次換模型）	值得換，先看 CPU 路徑
用 HNSW、不需要粗量化	這一步不存在，跳過
想加速的是推論	換錯題目了

還有一個常被忽略的前提：GPU 那條路要 H100 或 H200 等級的卡。還要對應的 GPU 核心函式庫（CuTe 或 Triton 後端），以及對得上版本的 CUTLASS、QuACK。CPU 那條路只要 faiss 本身，反而是多數人實際能跑的。專案頁的 8–15 倍就是 CPU 對 Faiss。

代價也要寫清楚：新 API 要驗，換初始化之後 recall 要重測。近似解本來就不保證全域最優（Lloyd 也不保證）。快 10 倍換到的是重建時間，不是免費的品質。

要驗的話，準備一份查詢集，跟暴力搜尋（Flat）的 top-10 對答案算 recall@10。只看 MSE 會漏掉檢索品質這一塊。

明天可以做的三件事

第一，量一次重建。 記五個數字：n、k、niter、wall-clock、最終 MSE。沒有這五個，任何「要不要換」都是猜的。

import numpy as np, faiss, time

x = np.ascontiguousarray(x, dtype='float32')
flat = faiss.IndexFlatL2(x.shape[1])   # 只用來算最終損失

t0 = time.perf_counter()
km = faiss.Kmeans(x.shape[1], k, niter=25)
km.train(x)
secs = time.perf_counter() - t0

flat.add(km.centroids)
D, _ = flat.search(x, 1)
print(f"{secs:.1f}s  MSE={D.mean():.3f}")

第二，把 niter 降下來看看。 這是最便宜的實驗：同一份資料，niter 跑 25、10、5，看 MSE 差多少。如果 10 輪的損失只差一點，你的預設值就多付了 1.5 倍的掃描。

for niter in (25, 10, 5):
    km = faiss.Kmeans(x.shape[1], k, niter=niter)
    km.train(x)
    flat.reset()
    flat.add(km.centroids)
    D, _ = flat.search(x, 1)
    print(niter, f"{D.mean():.3f}")

第三，規模夠大才換 e-means。 用同一份資料、同一組初始化，比 wall-clock 與最終 MSE；有索引的話再比 recall@10。CPU 那條路不用 GPU，適合先做。

最後回到那個 25。它不是物理常數，是一個預設值。這篇的重點不是叫你換掉 k-means，而是提醒你：那個 25 可以量、可以調，也可以被換掉。而提案換掉它的，是 Faiss 自己的作者。