BpVectorReorderer turns a zero centroid into NaN when half of a split's vectors cancel out

BpVectorReorderer (lucene/misc; main and branch_11x, unreleased; opt-in) renumbers documents so that similar vectors get nearby doc IDs. For DOT_PRODUCT and COSINE, computeCentroid sums a half's vectors and scales the sum by 1 / (float) Math.sqrt(VectorUtil.dotProduct(centroid, centroid)) with no zero check (BpVectorReorderer.java:279-281). When the vectors of a half cancel out exactly, for example 32 documents alternating (1, 0) and (-1, 0), the sum is (0, 0), the factor is Infinity and the centroid becomes (NaN, NaN). The next dot product with it trips Lucene's own finite-result assertion (VectorUtil.java:68-75): AssertionError: not finite: NaN from <[1.0, 0.0],[NaN, NaN]>. Through BPReorderingMergePolicy that error fails the merge and IndexWriter closes as a tragic event. With assertions off nothing throws and the doc map is a valid permutation, but the NaN biases leave that split in doc-ID order. The inputs are legal unit vectors with default settings; the class comment states no non-zero precondition for the centroid, and upstream fixed a closely related NaN-centroid assertion in another class as a bug (#15209 / #15213, where the centroid had zero samples). Skipping the normalization when the squared norm is 0 fixes it; no release contains the class.

1. Split. ReorderTask.compute splits a partition in half when each half has at least minPartitionSize documents (BpVectorReorderer.java:207-215; default 32, AbstractBPReorderer.java:25) and computes one centroid per half (:224-225). With 64 documents there is exactly one split, docs 0-31 against docs 32-63.
2. Centroid. computeCentroid (:267-283) adds up the half's vectors. EUCLIDEAN and MAXIMUM_INNER_PRODUCT then divide by the count (:278); DOT_PRODUCT and COSINE scale by 1 / (float) Math.sqrt(VectorUtil.dotProduct(centroid, centroid)) (:279-281). For docs 0-31 the sum is (0, 0): the dot product is 0, sqrt(0) is 0, 1/0 is Infinity, and vectorScalarMul (:481-485) multiplies each 0 by Infinity, which gives NaN.
3. Bias. computeBias (:564-574) returns dotProduct(vector, rightCentroid) - dotProduct(vector, leftCentroid).
4. Assertions on. VectorUtil.dotProduct(float[], float[]) asserts a finite result (VectorUtil.java:68-75). Doc 0, (1, 0), against the NaN centroid fails it: AssertionError: not finite: NaN from <[1.0, 0.0],[NaN, NaN]>, thrown from computeBias (:571) inside computeDocMap (:591).
5. On the merge path. BPReorderingMergePolicy catches only NotEnoughRAMException around computeDocMap (BPReorderingMergePolicy.java:133-146), and IndexWriter.merge hands any Throwable to tragicEvent (IndexWriter.java:5109-5113), which closes the writer.
6. Assertions off. Every bias is NaN, so gain (:324) and scale (:315) are NaN and the stop test 500 * gain <= scale (:336) is false. The selector compares biases with Float.compare, which treats NaN as equal to NaN, and breaks ties on doc ID (:353-357), so the split stays in doc-ID order. Recursion then continues where the halves are large enough (read; in the repro the 32-document halves are too small to split again), and the doc map is always a valid permutation.

The same line is reached after a round of swaps too, because centroids are recomputed from scratch after every round that moved documents (MAX_CENTROID_UPDATES = 0, :88, :240-248; read, not executed separately).

• Entry points. BPReorderingMergePolicy (forced merges were executed; natural merges are reordered too, since minNaturalMergeNumDocs defaults to 1, BPReorderingMergePolicy.java:46, read only), the public computeDocMap (executed), and the offline main() / reorderIndexDirectory tool (BpVectorReorderer.java:653-697, read only).
• What it takes. A half of a split, at least 32 documents with default settings, whose float32 vector sum has a squared norm of 0. In practice that is a sum that is exactly zero: antipodal pairs such as (1, 0) and (-1, 0), or v, v, v, -3v for COSINE. Learned embeddings essentially never cancel exactly; test fixtures and generated vectors can. Strictly, a non-zero sum whose square underflows does it too: 32 COSINE vectors (Float.MIN_VALUE, 0) sum to (4.5E-44, 0), whose squared norm is 0 (arithmetic checked through VectorUtil.dotProduct, not run through the reorderer); the recommended fix covers that too. EUCLIDEAN and MAXIMUM_INNER_PRODUCT divide by the count and are not affected: an executed EUCLIDEAN control passes; for MAXIMUM_INNER_PRODUCT this is from the code.
• With assertions on (most of Lucene's own test runs, and downstream test suites that enable them): computeDocMap throws, and a reordering merge fails and closes the writer. In an executed probe the 8 documents added after the last commit were lost (116 live documents instead of 124) and a fresh writer failed the same forced merge again; the last commit stayed intact and CheckIndex-clean, so the demonstrated loss is the changes since the last commit.
• With assertions off (the Java default): nothing throws, the merge succeeds, every document keeps its own vector, deletes stay deleted and CheckIndex is clean. The cancelling split is just not refined. On the repro's own 64 documents stock main (assertions off) and the fixed code both return the identity doc map, so nothing differs there; on another 128-document set (docs 0-63 alternate (0, 1) and (0, -1), the rest are 48 × (0, 1) and 16 × (1, 0)) the mean dot product of adjacent documents is -0.244 on stock main and 0.496 with the fix. The cost in compression or search speed was not measured.
• Not slower, in one probe. The NaN path stops early: 16,384 64-dimensional antipodal-pair vectors took 15.5 ms against 272 ms for random unit vectors, with 0 documents moved (medians of 3 runs on one machine).
• How likely. Rare. The searches found no upstream report or CI failure of this kind since the class was added in January 2025; a search cannot prove there is none.

The test sits in org.apache.lucene.misc.index next to the upstream TestBpVectorReorderer and uses only public API. It asserts only that a doc map comes back; the failure is Lucene's own assertion, whose message shows the NaN centroid. It failed at every seed tried (DEADBEEF, and 5EED1234 with 5 iterations). The reorderer's arithmetic uses no randomness, but LuceneTestCase randomizes the default codec behind new IndexWriterConfig(), and only these seeds were run.

It does not assert the effect with assertions off, because reorder quality is not part of the DocMap contract and on this data even the fixed code returns the identity order.

Not shown by this one test, all from the same line and executed elsewhere: the COSINE variant, the BPReorderingMergePolicy merge that closes the writer (isOpen() false, the AssertionError as tragic exception), and the unrefined split with assertions off.

As the regression test: the same test, for example as a new method of TestBpVectorReorderer. The comment on line 44 is over the 100-column limit, so ./gradlew tidy wraps it; nothing else changes. With that, :lucene:misc:check -x test (google-java-format, ecj lint, forbidden APIs) passes with the recommended fix.

cp TestBpVectorReordererZeroCentroid.java $LUCENE/lucene/misc/src/test/org/apache/lucene/misc/index/
cd $LUCENE && ./gradlew :lucene:misc:test --tests org.apache.lucene.misc.index.TestBpVectorReordererZeroCentroid -Ptests.seed=DEADBEEF -Ptests.asserts=true
# -Ptests.asserts=false: the test passes (nothing throws; the split is just not refined)

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=true
TestBpVectorReordererZeroCentroid > testHalfThatSumsToZero FAILED
    java.lang.AssertionError: not finite: NaN from <[1.0, 0.0],[NaN, NaN]>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:28C0EB26BD6F4DE9]:0)
        at org.apache.lucene.core@11.0.0-SNAPSHOT/org.apache.lucene.util.VectorUtil.dotProduct(VectorUtil.java:74)
        at org.apache.lucene.misc.index.BpVectorReorderer$ComputeBiasTask.computeBias(BpVectorReorderer.java:571)
        at org.apache.lucene.misc.index.BpVectorReorderer$ComputeBiasTask.compute(BpVectorReorderer.java:552)
        at org.apache.lucene.misc.index.BpVectorReorderer$ReorderTask.shuffle(BpVectorReorderer.java:313)
        at org.apache.lucene.misc.index.BpVectorReorderer$ReorderTask.compute(BpVectorReorderer.java:233)
        at org.apache.lucene.misc.index.BpVectorReorderer.computePermutation(BpVectorReorderer.java:627)
        at org.apache.lucene.misc.index.BpVectorReorderer.computeValueMap(BpVectorReorderer.java:606)
        at org.apache.lucene.misc.index.BpVectorReorderer.computeDocMap(BpVectorReorderer.java:591)
        at org.apache.lucene.misc.index.TestBpVectorReordererZeroCentroid.testHalfThatSumsToZero(TestBpVectorReordererZeroCentroid.java:45)

