🤖 Harold's Notes

Search

SearchSearch

Semantic dedupe

Sep 12, 202627 min read

Semantic Deduplication for LLM Pretraining

Beginner Introduction

Imagine studying for an exam with a massive textbook where 30% of the content is the same paragraph copied with tiny variations (different city names, different product names, but identical structure). You’d waste hours re-reading the same ideas instead of learning new things. That’s exactly the problem with web-scale training data for LLMs.

When we scrape the internet to build training corpora (CommonCrawl, C4, LAION), we get billions of documents. Many are near-duplicates: not identical copies (those are easy to catch with hashing), but semantically equivalent content:

  • Thousands of hotel booking pages from the same template, differing only by hotel name
  • Product listings that differ only by product name/price
  • News articles syndicated across hundreds of outlets with minor rewording

Traditional “exact” deduplication (MinHash/LSH) catches documents that share large chunks of identical text but completely misses semantic duplicates — documents that say the same thing in slightly different words or structures.

Semantic deduplication uses neural network embeddings to catch these. The core idea:

  1. Turn every document into a dense vector (embedding) using a pretrained model
  2. Documents with very similar embeddings are semantically similar
  3. Remove or downweight the redundant ones

The payoff is enormous: you can often remove 30-50% of your data with no performance loss — or even better performance — halving your training cost.

The Four Key Papers

PaperYearKey Idea
SemDeDup2023The foundational method: cluster embeddings, remove near-duplicates within clusters
D42023Extends SemDeDup by adding a “diversification” step after deduplication
SoftDedup2024Replaces hard removal with soft reweighting using cheap n-gram models
FineWeb2024Large-scale practical report from HuggingFace on dedup at 15T+ token scale

Paper 1: SemDeDup — The Foundation

Full Title: SemDeDup: Data-efficient learning at web-scale through semantic deduplication Authors: Amro Abbas, Kushal Tirumala, Daniel Simig, Surya Ganguli, Ari S. Morcos (Meta AI / Stanford) arXiv: 2303.09540 | Code: github.com/facebookresearch/SemDeDup

Abstract

Progress in machine learning has been driven in large part by massive increases in data. However, large web-scale datasets such as LAION are largely uncurated beyond searches for exact duplicates, potentially leaving much redundancy. Here, we introduce SemDeDup, a method which leverages embeddings from pre-trained models to identify and remove semantic duplicates: data pairs which are semantically similar, but not exactly identical. Removing semantic duplicates preserves performance and speeds up learning. Analyzing a subset of LAION, we show that SemDeDup can remove 50% of the data with minimal performance loss, effectively halving training time. Moreover, performance increases out of distribution. Also, analyzing language models trained on C4, a partially curated dataset, we show that SemDeDup improves over prior approaches while providing efficiency gains.

The Algorithm

+-------------------------------------------------------------+
|  SemDeDup Pipeline                                           |
|                                                              |
|  1. Embed all documents with pretrained model (CLIP/OPT)     |
|  2. K-Means cluster the embeddings (K=50,000)               |
|  3. Sort each cluster by distance to centroid                |
|  4. Within each cluster, compute pairwise cosine sim         |
|  5. Flag points where max_sim > (1 - eps) for removal       |
|  6. Keep the "harder" (far-from-centroid) example            |
+-------------------------------------------------------------+

Step-by-Step Implementation

Step 1: Compute Embeddings

import numpy as np
 
# For vision: use CLIP embeddings (512-dim)
# For text: use OPT/sentence-transformer embeddings
# Store as memory-mapped numpy array for efficiency
embeddings = np.memmap(
    "embeddings.mmap",
    dtype="float32",
    mode="w+",
    shape=(dataset_size, 512)
)
# Fill with your model's embeddings...

Step 2: K-Means Clustering with FAISS

import faiss
 
# SemDeDup uses spherical K-Means (cosine distance)
d = 512   # embedding dimension
K = 50000 # number of clusters
 
kmeans = faiss.Kmeans(
    d, K,
    niter=100,
    verbose=True,
    gpu=True,           # use GPU acceleration
    spherical=True,     # cosine distance (normalize to unit sphere)
    seed=1234
)
kmeans.train(embeddings)
 
# Assign every point to its nearest cluster
distances, cluster_assignments = kmeans.index.search(embeddings, 1)

Step 3: Sort Clusters by Distance to Centroid

# For each cluster, sort documents by distance to centroid
# "keep_hard" = keep examples FARTHEST from centroid (default, best)
for cluster_id in range(K):
    mask = cluster_assignments.flatten() == cluster_id
    cluster_indices = np.where(mask)[0]
    cluster_distances = distances[mask].flatten()
 
    # Sort DESCENDING: hardest (farthest) examples first
    sorted_order = np.argsort(-cluster_distances)
    sorted_cluster = cluster_indices[sorted_order]
    np.save(f"sorted_clusters/cluster_{cluster_id}.npy", sorted_cluster)

Step 4 & 5: Identify Semantic Duplicates (Core Logic)

import torch
 
def semdedup_cluster(embeddings_cluster, eps_list=[0.06, 0.07]):
    """
    Find semantic duplicates within a single cluster.
 
    Args:
        embeddings_cluster: (N, D) tensor of embeddings for this cluster
        eps_list: list of epsilon thresholds to evaluate
 
    Returns:
        dict mapping eps -> boolean mask (True = duplicate to remove)
    """
    # Compute full pairwise cosine similarity matrix
    # (embeddings should be L2-normalized for this to be cosine sim)
    sim_matrix = embeddings_cluster @ embeddings_cluster.T  # (N, N)
    sim_matrix.fill_diagonal_(0.0)  # ignore self-similarity
 
    # Take UPPER TRIANGULAR only
    # This ensures we only compare each pair once, and
    # because the cluster is sorted (hard->easy), the "later"
    # (easier/more redundant) example gets flagged
    triu = torch.triu(sim_matrix, diagonal=1)
 
    # For each point: what's the max similarity to any EARLIER point?
    M = torch.max(triu, dim=0)[0]  # shape: (N,)
 
    # Flag duplicates at each epsilon threshold
    results = {}
    for eps in eps_list:
        # If max_sim > (1 - eps), this point is a semantic duplicate
        results[eps] = (M > 1 - eps)
 
    return results
 
