AI 读论文：VSAG
论文：VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search
开源代码库：https://github.com/antgroup/vsag
本文由蚂蚁集团、同济大学、英特尔和上海交大联合发表，旨在解决图基近似最近邻搜索（ANNS）在生产环境中的性能瓶颈。
📚 论文核心概览
背景问题：图基ANNS算法（如HNSW）虽然精度高，但在生产环境中面临三大瓶颈：
- 内存访问开销大：图遍历的随机跳跃导致严重的缓存未命中。
- 参数调优成本高：性能对参数极度敏感，手动调参需反复重建索引，耗时数小时甚至数天。
- 距离计算开销大：高维向量的距离计算耗时。
解决方案 VSAG：一个开源的图基ANNS优化框架，通过三大核心优化解决上述问题，在保证相同召回率的情况下，比工业标准库 HNSWlib 快高达4倍。
1. 背景与挑战详解
论文以 GIST1M 数据集（使用 SQ4 量化的 HNSW 作为基线）为例，量化了生产环境中的痛点：
| 指标 | 基线表现 (HNSW+SQ4) | VSAG 优化效果 |
|---|---|---|
L3缓存未命中率 |
67.42% (内存访问占总时间63%) |
降至 39.23% |
参数调优成本 |
暴力搜索需 >60小时 |
仅需 2.92小时 |
距离计算开销 |
占搜索时间 26.12% |
降至 0.1ms |
表1：VSAG与现有算法在GIST1M上的对比（数据来源：原文Table 1）
2. 核心优化一：内存访问优化
图算法的根本问题在于随机内存访问。VSAG 从软件和硬件两个层面进行了优化。
2.1 软件预取：从被动到主动
传统的被动加载会导致CPU stall（等待数据）。VSAG利用 _mm_prefetch 指令，在计算当前向量时，提前将下一个邻居向量加载到缓存中。
- 确定性访问：传统预取会预取已访问过的邻居（浪费带宽）。VSAG 先批量过滤出未访问的邻居，只对有效邻居发起预取。
- 步长预取：预取时机很关键，太早会被驱逐，太晚则无效。VSAG 通过参数 控制在计算第 个向量时预取第 个向量。
图解：三种预取策略对比（参考原文Figure 3）
(a) 传统方式：预取了已访问的 ，且 预取太晚。
(b) 确定性访问：跳过 ，直接安排预取 。
(c) 步长预取：在计算 时预取 ，利用计算时间掩盖内存延迟。
2.2 硬件预取与 PRS (Partial Redundant Storage)
硬件预取器擅长处理连续内存（如IVF分区），但不擅图结构的随机访问。VSAG 提出了 PRS（部分冗余存储） 机制：
- 原理：在每个图节点处，冗余存储其邻居的压缩向量。这样在访问邻居列表时，向量数据在内存中是连续的，完美触发了硬件预取。
- 资源平衡：通过冗余率 控制冗余度。
- 计算受限场景（高吞吐）：增大 ，用内存换CPU效率，减少缓存未命中。
- 内存受限场景：减小 ，节省内存。
图解：冗余率
(a) 高吞吐/高召回场景：，全冗余，最大化CPU利用率。
(b) 内存受限场景：，无冗余，允许降配实例（如4C16G降到2C8G）节省成本。
3. 核心优化二：自动参数调优
VSAG 将参数分为三类，并分别设计了自动化策略，这是本文最大的亮点。
| 参数类型 | 影响范围 | 调优难度 | VSAG策略 | 例子 |
|---|---|---|---|---|
环境级 (ELPs) |
仅QPS |
低 |
网格搜索 |
预取步长 、深度 |
查询级 (QLPs) |
QPS + Recall |
中 |
机器学习模型 (GBDT) |
搜索候选池大小 |
索引级 (ILPs) |
QPS + Recall + 构建时间 |
极高 |
基于标签的压缩索引 |
最大度数 、剪枝率 |
3.1 查询级参数 (QLPs) 自动调优
观察发现：99%的简单查询只需很小的参数即可达标，1%的困难查询才需要大参数。VSAG 训练了一个 GBDT 分类器，根据查询特征（如扫描点数、Top-5距离分布）动态决定每个查询的 ，实现了个性化参数配置。
3.2 索引级参数 (ILPs) 自动调优（核心创新）
痛点：调节 或 通常需要重建整个索引，耗时数小时。
VSAG方案：只建一次图，通过标签模拟不同参数的图。
- 数学基础：论文证明了子图包含性质（Theorem 4.1 & 4.2）。即在固定其他参数下，用严格参数（小度数/小剪枝率）构建的图，是用宽松参数构建的图的子图。
- 标签机制：
- 1) 构建时：使用最宽松的参数（如最大度数64）建图，并为每条边打上一个标签 ，表示这条边在哪个剪枝率阈值下会被保留。
- 2) 搜索时：如果想模拟严格参数（如度数16，剪枝率1.2），只需在搜索过程中过滤掉标签大于1.2的边即可。
图解：标签化调参示例（参考原文Figure 5）
假设节点 有5个邻居，标签分别为 。
若设置搜索参数 ，则标签为1.4的边 被过滤；若设置 ，则只保留前3个有效邻居。
效果：无需重建索引，即可在运行时动态尝试不同的索引参数组合。
4. 核心优化三：距离计算加速
4.1 截断标量量化
传统SQ4量化使用向量的最大/最小值作为量化范围，容易受异常值影响，导致量化精度损失。
VSAG 采用 99分位数 作为量化边界，舍弃1%的异常值，大幅提升有效量化精度。
图解：截断量化（参考原文Figure 6）
利用99%的数据分布范围进行量化，避免被极值干扰。
4.2 选择性重排序
全精度计算耗时，低精度计算有误差。VSAG 采用两阶段策略：
- 使用低精度（INT8/INT4）进行图遍历。
- 仅对最终候选集进行全精度（FLOAT32）重排序。
5. 实验评估
5.1 整体性能
VSAG 在所有数据集上均达到SOTA。特别是在高维数据（如OPENAI 1536维）上，相比HNSWlib有 4倍 的加速。
图表：整体性能对比（参考原文Figure 7）
在 GIST1M 和 OPENAI 等高维数据集上，VSAG（红色/左上角曲线）在相同 Recall 下 QPS 显著高于 hnswlib 和 faiss。
5.2 消融实验
下表展示了各项优化技术的累积效果：
| 策略叠加 | GIST1M QPS | L3 缓存未命中率 | 说明 |
|---|---|---|---|
Baseline |
510 |
93.89% |
基础图搜索 |
+ 1. 量化 |
1272 |
67.42% |
大幅降低距离计算耗时 |
+ 2. 软件预取 |
1490 |
71.71% |
改善部分访问延迟 |
+ 3. 步长预取 |
1517 |
64.57% |
优化预取时机 |
+ 4. ELP自动调优 |
2052 |
45.88% |
找到最佳预取参数，效果显著 |
+ 5. 确定性访问 |
2167 |
39.23% |
减少无效预取 |
+ 6. PRS () |
2255 |
55.75% |
内存与算力平衡 |
+ 7. PRS () |
2377 |
71.62% |
极致吞吐量（牺牲部分缓存指标换CPU效率） |
表2：VSAG策略消融实验（数据来源：原文Table 5）
5.3 调优成本对比
| 方法 | GIST1M 调优时间 | GIST1M 内存占用 |
|---|---|---|
FIX (固定参数) |
3.20 H |
3.83 G |
BF (暴力搜索) |
61.64 H |
89.87 G |
VSAG (标签法) |
2.92 H |
4.07 G |
表3：ILPs调优成本对比（数据来源：原文Table 6）
分析：VSAG的调优时间仅为暴力搜索的 1/20，内存占用仅为 1/22，且性能更优。
6. 总结
VSAG 通过深入理解硬件特性（缓存行、预取器）和算法特性（图结构的子图包含性），提出了三大针对性优化：
- 内存：软件预取 + PRS冗余存储，治好了图算法的“缓存缺失病”。
- 调参：基于标签的索引压缩，将“重建索引调参”降维为“搜索时过滤边”，实现了秒级参数切换。
- 计算：截断量化 + SIMD指令 + 重排序，平衡了速度与精度。
该框架已应用于蚂蚁集团的支付和推荐系统，并在大模型（RAG）的高维向量检索中展现出巨大潜力。