💬 NLP

SEDD: Scalable and Efficient Dataset Deduplication with GPUs

SEDD is a high-performance, GPU-accelerated framework for large-scale dataset deduplication that significantly outperforms existing CPU and GPU tools by replacing data shuffling with a streaming approach and optimizing hash functions, achieving up to 375 $\times$ speedup while maintaining high fidelity.

Original authors: Youngjun Son, Chaewon Kim, Jaejin Lee

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Youngjun Son, Chaewon Kim, Jaejin Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a brilliant student (an Artificial Intelligence) by giving them a massive library of books to read. However, this library has a problem: it's filled with thousands of copies of the same story, just with slightly different fonts or a few words changed. If the student reads the same story 1,000 times, they waste time memorizing it over and over instead of learning new things. They might even start thinking that story is the only thing that matters.

To fix this, you need a librarian to go through the library, find all the duplicate books, and throw the extras away. This process is called dataset deduplication.

The paper you provided introduces a new, super-fast librarian named SEDD. Here is how it works, explained simply:

The Old Way: The Slow, Tired Librarian

Before SEDD, there were two main ways to do this job:

The CPU Method (The Human Librarian): This was like a very careful human walking through the library, reading every book, and comparing them one by one. It was accurate but incredibly slow. If you had a library the size of the internet (trillions of words), this human would take years to finish.
The GPU Method (The Fast Robot with a Bad Plan): NVIDIA created a robot (called NeMo Curator) that could read much faster than a human. However, this robot had a flaw: every time it needed to compare two books, it had to physically run back and forth between different rooms to grab them, write notes on the floor, and shuffle piles of paper around. This "running back and forth" (called data shuffling) wasted so much time that the robot's super-speed was often wasted just waiting in line.

The New Way: SEDD (The Super-Efficient Librarian)

The authors of this paper built SEDD, a new system designed specifically to run on powerful computer chips called GPUs (the same chips used for high-end video games). They fixed the robot's problems with three clever tricks:

1. The "Rolling" Stamp (Smarter Hashing)

To find duplicates, the system has to turn every book into a unique "fingerprint" (a code).

The Old Way: Imagine stamping every single page of a book with a heavy, slow ink stamp.
SEDD's Way: SEDD uses a "rolling stamp." If you have a sentence like "The cat sat," and you move to the next sentence "The cat sat on the mat," SEDD doesn't re-stamp the whole thing. It just erases the "The" and stamps the "on the mat" part. It reuses the work it just did. This makes creating fingerprints 375 times faster than the old computer methods.

2. The "No-Shuffle" Pipeline (Streaming)

This is SEDD's biggest innovation.

The Old Way: The robot would gather all the books, sort them into piles on the floor, walk away, come back, sort them again, and write the results down. It was a constant cycle of moving heavy boxes around.
SEDD's Way: SEDD uses a streaming approach. Imagine a conveyor belt. As the books move down the belt, the robot grabs them, checks them, and immediately throws the duplicates into a trash bin. It never stops to sort the whole pile first. It also does two things at once: while it is checking one book, it is already pulling the next book onto the belt. This eliminates the "running back and forth" that slowed down the previous robot.

3. The "Perfectly Sized" Bins (Smart Buckets)

When sorting books, you need bins. If you have too many bins, you spend all day walking between them. If you have too few, the bins get overflowing and messy.

SEDD uses a special math trick to automatically figure out the perfect number of bins for the specific size of the library it is working on. This ensures the robot is always busy and never waiting for a bin to clear out.

The Results: How Fast is it?

The paper tested SEDD on massive libraries (datasets) containing millions of documents and trillions of words.

Vs. The Human (CPU): SEDD was 158 times faster.
Vs. The Previous Robot (GPU): SEDD was 7.8 times faster.
The Big Win: SEDD managed to clean a library of 1.2 trillion words (a massive amount of data used for training AI) in just 3 hours using a cluster of 32 powerful graphics cards.

Did it miss any duplicates?

Speed is great, but accuracy matters. If the librarian throws away a unique book by mistake, the student loses knowledge.

The paper shows that SEDD is extremely accurate. It found the same duplicates as the slow, careful human method 95% of the time or more.
When they tested the AI student using the books cleaned by SEDD, the student performed just as well (or better) as one trained on books cleaned by the slower, older methods.

Summary

SEDD is like upgrading a library cleaning crew from a slow human with a clipboard to a high-speed assembly line robot that never stops moving, reuses its own tools, and knows exactly how to organize the shelves without ever getting tired. It makes preparing data for giant AI models fast, cheap, and efficient.

Technical Summary: SEDD – Scalable and Efficient Dataset Deduplication with GPUs

1. Problem Statement

Large-scale dataset deduplication is a critical preprocessing step for training Large Language Models (LLMs) to ensure data quality, reduce computational waste, and prevent overfitting. The standard approach for detecting near-duplicates in web-scale corpora is MinHash Locality-Sensitive Hashing (LSH). However, existing implementations face significant bottlenecks when scaling to trillion-token datasets:

