百萬級文檔秒匹配？HNSW 讓向量數據庫在 RAG 中封神
向量數據庫如何為檢索增強生成（RAG）高效匹配數據
包含4個層級和30個文檔的HNSW圖
檢索增強生成（RAG）是向大型語言模型（LLMs）添加外部知識的重要工具。
幾乎每個RAG系統都包含一個向量數據庫來執行語義搜索。在這種搜索方式中，存儲在向量數據庫中的文檔嵌入會與用戶的查詢嵌入進行比較。
一個基本的RAG設置包括一個嵌入模型、一個向量數據庫和一個大型語言模型。向量數據庫用于找到與查詢最匹配的前K個文檔
在實際應用中，將一個查詢向量與數據庫中數百萬個嵌入向量進行比較以找到完美匹配是非常緩慢的。為了提高速度，這些向量數據庫通常會返回足夠接近的結果。
讓我們仔細看看向量數據庫是如何工作的，并探討為當今許多RAG系統提供支持的分層可導航小世界（HNSW） 搜索算法。
基本語義搜索
在語義搜索中，嵌入模型會將文本轉換為一個密集向量，該向量捕捉了文本的含義。
通過使用同一個嵌入模型將查詢和文檔都轉換為向量，我們可以通過識別查詢向量的最近鄰來執行語義搜索。這個過程被稱為K近鄰（KNN） 搜索。
在一個RAG系統中，檢索器的工作是找到與用戶查詢最相似的文檔。在這個簡單的例子中，在10個文檔中，文檔1、5和7是三個最接近的匹配。
為了找到最近鄰，我們需要測量兩個向量之間的距離。通常使用的距離度量是余弦距離，它關注兩個向量之間的夾角，或者點積。
余弦距離公式是1減去兩個向量v和w的余弦相似度。
然后，我們按距離排序并選擇K個最接近的匹配。
然而，搜索所需的計算量會隨著向量數據庫中條目的數量線性增加。例如，有15個文檔時，必須計算15個距離。
如果數據庫包含數百萬個文檔，那么每次查詢時我們都需要計算數百萬個距離。
為了提高效率并解決這個問題，我們可以改用近似最近鄰（ANN） 搜索。
ANN比KNN高效得多。然而，顧名思義，這些算法不能保證返回最接近的匹配。但在實際應用中，它們通常足夠接近。
Navigable Small World (NSW)
NSW 算法[2]是一種基于圖的ANN算法。圖是一種由邊和頂點組成的數據類型。
首先，我們計算所有文檔之間的距離，這只需要做一次。接下來，我們構建一個鄰近圖，其中數據庫中的每個文檔對應一個頂點。每個文檔通過邊連接到其幾個最近的鄰居。超參數??M??決定了每個文檔的最大連接數。
使用上面的相同示例，下面是NSW鄰近圖的樣子：
一個包含10個文檔的NSW鄰近圖，每個頂點最多有M=3條邊。
圖構建完成后（只需要做一次），就可以用于高效搜索了。NSW是一種貪心算法，在每一步都做出局部最優選擇。
NSW背后的理念是，從任何一個文檔都可以通過幾次“跳躍”到達另一個文檔。
為了找到與查詢最接近的文檔，我們隨機選擇一個文檔作為起點，并計算查詢與當前文檔的所有相連鄰居之間的距離。然后，我們選擇距離最短的文檔。
如果查詢與所選文檔之間的距離小于查詢與當前文檔之間的距離，我們就移動到所選文檔。
然后，算法重復此過程。如果查詢與當前文檔之間的距離小于與所有鄰居的距離，則找到了局部最小值，并返回前K個文檔。
以下是一個示例查詢的NSW算法：
一個帶有查詢和隨機選擇起點的貪心搜索示例。
我們也可以用不同的隨機起點重復整個過程，以找到更好的解決方案。
Hierarchical Navigable Small World (HNSW)
HNSW在NSW的基礎上增加了分層結構，從而加快了搜索算法的速度[3]。
HNSW使用多層圖。最低層，即第0層，包含完整的NSW圖和所有文檔。
在HNSW中，會創建多個層級，每個層級進一步減少文檔的數量。在一個簡單的例子中，我們可能只使用兩個層級，如下圖所示。
一個包含兩個層級和10個文檔的HNSW圖。
搜索算法從最高層開始，其操作方式與NSW類似。在某個層級中找到局部最小值后，我們將該文檔作為下一個較低層級的起點。
最終，我們到達第0層并返回前K個文檔。
這個過程就像最初先縮小范圍在最高層級找到一個大致匹配，然后隨著層級降低不斷放大范圍以找到更好的匹配。
雖然HNSW在搜索方面比KNN快得多，但創建多層鄰近圖需要大量計算。當從數據庫中插入、更新或刪除文檔時，還需要進行額外的計算來更新或重新創建圖。
此外，像HNSW這樣的基于圖的搜索算法需要更多的內存來存儲圖結構和向量嵌入。
HNSW得到了流行向量數據庫的支持，如Chroma、Qdrant、Weaviate、Milvus、Faiss、Vespa、Pinecone和Elasticsearch，并且它通常被用作語義搜索的默認ANN算法。
實際應用中的HNSW
HNSW通常是大多數向量數據庫的默認選擇。這使得它在實際應用中非常容易使用。
例如，我們將在Python中使用開源向量數據庫Chroma，可以使用??pip install chromadb??命令安裝它。
首先，創建一個本地Chroma數據庫，然后為你的數據創建一個新的集合。在這里，我們可以顯式地設置HNSW算法的超參數，例如距離度量??space=cosine???和圖中每個文檔的最大鄰居數??max_neighbors=16??。
import chromadb
# 初始化Chroma客戶端
client = chromadb.Client()
# 在Chroma中創建一個帶有顯式HNSW配置的集合
collection = client.create_collection(
name="my-collection",
cnotallow={"hnsw": {"space": "cosine", "max_neighbors": 16}},
)有趣的是，Chroma使用L2范數（即歐氏距離）作為默認的距離度量。然而，大多數嵌入模型都是針對余弦距離進行優化的。
接下來，我們將文檔添加到集合中，并在后臺使用HNSW搜索算法搜索數據庫。
# 創建示例文檔
documents = [
"這是第一個文檔。",
"這個文檔是關于機器學習的。",
"這是第三個關于自然語言處理的文檔。",
]
# 將文檔插入集合
collection.add(ids=["doc1", "doc2", "doc3"], documents=documents)
# 搜索最相似的1個文檔
search_results = collection.query(query_texts=["自然語言處理"], n_results=1)
# 打印搜索結果
print(search_results)這應該會返回第三個文檔。
結論
隨著大型語言模型的興起，向量數據庫變得越來越重要，現在幾乎每個RAG系統都在使用它們。
大多數流行的向量數據庫都支持HNSW，它通常被用作默認的搜索算法。HNSW和NSW都是用于找到足夠接近的匹配的近似最近鄰算法。
對于大小為N的數據集，HNSW和NSW的搜索復雜度都是log(N)，而K近鄰搜索的復雜度是線性的。這在數據庫中有數百萬或更多條目的情況下會產生巨大的差異。
時間復雜度增長：O(N)隨著輸入大小線性增加，而O(log N)的增長要慢得多。
參考文獻
[1] Dr. Leon Eversberg (2025), Understanding Large Language Models and Generative AI: Inside the Technology Behind the Hype
[2] A. Ponomarenko et al. (2011), Approximate Nearest Neighbor Search Small World Approach, International Conference on Information and Communication Technologies & Applications
[3] Yu. A. Malkov, and 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
本文轉載自???AIGC深一度??
