为什么 HNSW 不是最终的答案

2024.12.24: 本文部分评论可见 Hacker News

Original post: Why HNSW is Not the Answer

HNSW 已经成为许多向量数据库的热门算法。它的多层次图结构和高效处理向量嵌入的能力确实很吸引人。不过，尽管 HNSW 看起来优势明显，但在大规模向量相似性搜索中，它可能不是最佳选择。在这篇博文中，我们将探讨 HNSW 的主导地位，并讨论为什么像 IVF（倒排文件索引）这样的基于磁盘的替代方案，可能对于处理大规模数据集更为实用。

HNSW 的优势

HNSW 具有几个显著优势：

高效搜索：其基于图的结构能够快速进行最近邻搜索，尤其适用于较小的数据集。
增量更新：可以增量地添加新向量，而无需重建索引，这对于动态环境来说是一个重要优势。
高召回率：HNSW 提供了高召回率和相对较低的延迟，非常适合实时应用。

不过，随着数据集规模的增长，HNSW 的一些缺点也变得更加明显。

HNSW 的问题

HNSW 面临的主要挑战之一是对内存的高度依赖，尤其是在索引和搜索操作中。以下是主要问题：

内存开销：遍历 HNSW 的图结构涉及高度随机的访问模式。为了获得合理的性能，整个数据集必须存储在内存中。这对于拥有数十亿高维向量的大规模数据集来说，内存需求过于庞大，变得不可行。
对内存大小的性能敏感性：如果内存稍微不足以容纳所有向量，HNSW 的性能会急剧下降。在这种情况下，数据交换到磁盘会严重影响搜索速度，使得在内存受限的系统中使用变得不切实际。
不适合基于磁盘的环境：HNSW 本质上是为内存操作设计的，在以磁盘为导向的场景（如 PostgreSQL）中表现不佳。其对频繁随机访问模式的依赖，使其与磁盘存储的顺序访问特性不兼容。
插入和删除成本：在 HNSW 中更新索引需要在整个图中进行级联修改，导致显著的计算和写放大。这使得插入和删除操作既缓慢又资源密集。

相比之下，像 IVF 这样的基于磁盘的解决方案在需要扩展性和效率的场景中表现出色。

为什么 IVF 可能比 HNSW 更快

一项关键观察（Key insight）是，所有向量搜索算法的性能在很大程度上取决于它们执行的距离计算次数。减少这些计算对于提高搜索速度至关重要。虽然原始的 IVF 索引需要扫描总向量的 1% 到 5%，但现代在量化和优化方面的进展显著提升了其效率，使 IVF 成为 HNSW 的强有力竞争者。

以下是 IVF 可能更快的几个原因：

减少距离计算：IVF 通过将数据集划分为多个簇，显著减少了需要计算的向量数量。搜索时只需在相关簇内进行距离计算，从而提高了搜索速度。
优化的量化技术：现代量化方法能够有效地压缩数据，同时保留重要信息，这进一步加快了搜索过程。
较低的内存需求：IVF 设计为更适合磁盘操作，减少了对内存的依赖，使其在处理大规模数据集时更加高效。

随着技术的发展，IVF 在速度和效率上已经成为一个值得关注的选择，尤其是在处理大规模向量时。

Quantization：改变游戏规则的关键

量化通过将高维向量压缩为紧凑的表示，显著提高了向量搜索的效率。以下是一些重要的量化方法：

RaBitQ：这一发表在 SIGMOD’24 上的工作利用测量集中现象提升二进制和标量量化的准确性，将每个维度量化为 1 位，实现 32 倍的压缩比，并且相比于 PQ 能够保证明确的 error bound。
产品量化（PQ）：通过将向量空间划分为多个子空间，独立量化每个子空间，以最小化近似误差。此方法在 FAISS 中提供从 4 倍到 64 倍的灵活压缩比，实现更精细的压缩和更快的近似搜索。
标量量化（SQ）：通过将每个向量维度的范围划分为离散级别，独立量化每个维度。通常通过从浮点数转换为 int8，实现约 4 倍的压缩比。
ScaNN：采用各向异性向量量化来优化内积准确性，通过惩罚影响高内积的方向错误，达到更优的召回率和速度。

