Summary (Overview)

• Core contribution: The paper proposes a scalable subdocument deduplication framework that explicitly decouples duplicate detection from copy retention for large language model pretraining corpora.
• Key innovation: A frequency- and length-aware retention function that adaptively allocates copy budgets per duplicate group, retaining more copies of low-frequency/short repetitions while aggressively deleting high-frequency/long ones.
• Detection approach: Uses natural-boundary segmentation, normalized exact hashing, and distributed aggregation to achieve global duplicate counting independent of shard placement—overcoming the shard-sensitivity of suffix-array methods.
• Empirical results: On FineWeb-Edu, the method achieves the best overall score (52.92 without document-level dedup; 52.90 with it), outperforming baselines including Doc-MinHash (51.51), Suffix-Array (52.79), and Keep-One (52.14). On a code-containing web corpus, it improves average performance from 37.98 to 41.40.
• Key finding: Explicit copy-retention control matters—Keep-One, which uses identical detection but uniform retention, underperforms the proposed adaptive policy.

---

Introduction and Theoretical Foundation

Background and Motivation

Large-scale pretraining corpora contain substantial duplicate content (web templates, announcements, quoted text, copied code, versioned content). Duplication wastes compute and degrades model performance disproportionately (Hernandez et al., 2022). While document-level deduplication is standard, it fails to handle subdocument-level redundancy—repeated content covering only part of a document.

Three Central Questions

1. How should duplicate content be defined and detected? (detection unit and matching criterion)
2. How can detection scale to large corpora?
3. How many copies of each duplicate should be retained?

Limitations of Existing Approaches

Empirical Observations (Section 3.1)

Analysis of duplicate chunk characteristics after document-level MinHash deduplication reveals:

• Long-tailed frequency distribution: Unique chunks (C=1) account for 54.2% (line-level) and 42.9% (sentence-level) of text; chunks with C>20 still account for 11.1% and 16.7%.
• Content differences by frequency: High-frequency duplicates are predominantly templates, navigation elements, boilerplate; low-frequency duplicates include reasonable quotations and legitimate content reuse.
• Length as a signal: Longer duplicated chunks more likely reflect template reuse or direct copying; short repeated segments may be legitimate linguistic reuse.

Implicit Retention Behavior of Shard-Local Deduplication (Section 3.2)

