Lychee speeds up high-accuracy vector search on graphics chips
Lychee was 9.7 to 117 times faster than the baseline IVF-Flat at equal recall with 200 probed lists on datasets of up to 100 million vectors.
Edited by Boris Djordjevic · Paperfoot
In a preprint, researchers developed Lychee, a graphics-processor search method evaluated on eleven datasets of one million to one billion vectors against ten central and graphics processor baselines. Nearest-neighbor search matches vectors, lists of numbers that represent data, to find the closest entries. Lychee screens candidate lists on specialized processor cores against mathematical bounds, calculating full distances only for vectors that pass. The authors proved that Lychee returns the exact nearest vectors of the probed lists while reading only a few hundred full vectors per query.
On datasets of up to 100 million vectors with 200 probed lists, Lychee ran 9.7 to 117 times faster than IVF-Flat at equal recall, the share of true matches found. It reached recall levels that baselines CAGRA and HNSW did not reach, and outran exact search by certified exclusion by 5 to 18 times above ten million vectors. On four graphics chips, Lychee searched the one-billion-vector BIGANN-1B dataset at 0.9999 recall, 44.5 times faster than IVF-Flat.
Why it matters
The approach enables high-recall vector search over up to one billion items on graphics chips while avoiding the sharp drop in throughput typically caused by reading full vectors. The evidence rests on a mathematical proof that candidate screening introduces no search errors within probed lists, alongside tests on eleven benchmark datasets.
Caveats
The abstract does not report whether the speed gains varied across repeated runs, and the comparisons were reported for specific search configurations like 200 probed lists. In addition, the work is a preprint that has not yet undergone peer review.
In this paper
approximate nearest-neighbor search
- Methods
- Lychee (this paper)IVF-Flat (baseline)CAGRA (baseline)HNSW (baseline)CertEx (baseline)IVF-PQ (baseline)IVF-SQ (baseline)cuVS (baseline)IVF-RaBitQ (baseline)ScaNN (baseline)Faiss IVF-Flat (baseline)
- Datasets
- BIGANN-1B (evaluated)MS MARCO (evaluated)ImageNet DINOv2 (evaluated)GIST1M (evaluated)SIFT1M (evaluated)Deep-10M (evaluated)BIGANN-10M (evaluated)BIGANN-100M (evaluated)Deep-100M (evaluated)DataComp (evaluated)
Results
- Lychee, throughput, on BIGANN-1B, n_p=1,000: 13,032 queries per second; Lychee, throughput, on BIGANN-1B, n_p=200: 21,108 queries per second; Lychee, throughput, on BIGANN-1B, n_p=500: 16,615 queries per second
On BIGANN-1B, Lychee answers 21,108 queries per second at recall 0.998 ( n_{p}=200 ), 16,615 at recall 0.9998 ( n_{p}=500 ), and 13,032 at recall 0.9999 ( n_{p}=1,000 ), against 1,455, 583, and 293 for IVF-Flat, which is 14.5 ×, 28.5 ×, and 44.5 × faster at equal recall.
4.5 Billion-Scale Search on Multiple GPUs
- Lychee, throughput, on MS MARCO, 500 probed lists: 115,163 queries per second
IVF-PQ with refinement returns the same passage at Rank 1, whereas its throughput at this setting is 1,025 queries per second against 115,163 for Lychee.
4.2 Passage Retrieval and Ranking Quality
- Lychee, queries per second, on Deep1B, recall 0.9999: 32,082; Lychee, queries per second, on Deep1B, recall 0.998: 59,466; Lychee, queries per second, on Deep1B, recall 0.9996: 43,333
The lifted rows and anchors of Lychee occupy about 70 GB per GPU, and Lychee answers 59,466 queries per second at recall 0.998, 43,333 at recall 0.9996, and 32,082 at recall 0.9999 after a build of 270 s.
4.5 Billion-Scale Search on Multiple GPUs
- Lychee, throughput, on BIGANN-100M, recall 0.9998: 75,053 QPS; Lychee, throughput, on Deep-100M, recall 0.9997: 67,548 QPS
Lychee is 9.7× to 10.4× faster than IVF-Flat at n_{p}=200, widening to 25× on BIGANN-100M (75,053 vs 2,959 QPS at recall 0.9998) and 65× on Deep-100M (67,548 vs 1,036 QPS at recall 0.9997) with full vectors in pinned host memory.
4.3 Recall and Throughput
- Lychee, QPS, on MS MARCO, 500 of 4,096 lists: 115,163 QPS
Lychee answers 115,163 QPS at this operating point compared to 704 for IVF-Flat ( 164× faster), and 201,220 vs 1,713 QPS at 200 probed lists ( 117× ).
4.2 Passage Retrieval and Ranking Quality
- Lychee, speed, on DataComp, recall 0.999: 18× faster
At recall 0.999 on DataComp, Lychee is also 18× faster than the exact search of CertEx, which answers 3,126 queries per second.
4.3 Recall and Throughput
- Lychee, QPS, on ImageNet DINOv2, n_p=200: 217,195 QPS
On wide embeddings, IVF-Flat throughput collapses as n_{p} grows, whereas Lychee sustains high throughput: at n_{p}=200, Lychee serves 217,195 QPS on DINOv2 and 131,302 on GIST1M at recall ≥ 0.998 ( 63× and 47× faster than IVF-Flat).
4.3 Recall and Throughput
What it shows
- Lychee returns exactly the k nearest vectors of the probed lists, matching the full-precision answer of an inverted-file search, while reading only a few hundred full vectors per query regardless of the number of probed lists.
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.
Abstract
- Stopping bound verification at equality prevents verifying thousands of duplicate candidate vectors that share the k-th distance of a query.
Stopping verification at equality is critical for datasets with duplicate vectors (such as DataComp), in which thousands of candidates share the k -th distance of a query and would otherwise all be verified.
3.5 Ordered Bound Verification
- Lychee can search one billion float32 vectors on a single server at recall 0.9999, whereas full-precision lists of IVF-Flat cannot fit in GPU memory.
Lychee therefore searches one billion float32 vectors on a single server at recall 0.9999, a configuration that the full-precision lists of IVF-Flat cannot hold.
4.5 Billion-Scale Search on Multiple GPUs
- Both the list-local anchor threshold and ordered verification are necessary, as the threshold bounds candidate survivors while ordered verification bounds full-precision vector reads.
Both components are therefore necessary, since the threshold bounds the survivors, whereas the ordered verification bounds their full-precision reads.
4.9 Ablation Study
Quoted word for word from the full text on arXiv.
The paper
Lychee: Certified Screening of Inverted Lists for High-Recall Vector Search
arXiv, Oct 22, 2026, Open access, CC BY-NC-ND, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.30697
arXiv:2610.30697v1 in cs.IR
Comments: 14 pages, 12 figures
Cite as BibTeX
@misc{zhao2026lychee,
title = {Lychee: Certified Screening of Inverted Lists for High-Recall Vector Search},
author = {Zhao, Dongfang},
year = {2026},
eprint = {2610.30697},
archivePrefix = {arXiv},
primaryClass = {cs.IR},
doi = {10.48550/arxiv.2610.30697},
url = {https://arxiv.org/abs/2610.30697}
}