arXiv CS open access

SieveIVF: Threshold-Aware IVF Execution for Large-Scale Training Data Deduplication

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

SieveIVF: Threshold-Aware IVF Execution for Large-Scale Training Data Deduplication Zhisheng Hu1,2 , Zhifang Li2 , Junjie Chen2 , Ke Xu2 , Yuxuan Li2 , Chufeng Chen2 , Rui Chen2 , Zhe Chen2 , and Ming-Chang Yang1 1 The Chinese University of Hong Kong 2 Tencent

arXiv:2608.03199v1 [cs.DB] 4 Aug 2026

ABSTRACT Embedding-based training data deduplication retrieves candidate duplicate edges above an application similarity threshold, but fixedprobe inverted-file (IVF) search ignores this predicate when giving every query the same partition budget. Across four Hunyuan workloads, qualifying neighbors appear early despite sharply varying search depths. We present SieveIVF, a threshold-aware IVF executor that stops after𝑊 consecutive searches find no qualifying candidate. The systems challenge is to preserve partition-major batching when each query’s remaining work depends on prior results. Continuous batching groups ready queries by partition. A lookahead scheduler layers on top, exposing only work committed by the stopping rule to increase concurrency without changing stopping decisions or returned results. We implement SieveIVF in Lance. At 𝑊 = 8, SieveIVF is 4.1–7.6× faster than fixed-probe IVF on four 10M Hunyuan workloads and 6.1–8.4× faster on two public 100M workloads under the same index and search parameters, with pooled filtered top-10 recall losses of 0.03–1.13 percentage points on Hunyuan and 1.43–2.29 percentage points on the public workloads. These results show how an application predicate can guide IVF work allocation without changing the index or bounded top-𝑘 interface.

KEYWORDS training data deduplication, vector search, IVF, threshold retrieval, approximate nearest neighbor search

INTRODUCTION

Large multimodal training corpora contain repeated screenshots, templated webpages, lightly edited images, and semantically redundant examples. Exact hashes identify byte-level duplicates but miss many of these relationships. Embedding-based training data deduplication instead retrieves similar records and uses qualifying neighbors as candidate edges for duplicate grouping. Prior work shows that removing such semantic duplicates can improve data and compute efficiency during model training [1]. Candidate retrieval for deduplication differs from generic top𝑘 search because it has an application similarity threshold 𝜏. A neighbor below 𝜏 cannot become a duplicate edge, regardless of its rank. Inverted-file (IVF) search, however, typically ranks partitions by centroid distance and probes a fixed number, 𝑛𝑝𝑟𝑜𝑏𝑒, for every query before filtering the returned candidates. This gives easy and difficult queries the same search budget. Lowering 𝑛𝑝𝑟𝑜𝑏𝑒 saves work for queries whose qualifying neighbors appear early, but it can truncate queries that require deeper probing. No single fixed probe budget accommodates both query types efficiently.

We study this mismatch using exact ground truth and stored IVF assignments from four 10M workloads in the Tencent Hunyuan training-data pipeline. Threshold-neighbor density varies sharply across queries and workloads, yet qualifying top-10 neighbors generally concentrate near the front of the partition order. The threshold can therefore guide search work instead of filtering output after every query exhausts the same fixed budget. We present SieveIVF, a threshold-aware IVF executor that follows the original partition order and stops each query after 𝑊 consecutive partition searches return no threshold-qualified candidate. The rule requires neither a learned predictor nor a new index. The consecutive-empty window 𝑊 is its only execution knob. Decreasing 𝑊 prunes more aggressively, whereas increasing it makes the rule more conservative and closer to fixed probing. The central systems challenge is to retain efficient partitionmajor batching. Conventional batched IVF determines before execution which queries will search each partition. With data-dependent stopping, this grouping changes as individual queries finish. Executing each query independently preserves the rule but produces small partition searches, while dispatching every remaining partition restores concurrency but performs work beyond an uncommitted stopping point. SieveIVF resolves this tension with continuous batching, which maintains per-query state and dynamically groups ready queries by partition. Furthermore, a lookahead scheduler layers on top of continuous batching to expose searches already committed by the stopping rule, increasing concurrency without changing the visited partitions, stopping decisions, or returned results. We implement SieveIVF in Lance [17] without changing the IVF index format, within-partition search, or bounded top-𝑘 interface. At 𝑊 = 8, SieveIVF is 4.1–7.6× faster than fixed-probe IVF on four 10M Hunyuan workloads and 6.1–8.4× faster on two public 100M workloads under the same index and search parameters, with pooled filtered top-10 recall losses of 0.03–1.13 percentage points on Hunyuan and 1.43–2.29 percentage points on the public workloads. This paper makes the following contributions: • We characterize threshold selectivity and IVF locality across four Hunyuan workloads, then turn consecutive threshold-empty searches into a lightweight per-query stopping signal. • We design continuous batching to preserve partition-major execution under data-dependent per-query stopping. A lookahead scheduler layers on top to expose additional committed work without changing the visited partitions or returned results. • We implement SieveIVF in Lance and evaluate it on four 10M Hunyuan workloads and two public 100M workloads. We compare a shared fixed-probe budget with workload-tuned baselines and isolate the effects of pruning, batching, and lookahead.

Zhisheng Hu et al.

2.2

Threshold Candidate Retrieval

Let 𝑋 = {𝑥 1, . . . , 𝑥 𝑁 } be the indexed corpus and 𝑄 be a batch of query embeddings. Given a similarity threshold 𝜏, the natural deduplication candidate set for query 𝑞 is 𝑅(𝑞, 𝜏) = {𝑥 ∈ 𝑋 | sim(𝑞, 𝑥) ≥ 𝜏 }. Vector search APIs often return at most 𝑘 records per query, so the system may compute a top-𝑘 subset of 𝑅(𝑞, 𝜏). The threshold 𝜏 determines which candidates qualify as potential duplicates. SieveIVF uses the presence or absence of such candidates in each partition to decide how much IVF work to perform, regardless of how the underlying search engine applies the threshold internally.

IVF Batch Search

Inverted file (IVF) indexes are widely used to scale vector search [7, 12, 22]. An IVF index clusters the corpus into partitions represented by centroids. For a query 𝑞, the search engine ranks centroids by distance to 𝑞, probes the nearest 𝑛𝑝𝑟𝑜𝑏𝑒 partitions, performs within-partition search [2], and merges candidate results. Training data deduplication processes large query batches offline, so our executor uses partition-major batching to improve throughput. It groups queries that probe the same partition so that they can share partition loading, cache locality, and CPU execution. This batch structure amortizes each partition’s fixed search cost across many queries, so throughput depends on keeping queries grouped by partition. If an optimization turns one large batch into many small per-query calls, it may reduce the number of searched partitions but lose the locality that makes IVF efficient. SieveIVF is designed around this constraint: it introduces per-query early stopping while preserving partition-major batching.

3 WORKLOAD CHARACTERIZATION 3.1 Hunyuan Workloads and Methodology We study four proprietary training-data deduplication workloads from the Tencent Hunyuan data pipeline: Webpage (WEB), TableQA (TABLE), STEM-Webpage (STEM), and Scene-OCR-QA (SCENE).

2--7 Median

100

B WE

BLE

M STE

(a)

E CEN

90th pct.

16 8 4 2 1

TAB

STE

(b)

SCE