1 test completed, 1 failed

# gradle, same seed, -Ptests.asserts=false: :lucene:misc:test (SUCCESS): 1 test

• The class comment sets no non-zero precondition. BpVectorReorderer.java:57-75 derives the centroid as sum(v) / n. Its last sentence starts with the max-inner-product case and ends: "since all collinear vectors of whatever scale will generate the same partition for these angular scores, we are free to choose any scale and ignore the normalization factor" (:71-74). It says nothing about a zero sum, which has no direction to normalize; keeping it as a zero centroid is a natural convention, though the comment does not settle it.
• Legal input, default settings. (1, 0), (-1, 0) and (0, 1) are unit vectors, as the DOT_PRODUCT javadoc asks (VectorSimilarityFunction.java:52-58); KnnFloatVectorField's value checks reject non-finite components (KnnFloatVectorField.java:105) and, for COSINE, the all-zero vector (:53-56); its other checks cover null, empty and over-long vectors.
• The assertion predates the class. The finite-result assertion in VectorUtil.dotProduct came with #12281 (2023); #15213 (2025) only added its "not finite" message. The reorderer was written against it.
• Upstream treats this symptom as a bug. In #15209 a NaN centroid tripped the same assertion in the scalar-quantization writer. benwtrent wrote "it does smell like a bug. The centroid is nan", and msokolov, who also wrote BpVectorReorderer, answered "Seems like divide by zero when there are no samples. I'll post a fix". #15213 fixed that writer only. The zero centroid there came from an empty sample set, not from cancellation: a close precedent, not the same root cause.
• The merge policy avoids failing merges over reordering, for low RAM. Its javadoc: when reordering lacks RAM, "it simply skips reordering in order not to fail the merge" (BPReorderingMergePolicy.java:34-39). That covers only the out-of-RAM case: a hint of intent, not a contract for this one.
• No comment, test or discussion covers a zero sum. The upstream DOT_PRODUCT test uses random angles on the unit circle (TestBpVectorReorderer.java:272-310), so no half cancels; the #14097 review of computeCentroid was about a stray semicolon.

