Introduction

Large language model training data is often described as a static dataset – a large pool of documents is collected, filtered, deduplicated, and then used to train a model. In practice, however,  training corpora rarely remain static. For instance, a new Common Crawl release could arrive, a code repository snapshot could be refreshed, or a new specialized dataset could be collected or publicly released which we want to integrate into our larger corpus. 

This poses a core problem for deduplication, a crucial practice to make sure models are not trained on many versions of the same or near-identical text. Each new release must be deduplicated not only against itself, but against everything that has already been admitted into the corpus. The conventional solution is to construct a fresh deduplication index for each snapshot of the corpus. This is reasonable when datasets are built infrequently and the historical state is small. However, naively adding a new dataset requires re-deduplicating the  entire corpus, and every new release forces the pipeline to reprocess an ever-expanding collection. For rapidly expanding datasets comprising billions of documents and trillions of tokens, this stops being a one-off data-processing step and becomes a persistent infrastructure challenge.

Fuzzy deduplication is particularly important in real-world LLM data processing. Exact deduplication can remove byte-identical documents, but real web data contains many documents that are effectively the same despite small changes in formatting, boilerplate text/code, timestamps, navigation elements, or wording. Leaving these near-duplicates in a training corpus can waste compute, distort the effective weighting of different sources, increase memorization, and contribute to train–test contamination.

To address the challenges and needs of an evolving corpus, we built PUFFER — Provenance-aware Updatable Fuzzy Filtering for Evolving Repositories — to make fuzzy-deduplication persistent, allowing us to incrementally add new datasets to our core training corpus as they are collected. 

Rather than rebuilding the state of the corpus each time new data arrives, PUFFER incrementally maintains the information required to determine whether a document resembles previously seen documents. It keeps this state on disk rather than in a corpus-sized in-memory table, keeping RAM requirements manageable even for massive corpora. PUFFER preserves the configured MinHash-LSH decisions as the corpus grows, so incrementally adding a dataset gives an identical result to reprocessing the entire corpus. It also embeds dataset provenance directly into the index, enabling targeted withdrawal of a dataset after ingestion.

The result is a system designed not for a single snapshot, but for the full lifecycle of a living corpus.

What Makes Incremental Deduplication Difficult?

At first glance, incremental deduplication sounds straightforward: save the fingerprints of previous documents, then compare each new release against them, but the rapid growth of the broader data ecosystem illustrates the scale of this challenge. The difficulty is making this approach continue to work over billions of documents and many successive releases. A practical system needs to satisfy several properties simultaneously.

• It should process only the incoming release and the maintained historical index, rather than repeatedly rebuilding everything. 

• Its memory requirements should not grow in direct proportion to the size of the corpus. 

• It should remain faithful to the chosen fuzzy-deduplication rule instead of gradually accumulating errors from a capacity-limited probabilistic data structure. 

• Failed jobs should be safely retryable. 

• Finally, the index should know which dataset contributed which state, so that individual datasets can be protected or withdrawn without requiring reprocessing the entire corpus.

Existing approaches generally trade away at least one of these properties.

A conventional MinHash-LSH table can preserve the desired membership rule, but its resident-memory requirements eventually become prohibitive. Bloom-filter approaches are compact, but introduce false positives, require capacity to be provisioned in advance, and cannot cleanly remove an individual dataset’s contribution. Approximate-nearest-neighbor indexes can support online search, but typically maintain a large memory-resident structure and do not natively provide deterministic retry or dataset-level withdrawal. Snapshot pipelines avoid maintaining long-lived state, but must repeatedly reconstruct global deduplication artifacts.

PUFFER is designed around a different premise: the deduplication index should be treated as durable, provenance-aware data infrastructure. PUFFER uses MinHash-LSH as its fuzzy-deduplication rule. The intuition is that a document can be represented by the short overlapping fragments of text it contains, often called shingles. Two documents with many shingles in common are likely to contain substantially the same content, even when they are not byte-identical and thus differ in formatting, paragraph boundaries, or the local arrangement of text.

Comparing every pair of documents directly would be prohibitively expensive. MinHash compresses each document’s shingle set into a compact signature. Locality-sensitive hashing then divides this signature into several bands and hashes each band into a small fixed-width key. A document therefore becomes a collection of band keys. When two documents share at least one of these keys, they are treated as a potential fuzzy match under the configured MinHash-LSH rule. Once these keys have been computed, the problem at the index layer is conceptually simple: we need to check whether any of the incoming document’s band keys has appeared in the live corpus before. The challenge is answering that question efficiently and reproducibly when the historical set contains billions of documents and is continually changing.

PUFFER’s Core Idea: Store History as Dataset-Tagged, Tiered Sorted Segments

PUFFER stores the historical keys for each LSH band in a collection of immutable, sorted files called segments. Each segment is a duplicate-free sorted array of 64-bit band keys. Because the keys are sorted, PUFFER can determine whether an incoming key is present using binary search. Because the segment is immutable, it can be memory-mapped directly from disk instead of being loaded into a large application-managed data structure. As soon as the number of segments grows to reach a prescribed value T in a given tier they are compacted and moved to the next level - this allows for an optimization of the combined screening and data writing costs. Each segment also carries a dataset tag and lineage metadata describing where its keys originated. This provenance is not stored as a separate afterthought: it is part of the physical organization of the index.

PUFFER operates on this state through four main operations: screen, commit, compact, and withdraw.