Figure 1: Exact-GT characterization of Hunyuan workloads. Each starts with 10M 768-dimensional image embeddings. We uniformly sample 100K queries and remove them from the base, leaving an exclusive 9.9M-vector base. The workloads share the embedding representation but apply different downstream policies and cosine-similarity thresholds: 0.85 for WEB, 0.93 for TABLE, 0.90 for STEM, and 0.93 for SCENE. Each is calibrated per workload via offline sampling analysis before deduplication. Each 9.9M-vector base uses an IVF index with 2,400 partitions and RaBitQ [10] configured with 7 bits, which we denote as IVF_RQ7. The partition count gives approximately 4,125 vectors per partition, close to Lance’s recommended target of 4,096 [17]. We derive two workload measurements from exact ground truth. To measure threshold-neighborhood density, we exhaustively compute each query’s exact top-50 under cosine similarity, matching the largest 𝑘 evaluated later, and count the neighbors that meet its threshold. To measure IVF locality, we take the threshold-filtered exact top-10 neighbors, locate their stored partitions, and record where those partitions occur in the probe order used by Lance’s cosine search. All indexes use exact centroid assignment. Section 6.5 evaluates approximate assignment separately.

3.2 2.3

1 ≥ 50

Last productive rank

Embedding-based training data deduplication pipelines first convert raw training records into vectors, then query a vector index to retrieve near-duplicate candidates above a similarity threshold. Candidate edges may then be filtered using application-specific content signals, such as OCR and associated QA text. The surviving candidate edges are then grouped into duplicate components, which are used to assign labels for downstream training. Our production context is a Tencent Hunyuan data pipeline that prepares deduplicated corpora for large-scale multimodal model pretraining. Duplicate semantics remain application-specific. For example, SemDeDup defines semantic redundancy in embedding space and studies how removing redundant records affects training [1]. Once an application has selected such a policy, including its embedding model and similarity threshold, SieveIVF accelerates only candidate retrieval and leaves the policy itself unchanged.

0 8--49

Query share (\%)

2 BACKGROUND 2.1 Training Data Deduplication

Threshold Selectivity Varies Sharply

Figure 1(a) shows that these workloads occupy substantially different selectivity regimes. SCENE is sparse: 90.77% of queries have no threshold neighbor. WEB and STEM have zero-neighbor shares of 75.09% and 66.94%. TABLE is much denser: only 29.51% have no threshold neighbor, while 25.36% reach the right-censored ≥ 50 bin. Consequently, a production pipeline cannot treat one modality’s duplicate density as representative of the others. This heterogeneity exposes the limitation of a query-agnostic probe budget. Fixed-probe IVF assigns the same 𝑛𝑝𝑟𝑜𝑏𝑒 to every query. A value large enough for dense, long-tailed queries wastes work on sparse queries, while a smaller value may miss useful neighbors that appear later. Density variation therefore motivates a per-query probe budget, but does not by itself justify early stopping. Empty partitions are informative only when threshold-qualified neighbors typically occur near the front of the probe order.

3.3

Exact Neighbors Are Front-Loaded

Figure 1(b) reports the rank of the last IVF partition containing a threshold-filtered exact top-10 neighbor. For WEB, STEM, and SCENE, the median last rank is 1 and the 90th percentile is only 2–3, whereas TABLE reaches 5 and 16, respectively. Pooling threshold-qualified exact top-10 neighbors across queries, the first eight centroid-ranked partitions store 99.77%, 99.95%, and

SieveIVF: Threshold-Aware IVF Execution for Large-Scale Training Data Deduplication

Table 1: Physical IVF partition-size statistics. Workload WEB TABLE STEM SCENE

CV 0.755 0.590 0.721 0.664

Gini 0.329 0.240 0.316 0.305

99.87% of these neighbors for WEB, STEM, and SCENE, respectively. TABLE reaches 93.76% at rank 8 and 98.31% at rank 16. These values measure partition placement rather than search recall because compressed-vector search introduces additional approximation. They show that useful neighbors are strongly front-loaded, but the tail length differs across workloads. TABLE therefore provides a difficult case for a common stopping policy.

3.4

The Opportunity Is Semantic, Not Physical

The preceding sparsity is query dependent; it is not caused by an accidentally empty index. Table 1 shows that every one of the 9,600 physical partitions across the four indexes contains vectors. Partition sizes have coefficients of variation from 0.590 to 0.755, and the largest partition is 5.61–7.14× the mean. Thus the indexes exhibit real, nonuniform occupancy but no empty-partition shortcut. TABLE is the most balanced index by both coefficient of variation and Gini coefficient, yet has the most diffuse qualifying neighbors. The opportunity therefore comes from threshold-empty results for a particular query, not from skipping physically empty partitions.

3.5

Partitions in query–centroid distance order

Max/mean 6.44× 5.61× 7.14× 6.35×

From Workload Evidence to a Search Policy

The characterization exposes a limitation of fixed-probe IVF. It visits the same number of partitions for every query even though useful-neighbor density and span vary sharply across queries and workloads. Simply lowering 𝑛𝑝𝑟𝑜𝑏𝑒 removes the same suffix for all queries and risks truncating TABLE-like queries whose useful neighbors extend farther into the probe order. Changing the similarity threshold instead changes the deduplication task. What is missing is a runtime signal that adapts each query’s executed probe count without changing 𝜏 or its maximum 𝑛𝑝𝑟𝑜𝑏𝑒 budget. The local search already provides such an observation. A partition is threshold-empty for a query when its local search returns no candidate satisfying 𝜏. A single empty result is inconclusive: IVF search is approximate and a later partition may still qualify. A run of empty results, however, is runtime evidence that the query has left the front-loaded productive region observed above. SieveIVF therefore uses a consecutive-empty window 𝑊 . It stops a query when the current run reaches 𝑊 threshold-empty partitions (Figure 2). A hit resets the counter, allowing a dense or long-tailed query to continue. A small 𝑊 reacts quickly and saves more work; a large 𝑊 is conservative and approaches fixed probing. The consecutive-run form matters. Unlike a cumulative empty count or average empty rate, it treats any later hit as evidence that the query remains in a productive region. Between hits the counter is monotone, so the partitions that must be searched next can be committed solely from completed observations. Section 4 uses this property to make batched execution reproduce the same sequential stopping rule without predicting future hits.

𝑝1

𝑝2

𝑝3

𝑝4

𝑝5

1 0 1 Reset on Hit

Stale Counter 0

𝑝6

𝑝7

𝑝8

𝑝9

𝑝10

Pruned (never searched) 3 Stop: Stale = 𝑾(=3)

Returns a threshold candidate

Empty under threshold 𝜏

Figure 2: Threshold-aware stopping over IVF partitions.

3.6

The Batch Execution Challenge

A useful stopping rule is not yet an efficient operator. Executing it independently for each query fragments IVF into tiny partition searches and loses the shared loading, cache locality, and CPU efficiency of partition-major batching. At the other extreme, dispatching a query’s entire remaining probe list restores concurrency but schedules ranks before completed results have committed them. Such speculative work weakens pruning and can change the rule’s output if results beyond the eventual stopping point are retained. The execution design must therefore reduce per-query work, preserve partition-local batching as queries reach different stopping points, and expose enough committed work when few queries are active. Section 4 addresses these requirements with continuous batching as the execution substrate and a lookahead scheduler layered on top. Continuous batching dynamically regroups active queries by partition. Lookahead adds concurrency by exposing only ranks already committed by the same stopping rule.

SIEVEIVF DESIGN

