acceptodds
Under review as a conference paper at ICLR 2027

Large-Scale Bucket-Feasible LSH-MinHash Deduplication

Abstract

LSH-MinHash deduplication in DataTrove keeps one document per connected component of band collisions. Connectivity does not make every pair a near-duplicate: the largest ClueWeb22 component contains 28.8 million documents, of which one is kept. We instead retain at most one document per collision bucket, reusing DataTrove's four stages—signature generation, band matching, clustering, and filtering. Band-sharded Stage 2.5 pruning removes redundant incidences before single-node, memory-bound clustering. A multi-seed extension reruns the same stages under independent signatures with retuned banding, suppressing low-similarity collisions at a chosen high-similarity recall target; processing survivors sequentially satisfies every round's constraints without materializing a joint bucket family. Within a prior strong independent set framework, intrinsic bucket weights connect exact reductions, selection, and optimality certificates, and an observed-history certificate bounds final retention with a sharp information limit. On 1.62B ClueWeb22 and 3.98B HPLT documents, on the same buckets as legacy unionization, bucket-feasible selection retains 32M/34M more documents; four retuned seeds raise the gain to 64M/65M and lower Stage 3 MaxRSS by /. Greedy retention reaches at least of the puncturing upper bound in all 20 active seed rounds. Within the 28.8M-document component, the strongest local run retains 1,474,462 documents; exhaustive MinHash comparison of all survivor pairs finds 20 with estimated similarity .

Primary area:
optimization
Keywords:
Data near deduplication, large-scale data curation, locality-sensitive hashing, MinHash, hypergraph independent sets.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_uWPMOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses over-removal in DataTrove’s near-duplicate pipeline, which uses MinHash/LSH to find candidate matches, merges them with union-find, and keeps one document per connected component. Because similarity is not transitive, a chain of pairwise matches can merge documents that are not near-duplicates of each other. The authors instead keep at most one document per collision bucket, using band-sharded pruning of redundant buckets, weight-one preclusion, layered greedy selection, and an optional multi-seed extension, with structural upper-bound certificates to assess retention optimality. Theory shows the output never retains fewer documents than unionization, and the gap can be unbounded. On ClueWeb22 and HPLT, the single-seed method retains 32M and 34M more documents than legacy on the same buckets. Four retuned seeds raise this to 64M and 65M and cut Stage 3 peak memory by 48.36% and 5.70%. Greedy reaches at least 99.43% of the strongest per-round bound on active documents. The main finding is higher retention. Whether the extra documents improve training data or model performance, and the runtime cost, are left untested.

Critical strengths

(+) Clearly identifies an important limitation of connected-component-based deduplication.

(+) Introduces a clean bucket-feasible formulation with billion-scale evaluation.

(+) Provides useful theoretical analysis of retention cardinality using upper-bound certificates.

Critical weaknesses

(-) Limited algorithmic novelty. Much of the optimization machinery is inherited from Wu & Cong (2026). The paper’s independent contributions lie primarily in adapting this framework to DataTrove, band-sharded pruning, the unionization comparison, and the multi-seed extension. These are useful systems and formulation contributions, but the paper provides limited evidence isolating how much each new component contributes beyond the inherited solver.

(-) Insufficient validation of deduplication quality and practical utility. The paper focuses on maximizing document retention without demonstrating that the additional documents improve data quality, diversity, or downstream language model performance. If legacy deduplication achieves comparable model performance with fewer documents, it may be more efficient. The paper provides neither an independent evaluation of duplicate quality nor downstream training experiments.

(-) Incomplete evaluation of computational and system costs. The evaluation focuses primarily on Stage 3 peak memory. It does not report end-to-end execution time, stage-level runtime, I/O overhead, or temporary storage requirements, so the overall computational trade-off remains unclear. Moreover, the reported memory reductions combine several configuration changes, making it difficult to isolate the contribution of Stage 2.5 pruning.

