arXiv CSopen access

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search

arXiv:2606.29968v1 [cs.DB] 29 Jun 2026

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search Yitong Song

Shuhang Lu

Xuanhe Zhou

Hong Kong Baptist University [email protected]

Shanghai Jiao Tong University [email protected]

Shanghai Jiao Tong University [email protected]

Pengcheng Zhang

Jianliang Xu

Tencent Inc. [email protected]

Hong Kong Baptist University [email protected]

ABSTRACT Vector search has become a core component of modern multimodal retrieval systems. Among existing methods, inverted file (IVF)–based methods are widely adopted due to their scalability, efficient updates, and hardware friendliness. However, they are fundamentally limited by coarse-grained execution: each query typically probes many clusters and exhaustively scans all vectors within them, resulting in high query latency. Prior works mitigate this using pruning strategies, but they often incur substantial extra pruning overhead, lack cluster-level pruning, and compromise update efficiency due to heavy maintenance of pruning metadata. This paper proposes CLIP, a lightweight cosine-law–based pruning technique that supports both inter- and intra-cluster pruning, substantially reducing unnecessary cluster and vector accesses with negligible overhead. First, CLIP exploits the monotonicity of cosinelaw–based lower bounds, enabling eliminating an undesirable cluster in 𝑂 (1) time and filtering batches of irrelevant vectors in logarithmic time in the list size, with a tight analytical guarantee. Second, building on this, we develop two IVF variants: IVF-CLIP, which integrates CLIP into IVFFlat, and HIVF-CLIP, which extends it with a hierarchical structure for adaptive sub-cluster probing. Third, for dynamic workloads, we present LSM-IVF, an LSM-inspired design that supports fast updates by deferring index maintenance to background compaction, and enables efficient queries via CLIPbased optimizations that eliminate costly level-by-level searches. Extensive experiments show that CLIP variants achieve up to 78% pruning and 69% higher efficiency over static IVF baselines, while LSM-IVF improves throughput by up to 141% over dynamic IVF baselines with comparable update efficiency.

1

INTRODUCTION

Vector search aims to retrieve the top-𝑘 most similar vectors from large-scale, high-dimensional datasets under similarity metrics such as Euclidean distance, typically formulated as Approximate Nearest Neighbor (ANN) search. It has become a cornerstone of modern multi-modal retrieval systems [37, 50, 54], supporting a broad range of applications such as image-to-image retrieval [41], music recognition [1], and code assistants [20]. To support efficient ANN queries, Inverted File (IVF)–based methods have been extensively developed [2, 10, 30, 34, 53]. These methods operate by clustering the entire vector dataset into partitions that group similar vectors together. Each cluster is associated with an inverted list recording its assigned vectors. At query time, the top-𝑛𝑝𝑟𝑜𝑏𝑒 closest clusters are first identified by comparing their

Table 1: Comparison of cluster access, data access, and pruning complexity at 99% recall, with cluster count set to 4,096, where 𝑙 denotes the inverted list length and 𝑠𝑢𝑏𝐾 is a constant. Legend: ✗= Not supported, ★= Best performance. Methods / Metrics IVFFlat [2] (traditional) Tribase [51] (other pruning) IVF-CLIP (ours)

Accessed Cluster Count GloVe Deep

Accessed Data Ratio GloVe Deep

500

400

35%

10%

500

400

34%

10%

✗

𝑂 (𝑙)

𝑂 (𝑙+ 𝑙 · 𝑠𝑢𝑏𝐾)

441 ★

215 ★

21% ★

4% ★

𝑶 (1) ★

𝑶 (2 log 𝒍) ★

𝑶 (𝒍) ★

Traditional Pruning 1

nprobe-based pruning

Pruning Complexity (per Cluster) Clus.-Prun. Vec.-Prun. Extra Stor.

✗

Inter-Cluster Pruning 2

Min-lower-boundbased pruning

Intra-Cluster Pruning 3

Lower-bound-based pruning

Query (nprobe = 3)

sorted by the distance to

Figure 1: Core pruning mechanism of CLIP. cluster centroids with the query vector. The vectors within these clusters are then scanned to compute exact distances and yield the top-𝑘 most similar results. The parameter 𝑛𝑝𝑟𝑜𝑏𝑒 controls the query efficiency and accuracy trade-off: larger values generally improve accuracy but reduce efficiency. Owing to their practical scalability, update friendliness, highly parallelizable structure, and satisfactory query performance, IVF-based methods have been widely adopted in real-world vector retrieval systems [2, 10, 34, 40, 44, 48, 53]. Despite these advantages, IVF-based methods suffer from a fundamental bottleneck: they must access a large number of clusters and scan all vectors within them to perform expensive distance computations, leading to limited query efficiency. As shown in Table 1, achieving 99% query recall requires the classic IVF-based method (IVFFlat) to probe 500 and 400 clusters, accessing 35% and 10% of the data vectors on the GloVe and Deep datasets, respectively. To alleviate this limitation, the recent work Tribase [51] applies triangle-inequality–based pruning within each probed cluster, where all vectors in these clusters are evaluated individually and only the vectors that remain after pruning are then involved in distance computations. However, Tribase still has several limitations:

Yitong Song, Shuhang Lu, Xuanhe Zhou, Pengcheng Zhang, and Jianliang Xu

(1) it offers no cluster-level pruning and still relies solely on 𝑛𝑝𝑟𝑜𝑏𝑒 to control the number of accessed clusters; (2) it incurs substantial pruning overhead due to per-vector bound evaluation, resulting in 𝑂 (𝑙) pruning complexity (where 𝑙 is the inverted list length) and 𝑂 (𝑙 +𝑙 ·𝑠𝑢𝑏𝐾) metadata storage; (3) it shows low pruning ratios due to its rigorous triangle-inequality–based pruning conditions; and (4) it undermines the update efficiency of IVF-based methods, as the widely-used in-place update strategy requires frequent cluster reorganization, with the stored metadata having to be re-computed accordingly, thereby increasing the online index maintenance cost. Motivated by these, this paper proposes CLIP (Cosine-Law-based Inverted-list Pruning), a lightweight method that enables both efficient and effective pruning in pure IVF structures. As illustrated in Figure 1, beyond standard 𝑛𝑝𝑟𝑜𝑏𝑒-based pruning, CLIP introduces two complementary strategies: inter- and intra-cluster pruning. Both rely on lower bounds derived from the Law of Cosines [13], which estimate the minimum possible squared distance between a query and a candidate vector. We detail them below. ⊲ Inter-Cluster Pruning. Given 𝑛𝑝𝑟𝑜𝑏𝑒 candidate clusters, we further identify pruning opportunities by estimating, for each cluster, the minimum lower bound 𝑙𝑏 min between the query vector 𝑞 and any vector assigned to it. If 𝑙𝑏 min exceeds the current threshold 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 (i.e., the squared distance of the current 𝑘-th nearest neighbor), the entire cluster can be safely pruned since all its vectors are guaranteed to be farther than 𝑚𝑎𝑥𝐷𝑖𝑠𝑡. Naïvely computing all individual lower bounds within a cluster to obtain 𝑙𝑏 min is expensive. Instead, we derive 𝑙𝑏 min in 𝑂 (1) time by exploiting the monotonicity of the cosine-law–based lower bound and closed-form expressions, enabling constant-time pruning. As shown in Table 1, CLIP reduces the number of probed clusters from 500/400 to 441/215 on the two datasets, respectively, demonstrating effective cluster-level pruning. ⊲ Intra-Cluster Pruning. For each candidate cluster that passes intercluster pruning, we retain only those in-cluster vectors whose 𝑙𝑏 ≤ 𝑚𝑎𝑥𝐷𝑖𝑠𝑡. Instead of computing the individual lower bound for each vector, we leverage the monotonicity of the bound again to efficiently locate all valid vectors. Specifically, during index construction, each inverted list is sorted by centroid–vector distance, which is also stored with 𝑂 (𝑙) extra space for query-time use. This induces a monotonic structure, implying that valid vectors form a contiguous segment within the sorted list. At query time, we only need to locate the segment boundaries via two binary searches, retaining the in-range vectors and pruning the rest. Overall, CLIP achieves vector-level pruning in 𝑂 (2 log 𝑙) time and substantially reduces data accesses (e.g., from 34%/10% to 21%/4% in Table 1). Beyond empirical results, we also provide theoretical analyses to explain the effectiveness of CLIP. In particular, we derive a quantilebased theoretical bound for the cosine-law–based lower bound, establishing its tightness in high-dimensional spaces and enabling principled control over the pruning tightness. Building on CLIP, we develop two enhanced IVF variants, i.e., IVF-CLIP and HIVF-CLIP, based on the standard IVFFlat and the common hierarchical IVF method (HIVF) [10, 34], respectively. Integrating CLIP into both variants requires only maintaining sorted inverted lists and storing centroid–vector distances, with negligible overhead from tightness parameters. IVF-CLIP is developed by directly integrating CLIP into IVFFlat, while HIVF-CLIP is further equipped with an adaptive query algorithm that selectively probes

promising sub-clusters at each layer based on the efficiently estimated 𝑙𝑏 min provided by CLIP. Our adaptive yet low-cost query algorithm improves upon existing approaches that either rely on simple heuristics to probe sub-clusters within a fixed distance range [10] or employ costly models to estimate the likelihood that a sub-cluster contains query results [34]. When handling dynamic workloads with both updates and queries, integrating CLIP improves query efficiency but increases update cost, since inverted list ordering and centroid–vector distances must be maintained. To address this, we propose LSM-IVF, an LSMinspired design that supports efficient online updates via a multilevel structure for fast in-memory writes, while deferring expensive index maintenance to background processing and keeping CLIP ’s sorted lists through LSM-style merge sort operations. However, its multi-level structure requires level-by-level search and aggregation, which degrades query efficiency. We further eliminate these redundant searches by jointly identifying global top-𝑛𝑝𝑟𝑜𝑏𝑒 clusters and top-𝑘 vectors across all LSM-IVF levels in a single search procedure, and applying CLIP to remove unnecessary clusters and vectors. To summarize, our contributions are as follows: • We propose CLIP, a lightweight pruning method that enables (1) inter-cluster pruning to reduce the number of probed clusters, and (2) intra-cluster pruning to access only a small range of vectors within each inverted list. (Section 3) • We derive a quantile-based theoretical bound that explains the efficiency of CLIP and provides principled control over pruning tightness. The derived bounds are consistent with empirical observations. (Section 3.3) • Building on CLIP, we develop two efficient IVF variants, IVF-CLIP and HIVF-CLIP. In particular, HIVF-CLIP incorporates an adaptive query algorithm that selectively probes promising sub-clusters for each query, avoiding static heuristics and costly query-time estimation. (Section 4) • To support dynamic workloads, we propose LSM-IVF, an LSM-style design that utilizes CLIP-based optimizations to achieve both high update and query efficiency. (Section 5) • Extensive experiments show that IVF-CLIP and HIVF-CLIP substantially outperform existing static IVF methods, achieving 69% higher query efficiency and enabling pruning ratios of up to 78% at the same recall. LSM-IVF improves throughput by up to 141% over state-of-the-art dynamic IVF baselines with comparable update efficiency (Section 6).