The dilemma in Section 3 yields four requirements. R1 (compatibility): run on an unmodified IVF index with the same centroids, partitions, and within-partition search logic, so the technique is a drop-in execution policy rather than a new index. R2 (batch-preserving): reduce per-query work without destroying the partition locality that batched IVF depends on. R3 (concurrency-robust): serve both large offline batches and low-concurrency calls. R4 (minimal interface): expose one execution knob rather than another application policy, because deduplication pipelines already tune embedding, OCR, and text thresholds. The stopping rule below satisfies R1 and R4 directly. Continuous batching (Section 4.2) addresses R2 and the many-query case of R3, and lookahead scheduling (Section 4.3) extends R3 to low-concurrency calls.

4.1

Threshold-Aware Ordered Traversal

For each query 𝑞𝑖 in a batch, IVF ranks candidate partitions by query-centroid distance and produces the ordered list: 𝑃𝑖 = (𝑝𝑖,1, 𝑝𝑖,2, . . . , 𝑝𝑖,𝑛𝑝𝑟𝑜𝑏𝑒 ). SieveIVF preserves this order and changes only how far each query proceeds through the list before stopping. Each query maintains the state in Table 2. Here, a partition is empty for a query if the local search returns no candidate satisfying 𝜏, not if the partition contains no indexed vectors. After a partition search, if the result is non-empty, SieveIVF appends it to results and resets stale to zero. If the result is empty, stale is incremented. Once stale reaches 𝑊 , the query is stopped.

Zhisheng Hu et al.

Table 2: Per-query state under continuous batching. Lookahead instead uses stop line 𝑠𝑖 and enqueue cursor 𝑒𝑖 (Section 4.3). State next stale results

Meaning Next rank in 𝑃𝑖 to process Consecutive threshold-empty result count Accumulated non-empty local results

Per-Query State Ready Queue (by partition ID) 𝑞1 17 42

𝑞2 42 17

5 Enqueue

𝑞3 17 31 42 𝑞4 42

𝑝17

𝑞1 𝑞3

𝑝42

𝑞2 𝑞4

Pop

Microbatch Load 𝑝17 once, Scan 𝑞1 , 𝑞3 Load 𝑝42 once, Scan 𝑞2 , 𝑞4

Same Partition → One Group

Next Partition (shaded) Result advances each query to its next partition (or stops it)

Figure 3: Continuous batching groups queries by partition.

4.2

Continuous Batching

Fixed-probe batching can form all partition batches in advance. With per-query stopping, however, whether a query should search its next partition is known only after earlier searches complete. SieveIVF therefore maintains per-query execution state and continuously groups queries that are ready to search the same IVF partition (Figure 3, Algorithm 1). Dynamic Regrouping. Each ready item (𝑞𝑖 , 𝑗) indicates that query 𝑞𝑖 is ready to search partition 𝑝𝑖,𝑗 . Items targeting the same IVF partition form a partition group. A microbatch is a bounded subset of one group that workers search together. Per-query stopping makes group membership data-dependent because each completed search determines whether its query contributes another item. Continuous batching therefore updates the groups online from currently ready items, preserving partition locality as queries stop at different ranks. Scheduling Partition Groups. The ready queue processes partition groups in first-in, first-out (FIFO) order. A group enters the queue when it receives its first item, and later items for the same partition join it until dispatch. Each queue pop selects a target partition 𝑝 and up to 16K ready items from its group, forming a microbatch 𝐵. Larger groups are therefore served across multiple dispatches. FIFO determines only which ready group is served next; the key distinction from fixed-probe batching is online regrouping under data-dependent membership. During development, we also experiment with random and largest-group-first ordering, but neither consistently outperforms FIFO. We therefore retain FIFO for its simplicity and competitive performance. Algorithm 1 initializes one ready item per query at rank 1. Each completion updates the query’s local results and stale counter, then enqueues the next rank if the query remains active (lines 11– 18). After all searches complete, lines 19–21 merge each query’s local results into its final top-𝑘 output. A query thus contributes at most one ready item at a time and preserves the order in 𝑃𝑖 . With few active queries, however, this progression can limit parallelism. Section 4.3 addresses that case with lookahead scheduling.

Algorithm 1 Continuous batching with per-query stopping 1 // 𝑄: query batch 2 // 𝑃 = (𝑃𝑖 )𝑞𝑖 ∈𝑄 : per-query centroid-ranked partition orders 3 // 𝜏: application similarity threshold; 𝑊 : consecutive-empty window; 𝑘: neighbors per query 4 procedure ContinuousBatching(𝑄, 𝑃, 𝜏,𝑊 , 𝑘) 5 (𝑛𝑒𝑥𝑡𝑖 , 𝑠𝑡𝑎𝑙𝑒𝑖 , 𝑟𝑒𝑠𝑢𝑙𝑡𝑠𝑖 ) ← (1, 0, ∅ ) for each 𝑞𝑖 ∈ 𝑄 6 initialize ready queue with (𝑞𝑖 , 1) for each 𝑞𝑖 ∈ 𝑄 7 while ready or in-flight work remains do 8 while worker available and ready queue non-empty do 9 (𝑝, 𝐵) ← PopMicrobatch(ready queue) 10 LaunchSearch(𝑝, 𝐵, 𝜏, 𝑘) 11 for each completion (𝑞𝑖 , 𝑗, 𝑟 ) do ⊲ 𝑗: rank; 𝑟 : search result 12 𝑛𝑒𝑥𝑡𝑖 ← 𝑗 + 1 13 if 𝑟 ≠ ∅ then 14 append 𝑟 to 𝑟𝑒𝑠𝑢𝑙𝑡𝑠𝑖 ; 𝑠𝑡𝑎𝑙𝑒𝑖 ← 0 ⊲ hit 15 else 16 𝑠𝑡𝑎𝑙𝑒𝑖 ← 𝑠𝑡𝑎𝑙𝑒𝑖 + 1 ⊲ empty 17 if 𝑠𝑡𝑎𝑙𝑒𝑖 < 𝑊 and 𝑛𝑒𝑥𝑡𝑖 ≤ |𝑃𝑖 | then 18 enqueue (𝑞𝑖 , 𝑛𝑒𝑥𝑡𝑖 ) 19 for each 𝑞𝑖 ∈ 𝑄 do 20 𝑅𝑖 ← MergeTopK(𝑟𝑒𝑠𝑢𝑙𝑡𝑠𝑖 , 𝑘) 21 return 𝑅 = (𝑅𝑖 )𝑞𝑖 ∈𝑄 One query, W = 3: a hit at rank 3 extends the committed stop line from 3 to 6

𝑟1

𝑟2

𝑟3

𝑟4

𝑟5

𝑟6

𝑡1

𝑡2

𝑡3

𝑡4

𝑡5

𝑡6

𝑡1

𝑡2

𝑟7

𝑟8

Basic Each dispatch waits for the previous result: no overlap

Lookahead 𝑡2

Stop Line

(never crossed)

Initial Commit [𝑟1 .. 𝑟𝑊 ]

Hit Extends Commit to 𝑟3+𝑊

Hit

Empty (searched)

Pruned

𝑡𝑛 = Dispatch Round

Figure 4: Lookahead advances dispatch within the committed prefix. Basic denotes continuous batching without lookahead.

4.3

Lookahead Scheduling