The strongest case for "not a bug": the failure is an assertion, so production (assertions off) never throws; the doc map is then a valid permutation and the DocMap contract promises no reorder quality; the data is degenerate (an exactly cancelling half of 32 or more vectors); and the class is unreleased and, in its author's words in #15219, "hasn't gotten a lot of real-world testing".

Why it fails: Lucene uses these assertions as invariants and runs most of its own tests with them on (about 75% of seeds by default), so legal input that trips one is a bug, as #15209 / #15213 show for the same assertion with a close mechanism (a centroid normalized with zero samples). The DocMap contract indeed promises no reorder quality, so the case rests on that invariant and on the effect with assertions off, which is not a designed fallback: it works only because Float.compare orders NaN and ties break on doc ID, and it skips refinement that the fixed code performs (-0.244 against 0.496 on the 128-document set). Degenerate but legal data lowers the priority, not the validity. GPT review lenses rated the intended argument weak; a later GPT fact check rated it moderate and still called it a bug, because of the effect with assertions off and the #15213 precedent.

One option was validated with gradle on 645d4fe14a20; a second was run as a data point; a third is a design question.

In computeCentroid, compute the squared norm once and scale only when it is positive, so a half whose vectors cancel keeps the zero centroid. A zero centroid adds 0 to every bias, so documents are placed by the other half's centroid alone and the split is still refined. This is the finder's guard.

