Page 126 - 《软件学报》2026年第3期

王可 等: 面向批量更新的向量索引召回率优化 1089

候选邻居集呈现致密的特性而发生系统性误判, 其后果是出现过度剪枝现象, 从而制约了索引在该类场景下的精
准度.
● HNSW 的构建、查询流程与索引参数. 基于上述两大机制, HNSW 的索引构建与查询处理得以高效执行.
在构建索引时, 一个新节点从顶层图的入口点出发, 逐层进行贪心搜索以定位其在每一层中的插入位置, 并利用前
述的启发式规则建立邻居连接; 查询过程与构建过程类似, 查询向量从顶层入口点开始, 以贪心策略迭代, 于多层
图中逐步下降, 直至在第 0 层图中完成最终的近似近邻搜索并返回结果. HNSW 索引的性能主要与以下 3 个关键
参数相关: M, 即单节点的最大邻居连接数, 其控制索引密度以平衡检索精度与计算效率; efConstruction, 简称 efC,
即建图时动态候选集大小, 其决定了图的质量与构建成本; efSearch, 即查询时动态候选集大小, 其直接权衡召回率
与查询延迟. 此外, mL 参数, 即层级生成参数, 用于控制节点层数分布.
1.3 影响 HNSW 索引召回率的相关工作

HNSW 索引的召回率受到其内在的静态拓扑结构、构建参数, 以及外在的数据、查询动态特性等多重因素
的复杂影响. 本节将围绕这两大方面, 对相关前沿工作进行综述.
大量研究聚焦于索引的静态拓扑结构与构建参数, 旨在通过优化图的内在属性来提升其召回性能上限: (1) 在
图的拓扑连通性层面, 网络的全局连通性被认为是保证节点可达性的基础. 文献 [38] 指出, 图中节点的入度不足
会破坏网络的全局连通性, 导致部分节点因路径缺失而难以在搜索中被发现. 类似地, HNSW 中的参数 M 控制着
节点的邻居数量, 其值过低同样会削弱图的连通性, 从而制约召回率的上限 [29] . (2) 在邻居选择与局部最优问题上,
文献 [22] 研究表明, HNSW 算法的贪心搜索特性会引发局部最优现象, 这一缺陷对其召回率形成显著约束. 为此,
DiskANN [34] 在其核心算法中引入参数 α 来调整长距离边的选择, 以增强跳出局部最优的能力. 这些工作表明,
HNSW 的启发式邻居选择规则是决定图导航质量的关键, 优化该规则是提升召回率的核心途径之一. (3) 在索引构
建的全局参数方面, Malkov 等人 [29] 验证了 efConstruction 和 mL 等参数的重要性, 前者决定了构建图时邻居选择
的广度, 后者则影响分层结构的合理性, 二者设置不当均会导致图的初始质量下降, 进而影响最终的召回率表现.
与此同时, 另一类研究则关注动态的外部因素对召回率的潜在影响: (1) 从数据自身特性的角度来看, Elliott
等人 [39] 首次发现, 向量数据固有的内在维度以及其写入索引的顺序会显著影响 HNSW 的图结构, 并对召回率产生
负面作用. 基于上述发现, 他们提出了一种基于内在维度计算来动态调整数据写入顺序的优化方法; (2) 关于查询
的动态特性, Li 等人 [40] 注意到不同查询在 HNSW 中的搜索难度存在差异. 其工作通过训练机器学习模型来预测
查询难度, 并对简单查询进行自适应的提前终止, 从而在保证召回率的同时优化了系统的查询延迟.
综上所述, 现有工作已从索引的静态属性与动态外部因素等多个维度对提升 HNSW 召回率的策略进行了相
应的探索. 然而, 这些研究基于一个共同的假设: 即索引的拓扑结构在构建或优化后便相对稳定. 这种假设导致其
优化策略大多属于静态、离线的场景, 或仅限于查询侧的被动调整, 因而揭示出一个关键问题: 当面向批量插入相
似数据场景时, 现有研究对索引自身的结构性退化问题关注不足, 缺乏一种动态地感知并修复索引结构的内在
机制.
受上述研究的启发, 本文将研究视角聚焦于批量数据更新场景下的图向量索引优化问题. 基于此视角, 本文的
核心贡献在于提出并验证了一种基于图结构局部自适应调整的 HNSW 优化方法: 该方法通过在索引更新过程中
赋予其局部拓扑感知与重构能力, 使其能够主动缓解因数据聚集性写入而引发的性能衰退, 从而提升 HNSW 在真
实应用中的鲁棒性与召回率.
2 问题与分析

第 2 节通过一系列对比实验, 系统性地分析 HNSW 索引在批量插入相似数据场景下的召回率退化问题. 首
先, 在第 2.1 节详细阐述实验设置与数据准备, 包括数据集的选取与处理方案、构建批量负载的方法. 然后, 在第
2.2 和 2.3 节分别从宏观性能与微观拓扑两个维度, 描述与分析召回率下降与簇内连接异常等现象. 最后, 在第 2.4