← 研踪 PaperTrailarXiv:2611.10622 · v1
CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching
首次提交 2026-11-07 17:58
版本更新 2026-11-07 17:58
雷达观测 2026-11-10 11:14
摘要
Vector search on untrusted infrastructure exposes the \emph{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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-07 17:58 · 最新观测版本
CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching
Vector search on untrusted infrastructure exposes the \emph{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.
查看此版本解读 →查看此版本原文 ↗