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

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

algorithms and lead to sparsification issues in the connections among similar vectors, collectively causing a significant decline in retrieval
recall. To address these issues, this study proposes an adaptive fine-grained pruning strategy based on local adjustments to the graph
structure and constructs a comprehensive optimization scheme that integrates an identification and repair mechanism. First, in the
identification phase, the regional neighbor distance is calculated to quantify local topological density, thereby precisely locating the dense
regions requiring intervention. Second, in the repair phase, for hub nodes in dense regions, a dual pruning neighbor selection strategy is
adopted: native and modified heuristic pruning rules are applied synergistically, and the results of both rules are merged to enhance
neighbor connection diversity while maintaining retrieval accuracy, effectively alleviating over-pruning and connection sparsification issues.
Experimental results on multiple public datasets show that the proposed method demonstrates good adaptability in scenarios with frequent
data updates, achieving a 1%–4% improvement in recall while maintaining stable query latency and throughput.
Key words: approximate nearest neighbor search (ANNS); vector retrieval; graph-based vector index

向量的近似最近邻搜索 (approximate nearest neighbor search, ANNS) [1−6] 致力于在大规模高维数据 (即高维向
量) 中迅速获取目标向量的最近向量, 是当代人工智能应用, 特别是大模型相关应用中的重要技术. 在当今主流
[7]
AI 系统中, 多模态异构数据 (如文本、图像、音视频等非结构化数据) 首先经由向量嵌入 (vector embedding) [8,9]
技术将其语义抽取表征为高维向量, 向量间的几何距离 (如欧氏距离、余弦相似度等) 表征了向量间的语义关系.
在这种模式下, 在多模态数据中检索语义相近的数据的任务即转化为了向量间的最近匹配. 由于高维空间中最近
邻匹配的计算复杂度较高, 近似最近邻 (ANN) 以匹配精度换取计算的高效性, 提升了算法在 AI 应用中的可行性.
向量数据库 [10,11] 存储与管理向量数据, 集成 ANNS 等向量检索算法, 现已成为前沿大模型应用的重要数据基座.
例如, 生成式大语言模型 (generative large language model) [12,13] 、检索增强技术 (retrieval-augmented generation,
RAG) [14−17] 通过向量检索从外源数据获取相关语义来增加 LLM 的生成和推理能力, 有效地解决了大模型的幻觉 [18]
问题, 显著提升大模型生成内容的质量.
为了实现高效的 ANNS, 学术界与工业界已探索出多种索引方法, 主要分为基于树 (tree-based) [19,20] 、基于图
(graph-based) [21–23] 、基于哈希 (hash-based) [24,25] 、基于聚类 (clustering-based) [26] 和基于量化 (quantization-based) [27,28]
等几类. 其中, 基于图的 ANNS 方法因其在查询效率、召回精度与可扩展性之间取得了卓越的平衡而备受青睐.
这类方法构建并利用向量间的近邻图进行快速的图导航. 作为该领域的代表性算法, 分层可导航小世界 (hierarchical
navigable small world, HNSW) [29] 通过引入层级化的图结构与可导航小世界网络, 实现了以较低的计算开销达到较
高的召回率, 已成为当前应用最为广泛的图索引方法之一.
然而, 尽管现有的 ANNS 算法在通用场景下性能优异, 但在向量数据频繁写入场景中, 其性能面临显著挑战.
这一挑战在许多现实应用中尤为突出, 例如在知识库构建或实时推荐系统中, 新数据常以批量形式集中写入, 其批
内向量因其相似的来源或主题, 在空间中呈现高度的局部聚集性. 在这种批量插入相似数据模式下, HNSW 索引
的召回率会发生显著下降, 经过本文实验测试, 在 GIST1M 数据集上, 最大降幅达到 9%. 经研究发现, 其召回率退
化的核心原因可归结为两点: 其一是 HNSW 选择邻居关系时所采用的启发式规则引发的过度剪枝, 即在处理过度
密集的局部区域时, 该规则会误判冗余连接, 从而错误地移除能提供关键搜索方向的邻居; 其二则是相似向量连接
稀疏化的问题, 即批量插入的相似数据节点难以建立足够数量的有效邻居连接, 从而在局部形成了导航能力严重
受损的稀疏子图, 导致索引无法支撑起有效的全局导航. 正是由于缺乏对索引结构性问题的有效感知, 现有索引方
法 [30−32] 在处理相似向量的批量插入时普遍暴露其性能局限, 最终导致召回率的显著下降. 鉴于此, 在不影响性能的
前提下, 如何设计一种能够有效应对上述结构性问题的索引优化方法, 保证向量检索在动态场景下的召回率, 已成
为一个关键问题.
为了解决过度剪枝和相似向量的连接稀疏化引发的召回率退化问题, 本文提出一种基于图结构局部调整的自
适应细粒度剪枝策略. 该策略通过多阶段的识别与修复框架, 在索引构建过程中对图的局部拓扑进行精准干预. 其
核心机制包含以下 3 个环节.
(1) 数据驱动的局部致密区域识别. 为精准应对过度剪枝问题, 该策略通过数据驱动的预分析过程, 自适应地
设定识别局部密度的阈值 β. 在此基础上, 根据节点的区域邻居平均距离与全局基线的差异来识别过度致密
区域.