# Example usage
cluster_embs = torch.tensor(embeddings[sorted_cluster_indices])
cluster_embs = cluster_embs / cluster_embs.norm(dim=1, keepdim=True)  # L2 normalize
duplicate_flags = semdedup_cluster(cluster_embs, eps_list=[0.03, 0.06, 0.07, 0.1])

Epsilon Controls How Much Gets Removed

eps~Data RetainedAggressiveness
0.001~80%Very conservative (only exact semantic dupes)
0.03~72%Light dedup
0.07~63%Moderate
0.124~50%Aggressive — sweet spot for LAION
0.26~20%Very aggressive

Key Hyperparameters

HyperparameterValue / ChoiceNotes
Embedding modelOA-CLIP (ViT-B/32 or B/16)Pre-trained, frozen; used only for computing embeddings
Embedding dimension512Standard CLIP embedding size
Number of K-Means clusters50,000Balances granularity vs. compute; clustering is done with FAISS
K-Means iterations100Standard convergence setting
K-Means distanceCosine (spherical K-Means)Kmeans_with_cos_dist: True — normalizes to unit sphere
Similarity metric for dedupCosine similarityComputed as dot product of normalized embeddings
Epsilon (eps)Varies: 0.001 to 0.26Lower = more aggressive pruning; ~0.06-0.07 for 50% retention
Which example to keep”hard” (default)Keep the example farthest from cluster centroid; alternatives: “easy”, “random”
Largest cluster size10,000,000Clusters larger than this are split into sub-chunks for memory management
Data storagenumpy memmap (float32)Enables efficient I/O for web-scale datasets
ParallelizationSLURM + submititDesigned for multi-node HPC clusters

Key Results

  • LAION (vision): Remove 50% of data → minimal ImageNet accuracy loss, improved OOD performance
  • C4 (text): Consistent efficiency gains on 125M and 1.3B models
  • Which to keep: “Hard” examples (farthest from centroid) > “Random” > “Easy”

Why It Works

The key insight is that keeping hard examples preserves diversity. Examples near cluster centroids tend to be prototypical/redundant (the “average” of their cluster). Examples far from centroids are unique, edge-case content that carries more information per token.

Critical Design Choices

  1. Clustering before pairwise comparison: Without clustering, computing all-pairs similarity for hundreds of millions of examples is infeasible (O(n^2)). K-Means reduces the problem to within-cluster comparisons only.
  2. Keeping “hard” examples: Farthest from centroid = atypical = more unique information. Validated experimentally, especially for OOD performance.
  3. Upper triangular matrix trick: By sorting examples by difficulty and using the upper triangular portion, the algorithm deterministically removes later (easier/more redundant) examples in favor of earlier (harder) ones.
  4. Pre-trained embeddings, not task-specific: Uses general-purpose pretrained model (CLIP), making it task-agnostic.
  5. Complementary to exact dedup: Designed to run after exact deduplication. Catches “soft” duplicates that hash-based methods miss.

Paper 2: D4 — Adding Diversification

Full Title: D4: Improving LLM Pretraining via Document De-Duplication and Diversification Authors: Kushal Tirumala*, Daniel Simig*, Armen Aghajanyan, Ari S. Morcos (Meta AI) arXiv: 2308.12284 | No public code (but uses SemDeDup codebase)

Abstract

Over recent years, an increasing amount of compute and data has been poured into training large language models (LLMs), usually by doing one-pass learning on as many tokens as possible randomly selected from large-scale web corpora. While training on ever-larger portions of the internet leads to consistent performance improvements, the size of these improvements diminishes with scale, and there has been little work exploring the effect of data selection on pre-training and downstream performance beyond simple de-duplication methods such as MinHash. Here, we show that careful data selection (on top of de-duplicated data) via pre-trained model embeddings can speed up training (20% efficiency gains) and improves average downstream accuracy on 16 NLP tasks (up to 2%) at the 6.7B model scale. Furthermore, we show that repeating data intelligently consistently outperforms baseline training (while repeating random data performs worse than baseline training).

The Core Insight

SemDeDup removes duplicates but doesn’t actively diversify. D4 asks: after cleaning up duplicates, can we additionally select the most diverse subset?

The answer is yes, using a two-stage pipeline:

+--------------------------------------------------------------+
|  D4 = SemDeDup -> Re-Cluster -> SSL Prototypes                |
|                                                               |
|  Stage 1: SemDeDup (dedup)                                   |
|    - Cluster -> remove near-duplicates within clusters         |
|    - This removes "duplicate-driven clusters"                 |
|                                                               |
|  * CRITICAL: Re-cluster the cleaned data *                    |
|    - SemDeDup cleaned up the corrupt clusters                 |
|    - Re-clustering now gives MUCH better topic clusters       |
|                                                               |
|  Stage 2: SSL Prototypes (diversify)                         |
|    - Within each new cluster, REMOVE points closest to        |
|      centroid (most prototypical/redundant)                   |
|    - KEEP points farthest from centroid (most diverse)        |
+--------------------------------------------------------------+

What Are “Duplicate-Driven Clusters”?

The authors embedded web documents, clustered them, and manually inspected the resulting clusters. They discovered extremely dense clusters filled with templated/near-duplicate content that MinHash failed to remove:

  • Nike shoe advertisements auto-generated from a template with minor modifications
  • USGS topographic map pages with identical boilerplate
  • Hotel booking site pages with identical structure but different hotel names
  • University info pages with templated text

These corrupt k-means clustering by wasting cluster assignments on redundant text rather than topically coherent groupings. This is the key motivation for D4.

Complete Implementation

import faiss
import numpy as np
import torch
 
