學習目標

• 理解 近似最近鄰檢索（ANN, Approximate Nearest Neighbor） 的核心概念
• 掌握兩種主流演算法：HNSW（Hierarchical Navigable Small World）與 IVF（Inverted File Index）
• 學會如何在億級數據中做到「秒級檢索」
• 熟悉常見索引優化與效能調校方法

1. 為什麼需要 ANN？

在 RAG 系統中，當企業知識庫規模達到 數百萬甚至上億條文檔向量 時，傳統的 暴力檢索 (Brute-force Search) 需要逐一計算與查詢向量的餘弦相似度，時間複雜度為 O(N)，難以滿足秒級回應需求。

ANN 的目標：在犧牲少量精度的前提下，大幅提升檢索速度。

常見思路：

• 建立索引結構 → 減少需要比較的向量數
• 多階段檢索 → 先粗排，再精排

2. ANN 主流演算法

(1) HNSW — 小世界圖索引

概念：透過建立 分層圖結構，讓查詢從高層快速縮小範圍，再在低層精細檢索。

特點：

• 高查詢精度（接近暴力搜尋）
• 適合線上檢索（低延遲）
• 記憶體消耗相對較大

工作原理：

1. 分層結構：建立多層次的導航圖，上層節點較少，下層節點較多
2. 貪婪搜尋：從上層開始搜尋，逐層向下精細定位
3. 小世界網路：利用小世界現象，任意兩點間距離都很短

(2) IVF — 倒排索引 (Inverted File Index)

概念：先將所有向量 聚類 (k-means) 成若干「桶」（Cluster），檢索時只在最相關的桶內比對。

特點：

• 記憶體友好，適合離線或大規模批處理
• 檢索速度快，但可能損失一些精度
• 支援大規模數據集

工作原理：

1. 訓練階段：使用 k-means 將向量聚類成 nlist 個中心點
2. 索引階段：每個向量分配到最近的聚類中心
3. 查詢階段：找到最近的 nprobe 個聚類中心，只在這些桶中搜尋

實務上，很多企業會 結合 HNSW + IVF，取兩者優點。

3. ANN 可視化直觀理解

假設有 1000 萬份文檔向量：

• 暴力搜尋：像是把每份文檔都翻一遍 → 太慢
• IVF：先把文檔分成 1000 個「櫃子」，只翻最相關的 3 個櫃子
• HNSW：先用大地圖（高層）找到一個大致的區域，再用小地圖（低層）逐步精細定位

這樣就能在 毫秒級 找到 Top-k 相似文檔。

4. 演算法比較表

5. 效能調校技巧

IVF 參數調整：

• nlist（桶數量）：增加可提升精度，但會增加記憶體使用
• nprobe（查詢桶數）：增加可提升召回率，但會降低速度

HNSW 參數調整：

• M（節點連結數）：影響圖的連通性和查詢精度
• efSearch（搜索深度）：影響查詢精度和速度的平衡
• efConstruction：建索引時的搜索深度

進階優化策略：

• 混合策略：先用 IVF 粗篩，再用 HNSW 精排
• 硬體加速：GPU 版本 FAISS、量化（PQ, Product Quantization）
• 分散式部署：將索引分片到多個節點
• 快取機制：熱門查詢結果快取

6. 實務選型指南

數據規模 < 10萬
├─ 使用暴力搜尋（簡單高效）

數據規模 10萬 - 1000萬
├─ 線上查詢頻繁 → HNSW
└─ 批次查詢為主 → IVF

數據規模 > 1000萬
├─ 高精度要求 → HNSW + 量化
├─ 成本敏感 → IVF + PQ
└─ 混合需求 → 多索引並行

想想看

1. 在企業中，如果知識庫向量數量達到 1 億，你會如何在 速度與精度 之間做取捨？

2. 對於需要 高精度（如法務文件） 與 高效率（如客服 FAQ） 的場景，應如何選擇 ANN 演算法？