Source-linked AI summary
PUFFER: Incremental Fuzzy Deduplication for Continuously Evolving Corpora
Xiao Yang, Erik Edward Aldape, Beren Millidge
TL;DR
Continuously evolving corpora require deduplication state that supports new releases and dataset removal without repeatedly rebuilding snapshot state. PUFFER incrementally maintains MinHash-LSH band-key state using immutable tagged segments and tiered compaction, achieving billion-document ingestion while preserving membership decisions and lifecycle control.
Problem
Data-curation pipelines built for fixed snapshot corpora do not match continuously arriving releases and datasets that may later require removal.
Method
PUFFER stores LSH band keys in immutable, dataset-tagged, memory-mapped sorted segments and uses tiered compaction to control screening fanout while supporting deterministic retry and dataset-scoped withdrawal.
Results
1.75 hours of index time completed ingestion of one billion documents across forty releases in a single process, while PUFFER achieved a 35× speedup over the served MinHash-LSH baseline.
Takeaways & Limitations
PUFFER makes deduplication state practical as persistent infrastructure for continuously evolving training corpora rather than temporary state rebuilt for each snapshot.
Takeaways & Limitations
The appropriate compaction fanout depends on release overlap and the relative costs of reading and writing; withdrawal after compaction requires reconstructing the affected segment.
Abstract
from arXiv · showhide
Large language model training corpora grow through successive, often redundant releases, so each release must be deduplicated against both itself and the accumulated history. At trillion-token scale, this requires incremental ingestion, bounded resident memory, deterministic retry, and dataset-scoped lifecycle control without repeated corpus-wide rebuilding. We introduce PUFFER (Provenance-aware Updatable Fuzzy Filtering for Evolving Repositories), a MinHash-LSH fuzzy-deduplication pipeline built around two design choices. First, PUFFER stores each LSH band as immutable, dataset-tagged, memory-mapped sorted segments, enabling exact historical band-key membership checks without RAM proportional to corpus size. Second, T-fanout tiered compaction periodically merges segments to control screening fanout, trading lower query cost against additional index-maintenance writes while preserving membership decisions. Across N ingested keys and K equal-sized releases, PUFFER's cumulative maintenance cost is O(N log N log_T K), compared with Theta(KN) for repeated snapshot rebuilding. Dataset-tagged segments also support dataset-scoped withdrawal: removal is constant-time for uncompacted or protected datasets, while post-compaction withdrawal reconstructs only the affected merged segment, even if the original dataset is unavailable. In our implementation, PUFFER completed cumulative index-stage ingestion for one billion documents in about 1.75 hours in a single process, using 128 bytes per document for a 16-band index. A classical resident MinHash-LSH table required about 6.5 KB per document and exceeded a 900 GiB RAM cap. In a ten-hour comparison capped at one billion documents, PUFFER was 11x faster than LSHBloom and 35x faster than Milvus-LSH. PUFFER is deployed on more than 30 billion documents, and we release it as open-source software at https://github.com/Zyphra/puffer.
I. INTRODUCTION
PUFFER addresses the mismatch between snapshot-oriented deduplication and continuously evolving corpora by maintaining exact, disk-resident fuzzy-deduplication state incrementally. Its dataset-tagged segments support bounded-memory screening, deterministic retries, compaction, and dataset-scoped lifecycle operations.
- Near-duplicates can waste compute, distort mixture composition, increase memorization risk, and worsen train–test contamination.
- Continuously arriving releases and occasional dataset withdrawals make a static snapshot corpus an inadequate maintenance model.New web dumps, code snapshots, and domain-specific collections arrive after prior corpora are built, while quality, licensing, compliance, or governance issues can require removal.
- Incremental deduplication must update only incoming releases and maintained history while preserving exact MinHash-LSH membership decisions in disk-resident structures.The stated desiderata also include bounded resident memory and dataset provenance embedded in the index.
- PUFFER stores immutable, dataset-tagged, memory-mapped sorted band-key segments and screens releases through batched binary search.Atomic tag replacement makes retries idempotent, while tiered compaction trades screening fanout against index-maintenance writes without changing membership decisions.
- 1.75 hours sufficed for PUFFER to complete index-stage processing of one billion documents across forty releases in a single process.The evaluation includes the full index lifecycle and reports PUFFER as the only evaluated design combining exact membership decisions, non-resident scaling, explicit compaction control, deterministic retry, and dataset-scoped withdrawal.
II. METHODS
PUFFER applies fixed MinHash-LSH to incremental releases, screening each against itself and live history before atomically committing surviving keys. Immutable sorted segments, bounded-memory compaction, stable tags, and sidecar state provide exact membership handling together with retry and withdrawal support.
- Screen: Each release is deduplicated internally and against the live historical union of non-withdrawn prior releases before new state becomes query-visible.Within each band-key collision group, PUFFER retains the document with the smallest stable identity and avoids constructing a transitive duplicate graph.
- MinHash-LSH rule: MinHash represents documents as shingle-set signatures, while LSH divides each signature into B bands of R = p/B rows and hashes each band to a 64-bit key.Two documents collide when they share at least one band key.
- MinHash-LSH rule: The configured shingle definition, signature length, banding parameters, and collision policy jointly define the fuzzy-deduplication rule.The index layer’s residual error comes from fixed-width 64-bit hash collisions, with an approximate bound of B U/2^64 for U distinct historical keys per band.
- Index representation: PUFFER stores duplicate-free sorted 64-bit band-key arrays as memory-mapped immutable segments whose manifests track tags, levels, status, and compaction lineage.The same lifecycle applies independently across all LSH bands.
- Commit and retry: Commit atomically installs a dataset-tagged sorted segment and replaces any prior logical contribution for the same tag.PUFFER retains keys removed only by historical screening so later withdrawal can reconstruct state without replaying subsequent datasets.
- Compaction: T-way streaming compaction merges eligible same-level segments into a unique sorted union under fixed working memory, changing costs but not membership decisions.Larger T reduces merge frequency but increases screening fanout; smaller T does the opposite, and compaction can mix dataset contributions.
- Withdrawal: Withdrawal removes uncompacted or protected datasets through constant-time manifest metadata, while post-compaction removal reconstructs only the affected merged segment.Saved sidecar band-key state enables reconstruction from constituent datasets without access to the original dataset.
- Commit and retry: Stable dataset tags and manifest-atomic commit make interrupted ingestion restarts deterministic and idempotent.Tagged segments are excluded from their own historical query view, and temporary writes remain attempt-local until commit.
III. RESULTS
PUFFER remains practical for continuously growing deduplication corpora by combining incremental ingestion, bounded memory, exact MinHash-LSH fidelity, and dataset-level lifecycle control. Across large-scale experiments, tiered compaction improves cumulative scaling while preserving membership decisions and supporting local withdrawal and deterministic retry.
- Ingestion and scaling: 1.75 hours completed PUFFER’s cumulative index-stage ingestion of one billion documents across forty releases in a single process.The run used B=16 bands and included every screen, commit, and compaction.
- Ingestion and scaling: 35× speedup over the served MinHash-LSH baseline was achieved in the ten-hour throughput comparison.PUFFER sustained billion-document ingestion while the baseline did not reach the same corpus scale within the benchmark window.
- Memory and fidelity: PUFFER tracked the exact-LSH oracle with zero index-layer false positives at every tested corpus size, without upfront capacity provisioning.LSHBloom’s error grew after its provisioned capacity was exceeded.
- Memory and fidelity: 128 bytes per document at B=16 bands kept PUFFER roughly 25× smaller than the classical resident MinHash-LSH table.The resident baseline required roughly 6.5 KB per document and exceeded a 900 GiB RSS cap at 173.7M documents.
- Compaction trade-offs: 67 seconds of streaming compaction restored single-segment screening latency with a 17.8× reduction at the two-billion-key scale, without changing membership decisions.At ten billion ingested keys per band, default T=4 achieved 2.42 writes per key while preserving key unions and per-release decisions.
- Compaction trade-offs: O(N log N log_T K) cumulative ingestion cost gives tiered compaction an asymptotic advantage over Θ(KN) repeated snapshot rebuilding.The fanout T controls screening work versus rewrite amplification; T=4 was optimal for the reported runs, while the optimum is machine-dependent.
- Lifecycle control: Uncompacted withdrawal took 2 milliseconds, while post-compaction withdrawal remained local to the affected state rather than requiring corpus-wide rebuilding.Interrupted commits also produced bit-identical state and decisions after retry.
- Lifecycle control: End-to-end deduplication of approximately 2.5 billion real documents completed in approximately five hours using eight nodes.The workload was partitioned into 100 Parquet releases and included cleaned-Parquet output.
IV. DISCUSSION
PUFFER treats fuzzy-deduplication state as persistent infrastructure for evolving corpora, while exposing tradeoffs and scope boundaries around compaction, workload assumptions, withdrawal, and corpus reconstruction.
- Discussion: PUFFER maintains MinHash-LSH band-key state incrementally without corpus-size-proportional resident memory, while supporting dataset-level retry and withdrawal.The design treats corpus construction as ongoing maintenance rather than an artifact rebuilt for each snapshot.
- Scope: PUFFER targets very large corpora arriving as successive releases when persistent historical state and dataset-level lifecycle operations are required.Snapshot, in-memory, Bloom-filter, database-backed, and graph-based approaches remain attractive under different workload constraints.
- Compaction tradeoffs: Increasing compaction fanout reduces write amplification but leaves more segments for screening; decreasing fanout has the opposite effect.The workload model assumes fixed dataset novelty and flat historical-index distributions for its approximation.
- Limitations: When dataset overlap depends on time, the workload model may be inappropriate, and the suitable fanout depends on release overlap and relative read and write costs.The authors report T = 4 as optimal in their experiments, but do not present it as universally optimal.
- Withdrawal: Withdrawal can remove a dataset’s impact from future index screening without rebuilding the full index, but restoring previously rejected documents requires replaying affected releases.Under first-seen incremental selection, representatives may depend on release order and partitioning; order-independent corpora need an additional global selection policy.
- Limitations: PUFFER preserves a configured lexical MinHash-LSH rule rather than defining duplication uniquely, and its implementation currently serializes index commits.Detection also depends on fixed normalization, boundaries, shingle construction, MinHash length, and banding choices.
APPENDIX A RELATED WORK
Prior systems largely deduplicate fixed candidate pools or pursue different index-layer goals, whereas PUFFER treats corpus construction as ongoing, provenance-aware maintenance.
- Existing curation pipelines: Existing corpus-curation toolkits are largely batch workflows over supplied input collections, including Bloom-filter and MinHash-LSH-style pipelines.Dolma, DataTrove, and NeMo Curator are presented as examples organized around fixed candidate pools.
- Representation-level methods: Embedding-based systems such as SemDeDup and D4 target semantic redundancy and data diversification, which is complementary to PUFFER’s index-layer problem.PUFFER addresses preservation of a selected deduplication rule as the corpus evolves.
- Bloom-filter approaches: LSHBloom reduces index size with Bloom filters but introduces capacity-dependent probabilistic false positives and requires rebuilding for dataset withdrawal.Bloom-filter state is not invertible, so surviving sources are needed for withdrawal.
- PUFFER’s position: PUFFER stores materialized band keys in sorted memory-mapped segments, enabling dataset withdrawal without fully rebuilding the index.Dataset tags make provenance and the deletion unit explicit in the physical layout.
- PUFFER’s position: PUFFER targets reproducible dataset-level batch ingestion rather than low-latency document-by-document admission or served approximate-neighbor retrieval.Its storage machinery draws on LSM-tree compaction theory while making dataset lifecycle control a first-class index property.
APPENDIX B COMPLEXITY DERIVATION
For fixed fanout and a bounded protected set, PUFFER’s incremental index costs grow polylogarithmically with corpus and release scale, unlike repeated snapshot rebuilding.
- Definitions and assumptions: K denotes committed releases, N the total ingested band keys, T the tier fanout, and P the protected L0 segments excluded from compaction.The bounds are stated per band, with T and P treated as configuration constants while K and N are unbounded.
- Live-segment count: At rest, each unprotected tier holds at most T−1 segments, with maximum level L ≤ log_T K.A level-ℓ segment represents T^ℓ L0 arrivals under the merge rule.
- Screening: Each ingested key is screened against every live segment using binary search, giving O(N log N log_T K) cumulative screening cost.The per-key bound is O(log N log_T K), and screening is the asymptotically dominant term.
- Compaction: Compaction costs O(N log_T K) because each key is rewritten only when its segment level increases, at most O(log_T K) times.Each merge writes keys at Θ(1) per rewrite.
- Withdrawal: Withdrawal costs Θ(1) per band for uncompacted or protected segments, while post-compaction withdrawal reconstructs only the affected merged segment.At the base tier, the reconstruction can reach Θ(N log K), but it is level-local rather than a whole-corpus rebuild.
- Total cost: O(N log N log_T K) is the cumulative bound for screening, commit, and compaction under fixed T and bounded P.For fixed release size, repeated snapshot rebuilding costs Θ(KN), even under an optimistic linear-work-per-rebuild assumption.
APPENDIX C MEASUREMENT NOTES
The measurements use controlled release streams, precomputed band keys, and per-process resource accounting to compare index-layer behavior. The real-release figure reports how within-release and cross-release duplicate removal vary over ingestion order.
- Measurement scope: Timed runs use deterministic release streams and exclude signature preparation from the measured phases.The comparison focuses on specified screening and insertion stages rather than end-to-end signature generation.
- Measurement scope: PUFFER’s index-layer timing consumes precomputed band keys and measures screening plus storage after band-key generation.This timing is an index-layer component measurement, not public-API or end-to-end pipeline timing.
- Memory measurement: Memory curves report peak process RSS per release, while PUFFER’s mapped index segments are file-backed and reclaimable by the operating system.The high-water metric does not decompose peak memory composition.
- Experimental configuration: The controlled throughput and memory experiments use 25M synthetic 64-bit band keys per release, 128-permutation MinHash, and 16 bands.PUFFER uses fanout T = 4 with a 4 GiB merge budget in these experiments.
- Experimental configuration: The fidelity experiment uses 128-permutation MinHash over 40-shingle documents, with near-duplicates calibrated at Jaccard similarity 0.90 and unique documents at 0.Bloom false positives are measured on a 2,000-document known-unique holdout.
- Real-release measurement: Across 100 real releases totaling approximately 2.5 billion documents, total removal rises from approximately 2% initially to approximately 40% in final releases.Within-release removal stays approximately stable, while cross-release removal increases as historical coverage grows.
APPENDIX D END-TO-END INGESTION ON REAL PARQUET
PUFFER was evaluated on approximately 2.5 billion real Parquet documents split across 100 sequential releases. As history accumulated, cross-release duplicate removal increased while within-release removal remained stable, and the complete workload finished in approximately five hours on eight worker nodes.
- Workload: Approximately 2.5 billion real Parquet documents were partitioned into 100 sequential releases of roughly 25 million documents each.Each new release was deduplicated against the accumulated historical index.
- Figure interpretation: The figure’s horizontal axis denotes release order, while its vertical axis reports each release’s fraction removed as duplicates.This is a per-release removal fraction, not a cumulative removal statistic.
- Observed behavior: Within-release removal remains approximately stable, whereas cross-release removal increases steadily as the historical index covers more previously observed content.Together, these effects raise total removal over release order.
- End-to-end result: Approximately five hours were required on eight worker nodes for the complete workload.The timing includes real Parquet processing, incremental deduplication, cumulative index construction and maintenance, and cleaned-output writing.
APPENDIX E OPTIMAL FANOUT MODELING
The fanout model estimates cumulative screening and compaction work under a fixed-novelty, uniformly distributed duplicate workload. It combines exact integer-cost evaluation with smooth Lambert-based candidate generators, while treating direct enumeration as the most reliable final optimization.
- Model assumptions: The model assumes each of K releases presents m keys with fixed novel fraction ν, while duplicate keys are uniformly distributed over retained keys.It models a protected prior-release segment plus a base-T counter over earlier releases.
- Screening cost: Novel keys scan all live segments, while duplicate probes stop at the first matching segment under earliest-first probing.The exact objective keeps novel and duplicate comparison counts separate.
- Compaction cost: A carry into level j occurs floor((K−1)/T^j) times and rewrites qT^j keys, defining the cumulative compaction rewrite count.The optimization combines screening costs with machine-specific read and write costs.
- Optimization procedure: Direct enumeration of the exact objective is the most reliable final optimization because it retains floor terms, partial counter cycles, and integer fanout restrictions.Closed digit forms and smooth approximations instead provide candidate generators.
- Approximation: The coarse Lambert optimum depends on workload through log_2 q and on hardware through c_w/c_r, while the number of releases does not enter its equation.The generalized refinement retains additional terms omitted by the coarse approximation.
- Numerical operating point: For the numerical workload, T_Lambert ≈ 3.80 and T_gen ≈ 3.49, so neighboring integer fanouts should be evaluated against the exact objective.At T = 4, the reported digit totals are (G_0, G_1, G_2, G_3) = (141, 141, 111, 31).