def d4_pipeline(
    embeddings,          # (N, D) numpy array, L2-normalized
    R_dedup=0.75,        # SemDeDup keeps 75% of data
    R_proto=0.33,        # SSL Prototypes keeps 33% of remaining
    K=11000,             # number of K-Means clusters
    semdedup_eps=0.07,   # SemDeDup epsilon threshold
):
    """
    Full D4 pipeline: Deduplication + Diversification
 
    Overall selection ratio: R = R_dedup * R_proto ~ 0.25 (keep 25%)
    """
    N, D = embeddings.shape
 
    # ============ STAGE 1: SemDeDup ============
    print("Stage 1: Initial clustering for SemDeDup...")
    kmeans1 = faiss.Kmeans(D, K, niter=20, spherical=True, verbose=True)
 
    # Subsample for centroid calculation if dataset is huge
    sample_size = min(N, 100_000_000)
    sample_idx = np.random.choice(N, sample_size, replace=False)
    kmeans1.train(embeddings[sample_idx])
 
    # Assign all points to clusters
    distances1, assignments1 = kmeans1.index.search(embeddings, 1)
    assignments1 = assignments1.flatten()
    distances1 = distances1.flatten()
 
    # Run SemDeDup within each cluster
    keep_mask = np.ones(N, dtype=bool)
    for cluster_id in range(K):
        cluster_idx = np.where(assignments1 == cluster_id)[0]
        if len(cluster_idx) <= 1:
            continue
 
        # Sort by distance to centroid (descending = hard first)
        cluster_dists = distances1[cluster_idx]
        sort_order = np.argsort(-cluster_dists)
        cluster_idx_sorted = cluster_idx[sort_order]
 
        # Get embeddings for this cluster
        cluster_embs = torch.tensor(embeddings[cluster_idx_sorted])
 
        # Pairwise cosine similarity (upper triangular)
        sim = cluster_embs @ cluster_embs.T
        sim.fill_diagonal_(0.0)
        triu = torch.triu(sim, diagonal=1)
        M = torch.max(triu, dim=0)[0]
 
        # Flag duplicates
        duplicates = (M > 1 - semdedup_eps).numpy()
        keep_mask[cluster_idx_sorted[duplicates]] = False
 
    # Surviving indices after SemDeDup
    deduped_idx = np.where(keep_mask)[0]
    print(f"SemDeDup: {N} -> {len(deduped_idx)} ({len(deduped_idx)/N:.1%} kept)")
 
    # ============ CRITICAL: RE-CLUSTER ============
    print("Re-clustering cleaned data...")
    embeddings_clean = embeddings[deduped_idx]
    kmeans2 = faiss.Kmeans(D, K, niter=20, spherical=True, verbose=True)
 
    sample_size2 = min(len(deduped_idx), 100_000_000)
    sample_idx2 = np.random.choice(len(deduped_idx), sample_size2, replace=False)
    kmeans2.train(embeddings_clean[sample_idx2])
 
    distances2, assignments2 = kmeans2.index.search(embeddings_clean, 1)
    assignments2 = assignments2.flatten()
    distances2 = distances2.flatten()
 
    # ============ STAGE 2: SSL Prototypes ============
    print("Stage 2: SSL Prototypes (diversification)...")
    final_idx = []
    for cluster_id in range(K):
        cluster_mask = assignments2 == cluster_id
        cluster_positions = np.where(cluster_mask)[0]
 
        if len(cluster_positions) == 0:
            continue
 
        # Sort by distance to centroid: KEEP the FARTHEST (most diverse)
        cluster_dists = distances2[cluster_positions]
        sort_order = np.argsort(-cluster_dists)  # descending
 
        # Keep top R_proto fraction (the furthest from centroid)
        n_keep = max(1, int(len(cluster_positions) * R_proto))
        kept = cluster_positions[sort_order[:n_keep]]
 
        # Map back to original dataset indices
        final_idx.extend(deduped_idx[kept].tolist())
 
    final_idx = np.array(final_idx)
    print(f"D4 Final: {N} -> {len(final_idx)} ({len(final_idx)/N:.1%} kept)")
 
    return final_idx

Why the Re-Clustering Step Matters

This is D4’s key contribution. Without re-clustering:

  • The initial clusters are corrupted by duplicate-driven clusters (thousands of templated pages in dense clusters)
  • SSL Prototypes would operate on these corrupt clusters and make poor decisions
  • With re-clustering after SemDeDup, the clusters become topically coherent

Embedding Choice Surprise

D4 uses a tiny OPT-125M model for embeddings (last-token, last-layer, 768-dim). Surprisingly:

  • At small training scales (125M), SentenceTransformers outperform OPT embeddings
  • At large training scales (6.7B), OPT embeddings outperform SentenceTransformers
  • Reason: SentenceTransformers (max context 256-384 tokens) disproportionately prune long documents due to truncation

Key Results

6.7B OPT model, 100B tokens, R = 0.25:

  • ~20% efficiency gains on validation perplexity (reaches same PPL 18-22% faster)
  • +2% improvement in average 0-shot downstream accuracy across 16 NLP tasks
  • Efficiency gains increase with model scale (projected ~22% for 175B models)

Landmark finding — smart data repetition beats single-epoch training:

StrategyTotal TokensSelected TokensEpochsNon-Web PPLInstruct PPL
Random (baseline)40B40B116.27 +/- 0.01214.19 +/- 0.003
Random (repeated)40B20B216.39 (+0.12)14.37 (+0.18)
D4 (repeated)40B20B216.10 (-0.17)13.85 (-0.34)

Randomly repeating data hurts; D4-selected repeated data beats fresh random data.

Key Hyperparameters

ParameterValueRationale
Embedding modelOPT 125M (last-token, last-layer, 768-dim)Outperforms SentenceTransformers at large training scales
Number of clusters K11,000~sqrt(100M sampled docs); robust to change (1K-1M tested)
K-Means iterations20Standard
R_dedup0.75Highest SemDeDup ratio that still improves PPL
R_total = R_dedup x R_proto0.25 (best)Select 25% from 4x oversized source
Model scales tested8M, 125M, 1.3B, 6.7B OPTEfficiency gains increase with scale

Conceptual Framework

  • SemDeDup = local deduplication (removes near-duplicates within clusters)
  • SSL Prototypes = global diversification (keeps diverse outliers, removes prototypical/redundant points)
  • D4 = SemDeDup → re-cluster → SSL Prototypes = local dedup + global diversification

