RACORN-1: Adaptive Recall-Preserving Speedup for Low-Selectivity Filtered Vector Search
2026-07-01 • Databases
DatabasesInformation Retrieval
AI summaryⓘ
The authors studied a method called Filtered Vector Search (FVS) that helps find relevant information by combining similarity searches with specific filters. They improved an existing method called ACORN-1 by creating RACORN-1, which fixes problems with missing results when filters are very strict. RACORN-1 uses clever techniques to reroute searches and keeps recall high while making searches faster. They also made RACORN-1+ to handle extremely selective queries better, combining it with an exact fallback method to keep all results while speeding up the process. Their improvements work well even when filters and queries interact in difficult ways.
Filtered Vector SearchVector EmbeddingHNSW IndexRecallLatencySelectivityAdaptive Search FallbackGraph SearchK-means ClusteringRetrieval Systems
Authors
Yoonseok Kim, Gyusik Choe
Abstract
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.