RAG 為何能瞬間找到答案？向量數據庫告訴你

發布于 2025-8-27 06:39

瀏覽

0收藏

了解 Hierarchical Navigable Small World (HNSW) 算法如何為當今的 RAG 系統提供動力

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

Retrieval-Augmented Generation (RAG) 是為 Large Language Models (LLMs) 添加外部知識的重要工具。

幾乎每個 RAG 系統都包含一個向量數據庫，用于執行 semantic search。在這種搜索中，存儲在向量數據庫中的 document embeddings 會與用戶的 query embedding 進行比較。

一個基本的 RAG 系統包括一個 embedding model、一個 vector database 和一個 LLM。文檔的 embeddings 會提前存儲（離線）。當你提出一個問題時，輸入會被嵌入并與存儲的 embeddings 進行匹配。最佳結果會被發送到 LLM，其中 retriever（由 embedding model 和數據庫組合而成）協助 generator（LLM）。一個基本的 RAG 系統包括一個 embedding model、一個 vector database 和一個 LLM。向量數據庫用于找到與查詢匹配的 top-K 文檔。

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

實際上，將查詢向量與數據庫中數百萬個 embedding vectors 進行比較以找到完美匹配是非常慢的。為了更快，這些向量數據庫通常返回近似匹配的結果。

讓我們更深入地看看向量數據庫是如何工作的，并探索 Hierarchical Navigable Small World (HNSW) 搜索算法，它為當今許多 RAG 系統提供了動力。

基本 Semantic Search

在 semantic search 中，embedding model 將文本轉換為一個 dense vector，捕捉文本的含義。

通過使用相同的 embedding model 將查詢和文檔都轉換為向量，我們可以通過識別 query vector 的 nearest neighbors 來執行 semantic search。這個過程被稱為 K-nearest neighbors (KNN) 搜索。

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

在 RAG 系統中，retriever 的任務是找到與用戶查詢最相似的文檔。在這個簡單示例中，文檔1、5和7是從10個文檔中找到的三個最接近的匹配項。一個 RAG 系統中的基本 semantic search 示例。黑點表示使用 cosine distance 度量時，與查詢最接近的三個匹配項（共10個文檔）。圖片由作者提供。

為了找到 nearest neighbors，我們需要測量兩個向量之間的距離。通常使用的距離度量是 cosine distance，它關注兩個向量之間的角度，或 dot product。

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

cosine distance 公式是 1 減去兩個向量 v 和 w 的 cosine similarity。圖片由作者提供。

然后，我們按距離排序并選擇 K 個最接近的匹配項。

然而，搜索所需的計算量隨著向量數據庫中的條目數量線性增加。例如，對于15個文檔，需要計算15個距離。

如果數據庫包含數百萬個文檔，我們每次查詢時都需要計算數百萬個距離。

為了更高效地解決這個問題，我們可以使用 approximate nearest neighbor (ANN) 搜索。

ANN 比 KNN 高效得多。然而，顧名思義，這些算法不保證返回最接近的匹配項。但在實踐中，它們通常已經足夠接近。

Navigable Small World (NSW)

Navigable Small World (NSW) 算法 [2] 是一種基于圖的 ANN 算法。圖是一種由 edges 和 vertices 組成的數據類型。

首先，我們一次性計算所有文檔之間的距離。接下來，我們構建一個 proximity graph，為數據庫中的每個文檔創建一個 vertex。每個文檔通過 edge 與其幾個最近的鄰居相連。超參數 M 決定每個文檔的最大連接數。

使用上面的例子，以下是一個 NSW proximity graph 的樣子：

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

一個 NSW proximity graph，展示文檔作為 vertices，通過對應距離的 edges 相互連接。一個包含10個文檔的 NSW proximity graph，每個 vertex 最多有 M=3 個 edges。圖片由作者提供。

在構建圖之后（只需做一次），它就可以用于高效搜索。NSW 是一種貪婪算法，在每一步都做出局部最優選擇。

NSW 的核心思想是，每個文檔都可以通過幾次“跳躍”從其他任何文檔到達。

為了找到與查詢最接近的文檔，我們隨機選擇一個文檔作為起點，計算查詢與當前文檔的所有連接鄰居之間的距離。然后選擇距離最短的文檔。

如果查詢與所選文檔的距離小于查詢與當前文檔的距離，我們就移動到所選文檔。

然后，算法重復進行。如果查詢與當前文檔的距離小于與所有鄰居的距離，那么就找到了一個局部最小值，并返回 top-K 文檔。

NSW 算法針對一個示例查詢是這樣的：

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

給定一個查詢和一個隨機選擇的起點，算法從節點9到7，再到5，然后到3。一個貪婪搜索的示例，包含一個查詢和一個隨機選擇的起點。圖片由作者提供。

