OSQ quantized vector scores become NaN when a large component overflows the correction terms

Lucene's opt-in OSQ formats (Lucene104ScalarQuantizedVectorsFormat and Lucene104HnswScalarQuantizedVectorsFormat) rebuild each quantized score in float32 from four products of per-vector correction terms (Lucene104ScalarQuantizedVectorScorer.java:290-291). For a vector with one large centred component the products are each larger than Float.MAX_VALUE while their exact sum is not: they overflow to +Infinity and -Infinity and the sum is NaN. In the repro (16 dims, doc 0 = (-1e19, 0, ..., 0)) doc 0 scores NaN against its own vector and KnnFloatVectorQuery returns 0 hits; the float format returns doc 0 with score 1.0. NaN passes the bounds added by #15411, and exhaustive kNN drops the whole 64-vector batch whose maximum is NaN. One large positive outlier pulls the centroid so far that the other documents and an ordinary query all score NaN (99 of 100 at 1024 dims). With MAXIMUM_INNER_PRODUCT the per-segment centroid terms themselves can overflow, and one outlier made every score of a 301-document segment NaN (assertions off). Doing the arithmetic in double fixes the EUCLIDEAN case. Every release with these formats, 10.4.0 to 10.6.0, is affected. The inputs are extreme (the stored vector and the query both about 6e17 or more below the segment centroid at 1024 dims), so the priority is low.

1. Accepted input. KnnFloatVectorField checks only that the vector is non-null, non-empty and finite (non-zero for COSINE): KnnFloatVectorField.java:42-61, :105 via VectorUtil.checkFinite (VectorUtil.java:485-492). The query gets the same check (KnnFloatVectorQuery.java:97).
2. What OSQ stores. With doc 0 = (-1e19, 0, ..., 0) and doc 1 = 0, the centroid is (-5e18, 0, ...). OptimizedScalarQuantizer.scalarQuantize (OptimizedScalarQuantizer.java:197-236) centres doc 0 to (-5e18, 0, ...), picks the interval [-5e18, 0] and stores the code sum 3825 (15 components at code 255) and the squared norm 2.5e37. All finite.
3. The estimate (Lucene104ScalarQuantizedVectorScorer.java:283-291), all float32:

   float score =
       ax * ay * targetVectors.dimension() + ay * lx * x1 + ax * ly * y1 + lx * ly * qcDist;

For doc 0 against its own vector (ax = ay = -5e18, lx = ly = 5e18 / 255, x1 = y1 = 3825, qcDist = 975,375):

1. The bounds pass NaN. EUCLIDEAN computes qAdd + xAdd - 2*score and returns 1 / (1f + Math.max(score, 0f)) (:294-301); computed in double from the same float32 inputs the distance is about -1.4e30 (rounding residue), which Math.max clamps to 0, so the score would be 1.0 (fix A does this: doc 0 scores 1.0); but Math.max(NaN, 0f) is NaN. MIP/COSINE add qAdd + xAdd - centroidDP and return scaleMaxInnerProductScore or Math.clamp(score, -1, 1) (:305-315), both NaN for NaN (VectorUtil.java:444-449).
2. One NaN drops a batch. exhaustiveBulkScore collects a 64-ordinal batch (Lucene104ScalarQuantizedVectorsReader.java:87) only if scorer.bulkScore(...) > knnCollector.minCompetitiveSimilarity() (:390, :402). The default bulkScore returns the Math.max over the batch (RandomVectorScorer.java:47-54), NaN here, and NaN > x is false. The HNSW reader has the same test in its exhaustive branch (Lucene99HnswVectorsReader.java:396, :408), and the HNSW runs checked (2 and 100 documents) went through it: minCompetitiveSimilarity() was called only from lines 396 and 408, never from the graph searcher. Graph search tests each batch of neighbours the same way (HnswGraphSearcher.java:341-343); no run here exercised it with a NaN.
3. The MIP leg. centroidDP = VectorUtil.dotProduct(c, c) (Lucene104ScalarQuantizedVectorsWriter.java:173-174) and the per-vector correction x.c (OptimizedScalarQuantizer.java:203, :235) are float32 and stored. Once c.c exceeds Float.MAX_VALUE it is stored as +Infinity; x.c is signed and becomes +Infinity or -Infinity once |x.c| exceeds it (|x||c| above Float.MAX_VALUE is needed for that, not enough). The score is then Infinity - Infinity. One outlier can do that for the whole segment. With -ea the writer's dotProduct call fails its finiteness assertion at flush instead.