(-) Insufficient ablation against simpler greedy selection baselines. The paper does not establish that the layered selection procedure is justified relative to simpler alternatives. Secondary within-layer ordering improves retained-root counts by less than 0.01% over random within-layer ordering, suggesting that the additional ordering heuristics offer only marginal benefit. More importantly, the paper does not provide a full-corpus comparison against a simple non-layered maximal greedy algorithm. It is therefore unclear how much of the retention gain comes from the layered strategy rather than from the basic bucket-feasible formulation itself, and whether the additional algorithmic complexity and computational costs are justified by the benefits.

Questions for authors
  1. Please clarify the practical interpretation of the “additional retained documents.” Can the authors report quality, usable-token yield, diversity, and independently measured duplication for the documents retained by their method but discarded by legacy? A controlled training run would directly test whether these documents help.

  2. Please separate the retention comparisons in the paper. The <0.01% figure in Section 6.3 / Appendix A.2 is for secondary ordering versus random ordering within the layered method; the same-bucket single-seed comparison in Table 1 is +32M/+34M over legacy. Can the authors add a full-corpus comparison with unlayered maximal greedy, plus runtime and peak-memory measurements, to show whether the method’s added complexity is worthwhile?

2 comments
AuthorsOpenReview ↗

**Response to Reviewer uWPM**

We thank the reviewer and ran the requested experiments; they change how we present the paper.

Unlayered greedy (W4, Q2). Same pruned (14,9;1)(14,9;1) buckets, same implementation, one node per run. An independent checker confirmed every output feasible and maximal.

RuleClueWeb keptTime / peakHPLT keptTime / peak
Legacy (connected components)78.711M—737.009M—
Maximal scan, document-ID order105.511M48 min / 156 GiB761.889M3.6 h / 570 GiB
Maximal scan, ascending degree111.856M62 min / 160 GiB771.322M3.1 h / 555 GiB
Layered greedy (paper)111.993M73 min / 152 GiB771.381M2.3 h / 480 GiB
Upper bound UpunctU_{\rm punct}, any algorithm112.639M—772.416M—

Time is selection after loading; peak is Stage 3 MaxRSS; times vary by up to 30% between runs.

The reviewer is right: the formulation, not layering, drives the gain. The ID-order scan already keeps 26.8M/24.9M more documents than legacy, low-degree-first order adds 6.3M/9.4M, and layering adds only 136,696/58,974 (0.12%/0.008% of UpunctU_{\rm punct}). Layering has the lowest peak; it is the slowest on ClueWeb and the fastest on HPLT. We will present degree-ordered greedy as the baseline, with layering and secondary ordering (<0.01%) as optional refinements, and separate the two comparisons in §6.3.

Costs (W3), with a correction. Table 1's legacy MaxRSS values are not from the same-bucket legacy jobs; the ClueWeb row is from an earlier run on different buckets. Same-bucket jobs, same node count per stage:

(14,9;1)(14,9;1)ClueWeb legacyClueWeb oursHPLT legacyHPLT ours
Stages 1+2, h:mm1:592:123:363:37
Stage 2.5 (14 nodes)—0:59—11:20
Stage 3 (1 node)2:212:2419:546:41
Stage 40:150:150:290:29
End to end4:355:4923:5922:06
Stage 3 peak, GiB128.7151.6713.1479.6
Bucket files, GB (after 2.5)72.227.0 (12.3)507.6238.8 (21.1)

Our selection needs 18% more peak memory than union-find on ClueWeb and 33% less on HPLT, where it is also 3× faster. Table 1's figures for ours included the optional certificates. Corrected, the single-seed gains are +33.3M/+34.4M and the four-seed peak reductions are 30%/29% (not 48.36%/5.70%). Stage 2.5, the added cost, reads 0.4/3.6 TB of the pipeline's 48/65 TB and shrinks Stage 3's input 2.1×/11.2×. Without it, ClueWeb Stage 3 needs 279.5 GiB instead of 151.6, takes 5:35 instead of 2:24, and keeps 399,100 fewer documents; extrapolated linearly, HPLT would need about 2.3 TiB, more than our 2.2 TiB nodes.

