MinHashFilter with hashSetSize >= 2 can drop a kept min hash when a token repeats

MinHashFilter hashes every token (typically 5-word shingles) and keeps, per hash and bucket, the hashSetSize lowest hash values; its javadoc says "You could have 1 hash and keep the 100 lowest values". The kept values live in FixedSizeTreeSet, a TreeSet with a capacity. When that set is full and a value below its largest one arrives, add first removes the largest (pollLast()) and then calls TreeSet.add. If the value is already in the set, because the token repeats, TreeSet.add does nothing: the set has lost its largest value and gained nothing, and the next new value, however large, fills the free slot. Only the N-th slot of a (hash, bucket) set can be wrong: the lowest N-1 values are always kept. No exception; the default hashSetSize of 1 is safe. The code dates from the filter's introduction (6.2.0), and a one-line guard fixes it.

• Min hash, bottom-k. Each token is hashed to a 128-bit value. With one hash the filter keeps the hashSetSize lowest values (a bottom-k sketch); with several hashes or buckets it keeps that many per hash and bucket. The overlap of two such sets estimates how similar the two texts' token sets are (Jaccard).
• FixedSizeTreeSet. The package-private TreeSet subclass that holds the kept values of one (hash, bucket), with a capacity of hashSetSize.

1. On the first incrementToken() the filter reads the whole input and adds every token's hash, repeats included, to the set of its hash and bucket (MinHashFilter.java:159-171, the insert at :168).
2. FixedSizeTreeSet.add (:333-345): if the set is full and the new value is not below last(), it returns false (:337-338); otherwise it calls pollLast() (:340) and then TreeSet.add (:343).
3. TreeSet.add leaves the set unchanged when the value is already in it. So a repeat of a kept value below the maximum removes the maximum and adds nothing: the set shrinks by one.
4. The next new value is added without any check because the set is no longer full, however large it is.
5. With hashSetSize 1 the only kept value is also the largest, so its repeat compares equal and is rejected at :337: the default is safe.

In "c a b c" the b is rejected while the set is full (b > a), and the final c then evicts a: the output is {c}.

• Who. Users of MinHashFilter or MinHashFilterFactory (SPI name minHash) with hashSetSize >= 2. The javadoc's first example is exactly that: "1 hash and keep the 100 lowest values". hashSetSize is a public constructor and factory parameter, validated only as > 0. Downstream engines wrap the factory as a min_hash token filter and pass hash_set_size through; one of them allows up to 10,000. How many applications use hashSetSize >= 2 is not known.
• Not affected. The default hashSetSize of 1, which published downstream example configurations also use. With many buckets (the default is 512) a bucket must first hold hashSetSize values before a repeat can do harm, so short documents in bucketed setups are less exposed (a code argument; not measured).
• Trigger. Ordinary text: a token or shingle that repeats while its (hash, bucket) set is full and whose hash is below that set's largest kept value. No crafted input; deterministic.
• Size. Only the N-th slot of each (hash, bucket) set can be wrong: the true lowest N-1 values are always kept, and the N-th slot is right, empty or holds a larger value (a code argument, then 1,464,843 exhaustive set sequences and 20,000 random end-to-end inputs). In the javadoc setting that is at most 1 of 100 values; "b a a" loses 1 of 2. With keep 2 and many buckets up to half the values can change: in a constructed worst case (1 hash, 64 buckets, keep 2, plain whitespace tokens) two texts with the same 2,000 words share 64 of 128 values, an overlap of 0.5 where the same word set should give 1.0 (no downstream similarity estimator was run).
• Effect. The indexed min-hash terms, and every near-duplicate or similarity estimate built on them, depend on how often and in what order shingles occur; a value that is not among the lowest can be indexed. No exception, the same with assertions on and off, and the index is well-formed.
• Not re-measured. The finder's synthetic-corpus rates (5 to 49 of 50 documents with a wrong signature, depending on the configuration) were not re-checked by a verifier, and how often real text hits the trigger was not measured.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<[␋䯍ᰂ閴ﭯ窨訍, 粌㪥轭炛熥鵴贇]> but was:<[␋䯍ᰂ閴ﭯ窨訍]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.analysis.minhash.TestMinHashRepeatedToken.testRepeatedTokenKeepsBothLowestHashes(TestMinHashRepeatedToken.java:33)

