解决向量搜索在低选择性下的召回率崩溃问题，显著提速且保持精度。
RACORN-1: Adaptive Recall-Preserving Speedup for Low-Selectivity Filtered Vector Search
- 通过自适应桥接机制，绕过被过滤切断的路径，恢复搜索连通性。
- 在1%-0.3%选择性下，延迟降低9-26倍，召回率从0.03回升至0.77以上。
- 适用于低选择性检索场景，尤其适合RAG和生产级推荐系统。
过滤向量搜索（FVS）结合向量相似度与结构化元数据谓词，已成为RAG和生产检索系统的核心需求。现有代表性的In-filtering算法ACORN-1虽在低选择性下大幅降低延迟，但在选择性低于5%时出现连接不稳定，低于1%时发生召回率崩溃。本文提出RACORN-1，作为ACORN-1的原地扩展，通过（i）自适应搜索回退（ASF）机制——将过滤失败节点临时用作桥梁，绕开断裂路径；桥接与两跳候选选择采用步长采样以保证空间多样性，有效改善召回-延迟权衡曲线，最小化召回损失并显著降低延迟。在三个100万规模和一个4000万规模数据集上，RACORN-1在甜点区间（1%-0.3%）实现约9-26倍延迟降低，将ACORN-1的召回率由1%时的0.45-0.72、0.3%时的0.03-0.10，恢复至0.70-0.96和0.77-0.98。针对极端低选择性场景（线性扫描优于图搜索），引入（ii）自适应精确回退（AEF）的变体RACORN-1+，在100万规模≤0.1%及4000万规模0.01%下实现召回率1.00，速度提升20-75倍和13倍。在负相关评估（K-means聚类）下，当ACORN-1召回率跌至0.08-0.41时，RACORN-1仍维持0.80-0.98的召回率，并比HNSW快5-9倍。RACORN-1与RACORN-1+共同构成对极端低选择性和对抗性查询-过滤相关性的鲁棒兼容机制。
原文摘要 · Abstract (English)
Filtered Vector Search (FVS), which combines vector embedding similarity with structured metadata predicates, has emerged as a core requirement in RAG and production retrieval systems. ACORN-1, the representative In-filtering algorithm that reuses an existing HNSW index, substantially reduces latency at low selectivity but suffers connectivity instability below 5% selectivity and recall collapse below 1%. We propose RACORN-1, an in-place extension of ACORN-1 that resolves this collapse via (i) Adaptive Search Fallback (ASF) -- repurposing filter-failing nodes as transient bridges to detour around severed paths; bridge and two-hop candidate selection uses stride sampling for spatial diversity. While filter-first ACORN-family methods have a structural recall trade-off relative to distance-first HNSW, RACORN-1 improves the trade-off curve via ASF, minimizing recall loss while substantially reducing latency. Across three 1M-scale and one 40M-scale dataset, RACORN-1 delivers approximately 9-26x latency reduction over HNSW in the sweet spot (1%-0.3%), and recovers ACORN-1's recall collapse from 0.45-0.72 (1%) and 0.03-0.10 (0.3%) to 0.70-0.96 and 0.77-0.98 respectively. For the extreme-low-selectivity regime where linear scan can outperform graph search, we combine RACORN-1 with (ii) Adaptive Exact Fallback (AEF) in a variant RACORN-1+, achieving recall 1.00 with 20-75x speedup at 1M <=0.1% and 13x speedup at 40M 0.01%. Under a Negative Correlation evaluation (K-means clusters), where ACORN-1 collapses (recall 0.08-0.41), RACORN-1 maintains recall 0.80-0.98 with a 5-9x latency advantage over HNSW. Together, RACORN-1 and RACORN-1+ form an ACORN-1-compatible mechanism robust to both extreme-low-selectivity and adversarial query-filter correlation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。