2

PRELIMINARIES

This section formalizes the ANN query problem and reviews the IVF methods, providing necessary background for the paper.

2.1

Problem Definition

We begin with the exact 𝑘 nearest neighbor (𝑘NN) query. Given a vector dataset D in 𝑑-dimensional space, a query vector 𝑞, and an integer 𝑘, the 𝑘NN query returns the 𝑘 vectors in D that are closest to 𝑞. Formally, it finds a subset R𝑘𝑛𝑛 ⊆ D such that |R𝑘𝑛𝑛 | = 𝑘 and ∀𝑣 ∈ R𝑘𝑛𝑛 ∀𝑜 ∈ D\R𝑘𝑛𝑛 Γ(𝑣, 𝑞) ≤ Γ(𝑜, 𝑞), where Γ(·, ·) denotes a distance metric (e.g., Euclidean distance and, inner product, cosine similarity, or angular distance).

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search

Due to the "curse of dimensionality", exact 𝑘NN search is prohibitively expensive in high-dimensional spaces. Recent research [17, 18, 32, 43] focuses on the approximate nearest neighbor (ANN) search. By relaxing the requirement for query accuracy, ANN methods achieve substantial gains in query efficiency. Their accuracy is typically measured by the query recall, defined as 𝑅𝑒𝑐𝑎𝑙𝑙@𝑘 = ′ ′ |/𝑘, where R |R𝑘𝑛𝑛 ∩ R𝑘𝑛𝑛 𝑘𝑛𝑛 and R𝑘𝑛𝑛 represent the exact and approximate result sets, respectively.

2.2

Review of Pure IVF Methods

The inverted file (IVF) technique supports ANN search by partitioning the dataset into clusters using 𝑘-means [27] and maintaining an inverted list (also known as posting list) for each cluster to store its assigned vectors. During query processing, the query vector 𝑞 is first compared with all centroids to identify the 𝑛𝑝𝑟𝑜𝑏𝑒 nearest clusters. Only vectors in these selected clusters are then scanned to compute distances to the query 𝑞, and the top-𝑘 nearest vectors are returned. The parameter 𝑛𝑝𝑟𝑜𝑏𝑒 controls the efficiency–accuracy trade-off: smaller values reduce computation but may degrade accuracy, while larger values improve accuracy at higher latency. To further reduce search cost, the IVF index structure is often extended into hierarchical or multi-layer variants [10, 34]. These designs organize clusters hierarchically, either by recursively partitioning clusters into sub-clusters in a top-down manner or by recursively grouping existing clusters in a bottom-up manner. This hierarchical structure enables early pruning of irrelevant regions, thereby reducing both query-centroid distance comparisons and the number of scanned vectors during query processing. Advantages and Limitations. Due to their simple implementation, practical scalability, strong hardware parallelism (e.g., scanning independent inverted lists in parallel across CPU cores or GPUs), update friendliness (e.g., appending vectors to inverted lists), and satisfactory query performance, IVF methods are widely adopted in modern vector retrieval systems [2, 10, 34, 40, 48, 50]. However, IVF structures provide only coarse-grained pruning: a large number of clusters must still be probed, and all vectors within the probed clusters need to be scanned during query processing, making this step a primary performance bottleneck. In addition, frequent updates can lead to imbalanced cluster sizes, potentially triggering costly online index maintenance operations such as re-partitioning [33].

3

THE CLIP METHOD

To overcome the limitations in IVF indexes, we propose CLIP, a cosine-law-based pruning strategy. We first provide an overview of CLIP in Section 3.1, then detail its pruning strategies in Section 3.2, and finally analyze the pruning effectiveness and determine the parameters that control pruning tightness in Section 3.3.

3.1

CLIP Overview

As illustrated in Figure 1, in addition to the widely used 𝑛𝑝𝑟𝑜𝑏𝑒based pruning strategy that probes a fixed number of nearest clusters [2, 30, 34, 51], CLIP further employs two pruning techniques, i.e., min-lower-bound-based pruning for inter-cluster pruning and lower-bound-based pruning for intra-cluster pruning. For each probed cluster, the min-lower-bound-based pruning strategy estimates the minimum lower bound (i.e., 𝑙𝑏𝑚𝑖𝑛 ) on the squared

distances between the query and all vectors in the cluster using the Law of Cosines [13] and its monotonicity property. If 𝑙𝑏𝑚𝑖𝑛 exceeds the threshold 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 (i.e., the squared distance of the 𝑘-th nearest neighbor found so far), the entire cluster can be safely skipped. In contrast, lower-bound-based pruning operates at a finer granularity. Within a candidate cluster, it identifies a contiguous range of vectors whose lower bounds may fall below 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 and prunes all remaining vectors outside this range. The valid vector range can be efficiently determined via two binary searches to locate the start and end positions of qualifying vectors. It is worth noting that, although CLIP relies on cosine-law–based lower bounds for pruning, both strategies are designed to operate without explicitly computing the lower bound for each vector, thereby achieving high pruning efficiency. The next section presents the pruning strategies in detail.

3.2

Pruning Strategies

We first define the cosine-law-based lower bound and its monotonicity, and then show how it enables efficient pruning. Let 𝑐, 𝑞, and 𝑣 denote the cluster centroid, query vector, and a data vector assigned to 𝑐, respectively. By the Law of Cosines [13], the squared distance between 𝑞 and 𝑣 can be written as: Γ(𝑞, 𝑣) 2 = Γ(𝑞, 𝑐) 2 + Γ(𝑐, 𝑣) 2 − 2 cos 𝜃 Γ(𝑞, 𝑐)Γ(𝑐, 𝑣), where 𝜃 = ∠𝑞𝑐𝑣. Then, we provide the following theorem. Theorem 1 (Cosine-Law-Based Lower Bound). Let 𝜃 min denote the minimum possible angle among all admissible triplets (𝑞, 𝑐, 𝑣), and define 𝜆 = cos 𝜃 min . Then, 𝑙𝑏𝑞𝑣 = Γ(𝑞, 𝑐) 2 + Γ(𝑐, 𝑣) 2 − 2𝜆 Γ(𝑞, 𝑐)Γ(𝑐, 𝑣)

(1)

is a valid lower bound of Γ(𝑞, 𝑣) 2 . Proof. Since 𝜃 ≥ 𝜃 min , we have cos 𝜃 ≤ 𝜆. Substituting this into the cosine law yields the result. □ We defer the discussion of the bound’s validity in high-dimensional spaces and the choice of 𝜆 to the next subsection, and now show how to exploit the monotonicity of this lower bound for efficient pruning without explicitly computing the bound for each vector. Theorem 2 (Monotonicity of Cosine-Law-Based Lower Bound). For fixed 𝑞, 𝑐, and 𝜆, the cosine-law-based lower bound can be expressed as a function of 𝑥 = Γ(𝑐, 𝑣):
2 𝑙𝑏 (𝑥) = 𝑥 2 −2𝜆 Γ(𝑞, 𝑐) 𝑥 +Γ(𝑞, 𝑐) 2 = 𝑥 −𝜆Γ(𝑞, 𝑐) +(1−𝜆 2 )Γ(𝑞, 𝑐) 2 . (2) Thus, 𝑙𝑏 (𝑥) is a convex quadratic function with a unique minimizer at 𝑥 ★ = 𝜆Γ(𝑞, 𝑐), attaining its minimum value 𝑙𝑏 min = (1 − 𝜆 2 ) Γ(𝑞, 𝑐) 2 , and is strictly decreasing on (−∞, 𝑥 ★] and increasing on [𝑥 ★, +∞). Proof. The result follows directly from the quadratic form.

□

By sorting data vectors within each inverted list according to the centroid-vector distance, i.e., Γ(𝑐, 𝑣), and additionally storing these distances, we enable the following pruning strategies. Inter-Cluster Pruning (InterCP). This pruning strategy eliminates unnecessary clusters among the 𝑛𝑝𝑟𝑜𝑏𝑒 nearest candidate clusters. We first scan the data vectors in the nearest cluster to obtain initial top-𝑘 results, and initialize 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 as the squared

Yitong Song, Shuhang Lu, Xuanhe Zhou, Pengcheng Zhang, and Jianliang Xu

Frequency

1.0

SIFT1M

GloVe

Deep

Tiny

MSong

GIST

The function of

Recall=0.99

0.5 0.0 0

(centroid-vector distance)

100

200

300

nprobe

400

500

600

Figure 2: Query frequency where the accessed cluster count inferred by inter-cluster pruning is smaller than 𝑛𝑝𝑟𝑜𝑏𝑒.

0 Centroid-vector distances of Access Range

distance between the query and the current 𝑘-th nearest neighbor. Then, for each remaining cluster 𝑐, we compute a cluster-level minimum lower bound 𝑙𝑏 min , representing the smallest possible lower bound of the squared distance between the query and any vector in 𝑐, given by 𝑙𝑏 min = (1 − 𝜆 2 )Γ(𝑞, 𝑐) 2 , as established in Theorem 2. Here, 𝜆 is precomputed, and Γ(𝑞, 𝑐) has already been obtained during the 𝑛𝑝𝑟𝑜𝑏𝑒-based cluster selection phase. If 𝑙𝑏 min > 𝑚𝑎𝑥𝐷𝑖𝑠𝑡, then for any vector 𝑣 ∈ 𝑐, it holds that Γ(𝑞, 𝑣) 2 ≥ 𝑙𝑏𝑞𝑣 ≥ 𝑙𝑏 min > 𝑚𝑎𝑥𝐷𝑖𝑠𝑡, implying that cluster 𝑐 cannot contribute to the top-𝑘 result and can be pruned without accessing its list. This check incurs only 𝑂 (1) time per cluster and is applied to all 𝑛𝑝𝑟𝑜𝑏𝑒 clusters. Note that we first perform standard 𝑛𝑝𝑟𝑜𝑏𝑒-based cluster selection and then apply InterCP within the selected 𝑛𝑝𝑟𝑜𝑏𝑒 clusters. An alternative design is to rely solely on InterCP for cluster selection, i.e., accessing all clusters satisfying 𝑙𝑏 min ≤ maxDist without explicitly specifying 𝑛𝑝𝑟𝑜𝑏𝑒. However, this may lead to query-dependent candidate clusters whose number is not fixed in advance, potentially increasing cluster access in certain cases. For example, as shown in Figure 2, on the Deep datasets at 0.99 recall, using only InterCP, about 67% of queries access fewer clusters than the 𝑛𝑝𝑟𝑜𝑏𝑒-based method, while the remaining 33% benefit from 𝑛𝑝𝑟𝑜𝑏𝑒-based selection. Similar trends are observed across other datasets, indicating that neither strategy dominates uniformly across queries. We further observe that the clusters selected by InterCP differ from those selected by 𝑛𝑝𝑟𝑜𝑏𝑒, reflecting their complementary nature: 𝑛𝑝𝑟𝑜𝑏𝑒 relies solely on query–centroid distances, whereas InterCP leverages 𝑙𝑏 min , which accounts for all in-cluster vectors rather than only centroids. These observations motivate a hybrid design that integrates 𝑛𝑝𝑟𝑜𝑏𝑒-based selection with InterCP, combining strict control over the number of accessed clusters with adaptive query-dependent filtering. Importantly, this introduces almost no additional computational overhead, since all distances required by InterCP are already computed during the 𝑛𝑝𝑟𝑜𝑏𝑒 phase. Empirically, applying InterCP after 𝑛𝑝𝑟𝑜𝑏𝑒-based selection can further remove 6.7%–46.2% of the initially selected clusters (Section 6.2), yielding an additional 10.7%–29% speedup (Section 6.4). Intra-Cluster Pruning (IntraCP). This strategy prunes unnecessary data vectors inside each qualified cluster. According to Equation 1, the lower bound 𝑙𝑏𝑞𝑣 for each vector 𝑣 can be computed by re-using the query–centroid distance Γ(𝑞, 𝑐) and the pre-stored centroid–vector distance Γ(𝑐, 𝑣). A straightforward pruning approach would compute the lower bound for every vector in the cluster and compare it with 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 one by one, accessing only those with 𝑙𝑏𝑞𝑣 ≤ 𝑚𝑎𝑥𝐷𝑖𝑠𝑡. However, this approach is inefficient since it requires 𝑂 (𝑙) lower bound computations per cluster, where 𝑙 denotes the size of a probed cluster. Instead, we utilize the monotonicity

