HNSW 的基础实现和优化探索
感谢 wibyuan 对优化探索过程中的讨论和建议。
问题引入
向量检索是指从一个实数向量集合 \(\mathcal{B}=\{v_1,v_2,..., v_n \} \subseteq R^{n\times d}\) 中，找到与查询向量 \(q \in R^d\) 最相似的向量集合 \(\mathcal{R}=\{v_{i_1}, v_{i_2}, ..., v_{i_k}\}\) 的过程
最相似的 K 个向量被称为 K 近邻（K Nearest Neighbors, KNN）
在大模型时代，向量检索被广泛应用于文本检索、图像检索、推荐系统等领域
这里的相似常用的有三种：
- \(L2\) 相似度：\(sim(q, v) = -||q-v||_2\)
- 内积相似度：\(sim(q, v) = q \cdot v\)
- 余弦相似度：\(sim(q, v) = \frac{q \cdot v}{||q||_2 ||v||_2}\)
这几个相似度在特殊情形下是等价的，其实也是为了处理“相似”而产生的不同做法，本质上相同。
比如，在向量已经归一化的情形下（归一化：\(||v||_2 = 1\)），内积相似度、余弦相似度和 \(L2\) 相似度本质上是相同的
内积相似度和余弦相似度的等价比较好理解，对于 \(L2\) 相似度： \[ ||q-v||_2^2 = ||q||_2^2 + ||v||_2^2 - 2 q \cdot v = 2 - 2 q \cdot v \]
向量检索算法的发展
为了方便，记 \(|\mathcal{B}|=n\)，\(d\) 为向量的维度，\(c\) 为编码压缩率，\(k\) 为空间划分的个数
暴力匹配
暴力匹配（Brute-Force Search）是最简单直接的向量检索方法，它通过计算查询向量 \(q\) 与数据集中每个向量 \(v_i\) 的相似度，找到最相似的 \(K\) 个向量，时间复杂度为 \(O(n \cdot d)\)
但在实际生产中，往往不需要如此精确的数据，可以通过近似算法在更短时间内获得足够好的结果，这就引出了近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）
量化
由于高维向量的存储和计算成本较高，量化（Quantization）技术被引入以减少存储空间和加速计算
量化的意思是将高维向量映射到一个较小的离散空间中，从而减少存储需求和计算复杂度
常见的量化方法包括：\(PQ\)，\(SQ\)
以上的量化方法受到了数据分布的影响，无法估计出精确的误差下界
\(2024\) 年，Jianyang Gao 和 Cheng Long 提出了 \(RaBitQ\) 量化，准确的估计了量化误差下界，并且速度和 \(PQ\)，\(SQ\) 近似
空间划分算法
空间划分算法通过将数据空间划分为多个区域，从而减少搜索空间，提高检索效率
KD 树
KD 树是一种空间划分方法，它通过递归地将数据空间划分为超平面，构建一棵二叉树，从而实现高效的近邻搜索
IVF
IVF （Inverted File）倒排索引是一种常用的空间划分方法，它通过聚类算法将数据集划分为多个簇，并为每个簇建立倒排索引
倒排索引算法具有优秀的性能，Faiss 库中实现的倒排算法结合了倒排索引和量化技术，显著提高了向量检索的效率，在 ANNBenchmarks 中表现出色
图匹配
图匹配是现在向量匹配发展的研究方向
主要的思路是将数据集中的向量表示为图中的节点，节点之间的边表示向量之间的相似度关系，下面介绍目前主流和经典的图匹配算法
NSW
NSW（Navigable Small World）图是一种基于小世界网络理论的近邻搜索算法
算法主要逻辑是把所有向量组织成一个小世界图结构，通过在图中进行贪心搜索来找到近邻
HNSW
HNSW（Hierarchical Navigable Small World）图是 NSW 的改进版本，它引入了层次结构，将图划分为多个层次，从而提高搜索效率
算法的主要逻辑是在不同层次上进行搜索，逐层缩小搜索范围，最终在底层找到近邻
一开始，认为 HNSW 对 NSW 的改进主要体现在引入了层次结构上，也就是所说的跳表，但深入研究会发现，HNSW 的层次结构实际上并未带来显著的性能提升，反而是 HNSW 在图构建和连接策略上的优化才是其性能提升的关键
NGT
NGT 是日本雅虎开源的向量检索库，核心算法基于 NSW，后续在度方面做出了多处优化
NSG
NSG（Navigable Small World Graph）是一种基于小世界网络理论的近邻搜索算法，目前主要使用该算法的开源库有 nmslib 和 pynsg
他是在 HNSW 的基础上进行改进的，主要优化了图的构建和连接策略，HNSW 在构建图时，使用了启发式方法来选择连接边，而 NSG 的入口点是固定的。
NSG 的选边策略实际上和 HNSW 是一致的
Vamana
Vamana 实际上是在 HNSW 建图算法的基础上添加了一个参数 \(\alpha\)，当 \(\alpha = 1\) 时，实际就为 HNSW 选边，但 Vamana 取不同的 \(\alpha\) 值进行了两次选边
DiskANN
DiskANN 是微软提出的一种基于磁盘存储的近邻搜索算法，主要用于处理大规模数据集
HNSW 基础实现
值得一提的是，原论文启发式选边算法中有一个错误，这种错误对于复现 HNSW 是致命的，后面会提到
原论文讲得比较复杂，通俗来讲， HNSW 就是图的跳表，每个向量为高维空间的一个点，这里把这个空间想象成一个平面，从这个平面上抽取若干个点到第一个平面，再从第二个平面抽取若干个点到下一平面，依次类推，形成一个跳表结构
在每一层平面上，点与点之间通过边连接，边的连接方式是通过启发式选边算法来实现
搜索的时候，从最高层开始，找到距离查询点最近的点，，每一层拿上一层的结果做下一层的入口点，然后逐层向下搜索，直到到达底层，最终找到最相似的 K 个点
下面结合我的代码来看看 HNSW 的具体实现，我这边的代码实现参考了
hnswlib 的实现，主要是 HNSW 主体的架构，其余优化都是在这个架构上进行的
该说不说，原论文的伪代码读着很乱，我会把伪代码贴出来，但主要还是看我的代码实现
HNSW 优化探索
References
[1] RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search | Proceedings of the ACM on Management of Data
[2] nmslib/hnswlib: Header-only C++/python library for fast approximate nearest neighbors