SynonymQuery adds boosted term frequencies in float in iteration order, so identical documents score differently and explain() differs from the hit score

SynonymQuery scores "the sum of all term frequencies for the document", each frequency multiplied by its per-term boost. SynonymScorer.freq() adds boost * freq in a float running sum, in the order of the disjunction's topList(), and that order follows the heap layout, which depends on how the iterator reached the document. Float addition is not associative, so with three or more terms whose boosted freqs do not add exactly, the same document gets slightly different scores on different paths: identical documents in one search score 1-2 ulps apart and come back out of doc-id order, and explain(), which builds a fresh scorer and calls advance(doc), reports a value the hit did not get. Separately, the max-score bound comes from the merged impacts, an exact integer sum of per-norm impact freqs (boosted ones rounded up); above 2^24 occurrences in one field the float sum can round above it, so score() exceeds getMaxScore() and pruned and exhaustive top-k disagree. It came with per-term boosts in 8.1.0 (LUCENE-8652) and is in every release up to 10.6.0 and main. CombinedFieldQuery has the same float sum (LFV-277, merged here). Summing in double and rounding once removes both symptoms in every executed probe.

1. SynonymScorer.freq() walks disjunctionDisi.topList() and keeps a float running sum: float freq = w.freq(); ... freq += w.freq(); (SynonymQuery.java:610-617 at 645d4fe14a20), where DisiWrapperFreq.freq() is the float product boost * pe.freq() (:659-661).
2. topList() returns the lead iterators' list or prepends the matching other iterators (DisjunctionDISIApproximation.java:196-218); DisiPriorityQueueN.topList() walks heap[0], then the heap[1] and heap[2] subtrees (DisiPriorityQueueN.java:71-84). The order is the heap layout, a product of the iteration history.
3. A search drives the scorer with nextDoc(). SynonymWeight.explain builds a fresh scorer and calls advance(doc) (SynonymQuery.java:246-249), then freq() (:253). The two paths can add the same three products in different orders.
4. It needs at least three of the query's terms matching the same document (two float operands commute) and boosted freqs that do not add exactly. With all boosts 1 and a summed freq below 2^24 the sums are exact.

• Minimal input (four identical documents a b c, BM25, Synonym(a^0.2, b^0.2, c^0.3)): the nextDoc() path scores doc0 = doc3 = 0.038817033 and doc1 = doc2 = 0.038817026 (freq 0.7); a fresh advance(doc) scores all four 0.038817033 (freq 0.70000005). The exact sum of the three floats, 0.7000000178813934..., lies exactly halfway between the floats 0.7 and 0.70000005; rounded once (the fix) it is 0.70000005, and all four hits score 0.038817033.
• How common in its setup: three-term queries built through QueryBuilder from tokens with one-decimal boosts 0.1..0.9 (all 729 triples), 60 documents, BM25: 568 of 729 fail CheckHits.checkExplanations, the first being Synonym(f:a^0.1 f:b^0.1 f:c^0.1); 0 with the fix.

mergeImpacts bounds each norm's frequency with the exact long sum of the (ceil-boosted) impact freqs (SynonymQuery.java:503, :543-564), and MaxScoreCache converts that int to float once (MaxScoreCache.java:80). The scorer converts each freq to float first and sums in float, which above 2^24 can round above the bound. ClassicSimilarity, boosts 1, 600 documents: doc 300 holds a x (2^24+3) and b x 3; (float) (2^24+3) is 2^24+4, and adding 3 rounds to 2^24+8, while the bound is the exact 2^24+6. Doc 300 scores 1.032795 > getMaxScore(511) = 1.0327948; a pruned top-1 search returns doc 0 (a x (2^24+6), 1.0327948) and an exhaustive one doc 300. Under exact arithmetic the two tie, so the pruned answer is the exact one; the defect is the broken bound and the disagreement. In the tested BM25 settings (k1=1.2/b=0.75 and k1=1e7/b=1) a scan of freqs 2^24..2^24+63 plus 1..7 found no score change, under that probe's statistics.

CombinedFieldScorer.freq() sums freq * weight in float over the same kind of topList() (CombinedFieldQuery.java:424-434), and its explain also uses a fresh advance(doc) (:323-326). With 3 or more matching fields and non-dyadic weights such as 1.1 and 1.2, explain() can differ from the hit by 1 ulp; no ranking change was shown there. Its if (freq < 0) // overflow check, inherited from the old int loop, cannot fire for a float sum.