The name “D4” stands for Document De-Duplication and Diversification.

Paper 3: SoftDedup — A Radically Different Approach

Full Title: SoftDedup: an Efficient Data Reweighting Method for Speeding Up Language Model Pre-training Authors: Nan He, Weichen Xiong, Hanwen Liu, Yi Liao, Lei Ding, Kai Zhang, Guohua Tang, Xiao Han, Wei Yang (Tencent AI Lab) arXiv: 2407.06654 | No public code

Abstract

The effectiveness of large language models (LLMs) is often hindered by duplicated data in their extensive pre-training datasets. Current approaches primarily focus on detecting and removing duplicates, which risks the loss of valuable information and neglects the varying degrees of duplication. To address this, we propose a soft deduplication method that maintains dataset integrity while selectively reducing the sampling weight of data with high commonness. Central to our approach is the concept of “data commonness”, a metric we introduce to quantify the degree of duplication by measuring the occurrence probabilities of samples using an n-gram model. Empirical analysis shows that this method significantly improves training efficiency, achieving comparable perplexity scores with at least a 26% reduction in required training steps. Additionally, it enhances average few-shot downstream accuracy by 1.77% when trained for an equivalent duration.

The Key Insight: Don’t Delete — Reweight

SemDeDup and D4 are hard deduplication — they permanently remove data. SoftDedup argues this is suboptimal:

  1. Information loss: deleted documents might contain unique information
  2. Threshold sensitivity: picking the right eps is arbitrary
  3. Binary thinking: duplication is a spectrum, not binary

Instead, SoftDedup reweights training samples: common/duplicated content gets lower sampling probability, rare/unique content gets higher probability. Nothing is deleted.

The “Data Commonness” Metric

The genius is using a cheap n-gram model instead of neural embeddings:

For each document x with tokens w_1, ..., w_N:

commonness(x) = geometric_mean(P(w_i | w_{i-3}, w_{i-2}, w_{i-1}))
              = exp(sum(log P(w_i | context)) / N)

High commonness = the document is made of common n-gram patterns
Low commonness  = the document contains rare/unique text

Formal Framework

Hard deduplication uses a binary indicator I(x) in {0, 1}:

L = sum_{x in D} I(x) * log P(x|theta)

Soft deduplication replaces this with a continuous weight W(x) in (0, 1):

L = sum_{x in D} W(x) * log P(x|theta)

where W(x) is proportional to 1/p(x)   (inverse of commonness)

Approximate Sampling at Scale

Assigning individual weights to billions of samples is impractical. The solution:

  1. Sort all M samples by ascending commonness
  2. Divide into K segments based on K quantiles
  3. Assign a single weight to each segment:
W_k = C * (1/p_k)^T

Where:

  • T is a temperature hyperparameter controlling weight disparity
  • C is a normalization constant ensuring all weights sum to 1

Complete Implementation

import subprocess
import math
import numpy as np
from tqdm import tqdm
 
# ==========================================
# Step 1: Train n-gram model with KenLM
# ==========================================
 
def train_ngram_model(corpus_file, output_model, order=4):
    """Train a KenLM n-gram model with Kneser-Ney smoothing."""
    subprocess.run([
        "lmplz",          # KenLM training binary
        "-o", str(order), # 4-gram
        "--prune", "0", "0", "0", "1",  # pruning thresholds
        "--text", corpus_file,
        "--arpa", output_model
    ], check=True)
 
    # Convert to binary for faster querying
    binary_model = output_model.replace(".arpa", ".binary")
    subprocess.run([
        "build_binary", output_model, binary_model
    ], check=True)
    return binary_model
 
 
# ==========================================
# Step 2: Score each document's commonness
# ==========================================
import kenlm
 
def compute_commonness(model_path, documents):
    """
    Compute data commonness for each document.
    Returns array of commonness scores (geometric mean of per-token probs).
    """
    model = kenlm.Model(model_path)
    scores = []
 
    for doc in tqdm(documents, desc="Scoring commonness"):
        # KenLM's score() returns log10 probability
        log10_prob = model.score(doc, bos=True, eos=True)
        num_tokens = len(doc.split()) + 1  # +1 for </s>
 
        # Geometric mean = 10^(log10_prob / N)
        commonness = 10 ** (log10_prob / num_tokens)
        scores.append(commonness)
 
    return np.array(scores)
 
 
# ==========================================
# Step 3: Partition and assign weights
# ==========================================
 
def softdedup_weights(commonness_scores, K=20, disparity=10.0):
    """
    Assign sampling weights based on commonness.
 
    Args:
        commonness_scores: array of commonness values per document
        K: number of quantile partitions
        disparity: max/min weight ratio (10 = 10x difference)
 
    Returns:
        weights: per-document sampling weights (sum to 1)
    """
    N = len(commonness_scores)
 
    # Sort by commonness (ascending = rarest first)
    sorted_idx = np.argsort(commonness_scores)
 
    # Divide into K equal segments
    segment_size = N // K
    segment_ids = np.zeros(N, dtype=int)
    for k in range(K):
        start = k * segment_size
        end = (k + 1) * segment_size if k < K - 1 else N
        segment_ids[sorted_idx[start:end]] = k
 
    # Get the median commonness of each segment
    segment_commonness = np.zeros(K)
    for k in range(K):
        mask = segment_ids == k
        segment_commonness[k] = np.median(commonness_scores[mask])
 
    # Compute temperature T to achieve desired disparity
    p_min = segment_commonness[0]   # rarest segment
    p_max = segment_commonness[-1]  # most common segment
    T = math.log(disparity) / math.log(p_max / p_min)
 
    # Compute raw weights per segment: W_k = (1/p_k)^T
    raw_weights = np.array([(1.0 / p) ** T for p in segment_commonness])
 
    # Normalize
    raw_weights /= raw_weights.sum()
 
    # Map segment weights back to per-document weights
    doc_weights = raw_weights[segment_ids]
    doc_weights /= doc_weights.sum()
 
    return doc_weights

