《SINDI：面向稀疏向量近似最大内积搜索的高效索引》学术报告

一、作者与发表信息
本文由Ruoxuan Li（华东师范大学）、Xiaoyao Zhong与Jiabao Jin（蚂蚁集团）、Peng Cheng（同济大学与华东师范大学）、Wangze Ni（浙江大学）、Lei Chen（香港科技大学广州校区与香港校区）、Zhitao Shen等（蚂蚁集团）、Wei Jia与Xiangyu Wang（蚂蚁集团）、Xuemin Lin（上海交通大学）、Heng Tao Shen与Jingkuan Song（同济大学）联合完成，发表于2026年的《PVLDB》期刊（Proceedings of the VLDB Endowment，卷14，第1期）。

二、学术背景
本研究属于信息检索与高维数据计算领域，聚焦于稀疏向量最大内积搜索（Sparse Maximum Inner Product Search, Sparse-MIPS）的优化问题。随着检索增强生成（Retrieval-Augmented Generation, RAG）框架的广泛应用，稀疏向量检索因其能同时保留语义信息与精确词项匹配能力（如SPLADE模型生成的稀疏向量）成为关键挑战。传统基于倒排索引（如Seismic）或图结构（如Pyanns）的算法存在两大瓶颈：
1. 冗余计算：稀疏向量的非零维度需显式匹配，时间复杂度为O(∥𝑞∥+∥𝑥∥)，且无法利用SIMD指令加速；
2. 随机内存访问：变长稀疏向量的存储格式导致频繁缓存失效，内存延迟高。
为此，作者提出稀疏倒排非冗余距离索引（Sparse Inverted Non-redundant Distance Index, SINDI），旨在通过结构化优化与算法创新实现高效检索。

三、研究流程与方法
1. 索引设计与构建
- 值存储倒排索引（Value-Storing Inverted Index）：在倒排列表中同时存储向量ID及其对应维度的值，避免检索时额外访问原始向量。算法1（PreciseSINDIConstruction）按维度聚合非零条目，并按窗口大小𝜆分区（窗口切换策略），减少内存碎片。
- SIMD加速内积计算：将内积拆分为乘积计算（SIMD批量乘）和累加（O(1)更新距离数组）两阶段，时间复杂度降至O(∥𝑞∥/𝑠)，𝑠为SIMD并行宽度。
- 向量质量剪枝（Mass Ratio Pruning, MRP）：仅保留向量中高权重的非零条目（𝛼-mass子向量），剪枝比例𝛼通过实验优化（如SPLADE数据集𝛼=0.6时召回率达99%）。

1. 查询流程优化

   • 两阶段检索（算法4 ApproximateSINDISearch）：
     *粗召回*：基于剪枝后的查询𝛽-mass子向量快速生成候选集（𝛾=500）；
     *重排序*：对候选集计算完整内积，提升精度。
     
   • 缓存友好设计：窗口切换策略将距离数组长度限制为𝜆，实验表明𝜆=100k时内存访问延迟最低（SPLADE-1M数据集）。
     

2. 实验验证

   • 数据集：涵盖多语言（英文MSMARCO、中文Antsparse）、多规模（1M至10M向量）及随机分布数据，平均稀疏度>99.5%。
     
   • 基线对比：与Seismic、Pyanns、SOSIA等5种算法比较，指标包括召回率（Recall@50/100）、吞吐量（QPS）、索引构建时间与内存占用。
     

四、主要结果
1. 效率优势：在Recall@50=99%时，SINDI单线程QPS达241，较Seismic（58）和Pyanns（24）分别提升4.2倍与26.4倍（MSMARCO数据集）。
2. 复杂度理论证明：定理3.1表明，SINDI内积计算复杂度为θ(∥𝑞∥/𝑠)，显著优于传统方法的O(∥𝑞∥+∥𝑥∥)。
3. 剪枝有效性：MRP策略在𝛼=0.5时即可将内积误差降至接近零（图6a），而LP（List Pruning）和VNP（Vector Number Pruning）误差更高（图12）。
4. 扩展性：10线程下Antsparse-10M数据集QPS达8374，核心效率损失<16%（图14）。

五、结论与价值
SINDI通过值存储倒排索引、SIMD批处理与质量剪枝三重创新，解决了稀疏向量检索中的计算冗余与内存访问瓶颈，其科学价值体现在：
1. 算法理论：提出首个支持SIMD加速的稀疏MIPS索引，复杂度严格优于现有方法；
2. 工程应用：已集成至蚂蚁集团开源库VSAG，支持亿级向量实时检索（构建时间60秒内）。

六、研究亮点
1. 创新索引结构：首次在倒排列表中存储维度值，消除ID查找开销；
2. 硬件感知优化：窗口切换策略与SIMD指令最大化CPU利用率；
3. 普适性：在分布均匀的Random-5M数据集上仍保持10倍QPS优势，证明对数据分布的鲁棒性。

七、其他贡献
- 开源代码与数据（GitHub: roxanne0321/vsag/tree/sparse）促进领域复现；
- 提出双幂律模型（公式2）量化窗口大小𝜆对内存延迟的影响，为类似优化提供理论工具。