为什么 HNSW 不是终极答案

HNSW（Hierarchical Navigable Small World，分层可导航小世界图）已成为众多向量数据库的首选算法。其多层图结构以及高效导航向量嵌入的能力使其格外具有吸引力。然而，尽管拥有诸多显著优势，对于大规模且动态变化的向量相似度搜索而言，HNSW 可能并非最优解。在本文中，我们将挑战 HNSW 的主导地位，并探讨为什么基于磁盘的替代方案——例如 IVF（Inverted File Index，倒排文件索引）——在面对海量数据集时更具实用价值。

HNSW 的吸引力

HNSW 具有以下几项优势：

• 搜索高效：其基于图的结构能够实现快速的最近邻搜索，在小规模数据集上表现尤为突出。

• 增量更新：无需重建整个索引即可增量添加新向量，这对于动态环境而言是一大优势。

• 高召回率：HNSW 能够在相对较低的延迟下提供高召回率，使其成为实时应用的理想选择。

然而，这些优势背后伴随着一系列权衡，并且随着数据集规模的扩大，这些问题会变得愈发突出。

HNSW 的局限性

HNSW 面临的核心挑战之一，是它在索引构建和搜索操作中对内存的高度依赖。以下是由此引发的主要问题：

• 高昂的内存开销：遍历 HNSW 的图结构涉及高度随机的内存访问模式。为了获得理想的性能，必须将整个数据集保存在内存中。面对包含数十亿高维向量的大规模数据集，天价的内存需求使得这一方案根本无法落地。

• 性能对内存大小极其敏感：一旦可用内存哪怕略微不足以容纳全部向量，HNSW 的性能就会断崖式下跌。在这种情况下，将数据交换（swap）到磁盘会严重拖慢搜索速度，使其在内存受限的系统中几乎不可用。

• 不适合基于磁盘的环境：HNSW 从根本上就是为纯内存操作而设计的，在面向磁盘的场景（例如 PostgreSQL）中表现不佳。它对频繁随机访问的依赖，与磁盘存储擅长顺序访问的特性格格不入。

• 插入与删除代价高昂：在 HNSW 中更新索引会触发整个图结构的级联修改，导致大量的计算开销与写放大（write amplification）。这使得插入和删除操作既缓慢又消耗资源。

相比之下，像 IVF 这样基于磁盘的解决方案，在需要兼顾可扩展性、高效率与低复杂度的场景中表现得尤为出色。

为什么 IVF 可以比 HNSW 更快

纵观所有向量搜索算法，一个关键规律是：算法的性能在很大程度上取决于它所执行的距离计算次数。最大限度地减少这些计算对于提升搜索速度至关重要。尽管原始的 IVF 索引需要扫描总向量数的 1% 到 5%，但现代量化技术与扫描优化的进步已经大幅提升了它的效率，使 IVF 成为 HNSW 的强劲对手。

量化技术：改变游戏规则的关键

量化（Quantization）可将高维向量压缩为紧凑的表示形式。例如：

• RaBitQ：利用测度集中（concentration of measure）现象来提升二值量化与标量量化的准确度，将每个维度量化为 1 比特，实现 32 倍的压缩比。

• 乘积量化（Product Quantization, PQ）：将向量空间划分为多个子空间，并对每个子空间独立进行量化以最小化近似误差。该方法在 FAISS 中提供了 4 倍至 64 倍的灵活压缩比，支持更精细的压缩和更快速的近似搜索。

• 标量量化（Scalar Quantization, SQ）：通过将每个向量维度的取值范围划分为离散级别来独立量化各个维度，通常通过将浮点数（float）转换为 8 位整数（int8）来实现 4 倍的压缩比。

• ScaNN：采用各向异性向量量化（anisotropic vector quantization），通过对影响高内积方向上的误差施加更大惩罚来优化内积准确度，从而实现优异的召回率与速度。

量化技术能够大幅降低内存和磁盘空间占用——将 32 位浮点数转换为比特时通常可缩减 32 倍——同时显著降低计算开销。尽管会带来一定的精度损失，但量化让向量距离比较变得高效得多。例如，将浮点数压缩为比特后，计算复杂度降低了 32 倍；此外，位运算通常比浮点运算高效得多，从而进一步提升了性能。结合快速扫描（fast-scan）优化，还可以通过高效的 CPU 寄存器查表进一步加速这些计算。当与 IVF 结合时，许多量化方法在速度和可扩展性上都能稳定超越 HNSW。其典型工作流程包括：

1. 初始搜索（Initial Search）：利用压缩表示快速筛选出候选向量。

2. 重排序（Reranking）：针对规模小得多的候选子集，使用全精度距离计算对结果进行精排。

RaBitQ+IVF 与 HNSW 对比

结合量化的 IVF 提供了一种将所有量化后向量保存在内存中的高效方式。借助 RaBitQ，内存占用相比全精度向量减少了 32 倍，从而可以将整个量化数据集轻松装入内存。这种设计使索引能够利用比特向量快速检索近似最近邻，并从磁盘读取全精度向量对其进行重排序。对于典型的 Top-10 查询，IVF 只需从磁盘读取 100–200 条向量，而 HNSW 则可能需要读取 800–1000 条向量。这种高效的方法在内存占用与磁盘访问之间实现了最佳平衡，带来了卓越的性价比。

虽然理论上类似的量化技术也可以应用于 HNSW，但实际限制削弱了它们在 HNSW 上的效果：

• 向量打包（Vector Packing）：快速扫描优化依赖于将 32 条压缩向量打包在一起，这与 HNSW 的图结构不兼容。

• 随机访问开销：HNSW 涉及跨图节点和边的频繁随机访问，导致遍历效率低下。相比之下，IVF 将向量按顺序组织在倒排列表（posting lists）中，支持更快的预取（prefetching）和高效的顺序扫描。

• 重排序开销：由于第一阶段都依赖量化表示，IVF 和 HNSW 在重排序阶段的计算开销相似。

归根结底，量化 IVF 与 HNSW 之间的极限性能差异微乎其微，但 IVF 凭借其简洁性和资源效率脱颖而出。

IVF 的运维简洁性

IVF 的简洁性使其成为真实生产应用中更具实用价值的选择：

• 插入与删除：在 HNSW 中，这些操作会触发整个图结构的级联修改，导致大量的计算开销与写放大。相比之下，IVF 只需要更新相应的倒排列表即可。

• 基于磁盘的存储：IVF 依托基于磁盘的索引机制，无需承担 HNSW 高昂的内存成本即可实现高效扩展。

• 适应性强：IVF 可以轻松与先进的量化技术相结合，从而实现更深层次的性能优化。

结论

虽然 HNSW 已经确立了其作为快速、准确的向量相似度搜索算法的声誉，但它并非没有局限性。其内存密集型的本质和较高的运维复杂度，使其不太适合超大规模应用场景。相比之下，IVF——尤其是与现代量化技术结合时——提供了一种可扩展且高性价比的替代方案。

随着向量搜索需求的持续增长，从业者必须审慎评估基于内存与基于磁盘的解决方案之间的权衡。HNSW 或许仍将在中小规模应用中占据主导地位，但面对海量数据集，是时候跳出 HNSW 的局限，拥抱像 IVF 这样更简洁、更具可扩展性的方案了。

如果您对这类数据库感兴趣，欢迎了解并试用 VectorChord。

%[https://github.com/tensorchord/VectorChord/]