Low Concurrency. Continuous batching gains throughput by merging queries that are simultaneously ready for the same partition. This works well when many queries are active, because partition groups can accumulate several ready items before dispatch. With only a handful of queries, however, a group often contains one item. Each query also exposes at most one ready item and waits for its result before advancing. Fixed-probe search commits to all 𝑛𝑝𝑟𝑜𝑏𝑒 partitions up front and can overlap them without this dependency, so serialization and queue bookkeeping can outweigh the work saved by pruning under low concurrency. Simply dispatching a query’s remaining tail would restore concurrency but would also schedule ranks whose necessity still depends on unseen hits. Lookahead instead uses work that the stopping rule has already committed. Every query must search ranks 1 through min(𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒), and every hit commits the next 𝑊 ranks. The committed ranks therefore form a prefix whose last rank is the query’s stop line. Lookahead dispatches this prefix without changing how far the query is allowed to travel (Figure 4).

SieveIVF: Threshold-Aware IVF Execution for Large-Scale Training Data Deduplication

Algorithm 2 Lookahead scheduling for one query 1 // 𝑞𝑖 : query with ordered partitions 𝑃𝑖 2 // 𝑠𝑖 : stop line; 𝑒𝑖 : first rank not yet enqueued 3 // 𝑊 : consecutive-empty window; 𝑛𝑝𝑟𝑜𝑏𝑒: maximum partition rank 4 procedure EnqueueCommitted(𝑞𝑖 , 𝑠𝑖 , 𝑒𝑖 ) 5 while 𝑒𝑖 ≤ 𝑠𝑖 do 6 enqueue (𝑞𝑖 , 𝑒𝑖 ) 7 𝑒𝑖 ← 𝑒𝑖 + 1 8 return 𝑒𝑖 9 procedure LookaheadSchedule(𝑞𝑖 ,𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒) 10 𝑠𝑖 ← min(𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒 ); 𝑒𝑖 ← 1 11 𝑒𝑖 ← EnqueueCommitted(𝑞𝑖 , 𝑠𝑖 , 𝑒𝑖 ) ⊲ initial prefix 12 for each completion (𝑞𝑖 , 𝑗, 𝑟 ) do ⊲ 𝑗: rank; 𝑟 : search result 13 if 𝑟 ≠ ∅ then 14 𝑠𝑖 ← max(𝑠𝑖 , min( 𝑗 + 𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒 ) ) ⊲ extend stop line 15 𝑒𝑖 ← EnqueueCommitted(𝑞𝑖 , 𝑠𝑖 , 𝑒𝑖 ) ⊲ new suffix

Stop Line. Formally, a query 𝑞𝑖 ’s stop line 𝑠𝑖 is the largest partition rank such that 𝑞𝑖 is committed to search every partition up to 𝑠𝑖 before it may stop. Initially 𝑠𝑖 = min(𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒). The query must complete every rank through 𝑠𝑖 even if all of their results are empty. Whenever partition 𝑝𝑖,𝑗 returns a hit, the consecutive-empty counter resets and the query commits the next 𝑊 ranks after 𝑗: 𝑠𝑖 ← max(𝑠𝑖 , min( 𝑗 +𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒)). Ranks at most 𝑠𝑖 are committed. Only later ranks depend on hits that have not yet happened. Lookahead scheduling enqueues each committed rank as soon as it becomes committed, instead of waiting for the preceding partition’s result. A single query can therefore contribute several ready items at once. Multiple low-concurrency queries are then more likely to contribute items to the same partition group and form a larger microbatch. Crucially, lookahead never expands the search beyond the stop line implied by the stopping rule. It changes when committed partition searches are dispatched, not which ranks the pruning policy is allowed to reach. Algorithm 2 shows the resulting scheduler. It reuses Algorithm 1’s partition queue, worker dispatch, local search, per-query result buffers, and final merge, but replaces its initial admission (line 6) and per-query continuation logic (lines 17–18) with committedprefix admission. Each query keeps 𝑒𝑖 , the first rank not yet enqueued, in addition to the stop line 𝑠𝑖 . Initialization enqueues ranks 1 through min(𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒) for each query. An empty result does not move 𝑠𝑖 . A hit at rank 𝑗 commits through min( 𝑗 + 𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒), after which the scheduler enqueues any newly committed suffix. Each rank is enqueued at most once, so lookahead adds parallelism without duplicating partition searches. Equivalence. Without lookahead, Algorithm 1 advances a query only after its preceding partition search completes, so it realizes the sequential stopping rule. Lookahead initially admits ranks 1 through min(𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒) and, when a completed search at rank 𝑗 returns a hit, updates the stop line to max(𝑠𝑖 , min( 𝑗 + 𝑊 , 𝑛𝑝𝑟𝑜𝑏𝑒)). A query–partition search’s hit-or-empty outcome does not depend on when it is dispatched. Because stop-line extensions arise only from already committed ranks and combine through monotone maximum updates, concurrent completion order cannot change the final stop line. Every admitted rank is therefore one that the sequential rule is also committed to visit, while the monotone enqueue cursor admits every rank through that stop line exactly once. The two configurations consequently execute the same query–partition

searches and merge the same local results. Lookahead changes dispatch timing, not stopping decisions or returned results.

4.4

Discussion

Tradeoff and Precondition. SieveIVF is a speed/recall optimization, not a lossless rewrite. A threshold-qualified candidate can appear after a run of empty partitions, and a small 𝑊 may stop before reaching it. The window therefore controls a real speed/recall tradeoff. SieveIVF also supports online calibration that selects 𝑊 from a small sample of the same query batch under a baseline-relative loss target (Appendix A). For training-data deduplication, a modest loss in candidate recall can be acceptable because a missed edge leaves some redundancy, whereas an incorrect edge may remove distinct training data. Lookahead changes only dispatch timing and leaves this tradeoff unchanged. The stopping signal also assumes that search-time centroid order is consistent with how vectors were assigned to partitions at construction. SieveIVF therefore requires exact centroid assignment. Section 6.5 deliberately violates this build-time precondition to measure its effect. Memory Efficiency. SieveIVF adds constant-sized state per query, and each ready item carries only query and partition metadata. Fixed-probe batching enumerates all |𝑄 | 𝑛𝑝𝑟𝑜𝑏𝑒 assignments before search, whereas continuous batching materializes only eligible work and lookahead only committed work. Early stopping therefore avoids scheduling metadata and local result batches for skipped searches, reducing memory relative to fixed probing.

IMPLEMENTATION

We implement SieveIVF in Lance [17], an open lakehouse format for multimodal AI with native vector search. The implementation reuses Lance’s on-disk IVF layout, within-partition search logic, and final top-𝑘 merge, and changes only how query–partition searches are admitted and scheduled at runtime. Lance already accepts 𝜏 as a distance upper bound and applies it to filter each partition’s local output. SieveIVF consumes the resulting hit-or-empty outcome to update the per-query state that drives the stopping rule (Section 4.1). The executor maintains these states together with the ready queue and partition groups. It forms a microbatch from up to 16K ready items for one partition and dispatches it to Lance’s search worker pool. As each microbatch completes, the executor updates the affected queries and admits any newly committed ranks. This integration requires neither a new index nor a learned stopping model.

6 EVALUATION 6.1 Setup and Metrics Workloads. We evaluate the four proprietary 10M Hunyuan workloads characterized in Section 3 and two public 100M workloads. For each workload, we uniformly sample 100K vectors without replacement as held-out queries and index the remainder. Table 3 summarizes the resulting base sizes, dimensions, thresholds, and IVF layouts. Each Hunyuan workload uses the workload-specific threshold reported in Section 3. LAION-100M uses embeddings from LAION-5B [20], while DEEP-100M uses descriptors from the first 100M vectors of DEEP1B [24]. Both public workloads use a cosine-similarity threshold of 𝜏 = 0.85.

