Lucene104ScalarQuantizedVectorFormat returns different scores after merging

[thecoop]

Description

We've found a bug in Lucene104ScalarQuantizedVectorFormat where the scorer is returning different documents scores after merging segments together. The test case can be found here (on branch_10x)

Before merge, docs returned and scores are:

{0=3.5892557207262143E-5, 1=6.082725012674928E-4, 2=1.0}

After merge, docs returned and scores are:

{0=3.581063720048405E-5, 1=6.144083454273641E-4, 2=0.0}

Doc 2 (which matches the query vector), has changed from 1.0 to 0.0

This only occurs with the PACKED_NIBBLE encoding.

Version and environment details

Reproduces on main and branch_10x

[thecoop]

After further testing, the incorrect scores are also output when the vectors are all written to the same segment in the first place.

[benwtrent]

I need to try and replicate, but when I tried before, there wasn't any bug.

I expect the scores to be different, but all my testing indicated they were within 0.002, no major 1.0 shifting.

[benwtrent]

The key part is having a doc almost exactly the same as the query vector

Was able to replicate with that

[mccullocht]

I am able to reproduce so taking a look

[benwtrent]

Some further testing I have done:

• Unsigned byte still returns in the correct order, with its equivalent vector being ranked first, but its outside of 0.001 tolerance. Seven bit has correct order within that tolerance (so, more accurate than unsigned????)
• PACKED_NIBBLE returns a score of 0 for the exactly equal vector after merge (really weird)
• SINGLE_BIT_QUERY_NIBBLE: suffers similarly as packed_nibble, but doesn't return exactly zero.

This is for euclidean, haven't tried inner product yet.

This is the test I am running: https://github.com/apache/lucene/compare/branch_10x...benwtrent:lucene:trying-to-repeat-weirdness?expand=1

[mccullocht]

I also experience failure with SINGLE_BIT_QUERY_NIBBLE but the quantization is lossier so I'm focusing on PACKED_NIBBLE. This also reproduces on main so I've been working there.

Agreed that the exactly equal quantized vector thing is weird, I guess it's a result of quantization loss?

I also get a failure for UNSIGNED_BYTE on the identical vector but it returns a value that is slightly out of bounds near 1 rather than a near-zero value.

[benwtrent]

OK, this looks like floating point arithmetic. Not 100% sure how to fix. But here are the values I see on this "nearly equivalent" doc:

The resulting score ends up being -8, which is REALLY close to the perfect score of 0 (given the magnitudes of the values).

Basically, ALL the stored values are correct, all the corrections & vector values themselves are exactly the same. However, somewhere along the line, we end up with a rounding error that causes the score to under-shoot by -8.99

I do not think this is a format error. We just need to fix some math in the scorer to handle this "almost" equivalent case.

[benwtrent]

Making the following change fixes it. Need to think through if its ever valid for score to be negative and then we scale it to 0 without scaling it eagerly to 0 before hand.

      score =
          Math.max(
              queryCorrections.additionalCorrection()
                  + indexCorrections.additionalCorrection()
                  - 2 * score,
              0f);
      return 1f / (1f + score);

[benwtrent]

Similarly, it makes me think we need to change how the scaling for normalized dot-product works and switch it to return (1f + Math.max(score, -1f)) / 2f;

[mccullocht]

score as this point is the euclidean distance and I don't think it's ever valid for that value to be negative.

For normalized dot product we should be able apply both a min and a max to keep the value in bounds, right?

[benwtrent]

For normalized dot product we should be able apply both a min and a max to keep the value in bounds, right?

Anything below -1 indicates a rounding error that should be accounted for. Possibly it should have a maximum value of 1f to prevent rounding errors in the other direction.

It seems to me that applying the snapping earlier just fixes the issue for both.