← 回首頁

近似最近鄰 HNSW(多層可導覽小世界圖)

想在幾十億筆資料裡找出跟手上這筆「最像」的幾個——例如上億張圖片中最接近的那幾張——一個一個比對慢到不能用。 HNSW的點子像看地圖找餐廳:先攤開只畫大城市的高速公路圖、一次跳很遠鎖定大概區域,再換成街道圖慢慢走到 門口。它把資料排成好幾層,高層稀疏、一跳跳得遠,底層綿密、走得細。代價是只保證找到「幾乎最近」而非「絕對最近」 ——用一點點準確度換巨大的速度。下面你會看到這個取捨具體長什麼樣子。

HNSW(Hierarchical Navigable Small World)為每個點抽一個隨機層數,層數越高的點越少、越稀疏;插入新點時先在 高層粗略貪婪下降定位大致方向,再逐層往下精煉、與該層最近的 M 個候選互連(新增邊後立刻對既有鄰居剪到 M 個, 維持鄰接對稱)。查詢時同樣先在高層貪婪下降快速定位,到底層(層 0)才切換成 ef 搜尋——維護一個大小 ef 的候選 結果集,逐一擴展最有希望的候選,ef 越大代表保留越多候選、越不容易錯過真正最近鄰,代價是多訪問幾個點。整個 結構是 skip list(多層跳躍)圖走訪(貪婪最近鄰擴展)的合體,用「查得快」換「不保證找到真正 最近鄰」——本頁固定資料集刻意設計出一個查詢範例,具體展示這個代價長什麼樣子。

為什麼 AI 時代重要

向量資料庫(pgvector、Milvus、Faiss、Pinecone 等)與 RAG(檢索增強生成)系統的核心索引結構正是 HNSW:把文件 /圖片/程式碼片段編碼成向量後,要在十億級向量中找出與查詢向量最相似的少數幾個,暴力全掃 O(n) 在這種規模下完全 不可行,HNSW 用多層圖 + 貪婪導覽把查詢代價降到近似 O(log n)——「近似」二字是關鍵:它不保證找到真正的最近鄰, 只保證機率上很接近,這正是本頁要誠實示範的取捨。

它是 SkipList 與圖走訪的合體

HNSW 的多層結構直接承自 Skip List 跳躍表:高層點稀疏、 一跳跳得遠,低層點密集、走得細,用隨機層高換取對數級的查找深度;而每層內部「檢查目前點所有鄰居、換到更近者」 的貪婪下降,本質是圖走訪的貪婪法變體——只往更近的方向走, 不像 BFS/DFS 保證走遍全圖或保證找到最短路,換得速度但可能卡在局部最優、錯過全域最近的點。

HNSW(多層圖建構 + 貪婪查詢 + 暴力真值對照)

建構:逐點插入,先依 LCG(線性同餘產生器,burn-in 3 步)抽層數(幾何分佈,u<0.5 升層,本頁 cap=2,共 0/1/2 三層);若圖為空,該點直接成為 entry point。否則從目前 entry point 出發,先在高於自己層數的各層只 找路不連邊(新點尚不存在於這些層),再從自己層數往下逐層插入自己、貪婪精煉目前位置,並與候選中離自己最近的 M 個點互連——新增邊後若既有點鄰居數超過 M,立刻剪到最近的 M 個(雙向剪除,鄰接恆對稱,本頁 M=2)。 查詢:從 entry point 於高層貪婪下降,到層 0 切換 ef 搜尋,並與獨立全掃的暴力最近鄰同幀對照。

固定資料:2D 點 10 個(座標 0..10 整數)[1,2] [3,1] [5,3] [7,2] [9,1] [2,6] [4,8] [6,7] [8,8] [5,5]; M=2;LCG 種子 seed=22;查詢點 Q1=[7,3](貪婪可達真最近鄰)、Q2=[6,0](實測設計:貪婪下降陷入局部最優, ef=1 時漏掉真最近鄰、ef=2 時找回)。四輪查詢固定跑 Q1(ef=1) → Q1(ef=2) → Q2(ef=1) → Q2(ef=2)。
累計距離計算次數(全域 visits,含建構+全部查詢):0 階段:declare-level
多層帶狀圖:由上而下依序為層 2(頂層,最少點)→ 層 1 → 層 0(底層,含全部 10 個點)—— 上面的帶就是高層;同一點跨層 x 座標不變,跨層之間的垂直邊代表「這個點同時存在於相鄰兩層」, 層內邊代表該層的近鄰連結。橘色(current)=當下處理/走訪節點;綠色(finalized)=連邊完成/entry point 建立/查詢終幀的 HNSW 結果;藍色外框(frontier)=新連上的鄰居,或查詢終幀漏標時另外標出的 「暴力真最近鄰」;紫色(visited)=本次查詢累積走訪過的節點。節點上方數字為其所在層數(L0/L1/L2)。
誠實揭露——近似可能漏掉真最近鄰:Q2([6,0])在 ef=1(純貪婪,等同只信任目前最近候選)時會 卡在局部最優、回傳的並非全域真正最近鄰;把 ef 提高到 2(保留較多候選繼續擴展)才找回真正最近鄰—— ef 越大越接近精確解,代價是多訪問幾個點,下方查詢對照表會逐列列出兩者差異,漏標列會醒目標紅。
教學縮尺:本頁僅 10 個點、M=2,暴力全掃只需 10 次距離計算,HNSW 反而不見得更快—— HNSW 的優勢要在十億級向量、M/ef 遠大於本例的生產設定下才會顯現,這裡看不出速度優勢,只能看出 「近似 vs 精確」的取捨長什麼樣子。
簡化裁剪策略:本頁連邊採簡化版「取離插入點最近的 M 個候選」啟發式(候選池只看目前搜尋到 的點與其直接鄰居),並非 HNSW 論文完整的 heuristic selection(論文版本會額外考慮候選之間的相對距離, 避免同側過度密集連邊),教學上足以展示多層 + 貪婪的核心機制,但非論文完整實作。

建構進度(insertProgress)

(尚未開始)

查詢對照表(HNSW 結果 vs 暴力全掃真值)

查詢efHNSW 結果暴力 NNHNSW visits暴力 visits漏標

已執行操作紀錄(opLog)

(空)