case DOT_PRODUCT, COSINE -> {
  float norm2 = VectorUtil.dotProduct(centroid, centroid);
  // vectors that cancel out (e.g. v and -v) have no direction: keep the zero centroid
  // rather than scaling it by 1/0, which turns it into NaN
  if (norm2 > 0) {
    vectorScalarMul(1 / (float) Math.sqrt(norm2), centroid);
  }
}

Trade-offs

• Nothing changes for a half whose squared norm is positive: the same expression runs.
• When both halves are zero, gain and scale are 0 and the existing stop test ends the round.
• Matches the class comment ("free to choose any scale") and the "don't normalize" fix of #15213.
• Open PR #15430, which moves the class to core, copies the unguarded line and would need the same change.
• The guard targets a squared norm of 0, including a sum of tiny vectors whose square underflows. A squared norm that overflows to Infinity (very large COSINE vectors) is a separate edge it leaves as it is: with assertions on, VectorUtil.dotProduct(centroid, centroid) itself asserts; with them off the factor is 0 and the centroid becomes zero (arithmetic checked, not run through the reorderer).

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20: the repro fails on stock main with assertions on and passes with this fix, with -Ptests.asserts=true and =false.
• With the fix: TestBpVectorReorderer 8 tests, 0 failures; the whole lucene/misc suite 24 classes, 317 tests, 0 failures, 9 skipped; :lucene:misc:check -x test passes with the repro test in place once ./gradlew tidy has wrapped its long comment.
• Earlier runs of the same guard: an independent 4-test reproducer (DOT_PRODUCT, COSINE, merge path, EUCLIDEAN control) 4 of 4 with assertions on, and the merge in the integrity probe completes with assertions on.
• On the 128-document set it reorders the split that stock main leaves in doc-ID order (mean adjacent dot product 0.496 against -0.244).

Use sum(v) / n, the centroid the class comment derives, for DOT_PRODUCT and COSINE too. A zero sum then stays zero.

Trade-offs

Changes the centroids, and possibly the order, for DOT_PRODUCT and COSINE inputs whose two halves' mean vectors differ in length: the bias becomes dot(v, sumR / nR - sumL / nL) instead of dot(v, unit(sumR) - unit(sumL)). It would need a reorder-quality benchmark.

What the checks validated

Data point only: with this change the repro passes with assertions on and the 8 upstream TestBpVectorReorderer tests pass (gradle, seed DEADBEEF); no quality comparison was run.

Whether COSINE centroids should sum each document's normalized vector, so every document weighs the same, rather than the raw vectors.

Trade-offs

A separate change; untested. It does not remove the zero case by itself, because antipodal unit vectors still cancel.

Method: bounded-exhaustive translation validation (the study's "semi-formal" tier). The harness enumerated every segment of up to 7 documents, each with no vector or a 1-dimensional vector in {-1, 0, +1} (without 0 for DOT_PRODUCT and COSINE, which ask for unit or non-zero vectors), under all four similarity functions, with minPartitionSize 1 or 2 and maxIters 1 or 20, and checked each computeDocMap result from the stock main jar against the DocMap contract (a permutation of the live documents).

• With assertions on: 12,736 runs failed with AssertionError: not finite: NaN, for example the DOT_PRODUCT segment (-1), (1), (-1) with minPartitionSize 1, whose second half (1), (-1) sums to 0.
• With assertions off: 401,744 checks, 0 violations, 0 exceptions. So every doc map in this domain was valid; the defect is the NaN itself.

The finder then wrote a JUnit test with default settings (128 documents, computeDocMap and a reordering merge), which was later reduced to the one 64-document test above.