Lychee speeds up high-accuracy vector search on large datasets

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

Information Retrieval

Summary

Searching for the closest items in large collections of data is used in things like recognizing faces, spotting fraud, or diagnosing diseases. The authors developed Lychee, a method that quickly filters out unlikely matches before doing detailed checks, which saves a lot of time. This works even when searching billions of items and still finds nearly all the closest matches. Lychee uses graphics processors to do this filtering efficiently and maintains very high accuracy.

What this means in practice

  • For fraud detection teams: Perform ultra-fast and highly accurate searches over large transaction patterns to detect fraud with minimal missed cases.
  • For medical image analysis teams: Compare medical imagery rapidly against large databases of confirmed cases to improve diagnosis recall at scale.

Authors

Dongfang Zhao

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.