• EUCLIDEAN: the stored vector and the query must both sit far below the segment centroid, each with a centred component of about -sqrt(Float.MAX_VALUE / dim) or less (the same coordinate or different ones): the four products grow with the lower ends ax, ay of the two quantization intervals, which are large and negative only then. In the runs a vector far above the centroid scored finitely. The study measured the onset at spikes of 5.95e17 at 1024 dims, 2.4e18 at 64 dims and 1.35e19 at 2 dims (a 32-document construction; the centred component is about 31/32 of the spike).
• Which document is the outlier does not matter. A negative outlier queried with itself scores NaN (the repro). A positive outlier moves the centroid (the mean, Lucene104ScalarQuantizedVectorsWriter.java:815) up by spike / n, so the other documents and an ordinary query sit far below it: with 16 dims, doc 0 = (+1e19, 0, ..., 0), doc 1 = 0 and a zero query, doc 1 scores NaN and 0 hits come back (the float format: doc 1 at 1.0); with 1024 dims, 100 Gaussian documents and doc 0 [0] = +1e20, 99 of 100 scores are NaN for doc 7's vector and 0 hits come back, flat and HNSW, assertions on and off (the float format, assertions off: doc 7 at 1.0). With the spikes in different coordinates (doc 0 = (-1e19, 0, ...), doc 1 = (0, -1e19, 0, ...), doc 2 = 0, query = doc 1) doc 0 and doc 1 score NaN.
• The spike needed grows with the segment size n: +5e19 in the 100-document case gave no NaN.
• At 1024 dims with 100 documents and doc 0 [0] = -1e18, both OSQ formats returned top-10 = docs 64-73 for doc 0's vector; the float format returns docs 0-9 with doc 0 at 1.0.

• Who is exposed. Only the opt-in Lucene104 scalar-quantized formats, flat and HNSW; all five ScalarEncoding values fail the same way. The default codec uses the float Lucene99HnswVectorsFormat (Lucene104Codec.java:123). DOT_PRODUCT needs unit vectors and COSINE normalizes first, so neither reaches these magnitudes.
• EUCLIDEAN. The stored vector and the query both sit far below the segment centroid (a centred component of about -sqrt(Float.MAX_VALUE / dim) or less in each). That happens to a negative outlier queried with itself, and, when one large positive outlier pulls the centroid up, to every other document and an ordinary query. Every float-path quantity can still be finite. No assertion fires in the OSQ path, even with -ea.
• MAXIMUM_INNER_PRODUCT. c.c or |x.c| above Float.MAX_VALUE. One outlier is enough for the whole segment: an outlier with a component of 6e21, added to 300 Gaussian documents, made 301 of 301 quantized scores NaN, and an ordinary query returned 0 hits (assertions off). With -ea the flush fails on an assertion instead.
• Effect. Silent wrong results: NaN scores, and in exhaustive search each NaN vector and up to 63 neighbours in its batch are missing. With a positive outlier that is nearly the whole segment: 1024 dims, 100 documents, one component of +1e20, 99 of 100 scores NaN and 0 hits.
• Likelihood. Rare: the values are many orders of magnitude beyond ordinary embedding values, so in practice it takes corrupt or synthetic vectors (an assessment, not measured). Priority low.

The test sets the codec with TestUtil.alwaysKnnVectorsFormat(new Lucene104ScalarQuantizedVectorsFormat()) (default 8-bit encoding). Doc 0 = (-1e19, 0, ..., 0), doc 1 = all zeros; the query is doc 0's own vector. It asserts that FloatVectorValues.scorer(q).score() for doc 0 is finite and that KnnFloatVectorQuery(k=1) returns doc 0. With the float Lucene99HnswVectorsFormat the same test passes (score 1.0), and with a spike of -1e10 instead of -1e19 the OSQ test passes too. It also fails as a plain main() with a Lucene104Codec subclass and no test framework, and with both the Panama and the scalar vector provider. ./gradlew tidy rewraps the three lines longer than 100 columns (file lines 42, 55 and 57); nothing else changes.

cp $REPRO/TestScalarQuantizedEuclideanOverflow.java $LUCENE/lucene/core/src/test/org/apache/lucene/codecs/lucene104/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.codecs.lucene104.TestScalarQuantizedEuclideanOverflow -Ptests.seed=DEADBEEF -Ptests.asserts=true
# also with -Ptests.asserts=false

TestScalarQuantizedEuclideanOverflow > testLargeComponentGivesFiniteScore FAILED
    java.lang.AssertionError: expected doc 0 found with a finite score, but its score is NaN and the query found 0 hits
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:658935A03473404D]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.codecs.lucene104.TestScalarQuantizedEuclideanOverflow.testLargeComponentGivesFiniteScore(TestScalarQuantizedEuclideanOverflow.java:56)
:lucene:core:test (FAILURE): 1 test, 1  failure