Inverted list sorted by centroid-vector distances

Figure 3: Intra-cluster pruning of CLIP. The distances 𝑑 left and 𝑑 right are obtained as the two roots of 𝑙𝑏 (𝑥) = maxDist, where 𝑙𝑏 (𝑥) is defined in Equation 2. Their corresponding positions 𝑖𝑑𝑥𝑙 and 𝑖𝑑𝑥𝑟 are located via two binary searches over the sorted centroid–vector distances. Only vectors within the range [𝑖𝑑𝑥𝑙 , 𝑖𝑑𝑥𝑟 ] are accessed. of the cosine-law-based lower bound to identify qualified vectors without explicitly evaluating each lower bound. Based on Theorem 2, the lower bound first decreases and then increases with the centroid–vector distance Γ(𝑐, 𝑣), as shown in Figure 3. Therefore, we can identify the two roots of 𝑙𝑏 (𝑥) = 𝑚𝑎𝑥𝐷𝑖𝑠𝑡, and any vectors whose centroid–vector distances fall between these two roots are guaranteed to have lower bounds smaller than 𝑚𝑎𝑥𝐷𝑖𝑠𝑡. These vectors must be accessed for candidate evaluation. Since each inverted list is sorted in ascending order of centroid–vector distance, these vectors form a contiguous segment that can be efficiently located by identifying its boundary positions idxl and idxr . Algorithm 1: Intra-Cluster Pruning (IntraCP) Input: Sorted distances 𝐷𝑐 = {𝑑𝑖 |𝑑𝑖 = Γ (𝑐, 𝑣𝑖 ), 𝑣𝑖 ∈ cluster c} for a candidate cluster 𝑐, Γ (𝑞, 𝑐 ) 2 , 𝜆, 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 Output: Access range [idxl , idxr ] 1 Solve 𝑙𝑏 (𝑥 ) = 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 to obtain 𝑑 left and 𝑑 right (Equation 2); 2 idxl ← BinarySearch(𝐷𝑐 , 𝑑 left ); 3 idxr ← BinarySearch(𝐷𝑐 , 𝑑 right ); 4 return [idxl , idxr ]

Specifically, as illustrated in Algorithm 1, the identification proceeds in three steps: (1) solving 𝑙𝑏 (𝑥) = 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 to obtain two roots 𝑑 left and 𝑑 right (𝑑 left ≤ 𝑑 right ); (2) locating their corresponding positions idxl and idxr via binary search over the sorted centroid–vector distances; and (3) returning the index range [idxl, idxr ], within which all vectors satisfy 𝑙𝑏 (𝑥) ≤ 𝑚𝑎𝑥𝐷𝑖𝑠𝑡, while all remaining vectors are pruned without exact distance computation. In practice, since nearby clusters are typically accessed, Γ(𝑞, 𝑐) is small and 𝑑 left often becomes negative. In this case, 𝑑 left is a mathematical artifact rather than a valid distance in the inverted list. Therefore, only a single binary search is needed to locate 𝑑 right , and all vectors with indexes from 0 up to that position are accessed. In contrast, two binary searches are required only for far clusters where 𝑑 left ≥ 0.

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search

80 75

Theorem 3 (Lower Bound on 𝛽-Quantile of 𝜃 ). Given cluster centroid 𝑐, for any possible query 𝑞 ∈ 𝑄 and any in-cluster vector 𝑣 ∈ 𝑉𝑐 , define the angle set: Θ𝑐 := {∠𝑞𝑐𝑣 ∈ [0, 𝜋] | 𝑞 ∈ 𝑄, 𝑣 ∈ 𝑉𝑐 }. Let 𝑄 𝛽 (Θ𝑐 ) denote the 𝛽-quantile of angles within Θ𝑐 . There exists a lower bound 𝑄 such that 𝛽,𝑐 n h io √︁ 𝑄 𝛽 (Θ𝑐 ) ≥ 𝑄 = 𝑎𝑟𝑐𝑐𝑜𝑠 min 1, 𝐵 𝛽 (𝑐) 𝑢 ⊤ Σ𝑐 𝑢. , 𝛽,𝑐

1 https://github.com/SongYitong826/CLIP/blob/main/Technical%20Report.pdf

Empirical Q ( c)

Theoretical Q , c

70 65 60

tiny5m 0.25

0.50

0.75

1.00

1.25

(q c)2

80

Q , c (°)

3.3

Q , c (°)

Pruning Effectiveness and Parameters

This section explains why CLIP is valid in high-dimensional spaces and how to set the key parameter 𝜆 (defined as cos 𝜃 min ). Here, 𝜃 min is the minimum possible value of the angle ∠𝑞𝑐𝑣 over all feasible queries 𝑞 ∈ 𝑄, centroids 𝑐, and in-cluster vectors 𝑣 ∈ 𝑉𝑐 . Pruning Effectiveness. CLIP employs the cosine-law–based lower bound for pruning, using a critical parameter 𝜃 min ≤ 𝜃 𝑟𝑒𝑎𝑙 to ensure correctness. A larger 𝜃 min yields a tighter bound and thus stronger pruning. Since 𝜃 ∈ [0, 𝜋], 𝜃 min degenerates to 0, reducing the bound to the traditional triangle-inequality–based form and making CLIP similar to prior methods such as iDistance [25] that relies on distance ordering and triangle-inequality-based pruning. However, such bounds are proven to be weak in high-dimensional spaces due to the distance concentration phenomenon, where pairwise distances become similar and the lower bounds approach 0 [43]. In contrast, the cosine-law–based bound avoids this degeneracy with high probability due to a key high-dimensional property: random vectors are nearly orthogonal, i.e., pairwise angles concentrate sharply around 90◦ [47]. As a result, 𝜃 min typically remains close to 90◦ rather than collapsing toward 0, leading to a tighter bound. Importantly, this concentration behavior of ∠𝑞𝑐𝑣 (i.e., 𝜃 ) approximately persists even when 𝑞 and 𝑣 are not independent in the embedding space. This is because the angle is computed between residual vectors 𝑐𝑞 ® and 𝑐𝑣 ® rather than the original vectors. The centroid 𝑐 captures the dominant mean direction within the local cluster; subtracting 𝑐 therefore reduces the shared directional bias induced by the embedding distribution. Therefore, the residual vectors exhibit a more isotropic structure, making the high-dimensional angle concentration phenomenon still a reasonable approximation. Moreover, this concentration becomes stronger as the dimensionality increases, in the sense that the probability of 𝜃 min deviating significantly from 90◦ decreases with dimension, typically at an exponential rate under standard concentration assumptions [47]. We formalize this intuition in Theorem 3, which establishes a theoretical lower bound on the 𝛽-quantile of 𝜃 , i.e., 𝑄 𝛽 (Θ). We focus on 𝑄 𝛽 (Θ), rather than 𝜃𝑚𝑖𝑛 , for the following two reasons. First, computing the exact minimum angle would require exhaustively enumerating all feasible triplets (𝑞, 𝑐, 𝑣), which is computationally prohibitive. Second, the minimum value is statistically brittle: even a small number of outliers can drive it to an excessively low value, resulting in a loose bound. Instead, we consider a 𝛽-quantile of 𝜃 (e.g., the 0.001-quantile), which provides a robust and practically meaningful lower bound for pruning. Due to space constraints, the detailed proofs of all theorems in this section are provided in the accompanying technical report.1

1.50

1.75

2.00

75 70 65

gist1m 2

4

(q c)2

6

8

10

Figure 4: Empirical 𝑄 𝛽 (Θ𝑐 ) values and their theoretical bound 𝑄 as a function of Φ = Γ(𝑞−𝑐), illustrating that (i) the bound 𝛽,𝑐

consistently dominates the empirical values (Theorem 3), and (ii) it varies with Φ, explicitly capturing the distance dependence (Theorem 4). where 𝑢 = ∥𝑞−𝑐 ∥ is the query direction, Σ𝑐 depends only on 𝑐, and 𝐵 𝛽 (𝑐) depends on 𝛽 and 𝑐. 𝑞−𝑐

Figure 4 empirically validates Theorem 3. On both datasets, the empirical quantile 𝑄 𝛽 (Θ) is consistently bounded by the theoretical estimate, while the theoretical bound itself remains well separated from 0◦ (with empirical values lying even further away). This confirms that CLIP does not degenerate to the triangle-inequality–based method and can provide stronger pruning effectiveness. Parameter Determination. Based on the above analysis, we set the key parameter 𝜆 of CLIP to cos 𝑄 𝛽 (Θ). While this choice may incur a slight loss in accuracy, such a trade-off is well accepted in vector search, where a small loss in accuracy is often exchanged for a substantial improvement in query efficiency. To determine an effective value of 𝜆, we make two key observations. First, although the theoretical bound closely tracks the empirical quantile and consistently provides a valid lower bound, it remains conservative and exhibits a non-negligible gap to empirical values, which limits pruning effectiveness. Second, as shown in both Theorem 4 and Figure 4, 𝑄 𝛽 (Θ) depends on the query–centroid squared distance Γ(𝑞, 𝑐) 2 , implying that a single global 𝜆 shared across all queries and clusters is inherently suboptimal. Theorem 4 (Distance Dependence of 𝑄 𝛽 (Θ)). Under the same setting as in Theorem 3, consider angles conditioned on the query–centroid distance Φ = Γ(𝑞, 𝑐), denoted as Θ𝑐 (Φ) := {𝜃 ∈ Θ𝑐 | Γ(𝑞, 𝑐) = Φ}. Assume a locally anisotropic Gaussian model for the 2 𝐼 + Δ 𝑐ˆ𝑐ˆ⊤ , 𝑐ˆ = 𝑐 , where 𝜎 2 and cluster distribution: Σ𝑐 = 𝜎⊥,𝑐 𝑐 ⊥,𝑐 ∥𝑐 ∥ 2 are the variances orthogonal and parallel to 𝑐, ˆ respectively, and 𝜎 ∥,𝑐 2 − 𝜎 2 . Then, the 𝛽-quantile of Θ (Φ) admits a distanceΔ𝑐 = 𝜎 ∥,𝑐 𝑐 ⊥,𝑐 dependent lower bound:    √︃ 2 + Δ 𝐺 (Φ2 ) 𝑄 𝛽 (Θ𝑐 (Φ)) ≥ 𝑄 (Φ) = arccos min 1, 𝐵 𝛽 (𝑐) 𝜎⊥,𝑐 , 𝑐 𝛽,𝑐

