BayesianScoreQuery top-k pruning can skip a hit that is still competitive

BayesianScoreQuery (new in 10.5.0, @lucene.experimental) maps an inner query's score to a calibrated probability, sigmoid(alpha * (score - beta) + logit(baseRate)), returned as a float. Near 1 a whole range of inner scores rounds to the same float probability: for alpha=1, beta=0, every inner score from 4.9999995 to 5.000008 has probability 0.9933072.

Top-k search tells a scorer it may skip every document scoring less than the minimum competitive score, which TopScoreDocCollector sets to the next float above the current k-th score once more than 1,000 hits are collected. BayesianScoreScorer#setMinCompetitiveScore turns that probability into an inner-score threshold with the closed-form inverse (logit(minScore) - logitBaseRate) / alpha + beta. That is the inverse of the rounded probability, so it lands inside the range (5.000004 for 0.9933072), and the inner query skips inner scores that still have exactly the minimum competitive probability. Those documents are one float step better than the k-th hit, so the default IndexSearcher.search(query, n) silently returns the weaker hit. Even the exact real logit (5.0000036) is above the range's start, so a more precise inverse alone does not help; forwarding the smallest inner score whose probability, computed as score() computes it, reaches minScore (a binary search over float bits, 33 sigmoid evaluations per call that forwards a threshold) fixes it. It has been there since the class was added in #15827. On natural BM25 data it showed only under steep calibrations, with probabilities within about 1e-5 of 1.

1. Float forward function. score() is sigmoid(alpha * (innerScore - beta) + logitBaseRate) (:262-266), with sigmoid computed in double and cast to float (:113-120). Each float probability is the rounded image of a range of float inner scores, and the range widens towards 1: for alpha=1, beta=0, 6 floats at p=0.953, 19 at p=0.9933, 507 at p=0.99988.
2. The collector asks for the next float. Past 1,000 hits (IndexSearcher.java:100), TopScoreDocCollector calls scorer.setMinCompetitiveScore(Math.nextUp(topScore)): "since we tie-break on doc id and collect in doc id order, we can require the next float" (TopScoreDocCollector.java:156-162).
3. Closed-form inverse. For 0 < minScore < 1: clamped = Math.max(1e-7f, Math.min(1f - 1e-7f, minScore)), logitMin = (float) Math.log(clamped / (1f - clamped)), innerMin = (logitMin - logitBaseRate) / alpha + beta, in.setMinCompetitiveScore(Math.max(0f, innerMin)) (:286-290).
4. It lands inside the range. It inverts the rounded probability, not the range's lower end, so the inner scorer skips inner scores below it whose probability is exactly minScore (the independent reproduction: 972 of 1,956 such inner scores over 16 buckets).
5. The skipped hit is strictly better than the k-th, because minScore is the next float above the k-th probability. Nothing throws; totalHits becomes a lower bound.

Even the exact real logit is above the skipped hit's inner score, so a more precise inverse cannot fix it. In the last row the skipped hit's inner score is 0.12 higher, although the probabilities differ by one float step.

The same four lines hold LFV-164: the lower clamp at :287 raises the threshold when every competitive probability is below 1e-7. Its minimal fix (removing the clamp) leaves this bug; the fix recommended here fixes both.

