向量检索速度提升500%！内存节省90%！Infinity v0.6.0 三大革命性技术颠覆HNSW
简介
在 RAG（检索增强生成）和 LLM（大语言模型）内存中，向量检索被广泛应用。在各种方案中，基于图的索引因其高精度和高性能而成为最常见的选择，其中 HNSW（分层可导航小世界）索引是最具代表性的一种1 2。
然而，在我们将 HNSW 应用于 RAGFlow 的实践过程中，我们遇到了以下两个主要瓶颈：
- 随着数据规模的持续增长，向量数据的内存消耗变得非常巨大。例如，十亿个1024维的浮点向量将需要大约 4TB 的内存空间。
- 在复杂数据集上构建 HNSW 索引时，检索准确率存在瓶颈。达到某个阈值后，仅通过调整参数很难进一步提高准确率。
为解决这一问题，Infinity 基于 HNSW 实现了一系列改进算法。用户可以通过调整 HNSW 的索引参数来选择不同的索引方案。每种 HNSW 索引变体都具有独特的特性，适用于不同的场景，允许用户根据实际需求构建相应的索引结构。
索引方案介绍
原始 HNSW 作为一种常用的基于图的索引，表现出优异的性能。
其结构由两部分组成：
一组原始向量数据，以及由跳表和邻接表共同构建的图结构。以 Python 接口为例，可以按以下方式构建和使用索引：
## Create index
table_obj.create_index(
"hnsw_index",
index.IndexInfo(
"embedding",
index.IndexType.Hnsw, {
"m": 16,
"ef_construction": 200,
"metric": "l2"
},
)
)
## Vector retrieval
query_builder.match_dense('embedding', [1.0, 2.0, 3.0], 'float', 'l2', 10, {'ef': 200})
为了解决高内存消耗和准确率瓶颈的问题，Infinity 提供了以下解决方案：
- 引入 LVQ 和 RaBitQ 量化方法，以减少图搜索过程中原始向量的内存开销。
- 引入 LSG 策略，优化 HNSW 的图索引结构，提升其准确率阈值和查询效率。
为了方便用户在本地测试不同索引的性能，Infinity 提供了一个基准测试脚本。您可以按照 Infinity 在 GitHub 上提供的教程设置环境并准备数据集，然后使用基准测试来测试不同的索引方案。
###################### compile benchmark ######################
cmake --build cmake-build-release --target hnsw_benchmark
###################### build index & execute query ######################
# mode : build, query
# benchmark_type : sift, gist, msmarco
# build_type : plain, lvq, crabitq, lsg, lvq_lsg, crabitq_lsg
##############################################################
benchmark_type=sift
build_type=plain
./cmake-build-release/benchmark/local_infinity/hnsw_benchmark --mode=build --benchmark_type=$benchmark_type --build_type=$build_type --thread_n=8
./cmake-build-release/benchmark/local_infinity/hnsw_benchmark --mode=query --benchmark_type=$benchmark_type --build_type=$build_type --thread_n=8 --topk=10
其中，原始 HNSW 对应参数 build_type=plain。本文对所有变体索引的查询性能进行了统一测试，实验环境配置如下：
- 操作系统：Ubuntu 24.04 LTS (Noble Numbat)
- CPU：第13代 Intel(R) Core(TM) i5-13400
- 内存：64G
该 CPU 为 16 核规格。为了与大多数用户的实际设备环境保持一致，基准测试中的并行计算参数统一设置为 8 线程。
方案 1：原生 HNSW + LVQ 量化器 (HnswLvq)
LVQ 是一种标量量化方法，它将原始向量中的每个 32 位浮点数压缩为 8 位整数3，从而将内存占用降低至原始向量的四分之一。
与简单的标量量化方法（如均值标量量化）相比，LVQ 通过统计分析每个向量的残差来减少误差，有效地最小化了量化向量距离计算中的信息损失。因此，LVQ 仅需约30%的原始内存占用，即可准确估算原始向量之间的距离。
在 HNSW 算法中，原始向量用于距离计算，这使得 LVQ 可以直接与 HNSW 集成。我们将这种组合方法称为 HnswLvq。在 Infinity 中，用户可以通过设置参数 "encode": "lvq" 来启用 LVQ 编码。
## Create index
table_obj.create_index(
"hnsw_index",
index.IndexInfo(
"embedding",
index.IndexType.Hnsw, {
"m": 16,
"ef_construction": 200,
"metric": "l2",
"encode": "lvq"
},
)
)
## Vector retrieval
query_builder.match_dense('embedding', [1.0, 2.0, 3.0], 'float', 'l2', 10, {'ef': 200})
HnswLvq 的图结构与原始 HNSW 保持一致，关键区别在于它使用量化向量在图内执行所有距离计算。通过这一改进，HnswLvq 在索引构建和查询效率方面均优于原始 HNSW 索引。
构建效率的提升源于量化向量的长度更短，从而减少了使用 SIMD 指令进行距离计算的时间。查询效率的提升则归因于量化带来的计算加速，其效果超过了精度损失所带来的负面影响。
总之，HnswLvq 在保持出色查询性能的同时，显著降低了内存使用。我们建议用户在大多数场景下将其作为主要索引。为复现此实验，用户可以在基准测试中设置参数 build_type=lvq。具体的实验结果将在方案二中与 RaBitQ 量化器方案一并比较。
方案 2：原生 HNSW + RaBitQ 量化器 (HnswRabitq)
RaBitQ 是一种二值标量量化方法，其核心思想与 LVQ 类似，都旨在用更少的编码位替换原始向量中的32位浮点数。不同之处在于，RaBitQ 采用二值标量量化，仅用1位表示每个浮点数，从而实现了极高的压缩比。
然而，这种极端的压缩也会导致向量中更显著的信息丢失，从而引起距离估算精度的下降。为了缓解这一问题，RaBitQ 在预处理阶段引入了旋转矩阵来处理数据集，并保留了更多的残差信息，从而在一定程度上减少了距离计算的误差4。
尽管如此，二值量化在精度方面有明显局限性，与 LVQ 相比存在较大差距。直接使用 RaBitQ 编码构建的索引查询性能较差。
因此，Infinity 中实现的 HnswRabitq 方案是先为数据集构建一个原始 HNSW 索引，然后通过 optimize 方法中的 compress_to_rabitq 参数将其转换为 HnswRabitq 索引。
在查询过程中，系统首先使用量化向量进行初步检索，然后使用原始向量对用户指定的 ef 个候选结果进行重新排序。
## Create index
table_obj.create_index(
"hnsw_index",
index.IndexInfo(
"embedding",
index.IndexType.Hnsw, {
"m": 16,
"ef_construction": 200,
"metric": "l2"
},
)
)
## Construct RaBitQ coding
table_obj.optimize("hnsw_index", {"compress_to_rabitq": "true"})
## Vector retrieval
query_builder.match_dense('embedding', [1.0, 2.0, 3.0], 'float', 'l2', 10, {'ef': 200})
与 LVQ 相比，RaBitQ 可以将编码向量的内存占用进一步减少近70%。在某些数据集上，由于二值量化后距离计算效率更高，HnswRabitq 的查询效率甚至超过了 HnswLvq。
但是，需要注意的是，在某些数据集（如 sift1M）上，量化过程可能导致严重的精度损失，使得这类数据集不适合使用 HnswRabitq。
总之，如果用户的数据集对量化误差不敏感，采用 HnswRabitq 索引可以在显著降低内存开销的同时，仍然保持相对较好的查询性能。
在这种情况下，建议优先使用 HnswRabitq 索引。用户可以通过设置基准测试参数 build_type=crabitq 来复现上述实验。
方案 3：LSG 图构建策略
LSG（局部缩放图）是一种基于图索引算法（如 HNSW、DiskANN 等）改进的图构建策略5。
该策略通过统计分析数据集中每个向量的局部信息——邻域半径，来缩放任意两个向量之间的距离（如 L2 距离、内积距离等）。缩放后的距离被称为 LS 距离。
在图索引构建过程中，LSG 统一使用 LS 距离替代原始距离度量，实际上是对原始度量空间进行了一次“局部缩放”。通过理论证明和实验，该论文表明，在这个缩放后的空间中构建图索引，可以在原始空间中获得更优的查询性能。
LSG 在多个方面优化了 HNSW 索引。当准确率要求相对宽松（< 99%）时，LSG 相比原始 HNSW 索引表现出更高的 QPS（每秒查询数）。
在高精度场景（> 99%）下，LSG 提升了图索引的质量，使 HNSW 能够突破其原有的准确率限制，达到原始 HNSW 索引难以企及的检索精度。这些改进在 RAGFlow 的实际应用中，为用户带来了更快的响应时间和更精确的查询结果。
在 Infinity 中，LSG 作为 HNSW 的一个可选参数提供。用户可以通过设置 build_type=lsg 来启用此图构建策略，我们将相应的索引称为 HnswLsg。
## Create index
table_obj.create_index(
"hnsw_index",
index.IndexInfo(
"embedding",
index.IndexType.Hnsw, {
"m": 16,
"ef_construction": 200,
"metric": "l2",
"build_type": "lsg"
},
)
)
## Vector retrieval
query_builder.match_dense('embedding', [1.0, 2.0, 3.0], 'float', 'l2', 10, {'ef': 200})
LSG 本质上是在索引构建过程中改变了度量空间。因此，它不仅可以应用于原始 HNSW，还可以与量化方法（如 LVQ 或 RaBitQ）结合，形成 HnswLvqLsg 或 HnswRabitqLsg 等变体索引。用户接口的使用方式与 HnswLvq 和 HnswRabitq 保持一致。
LSG 能够提升绝大多数图索引和数据集的性能，但代价是在图构建阶段需要额外计算局部信息——邻域半径，因此会在一定程度上增加构建时间。例如，在 sift1M 数据集上，HnswLsg 的构建时间约为原始 HNSW 的1.2倍。
总之，如果用户对索引构建时间不敏感，可以放心启用 LSG 选项，因为它能够稳定地提升查询性能。用户可以通过将基准测试参数设置为 build_type=[lsg/lvq_lsg/crabitq_lsg] 来复现上述实验。
索引性能评估
为了评估 Infinity 中各种索引的性能，我们选择了三个具有代表性的数据集作为基准，包括向量索引评估中广泛使用的 sift 和 gist 数据集。
鉴于 Infinity 在当前场景中常与 RAGFlow 结合使用，在 RAG 类型数据集上的检索效果对于用户评估索引性能尤为关键。
因此，我们还加入了 msmarco 数据集。该数据集是通过使用 Cohere Embed English v3 模型对 TREC-RAG 2024 语料库进行编码生成的，包含了1.135亿个文本段落的嵌入向量，以及来自 TREC-Deep Learning 2021-2023 的1677条查询指令对应的嵌入向量。
从各数据集的测试结果可以看出，在大多数情况下，HnswRabitqLsg 实现了最佳的综合性能。例如，在 RAG 场景的 msmarco 数据集上，RaBitQ 在实现内存使用减少90%的同时，在99%召回率下提供了5倍于原始 HNSW 的查询性能。
基于以上实验结果，我们为 Infinity 用户提供以下实践建议：
- 与 HnswLvq 和 HnswRabitq 相比，原始 HNSW 可以达到更高的准确率上限。如果用户有极高的准确率要求，应优先考虑此策略。
- 在可接受的准确率范围内，对于大多数数据集，可以放心选择 HnswLvq。对于不易受量化影响的数据集，HnswRabitq 通常是更好的选择。
- LSG 策略能够提升所有索引变体的性能。如果用户对索引构建时间不敏感，建议在所有场景中都启用此选项以提高查询效率。此外，由于其算法特性，LSG 能显著提高准确率上限。因此，如果使用场景要求极高的准确率（>99.9%），强烈建议启用 LSG 以优化索引性能。
Infinity 仍在不断迭代和完善。我们欢迎大家的持续关注并提出宝贵的反馈和建议。
