SweetSpotSimilarity returns a NaN length norm for fields longer than 2^30 terms

SweetSpotSimilarity (lucene/misc) documents its length norm as 1/sqrt( steepness * (abs(x-min) + abs(x-max) - (max-min)) + 1 ) and says it degrades to 1/sqrt(x) with the default factors (min = max = 1, steepness 0.5). lengthNorm evaluates the sum in int, so with the defaults 2·(x − 1) wraps negative from x = 2^30 + 1 and the norm is NaN.

Through an index, lengthNorm sees only the 255 decoded norm lengths, so every field length of 1,073,741,848 or more (norm bytes 248-255) scores NaN. Lucene accepts such lengths: the indexing chain rejects only an int overflow, and one token with custom term frequency 1.1e9 on a DOCS_AND_FREQS field reaches it (so do about a billion ordinary tokens). The NaN document is never collected, and because a NaN block maximum never passes the competitive check, top-k search also skips competitive documents in the same 256-document postings block and 8,192-document skip range. Computing the distance in long fixes it. The int expression dates from the class's first version (2006); it is silent even with assertions on since 10.1.0. Low impact: an opt-in class and a 2^30-scale field.

1. Int arithmetic. SweetSpotSimilarity.lengthNorm (SweetSpotSimilarity.java:110-120): final int l = ln_min; final int h = ln_max; (:112-113), then (float) (1.0f / Math.sqrt((s * (float) (Math.abs(numTerms - l) + Math.abs(numTerms - h) - (h - l))) + 1.0f)) (:116-119). The sum is int; the cast to float comes after it.
2. It wraps. With the defaults (:36-38) the sum is 2·(x − 1): 2,147,483,646 at x = 2^30 (correct norm), -2,147,483,648 at x = 2^30 + 1, so 0.5 · sum + 1 is negative, Math.sqrt returns NaN and so does lengthNorm.
3. Decoded lengths. computeNorm stores SmallFloat.intToByte4(length) (Similarity.java:151-161); TFIDFSimilarity.scorer fills normTable[i] = lengthNorm(byte4ToInt(i)) for i = 1..255 (TFIDFSimilarity.java:427-446) and score reads it (:470). Byte 247 decodes to 1,006,632,984 (finite), byte 248 to 1,073,741,848 (NaN), byte 255 to 2,013,265,944 (NaN). A field of exactly 2^30 + 1 terms encodes to byte 247 and is unaffected.
4. Legal length. IndexingChain sums the field length with Math.addExact (1 per token for DOCS_AND_CUSTOM_FREQS, the custom frequency otherwise) and throws "too many tokens" only on an int overflow (IndexingChain.java:2053-2064). TermFrequencyAttribute names DOCS_AND_FREQS and sets no upper bound (TermFrequencyAttribute.java:23-34).
5. Not collected. BatchScoreBulkScorer collects only if (score >= scorable.minCompetitiveScore) (BatchScoreBulkScorer.java:53-55): false for NaN.
6. Block skipped. MaxScoreCache.computeMaxScore takes Math.max over the block's impacts (MaxScoreCache.java:84-88), and Math.max returns NaN if either argument is. ImpactsDISI keeps a block only if (maxScore >= minCompetitiveScore) (ImpactsDISI.java:80-82) and getSkipLevel climbs to the highest level whose maximum fails that test (MaxScoreCache.java:137-158), so the 256-doc block and the 8,192-doc level-1 range of the default postings format (Lucene104PostingsFormat.java:343-351) are skipped. In the 10,000-document example, doc 50 is collected before pruning starts (after 1,000 hits) and doc 9000 lies outside that range; docs 2010, 3000 and 7000 lie inside it. There the raised bar reaches the term scorer at doc 1024 and one skip goes from doc 1024 to doc 8192, so doc 2000 itself is skipped before it is scored; step 5 is what drops it when every hit is collected.

int arithmetic wraps consistently, so an intermediate overflow alone is harmless: the result is wrong only when the true value 2·(x − max) (for x ≥ max ≥ min) exceeds Integer.MAX_VALUE, i.e. x ≥ max + 2^30 (executed probe):

For the decoded lengths the wrapped value lies between -2^31 and about -2.7e8, so the norm is NaN for any steepness above about 4e-9; steepness 0 never gives NaN. With the defaults, norm bytes 248-255 are NaN, and bytes 1-247 are finite and match ClassicSimilarity to within one float step (243 of 247 identical; bytes 226, 229, 234 and 241 differ by one float step). Byte 0 is not a legal norm ("norm is never 0", Similarity.java:205); its table entry 1f / normTable[255] is NaN too, but by that contract a scorer never receives norm 0.

