PaperlayerView exact revision on arXiv

Source-linked AI summary

Lychee: Certified Screening of Inverted Lists for High-Recall Vector Search

Dongfang Zhao

arXiv:2610.30697v1cs.IR

TL;DR

High-recall nearest-neighbor search matters because approximate indexes can silently miss relevant vectors, while exact full-precision scans are costly. Lychee screens IVF's probed lists with certified bounds and exactly verifies the survivors. On DINOv2, it reaches 217,195 QPS at recall 0.999, 63 times IVF-Flat's throughput at the same recall.

  • Problem

    Approximate indexes can silently miss true neighbors, while high-recall IVF scans read and score every probed vector at full precision.

    Source: §1 · p. 1

  • Method

    Lychee uses a threshold from anchors of the probed lists to screen vectors with certified bounds, then exactly verifies survivors.

    Source: §1 · p. 2

  • Results

    217,195 QPS at recall 0.999 (n_p=200) on DINOv2 is 63 times IVF-Flat's throughput at the same recall.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Lychee returns exactly the k nearest vectors of the probed lists while its full-precision reads follow the survivors rather than the probed vectors.

    Source: §1 · p. 2

    The threshold uses a probed anchor set gathered in list-center order; when fewer than k anchors are available, the search falls back to an exact scan of fewer than (k + n_p)s probed vectors.

    Source: §3.3 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Lychee addresses the high cost of high-recall inverted-file search by screening probed vectors with certified bounds, then exactly verifying survivors. It preserves the exact top k of the probed lists while substantially increasing throughput.

1 Introduction

  • At recall 0.99, an index silently loses about one true neighbor in a hundred; at 0.9999, a million daily queries miss about one hundred.The passage contrasts this with about ten thousand misses at recall 0.99.Source: §1 · p. 1
  • As IVF-Flat probes 1 to 200 of 1,024 lists, DINOv2 throughput falls from 562,367 to 3,450 QPS while recall at 10 rises from 0.860 to 0.999.Figure 1 presents recall and throughput on DINOv2 embeddings.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • At n_p=200, a DINOv2 query probes about 280,000 vectors, though fewer than 200 exact distances can certify its exact top 10.Lychee targets the cost of proving that far vectors are far by screening from low-dimensional projections rather than scoring every full vector.Source: §1 · p. 2
  • Lychee derives a list-local threshold from exact distances to anchors, then screens query-list pairs on tensor cores and verifies survivors together.Its GPU implementation routes batches so each list streams through the tensor cores once per batch.Source: §1 · p. 2
  • Lychee returns exactly the k nearest vectors of the probed lists, matching IVF-Flat on those lists.It screens with certified bounds, then verifies survivors in increasing bound order until none can enter the top k.Source: §1 · p. 2
  • 217,195 QPS at recall 0.999 on DINOv2 (n_p=200) is 63 times IVF-Flat and 53 times IVF-PQ with refinement at the same recall.The evaluation spans eleven datasets from one million to one billion vectors and ten GPU and CPU baselines.Source: §1 · p. 2

2 Related Work

Related approaches change which vectors are probed, compress scanned vectors, or use graph traversal; Lychee instead screens the vectors in IVF's probed lists with certified bounds.

Partition and quantization indexes

  • Partition and quantization methods change the probed set or compress scanned vectors for full-vector reranking, whereas Lychee certifies exclusion within IVF-Flat's probed set.The passage lists partition variants and product-quantization approaches including ScaNN and RaBitQ.Source: §2 · p. 2

Graph indexes

  • Graph indexes visit few vectors per query but saturate at moderate recall, while Lychee reaches the inverted lists' recall at every n_p, up to 0.9999 on DINOv2.Lychee's screening cost grows with the survivors.Source: §2 · p. 3

Exact search and lower bounds

  • Classical lower-bound filters lose power in high dimensions, while CertEx restores it with a principal-component lift and rounding certificate for tensor cores.Lychee applies this bound inside probed IVF lists under a list-local threshold to match IVF-Flat's answer on those lists.Source: §2 · p. 3

3 Methodology

Lychee preserves the exact top-k ranking within the probed IVF lists while screening most candidates with certified bounds instead of full-precision reads. Its list-local threshold, routed tensor-core screening, and ordered verification support this guarantee while limiting full-vector reads to anchors and survivors.

