Apache Lucene向量搜索中的过滤优化：ACORN-1算法实践探索

背景与问题本质

在基于向量的相似性搜索场景中，过滤查询（Filtered kNN Search）是一个常见需求。传统HNSW（Hierarchical Navigable Small World）算法在纯向量搜索时表现优异，但当引入文档过滤条件后，其搜索效率会显著下降。核心矛盾在于：过滤条件可能破坏原始向量空间的拓扑结构，导致搜索路径上的优质候选节点被意外跳过。

ACORN-1算法核心思想

ACORN-1算法通过多级邻域扩展策略改进了传统HNSW的搜索过程，其创新点主要体现在：

1. 谓词子图遍历（Predicate Subgraph Traversal）
   仅对通过过滤条件的候选节点进行评分和收集，避免无效计算。这种策略虽然节省时间，但可能遗漏两跳之外的合格节点。

2. 有条件的两跳邻域扩展
   动态判断是否需要进行二级邻域探索：当过滤条件较严格（如仅保留5%文档）时启用扩展，保证召回率；在宽松过滤条件下保持单跳搜索以降低延迟。

3. 搜索路径优化
   不再局限于当前邻域的纯广度优先探索，而是允许跨层级访问符合过滤条件的"邻居的邻居"节点。

实现验证与性能表现

在Apache Lucene框架中的实验验证显示：

• 基准测试环境
  使用20万条Cohere嵌入向量，测试参数包括：topK=100、fanout=50、maxConn=32等，过滤选择性从5%到95%分级测试。

• 性能对比数据

  过滤选择性	原始召回率	原始延迟(ms)	优化后召回率	优化后延迟(ms)
  5%	0.037	17.182	0.028	2.744
  25%	0.166	7.348	0.157	4.614
  50%	0.332	4.376	0.308	4.833

• 关键发现
  在严格过滤条件（5%选择性）下延迟降低84%，虽然召回率略有下降，但可通过调整扩展策略平衡。中等过滤条件下性能基本持平。

技术延伸思考

1. 相关性调节机制
   需要特别关注过滤条件与查询向量的相关性。当二者呈负相关时，传统方法容易陷入局部最优，此时引入多入口点搜索（Multiple Entry Points）可能更有效。

2. 动态策略选择
   理想实现应包含：

   • 自动检测过滤条件的选择性
   • 分析过滤条件与查询向量的相关性
   • 动态选择单跳/多跳搜索策略

3. 图结构优化方向
   未来可探索量化估计构建和二分图组织等进阶技术，与ACORN-1形成互补优化。

实践建议

对于Lucene使用者，当面临以下场景时可考虑此类优化：

• 业务查询包含严格文档过滤条件
• 过滤字段与向量语义关联性较弱
• 可接受微小召回率损失换取显著延迟降低

该优化已进入Apache Lucene主干代码，开发者可通过调整HNSW参数中的enableTwoHopForSelectiveFilters等选项进行控制。