Key Results (1.3B LLaMA-style model, 40B tokens)

SoftDedup vs. HardDedup (MinHashLSH) on RedPajama CC:

TaskBaselineHardDedupDeltaSoftDedupDelta
NQ Open (1-shot)4.134.60+0.475.37+1.24
SQuADv2 (1-shot)11.5112.95+1.4414.66+3.15
Trivia QA (1-shot)15.8917.71+1.8216.39+0.50
WebQuestions (1-shot)3.305.71+2.413.40+0.10
LAMBADA openai (1-shot)46.0743.64-2.4348.52+2.45
LAMBADA standard (1-shot)36.9137.65+0.7440.89+3.98
PIQA (1-shot)65.3466.00+0.6666.70+1.36
Social IQa (1-shot)88.0087.90-0.1089.60+1.60
WinoGrande (1-shot)52.8853.99+1.1154.38+1.50
HellaSwag (1-shot)34.9335.54+0.6136.51+1.58
ARC easy (2-shot)57.2457.79+0.5559.89+2.65
ARC challenge (2-shot)25.1725.09-0.0826.28+1.11
Average36.7837.38+0.6038.55+1.77

SoftDedup improves on all 12 tasks vs. baseline (avg +1.77%), while HardDedup only improves on 9/12 (avg +0.60%). SoftDedup is 3x more effective than hard deduplication.

The killer feature: SoftDedup works even on already-deduplicated data. On Falcon RefinedWeb (the most aggressively deduplicated public dataset), SoftDedup still provides 26-39% training step savings.

Cost: Nearly Free

ComponentCost
N-gram training (40B tokens)4 CPU cores x 5 hours
Commonness scoring4 CPU cores x 2 hours
Total~28 CPU-hours
Compare: GPU training budget>=930 V100 GPU-hours

Key Hyperparameters

ParameterValue/ChoiceRationale
N-gram order (n)4Empirically chosen
SmoothingKneser-NeyStandard choice for handling sparse n-gram counts
ToolkitKenLMEfficient, CPU-based n-gram LM training
Number of partitions (K)20 (default), tested 10/20/50/100More partitions → better downstream accuracy; diminishing returns
Temperature (T)Set for 10-fold max/min weight ratio10-fold disparity consistently best across all metrics
Commonness metricGeometric mean of n-gram probsEliminates length bias
TokenizerSame as pre-training LLM (LLaMA)Ensures consistency

SemDeDup vs SoftDedup

DimensionSemDeDupSoftDedup
ApproachHard removal (binary keep/discard)Soft reweighting (continuous weights)
Similarity metricEmbedding-based cosine similarityN-gram occurrence probability
RequiresPre-trained embedding model + GPUOnly CPU-based n-gram model
Data lossYes — removes samples entirelyNo — all samples retained
ThresholdRequires tuning a similarity cutoffNo threshold needed (continuous)
Computational costHigh (embedding all data, clustering, pairwise sim)Very low (n-gram training + scoring on CPU)
CapturesSemantic/meaning-level duplicationSurface-level / lexical redundancy
ComplementarityNot designed to stack with other methodsExplicitly designed as a complement

Paper 4: FineWeb — Dedup at Massive Scale

Full Title: The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale Authors: Guilherme Penedo, Hynek Kydlicek, Loubna Ben Allal, Anton Lozhkov, Margaret Mitchell, Colin Raffel, Leandro von Werra, Thomas Wolf (HuggingFace) arXiv: 2406.17557 | Code: github.com/huggingface/datatrove | Dataset: hf.co/datasets/HuggingFaceFW/fineweb

What FineWeb Is

FineWeb is a 15 trillion token English web dataset from 96 CommonCrawl snapshots. It’s the most thorough publicly documented data curation pipeline for LLM pretraining. While not purely a dedup paper, it provides invaluable practical lessons about deduplication at scale.

MinHash Deduplication Configuration

FineWeb chose a compute-efficient MinHash setup:

  • 5-grams for shingling
  • 112 hash functions
  • Split into 14 buckets of 8 hashes each
  • Documents match if they share 8 minhashes in at least 1 of 14 buckets
  • Formula: Match probability = 1 - (1 - s^8)^14

Match probability at different similarity levels:

n-gram SimilarityMatch Probability
70%56%
75%77%
80%92%
85%98.8%

This is notably lighter than RefinedWeb’s 9,000 hashes / 450 buckets / 20 per bucket — but much cheaper to compute. HuggingFace argues the savings outweigh the slightly fuzzier threshold.

Critical Finding: Per-Snapshot > Global Dedup

FineWeb deduplicates each CommonCrawl snapshot independently, not globally. They tested several global dedup strategies and found them all harmful:

MethodTokens RemovedPerformance
Individual snapshot MinHash (baseline)—Best
URL dedup (global)71.5%Worse
Line dedup (global)77.8%Worse
Line dedup w/ min words (global)85%Worse
3-line span dedup (global)80.9%Worse

Why does global dedup hurt? Oldest snapshots lose up to 90% of data when deduplicated against many newer snapshots. The remaining data is actually worse quality — ads, incoherent keyword lists, badly formatted text. Global dedup removes large “good” duplicate clusters (common quality content replicated across crawls) while keeping unique low-quality content.

Scale Sensitivity of Dedup

One of FineWeb’s most important insights: you can’t measure dedup impact at small scale. They simulated drawing subsets from a dataset where every document is repeated 100 times:

  • At 1B tokens: almost all documents appear unique (sampling is too sparse)
  • At 100B tokens: some documents start showing 2-4 repetitions
  • At 1T tokens: majority repeated 8+ times

Lesson: If you’re doing ablations at 28B tokens, you literally cannot see the effects of deduplication. FineWeb ran their dedup evaluations at 350B tokens.

FineWeb-Edu: Quality Filtering as Alternative to Dedup

FineWeb also introduces FineWeb-Edu, which uses an LLM-based educational quality classifier (trained on Llama3 annotations) to filter documents. A score threshold of 3/5 yields the best results, and FineWeb-Edu outperforms all other public datasets — showing that quality filtering and dedup are complementary strategies.