• Who is exposed. A scoring SynonymQuery with three or more terms matching the same document and per-term boosts below 1: from SynonymQuery.Builder#addTerm(term, boost), or since 8.5.0 (LUCENE-9171) from QueryBuilder, which copies each stacked token's BoostAttribute into the query (QueryBuilder.java:385-395, :603-609), for example from DelimitedBoostTokenFilter ("foo|0.7"). Default IndexWriterConfig, codec, BM25 and IndexSearcher; ordinary small documents; any index size.
• What users see. Equally relevant documents score 1-2 ulps apart within one search and come back out of doc-id order; explain() reports a value the hit did not get. Test suites that compare explain() with the score exactly, as Lucene's CheckHits.checkExplanations does, fail. Nothing throws or logs.
• Not affected. Which documents match: without scores (FILTER, MUST_NOT, ConstantScoreQuery, the query cache) createWeight builds a weight over TermQuery SHOULD clauses instead (SynonymQuery.java:181-195), which never runs this code. Single-term queries use a TermScorer.
• The bound part is rare. More than 2^24 occurrences of the synonym terms in one field of one document and a similarity such as ClassicSimilarity or LMDirichlet; TOP_SCORES and COMPLETE then return different top hits, so CheckHits.checkTopScores fails. AssertingScorer (score <= getMaxScore(docID()), AssertingScorer.java:130) checks the bound only after advanceShallow, so it trips only in tests that shallow-advance the scorer, not in ordinary searches.
• How likely. Common in its setup, tiny in effect: priority low (registry: minor, common, low).

ByteBuffersDirectory, a plain IndexWriterConfig (with TestUtil.getDefaultCodec(), so the test framework's random codec stays out), StandardAnalyzer and a plain IndexSearcher; one segment; nothing random, one thread; the same result for every seed (DEADBEEF and 1234ABCD checked). The test asserts only the exact explain == score rule of CheckHits.verifyExplanation.

The summed freqs are 1 ulp apart (0.7 vs 0.70000005) and the scores 2 float ulps (0.038817026 vs 0.038817033), as the in-code comment says.

It shows the order symptom under default settings. The bound symptom (more than 2^24 occurrences) and the CombinedFieldQuery copy come from the same kind of sum; they were executed in the study and are described in the text, not added as more tests.

Regression test: this same test, as one more method of the existing TestSynonymQuery. It passes with the recommended fix.

cp $REPRO/TestSynonymFreqSumOrder.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests TestSynonymFreqSumOrder -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (the same failure)

# gradle, scratch worktree at 645d4fe14a20, unchanged source, -Ptests.seed=DEADBEEF (assertions on; the same with -Ptests.asserts=false)
TestSynonymFreqSumOrder > testExplainEqualsHitScore FAILED
    java.lang.AssertionError: doc 1 hit score vs explain() expected:<0.038817026> but was:<0.038817033>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:D4A91A568797343C]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:577)
        at org.apache.lucene.search.TestSynonymFreqSumOrder.testExplainEqualsHitScore(TestSynonymFreqSumOrder.java:57)
:lucene:core:test (FAILURE): 1 test, 1  failure
BUILD FAILED

# standalone runner: main 645d4fe14a20 jars and release jars 10.5.2 and 10.6.0, -ea and -da: FAIL 1/1, same message

# per-hit probe, same index and query (stock main, assertions off)
float: (0.2f + 0.2f) + 0.3f = 0.70000005    (0.2f + 0.3f) + 0.2f = 0.7
hit doc=0 score=0.038817033 explain=0.038817033 explainFreq=0.70000005
hit doc=3 score=0.038817033 explain=0.038817033 explainFreq=0.70000005
hit doc=1 score=0.038817026 explain=0.038817033 explainFreq=0.70000005
hit doc=2 score=0.038817026 explain=0.038817033 explainFreq=0.70000005
nextDoc path:          doc0=0.038817033 doc1=0.038817026 doc2=0.038817026 doc3=0.038817033
fresh advance(doc):    doc0=0.038817033 doc1=0.038817033 doc2=0.038817033 doc3=0.038817033

# with the recommended fix, gradle, -Ptests.seed=DEADBEEF
:lucene:core:test (SUCCESS): 1 test                  # the minimal test (and again with -Ptests.asserts=false)
:lucene:core:test (SUCCESS): 262 tests, 2 skipped    # TestSynonymQuery, TestCombinedFieldQuery, TestSimpleExplanations*, TestQueryBuilder, +LFV-277's test
:lucene:core:test (SUCCESS): 2342 tests, 49 skipped  # --tests 'org.apache.lucene.search.*' (216 classes)
# per-hit probe with the fix: all four hits, explain() and both paths 0.038817033