• Who is hit. Applications that score a normed field with SweetSpotSimilarity and index at least one document whose field length is at least 1,073,741,848 (with the defaults; other factors from max + 2^30). Routes: custom term frequencies on a DOCS_AND_FREQS field (TermFrequencyAttribute, or DelimitedTermFrequencyTokenFilter input such as a|1100000000), or about a billion ordinary tokens (an independent verifier indexed 1,073,741,848 tokens in about 45 s and reproduced it). The 10.5 option DOCS_AND_CUSTOM_FREQS counts tokens instead of summing frequencies, so it closes the custom-frequency route, not the ordinary-token one.
• What goes wrong. Silently: the long document scores NaN and never appears in scored results (in the example it should be the top hit), and default top-k search (pruning after 1,000 hits) also skips the competitive documents of the same term in its 256-document block and 8,192-document skip range, returning weaker hits in their place. The skipping reach depends on the postings format: on 9.12.3 a different set is lost.
• Not affected. Non-scoring matching (filters, count(), constant-score queries). The stored norm byte is the encoded length, which is correct, so a fix needs no reindex (since 7.0).
• Likelihood: contrived. A 2^30-scale length in one field does not happen by accident, and maintainers ask users of custom frequencies to keep "reasonable values" (#11086). Low priority, but a real defect in the documented formula.

The test calls the public lengthNorm with 2^30 + 1, the first length that overflows with the defaults. Through an index the first affected length is 1,073,741,848 (norm byte 248); the end-to-end effects (the NaN document dropped, other hits skipped) follow from the NaN norm and are shown by the larger tests of the study, summarised under "Observed" below.

As the regression test it can go in as is: with the fix and this file in place, :lucene:misc:check -x test (google-java-format, ecj lint, forbidden APIs, license checks) passes. It can also become a method of TestSweetSpotSimilarity.

TestSweetSpotLengthNormOverflow > testDefaultLengthNormAboveTwoToThe30 FAILED
    java.lang.AssertionError: expected:<3.0517578E-5> but was:<NaN>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:C95E8C6BB254070C]:0)
        at junit@4.13.2/org.junit.Assert.fail(Assert.java:89)
        at junit@4.13.2/org.junit.Assert.failNotEquals(Assert.java:835)
        at junit@4.13.2/org.junit.Assert.assertEquals(Assert.java:577)
        at junit@4.13.2/org.junit.Assert.assertEquals(Assert.java:701)
        at org.apache.lucene.misc.TestSweetSpotLengthNormOverflow.testDefaultLengthNormAboveTwoToThe30(TestSweetSpotLengthNormOverflow.java:26)
:lucene:misc:test (FAILURE): 1 test, 1  failure

# the same assertion with -Ptests.asserts=false, and on the 10.6.0 release jars (assertions on and off)

# end to end, the 10,000-document example (main 645d4fe14a20 jars, the same with -ea and -da):
SweetSpotSimilarity: count=10000 explain(2000)=NaN
  default search(q, 7):  [50:1.0 9000:1.0 0:0.5 1:0.5 2:0.5 3:0.5 4:0.5 ]
  exhaustive top 7:      [50:1.0 2010:1.0 3000:1.0 7000:1.0 9000:1.0 0:0.5 1:0.5 ]
  exhaustive hits:       9999
ClassicSimilarity (and SweetSpotSimilarity with the fix): count=10000 explain(2000)=1.0121535
  default search(q, 7):  [2000:1.0121535 50:1.0 2010:1.0 3000:1.0 7000:1.0 9000:1.0 0:0.5 ]
  exhaustive hits:       10000

# norm table of the default SweetSpotSimilarity
byte 247 decodes to 1006632984: SweetSpot 3.151842E-5, Classic 3.151842E-5
byte 248 decodes to 1073741848: SweetSpot NaN, Classic 3.0517578E-5
byte 255 decodes to 2013265944: SweetSpot NaN, Classic 2.2286888E-5

• The contract. "Implemented as: 1/sqrt( steepness * (abs(x-min) + abs(x-max) - (max-min)) + 1 )" and "This degrades to 1/sqrt(x) when min and max are both 1 and steepness is 0.5" (SweetSpotSimilarity.java:97-102), the defaults (:36-38).
• The upstream test asserts that equivalence with ClassicSimilarity for lengths 1 to 999 only (@Nightly testSweetSpotComputeNorm, "base case, should degrade", TestSweetSpotSimilarity.java:72-86).
• Finite scores. BaseSimilarityTestCase checks that "scores are non-negative and finite" for every norm value (LUCENE-6896, -7997, -8010), but TestSweetSpotSimilarity extends LuceneTestCase. SimScorer#score must not decrease when freq increases "for any value of norm that may be produced by computeNorm", and must not increase when the unsigned norm increases "for any legal freq" (Similarity.java:207-213); NaN satisfies neither, since every comparison with NaN is false. TopScoreDocCollector says NaN and NEGATIVE_INFINITY "are not valid scores" (TopScoreDocCollector.java:30-31).
• Legal input. IndexingChain accepts the length (Math.addExact, :2053-2064). Michael McCandless on #9990 (LUCENE-8947): "users must not try to write too many, too large custom term frequencies such that their sum overflows a Java int in a single field / document"; 1.1e9 is inside that bound. The ordinary-token route needs no custom frequency at all.
• History. The int expression is in the class's first version (LUCENE-577, 2006); no javadoc, CHANGES entry, test or issue sets a length limit below Integer.MAX_VALUE.