Zhisheng Hu et al. WEB

Table 3: Evaluation workloads. IVF layout gives indexes × partitions per index. Data is raw FP32 base-vector size in decimal GB. Data (GB) 30.4 30.4 30.4 30.4 204.6 38.4

Index and Measurement. All workloads use cosine IVF_RQ7 indexes with exact centroid assignment. Lance normalizes base vectors at index time and queries at search time, and exact ground truth uses the same normalization. We choose IVF partition counts around Lance’s recommended 4,096 vectors per partition [17]. Each Hunyuan workload uses one index with 2,400 IVF partitions. Each public 100M workload has 16 coarse KMeans shards, with a separately built 1,500-partition Lance IVF_RQ7 index for each shard. Unless varied, fixed probing and SieveIVF use the same index, 𝑛𝑝𝑟𝑜𝑏𝑒 = 90, 𝑘 = 10, and threshold, while SieveIVF uses 𝑊 = 8 with lookahead. Public queries search all 16 shards at 𝑛𝑝𝑟𝑜𝑏𝑒 = 90 with identical four-way concurrency across executors, and their timing includes the global top-10 merge. Experiments use the Lance implementation described in Section 5 on a Tencent Cloud server with 32 logical cores on an AMD EPYC 7K62 CPU, 64 GiB of memory, and two 1 TB Tencent Cloud Block Storage (CBS) volumes of the Cloud SSD type. We report warmed-index wall-clock time under identical cache, warm-up, and concurrency conditions. Timing covers search and result collection, while setup and offline recall scoring remain outside every reported search time. Quality Metric. We compute ground truth by exhaustive cosine search over the full base, independently of IVF and pruning. Public experiments fix 𝑘 = 10 and use exact global top-10 lists. Let 𝐺𝜏,𝑘 (𝑞) be the threshold-filtered exact top-𝑘 ground-truth set for 𝑞, and let 𝐴(𝑞) be the returned neighbor set. Aggregating over all queries gives our primary metric, pooled filtered top-𝑘 recall: Í 𝑞 ∈𝑄 |𝐴(𝑞) ∩ 𝐺𝜏,𝑘 (𝑞)| Í 𝑅pool = . 𝑞 ∈𝑄 |𝐺𝜏,𝑘 (𝑞)| Queries with empty 𝐺𝜏,𝑘 (𝑞) remain in the timed workload but do not contribute to the denominator. The DiskJoin comparison in Section 6.6 reports direct-edge and connected-component coverage.

6.2

Effectiveness and Scale

Figure 5 sweeps the consecutive-empty window while holding the index, 𝑛𝑝𝑟𝑜𝑏𝑒, 𝑘, and threshold fixed. At the main setting 𝑊 = 8, SieveIVF is 4.1–7.6× faster than fixed probing with 0.03–1.13 percentage points of pooled filtered top-10 recall loss. The workload characterization in Section 3 explains this asymmetry. TABLE has the most qualifying neighbors, which extend furthest into the probe order, so it shows the smallest speedup and the largest recall change, while each of the other three workloads loses at most 0.13 percentage points of pooled filtered top-10 recall at 𝑊 = 8. The full sweep shows why 𝑊 remains an explicit knob. At 𝑊 = 2, speedup rises to 7.2–15.2×, but TABLE loses 7.03 percentage points of pooled recall. At 𝑊 = 16, the loss falls to 0.005–0.351 percentage points while speedup remains 2.9–4.7×. No single window is optimal for every workload. We use 𝑊 = 8 in later experiments as a common operating point between these extremes.

Recall loss (pp)

IVF layout 1 × 2,400 1 × 2,400 1 × 2,400 1 × 2,400 16 × 1,500 16 × 1,500

10 5 1 0 2

STEM

−1

−2

Empty window W (a)

SCENE

Empty window W (b)

Figure 5: Speed/recall tradeoff across empty windows. LAION

DEEP

10.0

Recall loss (pp)

𝜏 0.85 0.93 0.90 0.93 0.85 0.85

15 10 5 1 0

7.5 5.0 2.5 0.0

Empty window W (a)

Empty window W (b)

Figure 6: Scale-out results on two public 100M workloads. WEB

TABLE

STEM

SCENE

0.99

Pooled recall

Queries 100K 100K 100K 100K 100K 100K

Speedup

Dim. 768 768 768 768 512 96

Speedup

Base 9.9M 9.9M 9.9M 9.9M 99.9M 99.9M

Speedup

Workload WEB TABLE STEM SCENE LAION-100M DEEP-100M

TABLE

6 4 2 1

0.95 0.90

Fixed probing SieveIVF

0.85 0.80

4 8 16 24

Maximum probes nprobe (a)

Wall time (s) (b)

Figure 7: Probe-budget sensitivity and tuned fixed probing. Figure 6 repeats the sweep on the public workloads. At 𝑊 = 8, SieveIVF is 6.11× faster on LAION-100M and 8.38× faster on DEEP100M, with 1.43 and 2.29 percentage points of pooled recall loss. Increasing 𝑊 improves recall monotonically. At 𝑊 = 12, the two workloads retain 5.59× and 5.83× speedups while reducing the losses to 0.88 and 1.34 percentage points. These results extend the same execution mechanism to 100M-vector scale-out workloads with different dimensions and embedding geometries. Tuned Fixed-Probe Baseline. In deployment, 𝑛𝑝𝑟𝑜𝑏𝑒 is set by index scale rather than by a per-workload ground-truth study, so all four workloads use 90 of 2,400 partitions. No shared fixed budget is efficient across all four. WEB, STEM, and SCENE saturate early, while TABLE benefits from deeper probing (Section 3). SieveIVF instead adapts per-query work with one shared 𝑊 = 8. With both executors capped at 𝑛𝑝𝑟𝑜𝑏𝑒 = 24 (1% of the 2,400 partitions), Figure 7(a) shows that SieveIVF remains 1.53–2.39× faster with only 0.02–0.72 percentage points of pooled recall loss. Panel (b) matches recall by interpolating measured fixed-probe settings. Even then, SieveIVF remains 1.09–1.22× faster across all four workloads.

6.3

Why It Is Faster

Execution Ablation. Reducing partition scans is useful only if the remaining work still executes efficiently. Figure 8(a) separates work skipping, continuous batching, and lookahead at 𝑊 = 8. Serial traversal applies the stopping rule but fragments the workload into small partition calls, reaching only 1.25–2.54× speedup. Continuous batching regroups ready queries by partition and raises the speedup

SieveIVF: Threshold-Aware IVF Execution for Large-Scale Training Data Deduplication

2.5 1 0.0

TAB

STE

5.0 2.5 1 0.0

SCE

TAB

(a)

STE

SCE

89.5

89.3

89.2

87.9

TABLE

89.0

87.6

86.2

84.8

70.0

STEM

91.1

89.9

89.7

89.6

89.3

SCENE

91.1

89.7

89.5

89.3

89.1

88.2

2-3

4-5

6-9

Filtered exact top-10 GT neighbors

90 80 70

Operating Envelope

Request batch size sets how many queries each call contains. The similarity threshold decides which candidate vectors qualify, and 𝑘 caps how many are returned per query. Figures 10 and 11 vary these parameters independently to show where SieveIVF is effective. Request Batch Size. Figure 10(a) compares continuous batching with and without lookahead as each call grows from one query to the full 100K-query set. With one query per call, continuous batching alone reaches only 0.99–1.29× speedup, while lookahead raises this to 2.5–2.8× by parallelizing committed partition searches within the query. As the batch grows, continuous batching can group work from more queries, so lookahead’s additional advantage narrows to 1.02–1.08× for the full set. Threshold Selectivity. Figure 10(b) varies 𝜏 from 0.10 to 0.95. At loose thresholds, most partition searches return a qualifying candidate, leaving little work to prune. Scheduling overhead can then outweigh the savings, although throughput remains 0.71– 0.99× that of fixed probing in this unfavorable range. The first

