Near-duplicate finders materialise every candidate pair (shared seen set + pairs list): quadratic memory/time on duplicate clusters and on large unique corpora (CR-A11-004) #478

Wave 2 · theme D2-5: Data audit, masking and ingestion: medium effort · highest severity High · 1 finding(s) · effort large

Summary

A support-ticket or scraped corpus with tens of thousands of copies of a boilerplate reply (or an adversarially submitted dataset of repeated rows) makes forgelm audit consume tens of GB and get OOM-killed, or run for hours. The pre-training audit step dies instead of reporting.

Primary finding

CR-A11-004 — Near-duplicate finders materialise every candidate pair (shared seen set + pairs list): quadratic memory/time on duplicate clusters and on large unique corpora

severity High · reachability default · intent contract-violation · confidence confirmed · independently confirmed · reproduced end to end · already tracked: KNOWN-OPEN TRUST-12 — docs/roadmap/phase-16-trust-surface-hardening.md:586-601 (S10 open)

What happens. _bucket_pairs_within_threshold (forgelm/data_audit/_simhash.py:217-238) adds every in-bucket (i,j) to a scan-wide seen set and appends every verified triple to pairs; find_near_duplicates (:294-303) returns and sorts the whole list, and find_near_duplicates_minhash (_minhash.py:125-136, _emit_minhash_pair) has the same shape. The only consumer _within_split_pairs (_aggregator.py:248-263) uses len(pairs). A cluster of k identical rows gives k(k-1)/2 entries; with 4 bands of 16 bits, unique data also yields ~n^2/2^17 seen-set entries.

Where.

• forgelm/data_audit/_simhash.py:295-303 (seen and pairs initialisation plus loop)
• forgelm/data_audit/_simhash.py:217-238 (confirmed)
• forgelm/data_audit/_aggregator.py:248-263 (confirmed)
• forgelm/data_audit/_minhash.py:125-136 (confirmed)
• forgelm/data_audit/_simhash.py:198-214
• forgelm/data_audit/_simhash.py:296
• forgelm/data_audit/_minhash.py:125
• forgelm/data_audit/_minhash.py:77-96 (_emit_minhash_pair seen set)
• docs/guides/data_audit.md:617
• forgelm/data_audit/_simhash.py:256-303

Evidence.

• logs/dup_summary.txt: D_2500_simhash 2.74 s 987807744 B; D_5000_simhash 10.15 s 3674226688 B; D_10000_simhash 45.54 s 10497589248 B (pairs 49,995,000); D_10000_minhash 117.31 s 10497228800 B. Scale: 100k simhash 219398144 B vs 1M simhash 4761501696 B.
• memtest.py (tracemalloc peak, k identical fingerprints, threshold 3): k=1000 -> 499,500 pairs, 113 MB, 1.0 s; k=2000 -> 451 MB, 4.4 s; k=4000 -> 1,804 MB, 18.6 s. That is quadratic, so about 45 GB and about 8 min at k=20,000.
• Measured in the snapshot lane on Python 3.13, macOS arm64. find_near_duplicates on k identical fingerprints: k=1000 took 0.98 s with 113 MB traced peak; k=2000 took 4.41 s with 451 MB; k=4000 had an 1804 MB traced peak. A mixed list of 20K random fingerprints plus a 4K identical cluster took 6.32 s untraced (7,998,000 pairs). End-to-end audit_dataset on a 6000-row JSONL file of one repeated sentence (432,000 bytes): 17,997,000 pairs, 13.89 s, maxrss 4776 MB. With 1000 rows: 0.25 s, 228 MB. With…

Recommended fix. Stop storing (i,j) tuples. Count C(k,2) for identical fingerprints by multiplicity and dedupe across bands by checking 'first colliding band'. Add a memory regression test on a duplicate-heavy corpus. Correct the O(n x k) and 10M-row claims.

Acceptance criteria

• A regression test reproduces the failure scenario and asserts the corrected behaviour.
• Documentation listed above is corrected in English and in its Turkish mirror in the same PR.
• Every finding in this issue is resolved or explicitly closed with a reason.

_{Found by the October 2026 ForgeLM code and documentation review against commit cab2947. Code links point at that commit; line numbers may have moved since. Finding IDs (CR-…, DOC-…, TECH-…) are stable references for this backlog.}