Results:

  • MMLU: 33% → 37% = +12% relative improvement
  • ARC: 46% → 57% = +24% relative improvement
  • Matches Matrix’s final MMLU with ~10x fewer tokens

Practical Implementation with Datatrove

# Minimal example of MinHash dedup with datatrove
from datatrove.pipeline.dedup import (
    MinhashDedupSignature,
    MinhashDedupBuckets,
    MinhashDedupCluster,
    MinhashDedupFilter,
)
 
# Step 1: Compute MinHash signatures
signature_step = MinhashDedupSignature(
    output_folder="signatures/",
    n_grams=5,
    num_buckets=14,
    hashes_per_bucket=8,
)
 
# Step 2: Find matching pairs via LSH buckets
bucket_step = MinhashDedupBuckets(
    input_folder="signatures/",
    output_folder="buckets/",
)
 
# Step 3: Cluster matched documents
cluster_step = MinhashDedupCluster(
    input_folder="buckets/",
    output_folder="clusters/",
)
 
# Step 4: Filter (keep one per cluster)
filter_step = MinhashDedupFilter(
    input_folder="clusters/",
    output_folder="deduplicated/",
)

Grand Synthesis: Comparing All Four Approaches

Method Comparison Matrix

SemDeDupD4SoftDedupFineWeb
Year2023202320242024
TeamMeta AIMeta AITencent AI LabHuggingFace
ApproachHard removal (embedding clusters)Hard removal (dedup + diversify)Soft reweighting (n-gram scores)Hard removal (MinHash LSH)
SignalCosine sim in embedding spaceEmbedding clusters + centroid distN-gram occurrence probabilityN-gram Jaccard similarity
Embedding model needed?Yes (CLIP/OPT)Yes (OPT 125M)No (CPU n-gram only)No (hash-based)
GPU required for dedup?YesYesNoNo
Removes data?YesYesNo (reweights)Yes
Computational costHighHighNegligible (~28 CPU-hrs for 40B tokens)Moderate
Best data reduction~50% with minimal loss~75% (select 25%)N/A (keeps everything)~50-70% per snapshot
Captures semantic duplicationYes (strong)Yes (strong)Partial (surface-level)No (only string-level)
Captures templated contentYesYes+ (better with re-clustering)Yes (common n-grams)Only if strings overlap
Works on already-deduped data?Limited gainsLimited gainsYes, big gainsN/A
Scale testedLAION (440M), C4600M docs, up to 6.7B model40B tokens, 1.3B model15T tokens, 1.71B model
Open code?YesNoNoYes (datatrove)

The Redundancy Spectrum

These methods target different types of redundancy:

EXACT DUPLICATES <----- MinHash/FineWeb -----> NEAR-DUPLICATES
                                                     |
                                        +------------+
                                        v            v
                                   SemDeDup     SoftDedup
                                (semantic sim)  (n-gram frequency)
                                        |
                                        v
                                  D4 (dedup +
                                   diversify)
  1. MinHash (FineWeb): catches string-level near-duplicates (high Jaccard similarity in n-gram sets)
  2. SemDeDup: catches meaning-level duplicates (paraphrases, same idea in different words)
  3. D4: catches duplicates AND actively promotes diversity by removing prototypical/boring examples
  4. SoftDedup: catches statistical redundancy (content made of very common n-gram patterns) — orthogonal to all of the above
Raw CommonCrawl
      |
      v
 [1] MinHash/LSH Dedup (per-snapshot)     <- FineWeb approach
      |  Removes: exact + near-exact string dupes
      |  Cost: moderate (CPU)
      v
 [2] SemDeDup (embedding-based)            <- SemDeDup approach
      |  Removes: semantic duplicates (paraphrases, templates)
      |  Cost: high (GPU for embeddings, FAISS clustering)
      v
 [3] Re-cluster + SSL Prototypes           <- D4 extension (optional)
      |  Removes: prototypical/redundant content
      |  Promotes: diverse, informative content
      |  Cost: moderate (CPU clustering)
      v
 [4] SoftDedup reweighting                 <- SoftDedup approach
      |  Reweights: remaining statistical redundancy
      |  Cost: negligible (~28 CPU-hours)
      v
 Training-ready dataset

End-to-End Implementation

A complete, practical pipeline combining the key ideas:

"""
Complete semantic deduplication pipeline for LLM pretraining data.
Combines ideas from SemDeDup, D4, SoftDedup, and FineWeb.
"""
 
import numpy as np
import torch
import faiss
import kenlm
import subprocess
from pathlib import Path
from tqdm import tqdm
 
 
# ================================================================
# STAGE 1: MinHash Deduplication (FineWeb-style)
# ================================================================
# Use datatrove for this (pip install datatrove)
# See FineWeb section above for code
 
 
# ================================================================
# STAGE 2: SemDeDup (Embedding-based Semantic Dedup)
# ================================================================
 
