如何平衡向量检索速度和精度？深度解读 HNSW 算法

向量检索（向量相似性搜索）是 AI 时代最重要的技术之一。其典型应用场景包括：推荐系统、检索增强生成（RAG）等高级 GenAI 应用。

向量检索最突出的优势是准确性和速度。

过去，向量搜索通常是用暴力扫描的方式来找到和查询向量最近的 K 个邻居（KNN）。它的核心思想是比对查询向量和库内所有向量的距离，简单直观但计算量大。也就是说，如果内存中有 100 个文档，kNN 算法将计算查询向量与 100 个文档向量的相似度或距离。因此 kNN 的优势在于可以获得精确的搜索结果，但缺陷则是在检索时间与数据规模成正比。因此在处理数百万级以上数据规模时，成本、效率、速度都会遇到极大瓶颈。

图：kNN 算法工作流程

在本文，我们将介绍一个基于 Hierarchical Navigable Small World（HNSW）算法实现的HNSWlib的向量检索库。

什么是向量检索

解读HNSWlib之前，我们需要对什么是向量检索先有一个基本的概念。

向量检索是信息检索中的一种常用方法，用于从大量非结构化数据集（图像、文档、音频等）中找到与给定查询最相似的信息。顾名思义，文档和查询都被表示为高维向量空间中具有特定维度的向量。向量的维度取决于用于转换文档和查询的 Embedding模型。例如，如果我们使用“all-MiniLM-L6-v2”作为 Embedding 模型，每个查询或文档将获得 384 个维度的向量。

在查询时，Embedding 模型会将查询内容，转化为文档中已有的语义维度，然后进行计算，相似含义的内容在向量空间中的位置更加靠近，然后返回其中最高相似性得分（或最短距离）的内容，这就是向量检索背后的逻辑。

图：2D 向量空间中相似单词的向量嵌入。

什么是 HNSW

近些年，为了优化 kNN 的检索性能，业内已经开发了各种索引算法，HNSW 就是最有效的算法之一。

HNSW 是一种基于图的高效向量检索算法。它依赖于两个关键概念：跳表（Skip List）和可导航小世界（NSW）图。

其中，跳表是一种概率数据结构，由多层链表组成，层次越高，链表中跳过的元素就越多。正如下面的可视化图，最低层包含了链表中的所有元素。随着我们向更高层移动，链表逐渐跳过越来越多的元素，所剩下的元素就越来越少。

图：跳表工作流程

假设我们需要从有 3 层和 8 个元素的原始链表中查找元素 7。首先，我们从最高层开始，检查第一个元素是否低于 7。如果是，那么我们检查第二个元素。如果第二个元素高于 7，那么我们将第一个元素用作较低层的起点。接下来，我们在较低层做完全相同的事情，并逐渐下降到最低层以找到所需的元素。在许多元素上的跳过过程使得跳表在执行搜索操作时非常快。

理解了跳表的基本概念之后，我们再来看看 NSW 图。

NSW 图中，每个节点（或称为顶点）都会与相似的节点相连，组成一张完整的 NSW 图。其检索的底层逻辑是贪婪路由搜索，从任意节点开始，检索起相邻节点中与其更加相似的节点，然后转移到该节点，过程循环往复，直到找到局部最小值，即当前节点比之前访问的任何节点都更接近查询向量，此时停止搜索。

图：NSW 图创建过程

HNSW 算法，结合了跳表和 NSW 图的优势于一体。HNSW 不仅仅是一个简单的二维图，而是由几层图所组成的多图层结构。与跳表概念类似，图的最低层包含所有元素，层越高，跳过的元素就越多。

在图创建过程中，HNSW 首先为每个元素分配一个从 0 到 I 的随机数，其中 I 是一个元素在多层图中能存在的最大层。如果一个元素的 I 等于 2，并且总层数为 4，那么这个元素将从第 0 层一直存在到第 2 层，但不存在于第 3 层。

图：使用 HNSW 算法的向量检索

在向量检索过程中，HNSW 算法首先选择最高层的任意节点，然后通过 NSW 图检索到局部最小值，紧接着，相同的流程在下一层重复，逐步逼近目标节点，直到找到最接近查询向量的节点。

通过这一方法，HNSW 算法不必检索那些离查询点较远的相关度较低的元素，进而增加了检索的效率。这也导致了 HNSW 并不适用于精确匹配，因为 HNSW 在搜索过程中跳过了一些元素，当然，其他的近似最近邻（ANN）方法，如FAISS或 ScaNN 也是一样。

那么如何在不需要精确匹配结果，但仍然希望获得相对高效的召回时，我们要怎么办？我们可以调整 HNSW 的超参数：

• M：NSW 图中每个元素的边数。较高的M值通常会对应更好的搜索精度，但代价是更慢的索引构建时间。

• efConstruction：构建索引时的动态候选列表大小。一般来说，候选队列越长，索引质量越好，索引构建时间也就会越长。

• efSearch：搜索阶段的动态候选列表的大小。一般来说，efSearch越高，召回率越高，但是搜索过程会比较慢。

除了速度与精度的权衡之外，我们还需要注意图创建过程中的内存消耗。这是因为 HNSW 要求将整个数据集加载到 RAM 中，如果您的数据集太大而无法放入内存中，就会导致比较尴尬的情况发生。比如，M值越高，我们就需要分配越多存储资源用于每个元素相邻信息的存储。此外，随着元素和其相邻信息被添加到图中，内存需求会呈线性增长。因此，在图创建过程中，微调M和efConstruction至关重要，特别是在大规模应用中。

整体来说，HNSW 具有对数复杂度 O（log N）和高召回率，并支持动态更新，无需重建索引即可添加新数据。然而，与其他 ANN 算法相比，HNSWlib 也具有更高的内存消耗，索引构建时间较慢，缺乏对元素删除的原生支持。

