了解 Hierarchical Navigable Small World (HNSW) 算法如何为当今的 RAG 系统提供动力
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 文档。
实际上，将查询向量与数据库中数百万个 embedding vectors 进行比较以找到完美匹配是非常慢的。为了更快，这些向量数据库通常返回近似匹配的结果。
让我们更深入地看看向量数据库是如何工作的，并探索 Hierarchical Navigable Small World (HNSW) 搜索算法，它为当今许多 RAG 系统提供了动力。
目录
• 基本 Semantic Search • Navigable Small World (NSW) • Hierarchical Navigable Small World (HNSW) • HNSW 在实践中的应用 • 结论 • 参考文献
基本 Semantic Search
在 semantic search 中，embedding model 将文本转换为一个 dense vector，捕捉文本的含义。
通过使用相同的 embedding model 将查询和文档都转换为向量，我们可以通过识别 query vector 的 nearest neighbors 来执行 semantic search。这个过程被称为 K-nearest neighbors (KNN) 搜索。
在 RAG 系统中，retriever 的任务是找到与用户查询最相似的文档。在这个简单示例中，文档1、5和7是从10个文档中找到的三个最接近的匹配项。
一个 RAG 系统中的基本 semantic search 示例。黑点表示使用 cosine distance 度量时，与查询最接近的三个匹配项（共10个文档）。图片由作者提供。
为了找到 nearest neighbors，我们需要测量两个向量之间的距离。通常使用的距离度量是 cosine distance，它关注两个向量之间的角度，或 dot product。
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 的样子：
一个 NSW proximity graph，展示文档作为 vertices，通过对应距离的 edges 相互连接。
一个包含10个文档的 NSW proximity graph，每个 vertex 最多有 M=3 个 edges。图片由作者提供。
在构建图之后（只需做一次），它就可以用于高效搜索。NSW 是一种贪婪算法，在每一步都做出局部最优选择。
NSW 的核心思想是，每个文档都可以通过几次“跳跃”从其他任何文档到达。
为了找到与查询最接近的文档，我们随机选择一个文档作为起点，计算查询与当前文档的所有连接邻居之间的距离。然后选择距离最短的文档。
如果查询与所选文档的距离小于查询与当前文档的距离，我们就移动到所选文档。
然后，算法重复进行。如果查询与当前文档的距离小于与所有邻居的距离，那么就找到了一个局部最小值，并返回 top-K 文档。
NSW 算法针对一个示例查询是这样的：
给定一个查询和一个随机选择的起点，算法从节点9到7，再到5，然后到3。
一个贪婪搜索的示例，包含一个查询和一个随机选择的起点。图片由作者提供。
我们还可以用不同的随机起点重复整个过程，以找到更好的解决方案。
Hierarchical Navigable Small World (HNSW)
HNSW 通过添加 hierarchical layers 改进了 NSW，加快了搜索算法的速度 [3]。
HNSW 使用多层图。最低层（layer 0）包含完整的 NSW 图和所有文档。
在 HNSW 中，创建多个层，每一层进一步减少文档数量。在一个简单示例中，我们可能只使用两层，如下图所示。
一个包含 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",
configuration={"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 搜索的复杂度是线性的。这对于包含数百万或更多条目的数据库来说有巨大差异。
一个展示 O(N) 与 O(log N) 时间复杂度的图形。相比线性复杂度，对数复杂度增长不明显。
时间复杂度增长：O(N) 随输入大小线性增加，而 O(log N) 增长慢得多。图片由作者提供。