Under random sharding with singleton-only retention (a copy retained only if it's the sole occurrence in its shard), the expected retained count for a group with C copies across N shards is:

$$g_N(C) = C \left(1 - \frac{1}{N}\right)^{C-1}$$

The expected retention ratio is:

$$r_N(C) = \frac{g_N(C)}{C} = \left(1 - \frac{1}{N}\right)^{C-1}$$

This curve decreases monotonically with frequency C, exhibiting the desired frequency-dependent behavior—but it is coupled to physical sharding. The paper abstracts this curve and reinterprets N as a tunable hyperparameter.

---

Methodology

Overall Pipeline (5 Stages)

1. Segmentation: Documents are split into chunks at natural boundaries (paragraphs, lines, sentences). Chunks shorter than τ_seg = 32 characters are merged with subsequent chunks. Code documents preserve structural integrity (Markdown blocks, brace-delimited structures treated as indivisible).

2. Text Normalization: For natural language, numeric expressions (dates, prices, statistics) are replaced with placeholders. For code, no normalization is applied (norm(x) = x) to avoid grouping semantically distinct code. Chunks with identical normalized text form a duplicate group.

3. Global Duplicate Counting: Hash-based distributed aggregation:

   • h(x) = H(norm(x)) where H is a content hash function
   • Global frequency: $C(z) = \sum_{x \in X(D)} \mathbb{1}[\text{norm}(x) = z]$
   • Implemented via shuffle-and-aggregate (MapReduce/Spark)

4. Reconstruction: Join duplicate-group metadata back to chunks; restore document order and context.

5. Retention-Guided Deletion: Apply retention function T(C, L), then group consecutive candidate deletion chunks into maximal runs; delete a run only if:

$$\sum_{j=s}^{t} \ell(x_j) \geq \tau_{del}$$

(τ_del = 100 characters), reducing fragmentation.

Frequency- and Length-Aware Retention Function

Base budget (frequency-aware, derived from shard-local analysis):

$$g_N(C) = C \left(1 - \frac{1}{N}\right)^{C-1}$$

N is reinterpreted as a hyperparameter controlling compression strength (larger N = slower decay = more conservative).

Length adjustment (truncated linear):

$$\alpha(L) = \max\left(0, 1 - \frac{L}{L_0}\right)$$

where L is the normalized chunk length in characters and L₀ = 512 is a reference length controlling decay rate.

Joint retention budget:

$$T(C, L) = \left\lceil 1 + \left(g_N(C) - 1\right) \alpha(L) \right\rceil$$

Key properties:

• 1 ≤ T(C, L) ≤ C for all C ≥ 1, N > 1
• When L < L₀: budget decreases from g_N(C) toward 1 as L increases
• When L ≥ L₀: T(C, L) = 1 (strongest compression)
• The additive anchor at 1 guarantees at least one copy is retained
• Ceiling operation ensures conservative integer budgets

Initial retention decision for occurrence o with rank(o) ∈ {1, ..., C}:

$$\text{keep}_0(o) = \mathbb{1}[\text{rank}(o) \leq T(C, L)]$$

---

Empirical Validation / Results

Experimental Setup

• Model: Hy-MT2-30B-A3B (30B parameters, active 3B)
• Training: 36,000 steps × 8.192M tokens/step = 294.9B tokens total
• Hyperparameters: τ_seg = 32, τ_del = 100, L₀ = 512, N = 100/3
• Corpora: FineWeb-Edu (6.28T tokens) and a code-containing web corpus (561.53B tokens from Common Crawl)

Main Results on FineWeb-Edu (Table 1)

Key comparisons:

• Both Ours variants improve over FineWeb-Edu by ~1.0 point and exceed Suffix-Array by 0.11–0.13 points
• Ours (Subdoc-only) leads on GSM8K, MMLU, and CMMLU; Ours leads on TriviaQA, HellaSwag, PIQA, MATH
• Keep-One vs. Ours (controlled comparison isolating retention policy): identical detection, but Ours outperforms by 0.76–0.78 points—direct evidence that adaptive retention beats uniform keep-one

Results on Code-Containing Webpages (Table 2)

Improvements across all five benchmarks, including non-code ARC-Challenge, indicating no trade-off of general capability.

Corpus Reduction Analysis (Table 3)

Critical insight: Performance is not determined by amount of data removed. Keep-One removes the most data but performs worst; Ours achieves best performance with intermediate retention.

Retention Behavior (Figure 4)

• For L < L₀: retention budget peaks around C ≈ 33, then decreases toward 1
• Longer chunks receive smaller budgets at the same frequency
• Retained fraction decreases monotonically with frequency
• L = L₀ = 512 yields one-copy retention across all frequencies

---

Theoretical and Practical Implications

Theoretical Contributions

1. Formal analysis of shard-local retention: The paper provides a rigorous probabilistic analysis showing that random shard-local deduplication induces a specific expected retention curve r_N(C) = (1 - 1/N)^(C-1), making explicit the hidden coupling between data partitioning and deduplication outcomes.

2. Decoupling detection from retention: By separating the what (detection) from the how many (retention), the framework enables independent optimization of each component—a conceptual advance over monolithic pipelines.

3. Frequency- and length-aware retention as a principled policy: The retention function formalizes the intuition that high-frequency and long repetitions are more likely to be templated/low-information content, while low-frequency and short repetitions may be legitimate reuse.

Practical Implications

• Scalability: The hash-based detection stage uses standard distributed aggregation (MapReduce/Spark), making it directly applicable at web scale without the computational cost of global suffix arrays.
• Controllability: N and L₀ provide interpretable knobs for compression strength, decoupled from physical infrastructure.
• Code-aware handling: Preserving code structure during segmentation and skipping normalization for code chunks are important practical considerations for code-heavy corpora.
• Fragmentation control: The coherence-preserving deletion rule (τ_del threshold on contiguous runs) prevents excessive document fragmentation.

---

Conclusion

Main Takeaways

1. Subdocument deduplication is more effective than document-level alone, but how many copies to retain is as important as what to detect.
2. Explicit frequency- and length-aware retention policies outperform both uniform keep-one policies and implicitly-sharded suffix-array approaches.
3. The framework achieves the best overall performance on FineWeb-Edu (52.92 average) and consistent gains on code-containing web corpora (41.40 vs. 37.98 baseline).

Future Directions

The paper's conclusion is brief, but implied future work includes:

• Exploring alternative retention functions beyond the truncated linear form
• Applying the framework to other modalities or specialized corpora
• Investigating interactions between subdocument deduplication and other data processing stages (e.g., quality filtering, curriculum strategies)
• Further analysis of how retention budgets affect specific capabilities (e.g., memorization vs. generalization trade-offs)