但与其他 ANN 方法相比，HNSW 在大型数据集上的表现依然非常具有竞争力。

参考下面的 GIST1M 数据集（具有 960 维的 1M 向量）上的ANN基准测试，HNSW 效果整体好于 FAISS，Annoy，pgector 等，特别是当需要高召回率时。排名上，其表现只在 Milvus 的Knowhere和Zilliz Cloud的 Glass 算法之后，获得了前三名的成绩。

图：GIST1M 数据集的 ANN 基准测试结果

HNSWlib 是一个基于 C++ 的开源 HNSW 算法实现。用途上，HNSWlib 非常适合为向量检索用例构建简单场景，并不适合如 1 亿甚至数十亿数据点这样的复杂场景检索。

因为 HNSWlib 是一个功能有限的轻量级 ANN 库，会随着数据点的增长，因为内存消耗问题，导致出现扩展性瓶颈。

因此，在大规模应用中，使用像Milvus这样的向量数据库将是更好的选择。向量数据库作为一种成熟的解决方案，能够高效地存储大量数据并执行有效的向量检索。例如，Milvus支持云原生和多租户服务，允许用户从云上的多个用户存储、索引和检索数百万甚至数十亿个数据点。

当然，HNSWlib 也可以被集成到 Milvus 这为代表的向量数据库中，接下来我们将展示这一过程。

如何将 HNSWlib 与 Milvus 的集成

第一步，通过 pip install 安装 HNSWlib：

pip install hnswlib

接下来，让我们创建 100 个虚拟数据点，每个数据点的维度为 128。接下来，我们构建M为 8，efConstruction为 25 的 HNSW 图。最后，我们计算查询数据点的最近邻。

import hnswlibimport numpy as npimport pickle
dim = 128num_elements = 100
# Generating sample datadata = np.float32(np.random.random((num_elements, dim)))ids = np.arange(num_elements)
# Generating query pointquery = np.float32(np.random.random((1, dim)))
# Declaring indexp = hnswlib.Index(space = 'l2', dim = dim) # possible options are l2, cosine or ip
# Initializing index - the maximum number of elements should be known beforehandp.init_index(max_elements = num_elements, ef_construction = 25, M = 8)
# Element insertion (can be called several times):p.add_items(data, ids)
# Controlling the recall by setting ef:p.set_ef(50) # ef should always be > k
# Query dataset, k - number of the closest elements (returns 2 numpy arrays)labels, distances = p.knn_query(query, k = 1)

这就是我们实现原生 HNSWlib 所要做的一切。

接下来，让我们看看如何在 Milvus 中使用 HNSW 集成。

使用 Milvus 的最简单方法是通过Milvus Lite（Milvus 的轻量级版本，可以导入到您的 Python 应用程序中），我们可以使用 pip install 安装它。

!pip install -U pymilvus!pip install pymilvus[model]

现在我们可以从创建集合并定义索引方法开始。首先，我们定义一个集合模式，指定 HNSW 作为索引方法，Milvus 将自动在幕后使用 HNSW。然后，我们可以开始将数据插入到集合中进行索引构建。

from pymilvus import MilvusClient, DataTypefrom pymilvus import model
client = MilvusClient("demo.db")
# 1. Create schemaschema = MilvusClient.create_schema(    auto_id=False,    enable_dynamic_field=False,)
# 2. Add fields to schemaschema.add_field(field_name="id", datatype=DataType.INT64, is_primary=True)schema.add_field(field_name="vector", datatype=DataType.FLOAT_VECTOR, dim=768)schema.add_field(field_name="text", datatype=DataType.VARCHAR, max_length=200)
# 3. Prepare index parametersindex_params = client.prepare_index_params()
# 4. Add indexesindex_params.add_index(    field_name="vector",     index_type="HNSW",    metric_type="L2")
# Create collectionif client.has_collection(collection_name="demo_collection"):    client.drop_collection(collection_name="demo_collection")
client.create_collection(    collection_name="demo_collection",    schema=schema,    index_params=index_params)
# Define embedding modelembedding_fn = model.DefaultEmbeddingFunction()
# Text data to search from.docs = [    "Artificial intelligence was founded as an academic discipline in 1956.",    "Alan Turing was the first person to conduct substantial research in AI.",    "Born in Maida Vale, London, Turing was raised in southern England.",]
# Transform text data into embeddingsvectors = embedding_fn.encode_documents(docs)
data = [    {"id": i, "vector": vectors[i], "text": docs[i]}    for i in range(len(vectors))]
# Insert embeddings into Milvusres = client.insert(collection_name="demo_collection", data=data)
Finally, if we want to perform vector search, we can do the following:
SAMPLE_QUESTION = "What's Alan Turing achievement?"query_vectors = embedding_fn.encode_queries([SAMPLE_QUESTION])
res = client.search(    collection_name="demo_collection",      data=query_vectors,      limit=1,      output_fields=["text"],
)
context = res[0][0]["entity"]["text"]

结论

向量检索在需要准确度和速度的现代 AI 应用中非常重要。虽然 kNN 暴力搜索通过穷举搜索提供高度准确的结果，但其线性时间复杂度使其在大规模数据集上不切实际。

HNSW 算法通过使用多层次图结构，在速度和准确性之间提供了创新的解决方案。通过结合跳表和 NSW 图，HNSW 实现了快速、近似的搜索，可以有效处理海量数据集此外，通过微调超参数（如M、efConstruction和efSearch），我们可以允根据每个应用所需的搜索速度、准确性和内存消耗这三者之间进行权衡优化。实际使用中，我们可以将 HNSWlib 集成到 Milvus 向量数据库优化我们的使用体验。

本文作者：Ruben Winastwan