2.5

0.1

all

10K

WEB

TABLE

STEM

1 0 5 10

Returned-neighbor bound k (a)

Figure 9: Pruned probes by threshold-neighbor count.

0.3

0.5

0.7

0.9

Cosine-similarity threshold τ (b)

SCENE

−1

−2

5 10

Returned-neighbor bound k (b)

Figure 11: Sensitivity to the returned-neighbor bound 𝑘. WEB

Build time (% of exact)

to 3.89–7.40×. Lookahead then exposes committed ranks earlier and reaches 4.12–7.86×. It is most useful for small request batches because it parallelizes committed partition searches within each query, as Figure 10(a) shows. Figure 8(b) shows the corresponding increase in mean microbatch occupancy, from 24–51 queries without lookahead to 162–209 with it. These larger microbatches also reduce loads into Lance’s partition cache by 2.7–3.4×. Because lookahead leaves the committed searches unchanged, its additional gain therefore comes entirely from fuller microbatches. Per-Query Adaptivity. Fixed probing visits 90 partitions per query. At 𝑊 = 8, SieveIVF visits only 8.16–17.05 on average, reducing total partition visits by 81.05–90.94%. This reduction is not limited to queries with no qualifying neighbor. Figure 9 groups queries by their filtered exact top-10 neighbor count. Even queries with ten such neighbors avoid 70.0% of partition visits on TABLE and 87.9– 89.3% on the other workloads. Thus, the savings depend on how early qualifying neighbors appear in the partition order, rather than merely on how many of them each query has.

5.0

Figure 10: Sensitivity to batch size and threshold.

Speedup

89.7

91.1

Queries per call (a)

Partitions pruned (%)

91.1

100

(b)

WEB

SCENE

1 0.0

Figure 8: Execution-mechanism ablation at 𝑊 = 8. Wall time is uninstrumented and counters are diagnostic.

6.4

STEM

7.5

Recall loss (pp)

100

TABLE

No lookahead + Lookahead

7.5

Speedup

5.0

WEB

200

TABLE

STEM

100 14.9%

1.7%

9.6%

8.1%

Extra loss (pp)

Speedup

Continuous + Lookahead

Speedup

Continuous

Queries / microbatch

Serial

7.5

SCENE

3 1 0.3 0.1

TAB

STE

(a)

NE SCE

Empty window W (b)

Figure 12: HNSW-assisted assignment at build time. Bar labels show nearest-centroid assignment mismatch. measured point above 1× is 𝜏 = 0.35 for WEB, 0.90 for TABLE, and 0.40 for STEM and SCENE. In practice, semantic deduplication commonly uses high similarity thresholds [1], so SieveIVF can operate in the range where it accelerates search. At 𝜏 = 0.95, all four workloads reach 6.8–7.9× speedup over fixed probing. Returned-Neighbor Bound. Figure 11 varies 𝑘 from 5 to 50 at each workload threshold. This bound controls how many qualifying neighbors the deduplication pipeline can retain for each query. SieveIVF remains faster at every point, by 3.9–4.6× on TABLE and 6.4–9.6× on the other workloads, while pooled filtered recall loss stays below 1.36 percentage points. Larger 𝑘 increases withinpartition search and merge work for both executors, but it does not remove the threshold-empty signal used for stopping.

6.5

Impact of Approximate Assignment

Build-Time Assignment. An IVF build assigns each base vector to a centroid and stores it in the corresponding IVF partition. Exact assignment uses the nearest centroid, while Lance can approximate this step with HNSW [19] to reduce centroid-distance computations. Because SieveIVF follows the query-time centroid order, a vector stored under a different centroid may be visited later. We compare exact and HNSW-assisted builds with the same base vectors and centroids. Figure 12(a) shows that HNSW shortens full-build wall time by 12.1–14.8%, but assigns 1.73–14.89% of sampled vectors to a non-nearest centroid. Exact assignment shows no mismatch.

Zhisheng Hu et al.

2.2x

1.03x

0.6x

Pairs covered (%)

DiskJoin / Lance time

Direct edges 13.4x

100

TAB

STE

SCE

(a)

100.0

95.2

95.0

75 50 25 0

Connected

3.5

5.4

8.3

Returned-neighbor bound k (b)

Figure 13: Lance and DiskJoin as different deduplication paths. SCENE coverage uses sampled DiskJoin pairs. Recall Impact. Figure 12(b) shows the consequence for early stopping. Relative to each index’s own fixed-probe recall, HNSWassisted assignment adds 0.27–2.88 percentage points of pooled recall loss at 𝑊 = 8. Increasing 𝑊 reduces but does not remove the gap. At 𝑊 = 16, WEB and STEM still lose an additional 1.02 and 1.50 points. We therefore disable HNSW-assisted assignment in all other experiments. Exact assignment makes each index build roughly 1.2× slower, but this cost is paid once and amortized as the index is reused for daily deduplication of millions of new vectors.

6.6

Comparison with DiskJoin

Our pipeline and DiskJoin [8] represent two different deduplication paths. DiskJoin targets the threshold-qualified pair relation, whereas our pipeline retains at most 𝑘 qualifying neighbors per query and forms duplicate groups through connected components. Figure 13(a) compares their wall time for a full self-search in which all 9.9M base vectors query the same base. For a conservative comparison, we exclude the cost of materializing DiskJoin’s complete pair output. With 𝑘 = 10, Lance with SieveIVF finishes 2.2× and 13.4× sooner on WEB and TABLE. DiskJoin is particularly slow on TABLE because the workload’s embeddings are more densely clustered, causing it to evaluate substantially more candidate pairs. The two paths differ by only 3.1% on STEM, while DiskJoin finishes 1.7× sooner on SCENE. These mixed results show that neither path consistently dominates across workloads and output requirements. Figure 13(b) asks whether returning only 𝑘 neighbors per query is still sufficient for deduplication. For 990 uniformly spaced SCENE samples, only 3.5–8.3% of the pairs found by DiskJoin appear as direct Lance edges across 𝑘 = 10, 20, and 40. After connected components, however, the two records are grouped together for 95.0–100% of these pairs. In other words, for almost every sampled pair that DiskJoin identifies as duplicate, our pipeline also groups the two records together while retaining far fewer edges. The two paths also suit different data lifecycles. DiskJoin is attractive for onetime deduplication of a largely static corpus. In our setting, millions of new vectors arrive each day, so the indexed path amortizes its build cost by reusing the same index for each arriving batch. This recurring workflow motivates our use of SieveIVF.

RELATED WORK

Deduplication and Threshold Joins. Semantic deduplication methods such as SemDeDup use pretrained embeddings to identify redundant training examples and study removal policies [1]. Classical pipelines rely on keys, shingles, MinHash, or SimHash [4, 5]. Similarity joins target threshold-qualified vector pairs. DiskJoin

