How wrong is the quoted PDQ false-positive rate?
Code and results: github.com/castacu0/pdq-census (MIT; results CC BY 4.0). Hash file of record SHA-256 0a19493d…d17d4. Every number below regenerates from committed code with its seed and command.
The question
Perceptual hashes (PDQ, pHash, Blockhash) are how platforms and hotlines recognise known abuse imagery without storing it. Meta's PDQ declares a match at Hamming distance 31 of 256 bits. The false-positive rate at that threshold is the number that decides how many innocent reports a reviewer sees, and it is almost always quoted from a model rather than measured.
The two quoted figures:
| Model | P(unrelated pair ≤ 31 bits) |
|---|---|
| Independent uniform bits, 2⁻²⁵⁶ · Σ C(256,k) | 8.3 × 10⁻³⁸ |
| Gaussian fit to the published spread (μ 0.5000, σ 0.0321) | 1.9 × 10⁻³² |
Both assume something false about natural images. PDQ bits are signs of DCT coefficients, and low frequencies in photographs are correlated, so the tail has structure that neither model has. McKeown and Buchanan (DFRWS EU 2023, arXiv:2212.08035) measured about 50 million random pairs on MIRFLICKR-1M and reported a closest unrelated pair at 10 bits, which would already put the rate at or above 2 × 10⁻⁸. I wanted the rate itself, not a floor.
What I did
Reproduction gate. Before any large run, the pipeline had to reproduce McKeown and Buchanan's Table 3 for PDQ. On COCO val2017 (19.96 million random pairs) it gives mean 0.5000 and σ 0.0321 against the published 0.5000 / 0.0321; on Flickr8k, 0.4999 / 0.0325. pHash and Blockhash do not reproduce to three decimals on either corpus, even with implementations checked bit for bit against imagehash and the Commons Machinery reference. Their published moments are corpus-dependent and should not be used as an acceptance test. I say so because my own README had claimed otherwise.
Hash once, never store the corpus. All four COCO 2017 splits, 287,360 photographs, 46.9 GB streamed through a disposable container and discarded. Only hashes, a manifest and a checksum are kept. The harness refuses to run on a path inside the repository and requires an explicit benign-corpus flag. It has never been pointed at abuse material and is built so that it cannot be.
Exhaustive census. Instead of sampling pairs, a multi-index search with a fixed bit permutation finds every pair within the threshold among all 41,176,033,935 distinct pairs (286,971 images after PDQ's quality floor). It is exact by the pigeonhole principle and checked against brute force in the tests.
Three side experiments on the same hashes: error correlation across the three algorithms, the cost and benefit of dihedral (flip and rotation) indexing, and recall through a realistic laundering chain (platform recompress, screenshot, repost). Machine time about 2.7 hours on 4 vCPUs, no GPU, cloud spend zero.
What came out
| Quantity | Measured | What was assumed |
|---|---|---|
| PDQ pairs ≤ 31 bits, exhaustive | 392 of 41.2 B: 9.5 × 10⁻⁹ per comparison (Poisson 95%: 8.6 to 10.5 × 10⁻⁹) | 8.3 × 10⁻³⁸ or 1.9 × 10⁻³² |
| Of which flagged by PDQ alone | 8: 1.9 × 10⁻¹⁰ (95%: 0.8 to 3.8 × 10⁻¹⁰) | |
| Random pairs ≤ 31 bits, 99.9 M | 0, so < 3.0 × 10⁻⁸ (rule of three); closest pair 38 bits | published closest pair 10 bits |
| Error correlation, PDQ vs pHash | Pearson r 0.327; joint 0.1st-percentile tails 22× more common than if independent | independent layers |
| PDQ vs Blockhash | r 0.090, lift 2.4 | |
| Dihedral indexing, false-positive multiplier | 1.01 (278 vs 276 pairs, exhaustive) | 8× |
| Recall against a mirrored copy | plain PDQ 0.0%; DCT-domain dihedral 99.98% (5,105 of 5,106) | |
| Laundering chain recall, 5,106 images | PDQ 100%, pHash 100%, Blockhash 99.98% |
Three readings.
The quoted rate is wrong by 23 to 29 orders of magnitude, depending on which quoted number you start from. The measured per-comparison rate sits between 1.9 × 10⁻¹⁰ and 9.5 × 10⁻⁹. Which end is right depends on whether the 360 pairs that PDQ, pHash and Blockhash all flag are errors or repeated uploads; COCO is known to contain repeats, and 137 pairs sit at distance zero. The same ambiguity hangs over the published closest unrelated pair at 10 bits, which on this evidence is far more likely a duplicate photograph than a collision. My own earlier floor of 2 × 10⁻⁸, derived from that published minimum, was therefore too high, and I have corrected it.
The corpus size does the damage, not the algorithm. A query against a 50 million hash corpus is 50 million comparisons. At 9.5 × 10⁻⁹ that is a 38% chance of at least one false hit per query; at 1.9 × 10⁻¹⁰ it is 1%. Either way the review queue, not compute, is the budget, and nothing should auto-file.
Layering buys robustness, not a multiplicative drop in false positives. PDQ and pHash are both DCT descendants and fail together in exactly the tail where fusion operates. A second DCT hash is nearly redundant; a signal that fails differently (Blockhash here, an embedding in production) is what buys independence. And the long-assumed 8× false-positive cost of flip-and-rotate indexing is, measured, 1%.
What this does not show
The corpus of record is COCO 2017, not MIRFLICKR-1M, so the comparison with the published study is across corpora. The PDQ moments match to four decimals, which is evidence the tail transfers, not proof. 286,971 images give far fewer independent pairs than the 41 billion suggests; the effective sample size sits closer to N than to N²/2. The MIRFLICKR-1M run is a one-command overnight job and is next. Nothing here says anything about first-generation synthetic imagery: a hash answers "have we seen this before", and a freshly generated image is in no corpus.
Why it matters beyond hashing
Thresholds for abuse detection are being written into platform policy and law on numbers nobody re-ran. The pattern (a clean closed-form rate, a Gaussian correction, and a measured reality many orders away) is not specific to perceptual hashes. It is the failure I expect to find, at smaller magnitudes but with the same consequences, in the quoted false-positive rates of learned safety classifiers. Measuring it the same way is what I want to do next.
Sources: McKeown & Buchanan 2023, arXiv:2212.08035 · PDQ reference, facebook/ThreatExchange · pdqhash 0.2.8, imagehash 4.3.2, Commons Machinery blockhash. The pipeline was built and run with Claude Code under my design and review; every result was regenerated and checked by me from the committed code.