• Who is hit. A BayesianScoreQuery at top level, or as the only scoring clause next to FILTER or MUST_NOT clauses (with MUST_NOT ReqExclScorer passes the threshold on, ReqExclScorer.java:89-91; with FILTER ConjunctionScorer forwards it to its single scoring clause, ConjunctionScorer.java:88-93; both executed), with the default IndexSearcher.search(query, n) or any TOP_SCORES collector. These are examples, not a complete list: by reading (not run), the threshold also reaches it as the optional clause next to a FILTER clause (ReqOptSumScorer.java:282-295) and inside a DisjunctionMaxQuery with tie-breaker 0 (DisjunctionMaxScorer.java:112-121); a conjunction with several scoring clauses does not forward it (BlockMaxConjunctionScorer.java:234-236). The error is in the query's own arithmetic, which does not depend on the codec; the runs covered only the codecs their test seeds picked.
• Fusion: a query fused through LogOddsFusionQuery, the use the class javadoc names (BayesianScoreQuery.java:28-30), is not affected where its fusion scorer runs: LogOddsFusionScorer.setMinCompetitiveScore only moves a block-boundary index and never calls the sub-scorers (LogOddsFusionScorer.java:214-218, DisjunctionScoreBlockBoundaryPropagator.java:104-109). A lone active signal is not shielded (by reading, not run for this bug): LogOddsFusionQuery hands its scorer straight to the collector (LogOddsFusionQuery.java:230-233) and rewrites to the clause itself when only one clause is left (:359-360, :393-394); LFV-164's executed fused-query probe fails through that path.
• Inner query. It must honour setMinCompetitiveScore: shown for constant-score clauses and WAND disjunctions, and on natural BM25 term and 2-3-term disjunction queries. Block-level pruning of a single TermQuery was not shown to trigger.
• What goes wrong. The k-th hit (the top hit for k=1) is replaced by one whose probability is one float step lower; the number of hits stays the same and nothing throws. Where the sigmoid saturates, the dropped hit's inner score can be clearly higher (15.5 against 15.382769).
• Scale. 1,002 documents in one segment are enough; 1,000 is the default totalHitsThreshold.
• Likelihood: rare. On synthetic natural-text BM25 indexes: 2 of 5,600 searches differed, both at alpha=3; 0 of 54,000 with BayesianScoreEstimator's own alpha or twice it, 45 of 18,000 at 4x that alpha (k-th probabilities within about 1e-5 of 1); 0 with the fix. One synthetic corpus each, so steeper hand-set calibrations or denser high scores may hit it more often; these are not real-world frequencies. Experimental class, new in 10.5.0; no prior report was found.

The test sits in the org.apache.lucene.search test package, as Lucene's own tests do, but uses no package-private member. The three SHOULD clauses BoostQuery(ConstantScoreQuery(TermQuery), x) give the fillers inner score 1.0, doc 1000 inner score 4.999999 and doc 1001 inner score 5.0. Four seeds give the same result.

As the regression test it needs one formatting edit: the doc.add(...) line is 101 characters, over google-java-format's 100, and ./gradlew tidy wraps it:

          doc.add(
              new StringField("f", i < 1000 ? "filler" : i == 1000 ? "a" : "b", Field.Store.NO));

With that edit and the fix in place, :lucene:core:check -x test (google-java-format, ecj lint, forbidden APIs, license checks) passes; the formatted test passes with the fix and fails on stock.

TestBayesianMinCompetitiveTies > testTopHit FAILED
    java.lang.AssertionError: score=0.9933071 expected:<1001> but was:<1000>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:13AC4067EA6145B7]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.apache.lucene.search.TestBayesianMinCompetitiveTies.testTopHit(TestBayesianMinCompetitiveTies.java:54)
:lucene:core:test (FAILURE): 1 test, 1  failure

# the same assertion with -Ptests.asserts=false, and on the 10.6.0, 10.5.2 and 10.5.0 release jars

# inside the search (probe on the same data shape, identical code):
stock: inner scores with probability 0.9933072: [4.9999995, 5.000008]
stock: requested minScores=[0.9933072] | forwarded inner thresholds=[5.000004]
fix:   requested minScores=[0.9933072, 0.99330723] | forwarded inner thresholds=[4.9999995, 5.0000086]