3.1 Preliminaries and Background

  • IVF-Flat reads every vector in its probed lists, while Lychee uses certified lower bounds to exclude candidates without full-precision reads.The full-precision scan cost grows with the size of the probed set.Source: §3.1 · p. 3, §3.2 · p. 3

3.3 List-Local Certified Threshold

  • A threshold from exact distances to at least k distinct anchors in the probed lists bounds their k-th distance from above.If fewer than k anchors are available, Lychee uses a bound valid for every stored vector and scans the probed vectors exactly.Source: §3.3 · p. 4

3.4 Routed Tensor Screening

  • Lychee groups queries by probed list so tensor cores screen dense tiles, streaming each list once per batch.The screening retains candidates whose certified lower bound is at most the query's list-local threshold.Source: §3.4 · pp. 4–5

3.5 Ordered Bound Verification

  • Lychee verifies survivors in increasing order of their certified lower bounds and stops when the next bound reaches the current k-th exact distance.Stopping at equality avoids verifying additional candidates tied at the k-th distance.Source: §3.5 · p. 5
  • Lychee returns the exact k nearest vectors of the probed lists, matching IVF-Flat's full-precision candidate ranking.The returned list therefore retains the recall of the inverted lists at each n_p.Source: §3.2 · p. 3, §3.5 · p. 5

3.6 Cost Analysis

  • Full-precision reads cover the anchors and verified survivors, while short lifted rows screen the probed vectors.The per-query traffic ratio to IVF-Flat approaches 2D/(m+5) as n_p grows; routed screening also reuses each list across its query group.Source: §3.6 · p. 5

4 Evaluation

The evaluation spans eleven embedding and descriptor datasets from one million to one billion vectors, using two H100 GPU servers. It compares ten GPU and CPU baselines and checks recall, throughput, and exactness against defined ground truth.

4.1 Experimental Setup

  • Eleven text, image, and local-descriptor datasets cover one million to one billion vectors and 96 to 960 dimensions.Ground truth is the exact top 10; exhaustive float64 search provides it for the Deep1B prefixes.Source: §4.1 · p. 6
  • Experiments use two servers with five H100 GPUs total, with single-GPU tests on one GPU and billion-scale tests on all four GPUs of the second server.The servers share the GPU model and software stack; the second server has 192 CPU cores.Source: §4.1 · p. 6
  • Recall at 10 averages the fraction of true nearest neighbors returned, while throughput counts queries per wall-clock search time including probe, screening, and verification.Lychee's answers are checked against float64 top 10 results within its probed lists for sampled queries on every dataset.Source: §4.1 · p. 6
  • Ten baselines cover inverted-file, graph, and exhaustive search on GPUs and CPUs, with IVF indexes sweeping 1–500 probed lists or up to 1,000 on 100-million-vector datasets.CPU methods run on all 192 cores; Faiss IVF-Flat, HNSW, and ScaNN are included.Source: §4.1 · p. 6, Table 2 · p. 6

4.2 Passage Retrieval and Ranking Quality

On MS MARCO, Lychee delivers much higher throughput than IVF-Flat and refined quantized indexes at reported recall levels while maintaining passage-ranking quality. At recall 0.990 it also outpaces CAGRA, while exact CertEx is faster once recall reaches 0.997.

4.2 Passage Retrieval and Ranking Quality

  • 112×: At 500 probed lists, Lychee matches IVF-PQ with refinement’s Rank 1 passage at 115,163 versus 1,025 QPS.Across all 6,980 dev queries, their MRR@10 scores are 0.3337 and 0.3334, respectively.Source: §4.2 · p. 7
  • 164×: Lychee serves 115,163 QPS versus IVF-Flat’s 704 at recall 0.979, and 117× faster at 200 probed lists.At 200 lists, Lychee serves 201,220 QPS versus IVF-Flat’s 1,713 QPS.Source: §4.2 · p. 7
  • 2.2×: Lychee reaches recall 0.990 at 65,178 QPS, exceeding CAGRA’s 29,364 QPS and MRR@10 of 0.3352 with MRR@10 of 0.3357.At recall 0.997, Lychee serves 21,457 QPS, while exact CertEx serves 47,630 QPS and returns full MRR@10 of 0.3378.Source: §4.2 · p. 7

4.3 Recall and Throughput

