CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching
In the authors' words
Vector search on untrusted infrastructure exposes the query embedding, a faithful summary of the user's intent. Fully homomorphic encryption can hide the query, but existing approaches still require a full scan followed by ranking of encrypted scores. Scalable private systems avoid encrypted ranking by either sending scores from a single cluster to the client or moving the search to the client, which must first stream the entire vector index for preprocessing. We present \textsc{Carousel}, which instead scores the full corpus under encryption and compresses the results for client-side ranking. The server scores every vector under encryption, raises the scores to a power that preserves their order by magnitude while suppressing all but a handful, and compresses the resulting sparse vector into a logarithmic number of ciphertexts using homomorphic additions alone. Because every vector is scored, \textsc{Carousel} incurs no recall loss from discarding candidates. Since clients hold no database-dependent state, insertions and deletions take effect immediately at the cost of a single vector write. \textsc{Carousel} searches billion vectors of BIGANN SIFT1B across multiple GPUs and achieves recall@100 of . At million SIFT vectors, it achieves recall@100 of with a query latency of seconds on a single GPU.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.