RAG 为何能瞬间找到答案？向量数据库告诉你

显示全部楼层

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 14px;font-style: italic;padding: 1em 1em 1em 2em;border-radius: 6px;color: rgba(0, 0, 0, 0.6);background: rgb(247, 247, 247);box-shadow: rgba(0, 0, 0, 0.05) 0px 4px 6px;">
了解 Hierarchical Navigable Small World (HNSW) 算法如何为当今的 RAG 系统提供动力

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 14px;letter-spacing: 0.1em;color: rgb(63, 63, 63);">

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 14px;letter-spacing: 0.1em;color: rgb(63, 63, 63);">Retrieval-Augmented Generation (RAG) 是为 Large Language Models (LLMs) 添加外部知识的重要工具。

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 14px;letter-spacing: 0.1em;color: rgb(63, 63, 63);">几乎每个 RAG 系统都包含一个向量数据库，用于执行 semantic search。在这种搜索中，存储在向量数据库中的 document embeddings 会与用户的 query embedding 进行比较。

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 14px;letter-spacing: 0.1em;color: rgb(63, 63, 63);">一个基本的 RAG 系统包括一个 embedding model、一个 vector database 和一个 LLM。文档的 embeddings 会提前存储（离线）。当你提出一个问题时，输入会被嵌入并与存储的 embeddings 进行匹配。最佳结果会被发送到 LLM，其中 retriever（由 embedding model 和数据库组合而成）协助 generator（LLM）。
一个基本的 RAG 系统包括一个 embedding model、一个 vector database 和一个 LLM。向量数据库用于找到与查询匹配的 top-K 文档。

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 14px;letter-spacing: 0.1em;color: rgb(63, 63, 63);">实际上，将查询向量与数据库中数百万个 embedding vectors 进行比较以找到完美匹配是非常慢的。为了更快，这些向量数据库通常返回近似匹配的结果。

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 14px;letter-spacing: 0.1em;color: rgb(63, 63, 63);">让我们更深入地看看向量数据库是如何工作的，并探索 Hierarchical Navigable Small World (HNSW) 搜索算法，它为当今许多 RAG 系统提供了动力。

ingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;display: table;padding: 0.3em 1em;color: rgb(255, 255, 255);background: rgb(250, 81, 81);border-radius: 8px;box-shadow: rgba(0, 0, 0, 0.1) 0px 4px 6px;">目录

• 基本 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。

importchromadb

# 初始化 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) 增长慢得多。图片由作者提供。