Across datasets from one million to 100 million vectors, Lychee sustains higher throughput than IVF-Flat at high recall and exceeds the recall ceilings reported for graph and CPU baselines. Its advantage also holds against exact search on the cited datasets and operating points.

4.3 Recall and Throughput

  • At 200 probed lists, Lychee serves 217,195 QPS on DINOv2 and 131,302 QPS on GIST1M at recall ≥0.998, 63× and 47× faster than IVF-Flat.Lychee and IVF-Flat reach nearly the same recall at every probed-list count because both return the exact top 10 of their probed lists.Source: §4.3 · p. 7
  • On SIFT1M and Deep-10M, Lychee is 19.7× and 30× faster than IVF-Flat at 200 probed lists; CAGRA saturates at recall 0.9992 on SIFT1M while Lychee reaches 0.9998.CAGRA is faster at lower recall (≤0.995) on SIFT1M.Source: §4.3 · p. 8
  • ScaNN reaches recall 0.999 at 18,866 QPS on DINOv2 and 105,628 QPS on SIFT1M, 11.7× and 5.7× below Lychee.ScaNN saturates at recall 0.985 on GIST1M and 0.9987 on BIGANN-10M; HNSW reaches at most 0.998 on DINOv2 and 0.992 on GIST1M.Source: §4.3 · p. 8
  • On BIGANN-100M, Lychee serves 75,053 versus IVF-Flat’s 2,959 QPS at recall 0.9998; on Deep-100M it serves 67,548 versus 1,036 QPS at recall 0.9997.Lychee uses full vectors in pinned host memory on Deep-100M; on DataComp it serves 75,565 QPS at recall 0.997, 63× faster than IVF-Flat.Source: §4.3 · p. 8

4.4 Data Size Scalability

At recall 0.999, Lychee's throughput advantage over exact certified screening grows with dataset size in the reported BIGANN and Deep1B prefixes. IVF-Flat remains slower, while the paper identifies Lychee for datasets too large for exact screening of every row.

4.4 Data Size Scalability

  • At recall 0.999, Lychee reaches 1.3×, 2.0×, and 5.7× CertEx throughput on SIFT1M, BIGANN-10M, and BIGANN-100M, respectively.CertEx throughput is 449,676, 168,264, and 19,427 QPS on those datasets; Lychee screens only probed lists, whose share shrinks as the dataset grows.Source: §4.4 · p. 8
  • On Deep1B prefixes, Lychee is 1.9× faster than CertEx on Deep-10M and 5.0× faster on Deep-100M, with full Deep-100M vectors in host memory.IVF-Flat remains 10× to 69× below Lychee at recall 0.999 on all five prefixes.Source: §4.4 · p. 8
  • Lychee is identified as the method of choice when a dataset is too large for exact screening of every row, while CertEx remains the exact choice for datasets of a few million vectors.This scope conclusion follows the reported size-dependent comparison with exact screening.Source: §4.4 · p. 9

4.5 Billion-Scale Search on Multiple GPUs

On BIGANN-1B, Lychee sustains high recall while substantially outpacing IVF-Flat on four GPUs. On Deep1B, it searches one billion float32 vectors at recall 0.9999, a configuration IVF-Flat cannot build on those GPUs.

4.5 Billion-Scale Search on Multiple GPUs

  • 44.5×: On BIGANN-1B, Lychee is faster than IVF-Flat at equal recall 0.9999, serving 13,032 versus 293 queries per second.At recall 0.998, the respective throughputs are 21,108 and 1,455 QPS; at 0.9998, they are 16,615 and 583 QPS.Source: §4.5 · p. 9
  • Lychee searches one billion float32 vectors on a single server at recall 0.9999, while IVF-Flat cannot build on the four GPUs because a Deep1B shard exceeds H100 memory.Lychee’s lifted rows and anchors occupy about 70 GB per GPU on Deep1B.Source: §4.5 · p. 9
  • Lychee builds the BIGANN-1B index in 122 s, compared with 398 s for IVF-Flat.Source: §4.5 · p. 9

4.6 Workload per Query

As the number of probed lists grows, the number of vectors Lychee verifies stays nearly flat because most additional vectors are screened out. Ordered verification further reduces full-vector reads by stopping once remaining lower bounds reach the current k-th distance.

