Papers

CapCover Filter:用球冠摘要加速向量库相似性预筛

CapCover Filter: Semantic Approximate Membership Queries over Embeddings

Why we picked it

做向量检索的可以看看这个论文:一个球冠结构的预筛过滤器,放在 FAISS 前面能把无效查询挡掉,实测吞吐平均提升约 116%,内存只多占 2%。如果你的场景有固定相似度阈值,比如去重或安全过滤,很省算力。

论文提出语义近似成员查询(SAMQ):当向量库中没有向量达到请求的相似度阈值时,直接拒绝该查询,且保证不产生假阴性。核心数据结构 CapCover Filter 用球冠(spherical caps)来摘要一组 embedding,其表示与具体阈值无关,一个过滤器可支持任意阈值而无需重建。

Body

在五个真实数据集上、余弦相似度阈值取 0.95 时,CapCover Filter 能消除约 20–100% 的索引访问,仅占原始 FP32 embedding 内存约 2%。放在 FAISS flat 索引之前,它使查询吞吐最高提升 382%,五个数据集平均提升约 116%,同时返回与原始范围搜索相同的结果。

作者的结论是:当相似度阈值较紧、检索成本高、索引 embedding 高度聚集时,该过滤器收益最大。论文比较了多种构建与量化方案及竞争过滤器,并开源了优化实现和评测框架。

Original · arXiv cs.AI

CapCover Filter: Semantic Approximate Membership Queries over Embeddings

Determining whether an embedding is sufficiently similar to any vector in a vector store without performing a nearest-neighbor search can substantially improve query throughput in vector-store systems. We study Semantic Approximate Membership Queries (SAMQs), which allow queries to be rejected when no indexed vector meets the requested similarity threshold, while guaranteeing no false negatives. We introduce CapCover Filter, a geometric data structure that summarizes a set of embeddings using spherical caps. Its representation is independent of the query threshold, allowing a single filter to support arbitrary thresholds without reconstruction. We evaluate alternative construction and quantization methods, compare CapCover Filter with competing filters, and measure its impact on query throughput. Across five real-world datasets, at a cosine similarity threshold of 0.95, CapCover Filter eliminates approximately 20--100\% of index accesses while using only 2\% of the raw (FP32) embedding memory. When placed before a FAISS flat index, it improves query throughput by up to 382\% and by approximately 116\% on average across the five datasets, while returning the same range-search result. We also evaluate lower similarity thresholds. Our results show that CapCover Filter can substantially improve vector-store throughput when similarity thresholds are tight, retrieval is expensive, and indexed embeddings are highly clustered. We release an optimized implementation of CapCover Filter and its evaluation framework.

Industry Coordinates & Source Verification

This report is categorized under AITOP's "Papers" desk. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include FAISS, vector search, embedding.

Source attribution: curated from arXiv cs.AI (@Dvir David Biton, Shay Hahiashvili, Nadav Keren, Gil Einziger, Roy Friedman).