# the same with -Ptests.asserts=false, and on the 10.4.0, 10.5.2 and 10.6.0 release jars (-ea and -da)
# with the recommended fix: BUILD SUCCESSFUL, 1 test, 0 failures

• Legal input. KnnFloatVectorField and KnnFloatVectorQuery check only finiteness; no magnitude limit is documented in the field, VectorSimilarityFunction, the OSQ format or the quantizer. MAXIMUM_INNER_PRODUCT "does not require normalization of the inputs. Should be used when the embedding vectors store useful information within the vector magnitude" (VectorSimilarityFunction.java:99-103). #12373 proposed rejecting components of 1e17 and more and was closed unmerged: "there's no consensus to impose this limit" (msokolov).
• The documented range. EUCLIDEAN maps the squared distance to a "similarity score in (0, 1]" (VectorUtil.java:465-476, used by VectorSimilarityFunction.java:35-39); the float format returns 1.0 for the same vectors. The float path has its own limit: its squared distance overflows once two vectors differ by more than about 1.8e19 in a coordinate, and then it scores 0 with assertions off and trips its finiteness assertion with -ea (VectorUtil.java:135). The repro stays below that (largest squared distance 1e38).
• Maintainers bound quantized scores on purpose. #15411 (mccullocht, merged 2025-11-07) added Math.max and Math.clamp at :301 and :314, saying out-of-bounds values are "more likely when the inputs are 'extreme' in the sense that they are very far from the segment-level centroid". Java's Math.max and Math.clamp return NaN for NaN.
• An exact self-match. In #12281 uschindler wrote "A query searching for the exact same vector (cosine=1) should return a valid score". The repro is that case for EUCLIDEAN.
• The older quantizer guards against it. ScalarQuantizer throws "Scalar quantizer does not support infinite or NaN values" (ScalarQuantizer.java:92-96, #13366); OSQ has no such guard.

Strongest case: the values are absurd for any embedding model. On #15408 benwtrent called that issue's extreme test values "pretty...extreme". On #15784 msokolov, asking whether a graph-search collector should also account for NaN, answered "no -- that's a matter for checking valid inputs". The OSQ formats and the scorer are @lucene.experimental (Lucene104ScalarQuantizedVectorsFormat.java:97, Lucene104HnswScalarQuantizedVectorsFormat.java:47, Lucene104ScalarQuantizedVectorScorer.java:39) and lossy by design. So maintainers may answer "outside the practical range".

Why it fails: the input checks Lucene has (the "valid inputs" check) accept these vectors, and the one proposal to reject them, #12373, was declined (it predates OSQ, so it says nothing about OSQ itself). The float format handles the tested inputs. The quantized path does not fail loudly: it returns NaN silently, with no assertion for EUCLIDEAN even with -ea, and takes other documents with it, up to 63 of a batch or, with a positive outlier, nearly the whole segment. A fix in the scorer is small and needs no format change. Verdict of every checker that ran code: a defect, low priority.

One fix was built and run in a scratch worktree of 645d4fe14a20 with gradle. Three alternatives were considered and not built; B and C address the MIP leg, D only limits the damage.

The four products and their sum, the EUCLIDEAN distance and the MIP/COSINE correction are computed in double. The EUCLIDEAN 1 / (1 + max(d, 0)) and the COSINE Math.clamp also run in double and their results are cast to float; for MIP the score is cast to float just before scaleMaxInnerProductScore, which takes a float. The stored corrections and the format are unchanged.

double score =
    (double) ax * ay * targetVectors.dimension()
        + (double) ay * lx * x1
        + (double) ax * ly * y1
        + (double) lx * ly * qcDist;
if (similarityFunction == EUCLIDEAN) {
  score =
      (double) queryCorrections.additionalCorrection()
          + indexCorrections.additionalCorrection()
          - 2 * score;
  return (float) (1 / (1 + Math.max(score, 0)));
}
// MIP/COSINE: the same (double) cast for the correction; then
// MIP: scaleMaxInnerProductScore((float) score); COSINE: (float) Math.clamp(score, -1, 1)

Trade-offs

• Fixes the repro (doc 0 now scores 1.0, like the float format), the study's 64-dim EUCLIDEAN spike (doc 0 = 1.0, 3 hits), its 130-document batch test (hits start at doc 0 again), and the positive-outlier and different-coordinate cases (the float format's scores). With one +1e20 component at 1024 dims it removes all NaN and 10 hits come back, but the ranking stays coarse (docs 1-10 tie at 1.0; the float format ranks doc 7 first): with the centroid pulled 1e18 away each vector's 8-bit interval spans about 1e18. That is quantization loss, not this NaN.
• Does not fix the MIP single-document case ({3e19, 1}: still NaN, 0 hits): centroidDP and the per-vector x.c are stored as float32 Infinity. In the 301-document MIP outlier case the 300 ordinary documents no longer score NaN but 0.0, and the outlier stays NaN, so the ranking is still wrong.
• Ordinary inputs: the same formula over the same float inputs (the stored corrections, and lx, ly still computed in float), rounded once at the end instead of after each float32 step. Scores usually change only in the last bits; where the terms cancel (as in #15408) today's float32 result can be off by more, and the fix's result differs from it by that much, nearer the formula's exact value. No reindexing.
• Cost: about 15 scalar double operations per scored vector (8 multiplications and 3 additions for the estimate, 3 to 6 more for the correction and the final step) plus the float-to-double conversions, outside the SIMD dot product of the codes; not benchmarked. In #12281 double math was rejected for the per-component SIMD loops; this is not in a loop, but expect the question.
• The same float32 expression in the read-only BBQ format (backward_codecs/lucene102/Lucene102BinaryFlatVectorsScorer.java:183) is left unchanged.

What the checks validated

• gradle, stock + test: fails with assertions on and off; + this fix: passes with assertions on and off.
• + this fix: the closest suites (codecs.lucene104.*, util.quantization.*, codecs.lucene99.*, TestRescoreTopNQuery*, TestFullPrecision*, TestKnn*, TestVectorSimilarity*, TestKnnGraph, TestHnswMergeAbort, TestFilterReadersForwardVectorPrefetch, TestColumnBatchVectorColumn): 32 suites, 592 tests, 19 skipped, 0 failures, with seed DEADBEEF and assertions on and with seed C0FFEE and assertions off.
• + this fix: the full :lucene:core:test, 8,898 tests, 322 skipped, 0 failures (assertions on); checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest pass.
• The study's 5-test class with this fix shadowed (assertions off): the 2 EUCLIDEAN tests and the dim-1 scan pass; testMipSingleDocLargeMagnitude still fails (NaN, 0 hits), and testOneOutlierDocBlastRadius still fails: its MIP half leaves the outlier at NaN and the rest at 0.0, and its EUCLIDEAN half (no NaN, on stock either) overlaps the float top-10 in 1 of 10, on stock as with the fix (quantization loss, not this NaN). Not run: other modules, nightly tests, benchmarks.
• The resolution probe (production codec, no test framework) with this fix shadowed, assertions on and off: P1 (the repro's inputs: doc 0 = 1.0), P2 and P3 (the float format's scores), P4 (no NaN), P5 (hits 0-4, as with the float format).

The MIP score adds q.c + x.c - c.c, and for vectors near the centroid the last two cancel. Storing (x - c).c per vector, instead of x.c next to a per-segment c.c, keeps that cancellation before anything is stored. The study's Z3 model found that re-associating as qAdd + (xAdd - cDP) makes the single-document dim-1 score exact when |x| < 2^64 and q - x is finite.

Trade-offs

Changes what the format stores (a new format version, back-compat for old segments), and the query-side q.c can still overflow for an extreme query. Neither built nor run.

Check that the correction products stay finite, in the spirit of the older ScalarQuantizer guard (#13366).

Trade-offs

The centroid is known only at flush, so the error would come at flush, not at addDocument; a field-level cap like #12373 was declined. It turns a silent wrong result into an error, for MIP too.

Make the exhaustive batch test ignore NaN scores, for example with a NaN-skipping maximum.

Trade-offs

Defence in depth only: the 63 neighbours come back, but the outlier's own score stays NaN.

Method: SMT (Z3) floating-point queries on a bit-precise model of quantizedScore for a dim-1, single-document MIP segment, built from the code of main 7cecf79523 (study experiment SMT-6, query M1, 23 s: witness x = 1.73 x 2^78). Query M2 proved that the quantized score is NaN only if x*x overflows or q - x or q*x is not finite. The study's independent verifier wrote its own 5-test JUnit, reproduced it on main and 10.5.2, found the EUCLIDEAN form (64 dims, one component -1e19, every float quantity finite), the 64-vector batch drop and the 301/301 MIP blast radius, and measured the thresholds per dimension. On 2026-10-29 a small sweep (2-16 dims, 2-4 documents) cut it down to the one-method test above.