Novelty (W1). We agree that Wu & Cong (2026) state the formulation, layered greedy and certificates for general hypergraphs. The measurements above isolate this paper's components: bucket-feasible selection in DataTrove (+26.8M/+24.9M even with the simplest scan), Stage 2.5 (needed to fit HPLT on one node; −46% Stage 3 peak on ClueWeb) and optional multi-seed (+32M/+31M at 4.7×/4.0× the signature work). The inherited solver adds 6.5M/9.5M.

The extra documents (W2, Q1). Measured on ClueWeb22 (HPLT's texts were not kept), samples of 10,240 per group, same buckets:

Group (size)GPT-2 tokensFineWeb-EduEdu ≥3Hosts
Kept by ours only (77.6M)1,2051.124.9%6,805
Kept by legacy only (44.3M)1,3581.297.4%7,683
Kept by both, in a bucket (34.4M)1,3531.297.4%7,663
In no bucket (1,175M)1,3701.215.9%6,911
Removed by both (288.8M)1,0340.943.0%5,553

Means; hosts: distinct per sample. The "only" groups exceed the net 33.3M because the methods often keep different members.

  • Duplication, without MinHash. For one extra document per rank (2,048), exact character-20-gram Jaccard to the retained documents two collisions away has median 0.64 and never reaches 0.9; 8% have one at ≥0.75 (5.5% with word 5-grams). For 24%, the document legacy kept in their place has Jaccard below 0.5. Bucket partners (control): median 0.72.
  • Yield. +33.3M documents and +33.3B ± 5.6B GPT-2 tokens (+1.9%).
  • Quality. The gap reflects which components, not which members: against legacy's kept document in the same component, the extra documents score the same (+0.009 ± 0.010). Scores fall with component size (1.30 in pairs, 0.72 above 64K documents), and legacy keeps one per component, so 70% of its kept bucketed documents come from pairs. Large components are templated pages (listings, product and company pages) with distinct text; legacy drops all but one by connectivity, a quality filter would by content.

A training run would test the criterion (b,r)(b,r), which binds legacy equally; it is our next step.

Revisions. Corrected Table 1 and every claim based on it; the tables above, the full baseline table and this study in the appendix; a rewritten §6.3.

Thank you for the additional experiments and corrections. The unlayered baselines and stage-level cost measurements provide additional evidence regarding the selection algorithms and computational trade-offs. The results indicate that most retention gains come from the bucket-feasible formulation, while layering provides modest additional retention and some memory benefits.

The data-quality study offers useful diagnostics, but its restricted similarity comparisons and ClueWeb-only coverage leave the practical value of the additional documents uncertain. A controlled training experiment would test the retention policy, not merely the shared ((b,r)) criterion, since the policies produce different training corpora.

While my concerns about the limited algorithmic novelty beyond the prior framework and the lack of downstream validation remain, the additional experiments provide useful evidence. I will therefore raise my rating to 2.

Reviewer_88FTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper changes which documents DataTrove keeps after MinHash detects possible duplicates. Instead of keeping one document from each connected group, it allows multiple documents provided that no detected collision bucket contains two survivors. With identical buckets, it retains 32M more ClueWeb22 documents and 34M more HPLT documents than the legacy rule. A mathematical upper bound estimates how many more documents could satisfy those same constraints.

Critical strengths
  • The paper identifies a concrete source of over-deletion: if A collides with B and B collides with C, the legacy rule keeps only one, even when A and C do not collide. The new rule can keep A and C together.

  • The system is evaluated on 1.62B ClueWeb22 documents and 3.98B HPLT documents, making the memory and retention results relevant to large corpus processing.

  • The retained count is compared with a verifiable upper bound under the same bucket constraints. This tells readers how much room remains to improve selection without claiming that all retained documents are semantically distinct.

Critical weaknesses
  • The four-round gain of 64M/65M retained documents is not solely the effect of the new rule. Those runs also change the number of MinHash bands and rows and repeatedly filter survivors. The paper acknowledges that only the 32M/34M identical-bucket comparison isolates the rule.

  • More survivors do not necessarily make better training data. Duplicate diagnostics reuse the hashes that selected the survivors rather than independently checking text similarity. Total pipeline runtime and temporary storage are also missing, so the quality–resource trade-off is unknown.

  • The document-selection algorithm and upper bounds reuse other's solver. The added step removes redundant buckets before selection, but no ablation measures its own runtime or memory savings. Its contribution beyond integrating the existing solver is therefore hard to assess.

Questions for authors

See weaknesses

1 comment
AuthorsOpenReview ↗

**Response to Reviewer 88FT**

We thank the reviewer. We added measurements for each weakness; the full stage-by-stage cost and baseline tables are in our response to Reviewer uWPM.

Isolating the rule (W1). We agree that the four-seed 64M/65M mixes the rule with changed evidence. The revision removes it from the abstract and leads with the identical-bucket comparison. That comparison also needs a correction: Table 1's ClueWeb legacy row came from an earlier run on different buckets, and the gains are +33.3M/+34.4M. To check that the gain is not specific to (14,9)(14,9), we also compared legacy and ours on the identical first-round buckets of the retuned settings (same active documents in both runs):

Identical bucketsClueWeb gainHPLT gain
(14,9)(14,9)+33.3M+34.4M
(12,11)(12,11)+28.4M+24.3M
(10,12)(10,12)+25.6M+20.2M

The gain shrinks as the settings produce fewer collisions (445M → 348M colliding ClueWeb documents) but stays above 20M. Later rounds compute signatures only for our survivors, so they have no identical-bucket legacy counterpart; we will report them as an optional configuration with their cost (4.7×/4.0× the signature work).

Training value and costs (W2). We sampled ClueWeb22 texts (HPLT's were not kept) and checked them without MinHash:

  • Duplication. For 2,048 extra documents, exact character-20-gram Jaccard to the retained documents two collisions away has median 0.64 and never reaches 0.9; 8% have one at ≥0.75. Bucket partners (control): median 0.72.
  • Yield. +33.3B ± 5.6B GPT-2 tokens (+1.9%).
  • Quality. Paired with the document legacy kept from the same component, the extra documents score the same on the FineWeb-Edu classifier (+0.009 ± 0.010). Overall they score lower (1.12 vs 1.29), because many come from large components of templated pages (listings, product and company pages), where legacy keeps one document regardless of content.
  • Costs. End to end, 4:35 → 5:49 on ClueWeb and 23:59 → 22:06 on HPLT; Stage 3 peak 128.7 → 151.6 GiB and 713.1 → 479.6 GiB. Bucket files take 72 → 27 GB and 508 → 239 GB (12/21 GB after Stage 2.5). The largest temporary files, Stage 1's signatures (about 3/8 TB), are written by both methods. On ClueWeb, the extra tokens cost 27% more time and 18% more peak memory; on HPLT, our pipeline is 8% faster and needs 33% less.

A training run would test the criterion (b,r)(b,r), which binds legacy equally; it is our next step.

Solver, bounds and Stage 2.5 (W3). We agree that the selection solver and the upper bounds come from Wu & Cong (2026). Replacing the solver with a plain maximal scan in document-ID order still keeps 26.8M/24.9M more documents than legacy; the solver adds 6.5M/9.5M. Without Stage 2.5, ClueWeb Stage 3 peaks at 279.5 GiB instead of 151.6 GiB, takes 5:35 instead of 2:24, and keeps 399,100 fewer documents. On HPLT, Stage 2.5 cuts Stage 3's input from 25.2B to 2.25B incidences; without it, Stage 3 would need about 2.3 TiB by linear extrapolation, more than our 2.2 TiB nodes. Stage 2.5 itself takes 59 min / 11.3 h on 14 nodes. Most of the gain therefore comes from applying the rule in DataTrove, and Stage 2.5 is what fits HPLT on one node.

Revisions. The identical-bucket gain as the headline, with Table 1 corrected; the four-seed results as an optional configuration with their cost; these measurements and the Stage 2.5 ablation in the appendix.

Reviewer_AxaDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the problem of excessive removal caused by traditional deduplication methods that only retain one document for the same connected component. Therefore, author changed the retention rule to a maximum of one document per collision bucket based on the LSH-MinHash method in the style of DataTrove. Then author optimized the performance of the method through redundant bucket pruning by band partitioning, hierarchical greedy selection, and optional multi seed screening. Experiments on billions of web documents have shown that compared to traditional methods, our approach can preserve tens of millions of more documents. In addition, this article also provides a mathematical upper limit estimate for the number of documents that meet the same constraints.

Critical strengths

The research question is interesting and practically relevant. The paper highlights that if A and B collide in one band and B and C collide in another, A and C need not collide in any band. That is to say, conflicts in documents cannot be transmitted through conflict relationships. This paper also provides a simple solution.

The paper provides experiments on billions of web documents. The paper evaluates the method on web corpora with billions of documents. Experimental results have shown that the method proposed in this paper is effective in avoiding the problem of excessive removal in large-scale online corpora. And the subsequent design will help solve the memory limitation problem in practical applications.

Critical weaknesses

The innovation of this paper is weak, the key issues and most of the optimization mechanisms are basic follow Wu and Cong (2026).However, the lack of a matched comparison with a simple unlayered maximal greedy baseline makes it difficult to assess the added value of the layered method.

Component ablations and resource cost comparisons remain insufficient. This paper only tests intra layer ordering, and the multi-seed runs change both the seed count and the banding parameters. Therefore, the benefits and costs of pruning, layering, and adding seeds still cannot be quantified.

The evaluation of system costs is incomplete. The benefits of Stage 2.5 need to be measured by the full process cost. Table 1 reports the peak memory of a single node Stage 3. Sharding pruning itself requires cross band scanning, multiple rounds of filtering, and recalculating signatures and reading/writing intermediate files. It is recommended to compare the opening and closing of Stage 2.5 under the same input, signature, and node configuration, and report the time consumption, end-to-end time consumption, total CPU hours, read and write volume, and temporary storage peak for each stage. These results indicate how much additional computation and I/O cost is required for pruning when single node memory is limited.

Questions for authors

Under the same collision buckets and preprocessing, how much does each component contribute to document retention? In particular, how does layered selection compare with a simple unlayered maximal greedy baseline, and can the effects of parameter retuning and additional seeds be evaluated separately?

What are the end-to-end runtime, total CPU hours, I/O volume, and temporary storage requirements compared with the traditional method? How does enabling or disabling Stage 2.5 affect these costs and peak memory use?

What are the quality and diversity of the additional retained documents? Is there evidence that they provide useful new content rather than more noise or redundant text, and could this be tested in a small-scale training experiment under a fixed compute budget?

2 comments
AuthorsOpenReview ↗

**Response to Reviewer AxaD**

We thank the reviewer. We ran the requested matched ablations and measured full-pipeline costs; they change how we present the paper. The extra-document study is detailed in our response to Reviewer uWPM.

Matched ablation (W1, W2, Q1). Same pruned (14,9;1)(14,9;1) buckets, one node per run; an independent checker confirmed every output feasible and maximal.

Stage 3 ruleClueWeb keptTime / peakHPLT keptTime / peak
Legacy (connected components)78.711M— / 129 GiB737.009M— / 713 GiB
Maximal scan, document-ID order105.511M48 min / 156 GiB761.889M3.6 h / 570 GiB
Maximal scan, ascending degree111.856M62 min / 160 GiB771.322M3.1 h / 555 GiB
Layered greedy (paper)111.993M73 min / 152 GiB771.381M2.3 h / 480 GiB
Upper bound UpunctU_{\rm punct}112.639M—772.416M—

Time: selection after loading; peak: Stage 3 MaxRSS; our rules read the same 12/21 GB of pruned buckets (legacy: 72/508 GB of pairs). The rule with the simplest scan keeps 26.8M/24.9M more than legacy, degree order adds 6.3M/9.4M, and layering only 136,696/58,974. We agree that chain over-merging is known and that the reductions, layered greedy and bounds follow Wu & Cong (2026); we will make degree-ordered greedy the baseline and layering optional. Without Stage 2.5, ClueWeb Stage 3 peaks at 279.5 GiB instead of 151.6, takes 5:35 instead of 2:24 and keeps 399,100 fewer; end to end, 8:02 instead of 5:49, with 6% fewer node-hours. HPLT would need about 2.3 TiB by extrapolation, more than our 2.2 TiB nodes.

Retuning vs. seeds (W2, Q1). ClueWeb survivors (M); each first round uses identical buckets for both rules; P(s)P(s) is the collision probability at Jaccard ss:

SettingP(0.8)P(0.5)LegacyOurs
(14,9)×10.8670.0271,253.81,287.1
(12,11)×10.6600.0061,311.51,339.9
(12,11)×20.8840.012—1,300
(10,12)×10.5090.0021,340.21,365.8
(10,12)×30.8820.007—1,306
(12,14)×40.8850.003—1,319

Retuning alone raises retention for both rules but loses recall; the rule still adds 28.4M/25.6M (HPLT: 24.3M/20.2M). Added seeds restore recall at 0.8 and remove more. Four seeds keep 32M more than one seed with ninefold fewer collisions at 0.5, but recall at 0.75 also falls (0.665 → 0.578), so part of that gain is a looser threshold. Later rounds exist only for our survivors, so we will report multi-seed as retuned evidence, not as the rule's gain.

Costs (W3, Q2). Same input; 64/28/14/1/128 nodes for Stages 1/2/2.5/3/4 (Stage 2.5: 12 for ×4), 128 logical CPUs each; "×4" is the measured four-round pipeline:

ClueWeb legacyoursours ×4HPLT legacyoursours ×4
End to end, h:mm4:355:4910:5323:5922:0629:11
CPU-hours used3,2843,27713,5895,8796,03920,283
Node-hours allocated1571846203064521,047
Peak per node, GiB128.7151.690.1713.1482.3504.8
Disk reads / writes, TB51.5 / 6.748.1 / 6.5229 / 25.064.8 / 14.565.5 / 13.6265 / 45.8
Bucket files, GB (after 2.5)72.227.0 (12.3)19.0 (8.6)507.6238.8 (21.1)198.9 (20.9)

With one seed, CPU time is nearly unchanged. Node-hours rise 17%/47% because Stage 2.5 holds 14 nodes for 1.0/11.3 h while using under one core per node (it reads 0.4/3.6 TB); its 482.3 GiB also sets HPLT's per-node peak (Stage 3 alone: 479.6). Signatures (about 3/8 TB per round, either rule) are the largest temporary files. Four seeds cost 4.1×/3.4× legacy's CPU time, almost all in Stages 1, 2 and 4 rerunning on survivors. Correction: Table 1's legacy MaxRSS values came from other runs; on identical buckets our Stage 3 needs 18% more peak memory on ClueWeb and 33% less on HPLT, and four seeds 30%/29% less (not 48.36%/5.70%).

Per component, then: bucket-feasible selection in DataTrove gives most of the gain at legacy's CPU time; Stage 2.5 is needed for HPLT and costs 1.0/11.3 h on 14 nodes; four seeds add 32M/31M at 4.1×/3.4× the CPU time; layering adds little.

Extra documents (Q3). By exact, non-MinHash Jaccard they are distinct (median 0.64 to retained documents two collisions away, none ≥0.9, 8% ≥0.75), and they add 33.3B ± 5.6B GPT-2 tokens (+1.9%). Against the document legacy kept from the same component they score the same on FineWeb-Edu (+0.009 ± 0.010). Overall they score lower (1.12 vs 1.29) and span fewer hosts (6,805 vs 7,683 per 10,240), because many come from large components of templated pages. We have not run a fixed-compute training comparison; we plan equal-token runs on both outputs.

Revisions. Corrected Table 1 and every claim based on it; these tables in the appendix; degree-ordered greedy as the baseline; a rewritten §6.3.

Thank you for providing supplementary experiments and corrections. Your supplementary experiment can largely demonstrate the additional document retention rate and memory optimization brought by layered greedy models and multi-seed designs during actual operation. But I am still concerned about the innovation of this paper , as it focuses more on engineering optimization and lacks deeper thinking. Thus, I will maintain my original score of 2 (Weak Reject)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.