拆解 RAG 的核心引擎：圖解 HNSW 演算法 (Hierarchical Navigable Small World)
前言：RAG 背後的黑魔法
最近在研究 RAG (Retrieval-Augmented Generation) 架構時，我們常把文件轉成 Vector 存入 Elasticsearch。當使用者提問時，系統能瞬間從百萬筆資料中撈出「語意最相似」的段落。
這背後的功臣不是傳統的 B-Tree，而是 HNSW (Hierarchical Navigable Small World)。
很多人知道它很快，但很少人知道它為什麼快。簡單來說，HNSW 是 「跳表 (Skip List)」 與 「小世界圖 (Small World Graph)」 的完美結合。
這篇文章將帶你拆解 HNSW 的三大核心機制：分層、鄰居、搜尋。
1. 分層結構：隨機打造的「高鐵路網」
HNSW 的第一個字母 H (Hierarchical) 代表分層。你可以把它想像成一個交通運輸網。
- Layer 0 (平面道路)： 這是最底層，包含 100% 的資料點。這裡非常擁擠，如果要在這裡搜尋，就像在市區開車，紅綠燈多，速度慢。
- Layer 1 (快速道路)： 這裡的點比較少，可以快速跨區。
- Layer 2 (高速鐵路)： 點更少，距離更遠。
- Top Layer (機場)： 最高層，只有極少數的節點，視野最廣。
誰有資格住樓上？(隨機性)
你可能會問：「是不是比較重要的點才會在第一層？」 答案出乎意料：不，完全是運氣 (Random)。
HNSW 使用一個機率函數（通常是指數衰減）來決定每個點的「最高樓層」。
- 每個點一定會在 Layer 0。
- 擲一次硬幣，有機會升到 Layer 1。
- 再擲一次，有機會升到 Layer 2。
這種隨機性反而保證了高層節點在空間分佈上的均勻，避免了「富者越富」的聚集效應，讓長距離跳躍更有效率。
2. 鄰居選擇：拒絕同溫層的「多樣性」
決定了樓層後，每個點都要開始找鄰居（建立連線 Edge）。這決定了這張圖好不好走。 這對應到 NSW (Navigable Small World) 的概念。
建立連線的流程
當一個新節點插入時，它不會隨便亂連，它有兩個篩選標準：
-
海選 (ef_construction)： 系統會先在圖上搜尋，找出離自己最近的 $K$ 個候選人。這就是所謂的「先找 100 多人」。
-
精選 (Heuristic / Diversity)： 如果只連「最近」的鄰居，會導致所有連線都擠在一起（形成聚落/同溫層），搜尋時很難跨出去。
HNSW 使用啟發式算法來強制多樣性：
三角形法則： 如果候選鄰居 B 離我很近，但 B 離我的鄰居 A 更近，那我可能就會捨棄 B。
因為我可以透過 A 走到 B，不需要浪費珍貴的連線配額 (Parameter
m)。系統會傾向選擇一個「稍微遠一點，但在不同方向」的點作為鄰居。
結論： 你的鄰居不一定是你身邊最近的人，而是能幫你通往不同世界的人。
3. 搜尋流程：從高空跳傘 (Greedy Search)
有了分層和鄰居，搜尋過程就像是一場高空跳傘。
假設我們要搜尋目標 Vector Q：
- Enter Point (Top Layer)： 我們從最高層的入口點開始。
- Greedy Search (貪婪移動)： 在這一層，我看著我的鄰居，誰離 Q 最近，我就跳到誰身上。直到身邊的鄰居都比我離 Q 還遠，我就達到了這一層的「局部最佳點」。
- Descend (下樓)： 我把目前的點當作下一層的起點，往下降一層。
- Repeat： 重複貪婪移動 -> 下樓。
- Layer 0 (決戰)： 到了最底層，這裡有所有的細節。我再做最後一次精細的搜尋，找到真正的 Top K。
這種方式讓搜尋複雜度從 $O(N)$ 降到了 $O(\log N)$，這就是為什麼它能在毫秒級內搜尋百萬向量的原因。
4. SRE 視角：Elasticsearch 參數調優
懂了原理，我們來看 Elasticsearch (kNN Search) 裡面的參數對應，這直接影響你的 RAG 效能與 寫入速度。
| ES 參數 / 概念 | HNSW 參數 | 意義 | SRE 調優建議 |
|---|---|---|---|
| m | m | 每個點的最大鄰居數。 | 記憶體殺手。 預設 16。數值越大，圖越密集，查詢越準確，但 RAM 吃越兇。通常 16~24 就夠用。 |
| ef_construction | ef_construction | 建圖時的視野 (海選數量)。 | CPU 殺手。 數值越大，建立索引越慢，但圖的品質越好（高速公路規劃越完善）。如果你重視查詢準確度，可調高至 100~512。 |
| num_candidates | ef_search | 查詢時的視野。 | Latency 殺手。 這是你在 Query DSL 裡下的參數。數值越高，召回率 (Recall) 越高，但 QPS 下降。通常設為 Top K 的 1.5 ~ 2 倍即可。 |
ef_construction
- 擴展視野 (Expansion)： 當一個新節點進來時，系統會在圖上瘋狂搜尋，試圖找到當下離這個新節點最近的點。它會維持一個 候選名單 (Candidate Queue)，這個名單的長度就是
ef_construction。 - 填滿名單： 系統會不斷探索鄰居的鄰居，只要發現更近的，就塞進這個名單，把遠的踢出去。直到名單裡塞滿了
ef_construction(例如 100) 個「目前已知最近」的節點。 - 縮減錄取 (Shrinking)： 最後，系統從這 100 個候選人中，根據「距離 + 多樣性」算法，精選出
m(例如 16) 個最好的節點，建立正式連線 (Edge)。
2. 詳細解析：ef_construction (建圖時的暫存區)
想像你要組建一支 16 人 (m) 的籃球隊。
-
m= 16 (最終錄取人數)： 這是硬體限制。你的節點記憶體只能存 16 條連線。如果太多，記憶體會爆炸。 -
ef_construction= 100 (面試人數)： 為了找到這最強的 16 人，你不能只看前 16 個來應徵的人（這樣可能錯過高手）。 你需要把「觀察名單」擴大到 100 人。- 在建圖過程中，你會在心裡保留 100 個高手的名單。
- 透過這 100 人，再去問他們「有沒有認識更強的人？」，有的話就更新這份名單。
- 搜尋結束後，你從這 100 人中挑出最完美的 16 人 (
m) 簽約。
為什麼它是 CPU 殺手？
- 如果
ef_construction設為 100，你要計算距離、比對、排序 100 個點。 - 如果設為 500，你要處理 500 個點。建立 Index 的時間會變長，但因為你看過更多候選人，最後挑出來的
m個鄰居會「品質更好」（更準確的捷徑）。
3. 詳細解析：num_candidates (查詢時的暫存區)
這是在 搜尋 (Search) 階段用的，跟建圖無關，但邏輯一模一樣。 在 Elasticsearch 語法中，這對應 kNN search 的 num_candidates (底層對應 HNSW 的 ef_search)。
想像你要在剛才建好的圖裡面，找 Top 10 (k) 最像的結果。
-
k= 10 (你要的結果)： 最終回傳給使用者的數量。 -
num_candidates= 100 (搜尋時的視野)：- 如果你只在此刻的候選名單保留 10 個點，很容易陷入「局部最佳解」（走到一個死胡同，以為自己到了，其實隔壁巷子還有更近的）。
- 所以你告訴系統：「幫我保持 100 個 候選人在佇列裡」。
- 系統會邊走邊看，確保看過夠多的點，最後才從這 100 個裡面回傳前 10 名給你。
為什麼它是 Latency 殺手？
- 數值越大，系統在圖上「逛」的時間越久，比較不會錯過正確答案（Recall 變高）。
- 但代價就是逛越久，回應時間 (Latency) 就越慢。
總結
HNSW 的哲學非常迷人：
- 分層 解決了「視野」問題。
- 隨機性 解決了「分佈」問題。
- 多樣性連線 解決了「路徑」問題。
理解這些，下次當你覺得 Vector Search 回應太慢或結果不準時，你就知道該去調整 m 還是 ef_construction 了。