class SemDeDup:
    """
    Semantic deduplication using pretrained model embeddings.
    Based on Abbas et al. (2023).
    """
 
    def __init__(
        self,
        embedding_dim: int = 768,
        n_clusters: int = 50000,
        kmeans_niter: int = 100,
        eps: float = 0.07,           # duplicate threshold
        keep_strategy: str = "hard", # "hard", "easy", or "random"
        max_cluster_size: int = 50000,  # for memory management
    ):
        self.embedding_dim = embedding_dim
        self.n_clusters = n_clusters
        self.kmeans_niter = kmeans_niter
        self.eps = eps
        self.keep_strategy = keep_strategy
        self.max_cluster_size = max_cluster_size
 
    def embed_documents(self, documents, model, tokenizer, batch_size=64):
        """
        Embed documents using a pretrained model.
        For text: use a sentence transformer or OPT model.
        For images: use CLIP.
        """
        embeddings = []
        model.eval()
 
        with torch.no_grad():
            for i in range(0, len(documents), batch_size):
                batch = documents[i:i+batch_size]
                inputs = tokenizer(
                    batch,
                    padding=True,
                    truncation=True,
                    max_length=512,
                    return_tensors="pt"
                ).to(model.device)
 
                outputs = model(**inputs)
                # Use mean pooling of last hidden state
                emb = outputs.last_hidden_state.mean(dim=1)
                # L2 normalize
                emb = emb / emb.norm(dim=1, keepdim=True)
                embeddings.append(emb.cpu().numpy())
 
        return np.vstack(embeddings).astype("float32")
 
    def cluster(self, embeddings):
        """Run spherical K-Means clustering with FAISS."""
        print(f"Clustering {len(embeddings)} embeddings "
              f"into {self.n_clusters} clusters...")
 
        kmeans = faiss.Kmeans(
            self.embedding_dim,
            self.n_clusters,
            niter=self.kmeans_niter,
            verbose=True,
            gpu=torch.cuda.is_available(),
            spherical=True,
            seed=42,
        )
        kmeans.train(embeddings)
 
        distances, assignments = kmeans.index.search(embeddings, 1)
        return distances.flatten(), assignments.flatten(), kmeans.centroids
 
    def deduplicate_cluster(self, cluster_embeddings):
        """
        Find duplicates within a single cluster.
        Returns: boolean mask where True = keep, False = remove.
        """
        N = len(cluster_embeddings)
        if N <= 1:
            return np.ones(N, dtype=bool)
 
        embs = torch.tensor(cluster_embeddings)
 
        # Process in chunks if cluster is very large
        if N > self.max_cluster_size:
            keep = np.ones(N, dtype=bool)
            chunk_size = self.max_cluster_size
            for start in range(0, N, chunk_size):
                end = min(start + chunk_size, N)
                chunk_embs = embs[start:end]
                sim = chunk_embs @ embs.T
                sim[torch.arange(end-start),
                    torch.arange(start, end)] = 0
                triu = torch.triu(sim[:, start:end], diagonal=1)
                M = torch.max(triu, dim=0)[0]
                keep[start:end] = (M <= 1 - self.eps).numpy()
            return keep
 
        # Full pairwise similarity
        sim = embs @ embs.T
        sim.fill_diagonal_(0.0)
 
        # Upper triangular: later (more prototypical) items get flagged
        triu = torch.triu(sim, diagonal=1)
        M = torch.max(triu, dim=0)[0]
 
        keep = (M <= 1 - self.eps).numpy()
        return keep
 
    def run(self, embeddings):
        """
        Full SemDeDup pipeline.
 
        Args:
            embeddings: (N, D) numpy array, should be L2-normalized
        Returns:
            keep_indices: array of indices to keep
        """
        N = len(embeddings)
 
        # Step 1: Cluster
        distances, assignments, centroids = self.cluster(embeddings)
 
        # Step 2: Process each cluster
        keep_mask = np.ones(N, dtype=bool)
        removed_count = 0
 
        for cluster_id in tqdm(range(self.n_clusters), desc="SemDeDup"):
            cluster_idx = np.where(assignments == cluster_id)[0]
            if len(cluster_idx) <= 1:
                continue
 
            # Sort by distance to centroid
            cluster_dists = distances[cluster_idx]
            if self.keep_strategy == "hard":
                sort_order = np.argsort(-cluster_dists)
            elif self.keep_strategy == "easy":
                sort_order = np.argsort(cluster_dists)
            else:  # random
                sort_order = np.random.permutation(len(cluster_idx))
 
            sorted_idx = cluster_idx[sort_order]
            sorted_embs = embeddings[sorted_idx]
 
            # Find duplicates
            cluster_keep = self.deduplicate_cluster(sorted_embs)
 
            # Map back to global indices
            removed_in_cluster = sorted_idx[~cluster_keep]
            keep_mask[removed_in_cluster] = False
            removed_count += len(removed_in_cluster)
 
        keep_indices = np.where(keep_mask)[0]
        print(f"SemDeDup: {N} -> {len(keep_indices)} "
              f"({len(keep_indices)/N:.1%} kept, "
              f"{removed_count} removed)")
 
        return keep_indices, assignments, centroids
 
 
# ================================================================
# STAGE 3: D4 Diversification (Optional, after SemDeDup)
# ================================================================
 
class D4Diversifier:
    """
    Post-SemDeDup diversification via re-clustering + SSL Prototypes.
    Based on Tirumala et al. (2023).
    """
 
    def __init__(self, embedding_dim=768, n_clusters=11000,
                 proto_keep_ratio=0.5):
        self.embedding_dim = embedding_dim
        self.n_clusters = n_clusters
        self.proto_keep_ratio = proto_keep_ratio
 
    def run(self, embeddings, original_indices):
        """
        Re-cluster cleaned data and apply SSL Prototypes.
 
        Args:
            embeddings: (M, D) embeddings of already-deduped data
            original_indices: mapping back to original dataset indices
        Returns:
            selected_original_indices: final selected indices
        """
        M = len(embeddings)
 
        # Re-cluster the cleaned data
        print(f"D4: Re-clustering {M} documents...")
        kmeans = faiss.Kmeans(
            self.embedding_dim, self.n_clusters,
            niter=20, spherical=True, verbose=True,
            gpu=torch.cuda.is_available()
        )
        kmeans.train(embeddings)
        distances, assignments = kmeans.index.search(embeddings, 1)
        distances = distances.flatten()
        assignments = assignments.flatten()
 
        # SSL Prototypes: keep FARTHEST from centroid (most diverse)
        selected = []
        for cluster_id in range(self.n_clusters):
            cluster_mask = assignments == cluster_id
            cluster_positions = np.where(cluster_mask)[0]
            if len(cluster_positions) == 0:
                continue
 
            cluster_dists = distances[cluster_positions]
            sort_order = np.argsort(-cluster_dists)
            n_keep = max(1, int(len(cluster_positions)
                                * self.proto_keep_ratio))
            kept = cluster_positions[sort_order[:n_keep]]
            selected.extend(kept.tolist())
 
        selected = np.array(selected)
        result = original_indices[selected]
        print(f"D4: {M} -> {len(result)} ({len(result)/M:.1%} kept)")
        return result
 
 
# ================================================================
# STAGE 4: SoftDedup Reweighting
# ================================================================
 
