Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

MinHash › Accuracy Analysis: How Many Hash Functions Do You Need?

Michael BrenndoerferJanuary 10, 20263 min read

Language AI HandbookAll chapters

Part 20 of 67Data Curation

Chapter 143MinHash › Accuracy Analysis: How Many Hash Functions Do You Need?

Reading section 9 of 13 · Accuracy Analysis: How Many Hash Functions Do You Need? · 3 minSection 9 of 13 · 3 min

Section 9 of 13 · 3 min read

MinHash › Accuracy Analysis: How Many Hash Functions Do You Need?One section · Sections in this chapter9 / 13 ↓

Sections in this chapter13

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The estimation variance of MinHash follows directly from the properties of Bernoulli trials. Each of the $k$ positions in the signature independently agrees with probability $J(A, B)$ . The estimated similarity $\hat{J}$ is a sample mean of $k$ independent Bernoulli trials with success probability $J$ . By standard statistics:

\text{Var}\left(\hat{J}\right) = \frac{J(1-J)}{k}

and the standard deviation is:

\text{SD}\left(\hat{J}\right) = \sqrt{\frac{J(1-J)}{k}}

where:

$J$ : the true Jaccard similarity
$k$ : the number of hash functions
$\hat{J}$ : the MinHash estimate

The variance is maximized when $J = 0.5$ , giving $\text{Var} = 0.25/k$ . At the extremes ( $J = 0$ or $J = 1$ ), the variance is zero because the answer is known exactly with no uncertainty. For deduplication, the most error-prone regime is when you are near the threshold, which is typically around 0.7 to 0.9 for LLM training pipelines. At $J = 0.8$ , the variance is $0.8 \times 0.2 / k = 0.16 / k$ , somewhat lower than the worst case.

For $k = 128$ and $J = 0.5$ , the standard deviation is $\sqrt{0.25 / 128} \approx 0.044$ . A 95% confidence interval spans roughly $\pm 1.96 \times 0.044 \approx \pm 0.086$ . For deduplication decisions, you typically only care whether similarity exceeds a threshold (say, 0.8), not the exact value. An error of 0.09 around the threshold means pairs close to the threshold are uncertain, but pairs well above or well below are reliably classified.

In[17]:

Code

# Analyze the accuracy of MinHash estimation as a function of k
def minhash_std(j: float, k: int) -> float:
    """Theoretical standard deviation of MinHash similarity estimate."""
    return np.sqrt(j * (1 - j) / k)


k_values = [32, 64, 128, 256, 512]
jaccard_test = 0.5  # Worst-case variance at J=0.5

Out[18]:

Console

MinHash estimation standard deviation at J=0.5:
     k     Std Dev     95% CI width
------------------------------------
    32      0.0884           0.3465
    64      0.0625           0.2450
   128      0.0442           0.1732
   256      0.0312           0.1225
   512      0.0221           0.0866

At $k = 128$ hash functions, the 95% confidence interval width is roughly 0.17. At $k = 256$ , it narrows to about 0.12. In practice, 128 hash functions is the most common choice: it provides sufficient accuracy for deduplication decisions while keeping memory requirements manageable (512 bytes per document).

Confidence Intervals and Threshold DecisionsLink Copied

The practical question is not "how accurate is the estimate?" but "how likely are we to make the wrong deduplication decision?" If your threshold is $\tau = 0.8$ and two documents have true similarity $J = 0.85$ , what is the probability that the MinHash estimate falls below 0.8, causing a false negative?

With $k = 128$ and $J = 0.85$ , the standard deviation is $\sqrt{0.85 \times 0.15 / 128} \approx 0.031$ . The threshold is $(0.8 - 0.85) / 0.031 \approx -1.6$ standard deviations below the true value. The probability of a false negative is approximately $P(Z < -1.6) \approx 0.055$ , or about 5.5%. Increasing $k$ to 256 reduces this to about 1.5%.

This analysis explains why practitioners choose 128 to 256 hash functions rather than fewer: the marginal cost in memory and computation is small, but the reduction in deduplication errors is meaningful.