Vector Index 相关技术调研

发表于 |

Vector Index 相关的一些总结吧。

存储

综述

目前存储格式基本上分两种思路：

  • 基于图的方法，如 HNSW、Vamana / DiskANN
    • 结构：向量是图里面的点。选择比较近的向量，或者能够向其他 cluster 连通的向量（Vamana）去连边。
    • 搜索方式：从入口点开始，查找当前节点的所有邻居和待查询向量的距离，然后选择最近的跳过去。重复迭代，直到找不到更近的邻居。
    • 特点：Accuracy 高，但如果图太大或者结构太复杂，IO 性能不是很好。特别地，HNSW 得全部放在内存里面。
  • 基于聚类的方法，如 IVF-PQ、SPANN、SPFresh
    • 结构：先用 KMeans 等算法对向量进行聚类，然后把这些向量都挂到对应的 cluster 下面，类似倒排索引一样（Inverted File / IVF）。
    • 搜索方式：找到最近的几个 Centroids，把倒排索引里面的向量捞出来比对。
    • 特点：对磁盘友好，数据局部性好。

量化技术

Vamana 算法

Vamana 没有 HNSW 那么多层级，它只有一层图。这一层图中，既保留了 HNSW 中最下面的稠密层类似 kNN 那样的边，但是又保留了一些长程边。这样，兼顾了 HNSW 稀疏层的“快速跨越跨度”能力和稠密层的“局部精细搜索”能力。

因为只有一层，所以 Vamana 是把一个节点及其所有的邻居节点、连同它们的原始向量，物理上紧密地排列在磁盘上的相邻位置。当算法访问节点 $A$ 时，直接把 $A$ 的向量和它所有邻居的信息整块（Block）读入内存。Vamana 严格限制每个节点的最大邻居数（例如最多 64 个）。这样可以确保“节点+邻居信息”的大小绝对不会超过磁盘的一个 Page（通常是 4KB）。

具体实现

  1. 搜索时的 Tradeoff：参数 $L$
    • $L$ 设得大： 搜索时在内存里维护的候选队列更长，探索的分支更多。代价是更慢（计算距离和磁盘 I/O 次数增加），收益是更准确（Recall 更高，不容易漏掉正确答案）。
    • $L$ 设得小： 搜索时只看眼前最近的几个节点。代价是容易掉进局部最优解（准确率下降），收益是极速返回。
  2. 建图时的 tradeoff：参数 $\alpha$
    $\alpha$ 是 Vamana 独创的 RobustPrune 算法中的参数，通常 $\alpha \ge 1$。它的真正使命是控制长程边（跨区域高速公路）的生成，从而从根本上决定搜索的跳数和效率。
    假设在建图时，节点 $A$ 已经连了邻居 $B$，现在算法在评估要不要保留通向远处 $C$ 的边：
    • 当 $\alpha = 1$ 时（严格剪枝）： 算法非常“近视”。只要通过 $B$ 通过多条短边一点点挪去 $C$ 的距离在数学上还能接受，它就会把 $A$ 直连 $C$ 的边剪掉。最终图里全都是局部短边。由于缺乏跨越巨大空间的长程边，搜索时需要一步步缓慢挪动，跳数急剧增加，导致搜索非常慢。
    • 当 $\alpha > 1$ 时（例如 1.2，适度放松）： 算法变得更加包容，会刻意保留一些跨越较大空间的长程边。这正是 Vamana 能用单层图匹敌 HNSW 多层图的奥秘。这些长程边充当了“高速公路”，搜索时能极快地跨越广阔的向量空间逼近目标区域，不仅让搜索变快（跳数大幅减少），还能跳出局部死胡同（提高准确率）。
    • 当 $\alpha$ 极大时（例如无穷大）： 算法完全不剪枝，直接退化成传统的 kNN Graph（每个点只连物理上绝对距离最近的几个点）。整张图彻底失去长程高速公路，且极易断连成一个个孤岛，导致全局搜索常常在中途断掉，准确率会暴跌。

α 的判断条件

在 Vamana 为某个中心节点建图时，它会按距离从近到远遍历所有的候选节点，并使用以下公式来决定是保留还是剪除（Prune）一条边：
如果在候选池中，存在一个节点 $p’$，满足以下条件：

$$\alpha \cdot d(p^*, p’) \le d(p, p’)$$

那么，系统就会剪掉中心节点 $p$ 直连 $p’$ 的边（将其从候选池中剔除）。
这里面的三个变量代表什么？

  • $p$：当前正在建边的中心节点。
  • $p^*$：刚才已经被 $p$ 选中的近邻节点（已经决定要连边了）。
  • $p’$：还在候选池子里，等待被评估要不要和 $p$ 连边的目标节点。
  • $d(x, y)$：表示两个节点之间的距离。

不妨令 alpha 为 1，这也意味着：如果目标节点 $p’$ 距离已选邻居 $p^*$ 的距离，比它距离中心节点 $p$ 的距离要小，那么 $p’$ 就不要连一根线去 $p$ 了。那么搜索的路径就是

$$
p \rightarrow p^* \rightarrow p’
$$

alpha 等于 1 或者无穷大的时候，都没有长程高速公路？

  • 当 $\alpha = 1$ 时（极端吝啬）
    高速公路死于：“过度追求最短路径，把长边当成了浪费”。
    • 逻辑： 当 $\alpha = 1$ 时，剪枝机制极其严格。只要 $A$ 觉得“通过 $B$ 走到 $C$ 的距离 $\le A$ 直达 $C$ 的距离”，$A$ 就会无情地把直达 $C$ 的长边剪掉。
    • 结果： 在这种极度“抠门”的策略下，算法认为任何长跨度的边都是“冗余的、不划算的”，因为总能找到一系列小短边拼凑出一条路径。
    • 资源状态： 节点手里的 64 个连边名额（$R$）可能都没用完。但它就是不愿意建长边，最后图里全是非常精简、互不重叠的小短边（在数学上这非常接近 Delaunay 三角网格）。
  • $\alpha = \infty$ 时（极端短视）
    高速公路死于：“名额被短边全部占满，根本没有余力去连远方”。
    • 逻辑： 当 $\alpha = \infty$ 时，剪枝机制彻底关闭（不再判断抄近路的问题）。算法会严格按照绝对物理距离，连接周围的点。
    • 结果： 因为距离中心节点最近的点，肯定是它身边的局部点。这些局部点会迅速消耗掉那 64 个连边名额（$R$）。
    • 资源状态： 当算法扫描到远处的节点（潜在的高速公路目标）时，发现名额已经满了。