where 𝐺 (Φ2 ) is a non-decreasing function of Φ2 capturing the effect of query–centroid distance on the angular variance.

Yitong Song, Shuhang Lu, Xuanhe Zhou, Pengcheng Zhang, and Jianliang Xu

Based on these findings, we estimate 𝜆 using empirical quantiles and make it adaptive to Γ(𝑞, 𝑐) 2 , instead of relying on the conservative theoretical bound. Specifically, we first sample a set of triplets (𝑞, 𝑐, 𝑣) and partition them into 𝑝 equal-width slices 2 , Γ(𝑞, 𝑐) 2 ]. When query vectors are unavailable, over [Γ(𝑞, 𝑐)min max we approximate them using data vectors.Then, for each slice, we compute a slice-specific 𝜆 = cos 𝑄 𝛽 (Θ), where 𝑄 𝛽 (Θ) is the 𝛽quantile of 𝜃 within the sampled triplets falling into that slice. During querying, the appropriate 𝜆 is selected based on the slice index 2 ⌊(Γ(𝑞, 𝑐)max − Γ(𝑞, 𝑐) 2 )/slice_len⌋ for pruning, where slice_len = 2 2 )/𝑝. This design replaces overly conserva(Γ(𝑞, 𝑐)max − Γ(𝑞, 𝑐)min tive theoretical bounds with empirical estimates, while capturing the dependence on Γ(𝑞, 𝑐) 2 via distance-aware partitioning. Both 𝛽 and 𝑝 influence the query recall. Empirically, we observe that 𝛽 = 0.001 and 𝑝 = 20 consistently achieve high recall (Figures 14).

Algorithm 2: IVF-CLIP (𝑞, 𝑘, 𝑛𝑝𝑟𝑜𝑏𝑒) Input: query vector 𝑞, parameter 𝑘, probed cluster count 𝑛𝑝𝑟𝑜𝑏𝑒 Output: 𝑘 nearest neighbors of 𝑞 1 Result queue R = ∅ (capacity 𝑘); 2 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 ← +∞ ; // current 𝑘-th nearest distance 2 3 𝐶 ← 𝑛𝑝𝑟𝑜𝑏𝑒 nearest centroids ; // Γ (𝑞, 𝑐 𝑖 ) is computed here 4 for each centroid 𝑐 𝑖 ∈ 𝐶 do 5 𝜆 ← GetLambda(Γ (𝑞, 𝑐𝑖 ) 2 ) ; // locate the slice 6 𝑙𝑏 min ← (1 − 𝜆 2 ) Γ (𝑞, 𝑐𝑖 ) 2 ; 7 if 𝑙𝑏 min ≤ 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 then // InterCP 8 Get sorted distances 𝐷𝑖 for cluster 𝑐𝑖 ; 9 idxl , idxr = IntraCP(𝐷𝑖 , Γ (𝑞, 𝑐𝑖 ) 2 , 𝜆, 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 ) ; // Alg. 1 10 for 𝑡 in [idxl idxr ] do 11 UpdateTopK(R, Γ (𝑞, cur_list[𝑡 ] ) 2 , 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 ); 12

4

CLIP INTEGRATION

In this section, we integrate CLIP into the IVFFlat structure (Section 4.1) and the hierarchical IVFFlat (HIVF) structure (Section 4.2), yielding the variants IVF-CLIP and HIVF-CLIP, respectively.

4.1

return R;

performed on candidate inverted lists, with 𝑙 denoting the average list length. In contrast to existing pruning methods [43, 51] that compute a lower bound for every candidate vector and incur a cost of 𝑂 (𝑛𝑝𝑟𝑜𝑏𝑒 · 𝑙), CLIP substantially reduces pruning overhead.

IVF-CLIP

When integrating CLIP into IVFFlat, both the index preparation and query processing pipelines require minor modifications. Index Preparation. IVF-CLIP follows the standard IVF construction pipeline, with the only modification being that inverted lists are sorted based on the centroid–vector distances. It also stores two auxiliary components: (1) the sorted centroid–vector distances and (2) the 𝜆 values. The centroid–vector distances are computed and stored directly during the clustering phase, incurring almost no extra computational cost. The values of 𝜆 are obtained via the sampling method described in Section 3.3, which is performed after the IVF index is built. As confirmed by our experiments (Figure 10), the overhead of computing these auxiliary statistics is negligible, as the clustering procedure itself dominates the index building cost. The additional storage overhead of CLIP is approximately 4𝑛 bytes for storing centroid–vector distances, where 𝑛 is the dataset size. Since the storage cost of 𝜆 depends only on the number of slices 𝑝 (typically no more than 20), it is negligible and thus omitted in the subsequent space complexity analysis. Query Processing. As shown in Algorithm 2, IVF-CLIP begins by selecting the top-𝑛𝑝𝑟𝑜𝑏𝑒 clusters closest to the query vector 𝑞, identical to the standard IVF procedure (Line 3). For each probed cluster 𝑐𝑖 , it locates the corresponding 𝜆 and computes the minimum possible lower bound 𝑙𝑏 min based on the already computed distance Γ(𝑞, 𝑐𝑖 ) 2 (Lines 5–6). If 𝑙𝑏 min > 𝑚𝑎𝑥𝐷𝑖𝑠𝑡, the entire cluster is discarded. Otherwise, IVF-CLIP proceeds with IntraCP (Lines 7–11): the two distance thresholds 𝑑 left and 𝑑 right are derived from Equation 2, and their positions in the sorted inverted list are efficiently located via binary searches. Only vectors within this range are accessed for distance computations and updating the result queue R. After all 𝑛𝑝𝑟𝑜𝑏𝑒 clusters have been processed, R is returned. Time Complexity. The additional time complexity introduced by CLIP is 𝑂 (𝑛𝑝𝑟𝑜𝑏𝑒 + 2 · 𝑛𝑝𝑟𝑜𝑏𝑒 · log 𝑙), where the 𝑂 (𝑛𝑝𝑟𝑜𝑏𝑒) term corresponds to computing 𝑙𝑏 min for each candidate cluster, and the 𝑂 (2 · 𝑛𝑝𝑟𝑜𝑏𝑒 · log 𝑙) term arises from the two binary searches

4.2

HIVF-CLIP

HIVF organizes clusters hierarchically by recursively partitioning coarse clusters into finer sub-clusters. Query processing follows a top-down traversal, where a subset of clusters is explored at each layer and only vectors in the reached leaf clusters are accessed. A key challenge in HIVF is accurately identifying which sub-clusters should be probed. Existing methods either rely on simple heuristics that select sub-clusters within a predefined distance range [10], or adopt complex probabilistic models [34] to estimate the likelihood of a sub-cluster containing query results, often suffering from either suboptimal accuracy or high computational overhead. In this section, we present HIVF-CLIP, which integrates HIVF with CLIP to adaptively and efficiently select sub-clusters at each layer using InterCP and IntraCP, and further reduces the number of scanned vector within leaf clusters via IntraCP. The index construction and query processing are detailed below. Index Preparation. HIVF-CLIP is constructed in a bottom-up manner, where finer clusters at a lower layer are recursively grouped to coarser clusters at higher layers. During this process, sub-clusters are ordered according to the distances between their centroids and their parent centroids, and these distances are stored for later use in computing lower bounds between queries and sub-cluster centroids. After the HIVF index is built, the corresponding 𝜆 values are computed and maintained at each layer. Similar to IVF-CLIP, the overhead of computing this extra information is negligible (Figure 10) as the clustering procedure dominates the index building cost. The additional storage cost is approximately 4 × (𝑛 +𝑛𝑐 ) bytes, where 𝑛𝑐 denotes the number of clusters across all HIVF layers. Query Processing. As shown in Algorithm 3, we still retain 𝑛𝑝𝑟𝑜𝑏𝑒 to control the number of accessed leaf clusters. Unlike IVF-CLIP, however, the top-𝑛𝑝𝑟𝑜𝑏𝑒 clusters are selected adaptively via hierarchical traversal instead of exhaustive scanning over all leaf clusters. During initialization (Lines 1–5), we initialize a result queue R of size 𝑘 and a cluster queue S seeded with the root cluster tuple,

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search

Algorithm 3: HIVF-CLIP (𝑞, 𝑘, 𝑛𝑝𝑟𝑜𝑏𝑒) Input: query vector 𝑞, parameter 𝑘, probed cluster count 𝑛𝑝𝑟𝑜𝑏𝑒 Output: 𝑘 nearest vectors of 𝑞 1 Result queue R = ∅ (capacity 𝑘); // S is sorted by the first key 2 2 Candidate cluster queue S = {tuple(root.𝑙𝑏 min , root, Γ (𝑞, root) ) }; 3 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 ← +∞ ; // current top-𝑘 vector dist. 4 𝑚𝑎𝑥𝐶𝐷 ← +∞ ; // current top-𝑛𝑝𝑟𝑜𝑏𝑒 leaf cluster dist. 5 cur_nprobe ← 0 ; // current accessed leaf cluster count 6 while S is not empty and cur_nprobe < 𝑛𝑝𝑟𝑜𝑏𝑒 do 7 cur_tuple ← S.pop(); 8 if cur_tuple denotes a leaf cluster then // IntraCP 9 Perform Lines 8–11 in Algorithm 2; cur_nprobe++; 10 11 12 13 14 15 16 17 18 19

L2 Sub-Clusters （Leaf）

… Candidate Cluster Queue (sorted by the first key)

else if cur_tuple.𝑙𝑏 min ≤ 𝑚𝑎𝑥𝐶𝐷 then // InterCP compute 𝑑 left and 𝑑 right based on 𝑚𝑎𝑥𝐶𝐷 (Equation 2); idxl ← BinarySearch(childList, 𝑑 left ); idxr ← BinarySearch(childList, 𝑑 right ); for 𝑡 in [idxl , idxr ] do // IntraCP child ← childList[𝑡 ]; if child is a leaf cluster then S.add(tuple(Γ (𝑞, child) 2 , child, child.𝑙𝑏 min )); update 𝑚𝑎𝑥𝐶𝐷; else

20

S.add(tuple(child.𝑙𝑏 min , child, Γ (𝑞, child) 2 ));

21

22

L1 Clusters

return R;

consisting of its 𝑙𝑏 min , cluster pointer, and squared distance to 𝑞. S is ordered by the first key, which differs between leaf and non-leaf clusters: for leaf clusters, the key is the squared query-centroid distance, while for non-leaf clusters, it is the 𝑙𝑏 min (as explained later). We maintain dynamic thresholds 𝑚𝑎𝑥𝐷𝑖𝑠𝑡 and 𝑚𝑎𝑥𝐶𝐷 for the current 𝑘-NN and top-𝑛𝑝𝑟𝑜𝑏𝑒 cluster distances, and track 𝑐𝑢𝑟 _𝑛𝑝𝑟𝑜𝑏𝑒 as the number of accessed leaf clusters. At each iteration (Lines 6–21), the algorithm pops the tuple in S with the smallest priority key. If the tuple corresponds to a leaf cluster, HIVF-CLIP invokes the same IntraCP procedure as IVF-CLIP, accessing only a contiguous range of vectors whose lower bounds are below 𝑚𝑎𝑥𝐷𝑖𝑠𝑡, and incrementing 𝑐𝑢𝑟 _𝑛𝑝𝑟𝑜𝑏𝑒 by 1. If the tuple corresponds to a non-leaf cluster, HIVF-CLIP applies both InterCP and IntraCP to determine the accessed sub-clusters, as shown in Figure 5 and detailed below: ⊲ Inter-Cluster Pruning (Line 11). A non-leaf cluster can be safely pruned when the lower bound distances between 𝑞 and all of its sub-cluster centroids exceed 𝑚𝑎𝑥𝐶𝐷. This is detected by checking 𝑙𝑏𝑚𝑖𝑛 of the current tuple, which represents the minimum lower bound distance between 𝑞 and any of its sub-clusters centroids. If 𝑙𝑏𝑚𝑖𝑛 > 𝑚𝑎𝑥𝐶𝐷, none of its children can enter the top-𝑛𝑝𝑟𝑜𝑏𝑒 leaf cluster queue, and the cluster is discarded. ⊲ Intra-Cluster Pruning (Line 12–21). If the non-leaf cluster cannot be entirely pruned, HIVF-CLIP identifies a contiguous segment of sub-clusters whose lower bound distances to 𝑞 are below 𝑚𝑎𝑥𝐶𝐷, again using binary searches to determine the boundary indexes. For each qualified sub-cluster 𝑐ℎ𝑖𝑙𝑑, we compute both its exact squared distance and its minimum lower bound distance to 𝑞. If 𝑐ℎ𝑖𝑙𝑑 is

Figure 5: The inter- and intra-cluster pruning in HIVF-CLIP. a leaf cluster, it is inserted into S with its exact distance as the first key (Line 18); otherwise, it is inserted with 𝑙𝑏 min as the first key (Line 21). This design ensures that a non-leaf cluster with 𝑙𝑏 min smaller than the exact squared distance of any candidate leaf cluster is expanded first, since it may still contain a closer leaf cluster. The search terminates once S becomes empty or 𝑐𝑢𝑟 _𝑛𝑝𝑟𝑜𝑏𝑒 ≥ 𝑛𝑝𝑟𝑜𝑏𝑒. At that point, the result queue R is returned. Time Complexity. Compared with IVF-CLIP, HIVF-CLIP adopts a hierarchical traversal strategy that reduces the cost of identifying the top-𝑛𝑝𝑟𝑜𝑏𝑒 clusters from 𝑂 (𝑛𝑙𝑖𝑠𝑡) to 𝑂 (log 𝑛𝑙𝑖𝑠𝑡), where 𝑛𝑙𝑖𝑠𝑡 denotes the number of leaf clusters. Empirically, HIVF-CLIP is more efficient than IVF-CLIP, as validated in Section 6.2. The overall time complexity of CLIP under HIVF is 𝑂 (𝑎𝑐 + 2𝑎𝑐 log 𝑠 + 2 · 𝑛𝑝𝑟𝑜𝑏𝑒 · log 𝑙), where 𝑎𝑐 is the average number of accessed non-leaf clusters with 𝑎𝑐 = Θ(log 𝑛𝑝𝑟𝑜𝑏𝑒), and 𝑠 is the average branching factor of non-leaf nodes. The first two terms correspond to the InterCP and IntraCP costs at the non-leaf levels, while the last term accounts for IntraCP at the leaf level and dominates the overall complexity.

5

DYNAMIC WORKLOAD PROCESSING

Existing IVF methods support dynamic workloads mainly via inplace updates, i.e., directly modifying the IVF index while serving queries [33, 34, 53]. Each update first identifies the target cluster, incurring an 𝑂 (𝑛𝑙𝑖𝑠𝑡) cost without auxiliary routing indexes (e.g., HNSW [32]), followed by lightweight list modifications (e.g., append-only insertions). Therefore, update performance is dominated by the cluster identification phase. For CLIP variants, the update overhead is further amplified since the ordering of inverted lists and distances must be additionally maintained. Moreover, skewed updates can lead to severe cluster imbalance, often triggering costly online index maintenance such as rebalancing or rebuilding [34, 53]. To overcome these limitations, we propose LSM-IVF, an LSMstyle architecture that enables highly efficient updates by deferring costly maintenance to background and keeping the inverted lists sorted via an LSM-style merge sort process, while mitigating the search inefficiencies inherent to LSM-based designs through CLIPbased optimizations. As shown in Figure 6, LSM-IVF maintains a memory buffer at Level 0 and organizes IVF indexes across deeper LSM levels with increasing hierarchy: Level 1 uses single-layer IVF-CLIP, while Level 𝑖 adopts an 𝑖-layer HIVF-CLIP. This design is motivated by the increasing data volume at deeper LSM levels,

Yitong Song, Shuhang Lu, Xuanhe Zhou, Pengcheng Zhang, and Jianliang Xu

Write Level 0

Buffer

Level 1

IVF-CLIP

Level 2 Level 3

Algorithm 4: LSM-IVF (𝑞, 𝑘, 𝑛𝑝𝑟𝑜𝑏𝑒)

reaching threshold

HIVF-CLIP (2-Layer) HIVF-CLIP (3-Layer)

Merge Merge

IVF-CLIP HIVF-CLIP (2-Layer)

Merge

HIVF-CLIP (3-Layer)

Figure 6: The architecture of LSM-IVF. where the number of clusters grows accordingly, making multilayer IVF structures more efficient at higher levels. We then detail how LSM-IVF efficiently supports updates and queries. Update Processing. As in conventional LSM designs, newly inserted vectors are first buffered in 𝐿0 and become immediately visible to queries. Once the buffer reaches its threshold, it is flushed and merged into Level 1. As levels fill up, merges are propagated to deeper levels via cascading compaction (e.g., 𝐿0 → 𝐿1 → 𝐿2 → · · · ). All merges are executed in the background, ensuring non-blocking query processing. During ongoing merges, queries are executed over a logical union of all components (including the buffer and all existing levels), guaranteeing that no recently inserted vectors are missed, at the cost of temporarily increased query cost due to multilevel access. Once a merge completes, the newly built component atomically replaces the corresponding old ones in this merge. The merge operation handles two cases: (i) merging unindexed vectors from 𝐿0 into IVF-CLIP at 𝐿1 , and (ii) merging two IVF indexes across adjacent levels. In the first case, vectors from 𝐿0 are assigned to the clusters of IVF-CLIP. For each cluster, newly assigned vectors are first collected into a list 𝑙𝑖𝑠𝑡𝑛𝑒𝑤 , which is sorted by centroid–vector distances. This list is then merged with the existing list 𝑙𝑖𝑠𝑡𝑜𝑙𝑑 using a merge sort process, following the standard compaction in LSM trees. In the second case, vectors from the smaller index are reassigned into the larger index using the same merge sort process. For HIVF-CLIP, this merge is only restricted to leaf clusters. To maintain clustering quality as data grows, we periodically trigger centroid re-training whenever a merge causes a level’s size to exceed predefined capacity thresholds (e.g., 25%). Query Processing. Unlike classic LSM-based search, which queries each level independently and then aggregates the results, LSM-IVF flattens IVF indexes across all levels and performs a unified search. As shown in Algorithm 4, LSM-IVF applies the HIVF-CLIP query procedure (i.e., Algorithm 3) with a modified initialization. Specifically, R is initialized with the top-𝑘 results in the buffer (Line 1), and S is populated with candidate clusters from all levels (Lines 2–9): top-𝑛𝑝𝑟𝑜𝑏𝑒 clusters from the IVF-CLIP level using the exact distance as the priority key, and root clusters from HIVF-CLIP levels using their 𝑙𝑏 min as the priority key. The search then proceeds as in Algorithm 3, iteratively expanding the most promising cluster and applying CLIP for pruning until global 𝑛𝑝𝑟𝑜𝑏𝑒 leaf clusters are accessed. In summary, LSM-IVF improves query efficiency through: (1) employing layer-appropriate IVF structures at different LSM levels, reducing cluster-identification cost as data volume grows; (2) jointly identifying the global top-𝑛𝑝𝑟𝑜𝑏𝑒 clusters across all levels within a single search process, avoiding level-by-level lookup and aggregation; and (3) using CLIP to prune both clusters and vectors, reducing data accesses and computations.

Input: query vector 𝑞, parameter 𝑘, probed cluster count 𝑛𝑝𝑟𝑜𝑏𝑒 Output: 𝑘 nearest vectors of 𝑞 1 Result queue R = Search(buffer, 𝑞, 𝑘 ); 2 Candidate cluster queue S = ∅; // sorted by the first key 3 for 𝑙 in (0, 𝑀𝑎𝑥𝐿] do // Adding clusters in all levels 4 if 𝑙𝑒𝑣𝑒𝑙 [𝑙 ].𝑖𝑛𝑑𝑒𝑥 == IVF-CLIP then 5 𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶 ← TopKClusters(𝑞, 𝑛𝑝𝑟𝑜𝑏𝑒 ) ; 6 for each 𝑐 in 𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶 do 7 S.add(tuple(Γ (𝑞, 𝑐 ) 2 , 𝑐, 𝑐.𝑙𝑏 min )); 8 9

10 11

if 𝑙𝑒𝑣𝑒𝑙 [𝑙 ].𝑖𝑛𝑑𝑒𝑥 == HIVF-CLIP then S.add(tuple(root.𝑙𝑏 min , root, Γ (𝑞, root) 2 )); Perform Lines 2–21 in Algorithm 3; return R;

6 EXPERIMENTS 6.1 Experimental Setup Datasets and Evaluated Workloads. As summarized in Table 2, we evaluate our methods on six widely used benchmark datasets for ANN search, including SIFT2 , GloVe3 , Deep4 , Tiny5 , MSong6 , and GIST7 . These datasets span diverse application domains, including text, image, and audio retrieval, with vector dimensionalities ranging from 128 to 960. For SIFT, we use three scales: a 1M-vector subset for most experiments, a 10M-vector subset for scalability evaluation, and a 1B-vector subset for disk-based experiments. Table 2: Statistics of datasets Dataset

Dimension

SIFT

128

GloVe Deep Tiny MSong GIST

200 256 384 420 960

#Vectors 1,000,000 10,000,000 1,000,000,000 1,193,514 1,000,000 5,000,000 994,185 1,000,000

#Queries 10,000 1,000 1,000 1,000 1,000 1,000

Data Size (GB) 0.48 4.81 119.21 0.89 0.96 7.17 1.56 3.58

Source Images Texts Images Images Audios Images

Table 3 summarizes the evaluated workloads. In addition to a static, query-only workload, we consider three dynamic workloads with varying update-to-query ratios, modeling update-light, balanced, and update-intensive scenarios. Table 3: Evaluated workloads Workload

Update : Query

Scenario

Static

0 : 10

Query-only

Low Dynamic Med High

2:8 5:5 8:2

Update-light Balanced Update-intensive

Compared Methods. We compare our methods against other pure IVF-based indexes under static and dynamic workloads. Under static workloads that contain only queries, we compare IVF-CLIP 2 http://corpus-texmex.irisa.fr/ 3 https://www.cse.cuhk.edu.hk/systems/hash/gqr/datasets.html 4 https://www.cse.cuhk.edu.hk/systems/hash/gqr/datasets.html 5 https://www.cse.cuhk.edu.hk/systems/hash/gqr/datasets.html 6 https://www.cse.cuhk.edu.hk/systems/hash/gqr/datasets.html 7 http://corpus-texmex.irisa.fr/

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search

IVFFlat

SIFT1M

103

GloVe

10

CrackIVF

Deep

SPANN

102

IVF-CLIP

HIVF-CLIP

Tiny 103

MSong 102

GIST

QPS

102

0.94

Pruning Ratio

Tribase 3

0.96

0.98

Recall@10

0.5 SIFT1M 0.4 0.3 0.2 0.1 0.00.94 0.96 0.98

Recall@10

2 1.00 0.90 0.92 0.94 0.96 0.98 100.94

Recall@10

0.96

0.98

Recall@10

101 0.90 0.92 0.94 0.96 0.98

Recall@10

0.6 GloVe

(a) QPS vs. Recall 0.8 0.5 Deep Tiny 0.4

0.4

0.4

0.2

0.2

Recall@10

0.96

0.98

Recall@10

Recall@10

0.3 MSong

0.6

1.00 0.00.90 0.92 0.94 0.96 0.98 0.00.94

0.92 0.94 0.96 0.98

0.3

0.2

0.2

0.1

0.1 0.90 0.92 0.94 0.96 0.98

Recall@10

(b) Pruning Ratio vs. Recall

1 100.90 0.92 0.94 0.96 0.98

Recall@10

0.4

GIST

0.2

0.00.92 0.94 0.96 0.98

Recall@10

0.00.90 0.92 0.94 0.96 0.98

Recall@10

Figure 7: Overall query performance under static workloads. and HIVF-CLIP with static single-layer methods, i.e., IVFFlat [2], Tribase [51], and CrackIVF [30], as well as a multi-layer method, SPANN [10]. Under dynamic workloads, we compare LSM-IVF with SOTA dynamic methods, i.e., SPFresh [53] and Quake [34]. Descriptions of these baselines are detailed below. • IVFFlat. The standard IVF baseline implemented in Faiss [2], which partitions vectors into clusters and performs exhaustive vector scans within the probed lists without pruning. • Tribase. An IVF-based pruning baseline that leverages the triangle inequality to derive distance- and angle-based bounds for each vector in the probed lists, eliminating those that do not satisfy the pruning criteria. • CrackIVF. An adaptive IVF baseline that incrementally reorganizes inverted lists during query processing to improve query performance. • SPANN. An HIVF baseline that constructs multi-layer balanced clusters and guides query processing from coarse to fine levels to reduce the search space. • SPFresh. A dynamic HIVF baseline built on top of SPANN, which maintains index quality under updates via several in-place strategies, i.e., online split and merge operations. • Quake. A dynamic HIVF method that adaptively reorganizes multi-layer partitions using a cost model. During query processing, it employs query-adaptive strategies (e.g., recall estimation) to dynamically select sub-clusters to access. Metrics. Query efficiency and accuracy are measured using QPS (i.e., queries per second) and recall (i.e., 𝑅𝑒𝑐𝑎𝑙𝑙@𝑘, defined in Section 2.1), respectively. Pruning effectiveness is quantified by the pruning ratio, defined as the reduction ratio of accessed data vectors before and after applying pruning. To further illustrate pruning behavior, we additionally report the number of accessed clusters and the number of distance computations. Throughput under dynamic workloads is evaluated by operation count per second. Parameter Settings. The number of clusters 𝑛𝑙𝑖𝑠𝑡 is set to 4,096 for all methods. The key parameter 𝑛𝑝𝑟𝑜𝑏𝑒 is dynamically adjusted to achieve different trade-offs between QPS and recall. For CLIP variants, we set 𝛽 = 0.001 and use 20 slices by default. For HIVF-CLIP,

the number of cluster layers defaults to 2. For LSM-IVF, the maximum data capacity of Levels 0, 1, 2, and 3 is set to 10K, 100K, 1M, and 10M vectors, respectively. For all other baselines, we use the default method-specific parameters from their original implementations. Implementations. Our experiments are conducted on a Linux server equipped with 512 GB RAM, an Intel Xeon Platinum 8457C processor, and a 1.92 TB Samsung enterprise SSD. All methods are implemented in C++ with SIMD optimizations opened. The baselines are implemented using their respective libraries [2, 12, 31, 35, 52]. We implement our methods based on Faiss [2] and release the source code at https://github.com/SongYitong826/CLIP. Following prior work [17, 49], all available threads are used for index construction, while query processing is performed in a singlethreaded, single-query setting.

6.2

Performance under Static Workloads

Overall Query Performance. Figure 7(a) reports the QPS–Recall trade-offs for all static methods. Across all datasets, IVF-CLIP and HIVF-CLIP consistently achieve the highest QPS at the same recall levels. On average, IVF-CLIP outperforms the strongest baseline in QPS by 23.4%, 46.7%, 20.5%, 11.5%, 5.8%, and 29.4% on SIFT, GloVe, Deep, Tiny, MSong, and GIST, respectively. Building on this, HIVF-CLIP further improves over IVF-CLIP by an additional 11%, 15%, 14%, 7%, 10%, and 20% on average across the six datasets, benefiting from its hierarchical design that reduces candidate cluster identification cost. Notably, at a high recall of 0.99, IVF-CLIP reaches up to a 51% improvement over the strongest baseline, while HIVF-CLIP pushes the gain to as high as 69%. These gains stem from reduced data access and computation costs enabled by CLIP. Pruning Performance. Figure 7(b) evaluates pruning effectiveness under different recall levels. This experiment includes only pruning techniques applicable to pure IVF indexes, i.e., Tribase and our methods. Over the recall range shown in the figure, HIVF-CLIP achieves an average pruning ratio 26.6× that of Tribase, with perdataset multipliers of 7.4×, 22.0×, 123.1×, 2.7×, 1.06× and 3.5× respectively, reaching up to 78% pruning over a recall of 0.99 on Deep dataset. We note that pruning effectiveness varies across datasets

Yitong Song, Shuhang Lu, Xuanhe Zhou, Pengcheng Zhang, and Jianliang Xu

Accessed Clusters

IVFFlat, Tribase, CrackIVF-START, SPANN

SIFT1M

200

Accessed Clusters

100

100 7 7 8 8

200

156156 150 123123

50 46 46

0 50 100 150 200

nprobe Tiny

400 200

100 88 85

200 64 7 1 15

400

300 296280 233222

0 100 200 300 400

nprobe

GloVe

400 200

100 93 90

200182175

300 70 9 2 25

IVF-CLIP

200

0 100 200 300 400

nprobe MSong

60 40 20 15 14 14

45 30

5

35 35

60

100

83 80

215203 200 182174 140134

0 100 200 300 400

nprobe GIST

400

0 15 30 45 60

400

300

44 44

22 2

nprobe

HIVF-CLIP

Deep

400 6 35 340 400

200

100 91 89

200 73 67 1 1

400 316297 300 248236

IVFFlat

Distance Calculations

due to their intrinsic characteristics, particularly cluster distributions. Well-separated clusters yield tighter bounds and enable more aggressive pruning. On the SIFT dataset, although IVF-CLIP attains a 0.97× pruning ratio of Tribase when recall is below 0.96, it still provides a 1.87× QPS speedup over Tribase. This is because CLIP incurs substantially lower pruning overhead, as it avoids per-vector bound evaluation, whereas Tribase requires computing multiple costly bounds for each vector. As a result, CLIP achieves higher end-to-end query efficiency even when pruning fewer vectors. It is worth noting that Tribase relies on the strict triangle inequality for pruning and guarantees no recall loss. Its rigorous pruning criterion makes it more suitable for extremely high recall regimes (e.g., ≥ 0.995), where more candidates must be examined, creating greater opportunities for pruning. In contrast, CLIP adopts a lightweight, approximate pruning strategy that targets high efficiency with slight recall loss, and is particularly effective in moderate-to-high recall regimes (e.g., ≤ 0.995).

105

104

Tribase

SIFT1M

CrackIVF SPANN Deep 105

IVF-CLIP

HIVF-CLIP

GIST

105 104 200

nprobe

400

200

nprobe

4 40010

250 500 750

nprobe

Figure 9: Comparison of distance computation count. this ratio to 0.67×, ranging from 0.43× to 0.87×. These results highlight the effectiveness of our InterCP and IntraCP strategies in lowering the number of distance computations. Index Performance. Figure 10 reports the index construction time, storage footprint, and peak memory usage during querying. IVF-CLIP achieves construction time and storage cost comparable to IVFFlat, as it introduces only low computational cost (i.e., list sorting and sampling) and requires small extra storage for centroid–vector distances. Compared with IVF-CLIP, HIVF-CLIP requires 8.6% more construction time and 0.4% more storage cost, while remaining 73% and 66% less than other hierarchical method (i.e., SPANN) in these two aspects, respectively. SPANN incurs higher construction complexity and larger index size due to its hierarchical balanced clustering and the need to assign boundary vectors to multiple clusters for improving recall. Tribase typically incurs higher construction and storage overhead than IVF-CLIP, as it requires computing and storing multiple auxiliary neighbors per vector. IVFFlat

Tribase

CrackIVF

SPANN

IVF-CLIP

SIFT1M

GloVe

Deep

Tiny

MSong

GIST

SIFT1M

GloVe

Deep

Tiny

MSong

GIST

SIFT1M

GloVe

Deep

Tiny

MSong

GIST

HIVF-CLIP

103 102

0 100 200 300 400

nprobe

Figure 8: Comparison of accessed cluster count.

(a) Construction Time (s)

104 103

Number of Accessed Clusters. Figure 8 compares the number of accessed clusters under different 𝑛𝑝𝑟𝑜𝑏𝑒 settings. For IVFFlat, Tribase, CrackIVF, and SPANN, the number of accessed clusters is fully determined by 𝑛𝑝𝑟𝑜𝑏𝑒. In contrast, IVF-CLIP and HIVF-CLIP leverage CLIP to prune the 𝑛𝑝𝑟𝑜𝑏𝑒 candidate clusters, reducing the number of accessed clusters by 6.7%–49.2% across all datasets and 𝑛𝑝𝑟𝑜𝑏𝑒 settings. Moreover, the pruning benefit becomes more pronounced as 𝑛𝑝𝑟𝑜𝑏𝑒 increases: with larger 𝑛𝑝𝑟𝑜𝑏𝑒 (typically required for higher recall), CLIP prunes a larger fraction of candidate clusters. We note that although HIVF-CLIP accesses a similar number of clusters as IVF-CLIP due to the shared pruning mechanism, it typically achieves better QPS–recall trade-offs (Figure 7) by further reducing the cost of identifying the initial top-𝑛𝑝𝑟𝑜𝑏𝑒 clusters through hierarchical traversal (Section 4.2). Number of Distance Computations. Figure 9 reports the number of distance computations as a function of 𝑛𝑝𝑟𝑜𝑏𝑒. As 𝑛𝑝𝑟𝑜𝑏𝑒 increases, all methods incur more distance computations. Nevertheless, IVF-CLIP and HIVF-CLIP consistently require the fewest distance computations, where the advantage over baselines is typically amplified at larger 𝑛𝑝𝑟𝑜𝑏𝑒. Specifically, at the largest tested 𝑛𝑝𝑟𝑜𝑏𝑒 shown in Figure 9, IVF-CLIP requires only 0.75× the distance computations of the best baseline on average, ranging from 0.48× to 0.87× across all datasets, while HIVF-CLIP further reduces

(b) Index Size (MB)

104 103

(c) Peak Memory (MB)

Figure 10: Construction time, index size and peak memory. In terms of peak memory during querying, most methods exhibit comparable memory footprints, as the accessed data volume dominates the memory overhead rather than the index structure itself. IVF-CLIP and HIVF-CLIP incur negligible additional memory overhead beyond standard IVF traversal, while CrackIVF shows higher peak memory due to its adaptive cracking mechanism, which maintains additional intermediate state during query processing.

6.3

Performance under Dynamic Workloads

Throughput and Recall. Figure 11 reports throughput and recall at 𝑛𝑝𝑟𝑜𝑏𝑒 = 400 under different update-to-query ratios (U/Q). To evaluate LSM-IVF after high-level merges, we extend each dataset beyond 106 vectors through random sampling with an added bias. Across all workloads, LSM-IVF consistently achieves the highest throughput. Before the dataset size reaches 106 , LSM-IVF outperforms the strongest baseline (Quake) by 141%, 38%, and 39% on

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search

102 101

1.00 0.99 80 85 90 95 100 105 80 85 90 95 100 105 80 85 90 95 100 105 0.98

Data Size (×104) Data Size (×104) Data Size (×104) Figure 11: Performance under varying dynamic workloads. SIFT, Deep, and GIST, respectively. Averaged across datasets, its advantage over Quake grows as updates become more frequent, increasing from 65.5% at U/Q=2:8 to 68.8% at U/Q=5:5 and 83.8% at U/Q=8:2. After the dataset size exceeds 106 , LSM-IVF exhibits fluctuations due to its merge mechanism: throughput gradually declines as updates accumulate in buffers, but rises sharply after merges consolidate data. In particular, the major merge at 106 vectors boosts throughput by 89%/192%/186% on SIFT/Deep/GIST, respectively. In terms of recall, LSM-IVF consistently maintains a high and stable recall (close to 0.997). In contrast, Quake exhibits a slight recall degradation on Deep (0.997 → 0.993), likely due to its costmodel-driven inverted-list splitting, which may occasionally result in insufficient scanning. Similarly, SPFresh shows noticeable recall fluctuations on GIST (0.999 → 0.991), potentially caused by IVF assignment drift under dynamic updates.

Amortized Update Time ( s)

Quake

SPFresh

LSM-IVF (bottom light: insert; top dark: merge)

104 103 102 101 100 10 1

SIFT1M GloVe Deep

Tiny MSong GIST

Figure 12: Update efficiency. Update Efficiency. Figure 12 compares the update time of LSM-IVF with Quake and SPFresh. LSM-IVF decomposes updates into two components: (i) a lightweight online insertion into an in-memory buffer, and (ii) background merges triggered when level thresholds are reached, whereas both baselines perform updates entirely online. The online insertion cost of LSM-IVF is minimal due to the in-memory buffer design, leading to very low per-update latency. When accounting for merge overhead, the amortized update cost of LSM-IVF remains comparable to Quake, while being significantly lower than SPFresh. Note that during merging, queries need to access more levels before the merge completes, temporarily resulting in suboptimal query performance. SPFresh incurs higher update latency as each insertion requires a graph traversal to locate neighbors and maintain connectivity. Overall, these results show that LSM-IVF achieves efficient and practical update performance.

IVFFLAT IVF-CLIP 3

IVF-CLIP(only inter-pruning) IVF-CLIP(only intra-pruning)

10

102

102

GloVe Recall

Deep 0.96 0.99 Recall

GIST

0.90 0.93 0.96 0.99 0.93 1.0

1.0

0.5

0.5

0.91

0.95

Recall

1.0

0.99

0.5

GloVe Deep GIST 0.00.90 0.93 0.96 0.990.00.93 0.96 0.99 0.0 0.91 0.95 0.99 Recall Recall Recall

Figure 13: Ablation study, where the relative pruning ratio is normalized by the pruning ratio of the full IVF-CLIP. The relative pruning ratio results show that the dominant pruning strategy varies across datasets. Inter-cluster pruning contributes an average of 65.6% and 60.1% of the full pruning effectiveness on Deep and GIST, respectively, making it the dominant factor on these datasets, while intra-cluster pruning contributes 74.2% on GloVe and plays a more important role there. These results demonstrate that both pruning strategies substantially contribute to the overall pruning effectiveness, and combining them consistently achieves the best performance. We omit the ablation of HIVF-CLIP due to its similar behavior to IVF-CLIP and space limitations.

SIFT1M

Deep

103

0.6 0.4 0.2

102

1 0.6 0.4 0.2 0.0 2 10

2

5 10 20

1

p

2

5 10 20

p

(a) Slice Count (p)

103 102

10 3

10 4

10 2

10 3

GIST

100

Recall@10 (%)

GIST

101

10 4

98 96

1

2

5 10 20

p

100

Recall@10 (%)

1.00 0.99 0.98

102

QPS

Recall

101 103

QPS

1.00 0.99 0.98

102

QPS

Deep SIFT1M Throughput (ops/s)

103

In-Depth Analysis of CLIP

6.4

Ablation Study. Figure 13 reports an ablation study of IVF-CLIP by selectively enabling pruning components. We consider two special settings: (i) inter-cluster pruning only, and (ii) intra-cluster pruning only (using 𝑛𝑝𝑟𝑜𝑏𝑒-based cluster selection without intercluster pruning). Compared to the full IVF-CLIP, the inter-clusteronly variant exhibits an average 10.8% QPS drop at 0.99 recall, while the intra-cluster-only variant leads to an average 20.4% QPS drop, showing that removing either pruning strategy noticeably degrades the performance of IVF-CLIP. Compared to IVFFlat without any pruning strategies, the inter- and intra-cluster-only variants still achieve 10.7%–29.0% and 5.3%–28.7% higher QPS across datasets, respectively, showing effectiveness of both pruning strategies.

Relative Pruning Ratio

LSM-IVF Throughput LSM-IVF Recall U/Q=8:2

Pruning Ratio

SPFresh Throughput SPFresh Recall U/Q=5:5

Pruning Ratio

Quake Throughput Quake Recall U/Q=2:8

96 10 2

10 3

10 4

(b) Quantile ( ) Figure 14: Evaluating the effect of 𝑝 and 𝛽. Parameter Sensitivity. Figure 14(a) examines the impact of 𝑝 (i.e., the number of slices) on pruning effectiveness and query quality under 𝑛𝑝𝑟𝑜𝑏𝑒 = 200. When 𝑝 is small, the slicing is too coarse, leading to suboptimal bound quality and unstable pruning ratios and recall. As 𝑝 increases, the pruning behavior becomes progressively

Yitong Song, Shuhang Lu, Xuanhe Zhou, Pengcheng Zhang, and Jianliang Xu

0.98 0.96 0.94

1

2

3

Height

4

5

900 0.98

60

600 0.96

40

300 0.94

20

0

0.92

1

2

3

Height

4

5

0

Figure 15: Effect of hierarchy height in HIVF-CLIP. Figure 15 evaluates the effect of the hierarchy height in HIVF-CLIP. Overall, increasing the height has negligible impact on recall, while QPS exhibits a non-monotonic trend, i.e., first increasing and then decreasing, with the optimal height at 2. This behavior reflects a trade-off: additional layers reduce the cost of identifying the top𝑛𝑝𝑟𝑜𝑏𝑒 clusters, but also incur extra traversal and routing overhead, which eventually outweighs the benefits and degrades performance. These results justify our default choice of using two layers, which achieves the best trade-off between efficiency and overhead.

IVF-CLIP, 0.95 Recall HIVF-CLIP, 0.95 Recall

80

Pruning ratio (%)

IVF-CLIP, 0.99 Recall HIVF-CLIP, 0.99 Recall

60

QPS

1200 1000 800 600 400 200

40 20

2

4

6

8

10

2

4

6

8

10

Data size (million) Data size (million) (a) QPS vs. Data Size (SIFT10M) (b) Pruning Ratio vs. Data Size (SIFT10M) Figure 16: Evaluating the scalability. Scalability Analysis. Figure 16 evaluates scalability under two recall targets (0.95 and 0.99). As shown in Figure 16(a), when the dataset size increases from 2M to 10M vectors (5×), QPS decreases sub-linearly at both recall levels. For example, at 0.99 recall, IVF-CLIP drops from about 480 to 130 QPS (∼3.7×), while HIVF-CLIP decreases from about 500 to 150 QPS (∼3.3×). A similar trend is observed at 0.95 recall. Figure 16(b) shows that the pruning ratio also increases steadily with data size under both recall settings.

6.5

Evaluation in Disk-Resident Settings

This section evaluates IVF-CLIP in a disk-resident IVF setting. We extend IVF-CLIP to this setting by storing cluster centroids, inverted lists (vector identifiers only), vector–centroid distances, and 𝜆 values in memory, while keeping the raw vectors on SSD. During query processing, the in-memory metadata supports both interand intra-cluster pruning, reducing SSD accesses and disk I/O. Figure 17 compares IVF-CLIP with disk-based baselines (i.e., SPANN and IVFFlat) on the 1-billion-scale SIFT dataset. IVF-CLIP consistently outperforms both baselines across all recall levels. At

100

AvgDiskIO

101

IVFFLAT

SIFT1B

105

0.92

0.96

Recall

1.00

1.0

Pruning Ratio

SPANN

SIFT1B QPS

more stable and eventually plateaus, since finer slicing provides more accurate bounds for pruning. In practice, 𝑝 = 20 is sufficient to achieve near-stable pruning performance for most datasets. Figure 14(b) evaluates the effect of 𝛽 (i.e., the quantile used to set 𝜆) on query performance under 𝑛𝑝𝑟𝑜𝑏𝑒 = 200. Larger 𝛽 applies more aggressive pruning and improves efficiency but may hurt recall, whereas smaller 𝛽 is more conservative and preserves accuracy at the cost of reduced pruning. Overall, setting 𝛽 = 0.001 provides a good trade-off between efficiency and accuracy, achieving high recall while maintaining high pruning effectiveness. nprobe=60 nprobe=100 nprobe=100 nprobe=250 nprobe=150 nprobe=180 nprobe=400 nprobe=80 Recall (bar) QPS (line) Recall (bar) QPS (line) SIFT1M GIST 1.00 1200 1.00 80

IVF-CLIP

SIFT1B

0.5

0.92

0.96

Recall

1.00 0.0 0.92

0.96

Recall

1.00

Figure 17: Evaluation in the disk-resident setting. 0.99 recall, it achieves 34.2% higher QPS and 22.5% lower I/O than IVFFlat. At 0.95 recall, the gains change to 50.2% higher QPS and 18% lower disk I/O. In contrast, SPANN incurs 5–8× higher I/O due to frequent random accesses during graph traversal. The pruning ratio of CLIP exceeds 65% at 0.99 recall, demonstrating that IVF-CLIP remains effective at billion scale under disk-resident settings.

7

RELATED WORK

ANN Algorithms. ANN search methods are commonly categorized into four families: (1) partition-based [2, 6, 7, 10, 11, 14, 34, 36, 40], (2) hash-based [22, 24, 28, 45, 46], (3) graph-based [16, 17, 29, 32, 39, 55], and (4) quantization-based approaches [3–5, 19, 21, 23, 26]. This work focuses on IVF-based methods within the partition-based family. To reduce distance computation costs, numerous methods have been proposed [9, 15, 18, 19, 26, 43, 51, 55]. However, most of them either reduce the dimensionality of distance computations or rely on auxiliary structures (e.g., hash tables or quantization codes) for pruning, making them unsuitable for reducing cluster and vector accesses in pure IVF indexes. For example, TRIM [43] exploits PQ-derived bounds for pruning and is therefore applicable only to IVFPQ rather than pure IVF indexes. Tribase [51] is a notable exception that derives triangle-inequality-based bounds for IVF pruning. However, its pruning conditions are often overly conservative and incur considerable computational overhead. Dynamic IVF Index Maintenance. Under dynamic workloads, insertions and deletions may cause centroid drift and inverted-list imbalance, degrading IVF query performance. Existing methods maintain IVF indexes through online reorganization, such as repartitioning, split/merge, and cost-aware rebalancing [33, 34, 53]. Although effective, these maintenance operations compete with query processing for system resources, often reducing overall throughput. In contrast, LSM-based designs [8, 38, 42] buffer updates and perform merges asynchronously, thereby improving throughput while maintaining query availability. Such designs have recently been extended to graph-based ANN indexes [56]. However, applying LSM-style designs to IVF indexes remains largely unexplored.

8

CONCLUSION

This paper presents CLIP, a lightweight cosine-law-based pruning technique for IVF-based vector search. We theoretically establish its correctness and pruning effectiveness, and develop two IVF variants, IVF-CLIP and HIVF-CLIP, to support both flat and hierarchical IVF structures. We further propose LSM-IVF, which integrates CLIP with an LSM-tree to enable efficient updates while maintaining high query performance. Extensive experiments on static and dynamic workloads demonstrate the effectiveness of all proposed methods. While this work focuses on pure IVF indexes, extending CLIP to compressed IVF structures (e.g., IVFPQ) and combining it with other pruning techniques are promising directions for future research.

CLIP: Lightweight Cosine-Law-Based Inverted-List Pruning for IVF-Based Vector Search

REFERENCES [1] Blaise Agüera y Arcas, Beat Gfeller, Ruiqi Guo, Kevin Kilgour, Sanjiv Kumar, James Lyon, Julian Odell, Marvin Ritter, Dominik Roblek, Matthew Sharifi, and Mihajlo Velimirović. 2017. Now Playing: Continuous low-power music recognition. NeurIPS (2017). [2] Meta AI. 2017. FAISS. https://ai.facebook.com/tools/faiss. [3] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2016. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. VLDB 9, 4 (2016), 12. [4] Artem Babenko and Victor Lempitsky. 2014. Additive quantization for extreme vector compression. CVPR (2014), 931–938. [5] Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE TPAMI 37, 6 (2014), 1247–1260. [6] Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. ACM Communications 18, 9 (1975), 509–517. [7] Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for nearest neighbor. ICML (2006), 97–104. [8] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. 2006. Bigtable: A Distributed Storage System for Structured Data. OSDI (2006), 205– 218. [9] Patrick Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2023. Finger: Fast inference for graph-based approximate nearest neighbor search. In Proceedings of the ACM Web Conference 2023. 3225– 3235. [10] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly-efficient billion-scale approximate nearest neighborhood search. NeurIPS 34, 5199–5212. [11] Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An efficient access method for similarity search in metric spaces. VLDB 97 (1997), 426–435. [12] SPTAG Contributors. 2021. SPTAG-Library. https://github.com/microsoft/ SPTAG. [13] H. S. M. Coxeter. 1969. Introduction to Geometry (2nd ed.). John Wiley & Sons. [14] Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. STOC (2008), 537–546. [15] Liwei Deng, Penghao Chen, Ximu Zeng, Tianfu Wang, Yan Zhao, and Kai Zheng. 2024. Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search. arXiv preprint arXiv:2411.17229 (2024). [16] Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE TPAMI 44, 8 (2021), 4139–4150. [17] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. In PVLDB, Vol. 12. VLDB Endowment, 416–474. [18] Jianyang Gao and Cheng Long. 2023. High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations. ACM SIGMOD 1, 2 (2023), 1–27. [19] Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. ACM SIGMOD 2, 3 (2024), 1–27. [20] Pengfei Gao, Zhao Tian, Xiangxin Meng, Xinchen Wang, Ruida Hu, Yuanan Xiao, Yizhou Liu, Zhao Zhang, Junjie Chen, Cuiyun Gao, et al. 2025. Trae agent: An llm-based agent for software engineering with test-time scaling. arXiv preprint arXiv:2507.23370 (2025). [21] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization for approximate nearest neighbor search. IEEE TPAMI (2013), 2946– 2953. [22] Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. 2020. iDEC: indexable distance estimating codes for approximate nearest neighbor search. PVLDB 13, 9 (2020). [23] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. ICML (2020), 3887–3896. [24] Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-aware locality-sensitive hashing for approximate nearest neighbor search. PVLDB 9, 1 (2015), 1–12. [25] Hosagrahar V Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Rui Zhang. 2005. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Transactions on Database Systems (TODS) 30, 2 (2005), 364–397. [26] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE TPAMI 33, 1 (2010), 117–128. [27] K Krishna and M Narasimha Murty. 1999. Genetic K-means algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 29, 3 (1999), 433–439. [28] Jinfeng Li, Xiao Yan, Jian Zhang, An Xu, James Cheng, Jie Liu, Kelvin KW Ng, and Ti-chung Cheng. 2018. A general and efficient querying method for learning

to hash. ACM SIGMOD (2018), 1333–1347. [29] Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search. PVLDB 15, 2 (2021), 246–258. [30] Vasilis Mageirakos, Bowen Wu, and Gustavo Alonso. 2025. Cracking Vector Search Indexes. VLDB (2025), 3951–3964. [31] Vasilis Mageirakos, Bowen Wu, and Gustavo Alonso. 2025. crackivf-Library. https://github.com/mageirakos/crack-ivf-vldb. [32] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAMI 42, 4 (2018), 824–836. [33] Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Umar Farooq Minhas, Jeffery Pound, Cedric Renggli, Nima Reyhani, Ihab F Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2024. Incremental IVF Index Maintenance for Streaming Vector Search. arXiv preprint arXiv:2411.00970 (2024). [34] Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2025. Quake: Adaptive Indexing for Vector Search. arXiv preprint arXiv:2506.03437 (2025). [35] Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2025. Quake-Library. https://github.com/marius-team/quake. [36] Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE TPAMI 36, 11 (2014), 2227–2240. [37] Zhaojie Niu, Xinhui Tian, Xindong Peng, and Xing Chen. 2025. BlendHouse: A Cloud-Native Vector Database System in ByteHouse. IEEE ICDE (2025), 4332– 4345. [38] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 1996. The log-structured merge-tree (LSM-tree). Acta informatica 33, 4 (1996), 351–385. [39] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. ACM SIGMOD 1, 1 (2023), 1–27. [40] Jeffrey Pound, Floris Chabert, Arjun Bhushan, Ankur Goswami, Anil Pacaci, and Shihabur Rahman Chowdhury. 2025. MicroNN: An On-device Disk-resident Updatable Vector Database. In Companion of the 2025 International Conference on Management of Data. 608–621. [41] Yong Rui, Thomas S Huang, and Shih-Fu Chang. 1999. Image retrieval: Current techniques, promising directions, and open issues. Journal of visual communication and image representation 10, 1 (1999), 39–62. [42] Russell Sears and Raghu Ramakrishnan. 2012. bLSM: a general purpose log structured merge tree. ACM SIGMOD (2012), 217–228. [43] Yitong Song, Pengcheng Zhang, Chao Gao, Bin Yao, Kai Wang, Zongyuan Wu, and Lin Qu. 2025. TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning. ACM SIGMOD (2025), 1–26. [44] Ji Sun, Guoliang Li, James Pan, Jiang Wang, Yongqing Xie, Ruicheng Liu, and Wen Nie. 2025. GaussDB-Vector: A Large-Scale Persistent Real-Time Vector Database for LLM Applications. PVLDB 18, 12 (2025), 4951–4963. [45] Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2014. SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. PVLDB (2014). [46] Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2010. Efficient and accurate nearest neighbor and closest pair search in high-dimensional space. ACM TODS 35, 3 (2010), 1–46. [47] Roman Vershynin. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, Cambridge, UK. [48] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. ACM SIGMOD (2021), 2614–2627. [49] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2022. Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints. arXiv preprint arXiv:2203.13601 (2022). [50] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. Analyticdb-v: A hybrid analytical engine towards query fusion for structured and unstructured data. PVLDB 13, 12 (2020), 3152–3165. [51] Qian Xu, Juan Yang, Feng Zhang, Junda Pan, Kang Chen, Youren Shen, Amelie Chi Zhou, and Xiaoyong Du. 2025. Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities. ACM SIGMOD 3, 1 (2025), 1–28. [52] Qian Xu, Juan Yang, Feng Zhang, Junda Pan, Kang Chen, Youren Shen, Amelie Chi Zhou, and Xiaoyong Du. 2025. Tribase-Library. https://github. com/xuqianmamba/Tribase. [53] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, et al. 2023. Spfresh: Incremental in-place update for billion-scale vector search. SOSP (2023), 545–561. [54] Rex Ying, Ruining He, Kaifei Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovec. 2018. PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest. ACM SIGKDD (2018).

Yitong Song, Shuhang Lu, Xuanhe Zhou, Pengcheng Zhang, and Jianliang Xu

[55] Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in HighDimensional Spaces. PVLDB 16, 8 (2023), 1979–1991.

[56] Shurui Zhong, Dingheng Mo, and Siqiang Luo. 2025. LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search. arXiv preprint arXiv:2505.17152 (2025).

Related documents

• TrajectoryDB: A New Database for Agent Trajectories#673620
• Preserving contextual information in cultural heritage metadata through multidimensional knowledge graphs#673621
• X-DigCheck: Co-Evolving Application Profiles and Knowledge Graphs, Demonstrated on the RTI Documentation of Rupe Magna#673622
• Open Tabular Insight Extraction: Where Do We Stand, and Where Should We Go?#673623
• Protocol effects on feature-based hardware-Trojan detection across Trust-Hub families#673624