The strongest case (verifiers and a cross-model review): SweetSpotSimilarity is an expert, legacy class in lucene/misc; a billion-term field is absurd; and custom term frequencies are the user's responsibility: "If you use custom term frequencies (expert feature), then it is your responsibility to have reasonable values. Otherwise, things can easily overflow, break scoring" (Robert Muir, #11086, won't fix). Once a score is NaN, the collector's behaviour is documented.

Why it fails: #11086 is about bypassing the int-sum check, and the same comment names the bound ("less than int32"); this trigger is inside it, and the ordinary-token route needs no expert feature. The NaN arises in the similarity, whose own javadoc promises a finite value that the parent class computes. Rarity lowers the priority; it does not make the NaN intended.

The recommended fix was run in a scratch worktree of 645d4fe14a20 (OpenJDK 25.0.3), removed afterwards. "Closest suite" means TestSweetSpotSimilarity, the class's own test, run with -Ptests.nightly=true so that its @Nightly length-norm test runs too. LFV-413 (a plateau breaks norm monotonicity in the same method) is a different defect: this fix does not fix it, and its redesign would remove this overflow as a side effect.

Declare l and h as long in lengthNorm, so the whole expression is evaluated in long; numTerms is an int, so abs(x-min) + abs(x-max) stays below 2^33. The cast to float follows as before. Since 7.0 the norm byte stores the encoded length, which was always correct, so the fix changes only the search-time norm table: no reindex.

   public float lengthNorm(int numTerms) {
-    final int l = ln_min;
-    final int h = ln_max;
+    // long, not int: abs(x-min) + abs(x-max) can exceed Integer.MAX_VALUE for long fields
+    final long l = ln_min;
+    final long h = ln_max;
     final float s = ln_steep;

Trade-offs

• Values. With the fix the default norm table equals ClassicSimilarity at 250 of 255 bytes; bytes 226, 229, 234 and 241 (unchanged from today) and byte 252 (2.49175E-5 vs 2.4917497E-5) differ by one float step, from the existing float conversion of the sum; lengths 1-999 are all identical.
• Cost: negligible: 255 evaluations when a scorer is built, as today (TFIDFSimilarity.java:442-446); not measured.

What the checks validated

• Gradle on a scratch worktree of 645d4fe14a20: stock fails the repro with assertions on and off; with the fix it passes with assertions on and off.
• TestSweetSpotSimilarity with -Ptests.nightly=true: 3 of 3 pass, including the @Nightly testSweetSpotComputeNorm (16 s), which no earlier run had enabled (stock passes it too).
• The whole lucene/misc test task: 317 tests, 9 skipped, 0 failures (the repro included). :lucene:misc:check -x test passes with the repro in place.
• With the fixed class shadowed into the jars: the independent reproduction's end-to-end test passes 8 of 8; the 10,000-document example gives the ClassicSimilarity hits; the study's 6-test JUnit and the ordinary-token test passed with the same fix on a9779ef3c193.
• Not run: other JDKs, x86, the full Lucene test suite.

Cast to double before the subtraction, e.g. Math.abs((double) numTerms - l) + ....

Trade-offs

Also overflow-free and closer to the javadoc formula. For the default factors, keeping the sum in double (dropping the (float) cast) reproduces ClassicSimilarity exactly at all 255 bytes and all lengths 1-999, since 0.5 · 2(x − 1) + 1 = x is exact in double; keeping the (float) cast gives the same values as the long fix (a standalone probe of both variants). Neither changes the nightly comparison for lengths 1-999; for other factors a norm may move by about one float step versus today. Not run through gradle.

TFIDFSimilarity.scorer could throw when lengthNorm returns a non-finite value.

Trade-offs

Catches any subclass with the same kind of bug, but turns silent wrong results into a search-time failure, and still needs the long fix. Not run.

Method: semi-formal (bounded-exhaustive translation validation of the real jar against exact semantics).

• Harness FormulaTV, part A1: lengthNorm on the stock jar against the javadoc formula evaluated in BigDecimal, for n = 1..1000 and the 255 decoded norm lengths x 8 plateaus x 6 steepness values: 60,240 checks, 334 mismatches, 305 of them NaN, all at norm bytes 248-255; the rest are rounding differences of at most 1.2 ulp. Part A1b ("degrades to 1/sqrt(x)"): 8 mismatches in 1,255, all NaN at bytes 248-255.
• The finder read the root cause in the code and bridged it end to end with one custom term frequency; an independent reproducer wrote its own test from the claim alone, and a devil's advocate reproduced it with ordinary tokens.