Figure 1: A schematic of the PUFFER deduplication engine. For each MinHash-LSH band, incoming keys are screened against immutable historical segments. A successful commit atomically installs a dataset-tagged segment. Tiered compaction merges same-level segments to control query fanout, while provenance metadata and retained band-key state support retry and dataset withdrawal.

Screening a New Release

When a dataset arrives, PUFFER first deduplicates it internally. The surviving documents are then screened against the historical index. For every band key, PUFFER performs binary searches across the live segments for that band and stops as soon as it finds a match. Documents matching any historical segment are removed from the output as near-duplicates.

Crucially, any segment tagged with the dataset currently being processed is excluded from the historical query view. This means that if a job is interrupted after partially committing its output, rerunning it does not cause the dataset to identify its own previous attempt as historical duplication.

Atomic, Dataset-Tagged Commits

After screening, PUFFER sorts and deduplicates the new release’s band keys and writes them into immutable segments tagged with the dataset’s identity. Commits are installed using atomic file and manifest operations. Until the commit completes, temporary files are not visible to future queries. A repeated commit for the same dataset tag replaces the earlier logical contribution instead of appending a second copy. PUFFER also preserves the document keys that survived within-release deduplication even when those documents were rejected because they matched an earlier dataset. This is so that datasets can be withdrawn later without replaying every release from scratch.

Compaction

The segment-based layout introduces a natural trade-off between retaining segments separately or merging them. Keeping every release in a separate segment avoids rewriting previously committed segments, but each new release must search an increasing number of segments. Merging segments reduces the number of searches, but requires reading and rewriting their keys.

With PUFFER, we manage this trade-off using T-fanout tiered compaction. When a level accumulates T eligible segments, PUFFER merges them into a single segment at the next level. Because the inputs are already sorted, this can be performed as a streaming merge under a fixed memory budget.

The resulting segment contains exactly the union of the original keys. Compaction changes the cost of maintaining and querying the index, but not which membership decisions it makes.

Withdrawal

We deliberately designed PUFFER to make dataset removal a first-class operation. When a dataset remains in its own uncompacted segment, withdrawing it is simply a metadata operation. However, after compaction, keys from multiple datasets may be mixed into one larger segment. PUFFER reconstructs the affected segment from the retained band keys of its surviving constituent datasets without needing to rebuild the full historical index or retain the original withdrawn dataset. 

Results

We evaluated PUFFER against the closest implemented alternatives across the main requirements of a living deduplication index: ingestion throughput, fidelity to the configured MinHash-LSH rule, and resident-memory demand.

For a controlled comparison, the primary benchmarks begin after document shingling and band-key computation. Each system receives the same deterministic stream of precomputed keys, allowing the experiments to isolate duplicate identification and index construction. We separately tested the complete pipeline on real Parquet data.

Figure 2: Document ingestion and deduplication speed with PUFFER vs. alternative methods. PUFFER dramatically outperforms LSHBloom (datasketch implementation) despite an asymptotic disadvantage: PUFFER’s amortized historical-index cost per insertion is O(log N log K) vs O(1) for a Bloom filter, where N is the corpus size and K is the number of releases. However in practice the constant implementation overheads of other methods are so large compared to PUFFER that this effect is completely masked.

Figure 3: PUFFER operates with a configurable RAM budget and uses a tiny fraction of the RAM as alternative methods (note the logarithmic Y axis). PUFFER’s segments are memory-mapped from disk and merged by streaming, so resident memory never grows in proportion to the historical corpus.  

One Billion Documents in 1.75 Hours

PUFFER completed the cumulative index-stage ingestion of one billion documents across 40 releases in approximately 1.75 hours, using a single process. This measurement includes historical screening, committing each release, and all scheduled compactions.

In a ten-hour comparison window capped at one billion documents ingested, PUFFER achieved an 11× speedup over LSHBloom and a 35× speedup over the served Milvus MinHash-LSH baseline, where LSHBloom and Milvus progressed to 600 million and 187 million documents, respectively.

Moreover, PUFFER’s cumulative cost remains quasilinear as new releases are added, rather than approaching the quadratic behavior of repeatedly rebuilding a snapshot index over an ever-larger corpus.These results show that PUFFER can efficiently continue incorporating new releases at billion-document scale, which current alternative methods cannot while satisfying the lifecycle needs of a growing pretraining corpus. 

PUFFER has now been deployed in production on more than 30 billion documents.

Why This Matters

Data quality is one of the most important determinants of model quality, but the infrastructure used to create training corpora is often treated as a second-class citizen. A snapshot-oriented workflow assumes that a corpus is collected and finalized once. However, as a foundation model lab developing multiple models over the course of years, this assumption is increasingly unrealistic. New data continues to arrive, processing methods improve, policies change, and individual sources may need to be reconsidered long after their initial ingestion.

We built PUFFER to make incremental deduplication a core part of our data infrastructure, with the goal of making the historical state of fuzzy deduplication persistent, reproducible, and governable. More broadly, PUFFER demonstrates that large-scale data curation benefits from many of the same properties expected from production databases: durable state, deterministic transactions, provenance, bounded-memory execution, compaction, and dataset-scoped lifecycle controls.

We are releasing the core PUFFER engine as open-source software under a permissive Apache 2.0 license. The implementation and instructions for building continuously maintained fuzzy-deduplication indexes are available through Zyphra’s GitHub. You can read more details about the underlying architecture and engineering of PUFFER in the technical report.