HNSW

Nini 喜歡聽古典音樂。他在 Spotify 上聽完德布西，順手按下「播放類似歌曲」，下一首接上蕭邦的夜曲，氛圍接得剛剛好。Spotify 到底如何在幾十毫秒內從茫茫歌海撈出最像的那幾首？每首歌在 ML 模型眼中是一個 128 維的 embedding vector，「風格相似」就是兩個 vector 之間的距離很近（cosine distance 或 L2 distance）。

暴搜法是跟每一首歌都算一次距離再排序取前 10。那用 B+Tree 呢？B+Tree 很會處理一維的 range query，但 128 維的 vector 沒有自然的排序方式。所以我們退一步：不要求精確的最近鄰，接受 approximate nearest neighbor (ANN)。反正推薦歌曲本來就沒有唯一正解，recall 95% 跟 100% Nini 根本聽不出差別。HNSW 是目前最廣泛使用的 ANN index。

HNSW 的結構

從 Skip List 到 Skip Graph

HNSW 的多層結構靈感來自 skip list。skip list 的底層是完整的 sorted linked list，每個元素以 $1/2$ 的機率出現在上一層。查詢時從最上層開始往右走，持續往下搜，上層的「大步跳躍」讓搜尋從 $O(n)$ 降到 $O(\log n)$ 。

HNSW 的底層包含所有節點，每個節點以指數遞減的機率被分配到更高層。但這裡沒有 sorted order，節點之間的邊不是「下一個」，而是「距離最近的鄰居」。上層節點少、邊跨距大，負責快速跳躍到目標區域；下層節點多、邊跨距小，負責精確的局部搜尋。

Navigable Small World 的性質

HNSW 的 graph 同時具備兩種邊：short-range connection（連接距離很近的鄰居，確保局部搜尋精準）和 long-range connection（連接距離較遠的節點，確保不會卡在局部最優解）。

每個節點的層級是獨立隨機抽出來的，和插入順序無關，但插入順序仍然會塑形 graph 的結構：早期插入而剛好被抽到高層的節點，會主導上層 graph，而且這些早期節點之間的邊往往比較長（當時 graph 中節點少，最近的鄰居本來就遠），後期插入的節點則補上短距離的精細連接。

查詢過程

查詢從最頂層的 entry point 開始。在每一層，執行 greedy search：從目前節點出發，檢查所有鄰居，移動到離 query 最近的那個鄰居，重複直到無法更近為止。然後帶著這個最近的節點下降到下一層，繼續搜尋。

在上層，greedy search 只保留 1 個候選點（ef=1），因為上層節點稀疏，只需要快速定位到大致區域。到了底層，改用 beam search，beam width 等於參數 efSearch。Beam search 同時追蹤多個候選點，每一步擴展所有候選點的鄰居，保留最近的 efSearch 個。搜尋結束後，從這些候選點中取最近的 $k$ 個回傳。

efSearch 越大，探索的候選點越多，recall 越高，但延遲也越長。典型的設定：如果要回傳 top-10，efSearch 通常設在 64 到 200 之間，可以達到 recall 95% 以上。

插入流程

插入新節點時，先隨機決定它的最高層級 $l$ 。層級的分配遵循指數分佈： $l = \lfloor -\ln(\text{uniform}(0,1)) \times m_L \rfloor$ ，其中 $m_L = 1 / \ln(M)$ 。大部分節點只存在於 layer 0，少數節點出現在更高層，和 skip list 的機率分配一樣。

決定好 layer 後，從 entry point 開始往下搜尋。在 layer $l$ 以上的層，用 greedy search（ef=1）快速定位。到了 layer $l$ 以下的每一層，用 beam width = efConstruction 搜尋最近的鄰居，然後和最近的 $M$ 個鄰居建立雙向邊。如果某個鄰居因此超過了最大連接數 $M$ ，就修剪掉它最遠的那條邊。

efConstruction 越大，搜尋到的鄰居品質越高，建出來的 graph 越好。但建構速度會變慢。一般來說 efConstruction 設在 100 到 400，建好之後就不太會改。

三個參數

HNSW 的行為由三個參數控制：

M：每個節點在每一層的最大連接數。 $M$ 越大，graph 的 connectivity 越好，recall 越高，但每個節點要存更多鄰居的 ID，記憶體用量正比於 $M$ 。以 128 維 float32 vector 為例，每個 vector 佔 512 bytes；layer 0 通常設為 $2M$ 個鄰居，若 $M = 16$ 、每個鄰居 ID 用 4 bytes 存，layer 0 的邊列表為 $2M \times 4 = 32 \times 4 = 128$ bytes，大約是 vector 本身大小的 25%。

efConstruction：插入時搜尋候選鄰居的 beam width。只在建構階段使用，查詢時不影響。值越大，graph 品質越好（recall 提升），建構速度越慢。典型值：100 到 400。

efSearch：查詢時的 beam width。讓你在 recall 和 latency 之間即時取捨。efSearch 必須 $\geq k$ （你要回傳的結果數），通常設為 $k$ 的 5 到 20 倍。

記憶體用量估算

以一億個 128 維 float32 vector、 $M = 16$ 為例：

Vector 本身： $10^8 \times 128 \times 4 = 51.2$ GB
edge list（layer 0 用 $2M = 32$ ，平均每節點約 40 個鄰居 ID）： $10^8 \times 40 \times 4 \approx 16$ GB
總共約 67 GB

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

如果你的應用需要在低延遲場景（P99 < 1ms）和高 recall 場景（recall > 99%）之間切換，你會怎麼調整 efSearch 參數？