4.6 Workload per Query

  • On ImageNet DINOv2, probed vectors rise from 1,361 to 653,749 per query as lists grow, while verified vectors increase only from 131 to 152.Survivors rise from 602 to 2,905; on BIGANN-10M, probes reach 1,206,157 while survivors stay below 330 and verification ends after its first round of 32 vectors.Source: §4.6 · p. 9
  • Figure 10 tracks probed, surviving, and verified vectors per query as the number of probed lists grows.Source: Figure 10 · p. 9, §4.6 · p. 9
  • At 200 probed lists on ImageNet DINOv2, Lychee reads 151 full vectors per query versus 282,650 for IVF-Flat, or 1,870 times fewer.Ordered verification reads 16.0× fewer vectors than verifying every survivor.Source: §4.6 · p. 9

4.7 Build Time and Host-Resident Vectors

Lychee builds its index quickly and can keep full vectors in host memory while retaining only lifted rows and anchors on the GPU. This reduces GPU-memory use for wide embeddings while preserving strong throughput.

4.7 Build Time and Host-Resident Vectors

  • On BIGANN-100M, Lychee builds in 12.4 s, while CAGRA takes 362.7 s and HNSW takes 185.8 s on 192 CPU cores.On datasets up to 10M vectors, Lychee builds in 0.6 to 1.6 s; its build includes k-means training and assignment followed by one projection and encoding pass.Source: §4.7 · p. 9
  • 74,627 QPS: The host-resident configuration serves ImageNet DINOv2 at recall 0.999 with 2.0 GB of GPU memory, 22× faster than device-resident IVF-Flat.On BIGANN-10M it retains 95% of device throughput at 200 probed lists.Source: §4.7 · p. 9
  • For wide embeddings, GPU memory scales with lifted width m rather than dimension D, admitting large datasets such as Deep-100M and DataComp onto one GPU.The host-resident setup keeps full vectors in pinned host memory and reads survivors over PCIe.Source: §4.7 · pp. 9–10

4.8 Parameter Sensitivity

Wider lifted rows can sharply improve throughput by reducing full-vector verification, while the number of lists trades throughput against recall. Ablations show that both list-local thresholds and ordered verification are needed to limit survivors and full-precision reads.

4.8 Parameter Sensitivity

  • 219,325 QPS: On ImageNet DINOv2, throughput at 200 probed lists rises from 2,542 at m=127 to 219,325 at m=507 as verified vectors fall from 90,008 to 151.GIST1M peaks at m=507 with 130,112 QPS; m=763 costs more than it saves.Source: §4.8 · p. 10
  • At a 20% probe share on ImageNet DINOv2, 256, 1,024, and 4,096 lists yield 199,023, 215,598, and 96,728 QPS at recall 0.9982, 0.9990, and 0.9997, respectively.More lists raise recall at a given share; the 1,024-list default balances this with throughput, which varies by less than 2.3× across a 16-fold list range.Source: §4.8 · p. 10

4.9 Ablation Study

  • The global threshold variant increases survivors by 75.6×, 47.3×, and 256.8× on ImageNet DINOv2, SIFT1M, and BIGANN-10M, with throughput drops of 18.8×, 2.0×, and 7.5×.Recall remains at or above 0.999, but the global threshold does not guarantee U(q) ≥ r_k(q).Source: §4.9 · p. 10
  • Without ordered verification, full-vector reads grow 16.0×, 6.5×, and 10.0× on ImageNet DINOv2, SIFT1M, and BIGANN-10M, respectively.Throughput drops 6.4× on ImageNet DINOv2, from 223,688 to 34,812 QPS; it drops 2.7× and 3.4× on the other datasets.Source: §4.9 · p. 10

5 Conclusion

Lychee screens probed inverted-file lists using certified lower bounds derived from anchors in those lists, then verifies only a few survivors. It returns the exact IVF-Flat answer on the same lists and is up to 185× faster at equal recall.

  • Up to 185× faster than IVF-Flat at equal recall across eleven datasets of up to one billion vectors and ten GPU and CPU baselines.Source: §5 · p. 10
  • Lychee returns exactly the IVF-Flat answer on the same probed lists by verifying survivors in increasing order of their certified lower bounds.Source: §5 · p. 10
  • Lychee screens probed vectors on tensor cores using certified lower bounds on their k-th distance, derived from anchors in the same lists.Source: §5 · p. 10
Loading 2610.30697v1…