我們還可以用不同的隨機起點重復整個過程，以找到更好的解決方案。

Hierarchical Navigable Small World (HNSW)

HNSW 通過添加 hierarchical layers 改進了 NSW，加快了搜索算法的速度 [3]。

HNSW 使用多層圖。最低層（layer 0）包含完整的 NSW 圖和所有文檔。

在 HNSW 中，創建多個層，每一層進一步減少文檔數量。在一個簡單示例中，我們可能只使用兩層，如下圖所示。

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

一個包含 HNSW layer 0（完整圖）和 layer 1（僅兩個 vertices）的 Python 子圖。一個包含兩層和10個文檔的 HNSW 圖。圖片由作者提供。

搜索算法從最高層開始，運行方式類似于 NSW。在給定層中找到局部最小值后，我們將該文檔作為下一較低層的起點。

最終，我們到達 layer 0 并返回 top-K 文檔。

這個過程就像最初放大以在最高層找到一個粗略匹配。然后，我們逐層縮小以找到更好的匹配。

雖然 HNSW 在搜索時比 KNN 快得多，但它需要大量計算來創建多層 proximity graph。在插入、更新或刪除數據庫中的文檔時，需要額外的計算來更新或重新創建圖。

此外，基于圖的搜索算法（如 HNSW）需要更多內存來存儲圖結構和向量 embeddings。

HNSW 受到許多流行向量數據庫的支持，如 Chroma、Qdrant、Weaviate、Milvus、Faiss、Vespa、Pinecone 和 Elasticsearch，通常作為 semantic search 的默認 ANN 算法。

HNSW 在實踐中的應用

HNSW 通常是大多數向量數據庫的默認設置。這使得它在實踐中非常易于使用。

例如，我們將使用 Python 中的開源向量數據庫 Chroma，可以通過命令 ??pip install chromadb?? 安裝。

首先，創建一個本地 Chroma 數據庫，然后為你的數據創建一個新 collection。在這里，我們可以明確設置 HNSW 算法的超參數，例如距離度量 ??space=cosine??? 和每個文檔在圖中的最大鄰居數 ??max_neighbors=16??。

import chromadb

# 初始化 Chroma Client
client = chromadb.Client()

# 在 Chroma 中創建一個 collection，明確配置 HNSW
collection = client.create_collection(
    name="my-collection",
    cnotallow={"hnsw": {"space": "cosine", "max_neighbors": 16}},
)

有趣的是，Chroma 默認使用 L2 norm（即 Euclidean distance）作為距離度量。然而，大多數 embedding models 都是為 cosine distance 優化的。

接下來，我們將文檔添加到 collection 中，并使用 HNSW 搜索算法在后臺搜索數據庫。

# 創建示例文檔
documents = [
    "This is the first document.",
    "This document is about machine learning.",
    "Here is a third document about natural language processing.",
]

# 將文檔插入 collection
collection.add(ids=["doc1", "doc2", "doc3"], documents=documents)

# 搜索最相似的 top 1 文檔
search_results = collection.query(query_texts=["NLP"], n_results=1)

# 打印搜索結果
print(search_results)

這應該返回第三個文檔。

結論

隨著 LLMs 的興起，向量數據庫變得越來越重要，現在幾乎每個 RAG 系統都在使用它們。

大多數流行的向量數據庫都支持 HNSW，它通常被用作默認搜索算法。HNSW 和 NSW 都是 approximate nearest neighbor 算法，用于找到足夠接近的匹配項。

HNSW 和 NSW 的搜索復雜度為 log(N)，對于大小為 N 的數據集，而 K-nearest neighbor 搜索的復雜度是線性的。這對于包含數百萬或更多條目的數據庫來說有巨大差異。

RAG 為何能瞬間找到答案？向量數據庫告訴你-AI.x社區

一個展示 O(N) 與 O(log N) 時間復雜度的圖形。相比線性復雜度，對數復雜度增長不明顯。時間復雜度增長：O(N) 隨輸入大小線性增加，而 O(log N) 增長慢得多。圖片由作者提供。

參考文獻

[1] Leon Eversberg 博士 (2025), Understanding Large Language Models and Generative AI: Inside the Technology Behind the Hype

??https://www.amazon.com/dp/B0FGJ67ZDC??

[2] A. Ponomarenko 等人 (2011), Approximate Nearest Neighbor Search Small World Approach, International Conference on Information and Communication Technologies & Applications

??https://www.iiis.org/CDs2011/CD2011IDI/ICTA_2011/PapersPdf/CT175ON.pdf??

[3] Yu. A. Malkov, D. A. Yashunin (2018), Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence

??https://arxiv.org/pdf/1603.09320??

本文轉載自???AI大模型觀察站??，作者：AI研究生

標簽

RAG

向量數據庫

工具

贊

回復