schedules bucket-pair work and SSD access for large self-joins [8], while recent approximate vector-join work shares graph traversal across related queries [15]. Unlike these pair-oriented systems, SieveIVF accelerates bounded top-𝑘 threshold retrieval and leaves deduplication policy downstream. Adaptive Vector Search and Batching. Vector systems increasingly incorporate predicates and bounds into search [21, 23]. VBASE composes vector and relational operators through relaxed monotonicity [26], while Filtered-DiskANN builds label-aware graph indexes [11]. Existing approaches learn stopping decisions from intermediate features [18], derive probabilistic signals from localitysensitive hashing [13], or use a learned recall predictor during HNSW or IVF traversal [6]. SieveIVF instead stops from observed runs of threshold-empty partitions. It needs neither training queries nor a predictor and exposes 𝑊 as an auditable speed/recall knob. Database engines have long adapted execution after observing intermediate results, including Eddies and threshold algorithms [3, 9]. SieveIVF applies this idea inside an IVF physical operator, where adaptation must preserve partition locality. Faiss partition-major batching forms query–partition groups from each query’s fixed 𝑛𝑝𝑟𝑜𝑏𝑒 set before execution [14]. SieveIVF makes group membership data-dependent. A query enters a group only when its stopping state admits the next rank, while lookahead exposes only ranks already committed by the rule. Its continuous-batching terminology follows neural model serving [16, 25], but it batches queries ready for the same IVF partition rather than decoding steps.

CONCLUSION

In training data deduplication, fixed-probe IVF gives every query the same partition budget. SieveIVF converts runs of thresholdempty partitions into per-query stopping signals and uses continuous batching and lookahead to preserve efficient partition-major execution. At 𝑊 = 8, SieveIVF is 4.1–7.6× faster than fixed-probe IVF on four 10M Hunyuan workloads and 6.1–8.4× faster on two public 100M workloads under the same index and search parameters, with pooled filtered top-10 recall losses of 0.03–1.13 percentage points on Hunyuan and 1.43–2.29 percentage points on the public workloads. SieveIVF accelerates IVF candidate retrieval rather than the end-to-end deduplication pipeline. More broadly, SieveIVF shows how a predicate known before search can guide physical work rather than serve only as an output filter, without changing either the index format or the existing bounded top-𝑘 interface.

REFERENCES [1] Amro Abbas, Kushal Tirumala, Dániel Simig, Surya Ganguli, and Ari S. Morcos. 2023. SemDeDup: Data-efficient learning at web-scale through semantic deduplication. arXiv:2303.09540 [cs.LG] https://arxiv.org/abs/2303.09540 [2] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2015. Cache locality is not enough: high-performance nearest neighbor search with product quantization fast scan. Proc. VLDB Endow. 9, 4 (Dec. 2015), 288–299. https: //doi.org/10.14778/2856318.2856324 [3] Ron Avnur and Joseph M. Hellerstein. 2000. Eddies: continuously adaptive query processing. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (Dallas, Texas, USA) (SIGMOD ’00). Association for Computing Machinery, New York, NY, USA, 261–272. https://doi.org/10.1145/ 342009.335420 [4] A.Z. Broder. 1997. On the resemblance and containment of documents. In Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171). 21–29. https://doi.org/10.1109/SEQUEN.1997.666900 [5] Moses S. Charikar. 2002. Similarity estimation techniques from rounding algorithms. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of

SieveIVF: Threshold-Aware IVF Execution for Large-Scale Training Data Deduplication

Computing (Montreal, Quebec, Canada) (STOC ’02). Association for Computing Machinery, New York, NY, USA, 380–388. https://doi.org/10.1145/509907.509965 [6] Manos Chatzakis, Yannis Papakonstantinou, and Themis Palpanas. 2025. DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 4, Article 242 (Sept. 2025), 26 pages. https: //doi.org/10.1145/3749160 [7] 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 neighbor search. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NIPS ’21). Curran Associates Inc., Red Hook, NY, USA, Article 398, 14 pages. [8] Yanqi Chen, Xiao Yan, Alexandra Meliou, and Eric Lo. 2025. DiskJoin: Large-scale Vector Similarity Join with SSD. Proc. ACM Manag. Data 3, 6, Article 315 (Dec. 2025), 27 pages. https://doi.org/10.1145/3769780 [9] Ronald Fagin, Amnon Lotem, and Moni Naor. 2001. Optimal aggregation algorithms for middleware. In Proceedings of the Twentieth ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems (Santa Barbara, California, USA) (PODS ’01). Association for Computing Machinery, New York, NY, USA, 102–113. https://doi.org/10.1145/375551.375567 [10] Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 3, Article 167 (May 2024), 27 pages. https: //doi.org/10.1145/3654970 [11] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. 2023. FilteredDiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In Proceedings of the ACM Web Conference 2023 (Austin, TX, USA) (WWW ’23). Association for Computing Machinery, New York, NY, USA, 3406–3416. https://doi.org/10.1145/3543507.3583552 [12] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (Jan. 2011), 117–128. https://doi.org/10.1109/TPAMI.2010.57 [13] Jianfeng Jiang, Shen Xu, and Ying Gao. 2025. A uniformed adaptive early termination model through probabilistic feature to speed up quantization-based search. International Journal of Computers and Applications 47, 1 (2025), 17–28. https://doi.org/10.1080/1206212X.2024.2431229 [14] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data 7, 3 (2021), 535–547. [15] Kyoungmin Kim, Lennart Roth, Liang Liang, and Anastasia Ailamaki. 2026. Fast Approximate Vector Joins via Offline-Online Co-Design. arXiv:2603.16360 [cs.DB] https://arxiv.org/abs/2603.16360 [16] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient Memory Management for Large Language Model Serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles (Koblenz, Germany) (SOSP ’23). Association for Computing Machinery, New York, NY, USA, 611–626. https://doi.org/10.1145/3600006.3613165 [17] Lance Format. 2026. Lance: The Open Lakehouse Format for Multimodal AI. https://github.com/lance-format/lance. [18] Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. 2020. Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD ’20). Association for Computing Machinery, New York, NY, USA, 2539–2554. https://doi.org/10.1145/ 3318464.3380600 [19] Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824– 836. https://doi.org/10.1109/TPAMI.2018.2889473 [20] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaczmarczyk, and Jenia Jitsev. 2022. LAION-5B: an open large-scale dataset for training next generation image-text models. In Proceedings of the 36th International Conference on Neural Information Processing Systems (New Orleans, LA, USA) (NIPS ’22). Curran Associates Inc., Red Hook, NY, USA, Article 1833, 17 pages. [21] 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. Proc. ACM Manag. Data 3, 6, Article 373 (Dec. 2025), 26 pages. https://doi.org/10.1145/3769838 [22] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD

’21). Association for Computing Machinery, New York, NY, USA, 2614–2627. https://doi.org/10.1145/3448016.3457550 [23] 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. Proc. ACM Manag. Data 3, 1, Article 82 (Feb. 2025), 28 pages. https://doi.org/10.1145/3709743 [24] Artem Babenko Yandex and Victor Lempitsky. 2016. Efficient Indexing of BillionScale Datasets of Deep Descriptors. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055–2063. https://doi.org/10.1109/CVPR.2016. 226 [25] Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and ByungGon Chun. 2022. Orca: A Distributed Serving System for Transformer-Based Generative Models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). USENIX Association, Carlsbad, CA, 521–538. [26] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 377–395.

AUTOMATIC WINDOW CALIBRATION