• The contract. "Tell the scorer that its iterator may safely ignore all documents whose score is less than the given {@code minScore}" (Scorable.java:46-47). The collector relies on it when it asks for the next float above the k-th score (TopScoreDocCollector.java:156).
• The class's tests. TestBayesianScoreQuery calls CheckHits.checkTopScores three times (:230, 333, 441). The oracle compares TOP_SCORES (pruning as soon as the queue is full) with COMPLETE hit by hit and, after setMinCompetitiveScore with a document's own score, asserts every skipped document scores < minScore (CheckHits.java:690-709, 748, 768-771). The three calls use a single TermQuery on a 53-document index with alpha=0.5 or the estimator's parameters, which do not aim at probabilities near 1, where the rounding ranges are wide.
• The author's intent. The #15827 description: "Since sigmoid is monotone, the original BM25 ranking is preserved exactly"; its test list names "WAND max score correctness". The code comment derives the threshold from an exact equation (:282-285). No javadoc, CHANGES, MIGRATE entry, test or review mentions approximate pruning.
• Lucene's practice. WANDScorer rounds max scores up and min scores down "to make sure that we do not miss any matches" (WANDScorer.java:85-88, 107-109); LongDistanceFeatureQuery and LatLonPointDistanceFeatureQuery binary-search their threshold (:270-271, :284-285; LUCENE-8340, and LUCENE-8482 where a reviewer agreed "that binary searching is easier than inverting the distance computation"). #13371, a top-k mismatch from float summation, was fixed by #13397.

The strongest case (built by the intended-behaviour check and the adjudication): the class is @lucene.experimental, which in #15827 a reviewer said "allows the API or behavior to change if we deem it necessary after more testing within Lucene"; the O(1) closed-form inverse is deliberate, its clamps show the author thought about numerical extremes, and the miss is the smallest possible: one float step of probability.

Why it fails: experimental lets the API change; it does not license TOP_SCORES results that differ from COMPLETE, which the class's own tests forbid. Lucene treats this kind of rounding miss as a bug elsewhere and solved it with a binary search, and near saturation one probability step can hide a clear gap in inner score. It argues for low priority, not for intended behaviour.

The recommended fix was run in a scratch worktree of 645d4fe14a20 (OpenJDK 25.0.3), removed afterwards. "Closest suites" means TestBayesianScoreQuery and TestLogOddsFusionQuery, the only tests that use the class, plus the repro. If open PR #16410 (same method, divides minScore by the boost) lands first, probability() must compare exactly what score() then returns.

Replace the closed-form inverse with a binary search over the bit patterns of the non-negative floats for the smallest inner score whose probability, computed exactly as score() computes it, is >= minScore. The finder's fix logic, rebased on 645d4fe14a20 with a rewritten comment (+29/-8 lines). It also removes the 1e-7 clamp, so it fixes LFV-164 too.

    // the probability of an inner score, computed exactly as score() computes it
    private float probability(float innerScore) {
      return sigmoid(alpha * (innerScore - beta) + logitBaseRate);
    }

    @Override
    public void setMinCompetitiveScore(float minScore) throws IOException {
      // Many inner scores round to the same float probability, so the closed-form inverse of
      // minScore can land inside that range and skip inner scores whose probability equals
      // minScore. Forward instead the smallest non-negative inner score whose probability is
      // >= minScore: probability() is non-decreasing in the inner score, so binary search over
      // the bit patterns of the non-negative floats finds it.
      if (minScore > 0f && minScore < 1f) {
        if (probability(0f) >= minScore) {
          return; // every inner score is competitive
        }
        if (probability(Float.MAX_VALUE) < minScore) {
          in.setMinCompetitiveScore(Float.MAX_VALUE);
          return;
        }
        // invariant: probability(lo) < minScore <= probability(hi), as float bit patterns
        int lo = 0;
        int hi = Float.floatToIntBits(Float.MAX_VALUE);
        while (hi - lo > 1) {
          int mid = (lo + hi) >>> 1;
          if (probability(Float.intBitsToFloat(mid)) >= minScore) {
            hi = mid;
          } else {
            lo = mid;
          }
        }
        in.setMinCompetitiveScore(Float.intBitsToFloat(hi));
      }
    }

Trade-offs

