Tuning MinHash LSH Bands: Fixing Missed and Over-Grouped Near-Duplicates

An LSH configuration that misses obvious near-duplicates while over-grouping unrelated documents is a banding-tuning failure, and it is the most common way a near-duplicate detection subsystem produces indefensible clusters. The symptom is a mismatch between the similarity threshold everyone agreed on and the clusters the pipeline actually forms: drafts of the same contract land in separate clusters (missed), while boilerplate-heavy but substantively different documents merge (over-grouped). The root cause is almost always a band count chosen without reference to the target threshold, placing the S-curve’s transition in the wrong place. This guide isolates the banding math and delivers a tuning procedure that positions the S-curve at the exact similarity you want to catch.

Diagnostic Log Signatures

The defect shows up when cluster quality is audited against known near-duplicate pairs. Capture it verbatim.

[INFO] LSH config: num_perm=128, bands=8, rows=16, target_threshold=0.80
[WARN] s_curve_midpoint=0.917 (bands=8,rows=16) but target_threshold=0.80
[ERROR] missed_pair DOC-04120/DOC-04121 true_sim=0.83 candidate=false
[ERROR] over_group cluster=C-559: 41 docs, min_pairwise_sim=0.44
[CRITICAL] Banding mismatch: S-curve midpoint 0.12 above the agreed threshold

Symptom checklist — two or more confirm a banding mismatch:

• The LSH S-curve midpoint (computed from bands and rows) differs materially from the agreed similarity threshold.
• Document pairs with known true similarity above the threshold are not generated as candidates (false negatives).
• Clusters contain pairs whose actual similarity is well below the threshold (false positives).
• Increasing the band count sharply increases cluster sizes; decreasing it drops known near-dupes.
• The same collection re-clustered with a different band count produces very different groupings, though the threshold was unchanged.

Root-Cause Breakdown

Every banding mismatch traces to bands and rows not being derived from the threshold.

1. Band count picked arbitrarily. With a signature of $k = b \times r$ values, the probability a pair with true similarity $s$ becomes a candidate is $P(s) = 1 - (1 - s^r)^b$. The S-curve’s midpoint — where $P \approx 0.5$ — sits near $(1/b)^{1/r}$. Choosing $b$ and $r$ without solving for the threshold puts that midpoint in the wrong place, so the pipeline’s effective threshold is not the one on paper.
2. Too few bands (rows too high). Pushes the midpoint high, so only very-high-similarity pairs become candidates and genuine near-duplicates just above the threshold are missed — false negatives.
3. Too many bands (rows too low). Pushes the midpoint low, so weakly similar documents become candidates and cluster together — false positives and over-grouping, especially with boilerplate.
4. Signature length not matched to the split. $k$ must be divisible by $b$, and a small $k$ limits how sharply the S-curve can be tuned; too few permutations make the curve shallow so precision and recall cannot both be high.

Remediation Architecture

Derive the banding from the threshold, verify the S-curve, and validate against labeled pairs.

1. Solve for the target threshold. Pick the threshold $t$, then choose $b$ and $r$ (with $b \times r = k$) so the S-curve midpoint approximates $t$: $t \approx (1/b)^{1/r}$. Search the divisor pairs of $k$ for the combination whose midpoint is closest to $t$ with an acceptably steep transition.
2. Verify the curve numerically. Compute $P(s)$ at $s = t \pm 0.1$ and confirm the candidate probability is high above the threshold and low below it — the S-curve is doing its job.
3. Validate against labeled pairs. Run the chosen configuration over a labeled set of known near-duplicate and non-duplicate pairs, and measure candidate-generation recall and precision at the threshold.
4. Increase $k$ if the curve is too shallow. If no divisor pair gives both high recall and high precision, raise the permutation count to sharpen the transition.

The S-curve below shows how the band count moves the transition relative to the target threshold.

Band-tuning implementation

The routine computes the candidate probability, searches the divisor pairs of the signature length for the banding whose S-curve midpoint is closest to the target threshold, and reports the curve at the threshold neighborhood. It compiles and runs on the standard library.

import math
from dataclasses import dataclass
from typing import List, Tuple


def candidate_probability(s: float, bands: int, rows: int) -> float:
    """P(pair with true similarity s becomes an LSH candidate)."""
    return 1.0 - (1.0 - s ** rows) ** bands


def s_curve_midpoint(bands: int, rows: int) -> float:
    """Approximate similarity where candidate probability crosses ~0.5."""
    return (1.0 / bands) ** (1.0 / rows)


