RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity
summary
The gist
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.
In short
RACORN-1 addresses recall collapse in Filtered Vector Search (FVS) algorithms like ACORN1 when selectivity is very low. It introduces RACORN-1, which uses
Key concepts
- Adaptive Search Fallback (ASF)
- This mechanism repurposes nodes that fail the filter search as 'transient bridges' to bypass broken paths in the graph. The number of these bridges grows if there aren't enough good candidates, ensuring the search frontier remains active and doesn't stall when selectivity is low.
- Stride Sampling
- Used during candidate selection, stride sampling ensures spatial diversity by extracting candidates uniformly at a specific interval (sigma) from the pool of filter-failing nodes. This prevents the search from focusing too heavily on just one neighbor, promoting a more radial exploration of the search space.
- Bridge Ratio Knob (BR)
- This adjustable parameter allows users to interpolate between different behaviors: ACORN-1's high latency advantage and HNSW's recall recovery. Tuning this knob lets operators trade search speed for better recall based on how selective their data is.
Terminology used across episodes
This episode discusses
- RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity · Paper Radio
- ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms
- SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search
- The Faiss library
- Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph
- Accelerating Large-Scale Inference with Anisotropic Vector Quantization
- Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
- ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data
- SOAR: Improved Indexing for Approximate Nearest Neighbor Search
- Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints
- A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
The paper
RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity · Read on arXiv
Yoonseok Kim, Gyusik Choe
Naver Corporation
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity".
Jane: Here's the gist of the paper. 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.
Tom: ACORN1, 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%.
Jane: 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.
Tom: Across three 1M-scale and one 40M-scale dataset, RACORN-1 delivers approximately 9–26× 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–96 and 87–98 respectively.
Title and authors: Tom: So we're looking at this paper called RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity. Jane, what's the big picture here for a listener who doesn't know what a vector search is?
Jane: Well, basically, they’re talking about combining two ways to search data: using vector embeddings for similarity and using structured metadata predicates to narrow things down. Tom, the title tells us this paper is tackling the problem of keeping that filtering working when you have very few matching results.
Lu: Exactly. The authors are focused on an algorithm called ACORN1, which is a type of in-filtering algorithm that uses an existing HNSW index. They found that while ACORN1 makes searching faster when there are few matches, it starts having problems—specifically connectivity instability and recall collapse—when the selectivity drops below about five percent and the recall drops below one percent <ref:2607.00768#pg1>.
Meng: What does "recall collapse" mean for us in production? It means if we only get a small fraction of results, the system starts missing important data entirely, which is a huge problem when you're trying to find something specific.
Tom: Right. And the authors are proposing RACORN-one as an extension to ACORN1 that fixes that collapse by adding two main things: first, an Adaptive Search Fallback or ASF, and second, stride sampling for spatial diversity <ref:2607.00768#pg1>.
Jane: It sounds like they’re trying to make the search structure smarter so it doesn't just stop working when the number of matches gets really low.
Lu: That's right. They are repurposing those nodes that fail the predicate checks into transient bridges, essentially building detour paths around sections that are blocked <ref:2607.00768#pg1>.
The paper's summary: Tom: So, what’s the core mechanism of this RACORN-one <ref:2607.00768#pg1>? Jane, can you explain how this adaptive fallback works in plain English for someone who isn't deep into graph algorithms?
Jane: Okay. When the search runs and it hits a node where the filter condition fails—meaning it doesn't satisfy our metadata predicate—instead of just stopping or failing that path, RACORN-one treats that failed node as a temporary bridge <ref:2607.00768#pg1>.
Lu: That bridge count isn't fixed; it adapts. If the number of good candidates it finds in one hop and two hops is too low, the system grows that bridge count by the deficit to keep exploring <ref:2607.00768#pg1>.
Meng: So if we’re looking for something rare, instead of just giving up on a path, it keeps trying to find a way around the dead ends? That sounds like it could help us find those rare items.
Tom: It does. And they use stride sampling for selection when there are too many candidates—when the pool gets bigger than some target size T—to make sure they aren't just stuck on one neighbor <ref:2607.00768#pg1>.
Jane: That sampling part sounds like it keeps things diverse, which is important so you don't just get tunnel vision on one type of result. So, to summarize, RACORN-one’s whole goal is to maintain a search frontier whose size doesn't depend on how selective the search is <ref:2607.00768#pg1>.
Lu: That’s the structural fix they are aiming for. The reason ACORN1 had that recall collapse is because below a certain selectivity, even two-hop expansion doesn't find enough predicate-satisfying candidates to keep the search queue going <ref:2607.00768#pg3>.
The paper's improvements: Tom: Now let’s look at the actual numbers they got. Jane, what did they find when they tested RACORN-one against the original ACORN1 <ref:2607.00768#pg1>? We need concrete results here.
Jane: They showed that across three one million scale datasets and one forty million scale dataset, RACORN-one delivers about nine to twenty-six times fewer milliseconds of latency compared to HNSW in the sweet spot, which is when selectivity is between one percent and zero point three percent <ref:2607.00768#pg1>.
Meng: That’s a big speedup. Nine to twenty-six times faster means we can handle way more queries in the same time window, which is exactly what we need for production systems. But what about the recall numbers they recovered?
Lu: They showed that RACORN-one recovers ACORN1’s recall collapse significantly <ref:2607.00768#pg1>. For example, when selectivity was at one percent, ACORN1’s recall dropped to between zero point four five and zero point seven two, but RACORN-one brought that up to seventy percent or higher <ref:2607.00768#pg1>.
Tom: And for the lowest selectivity case, when it was at zero point three percent, ACORN1’s recall was down to maybe just three percent or ten percent, and RACORN-one got that up to eighty-seven or ninety eight percent <ref:2607.00768#pg1>.
Jane: That jump from maybe ten percent back up to nearly ninety eight is what really tells you it solved the recall collapse issue they were worried about with ACORN1 <ref:2607.00768#pg1>.
Lu: And they also introduced a variant, RACORN-one plus, which combines this with an Adaptive Exact Fallback or AEF when things get really extreme <ref:2607.00768#pg1>.
Conclusion: Tom: So, to wrap up, what’s the big takeaway here for us right now? Jane, can you summarize how RACORN-one and RACORN-one plus change how we think about filtered vector search systems <ref:2607.00768#pg1>?
Jane: It means that filter-first methods don't have to choose between speed and finding results. RACORN-one uses that bridge mechanism to keep the search going even when the data is sparse, andRACORN-one plus adds an exact search switch when things are really low on selectivity <ref:2607.00768#pg1>.
Lu: The paper proves that you can get a structural improvement in how the algorithm searches without sacrificing recall at the expense of latency in those challenging low-selectivity scenarios <ref:2607.00768#pg3>.
Meng: From an engineering standpoint, this means we have a better tool to deploy when we know our data might be very sparse, because it won't just break down under those conditions <ref:2607.00768#pg1>.
Tom: And they also gave us that bridge ratio knob you can tune between ACORN1 and HNSW behavior, which lets you trade latency for recall based on what your specific dataset needs <ref:2607.00768#pg1>.
Jane: It sounds like a very practical tool for production where you need reliability across different data distributions <ref:2607.00768#pg1>.
Lu: And RACORN-one plus is really powerful because it handles the extreme low selectivity regime, like zero point three percent on one million records, giving you recall one point zero with a speedup of twenty to seventy times <ref:2607.00768#pg1>.
Meng: That speedup at that level is huge. If we can switch to linear scan at that low percentage, the performance gains are substantial <ref:2607.00768#pg1>.
Tom: So, RACORN-one and RACORN-one plus give us a robust way to handle those tricky situations where the standard filter search breaks down <ref:2607.00768#pg1>.
Jane: That’s it for this paper on RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity. We’ll see what else is coming in the next episode.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game