class SoftDedup:
    """
    Soft deduplication via n-gram commonness reweighting.
    Based on He et al. (2024).
    """
 
    def __init__(self, ngram_order=4, n_partitions=20, disparity=10.0):
        self.ngram_order = ngram_order
        self.n_partitions = n_partitions
        self.disparity = disparity
        self.model = None
 
    def train_ngram_model(self, corpus_file,
                          output_dir="/tmp/softdedup"):
        """Train KenLM n-gram model."""
        Path(output_dir).mkdir(exist_ok=True)
        arpa_path = f"{output_dir}/model.arpa"
        binary_path = f"{output_dir}/model.binary"
 
        print(f"Training {self.ngram_order}-gram model...")
        subprocess.run([
            "lmplz",
            "-o", str(self.ngram_order),
            "--text", corpus_file,
            "--arpa", arpa_path,
        ], check=True)
 
        subprocess.run([
            "build_binary", arpa_path, binary_path
        ], check=True)
 
        self.model = kenlm.Model(binary_path)
        return binary_path
 
    def score_documents(self, documents):
        """Compute commonness score for each document."""
        assert self.model is not None, "Train model first!"
 
        scores = np.zeros(len(documents))
        for i, doc in enumerate(
            tqdm(documents, desc="Scoring commonness")
        ):
            log10_prob = self.model.score(doc, bos=True, eos=True)
            n_tokens = len(doc.split()) + 1
            if n_tokens > 0:
                scores[i] = 10 ** (log10_prob / n_tokens)
 
        return scores
 
    def compute_weights(self, commonness_scores):
        """Compute per-document sampling weights."""
        import math
 
        N = len(commonness_scores)
        K = self.n_partitions
 
        sorted_idx = np.argsort(commonness_scores)
 
        segment_ids = np.zeros(N, dtype=int)
        segment_size = N // K
        for k in range(K):
            start = k * segment_size
            end = (k + 1) * segment_size if k < K - 1 else N
            segment_ids[sorted_idx[start:end]] = k
 
        seg_commonness = np.array([
            np.median(commonness_scores[segment_ids == k])
            for k in range(K)
        ])
 
        p_min, p_max = seg_commonness[0], seg_commonness[-1]
        if p_max > p_min and p_min > 0:
            T = math.log(self.disparity) / math.log(p_max / p_min)
        else:
            T = 1.0
 
        raw_weights = np.array([
            (1.0 / max(p, 1e-10)) ** T for p in seg_commonness
        ])
        raw_weights /= raw_weights.sum()
 
        doc_weights = raw_weights[segment_ids]
        doc_weights /= doc_weights.sum()
 
        return doc_weights
 
 
# ================================================================
# PUTTING IT ALL TOGETHER
# ================================================================
 
def full_dedup_pipeline(
    documents,             # list of text strings
    embeddings,            # (N, D) numpy array, L2-normalized
    semdedup_eps=0.07,
    use_d4=True,
    d4_proto_ratio=0.5,
    use_softdedup=True,
):
    """
    Full dedup pipeline combining all methods.
 
    Returns:
        selected_indices: indices of documents to keep
        weights: per-document sampling weights (if softdedup enabled)
    """
    N = len(documents)
    print(f"Starting dedup pipeline on {N} documents")
 
    # --- Stage 1: Assume MinHash already done upstream ---
 
    # --- Stage 2: SemDeDup ---
    semdedup = SemDeDup(
        embedding_dim=embeddings.shape[1],
        eps=semdedup_eps,
        keep_strategy="hard",
    )
    keep_idx, assignments, centroids = semdedup.run(embeddings)
 
    # --- Stage 3: D4 Diversification (optional) ---
    if use_d4:
        diversifier = D4Diversifier(
            embedding_dim=embeddings.shape[1],
            proto_keep_ratio=d4_proto_ratio,
        )
        keep_idx = diversifier.run(embeddings[keep_idx], keep_idx)
 
    # --- Stage 4: SoftDedup Reweighting (optional) ---
    weights = None
    if use_softdedup:
        soft = SoftDedup(
            ngram_order=4, n_partitions=20, disparity=10.0
        )
 
        selected_docs = [documents[i] for i in keep_idx]
        with open("/tmp/softdedup_corpus.txt", "w") as f:
            for doc in selected_docs:
                f.write(doc.replace("\n", " ") + "\n")
 
        soft.train_ngram_model("/tmp/softdedup_corpus.txt")
        commonness = soft.score_documents(selected_docs)
        weights = soft.compute_weights(commonness)
 
    print(f"\n=== Pipeline Complete ===")
    print(f"Original: {N} documents")
    print(f"Selected: {len(keep_idx)} documents ({len(keep_idx)/N:.1%})")
    if weights is not None:
        print(f"Weight range: {weights.min():.6f} to {weights.max():.6f}"
              f" (ratio: {weights.max()/weights.min():.1f}x)")
 
    return keep_idx, weights

Rules of Thumb for Implementation

If you’re just starting out (simplest → most complex):

  1. Start with MinHash — Use datatrove or datasketch Python libraries. Cheapest, most battle-tested.
  2. Add SoftDedup on top — Train a 4-gram KenLM model, score documents, reweight. Costs almost nothing (~7 CPU-hours for 40B tokens) and stacks with everything.
  3. Add SemDeDup if you have GPU budget — Embed with a sentence transformer, cluster with FAISS, dedup within clusters. The official code is a good starting point.
  4. Add D4 diversification if going all-in — Re-cluster after SemDeDup, apply SSL Prototypes. Best results but most complex.

Quick reference:

  • eps = 0.07 is a good starting SemDeDup threshold for text (removes ~35-40%)
  • K = sqrt(N) clusters is a reasonable default for K-Means
  • Keep “hard” examples (farthest from centroid) — this is the default and best strategy
  • SoftDedup with K=20, 10x disparity works well out of the box
  • Don’t over-deduplicate — FineWeb showed that aggressive global dedup can hurt
  • Measure at scale — dedup effects are invisible below ~100B tokens

References

Graph View

Backlinks

  • No backlinks found