@dataclass
class Banding:
    bands: int
    rows: int
    midpoint: float
    p_below: float      # candidate prob 0.1 below threshold (want low)
    p_above: float      # candidate prob 0.1 above threshold (want high)


def divisor_pairs(k: int) -> List[Tuple[int, int]]:
    return [(b, k // b) for b in range(1, k + 1) if k % b == 0]


def tune_banding(num_perm: int, threshold: float) -> Banding:
    """Pick the (bands, rows) split of num_perm whose S-curve midpoint is
    closest to the target threshold, breaking ties toward a steeper curve."""
    best: Banding | None = None
    for bands, rows in divisor_pairs(num_perm):
        if rows < 2 or bands < 2:
            continue  # degenerate splits give no useful S-curve
        mid = s_curve_midpoint(bands, rows)
        cand = Banding(
            bands, rows, mid,
            p_below=candidate_probability(max(0.0, threshold - 0.1), bands, rows),
            p_above=candidate_probability(min(1.0, threshold + 0.1), bands, rows),
        )
        if best is None or abs(cand.midpoint - threshold) < abs(best.midpoint - threshold):
            best = cand
    if best is None:
        raise ValueError(f"no valid banding for num_perm={num_perm}")
    return best


def steep_enough(b: Banding, min_gap: float = 0.6) -> bool:
    """The curve must separate below-threshold from above-threshold clearly."""
    return (b.p_above - b.p_below) >= min_gap

Verification Checklist

Confirm the banding matches the threshold before clustering a production collection:

• The chosen bands and rows multiply to the signature length, and both are at least 2.
• The S-curve midpoint is within a small tolerance of the agreed similarity threshold.
• Candidate probability is high (near 1) at threshold + 0.1 and low (near 0) at threshold − 0.1 — the curve is steep enough.
• Candidate-generation recall and precision measured on a labeled pair set meet the agreed targets.
• The num_perm, bands, rows, and threshold are version-controlled and logged with every clustering run.

Conclusion

LSH banding is not a free parameter — it is the effective similarity threshold, encoded in the shape and position of the S-curve. Missed near-duplicates and over-grouped clusters both come from choosing bands and rows without solving for the target threshold, which leaves the curve’s transition in the wrong place. Derive the banding from the threshold so the midpoint lands where you want it, verify the curve is steep enough to separate below from above, validate against labeled pairs, and raise the permutation count if the curve is too shallow. Version-control the result, and the near-duplicate layer clusters exactly at the similarity everyone agreed to — reproducibly and defensibly.

Frequently Asked Questions

How do I choose the band count for a given similarity threshold?

Solve for it rather than guessing. For a signature of length $k = b \times r$, the S-curve midpoint is approximately $(1/b)^{1/r}$, so search the divisor pairs of $k$ for the $(b, r)$ whose midpoint is closest to your threshold. For a 128-value signature and a 0.8 threshold, that lands around a moderate band count; the tuning routine picks it automatically and reports the candidate probabilities just below and above the threshold so you can confirm the curve is steep enough.

Why do more bands cause over-grouping?

More bands means fewer rows per band, and a pair only has to match in one band to become a candidate. With short bands, even weakly similar documents have a decent chance of matching some band by coincidence, so the S-curve shifts left and low-similarity pairs become candidates. Those pairs then cluster, especially when documents share boilerplate, producing large clusters whose members are not actually near-duplicates.

Can I fix a shallow S-curve without changing the threshold?

Yes — increase the number of hash permutations. The steepness of the S-curve is limited by the signature length: a longer signature allows a band/row split that transitions more sharply between “below threshold, rarely a candidate” and “above threshold, almost always a candidate.” If no divisor pair of your current $k$ gives both high recall and high precision at the threshold, raising $k$ from 128 to 256 gives the tuner more room to place a steep curve at the same threshold.

Related

• Near-Duplicate Detection — the subsystem whose banding this tunes.
• SimHash vs MinHash for Textual Near-Dupes — the alternative primitive and its own tuning.
• Similarity Threshold Configuration — governing the threshold this banding implements.
• Hash-Based Deduplication Strategies — the exact-match stage upstream of near-duplicate clustering.

For the theory, see the Stanford Mining of Massive Datasets, chapter 3 on finding similar items, and the datasketch MinHash LSH documentation.

Up one level: Near-Duplicate Detection — the subsystem that clusters similar documents at scale.