WorksComputer Science
CapCover Filter: Semantic Approximate Membership Queries over Embeddings
Abstract
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.
Introduction
Modern database and data-management systems increasingly use vector embeddings to represent and query unstructured data. Retrieval-Augmented Generation (RAG) retrieves passages from dense vector indexes [1]; vector database systems provide similarity search over high-dimensional representations [2, 3]; and semantic caches compare incoming requests with previously served requests to determine whether a result can be reused [4, 5, 6, 7]. Related uses of learned representations include semantic deduplication [8] and large-scale recommendation systems [9]. Across these settings, semantic proximity often becomes part of a system’s decision that is implemented through a vector search, even when the application needs only a binary indication of whether a sufficiently close vector exists.
We focus on applications that need only this binary answer, such as a semantic cache that rejects a query as a miss once no cached request meets its cosine similarity threshold, or a retrieval pipeline that screens queries before a costlier search or verification stage. When negative queries are common, answering them cheaply avoids substantial downstream work.
For unit-normalized embeddings, let denote cosine similarity. Throughout the paper, denotes the query’s cosine-distance threshold, corresponding to a minimum cosine similarity of . Given an indexed set and a unit query , the exact semantic-membership predicate is
Classical Approximate Membership Query (AMQ) structures, such as Bloom filters and their relatives, summarize a set compactly and may return false positives while preserving definite rejection of nonmembers [10, 11, 12]. The natural question is whether a similar compact one-sided filter can support semantic proximity.
We refer to the semantic query analogue as a Semantic Approximate Membership Query (SAMQ). A SAMQ returns YES for every query satisfying , while it may also return YES for some queries whose nearest indexed vector has cosine similarity below . Like a conventional one-sided AMQ, it trades false positives for a compact representation while preserving zero false negatives. This definition is independent of the representation used to implement it.
Distance-sensitive membership is itself well established (Section II), but existing structures encode proximity through locality-sensitive hashes and collisions, and similarity-search indexes retain point-level information needed to recover neighbors. We instead store a bounded collection of enclosing regions that together contain all indexed vectors: a query far from every stored region is rejected without examining any individual vector.
The geometric representation makes the coverage of the indexed set explicit, allowing us to impose a fixed physical memory budget directly on the filter. Each stored region may summarize many indexed vectors, and the number and precision of the regions can be chosen according to the available memory. As more vectors are summarized within the same budget, approximation appears as additional covered space, potentially increasing false positives, while the covering invariant continues to preserve zero false negatives. Another useful property of the geometric representation is that its construction is independent of the query threshold. The stored regions depend on the indexed vectors and the representation budget, while appears only in the query-time acceptance condition. Consequently, the same constructed filter supports multiple cosine-distance thresholds.
More formally, embeddings are unit-normalized, so only their direction matters, and we realize SAMQs using a collection of at most spherical caps
whose union contains every indexed embedding, where . We call this representation the CapCover Filter. As illustrated in Figure 1, a query is accepted whenever
Figure 1. Embeddings on the unit sphere are covered by caps, each defined by a direction and an angle . On query, each cap is conceptually widened by the angle corresponding to the cosine-distance threshold , resulting in an outer boundary of . A query vector is accepted for verification if it falls within at least one widened cap.
for some stored cap, where is the angle corresponding to cosine distance on the unit sphere. Geometric containment and the triangle inequality for angles immediately imply that every query having cosine similarity at least to an indexed vector is accepted. False positives arise from the additional space admitted by the enclosing caps.
Constructing a tight cover under a fixed memory budget is the central algorithmic problem. Our selected construction, soft anneal, starts from Gonzalez’s farthest-first directions [13] followed by minimax refinement, then attempts to reduce the total volume of the enclosing caps. We use reduced-precision directions, with angles re-measured so that the covering invariant, and with it the zero-false-negative guarantee, is preserved.
Summary of Contributions
We present CapCover Filter, a byte-budgeted geometric filter for SAMQs. Soft anneal constructs compact cap covers, while direction quantization and conservative angle remeasurement preserve coverage and zero false negatives (Sections III, III-C and IV-B).
We prove coverage-based correctness, analyze query and construction costs, and relate false positives to the cover’s geometric footprint and the query distribution. We also establish construction guarantees and a worst-case space lower bound for uniform queries (Sections IV and IV-D).
Across five corpora, we evaluate construction and encoding choices, compare zero-false-negative filters at equal memory budgets, and measure throughput gains before an exact flat index. The results distinguish filtering selectivity from query cost, test the volume objective as an encoding-selection heuristic, and identify the backend-cost break-even condition (Section V).
Related Work
Approximate and distance-sensitive membership
Approximate membership structures represent a set compactly while allowing false positives, so that definite non-members bypass more expensive operations [10, 11]. Kirsch and Mitzenmacher’s distance-sensitive Bloom filters answer whether a query is close to some member using locality-sensitive hashing [14]. The Locality-Sensitive Bloom Filter (LSBF) studies the resulting false-positive and false-negative rates [15], and multi-granularity filters support several query distances from one representation [16, 17]. One-sided structures have no false negatives: CoveringLSH guarantees a collision for every close pair in Hamming space [18, 19], and no-false-negative locality-sensitive structures exist for metrics and Euclidean near-neighbor search [20, 21, 22]. Learned Bloom filters replace part of the filter by a trained classifier and restore the one-sided guarantee with a backup filter [23, 24]. In contrast, CapCover Filter needs no training and takes its guarantee from geometry. Range filters such as SuRF and Rosetta answer range emptiness for keys [25, 26], and filtered vector search restricts nearest-neighbor search by attributes [27]; neither decides whether any neighbor exists. These representations are hash- or point-oriented, whereas the CapCover Filter replaces the indexed observations at query time by a bounded conservative cover, and can be viewed as approximate range emptiness [28] for spherical caps.
Similarity search and metric indexes
ANN methods retain enough information to locate or approximate the distance to individual indexed vectors: LSH [29, 30], Multi-Probe LSH [31], and graph-based indexes such as HNSW [32], whereas SAMQ may discard point identities after construction. Metric indexes (M-tree [33], cover trees [34]) use regions to prune within a point-level index. Conversely, in a CapCover Filter the regions are the whole query-time representation.
Vector quantization and compressed representations
Product Quantization (PQ) [35], Optimized PQ [36], the scalar and PQ quantizers of FAISS [37], and RaBiTQ [38] reduce the memory cost of high-dimensional similarity search. These methods compress individual indexed vectors while retaining enough information for candidate retrieval or distance estimation. Our CapCover Filter applies quantization to the geometric representation itself: a smaller direction code fits more caps into the same bytes and can reduce the angles of the cover, while the displacement it introduces is accounted for conservatively so that coverage is never violated.
Geometric covering, streaming summaries, and semantic caching
The metric -center problem controls the largest cluster radius, with Gonzalez’s farthest-first algorithm [13] being a factor-2 approximation under the triangle inequality [13] (angular distance is such a metric). Other works minimize the sum [39], squares [40], or other norms [41] of the radii. Our membership objective is related: in dimensions a cap’s measure scales as , so the accepted region is dominated by the widest caps, and the total measure of the caps is our tractable surrogate. BIRCH, streaming clustering, and BICO keep bounded clustering summaries of a stream [42, 43, 44]. Semantic caches (GPTCache [4], MeanCache [5], vCache [6]) decide whether reuse is valid and under what threshold. SAMQ addresses the orthogonal question of whether definite misses can be identified from a compact representation first.
CapCover Filter
We now describe the geometric realization studied in this paper for the SAMQ abstraction introduced in § 1. Our goal is to represent the region occupied by the indexed embeddings using a compact collection of enclosing regions, while guaranteeing that every true semantic match remains accepted. Our implementation also supports insertions, but for the sake of brevity we restrict our presentation and evaluation to the static setting.
Geometric Representation
Write the indexed embeddings as . A CapCover Filter stores a collection of closed spherical caps, where .
We say that is a valid cover of if , that is, for every indexed embedding there is a stored cap with .
Recall the exact semantic-membership predicate from § 1. Given a query embedding and cosine-distance threshold , the CapCover Filter returns YES whenever some stored cap satisfies , and returns NO otherwise. This query rule defines the behavior of our geometric realization. Other representations, such as a ball-based filter, may implement the same one-sided membership interface differently.
Memory Budget and Geometric Objective
The physical memory cost of a CapCover Filter depends on both the number of stored caps and their representation. A cap requires a -dimensional direction and a single angle, making caps a parameter-efficient geometric primitive. The numerical encoding of these parameters then determines how many caps can be stored within a given memory budget. We write for the filter’s memory footprint and for the raw embedding array’s size, both in bytes, and often reference the “compression ratio” .
Let denote the total memory budget in bytes and let denote a particular representation of the directions and angles. Let denote the number of bytes required per cap under encoding , including its direction, angle, and per-cap metadata, and let denote the number of bytes of representation-wide state, such as shared quantization metadata or codebooks. The corresponding cap budget is
Thus, is not itself a physical memory budget. Once the available memory and representation are fixed, they induce the number of caps that can be stored. A more compact representation may permit a larger , while also introducing numerical approximation into the stored directions and angles.
For a fixed representation, we seek a valid cover with small total cap volume. Let denote the normalized surface measure of a cap of angle . We target the additive volume objective
This objective sums the volumes of the unexpanded caps containing the indexed embeddings, counting overlapping regions more than once. It is independent of the query threshold . Although the union volume measures the covered region exactly, computing it is challenging, and bounds vary in tightness. We therefore use the additive objective as a tractable surrogate, which we empirically find to correlate with filtering effectiveness. We also use the maximum cap angle as a surrogate: in high dimensions, cap volume grows rapidly with angle below , so the widest cap often dominates the additive objective.
We also use the expanded-cap measure , which upper-bounds the measure of the accepted region. Section IV-E relates this quantity to false positives.
Static Cover Construction
Our selected static construction uses soft anneal (Section III-C3). We initialize the directions using Gonzalez’s farthest-first algorithm [13], apply minimax refinement (Section III-C2), and then use soft anneal to improve the unexpanded cap-volume objective . We then encode the resulting directions at reduced precision and conservatively re-measure the stored angles to preserve the covering condition. Note that following quantization, an embedding might end up closer to a different centroid than the one it was originally assigned to.
Because the encoding determines the cap budget in Equation (2), different encodings yield different covers under the same memory budget. Given a set of candidate encodings, our default auto configuration constructs a cover for each using its corresponding cap budget and a uniform encoding for all directions. After quantization and the volume-based reassignment check described below, it selects the representation with the smallest unexpanded cap-volume objective:
| Symbol | Meaning |
| , , | Indexed set, size, dimension |
| , | Query vector; members assigned to cap |
| Cosine-distance threshold | |
| , | Angular and chord thresholds |
| Exact membership predicate | |
| Cap with direction and angle | |
| , , | Cover, cap count, cap limit |
| , | Maximum cap angle; minimum with at most caps |
| , | Decoded direction; angular error |
| , , | Byte budget, encoding, cap budget |
| , | Bytes per cap; shared overhead |
| , | Filter and raw-vector bytes |
| Normalized cap measure at angle | |
| , | Unexpanded and expanded volume sums |
| , | Query law; uniform spherical measure |
| , , | Covered, true-positive, accepted regions |
| Maximum distance to the nearest point in over | |
| Query probability within angle of | |
| , | Query count; fraction of accesses saved |
| , | Average filter cost; constant backend cost |
Table I. Main notation; specialized symbols are defined in the text.
Section V-C evaluates this tradeoff. In the end-to-end and baseline experiments (§ 5-B and V-E), the candidates are drawn from TQ (TurboQuant) and SPQ (Seeded Product Quantization) configurations, excluding other methods empirically dominated in compression and query throughput.
Farthest-First Cover Construction
For a given cap budget , we initialize the cover using Gonzalez’s farthest-first algorithm under angular distance [13]. Starting from an arbitrary indexed embedding, the algorithm repeatedly selects the embedding farthest from its nearest selected direction, until directions have been chosen. Each indexed embedding is then assigned to its nearest direction. For the assigned set , we set , yielding a valid cover by construction.
Because angular distance is a metric, farthest-first provides a factor-2 approximation to the minimum possible maximum cap angle (Theorem IV.6). The traversal selects directions solely by distance, without accounting for cluster density or the resulting total cap volume. It can therefore allocate directions to isolated points while leaving dense clusters covered by wide caps, motivating the refinements below.
Minimax Refinement
Minimax refinement follows a Lloyd-style assignment-and-update procedure [45], replacing centroid updates with approximate enclosing-cap fitting. Each round assigns every vector to its nearest direction, then refines each cluster’s direction using 64 Bădoiu–Clarkson-style updates [46], , where is the member farthest in angular distance from the current direction. The resulting center is normalized to obtain a unit direction, and the cap angle is remeasured over all assigned members.
We perform five rounds and retain the cover with the smallest maximum cap angle, including the Gonzalez initialization as round zero. Thus, before quantization, refinement cannot worsen the maximum-angle objective relative to Gonzalez. We selected these constants empirically: they improved cover quality, while additional iterations provided diminishing returns. Since construction is performed once in our static setting, we prioritize cover quality over construction speed.
Soft Anneal
Soft anneal refines the minimax directions to reduce the unexpanded cap-volume objective . Writing , we softly assign each vector to its nearest directions using , refreshing the candidate lists every four iterations. We optimize the smooth surrogate
The softmax is restricted to each vector’s candidate list, and the sums over include only vectors listing direction . We do not explicitly weight cap contributions by their member counts. Although favoring tighter caps in denser regions improved FPR in our experiments, this benefit may reflect the similarity between the query and indexed-data distributions. We omit such weighting to avoid assuming that indexed-data density predicts query density in other workloads.
A Riemannian Adam variant [47], with , updates the unit directions using tangent gradients, normalization retraction, and projection transport of momentum. Over 300 iterations, , the learning rate, and follow geometric schedules from to , to , and to , respectively. Every ten iterations, we evaluate using hard nearest-direction assignments and maximum member angles.
We retain the best evaluated iterate, including the minimax initialization, and accept a final minimax round with 64 Bădoiu–Clarkson-style updates only if it further reduces . Before quantization, the returned cover therefore has no larger than the minimax initialization. Measuring cap angles over all assigned members preserves coverage (Theorem IV.1).
Soft anneal takes substantially longer than the preceding stages. It is appropriate when additional construction time is available to improve the volume objective; minimax alone offers a less expensive alternative.
Quantization
After constructing the cover, we encode all cap directions using a single reduced-precision encoding . Let denote the angle of cap before encoding, and let be its decoded unit direction. Keeping the assigned members fixed, we remeasure the cap angle as
where is the angular encoding error. The resulting cover preserves coverage by Proposition IV.3. We then tentatively reassign every indexed vector to its nearest decoded direction, remeasure the cap angles over their new members, and discard empty caps. This produces another
Algorithm 1 CapCover Filter Construction
Require: Nonempty indexed set $X$, byte budget $\mathcal{B}$, candidate encodings $\mathcal{E}$ with at least one feasible encoding
1: $\mathcal{E}_{\mathrm{feasible}} \leftarrow \varnothing$
2: for each encoding $E \in \mathcal{E}$ do
3: Compute $k_E$ from Equation 2
4: if $k_E \ge 1$ then
5: Add $E$ to $\mathcal{E}_{\mathrm{feasible}}$
6: Initialize $\min\{k_E, |X|\}$ directions by farthest-first
7: Apply minimax refinement (Section III-C2)
8: Apply soft anneal to improve $V$ (Section III-C3)
9: Assign each $x \in X$ to its nearest direction, forming $X_i$
10: for each direction $u_i$ with nonempty $X_i$ do
11: Encode $u_i$ using $E$ and decode its unit direction $\tilde{u}_i$
12: $\theta_i^{\mathrm{fix}} \leftarrow \max_{x\in X_i} \angle(x,\tilde{u}_i)$
13: Round $\theta_i^{\mathrm{fix}}$ outward as needed
14: Let $C_E^{\mathrm{fix}}$ be the resulting valid cover
15: Reassign each $x \in X$ to its nearest decoded direction
16: Remeasure cap angles over the new members
17: Round the remeasured angles outward as needed
18: Let $C_E^{\mathrm{re}}$ be the resulting valid cover
19: $C_E \leftarrow C_E^{\mathrm{fix}}$
20: if $V(C_E^{\mathrm{re}}) < V(C_E^{\mathrm{fix}})$ then
21: $C_E \leftarrow C_E^{\mathrm{re}}$
22: $E^\star \leftarrow \arg\min_{E\in\mathcal{E}_{\mathrm{feasible}}} V(C_E)$
23: return $C_{E^\star}$
valid cover, . We retain the reassignment only if it strictly reduces the unexpanded cap-volume objective:
Otherwise, we retain the original assignments with their remeasured angles. Both candidates are evaluated using the angles that would be stored, rounded outward as needed to preserve coverage. Thus, either choice preserves coverage, and the retained cover has no larger than .
We do not compress cap angles since each requires only one scalar, so we focus compression on the -dimensional directions. Each angle is measured around the decoded direction, so it absorbs the direction’s quantization error, and it is rounded upward when stored so that coverage is preserved. We also evaluated selecting an encoding separately for each cap, but the small FPR improvement did not justify the loss in query throughput.
For stored caps, a query scan costs , plus any encoding-specific preprocessing, such as rotation or lookup-table construction. A dense rotation adds work per query. Farthest-first construction and each full nearest-direction assignment pass cost ; total construction cost depends on the refinement iterations and candidate encodings.
Algorithm 1 summarizes the static construction.
Theoretical Analysis
Setting and notation
We assume a nonempty indexed set with , unit query vectors, and cosine-distance threshold . Angular distance is a metric. With ,
The equivalent Euclidean chord threshold is , giving . We use angular distance unless Euclidean distance is explicitly indicated.
We interpret cap angles at least as covering the entire sphere. Throughout this section, consists of decoded unit directions and stored angles . Writing , validity means . The filter accepts a query exactly when
for some .
The analysis assumes exact arithmetic and this acceptance rule.
For a query distribution and filter , define
provided that negative queries have positive probability. We also use a cover to denote the filter it induces under the specified decoding rule.
Let denote the uniform probability measure on . The normalized cap measure is independent of and satisfies
We extend as zero for and one for , and write for the maximum cap angle.
The following bounds quantify how cap angles affect covered surface area. For , the substitution shows that is nondecreasing. By continuity and ,
For , the same substitution yields
The lower bound follows from the preceding monotonicity. The upper bound follows by bounding the transformed integrand’s factor between and .
Correctness
Theorem IV.1 (No false negatives). Every valid cover accepts every query with .
Proof. Choose with and a cap containing . The angular triangle inequality gives .
Proposition IV.2 (Exact cap neighborhood). A query is within cosine distance of some point in if and only if .
Proof. The minimum angular distance from to the cap is ; apply (4).
Thus the accepted region is exactly the angular -neighborhood of .
Proposition IV.3 (Quantization preserves coverage). For a nonempty assigned set , let . With and as in Section III-C4, . Any stored angle covers , including an angle encoded on a grid and rounded outward.
Proof. Apply the angular triangle inequality to each member of .
Comparison with Ball Covers
Let cover . Euclidean expansion accepts
Each nonempty intersection is a spherical cap, possibly the entire sphere. These intersections define a valid cover with at most caps. Let denote the region accepted by under angular decoding.
Theorem IV.4 (Angular decoding of a ball cover). For every ball cover and ,
Consequently, whenever is defined,
Proof. An accepted cap query is within chord distance of some . Thus .
The excess accepted area can be substantial even for a ball whose spherical intersection is exactly the cap being expanded. For , the ball intersects the sphere exactly in .
Corollary IV.5 (Expansion overhead). Let , , and . Euclidean expansion of this ball accepts , where
Its accepted surface measure satisfies
which grows exponentially with for fixed and .
Proof. Expanding gives . Before clipping, its cosine threshold is smaller than by
The measure bound follows from (5) and monotonicity.
This comparison concerns angular versus Euclidean expansion of the same ball–sphere intersections. A ball decoder using their exact spherical neighborhoods matches the converted cap decoder. The single-cap surface-measure ratio does not imply the same ratio for unions of caps or workload FPR.
Construction Guarantees
Let denote the minimum maximum angle of a valid cover with at most caps.
Theorem IV.6 (Farthest-first angular guarantee). For , farthest-first with nearest-direction assignment produces a cover satisfying
Proof. If the final radius is , the selected points and a point attaining are pairwise separated by at least . Two belong to the same cap of an optimal cover, so . Monotonicity of gives the second bound. Both bounds also hold for $R=0.
Farthest-first can incur a volume penalty exponential in dimension. For , place pairs at on a great circle, where and . Inter-pair distances exceed , farthest-first selects one endpoint per pair regardless of initialization or tie-breaking. Nearest-direction assignment then produces caps of angle . Caps centered at their midpoints instead cover the points with angle . Thus, if denotes the minimum additive volume of a valid cover with at most caps,
Hence the factor-two angle guarantee does not imply a dimension-independent volume approximation.
Geometric Footprint and False Positives
Let
denote the true-positive and accepted regions. Validity gives .
Proposition IV.7 (Accepted mass and false positives). For any query distribution with ,
In particular, . More generally, if is absolutely continuous relative to with density at most almost everywhere, then .
Proof. For and , since . The remaining bounds follow from the union bound and the density bound.
Corollary IV.8 (Clustered data). If lies in at most caps of angle , with , then its unquantized farthest-first cover satisfies, whenever is defined and ,
Proof. The assumed cover gives , hence . Apply the preceding proposition and the cap-measure bound. □
These bounds describe the unquantized farthest-first cover, not the soft-anneal covers evaluated in § 5. This bound decays exponentially with when for fixed and . These bounds concern expanded caps; reducing the unexpanded objective does not by itself guarantee lower workload FPR. For arbitrary query distributions, we can instead bound false positives by the probability mass near the true matching boundary.
Theorem IV.9 (Cover-excess shell bound). For the stored region , define
Whenever ,
Proof. Every accepted query is within angle of some , which is within of an indexed point. Thus every false positive lies in the shell
Conditioning its probability on a negative query proves the bound. □
The quantity measures the cover’s excess angular reach and is independent of the query threshold. If each cap contains its nonempty assigned set , the triangle inequality gives
Thus the same cover-excess bound applies across all thresholds, although it can be loose when the cover contains wide caps.
Space Lower Bound
We derive a representation-independent bound for deterministic filters over the continuous sphere. All persistent data-dependent information occupies a fixed array of bytes; the decoder accesses only this state, the query, and fixed parameters. Encoding and query rules are measurable. The proof combines spherical isoperimetry with finite-state counting, following ideas from similarity identification [48, 49].
Theorem IV.10 (Uniform-sphere space lower bound). Fix , , , and , with
Every deterministic structure representing all -point subsets of , with no false negatives and conditional uniform-query FPR at most for every dataset, requires
Here is the inverse cap-measure function on .
Proof. For each used state , let be its accepted region. For any dataset represented by this state, the FPR guarantee gives
No false negatives imply that every represented point belongs to
For , the angular -neighborhood of lies in . Spherical isoperimetry [48 Lemma 2, journal version], followed by , therefore yields
An ordered tuple of independent uniform points has distinct entries almost surely and belongs to for some state. Each such product set has measure at most , and there are at most states. Hence . □
When , we have . Writing , we have , and the cap-measure bound gives
Consequently,
Here as . As an example, for , , , and , the theorem gives approximately 4.08 bytes per indexed vector.
This bound requires the FPR guarantee for every dataset under uniform queries. It does not bound the space needed for a particular clustered dataset or an empirical workload.
Evaluation
Our evaluation examines how much work a compact filter can save before a query reaches the vector index. We build filters under different memory budgets and test them on queries whose correct answers are established by exact search. We measure both how often the filter avoids an index lookup and whether the saved work outweighs the cost of filtering. Additional plots, raw data, and the evaluation framework are available online [50].
Experimental Setup
Workloads
Workloads: We evaluate CapCover Filter on five datasets that feature paraphrased or semantically similar data: WildChat [51], user prompts to LLM chat services; CC-News [52], lightly rewritten news articles; WikiAnswers [53], questions grouped as paraphrases; Quora [54], question pairs labeled as semantic duplicates; and ChatGPT-Paraphrases [55], source texts paired with LLM-generated paraphrases. We embed all corpora with all-MiniLM-L6-v2, which produces normalized embeddings.
Fold selection
We construct five folds per dataset while preserving the original corpus order. Indexed sets are consecutive blocks of 80,000 embeddings selected from the beginning of the corpus, while query sets are consecutive blocks of 20,000 embeddings selected from its end. Each fold pairs the corresponding indexed and query blocks. Thus, the first fold uses the first 80,000 embeddings for indexing and the last 20,000 for querying; subsequent folds advance inward from both ends. All selected blocks are disjoint. We apply the same selection procedure to every corpus and report the mean and one standard deviation across the five folds.
Ground truth and thresholds
We establish ground truth by exact cosine-similarity search over the indexed embeddings. Write for a query’s maximum similarity to the indexed set. A query is positive when , and negative otherwise. These labels follow the embedding-space membership criterion, independently of the duplicate or paraphrase annotations of the corpora. For each fold and memory budget, we reuse a single stored cover across all evaluated thresholds. This isolates the effect of the query threshold while holding the filter representation fixed.
Metrics
We report the false-positive rate (FPR) and false-negative rate (FNR):
Let be the total number of queries. With zero false negatives, the fraction of index accesses saved is , since rejected queries bypass the backend index. When negative queries are present,
Thus, savings equal the fraction of negative queries multiplied by , and the negative-query fraction sets the maximum achievable saving. We report as the percentage of accesses saved. If no query is negative, the savings are zero.
In some evaluations, to distinguish distant negatives from those near the indexed set, we grouped negative queries by their maximum cosine similarity to an indexed vector: least related (), moderately related (), and most related ().
Methods and memory accounting
We compare different construction methods for selecting the stored caps, all of which cover the entire indexed set and allow zero false negatives. The construction methods heuristically minimize the volume of stored caps, since we do not estimate the query distribution. Quantization experiments compare TQ [56], [57] and SPQ. Unless otherwise stated, the filter uses soft anneal with automatic encoding selection as described in Section III-C. Equal-memory comparisons account for each method’s query-time representation, including codes, angles, hash tables, bucket entries, identifiers, and other required metadata. Memory is reported relative to the raw FP32 embedding array. The filter is additional to the backend index, and its actual cap count depends on the encoding selected for the filter within the byte budget.
For vectors of dimension , MB.
Implementation and timing
Our implementation uses Python with a Rust query kernel exposed through PyO3. We use FAISS [37] for exact search and the flat backend index. The implementation is open-sourced and available online [50].
End-to-end timing experiments run on one pinned CPU core, one job at a time, and process queries individually. For each memory budget and threshold, we warm both paths and alternate baseline and filtered query passes, reporting the median total query runtime over three repetitions. Filter construction and first-query preparation are recorded separately. Data loading, backend construction, ground-truth computation, correctness checks, and memory accounting are outside the query timers. We measure filter-only query time separately for backend-cost projections. Per-query transformations and backend searches remain part of the timed query paths.
End-to-End Filtering Benefit
We evaluate the benefit of placing a CapCover Filter in front of an exact FAISS flat index. Queries rejected by the filter bypass the index, while accepted queries require an exact search. Since the filter guarantees zero false negatives, the fraction of queries with no similar indexed vector provides an upper bound on the reduction in index accesses.
We use soft anneal with automatic encoding selection (§ 5-C), varying the memory budget () and cosine-distance threshold ().
Index accesses saved
The memory sweep in the top row of Figure 2 shows that CapCover Filter can avoid a substantial share of backend searches while using relatively little memory. Increasing the budget brings savings closer to the ceiling set by each workload’s share of negative queries. The proximity breakdown in Figure 2 helps explain this gap: negatives close to indexed embeddings remain difficult to reject even at the largest evaluated memory budget, while more distant negatives are filtered effectively. This behavior reflects the excess space introduced by geometric summarization.
Figure 2. Filtering benefit of CapCover Filter. Top: memory ratio – at . Bottom: cosine-distance threshold – at a memory ratio of . The first three columns report FPR for negative queries grouped by their maximum similarity to the indexed set. The last column reports index accesses saved; dashed lines show each dataset’s negative-query fraction. Each filter uses automatic encoding selection; a band is not drawn where it has no negative queries. Error bars show standard deviation across five folds.
The bottom row of Figure 2 examines a similarity threshold sweep while keeping the stored cover and its memory footprint fixed. Increasing expands each cap’s acceptance region, increasing the number of queries forwarded to the index.
On most datasets, savings fall below the negative-query ceilings as the threshold becomes more permissive. Queries closest to the indexed embeddings become difficult to reject first, followed by more distant negatives as the acceptance regions expand further.
ChatGPT-Paraphrases retains effective filtering over a wider threshold range because its queries are predominantly farther from the indexed set. The useful operating range thus depends jointly on the requested cosine-distance threshold and the proximity of negative queries to the indexed embeddings.
Throughput
To measure the end-to-end impact, we compare an unfiltered FAISS flat index with the same index preceded by CapCover Filter. Both configurations use exact range search for queries reaching the backend, while rejected queries bypass that search.
The measured results in Figure 3 show that, at , a filter occupying of the raw embedding memory increases throughput by on average across the five datasets, ranging from (CC-News) to (ChatGPT-Paraphrases), with a median of . Avoided searches therefore more than compensate for the cost of filtering. Looser thresholds avoid fewer searches and reduce the throughput gain.
Figure 3. Throughput improvement (%) by adding a CapCover Filter to a flat FAISS index. Left: vs. (cosine distance) at 2% of . Middle: vs. the memory ratio , at . Right: modeled improvement versus backend lookup cost, using independently measured filter-only query time and the acceptance rate at and 2% memory. Markers show measured end-to-end improvement at the measured flat-index cost. Negative improvements denote slowdowns. Error bars in the left and middle panels: standard deviation over five folds.
The cost projection in the right panel of Figure 3 further shows how the value of rejection depends on the backend. More expensive lookups make each avoided search more valuable, allowing the same filter cost and rejection rate to produce a larger throughput gain. The benefit therefore depends on both filtering selectivity and the cost of the operation it bypasses.
a) Break-even cost: Let denote the average filter cost and a constant backend lookup cost. With rejection rate , the average filtered query costs , giving the break-even condition for .
The right panel of Figure 3 simulates the benefit of applying CapCover Filter as a function of the backend cost .
Larger flat indexes provide more search work to avoid, while the same cost model suggests potential benefits for approximate disk-resident or remote indexes and expensive verification stages.
Quantization
Direction encoding determines how a fixed memory budget is divided between the number of caps and the precision of their directions. Compact codes permit more caps and potentially tighter covers, while the representation error can increase the angles needed to enclose the indexed vectors. We preserve coverage by recomputing these angles around the decoded directions (Section III-C4).
Figure 4 compares TQ [56] and SPQ [35], alongside automatic encoding selection. SPQ generates its codebooks from a fixed seed, allowing their entries to be reconstructed instead of stored explicitly with the filter.
Figure 4. FPR (top) and modeled throughput improvement (%, bottom) versus at , one column per corpus. Auto (thick black line, stars) and seven fixed encodings are shown: SPQ 16 × 12, 12 × 12, 6 × 8, and TQ1–TQ4, selected by mean rank of accesses saved across corpus–budget cells. The model combines batched filter-query cost and acceptance rates with a mean flat-index lookup cost of 5.29 ms from end-to-end measurements. The horizontal axis is logarithmic; the bottom vertical axis is symmetric-log, with negative values indicating slowdowns. Curves show means over five folds. Auto selects the feasible encoding with the smallest unexpanded cap volume.
The memory sweep shows that the best encoding depends on both the workload and the available budget. The automatic configuration remains broadly competitive. Query cost adds another factor to the choice of quantization method. Thus, our default method, auto, may only select from a set of quantizations that were found to be most effective and efficient for this use case (memory aligned TQ and SPQ). The filter chooses the encoding that yields the cover with the smallest unexpanded cap-volume objective (Section III-C). We empirically found that a smaller correlates with a lower FPR in our evaluations. Among the plotted encodings, TQ1 gives the highest modeled throughput improvement in 34 of the 40 corpus–budget cells; TQ2, TQ3, or auto lead in the others. The model uses batched filter-query times, whereas Figure 3 times queries individually, so the modeled gains are not directly comparable to the measured ones.
At 0.5% memory, FPR is near one on Quora and CC-News, whereas ChatGPT-Paraphrases already has auto FPR 0.026, falling to 0.002 at 1%. At 2%, SPQ 16 × 12 and 12 × 12 have lower FPR than TQ4 on WildChat, Quora, and CC-News, but both incur modeled slowdowns on all five corpora. The auto configuration selects the slower SPQ methods when they beat TQ on volume. Thus, when using auto, the quantization options should be carefully selected to balance FPR and speed.
Figure 5 shows a positive association between unexpanded volume and FPR on every corpus (–). Budget drives both quantities: correlating the seven fixed encodings within each budget and averaging over the eight budgets gives only (CC-News) to (WikiAnswers), and 14 of the 40 corpus–budget correlations are negative. Encodings also differ in FPR at comparable volumes, so the pooled association supports as a heuristic, not a reliable ordering of encodings at fixed memory.
Figure 5. FPR versus , the unexpanded cap-volume sum, at , one panel per corpus. Each point averages FPR and over five folds for one encoding–budget pair, using the seven fixed encodings in Figure 4 with the same markers. Auto (stars) repeats the point of the encoding it selects and is excluded from the correlations. Panel annotations give the Spearman correlation over the fixed-encoding points, pooling budgets.
Construction Methods
Figure 6 compares Gonzalez, minimax, and soft anneal to examine how the construction method affects the FPR of CapCover Filter as a function of the memory ratio. Minimax may only decrease the maximum angle Gonzalez provides, while soft anneal may only reduce the unexpanded cap-volume objective minimax provides. The figure compares unquantized FP32 directions with TQ2 and TQ4 directions. While TQ2 achieves a lower FPR by storing more caps, once it stores a cap per indexed vector (clear in the Quora workload), it stops improving. Eventually, TQ4 achieves a lower FPR due to a lower quantization error.
Figure 6. FPR versus memory ratio at cosine-distance threshold , for Gonzalez, minimax, and soft anneal. Each method is shown with unquantized FP32, TQ4, and TQ2 directions. The memory axis is logarithmic. Error bars: standard deviation over five folds.
Construction timings are measured sequentially on one pinned CPU core and include all stages used by each method. Minimax includes its Gonzalez initialization, while soft anneal additionally includes minimax. For 80,000 vectors without applying quantization, total construction time ± standard deviation averaged (5.88±3.48) seconds for Gonzalez, (15.02±7.51) seconds for minimax, and (355.58 ± 128.82) seconds for soft anneal, making minimax a reasonable middle ground between runtime and quality.
Comparison Against Baselines
We compare methods at equal query-time memory budgets to determine where geometric summaries provide useful filtering relative to alternative representations. Curves begin at the first sampled feasible budget.
We compare against VA+-file [58], which uses lower bounds to KLT-rotated quantization cells; zero-FN LSH schemes [21, 22], which preserve close pairs through adjacent floor-hash cells; and a quantized point set using RaBitQ [38] codes with conservative bounds on representation error.
Figure 7 shows that CapCover Filter provides useful rejection at compressed operating points where the other evaluated one-sided representations remain ineffective or do not fit. Both zero-FN LSH schemes fit within small budgets but have FPR 1: their representations preserve close pairs, yet provide no useful exclusion on these workloads. The advantage of the geometric cover is consistent with its ability to summarize multiple indexed vectors within each stored region, sharing the representation cost across their members.
Figure 7. Mean FPR of zero-false-negative methods, at cosine-distance threshold . Curves begin at the first sampled feasible budget.
As budget increases, point-oriented representations gain enough precision to reject queries effectively. VA+-file can then achieve lower FPR than CapCover Filter, while the quantized point set becomes feasible at larger budgets. The resulting crossover identifies the benefit of geometric summaries for rejection when memory is too restricted to represent individual vectors effectively.
a) Methods that allow false negatives: In Figure 8 we compare four baselines that may report a true member as absent. DSH [59] stores distance-sensitive hash signatures and accepts a query whose signature collides with a stored one; unlike CapCover Filter, it fixes at construction. An MLP regresses the distance to the nearest indexed vector and accepts when the prediction is at most . IVF-PQ [35] and HNSW [32] accept when their approximate search returns a vector within .
On Quora, IVF-PQ attains low FPR from 0.7% memory but misses about half of the true members there (FNR 0.52), and HNSW fits only from about 5%, where its FNR is 0.16. DSH keeps FNR below 0.02, but its FPR stays above CapCover Filter’s from 1.4% memory on and levels off at about 0.17, whereas CapCover Filter reaches 0.06 at 10% with no false negatives. MLP accepts nearly every query at every budget and therefore provides no filtering.
Conclusion
We introduced CapCover Filter, a compact cap cover that rejects semantic nonmatches before index search while guaranteeing zero false negatives. Construction and encoding choices affect selectivity and cost, while conservative angle remeasurement preserves coverage.
The results distinguish geometric quality from system performance. More accurate encodings can lower FPR yet reduce throughput, as seen with SPQ and at 2% memory. Encoding selection should therefore account for backend cost: the best representation depends on whether avoided searches compensate for its scan cost. Unexpanded volume is a useful objective, but its strong association with FPR across budgets weakens when comparing encodings at fixed memory.
Representative queries could help select among candidate encodings, with coverage retaining the independent correctness guarantee. Smaller volume alone does not guarantee better rejection on a particular workload. Geometric summarization is
Figure 8. FPR (left) and FNR (right) versus on Quora at , with CapCover Filter (zero FNR) as reference. Curves begin at the first sampled feasible budget.
most valuable where multiple vectors can share a stored region; point-oriented representations become competitive as budgets grow. Construction introduces a further tradeoff: additional refinement must be amortized over subsequent queries, making the query volume between rebuilds relevant alongside filter size and scan cost. Future work includes encoding selection informed by backend cost, construction tailored to expected query volume, and space bounds for clustered embeddings.
References
References
- [1]P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Kuttler, M. Lewis, W.-t. Yih, T. Rocktäschel, S. Riedel, and D. Kiela, “Retrieval-augmented generation for knowledge-intensive nlp tasks,” in Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 9459–9474.arxiv.org/abs/2005.11401
- [2]J. J. Pan, J. Wang, and G. Li, “Survey of vector database management systems,” The VLDB Journal, vol. 33, no. 5, pp. 1591–1615, 2024.arxiv.org/abs/2310.14021
- [3]J. Wang, X. Yi, R. Guo, H. Jin, P. Xu, S. Li, X. Wang, X. Guo, C. Li, X. Xu, K. Yu, J. Yuan, Y. Zou, J. Long, Y. Cai, Z. Li, Z. Zhang, Y. Mo, J. Gu, R. Jiang, Y. Wei, and C. Xie, “Milvus: A Purpose-Built Vector Data Management System,” in Proceedings of the 2021 International Conference on Management of Data. ACM, 2021, pp. 2614–2627.DOI
- [4]F. Bang, “GPTCache: An Open-Source Semantic Cache for LLM Applications Enabling Faster Answers and Cost Savings,” in Proceedings of the 3rd Workshop for Natural Language Processing Open Source Software (NLP-OSS 2023). Singapore: Association for Computational Linguistics, Dec. 2023, pp. 212–218. [Online]. Available: https://aclanthology.org/2023.nlposs-1.24/
- [5]W. Gill, M. Eldrici, P. Kalapatapu, A. Ahmed, A. Anwar, and M. A. Gulzar, “MeanCache: User-Centric Semantic Caching for LLM Web Services,” in Proceedings of the 39th IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2025, pp. 1298–1310.DOI
- [6]L. G. Schroeder, A. Desai, A. Cuadron Lafuente, K. Chu, S. Liu, M. Zhao, S. Krusche, A. Kemper, M. Zaharia, and J. E. Gonzalez, “vCache: Verified Semantic Prompt Caching,” in International Conference on Learning Representations (ICLR), 2026, arXiv:2502.03771. [Online]. Available: https://proceedings.iclr.cc/paper_files/paper/2026/hash/9559cd211de7a8f5672eacf3cd232cc-Abstract-Conference.htmlarxiv.org/abs/2502.03771
- [7]D. D. Biton and R. Friedman, “Semantic caching: From exact hits to close enough,” in Proceedings of the 35th ACM International Conference on Information and Knowledge Management (CIKM ’26). Rome, Italy: ACM, 2026, pp. 340–350.
- [8]A. Abbas, K. Tirumala, D. Simig, S. Ganguli, and A. S. Morcos, “SemDep: Data-Efficient Learning at Web-Scale Through Semantic Deduplication,” arXiv #2303.09540, 2023, https://arxiv.org/abs/2303.09540.
- [9]P. Covington, J. Adams, and E. Sargin, “Deep neural networks for youtube recommendations,” in Proceedings of the 10th ACM Conference on Recommender Systems, 2016, pp. 191–198.DOI
- [10]B. H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, vol. 13, no. 7, pp. 422–426, Jul. 1970.DOI
- [11]L. J. Carter, R. W. Floyd, J. Gill, G. Markowsky, and M. N. Wegman, “Exact and Approximate Membership Testers,” in Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC). ACM, 1978, pp. 59–65.DOI
- [12]A. Broder and M. Mitzenmacher, “Network Applications of Bloom Filters: A Survey,” Internet Mathematics, vol. 1, no. 4, pp. 485–509, 2004.
- [13]T. F. Gonzalez, “Clustering to minimize the maximum intercluster distance,” Theoretical Computer Science, vol. 38, no. 2–3, pp. 293–306, 1985.DOI
- [14]A. Kirsch and M. Mitzenmacher, “Distance-sensitive bloom filters,” in Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2006, pp. 41–50.
- [15]Y. Hua, B. Xiao, B. Veeravalli, and D. Feng, “Locality-Sensitive Bloom Filter for Approximate Membership Query,” IEEE Transactions on Computers, vol. 61, no. 6, pp. 817–830, 2012.
- [16]J. Qian, Q. Zhu, and H. Chen, “Multi-Granularity Locality-Sensitive Bloom Filter,” IEEE Transactions on Computers, vol. 64, no. 12, pp. 3500–3514, 2015.DOI
- [17]——, “Integer-Granularity Locality-Sensitive Bloom Filter,” IEEE Communications Letters, vol. 20, no. 11, pp. 2125–2128, 2016.
- [18]R. Pagh, “Locality-Sensitive Hashing without False Negatives,” in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2016, pp. 1–9.DOI
- [19]M. Goswami, R. Pagh, F. Silvestri, and J. Sivertsen, “Distance sensitive bloom filters without false negatives,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2017, pp. 257–269.arxiv.org/abs/1607.05451
- [20]T. D. Ahle, “Optimal Las Vegas Locality Sensitive Data Structures,” in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017, pp. 938–949.arxiv.org/abs/1704.02054
- [21]A. Pacuk, P. Sankowski, K. Węgrzycki, and P. Wygocki, “Locality-Sensitive Hashing Without False Negatives for ℓp,” in Computing and Combinatorics (COCOON 2016), ser. Lecture Notes in Computer Science, vol. 9797. Springer, 2016, pp. 105–118.DOI
- [22]P. Sankowski and P. Wygocki, “Approximate Nearest Neighbors Search Without False Negatives For ℓ2 for c > √log log n,” in 28th International Symposium on Algorithms and Computation (ISAAC 2017), ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 92. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017, pp. 63:1–63:12.
- [23]T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The case for learned index structures,” in Proceedings of the 2018 International Conference on Management of Data, ser. SIGMOD ’18. Association for Computing Machinery, 2018, pp. 489–504.arxiv.org/abs/1712.01208
- [24]M. Mitzenmacher, “A model for learned bloom filters and optimizing by sandwiching,” in Advances in Neural Information Processing Systems, vol. 31, 2018, pp. 462–471.arxiv.org/abs/1901.00902
- [25]H. Zhang, H. Lim, V. Leis, D. G. Andersen, M. Kaminsky, K. Keeton, and A. Pavlo, “SRF: Practical range query filtering with fast succinct tries,” in Proceedings of the 2018 International Conference on Management of Data, ser. SIGMOD ’18. Association for Computing Machinery, 2018, pp. 323–336.DOI
- [26]S. Luo, S. Chatterjee, R. Ketsetsidis, N. Dayan, W. Qin, and S. Idreos, “Rosetta: A robust space-time optimized range filter for key-value stores,” in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’20. Association for Computing Machinery, 2020, pp. 2071–2086. [Online]. Available: https://dl.acm.org/doi/10.1145/3318464.3389731DOI
- [27]S. Gollapudi, N. Karia, V. Sivashankar, R. Krishnaswamy, N. Begwani, S. Raz, Y. Lin, Y. Zhang, N. Mahapatro, P. Srinivasan, A. Singh, and H. V. Simhadri, “Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters,” in Proceedings of the ACM Web Conference 2023, ser. WWW ’23. Association for Computing Machinery, 2023, pp. 3406–3416.
- [28]M. Goswami, A. Grønlund, K. G. Larsen, and R. Pagh, “Approximate range emptiness in constant time and optimal space,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2015, pp. 769–775.arxiv.org/abs/1407.2907
- [29]P. Indyk and R. Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC). ACM, 1998, pp. 604–613.
- [30]M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, “Locality-sensitive hashing scheme based on p-stable distributions,” in Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG), 2004, pp. 253–262.DOI
- [31]Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li, “Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search,” in Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 2007, pp. 950–961. [Online]. Available: https://www.vldb.org/conf/2007/paper/related/950-lv.pdf
- [32]Y. A. Malkov and D. A. Yashunin, “Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 42, no. 4, pp. 824–836, 2020.
- [33]P. Ciaccia, M. Patella, and P. Zezula, “M-tree: An Efficient Access Method for Similarity Search in Metric Spaces,” in Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 1997, pp. 426–435. [Online]. Available: https://www.vldb.org/conf/1997/P426.PDF
- [34]A. Beygelzimer, S. Kakade, and J. Langford, “Cover trees for nearest neighbor,” in Proceedings of the 23rd International Conference on Machine Learning (ICML), 2006, pp. 97–104.
- [35]H. Jégou, M. Douze, and C. Schmid, “Product Quantization for Nearest Neighbor Search,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 1, pp. 117–128, 2011.DOI
- [36]T. Ge, K. He, Q. Ke, and J. Sun, “Optimized product quantization for approximate nearest neighbor search,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 2946–2953.DOI
- [37]M. Douze, A. Guzhva, C. Deng, J. Johnson, G. Szilvasy, P.-E. Mazaré, M. Lomeli, L. Hosseini, and H. Jégou, “The faiss library,” 2024.
- [38]J. Gao and C. Long, “RaBitQ: Quantizing High-Dimensional Vectors with Theoretical Error Bound for Approximate Nearest Neighbor Search,” Proceedings of the ACM on Management of Data, vol. 2, no. 3, 2024.arxiv.org/abs/2405.12497
- [39]M. Gibson, G. Kanade, E. Krohn, I. A. Pirwani, and K. Varadarajan, “On Metric Clustering to Minimize the Sum of Radii,” Algorithmica, vol. 57, no. 3, pp. 484–498, 2010.
- [40]Z. Friggstad and M. Jamsidhian, “Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii,” arXiv 2412.16327, https://arxiv.org/abs/2412.16327, 2024.
- [41]R. Jaiswal, A. Kumar, and J. Yadav, “FPT Approximation for Capacitated Sum of Radii,” in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 287. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 65:1–65:21.
- [42]T. Zhang, R. Ramakrishnan, and M. Livny, “BIRCH: An Efficient Data Clustering Method for Very Large Databases,” in Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. ACM, 1996, pp. 103–114.
- [43]L. O’Callaghan, N. Mishra, A. Meyerson, S. Guha, and R. Motwani, “Streaming-Data Algorithms for High-Quality Clustering,” in Proceedings of the 18th International Conference on Data Engineering (ICDE). IEEE, 2002, pp. 685–694.
- [44]H. Fichtenberger, M. Gillé, M. Schmidt, C. Schwiegelshohn, and C. Sohler, “BICO: BIRCH Meets Coresets for k-Means Clustering,” in Algorithms – ESA 2013, ser. Lecture Notes in Computer Science, vol. 8125. Springer, 2013, pp. 481–492.DOI
- [45]S. P. Lloyd, “Least squares quantization in PCM,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, 1982.DOI
- [46]M. Bädui and K. L. Clarkson, “Smaller core-sets for balls,” in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 801–802. [Online]. Available: http://dl.acm.org/citation.cfm?id=644108.644240
- [47]G. Bécigneul and O.-E. Ganea, “Riemannian adaptive optimization methods,” in International Conference on Learning Representations, 2019. [Online]. Available: https://openreview.net/forum?id=r1eqi09K7arxiv.org/abs/1810.00760
- [48]A. Ingber, T. Courtade, and T. Weissman, “Compression for quadratic similarity queries,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2729–2747, 2015.
- [49]F. Steiner, S. Dempfle, A. Ingber, and T. Weissman, “Compression for quadratic similarity queries: Finite blocklength and practical schemes,” IEEE Transactions on Information Theory, vol. 62, no. 5, pp. 2737–2747, 2016.DOI
- [50]“Paper Implementation and Additional Data,” November 2026, https://github.com/dbiton/SemanticAMQ.
- [51]W. Zhao, X. Ren, J. Hessel, C. Cardie, Y. Choi, and Y. Deng, “WildChat: 1M ChatGPT Interaction Logs in the Wild,” arXiv preprint arXiv:2405.01470, 2024, dataset site: https://wildchat.allen.ai. [Online]. Available: https://arxiv.org/abs/2405.01470
- [52]F. Hamborg, N. Meuschke, C. Breitinger, and B. Gipp, “news-please: A Generic News Crawler and Extractor,” in Proceedings of the 15th International Symposium of Information Science (ISI), 2017, pp. 218–223.DOI
- [53]A. Fader, L. Zettlemoyer, and O. Etzioni, “Paraphrase-Driven Learning for Open Question Answering,” in Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL), 2013, pp. 1608–1618. [Online]. Available: https://aclanthology.org/P13-1158/
- [54]S. Iyer, N. Dandekar, and K. Csernai, “First Quora Dataset Release: Question Pairs,” https://quoradata.quora.com/First-Quora-Dataset-Release-Question-Pairs, 2017.
- [55]V. Vorobev and M. Kuznetsov, “ChatGPT Paraphrases Dataset,” https://huggingface.co/datasets/humarin/chatgpt-paraphrases, 2023.
- [56]A. Zandieh, M. Daliri, M. Hadian, and V. Mirrokni, “TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate,” arXiv 2504.19874, https://arxiv.org/abs/2504.19874, 2025.
- [57]S. Vargaftik, R. Ben-Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, and M. Mitzmacher, “EDEN: Communication-efficient and robust distributed mean estimation for federated learning,” in Proceedings of the 39th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 162, 2022, pp. 21 984–22 014. [Online]. Available: https://proceedings.mlr.press/v162/vargaftik22a.htmlarxiv.org/abs/2108.08842
- [58]H. Ferhatosmanoglu, E. Tuncel, D. Agrawal, and A. El Abbadi, “Vector Approximation Based Indexing for Non-Uniform High Dimensional Data Sets,” in Proceedings of the 9th International Conference on Information and Knowledge Management (CIKM), 2000, pp. 202–209.
- [59]M. Aumüller, T. Christiani, R. Pagh, and F. Silvestri, “Distance-Sensitive Hashing,” in Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018, pp. 89–104.arxiv.org/abs/1703.07867