CPU Limitations: Traditional CPU-based implementations (e.g., using the datasketch library) suffer from poor parallelization and high computational costs, making them prohibitively slow for massive datasets.
GPU Limitations: While GPU-accelerated frameworks like NVIDIA NeMo Curator offer improvements, they remain suboptimal due to architectural inefficiencies. Specifically, they rely on physical data shuffling (repartitioning data to disk based on bucket IDs), which incurs high I/O latency and communication overhead. Furthermore, their sparse bucketing strategies and sequential execution models often fail to saturate GPU resources, leading to underutilization of hardware parallelism.

2. Methodology

The authors propose SEDD, a high-performance, end-to-end GPU-accelerated deduplication framework optimized for distributed cluster environments. SEDD addresses the identified bottlenecks through three primary technical innovations:

A. Computationally Efficient Hashing

SEDD replaces standard cryptographic or non-cryptographic hash functions with a Rabin-Karp rolling hash for MinHash signature generation.

Mechanism: Unlike the CPU baseline (SHA-1) or GPU baseline (MurmurHash3), which recompute hashes for every shingle, the rolling hash allows the hash value of a shingle to be derived from the previous shingle using a few arithmetic operations (multiplication, addition, division).
Benefit: This enables partial reuse of hash values across adjacent shingles, significantly reducing the computational cost of generating MinHash signatures.

B. Streaming-Based Data Pipeline

SEDD eliminates the need for physical data shuffling (writing intermediate results to disk and repartitioning) by employing a streaming-based extraction strategy.

Mechanism: Instead of physically moving data to reorganize it by bucket ID, SEDD processes intermediate hash files on-the-fly. Each GPU process is assigned a subset of bands and scans the storage to extract signatures for specific buckets.
Double Buffering: The system utilizes double buffering to overlap communication (data transfer between CPU and GPU) with computation (GPU kernel execution), effectively hiding I/O latency.
Comparison Strategy: Unlike baselines that use $O(D)$ anchor-based heuristics (comparing only one anchor document against others in a bucket), SEDD performs exhaustive $O(D^2)$ all-pairs comparisons within each bucket. This is made feasible by highly optimized custom CUDA kernels.

C. Hardware-Aware Optimization

Kernel Design: SEDD implements custom CUDA kernels for the "count-match" operation (comparing signature vectors) using a GEMM-inspired tiled design to improve data locality and shared memory usage.
Parameter Selection: The framework includes an automatic parameter selection mechanism that determines the optimal number of buckets ( $K$ ) and concurrent processing batches based on available CPU/GPU memory and dataset size. The optimal bucket count is modeled as $K \propto \sqrt{N}$ to balance collision probability against buffer management overhead.

3. Key Contributions

End-to-End GPU Framework: SEDD is presented as a complete framework that achieves up to 7.8× speedup over the state-of-the-art GPU baseline (NVIDIA NeMo Curator) and 158× over CPU baselines on a single node with four GPUs.
Optimized MinHash LSH: The introduction of reusable rolling hash functions and custom GPU kernels accelerates the signature generation phase by up to 375× compared to CPU baselines.
Communication-Efficient Pipeline: By replacing physical shuffling with streaming extraction and double buffering, SEDD reduces total communication overhead to approximately 20% of that found in existing frameworks.
Scalability: The framework successfully processes 1.2 trillion tokens in just 3 hours on an 8-node, 32-GPU V100 cluster.

4. Experimental Results

The authors evaluated SEDD against CPU (SlimPajama) and GPU (NeMo Curator) baselines using the RealNews and C4 datasets.

Performance:
- On a 100GB RealNews dataset (30M documents), SEDD completed deduplication in 135.2 seconds, compared to 21,361.4 seconds for the CPU baseline and 1,048.8 seconds for the GPU baseline.
- The MinHash generation phase alone saw a 375× speedup over the CPU baseline.
- Scaling experiments showed that SEDD maintains at least a 7× speedup over the GPU baseline even as the number of GPUs increases to 32.
Accuracy:
- Despite the optimizations, SEDD maintains high fidelity. When compared to an "Exact MinHash" oracle on smaller datasets, SEDD achieved a Jaccard similarity of 0.956 (for 0.1M docs) and 0.966 (for 1M docs).
- Compared to NeMo Curator on large datasets, SEDD identified over 97% of the near-duplicates found by NeMo while uncovering additional instances.
- Downstream LLM training (LLaMA 3.2-1B) on SEDD-deduplicated data yielded performance comparable to NeMo-deduplicated data across multiple benchmarks (HellaSwag, MMLU, ARC-Easy, WinoGrande), despite using 10% fewer tokens.
Communication Efficiency:
- In a 4-GPU environment, SEDD reduced communication latency from 187.7s (GPU baseline) to 35.7s and communication volume from 3.45 TB to 398.9 GB.

5. Significance

The paper argues that SEDD provides a practical and scalable solution for the growing demands of modern LLM data pipelines. By addressing the specific architectural inefficiencies of existing GPU frameworks—namely excessive data shuffling and poor resource utilization—SEDD enables the efficient processing of trillion-token corpora within hours rather than days. The authors emphasize that this efficiency is achieved without compromising the accuracy of duplicate detection, ensuring that the resulting datasets remain high-quality for training state-of-the-art language models. The work highlights that hardware-aware system optimizations, such as rolling hashes and streaming pipelines, are essential for unlocking the full potential of GPU clusters in data preprocessing tasks.