量化显著减少了内存和磁盘空间的使用——将浮点数转换为比特时，减少的比例通常可达 32 倍，同时大幅降低计算开销。尽管会有一些精度损失，但量化使向量比较变得更加高效。例如，两个 D 维向量之间的典型距离计算复杂度为 O(D²)，但将浮点数压缩为比特后，这一复杂度降低了 1024 倍（32x32）。通过快速扫描优化，这些计算通过高效的 CPU 寄存器查找进一步加速。结合 IVF，许多量化方法在速度和可扩展性方面始终优于 HNSW。

典型工作流程非常简单：

初始搜索：利用压缩表示快速识别候选向量。
重新排序（rerank）：在较小的候选子集上使用全精度距离计算来细化结果。

通过这些方法，量化不仅提升了搜索速度，也为处理大规模数据集提供了更好的解决方案。

比较 RaBitQ+IVF 和 HNSW

RabitQ 是新近提出的一种量化方法，它将 32 位向量压缩为 1 位。虽然这种压缩会导致一些精度损失，但大大降低了计算要求。通过快速扫描优化，我们可以实现比传统向量距离计算快 100 倍以上的计算。

结合量化的 IVF 提供了一种高效的方式来存储所有量化向量。通过利用 RaBitQ，内存使用量相比于全尺寸向量减少了 32 倍，允许整个量化数据集适配于内存。这种设计使得索引能够快速检索近似最近邻，并使用从磁盘获取的全精度向量进行重新排序。对于典型的 Top-10 查询，IVF 只需从磁盘获取 100-200 个向量，而 HNSW 可能需要 800-1000 个向量。这种高效的方法在内存使用和磁盘访问之间达成了最佳平衡，提供了卓越的性价比。

尽管理论上可以将类似的量化技术应用于 HNSW，但实际约束降低了其有效性：

Vector Packing：Fast Scan 优化依赖于将 32 个压缩向量打包在一起，而这与 HNSW 的图结构不兼容。
随机访问成本：HNSW 涉及在图节点和边之间频繁的随机访问，使得遍历效率低下。相比之下，IVF 将向量顺序组织在发布列表中，便于更快的预取和有效的顺序扫描。
重新排序成本：IVF 和 HNSW 在重新排序计算成本上相似，因为它们在第一阶段都依赖于量化表示。

尽管量化 IVF 和 HNSW 之间的性能差异可能很小，但 IVF 以其简洁性和高效性脱颖而出。

Feature	IVF	IVF + RaBitQ	HNSW
Indexing Method	KMeans can be offloaded to GPU	KMeans + Quantization	Nearest Neighbor Graph, need to keep everything in memory
Overlapped Data Across Query	Centroids	Quantized vectors	No
Scalability	Limited by CPU and memory	Outstanding	Limited by memory
Insertion/Deletion	Simple (updates posting lists)	Simple (updates posting lists)	Complex (cascading graph changes)
Search Speed	Slow	Extremely Fast with Quantization	Fast with sufficient memory
Overall Complexity	Low	Low	High

IVF 的操作简便性

IVF 的简洁性使其成为现实世界应用中更实用的选择：

插入和删除：在 HNSW 中，这些操作会触发图中的级联修改，导致显著的计算和写放大。相比之下，IVF 只需更新相关的发布列表。
基于磁盘的存储：IVF 依赖于基于磁盘的索引，使其能够高效地扩展，而不需要 HNSW 所需的高昂内存成本。
适应性强：IVF 可以轻松与先进的量化技术结合，进一步优化性能。

结论

尽管 HNSW 已经巩固了其作为快速准确的向量相似性搜索算法的声誉，但它并非没有局限性。其内存密集型的特性和操作复杂性使其不太适合大规模应用。相反，IVF 提供了一种可扩展且具有成本效益的替代方案，特别是当与现代量化技术结合时。

随着对向量搜索需求的持续增长，实践者必须仔细评估内存基础和基于磁盘的解决方案之间的权衡。HNSW 可能在小到中型应用中占主导地位，但对于大规模数据集，应该超越 HNSW，采用像 IVF 这样更简单、更可扩展的方法。

License

This article is licensed under CC BY-NC-SA 3.0.
Please contact me for commercial use.