arXiv preprint ·
Lychee: Certified Screening of Inverted Lists for High-Recall Vector Search
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Nearest-neighbor search over embedding vectors matches faces against watchlists, transactions against known fraud patterns, and medical images against confirmed cases, where a missed neighbor is a missed threat, fraud, or diagnosis. Because an approximate index cannot report which queries lost a true neighbor, these applications require recall of 0.999 to 0.9999, at a cost far below that of exact search over billions of vectors. Inverted-file indexes reach high recall by probing more lists, but they read and score every probed vector at full precision, so that throughput falls in inverse proportion to the number of probed lists. Graph indexes saturate below these targets, whereas quantized lists must rerank their candidates with the full vectors. Our insight is to decide for almost every probed vector that it cannot enter the top k of the probed lists without reading the vector, through the certified lower bound of exact search by certified exclusion. This paper turns this insight into Lychee, a GPU inverted-file search that screens the probed lists on tensor cores under a threshold from anchors of the same lists and computes exact distances only for the few survivors. We prove that Lychee returns exactly the k nearest vectors of the probed lists, the answer of an inverted-file search at full precision, while it reads a few hundred full vectors per query regardless of the number of probed lists. On eleven datasets from one million to one billion vectors and against ten GPU and CPU baselines, Lychee is 9.7 to 117 times faster than IVF-Flat at equal recall with 200 probed lists on datasets of up to 100 million vectors. It also reaches recall levels that CAGRA and HNSW do not reach and outruns exact search by certified exclusion by 5 to 18 times above ten million vectors. On four GPUs, Lychee searches one billion vectors at recall 0.9999, 44.5 times faster than IVF-Flat on BIGANN-1B.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Retrieval
Better Reasoning, Not Just Bigger Models: A Structure-Grounded Framework for Efficient and Reliable Inference
Scaling Graph Query Processing: Focused Exploration on Partitions Using Load Balancing
The Fusion Tax: A Diagnostic Analysis of When Hybrid Retrieval Hurts
From Item Scores to Semantic Tokens: Test-Time Collaborative Adaptation for Generative Recommendation
Compiling Autoregressive LLM Control into Policy-Exact Parallel Inference for Hierarchical RAG
Get the few papers worth your time in Information Retrieval every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.