• Javadoc (MinHashFilter.java:38-40): "The number of hashes used and the number of minimum values for each hash can be set. You could have 1 hash and keep the 100 lowest values or 100 hashes and keep the lowest one for each." @param hashSetSize (:112): "the no. of min hashes to keep".
• TreeSet.add (JDK): "If this set already contains the element, the call leaves the set unchanged and returns false." FixedSizeTreeSet returns false too, although it has removed the largest element, contrary to that inherited contract (the filter's own call sites ignore the return value).
• Design discussion of LUCENE-6968 (now #8025), by one of the credited patch authors: "Let's start with 5 word shingles, one hash and keep the minimum 100 hash values. ... For a 100 word doc where all the shingles/words are the same we get one hash.", and the min set of one hash is "a random sample without replacement": bottom-k over distinct values. Nobody discusses a repeat arriving at a full set.
• Downstream documentation of the same parameters states frequency independence, for example: "it doesn't matter how many times a document contains a certain token, only that if it contains it or not."
• Tests. The upstream TestMinHashFilter feeds FixedSizeTreeSet only distinct values (testCollisions, testHashNotRepeated), and its bookkeeping assumes that add() == false removed nothing; testTokenStream3 (hashSetSize 10, two distinct shingles) never fills a set. No test asserts repeat-dependent output.
• History. No CHANGES or MIGRATE entry, javadoc caveat, issue or list thread documents a distinct-input precondition; the add body is unchanged in behaviour since the filter was added.

The strongest case for "intended": the javadoc never literally says "distinct"; FixedSizeTreeSet is package-private, so its TreeSet contract is internal; the default hashSetSize of 1 is immune and the published examples use 1; MinHash is an approximation anyway.

Why it fails: the output is not a function of the token multiset either. "c a c b" and "c a b c" have the same tokens with the same counts and give {c, b} and {c}; neither a set nor a multiset bottom-k reading lets the output depend on token order or keeps b, which is above the true 2 lowest of either. The design discussion and the downstream documentation state set semantics, and a safe default limits reach, not validity. The verifiers, the cross-model reviews and the adjudication found the intended-behaviour argument weak or unconvincing. Verdict: not intended, a defect.

Two fixes were run. The recommended one went through gradle in a scratch worktree at a9779ef3c193 with the module's tests; the alternative through the classpath runner only.

In FixedSizeTreeSet.add, return false before pollLast() when the full set already contains the value. add then honours the TreeSet.add contract, and each set is the exact bottom-N of the distinct values of its tokens.

     public boolean add(final E toAdd) {
       if (capacity <= size()) {
         final E lastElm = last();
-        if (toAdd.compareTo(lastElm) >= 0) {
+        if (toAdd.compareTo(lastElm) >= 0 || contains(toAdd)) {
           return false;
         } else {
           pollLast();

Trade-offs

• One extra O(log hashSetSize) lookup, only when the set is full and the value is below its largest. With the default hashSetSize 1 that is a lookup in a one-element set, made only for a new value below the kept one (a repeat or a larger value is rejected by the first comparison). Negligible either way.
• Signatures can change (to the correct ones) for documents whose repeated tokens left an incorrect final set, once re-analysed (a later token can repair the damage: "c b c a" ends correct, "c a c b" does not); until such documents are re-analysed or reindexed, a field mixes old and new signatures across segments. Worth a CHANGES line.

What the checks validated

• Stock main a9779ef3c193, gradle, seed DEADBEEF: the repro fails 4 of 5 with tests.asserts=true and =false (the hashSetSize 1 control passes).
• With the fix: the repro passes 5 of 5 with tests.asserts=true and =false; the whole lucene/analysis/common suite passes (340 classes, 1,914 tests, 0 failures, 18 skipped), including TestMinHashFilter 13 of 13; TestRandomChains (in lucene/analysis.tests; it can pick MinHashFilter; whether this seed did was not checked) passes 2 of 2 with one seed; ecjLint and checkGoogleJavaFormat pass for the module with the repro test in place.
• Both diffs, the one-line fix and the fix plus the repro test as a new test class, apply cleanly to a clean a9779ef3c193 tree.
• Classpath runner: the repro passes 5 of 5 with the fix shadowed, -ea and -da. Earlier in the hunt, the same fix shadowed: the finder's, the reproducer's, the devil's advocate's and both reviewers' tests (the reviewers' own runs used main ea57360912ed, whose minhash package is identical) and the 13 upstream tests pass, and the exhaustive model check reports 0 of 524,256 mismatches (92,628 without it).
• Not run: a benchmark (one extra lookup on a path that already calls last(), pollLast() and an insert).

Reject a value that is not below the largest of a full set; otherwise TreeSet.add first, and only when it added something, pollLast() if the set is over capacity.

public boolean add(final E toAdd) {
  if (capacity <= size() && toAdd.compareTo(last()) >= 0) {
    return false;
  }
  if (super.add(toAdd) == false) {
    return false; // already kept: the set is unchanged
  }
  if (size() > capacity) {
    pollLast();
  }
  return true;
}

Trade-offs

Avoids the extra lookup, but is a larger diff of an internal class, and the set briefly holds capacity + 1 elements.

What the checks validated

• This doc's JUnit 5 of 5, the finder's 3 of 3, the independent reproducer's 6 of 6 and the 13 upstream TestMinHashFilter tests pass with it shadowed onto the stock jars; the exhaustive model check reports 0 of 524,256 mismatches (92,628 without a fix).
• Not run through gradle.

Keep a per-document set of the terms already seen and skip repeats.

Trade-offs

Fixes it too, but costs memory per distinct token and duplicates what the bounded set should do.

Say in the javadoc that hashSetSize > 1 needs distinct tokens.

Trade-offs

Not a fix: the output would still depend on token order, and shingled text repeats by nature.

Method: bounded-exhaustive translation validation (the hunt's "semi-formal" tier), a hunt unit (analysis-common filters), 2026-10-26.

• The finder wrote an executable model of the class javadoc: per hash and bucket, the exact hashSetSize lowest distinct values, with its own murmur3 checked against a known-answer vector and 20,000 random inputs, and the filter's bucketing, rotation and term encoding mapped line by line.
• It compared the model with the stock MinHashFilter on every token sequence of length 0-6 over a 4-token alphabet, for hashCount {1, 2, 3} x bucketCount {1, 2, 3, 5} x hashSetSize {1, 2, 3, 4} x withRotation {false, true}: 524,256 checks, 92,628 mismatches, all with hashSetSize >= 2 and a repeated token.
• A second model that uses the FixedSizeTreeSet.add rule agreed with the filter on all 524,256 inputs, which pinned the root cause; with the one-line fix shadowed there were 0 mismatches.
• A public-API JUnit on the stock main jar then reproduced it ("b a a" against "b a", keep 2), with assertions on and off.