# Scalable Frequency- and Length-Aware Subdocument Deduplication for Large Language Model Pretraining

> Subdocument deduplication with a frequency- and length-aware copy-retention policy outperforms uniform keep-one and shard-sensitive suffix-array methods for LLM pretraining, achieving the best scores on FineWeb-Edu and code-heavy corpora.

- **Source:** [arXiv](https://arxiv.org/abs/2608.03089)
- **Published:** 2026-10-03
- **Permalink:** https://picx.dev/p/8uEvol
- **Whiteboard:** https://picx.dev/p/8uEvol/image

## Summary

## 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

| Approach | Strength | Limitation |
|----------|----------|------------|
| **Suffix-array (shard-local)** | Flexible variable-length substring matching | Cross-shard duplicates undetected; retention behavior coupled to sharding configuration |
| **Hash-based (global)** | Global exact counting via distributed aggregation | Fixed retention policies (keep-one, keep-*k*) cannot adapt to heterogeneous repetition patterns |

### 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)

| Method | Knowledge (NQ/TriviaQA) | Reasoning (HSwag/PIQA) | Mathematics (GSM8K/MATH) | Comprehensive (MMLU/CMMLU) | **Average** |
|--------|------------------------|------------------------|--------------------------|----------------------------|-------------|
| FineWeb-Edu | 25.87/78.75 | 76.83/81.12 | 32.17/10.61 | 58.67/51.07 | 51.89 |
| Doc-MinHash | 27.65/77.92 | 76.07/80.79 | 29.74/10.71 | 57.71/51.47 | 51.51 |
| Suffix-Array | 28.67/78.06 | 77.37/81.07 | 33.51/10.70 | 60.03/52.89 | 52.79 |
| Keep-One | 24.32/77.36 | 77.10/81.12 | 34.42/9.85 | 60.23/52.68 | 52.14 |
| **Ours (Subdoc-only)** | 27.01/78.06 | 77.03/80.63 | **36.19**/9.90 | **60.78**/**53.77** | **52.92** |
| **Ours** | 28.14/**78.89** | **77.73**/**81.34** | 33.51/**10.90** | 59.43/53.24 | 52.90 |

**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)

| Method | BigCodeBench | HumanEval+ | LiveCodeBench | FullStackBench-en | ARC-Challenge | **Average** |
|--------|-------------|------------|---------------|-------------------|---------------|-------------|
| No-Dedup | 36.93 | 51.53 | 12.99 | 35.29 | 53.18 | 37.98 |
| **Ours** | 39.30 (↑2.37) | 57.06 (↑5.53) | 14.72 (↑1.73) | 37.37 (↑2.08) | 58.53 (↑5.35) | **41.40** (↑3.42) |

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

### Corpus Reduction Analysis (Table 3)

| Method | Raw Tokens | After Doc-Level | After Subdoc-Level | Retention Ratio |
|--------|-----------|-----------------|--------------------|-----------------| 
| Suffix-Array (FineWeb-Edu) | 6.28T | 1.01T (16.08%) | 937.41B | 14.93% |
| Keep-One (FineWeb-Edu) | 6.28T | 1.01T (16.08%) | 799.55B | 12.73% |
| **Ours** (FineWeb-Edu) | 6.28T | 1.01T (16.08%) | 905.36B | 14.42% |
| **Ours** (Code Web) | 561.53B | – | 502.23B | 89.44% |

**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)

---

_Markdown view of https://picx.dev/p/8uEvol, served by PicX — AI-generated visual whiteboard summaries of research papers._