The consecutive-empty window𝑊 gives SieveIVF a single, transparent speed/recall knob, but the best setting varies across workloads and even across independently indexed shards. Selecting it offline would require profiling every new workload, potentially against exact ground truth. We therefore add a calibrated execution mode that selects 𝑊 automatically inside each sufficiently large search call. It uses fixed-probe output from a small sample of the same query batch and requires neither exact ground truth nor an offline workload profile. Sampling works because a call fixes the query distribution, threshold, and index, so a uniform sample observes the same mix of stopping behavior as the full batch. In-Call Calibration. Given a query batch 𝑄, the executor uniformly samples 𝑄𝑠 ⊂ 𝑄 without replacement and fully probes its 𝑛𝑝𝑟𝑜𝑏𝑒 partitions. It retains the resulting partition-level outputs and merges them into the fixed-probe result 𝐴fixed (𝑞) for every sampled query. The executor then replays the stopping rule over these recorded outcomes for each candidate 𝑊 . Let 𝐴𝑊 (𝑞) be the output that window 𝑊 would retain. We measure its loss relative to the sampled fixed-probe output as

Í loss(𝑊 ) = 1 −

𝑞 ∈𝑄𝑠 |𝐴𝑊 (𝑞) ∩ 𝐴fixed (𝑞)|

𝑞 ∈𝑄𝑠 |𝐴fixed (𝑞)|

The executor selects the smallest 𝑊 < 𝑛𝑝𝑟𝑜𝑏𝑒 satisfying loss(𝑊 ) < 𝜖, where 𝜖 is the user-specified loss target. If no pruned window satisfies the target, it uses full probing. The sampled queries keep their already computed fixed-probe results, while the remaining queries run with lookahead under the selected 𝑊 .

Zhisheng Hu et al.

Algorithm 3 Automatic consecutive-empty window calibration 1 // 𝑄: query batch; 𝑃 : per-query partition orders 2 // 𝑟 : sample rate; 𝜖: baseline-relative loss target 3 procedure CalibratedSearch(𝑄, 𝑃, 𝜏, 𝑘, 𝑛𝑝𝑟𝑜𝑏𝑒, 𝑟, 𝜖) 4 𝑄𝑠 ← UniformSample(𝑄, ⌈𝑟 |𝑄 | ⌉) 5 𝐿𝑠 ← FullProbeByPartition(𝑄𝑠 , 𝑃, 𝜏, 𝑘, 𝑛𝑝𝑟𝑜𝑏𝑒) 6 𝐴fixed ← MergeTopK(𝐿𝑠 , 𝑘) 7 𝐻 ← RequiredWindowHistogram(𝐿𝑠 , 𝐴fixed ) Í 8 𝑍 ← 𝑞 ∈𝑄𝑠 |𝐴fixed (𝑞) | ∗ 9 𝑊 ← 𝑛𝑝𝑟𝑜𝑏𝑒; 𝑟𝑒𝑡𝑎𝑖𝑛𝑒𝑑 ← 0 10 for 𝑊 ← 1 to 𝑛𝑝𝑟𝑜𝑏𝑒 − 1 do 11 𝑟𝑒𝑡𝑎𝑖𝑛𝑒𝑑 ← 𝑟𝑒𝑡𝑎𝑖𝑛𝑒𝑑 + 𝐻 [𝑊 ] 12 𝑙𝑜𝑠𝑠 ← 1 − 𝑟𝑒𝑡𝑎𝑖𝑛𝑒𝑑/𝑍 13 if 𝑙𝑜𝑠𝑠 < 𝜖 then 14 𝑊 ∗ ← 𝑊 ; break 15 𝐴𝑟 ← LookaheadSearch(𝑄 \ 𝑄𝑠 , 𝑃, 𝜏,𝑊 ∗ , 𝑘) 16 return RestoreOrder(𝐴fixed , 𝐴𝑟 )

12 Fixed W = 8

8 3

TAB

STE

(a)

SCE

Selected window W

2.77x

7.84x

2.57x

3.49x

EB BLE TEM ENE ION EEP D S LA TA SC

(a)

2.5 2.0 1.5 1.0 0.5 0.0

0.608

0.438 0.299 0.162 0.305

0.601

EB BLE TEM ENE ION EEP D S LA TA SC

(b)

Figure 15: Performance and recall under fixed and calibrated windows. Light dashed bars use fixed 𝑊 = 8, and solid bars use automatic calibration. Panels report speedup over fixed probing and recall loss against pooled filtered exact top-10 ground truth.

LAION

DEEP

48 32 16 0 3

9.16x

8.25x

10 8 6 4 2 0

Calibrated

Recall loss (pp)

Speedup

Fixed W = 8

Efficient Replay. Calibration does not issue another search for every candidate window 𝑊 . A lookahead execution always visits a prefix of the partition order. Cutting the probe order short only removes candidates, and a neighbor drops out of the top-𝑘 only when 𝑘 better candidates displace it. The prefix cannot supply a better candidate that was not already there, so every neighbor of 𝐴fixed (𝑞) found within the prefix also appears in 𝐴𝑊 (𝑞). Each neighbor therefore has a required window: the smallest 𝑊 whose prefix reaches the partition where that neighbor was found. One pass over a sampled query’s outputs, in rank order, computes it for all of them. Counting neighbors by required window gives the histogram 𝐻 of Algorithm 3: pooled over all sampled queries, 𝐻 [𝑊 ] is the number of neighbors whose required window is exactly 𝑊 . A larger 𝑊 only extends the prefix, so window 𝑊 retains every neighbor whose required window does not exceed 𝑊 . The prefix sums of 𝐻 therefore give loss(𝑊 ) for every window at once, at 𝑂 (𝑛𝑝𝑟𝑜𝑏𝑒 · 𝑘) cost per sampled query. In our evaluated configuration, calls below 10K queries or samples that return no neighbors use fallback 𝑊 = 8. Calls without a similarity threshold use full probing because they provide no threshold-empty stopping signal.

8–34 across DEEP’s (Figure 14(b)). This variation confirms that one fixed window need not fit even every shard of the same workload, consistent with the view that the selected window is determined jointly by the query batch and the index it searches.

Shard (b)

Figure 14: Online window selection across workloads and shards. Panel (a) shows one 10M index per workload. Panel (b) shows independent choices for the 16 shards of each public 100M workload. Results. We evaluate the mechanism with a 2% sample, a strict 0.5% sample-relative loss target, and the same 100K-query calls described in Section 6.1. Figure 14(a) shows that calibration selects 𝑊 = 3, 14, 3, and 5 for WEB, TABLE, STEM, and SCENE. For the scale-out workloads, each independently indexed shard calibrates against its own local output while using the same sampled query indices. The selected windows span 12–63 across LAION’s 16 shards and

Figure 15 compares calibration with the fixed 𝑊 = 8 setting. Including the full-probe sample cost, calibrated execution is 2.77– 9.16× faster on the 10M workloads and 2.57–3.49× faster on the public 100M workloads than fixed probing under the same setup. It chooses more conservative windows for TABLE and both public workloads, reducing the largest exact-GT recall loss from 2.29 percentage points under 𝑊 = 8 to 0.608. Although the sample-relative calibration loss and exact-GT recall loss are different metrics, all six calibrated losses stay around or below 0.5 percentage points (range: 0.162–0.608). The goal is automatic 𝑊 selection under an explicit loss target, not uniform speed gains over a manually chosen 𝑊 . Scope. The 0.5% target estimates loss against fixed-probe output on the sampled queries. It is neither a confidence bound nor a direct guarantee on full-call exact-GT recall. Sample queries receive full probing, whose cost is included in the reported wall time.

SieveIVF: Threshold-Aware IVF Execution for Large-Scale Training Data Deduplication

Analyze & explore related research in Conceptio

Related documents