• Cost: 33 sigmoid evaluations (Math.exp) per setMinCompetitiveScore call that forwards a threshold, instead of one Math.log: two bound checks plus 31 bisection steps (Float.floatToIntBits(Float.MAX_VALUE) is 2,139,095,039). Calls happen when the minimum competitive score increases (the collector's own k-th score, or with several slices the global minimum, TopScoreDocCollector.java:99-100, 137-164), not per document; no benchmark was run. The distance-feature queries sample their calls for this kind of cost (LUCENE-8482).
• Soundness rests on monotonicity and on non-negative inner scores (Lucene's scoring convention, which the stock Math.max(0f, innerMin) also relies on; Scorable does not state it as a rule): alpha * (x - beta) + logitBaseRate is non-decreasing in x for alpha > 0, and sigmoid was checked non-decreasing over all 4,278,190,079 adjacent finite float pairs on the real jar. The threshold is then the tightest one that never skips a document with probability >= minScore, and it grows with minScore, as successive calls require.
• The probability(Float.MAX_VALUE) < minScore branch is defensive: it is reachable only with an extremely small legal alpha (for example alpha = 1e-38f, where alpha * Float.MAX_VALUE is about 3.4), and no run exercised it.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20: stock fails the repro with assertions on and off; with the fix it passes with assertions on and off.
• Closest suites with the fix, seeds DEADBEEF and 5EEDF00D: 67 tests pass (TestBayesianScoreQuery 26, TestLogOddsFusionQuery 40, the repro 1); stock passes the same 66 upstream tests. Not run: the full core suite, other JDKs and x86.
• :lucene:core:check -x test passes with the fix and the formatted regression test in place.
• With the fixed class shadowed into the main jars: the finder's two tests pass; the independent reproducer's three tests pass (0 of 1,956 tied inner scores skipped, 0 of 16 top hits differ, 0 of 16 checkTopScores failures; stock 972, 13 and 13); LFV-164's minimal test passes.
• The finder's bounded-exhaustive check with the same logic: 0 counterexamples in 293,213,101 checks (every float inner score in [2^-3, 2^5) whose probability is strictly between 0 and 1, for 5 parameter sets; 104,478,882 on stock).

Start from today's innerMin, gallop down (or up) with probability() checks until the lower end of the range is bracketed, then binary-search inside the bracket. Usually fewer sigmoid evaluations than the recommended fix, with the same correctness argument; more code. Not run.

Invert the lower edge of the probability's rounding interval and step down a few nextDowns.

Trade-offs

Every float operation in score() rounds, so the margin needed is hard to prove (the lesson of LUCENE-8340). A sketch of this kind (double-precision inversion plus two nextDown steps) still fails this repro and leaves 50,655,235 of 293,213,101 bounded-exhaustive counterexamples. Stepping down one float at a time until the next lower float drops below minScore passes every repro, but near 1 the range spans hundreds to millions of floats, so that loop is unbounded in practice.

Method: semi-formal (the finder's label): instrumented bounded translation validation, then a bounded-exhaustive check on the real jar; not a proof.

• Harness BoundTV ran seven protocols over many scorers and parameter sets; two of them flagged this class: P_C (after setMinCompetitiveScore(m) every document with score >= m is still returned) and P_D (TOP_SCORES top-k equals COMPLETE top-k). For this class it reported 64,583 P_C skips and 71 top-k differences, not split by mechanism.
• BayesInversionExhaustive then ran the real BayesianScoreScorer on every float inner score in [2^-3, 2^5) whose probability is strictly between 0 and 1 (those that round to 0 or 1 are skipped), for 5 parameter sets, each fed through a one-document probe, checking that an inner score whose probability equals minScore is not skipped: 104,478,882 counterexamples of 293,213,101 on main, 50,655,235 with LFV-164's fix sketch, 0 with this bug's fix.
• The finder read the root cause in the code and wrote a deterministic public-API JUnit; an independent reproducer wrote its own test from the claim alone.