• A per-document contract. "it will match any of the terms but only invoke the similarity a single time, scoring the sum of all term frequencies for the document" (SynonymQuery.java:47-49).
• explain() == score, exactly, in Lucene's test framework. CheckHits.verifyExplanation asserts assertEquals(score, value, 0d) (CheckHits.java:393); it is the test framework's rule, not a public API promise. LUCENE-8008 (#9056, d27ddcb409d, 2017) made it exact and removed EXPLAIN_SCORE_TOLERANCE_DELTA, whose javadoc read "Some explains methods calculate their values though a slightly different order of operations from the actual scoring method".
• The max score is a bound. Scorer#getMaxScore returns "the maximum score that documents between the last target ... and upTo included" (Scorer.java:75-79); AssertingScorer.java:130 asserts score <= getMaxScore(docID()) once a caller has shallow-advanced the scorer. LUCENE-8652's second patch wrapped the boosted impacts "to scale the term frequency for max scores".
• Precedent. #12675 ("We generally prefer scores to not depend on the order of clauses ... sum up scores into a double") and PR #12682 (merged 2023-10-23) fixed this in MultiSimilarity and PassageScorer; DisjunctionSumScorer.score sums the same kind of topList in double (DisjunctionSumScorer.java:39-47).
• It worked before. Up to 8.0.0 SynonymScorer.freq() was an exact int sum; LUCENE-8652 (2019) made it a float sum when it added per-term boosts, and its discussion never mentions rounding, order or explain.
• Tests never reach it. testBoosts uses boosts 0.25, 0.5 and 1 with small freqs, which add exactly (TestSynonymQuery.java:222-280); testScores and testRandomTopDocs use exactly two terms (:178-220, :453-514), where float addition commutes.

The strongest case, from the refute review, the works-as-designed review and the devil's-advocate verifier: scoring is float arithmetic and no javadoc promises bit-identical scores across iteration paths; QueryUtils.checkSkipTo and checkFirstSkipTo tolerate 1e-5 and 1e-3 between nextDoc and advance (QueryUtils.java:356, :410) CheckHits.checkEqual tolerates 1e-6 between hit lists (CheckHits.java:223), and CheckHits.verifyExplanation allows 2 ulps per detail inside a "sum of" explanation ("TODO: remove this leniency", CheckHits.java:476-483); MIGRATE.md:852-856 says Lucene "does not guarantee identical scoring or document ranking behavior across major version upgrades"; maintainers have declined accuracy-only scoring work ("In general scoring doesn't focus on accuracy", #9547 / LUCENE-8501); and the bound part needs more than 2^24 occurrences.

Why it fails: this is consistency, not accuracy. The same document gets two scores from the same query on the same index, explain() reports a value the hit did not get, which is the exact rule LUCENE-8008 restored, and identical documents tie-break out of doc-id order. The tolerances cover only nextDoc/advance and hit-list comparisons and the inner sums of an explanation tree, not the top-level explain == score or score <= getMaxScore; MIGRATE.md is about upgrades, not one search; and the fix makes the score more accurate, not less (the correctly rounded sum for the repro operands; in general it greatly reduces the order dependence without removing it for every input). The refute review and the works-as-designed review rated the intended-behaviour argument weak; the devil's-advocate verifier called the nextDoc-vs-advance difference on its own tolerated but found the bug real, and the adjudication found no convincing not-real argument. Verdict: not intended, a defect, low priority.

Option A was built and run through gradle in a scratch worktree of 645d4fe14a20. B (a fixed term order in float) was tried by the independent reproducer and fixes the order symptom only; C (a fixed term order in double) is the strictly order-independent variant the adjudication named, not tried; D only documents the behaviour. Check the stale open PR #418, which moves mergeImpacts into shared code, for conflicts.

In SynonymQuery, DisiWrapperFreq.freq() returns (double) boost * pe.freq(), SynonymScorer.freq() accumulates in a double and returns (float) freq, and mergeImpacts computes (int) Math.ceil(freq * (double) boost) so the bound uses the same product as the score. In CombinedFieldQuery, CombinedFieldScorer.freq() does the same with (double) freq * weight and drops the freq < 0 overflow check, which a float or double sum never triggers. 2 files, +14/-11, formatted with ./gradlew :lucene:core:tidy.

// SynonymQuery.SynonymScorer
float freq() throws IOException {
  DisiWrapperFreq w = (DisiWrapperFreq) disjunctionDisi.topList();
  double freq = w.freq();
  for (w = (DisiWrapperFreq) w.next; w != null; w = (DisiWrapperFreq) w.next) {
    freq += w.freq();
  }
  return (float) freq;
}
// SynonymQuery.DisiWrapperFreq
double freq() throws IOException {
  return (double) boost * pe.freq();
}

Trade-offs

• Why it works. A float times an int below 2^29 is exact in double, and the sum of such products is exact whenever they fit one 53-bit window, which covers ordinary boosts and frequencies; an exact sum does not depend on the order, and rounding it once gives the correctly rounded float. The bound is an exact integer sum of per-norm impact freqs, each boosted one Math.ceil of the same double product and so never below it; it is therefore at least the exact sum, and since rounding is monotone it dominates the score's freq again.
• Not every possible input. As the adjudication and the intended-behaviour check put it, a double sum is exact for the repro operands but not order-independent for every possible input (for example boosts many binades apart); option C is the strictly order-independent variant.
• Scores change in the last bits, to the correctly rounded sum: in the repro the summed freq of docs 1 and 2 moves up 1 ulp (0.7 to 0.70000005) and their score 2 float ulps (0.038817026 to 0.038817033). Worth a CHANGES.txt line, since exact scores change.
• Cost. Double arithmetic per matching term per scored document; no benchmark was run.
• Review. No reviewer has read the diff line by line yet; #418 (stale, open) rewrites mergeImpacts and may conflict.

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle, seed DEADBEEF: the minimal test fails before the fix and passes after it, with assertions on and off.
• :lucene:core:test --tests TestSynonymQuery --tests TestCombinedFieldQuery --tests 'TestSimpleExplanations*' --tests TestQueryBuilder --tests TestCombinedFieldFreqSumOrder: 262 tests, 2 skipped, 0 failures (TestSynonymQuery 10, TestCombinedFieldQuery 14, TestSimpleExplanations* 3 x 70, TestQueryBuilder 26, and LFV-277's two-test repro TestCombinedFieldFreqSumOrder 2, copied into the scratch tree only for this check; the 2 skipped are in TestSimpleExplanationsWithFillerDocs).
• :lucene:core:test --tests 'org.apache.lucene.search.*': 216 classes, 2,342 tests, 49 skipped, 0 failures.
• The per-hit probe with the fix shadowed: all four hits, explain(), the nextDoc path and a fresh advance(doc) give 0.038817033.
• Earlier, the study's runs of the same SynonymQuery change: the finder's, the independent reproduction's and the intended-behaviour check's tests pass (the intended-behaviour check: 0 of 729 explain mismatches), and so does the 8.1.0 history shadow. Not run: the full core suite, :lucene:core:check, a benchmark.

Collect the matching wrappers, sort them by term index and add them in that order, in float.

Trade-offs

The independent reproducer's shadow of exactly this fixes the identical-documents and explain tests but not the max-score tests (2 of 5 still fail), because the float sum can still round above the exact integer bound above 2^24. It also costs a sort per scored document.

Accumulate each term's boost * freq in double in term-index order (for example into a small array indexed by term), then round once.

Trade-offs

The adjudication's strictly order-independent variant: the result never depends on the heap layout, for any input. Costs an array write and an ordered pass per scored document; not built or run.

Say in the javadoc that a SynonymQuery's score can differ by a few ulps depending on how the scorer reached the document.

Trade-offs

Leaves explain() disagreeing with the hit, against the exact rule of CheckHits.verifyExplanation, leaves identical documents out of doc-id order, and leaves the score above getMaxScore() in the 2^24 case. Not recommended.

Method: semi-formal (the hypothesis came from code reading while modelling; the lemma was posed as a counterexample search).

• A hunt unit (DisjunctionMax, Synonym and CombinedField queries) split SynonymQuery's merged-impacts bound into Z3 floating-point lemmas with a model-to-Java line map. Lemma S1 (boost 1, no size precondition) came back sat in 0.4 s: freqs 778,681,664 and 1,281,827,656 give a float sum of 1.9189989566802978515625 x 2^30, above the bound 1.91899883747100830078125 x 2^30. With the precondition "sum < 2^24" the same lemma is unsat. The witness became the public-API max-score test.
• The merge logic itself was checked bounded-exhaustively on the real mergeImpacts: 7,743,376 configurations, 0 failures (mutants killed).
• The order symptom came from the unit's differential baseline: QueryUtils.check reported explanation mismatches on three-term boosted SynonymQuery, and a random search over small indexes minimised it to a six-document test; the four-document test came later, from the independent reproducer.