When segments merge, Lucene may reuse the biggest HNSW graph instead of building a new one, but never a graph more than 40% deleted (counted in whole percent, rounded down). The check that enforces this overflows int for graphs with more than 21,474,836 deleted vectors.
- Each segment of a vector field has its own HNSW graph: every vector is a node with links to a few nearby vectors.
- Building the merged segment's graph from scratch is slow. Since 10.4.0 the merge can start from an existing graph, the base: it drops the deleted nodes and repairs the nodes that lost links.
- A graph that lost many nodes repairs badly, so a graph more than 40% deleted (in whole percent) may not be the base. If no graph qualifies, the merge builds a new graph from the live vectors.
21,474,837 x 100 wraps to a negative int, the deleted share reads -97%, and the 97.6%-deleted graph passes the 40% check and becomes the merge base. Select the still to open it at full size. Generated with AI, checked against the code.- One segment holds 22,000,000 vectors in an HNSW field. A bulk delete removes 21,474,837 of them (97.6%), leaving 525,163, and the segment is merged, for example by
forceMergeDeletes()orforceMerge(1). - Before reusing a segment's graph, the merge computes
deletePct = ((graphSize - live) * 100) / graphSizeinint. Only a graph whosedeletePctis at most 40 (DELETE_PCT_THRESHOLD, in whole percent, rounded down) may be the base. - You expect 97% > 40%: no base, so the merge builds a fresh graph from the 525,163 live vectors.
- Instead 21,474,837 x 100 = 2,147,483,700 is above
Integer.MAX_VALUE(2,147,483,647) and wraps to -2,147,483,596, sodeletePctis -97. -97 <= 40 passes, and the merge copies, prunes and repairs the 22M-node graph. - No error. By code reading the merge still drops the deleted documents; the recall and merge-time cost is unmeasured. On 10.x (executed on 10.4.0, 10.5.2 and 10.6.0) the opt-in concurrent merger throws
ArrayIndexOutOfBoundsExceptionwhen such a base has no live vectors.
Only an index with one segment holding more than 21,474,836 deleted vectors in one HNSW field: a segment of 21.5M+ vectors, past the default 5 GB merge cap (built by forceMerge(1), a raised cap or addIndexes), merged after a bulk delete. Default codec on main and 10.5.1-10.6.0. Rare; the quality and merge-time cost is unmeasured.
Mechanism, terms and numbers940 words
Since 10.4.0 (#15003) a merge may start its HNSW graph from an existing segment's graph that has deletions: it drops the deleted nodes and repairs the rest. To keep badly connected graphs out, IncrementalHnswGraphMerger.addReader skips a graph whose deleted percentage is above DELETE_PCT_THRESHOLD = 40. It computes that percentage as ((graphSize - candidateVectorCount) * 100) / graphSize in 32-bit int, in whole percent rounded down (so a graph just under 41% deleted still reads 40 and stays eligible, as the upstream test oracle also computes; that is not this bug). Once a graph has more than 21,474,836 deleted vectors (Integer.MAX_VALUE / 100), the product overflows and deletePct is never above 33 for any graph size up to IndexWriter.MAX_DOCS, so deletePct <= 40 always passes: 22,000,000 nodes with 21,474,837 deleted gives -97, 30,000,000 with 25,000,000 deleted gives -59. The heavily deleted graph becomes the base, in either reader order against a cleaner graph with fewer live vectors, and also when it is the only segment in the merge, where the rule says to build a fresh graph from the live vectors. By code reading the merge still drops the deleted nodes and repairs the rest; the repro does not run the merge, and the recall and merge-time cost is unmeasured. On 10.x the opt-in concurrent merger additionally throws ArrayIndexOutOfBoundsException when the chosen base has no live vectors (executed on 10.4.0, 10.5.2 and 10.6.0; the same code is in every 10.4.0-10.6.0 release and branch_10_6); on main that path is gone since #16794 (executed), and branch_11x has the same sources as main. A one-line long widening fixes both. The repro drives the real merger with a stub segment; no index with more than 21.5 million vectors in one segment was built.
- Every merging segment reaches the check. On a merge,
Lucene99HnswVectorsWriter.buildAndWriteGraphcallsmerger.addReader(...)for every merging segment that has the field, thenmerger.merge(...)(Lucene99HnswVectorsWriter.java:510-525).createGraphMergerreturnsIncrementalHnswGraphMergerby default andConcurrentHnswMergeronly with a merge executor, or an intra-merge executor and more than one merge worker (:668-689;DEFAULT_NUM_MERGE_WORKER = 1,Lucene99HnswVectorsFormat.java:120).ConcurrentHnswMergerinheritsaddReaderunchanged. On main the default per-field reader is anHnswGraphProvider(PerFieldKnnVectorsFormat.java:198,:357-369), so default-codec graphs get here. - The rule.
DELETE_PCT_THRESHOLD = 40(IncrementalHnswGraphMerger.java:65), javadoc:57-64: "A value of 40 means that if more than 40% of the graph's original vectors have been deleted, the graph will not be selected as the base." The check works in whole percent, rounded down, so a graph just under 41% deleted reads 40 and stays eligible; the upstream test oracle uses the same expression (TestIncrementalHnswGraphMergerBaseSelection.java:119). That rounding is not this bug. - The overflow.
addReader(:110-147) counts live vectors (:128), takesgraphSize = graph.size()(:129) and computesint deletePct = ((graphSize - candidateVectorCount) * 100) / graphSize;(:133). The deleted count times 100 exceedsInteger.MAX_VALUEfrom 21,474,837 deleted vectors on. For 21,474,837 to 42,949,672 deleted vectors the product wraps exactly once to a negative number, sodeletePctis 0 or less (it can be 0: a 42,949,672-node graph with every vector deleted gives the product -96 anddeletePct0). With more deleted vectors the product can wrap to a positive number, butdeletePctthen stays at most 33 for any graph size up toIndexWriter.MAX_DOCS(computed: a positive product after k >= 1 wraps givesdeletePct< 50 / (k + 0.5); a check of every deleted count agrees), and an SMT query found passing graphs up to 100% deleted. - The guard passes.
if (deletePct <= DELETE_PCT_THRESHOLD && (largestGraphReader == null || candidateVectorCount > largestGraphReader.liveVectorCount)) largestGraphReader = graphReader;(:135-139). Any value the overflow produces (at most 33) satisfies the first half. With two segments, a heavily deleted big graph beats a clean smaller one in either reader order, because it still has more live vectors (the hunt's two-segment tests, executed). Below the overflow the check is exact: one deletion fewer (21,474,836, same live count) is rejected. - What the merge then does (code reading).
createBuilder(:157-177) builds from scratch only whenlargestGraphReader == null(:159-161). OtherwiseorderGraphReadersputs the base first, adding it although it has deletions (:187-192),getNewOrdMappingmaps its live nodes (:204-250), andMergingHnswGraphBuilder.fromGraphs(MergingHnswGraphBuilder.java:108) callsInitializedHnswGraphBuilder.initGraph(InitializedHnswGraphBuilder.java:187), whose builder runsinitializeFromGraph(:303-316): it copies the surviving structure, repairs disconnected nodes and rebalances the levels. The concurrent merger on main does the same throughpruneGraph(ConcurrentHnswMerger.java:77-101).getNewOrdMappingsizes its map and ordinal array for the base to the full graph (new IntIntHashMap(graphSize),new int[graphSize],:221,:229), here 22,000,000 entries. The repro never callsmerge(), so none of this step ran. - The 10.x crash path. In 10.6.0 and
branch_10_6,ConcurrentHnswMerger.getNewOrdMappingreturnsnew int[0]when the base has no live document (ConcurrentHnswMerger.java:161-163at 10.6.0), andcopyAndPruneGraphStructurethen readsnewOrdMap[oldOrd](InitializedHnswGraphBuilder.java:352there):ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0(executed at class level on 10.4.0, 10.5.2 and 10.6.0's release commit). #16794 (CHANGES 11.0.0) replaced that method with the shared one, which allocates a full-1-filled array, so on main the base choice is wrong but the merge completes (executed on645d4fe14a20);branch_11xhas the same sources, so it should behave the same (code reading). The samenew int[0]return is in every release from 10.4.0 to 10.6.0 (with the default codec 10.4.0 and 10.5.0 never pick a base, #16400). By code reading,IndexWritertreats the 10.x merge exception as tragic and closes the writer.
Exposure and likelihood396 words
- Who. Anyone with one segment that has more than 21,474,836 deleted vectors in one HNSW field, merged afterwards. Default codec and default merger on main,
branch_11xand 10.5.1-10.6.0; on 10.4.0 and 10.5.0 only with a vectors format that is not wrapped per field, because there the default per-field reader never reached the check (#16400, fixed by #16403 in 10.5.1). - How such a segment comes about. Not by default background merges at typical dimensions:
TieredMergePolicycaps merged segments at 5 GB (TieredMergePolicy.java:77), and 22M float vectors of 128 dimensions are already about 11 GB of vector data.forceMerge(1)lifts the cap (:789-791), as do a raisedmaxMergedSegmentMB, a custom merge policy oraddIndexes. A later bulk delete (for example by query on a tenant or a time range) can push that segment far over 40% deleted in one step. - The trigger is the merge after that (code reading).
forceMerge(1)rewrites every segment with deletions (:813);forceMergeDeletes()merges segments over 10% deleted (:81), and a segment bigger than the cap is merged alone; natural merges stop excluding a too-big segment once both its own and the index-wide deleted share exceeddeletesPctAllowed, 20% (:82,:383-385). The singleton merge is the simplest case: the rule says rebuild from the live vectors, Lucene reuses the 97.6%-deleted graph instead. - What it costs. The merge prunes and repairs exactly the kind of graph the guard was added to exclude. On a pre-merge revision of #15003 at 100k documents, reuse at 90% deletes cut recall from 0.961 to 0.562 (maxConn 16) for a 1.4x faster force merge. On today's repair code it is unmeasured. By code reading, deleted nodes are still dropped and search-time live docs and filters still apply; no run built, merged, reopened or searched such an index, so recall, merge time, memory and the merged index itself were not checked.
- The 10.x crash needs the opt-in concurrent merger, one 21.5M+-node segment whose vector documents are all deleted while other documents in it stay live (a fully deleted segment is dropped before the merge), and no cleaner graph in the same merge. Contrived, but loud.
- Scale. Rare: one segment of more than 21.5 million vectors (about 11 GB of vector data at 128 float dimensions); the memory and time to build and merge it were not measured here.
One JUnit test in org.apache.lucene.util.hnsw: it gives the default merger one stub segment of 22,000,000 vectors with the first 21,474,837 deleted and reads the chosen base, as the upstream base-selection test does. It is deterministic, single-threaded and needs no extra heap.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.lucene.util.hnsw;
import java.util.Collections;
import java.util.Map;
import org.apache.lucene.codecs.KnnVectorsReader;
import org.apache.lucene.codecs.hnsw.HnswGraphProvider;
import org.apache.lucene.index.ByteVectorValues;
import org.apache.lucene.index.DocValuesSkipIndexType;
import org.apache.lucene.index.DocValuesType;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.Float16VectorValues;
import org.apache.lucene.index.FloatVectorValues;
import org.apache.lucene.index.IndexOptions;
import org.apache.lucene.index.MergePolicy;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.search.AcceptDocs;
import org.apache.lucene.search.KnnCollector;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.util.FixedBitSet;
public class TestMergeBaseDeletePctOverflow extends LuceneTestCase {
public void testMostlyDeletedGraphIsNotMergeBase() throws Exception {
int size = 22_000_000;
int deleted = 21_474_837;
FixedBitSet liveDocs = new FixedBitSet(size);
liveDocs.set(deleted, size);
FieldInfo field =
new FieldInfo(
"v", 0, false, false, false, IndexOptions.NONE, DocValuesType.NONE,
DocValuesSkipIndexType.NONE, -1, Map.of(), 0, 0, 0, 1, VectorEncoding.FLOAT32,
VectorSimilarityFunction.EUCLIDEAN, false, false);
IncrementalHnswGraphMerger merger = new IncrementalHnswGraphMerger(field, null, 16, 100);
merger.addReader(new GraphReaderStub(size), doc -> doc, liveDocs);
// expected: no base graph, 97.6% > DELETE_PCT_THRESHOLD (40%); actual: this graph is the base
assertNull("97.6%-deleted graph chosen as merge base", merger.largestGraphReader);
}
private static final class GraphReaderStub extends KnnVectorsReader
implements HnswGraphProvider {
private final int size;
GraphReaderStub(int size) {
this.size = size;
}
@Override
public HnswGraph getGraph(String field) {
return new HnswGraph() {
@Override
public int size() {
return size;
}
@Override
public void seek(int level, int target) {
throw new UnsupportedOperationException();
}
@Override
public int nextNeighbor() {
throw new UnsupportedOperationException();
}
@Override
public int numLevels() {
throw new UnsupportedOperationException();
}
@Override
public int maxConn() {
throw new UnsupportedOperationException();
}
@Override
public int entryNode() {
throw new UnsupportedOperationException();
}
@Override
public NodesIterator getNodesOnLevel(int level) {
throw new UnsupportedOperationException();
}
@Override
public int neighborCount() {
throw new UnsupportedOperationException();
}
};
}
@Override
public FloatVectorValues getFloatVectorValues(String field) {
return FloatVectorValues.fromFloats(Collections.nCopies(size, new float[1]), 1);
}
@Override
public ByteVectorValues getByteVectorValues(String field) {
throw new UnsupportedOperationException();
}
@Override
public Float16VectorValues getFloat16VectorValues(String field) {
throw new UnsupportedOperationException();
}
@Override
public void search(String field, float[] target, KnnCollector c, AcceptDocs a) {
throw new UnsupportedOperationException();
}
@Override
public void search(String field, byte[] target, KnnCollector c, AcceptDocs a) {
throw new UnsupportedOperationException();
}
@Override
public void search(String field, short[] target, KnnCollector c, AcceptDocs a) {
throw new UnsupportedOperationException();
}
@Override
public void checkIntegrity(MergePolicy.OneMerge merge) {}
@Override
public void close() {}
}
}
./gradlew :lucene:core:test --tests org.apache.lucene.util.hnsw.TestMergeBaseDeletePctOverflow -Ptests.seed=DEADBEEF
- Expected
- No merge base (97.6% deleted is over the 40% limit), so the merge would build a fresh graph from the 525,163 live vectors.
- Observed
deletePctis -97 and the 97.6%-deleted graph is the base:expected null, but was:<GraphReader[... graphSize=22000000, liveVectorCount=525163]>, also with assertions off.
More files, environment, full output307 words
Put the file at lucene/core/src/test/org/apache/lucene/util/hnsw/TestMergeBaseDeletePctOverflow.java. It calls the public IncrementalHnswGraphMerger constructor and addReader with a FixedBitSet of live docs (2.75 MB) and a stub reader that reports only what addReader reads: the graph's size and 22M dense vectors (FloatVectorValues.fromFloats(Collections.nCopies(size, new float[1]), 1), O(1) memory). The chosen base is read from the protected largestGraphReader field from the same package, like TestIncrementalHnswGraphMergerBaseSelection. No randomness is used, so the seed does not matter.
The FieldInfo call and the class header are written compactly, so :lucene:core:checkGoogleJavaFormat flags them until ./gradlew tidy reformats them (the test runs as is). As a regression test it stays the same test: it fails before the fix and passes after it, in seconds.
The test observes base selection only, through the protected largestGraphReader field (an implementation-level check, as in the upstream base-selection test); it never calls merge(). Not covered by the repro (code reading only): building a real 22M-vector segment, a real IndexWriter merge of it, and what the reused graph does to recall. The test is written against main: on 10.6.x Float16VectorValues, the short[] search overload and checkIntegrity(MergePolicy.OneMerge) do not exist, so a backported test needs those overrides adapted.
| lucene | main 645d4fe14a20 (11.0.0-SNAPSHOT; branch_11x has the same HNSW code); the hunt's class-level tests also fail on 10.4.0, 10.5.0, 10.5.1, 10.5.2 and 10.6.0, and pass on 9.12.3 and 10.3.2 |
|---|---|
| jdk | OpenJDK 25.0.3 |
| os | Linux aarch64 |
# from a Lucene checkout ($LUCENE), with the test in lucene/core/src/test/org/apache/lucene/util/hnsw/
./gradlew :lucene:core:test --tests org.apache.lucene.util.hnsw.TestMergeBaseDeletePctOverflow -Ptests.seed=DEADBEEF
# assertions off fails the same way: add -Ptests.asserts=false
TestMergeBaseDeletePctOverflow > testMostlyDeletedGraphIsNotMergeBase FAILED
java.lang.AssertionError: 97.6%-deleted graph chosen as merge base expected null, but was:<GraphReader[reader=org.apache.lucene.util.hnsw.TestMergeBaseDeletePctOverflow$GraphReaderStub@..., initDocMap=org.apache.lucene.util.hnsw.TestMergeBaseDeletePctOverflow$$Lambda/...@..., graphSize=22000000, liveVectorCount=525163]>
at __randomizedtesting.SeedInfo.seed([DEADBEEF:563A6E29822FEC7B]:0)
at org.junit.Assert.fail(Assert.java:89)
at org.junit.Assert.failNotNull(Assert.java:756)
at org.junit.Assert.assertNull(Assert.java:738)
at org.apache.lucene.util.hnsw.TestMergeBaseDeletePctOverflow.testMostlyDeletedGraphIsNotMergeBase(TestMergeBaseDeletePctOverflow.java:53)
1 test completed, 1 failed
BUILD FAILED
# -Ptests.asserts=false: the same failure
# object hashes shortened- The javadoc: a graph more than 40% deleted "will not be selected as the base".
- Upstream tests assert the rule, but only at sizes where
intcannot overflow. - #15003 added the guard on purpose after reuse at 90% deletes cut recall from 0.961 to 0.562; overflow was never discussed.
The full argument260 words
- The rule is written down.
IncrementalHnswGraphMerger.java:57-64: "A value of 40 means that if more than 40% of the graph's original vectors have been deleted, the graph will not be selected as the base." - Tests assert it.
TestIncrementalHnswGraphMergerBaseSelection(:94-98): "The base must be a graph within the deletion threshold that has the most live vectors, or none if no graph is within the threshold" (segments of 10-200 docs,:104; its oracle uses the sameintexpression,:119).TestHnswMergeAbort(:63-67): "Every segment carries more thanIncrementalHnswGraphMerger#DELETE_PCT_THRESHOLDdeletions, so no source graph is eligible as a base and the merged graph is rebuilt from scratch viaHnswGraphBuilder#addVectors." (javadoc;{@code}shown as code). - Why the guard exists. In #15003, Pulkitg64 benchmarked reuse at 60-90% deletes on 100k documents: "With higher deletes we are regressing on recall with out any benefits on force merge time. This suggest it is required to add some guardrails" (2025-11-06; at 90% deletes and maxConn 16, recall 0.961 rebuilt vs 0.562 reused, force merge 1.4x faster; across 60-90% the speed-up was 0.96x-2.01x). benwtrent proposed "lets focus on 40% or fewer deleted total docs" (2025-11-07), and the author replied "Keeping this threshold at 40% now." Nobody in the PR's 79 discussion items mentions overflow,
longorInteger.MAX_VALUE. - Elsewhere Lucene uses floating point.
TieredMergePolicy.java:383:double segDelPct = 100 * (double) segSizeDocs.delCount / (double) segSizeDocs.maxDoc;. - The input is legal. Segments up to
IndexWriter.MAX_DOCS(Integer.MAX_VALUE - 128,IndexWriter.java:208) are allowed; no HNSW format or merger documents a smaller per-segment vector limit.
The devil's-advocate check204 words
The strongest case: IncrementalHnswGraphMerger is @lucene.experimental (:42) and DELETE_PCT_THRESHOLD is a package-private merge heuristic, not public API; the addReader javadoc (:105-108) still says a reader must not "contain any deleted vector", so the documentation is inconsistent anyway; the trigger needs more than 21.5 million deleted vectors in one segment, beyond the default 5 GB merge cap; and the merged graph is still valid and searchable.
Why it fails: every point is about severity, not intent. Nobody designs an int overflow; #15003 deliberately removed the old no-deletions rule and added the 40% guard after measuring recall losses; upstream tests treat the guard as an invariant; and the input is reachable through documented operations (forceMerge(1), a bulk delete, a merge). The severity points do bear on priority, which is why it is rated low. The no-deletions rule in the addReader javadoc is older than #15003; #15003 even reworded that sentence ("deleted docs" -> "deleted vector") but kept the rule its own change made stale (git blame: :106 is 3752dba9c51d, :107 is #15003's ef10476d98ab; a separate doc nit). Every verifier rejected the intended-behaviour reading; the cross-model reviews, the only ones that rate its strength, called it weak.
Recommended Compute the percentage in long
Widen the product to long: long deletePct = ((long) (graphSize - candidateVectorCount) * 100) / graphSize; (one line, IncrementalHnswGraphMerger.java:133; :138 on branch_10_6). The repro then passes with assertions on and off, 19 HNSW and codec suites (352 tests) pass, and the core static checks pass. It also removes the 10.x crash.
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
@@ -130,7 +130,7 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
GraphReader graphReader = new GraphReader(reader, docMap, graphSize, candidateVectorCount);
- int deletePct = ((graphSize - candidateVectorCount) * 100) / graphSize;
+ long deletePct = ((long) (graphSize - candidateVectorCount) * 100) / graphSize;
if (deletePct <= DELETE_PCT_THRESHOLD
&& (largestGraphReader == null
All options and trade-offs3 options ยท 364 words
Option A was built and validated in a scratch worktree of 645d4fe14a20; B and C were not run.
One line in IncrementalHnswGraphMerger.addReader. The same line is :138 on branch_10_6 and 10.6.0, so the 10.6.x backport is the same change.
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
@@ -130,7 +130,7 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
GraphReader graphReader = new GraphReader(reader, docMap, graphSize, candidateVectorCount);
- int deletePct = ((graphSize - candidateVectorCount) * 100) / graphSize;
+ long deletePct = ((long) (graphSize - candidateVectorCount) * 100) / graphSize;
if (deletePct <= DELETE_PCT_THRESHOLD
&& (largestGraphReader == null
Trade-offs
None at runtime: one long multiply per merging segment. It keeps today's truncating integer-percent semantics exactly, so graphs between 40% and 41% deleted stay eligible, as the upstream test oracle (TestIncrementalHnswGraphMergerBaseSelection.java:119) expects.
What the checks validated
- The repro fails without the fix and passes with it, with assertions on and with
-Ptests.asserts=false(Gradle, 2026-10-31). - 19 suites, 352 tests, 0 failures, 12 skipped, with the repro in place: all of
org.apache.lucene.util.hnsw(includingTestIncrementalHnswGraphMergerBaseSelection), all oforg.apache.lucene.codecs.lucene99,TestHnswMergeAbortandTestKnnGraph. ./gradlew :lucene:core:check -x testwith the fix alone passes (google-java-format, ecj lint, forbidden APIs).- Earlier, the hunt's focused tests (two segments in both orders, the exact boundary, singleton merges, 10.4.0 and 10.5.2, and the zero-live probe whose concurrent merge threw
ArrayIndexOutOfBoundsException) all pass with the same line: a 0-live graph is now 100% deleted and never the base.
if ((long) (graphSize - candidateVectorCount) * 100 <= (long) DELETE_PCT_THRESHOLD * graphSize ...), or the same in double like TieredMergePolicy.
Trade-offs
Matches the javadoc's "more than 40%" literally, but also rejects graphs 40-41% deleted, which today's code and the upstream random test's oracle accept; it needs a matching change to that oracle (:119).
In the 10.6 ConcurrentHnswMerger.getNewOrdMapping (:161-163 at 10.6.0), a base with no live document returns an empty map that the builder then indexes.
Trade-offs
With option A no such base is chosen, so this only matters for some other way of picking one. Main already removed the method in #16794.
Engines built on Lucene that let users bulk-delete and force-merge very large vector segments, or that turn on the concurrent HNSW merger on 10.x, inherit this; it changes merge work and possibly graph quality; by code reading it does not expose deleted documents or corrupt data.
Found while modelling HNSW merge-base selection: encoding the rule for a small-scope checker, the finder noticed the int product, and an SMT query (Z3) over the exact Java expression showed graphs more than 40% deleted passing the check. A JUnit on the real merger confirmed it, and independent verifiers reproduced it with their own tests.
The method in full130 words
A hunt unit on HNSW merge-time graph reuse was building a bounded-exhaustive harness for the base-selection rule ("the base has the most live vectors among graphs at most 40% deleted"). Its small scopes cannot reach the overflow, but writing the invariant down exposed the int product (2026-10-25). A Z3 4.12 query over the exact Java expression, with an explicit 32-bit wrap and IndexWriter.MAX_DOCS as the size bound, found "at least 41% deleted but eligible" satisfiable (up to 100% deleted), the same without wrap-around unsatisfiable, and "at most 40% deleted but rejected" unsatisfiable; the smallest witness has 21,474,837 nodes. A JUnit on the stock jars that drives the real IncrementalHnswGraphMerger.addReader with stub readers then failed on main (-ea, -da), 10.5.2 and 10.4.0, and passed with the one-line fix.
No prior report: GitHub issues, PRs and commits, downstream repos, four mailing lists, the JIRA archive and the web (150 query lines, 36 hits read, all 413 open PRs), searched 2026-10-26 and re-checked 2026-10-31. Closest: #15003, which introduced the line, and #16739, which reworked the next line.
Searches4 searches
Verdict new, confidence high. Related, not this bug: #15003 (introduced the line; a review comment on it was about counting deleted docs, not overflow), #16739 (reworked the comparison on the next line and kept the formula; its test oracle uses the same int expression), #16400/#16403 (the per-field reuse gap of 10.4.0-10.5.0), #16552/#16559 and #16618/#16627 (repair quality and speed of reused graphs), #16794 (removed the 10.x crash path on main as a side effect). No open PR changes the line (#16879, #16915, #16555, #16567, #16815 checked). Gaps: GitHub search is lexical; private reports are not visible.
| Where | When | How | Found |
|---|---|---|---|
| GitHub issues, PRs, comments and commits (apache/lucene) | 2026-10-26 | two runs of a scripted prior-report search plus 10 manual issue searches and 3 code searches; the body and every comment of 14 related PRs and issues grepped for overflow, 100L, (long), Integer.MAX, multiplyExact and deletePct; every issue and PR updated since 2026-09-15 | no report |
| Open PRs | 2026-10-26 | the changed files of all 413 open PRs | none changes the line |
| Mailing lists (dev@, java-user@, issues@, commits@), JIRA archive, web, downstream repositories | 2026-10-26 | per tool run 20 list, 4 JIRA and 2 downstream queries (plus 15 web queries in the second run), and 19 direct list searches | no report |
| GitHub re-check (apache/lucene) | 2026-10-31 | deletePct, DELETE_PCT_THRESHOLD, "IncrementalHnswGraphMerger overflow", "hnsw merge base deleted percentage"; diffs of the open PRs touching the merger | no report (hits: #15003, #15429, #16403, #16559, #16627 and an unrelated 2009 issue, #2613, LUCENE-1539); #16879, #16915, #16555, #16567, #16815 do not touch the line |
Introduced in 10.4.0 by #15003 (ef10476d98ab, merged 2025-12-01), which allowed reusing graphs with deletions and added the 40% guard with the int line. Executed: 10.4.0 to 10.6.0 and main fail; 9.12.3 and 10.3.2 pass. Not fixed upstream.
Versions tested6 rows
Introduced by #15003 "Avoid reconstructing HNSW graphs during segment merging." (Pulkitg64; merged by benwtrent on 2025-12-01; main ef10476d98ab, branch_10x backport 3e024479d358; CHANGES 10.4.0 Optimizations). Only these two commits add the line (git log -S 'deletePct' over all refs). From 9.9.0 to 10.3.2 addReader skipped every graph with any deletion, so no percentage existed. Swapping only IncrementalHnswGraphMerger.java between the 10.3.2 and 10.4.0 jars flips the result in both directions. Every later edit to the file on main kept it: #15874, #16368, #16383, #16620, #16627, #16739, #16794. Today: upstream main and branch_11x :133, branch_10_6 and 10.6.0 :138 (with the new int[0] crash path at ConcurrentHnswMerger.java:162); branch_10x was decommissioned on 2026-10-29 (#16911: "10.6 is the last minor release of the 10.x series").
| Version or commit | Verdict | Result |
|---|---|---|
main 645d4fe14a20, ea57360912ed | affected | the repro fails with -ea and -da; the zero-live concurrent merge throws on ea57360912ed and completes on 645d4fe14a20 (#16794) |
| branch_11x (11.0) | affected | same HNSW sources as 645d4fe14a20, line :133 [read] |
10.6.0 (4ae946e5a9b, as branch_10_6 RC1) | affected + crash | fails with -ea and -da; the concurrent merger throws ArrayIndexOutOfBoundsException for an all-deleted base; branch_10_6 has the same code [read] |
| 10.5.1, 10.5.2 | affected + crash | fail (default codec reaches the line again, #16403); 10.5.2 also throws in the concurrent merger |
| 10.4.0, 10.5.0 | custom codec only | fail at class level; with the default codec merges never reused graphs (#16400), so only a non-per-field vectors format reaches the line |
| 9.12.3, 10.3.2 | not affected | pass: a graph with any deletion is never the base |
A cross-model review (OpenAI GPT-5.6), an independent reproducer with its own test and the exact boundary, a works-as-designed adversary, an intended-behaviour devil's advocate and an adjudication: confirmed, high confidence. Re-verified on main 645d4fe14a20 and 10.6.0.
Checks and verdicts270 words
This doc's own runs (stock fail, fix pass with assertions on and off, 352 tests, core static checks) are under Suggested fix. This doc was then fact-checked twice on 2026-10-31 (an independent re-run of the repro, the fix and every file:line, and a cross-model fact check by OpenAI GPT-5.6); the corrections are applied.
| Check | Verdict | What it found |
|---|---|---|
| Cross-model review, refute lens | real, high | OpenAI GPT-5.6, refute lens: its own test at the first overflowing deleted count fails on main and passes with the fix; upstream TestIncrementalHnswGraphMergerBaseSelection passes with the fix. |
| Reproducer | real | Own JUnit in another package, two observation channels. 21,474,837 deleted is accepted, 21,474,836 (same live count) rejected; a 20%-deleted 25M graph is correctly chosen. Fails on main, 10.5.2 and 10.4.0; 10.3.2 passes; the fix passes 5 of 5. |
| Cross-model review, works-as-designed lens | real, high | OpenAI GPT-5.6, works-as-designed lens: own test fails on main and passes with the fix; intended-behaviour argument weak. |
| Intended-behaviour devil's advocate | real, minor | Own singleton-merge test (30M with 25M deleted; 22M with 21,474,837 deleted) fails on main and passes with the fix; built the devil's-advocate case. |
| adjudication | confirmed, high | Re-ran the independent reproduction's test with a new seed (-ea, -da) and diffed the fix source: only line 133 differs. |
| security screen | not security-sensitive | Found the zero-live variant: with the concurrent merger the merge throws ArrayIndexOutOfBoundsException (main before #16794, 10.4.0, 10.5.2). |
| re-verification | still reproduces | main 645d4fe14a20 and branch_10_6 RC1 (= 10.6.0), -ea and -da. |
| noise audit | one minimal test | Cut the evidence to one deterministic test of the default merger. |
The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.
- PNG 458 KB
Finding record, Lucene and upstream sources, repro files and diagram notes1,590 words
- Registry title
- HNSW merge computes a graph's deleted percentage in int, so a graph with more than 21,474,836 deleted vectors (41-100% deleted) passes the 40% DELETE_PCT_THRESHOLD and is reused as the merge base; in 10.4.0-10.6.0 and branch_10x the opt-in concurrent merger then throws ArrayIndexOutOfBoundsException for an all-deleted base (main since #16794, 11.0 only, rebuilds the graph instead)
- Area
- search / HNSW (merge-time graph reuse: IncrementalHnswGraphMerger base-graph selection)
- Priority
- Low, rank 915: The HNSW merge deleted-percentage overflows past 21.47M deleted vectors, so a mostly deleted graph is reused as the merge base (and the opt-in concurrent merger can crash), contrived scale.
- Impact class
- minor
- Impact note
- Anyone whose HNSW vector field has one segment with more than 21,474,836 deleted vectors (for example a 30M-vector segment after a bulk delete) and then merges it, with the default codec and merger on main and from 10.5.1: Lucene reuses that 41-100%-deleted graph as the merge base, or reuses it instead of rebuilding when the segment is merged alone, so the merge prunes and repairs exactly the kind of graph the 40% guard was added to exclude (the recall and merge-time cost of that is unmeasured; results stay valid approximate kNN and the index stays readable); with the opt-in concurrent HNSW merger (numMergeWorkers > 1, default 1) an all-deleted base additionally makes the merge throw ArrayIndexOutOfBoundsException (executed at class level; that IndexWriter then closes the writer as a tragic event is from code reading).
- Summary
- You merge an HNSW vector segment that has had most of its vectors deleted and expect Lucene to rebuild the graph or reuse a cleaner one, because the DELETE_PCT_THRESHOLD javadoc says a graph with more than 40% of its vectors deleted is never selected as the merge base. Once more than 21,474,836 vectors of one graph are deleted, the percentage ((graphSize - live) * 100) / graphSize overflows int and goes negative (-59 for 25M deleted out of 30M), so the guard passes and a graph that is up to 100% deleted becomes the base, in either reader order and also when the segment is merged alone. The default merger still finishes, pruning and repairing the reused graph. In 10.4.0 through 10.6.0 and branch_10x, and on main before #16794 (for example ea57360912ed), the opt-in concurrent merger throws ArrayIndexOutOfBoundsException for an all-deleted base; on main since #16794 (from a9779ef3c193; to be released in 11.0, not in 10.6.0) it rebuilds the graph, and only the wrong choice of merge base remains.
- Introduced
- ef10476d98ab37b92fe48a1f71a1a06dad009ae3 (main) and its branch_10x backport 3e024479d358e77ba7d802308b70ccb25ccf08c4, PR #15003 'Avoid reconstructing HNSW graphs during segment merging.' (author Pulkitg64, merged by benwtrent, CHANGES 10.4.0 Optimizations), which let graphs with deletions be reused and added DELETE_PCT_THRESHOLD = 40 with the int deletePct line [read: git log -S 'deletePct' over all refs of the history clone finds only these two commits, and git blame on main attributes the line to ef10476d98ab; exec: commit isolation at class level, swapping only IncrementalHnswGraphMerger.java between the 10.3.2 and 10.4.0 jars flips the result in both directions] (2025-12-01 (merged 22:14 UTC; the commit's author date is 2025-12-02 +0530; branch_10x backport committed 2025-12-01))
- First affected version
- 10.4.0 [exec, class level]; with the default per-field codec 10.5.1 [read: in 10.4.0 and 10.5.0 addReader returns before the percentage is computed for the per-field wrapper, #16400, fixed by #16403 in 10.5.1]; 10.3.2 is the last unaffected release [exec]
- Affected versions
- 10.4.0, 10.5.0, 10.5.1, 10.5.2, 10.6.0 (RC1 4ae946e5a9b, executed 2026-10-29, see 'Also' below) and main ea57360912ed. [exec, class level] the version-neutral history probe fails 3 of 5 and the canonical repro 2 of 3 on each of them (-ea and -da on 10.4.0, 10.5.2 and main); Also [exec 2026-10-29]: main 645d4fe14a2 and branch_10_6 RC1 4ae946e5a9b, the canonical repro 2 of 3 (-ea and -da). 9.12.3 and 10.3.2 pass 5 of 5 (-ea and -da). [read] 9.9.0 to 10.3.2 skip every graph with a deletion (noDeletes / hasDeletes) and have no percentage line; before 9.9.0 the writer skipped such segments too (9.8.0 read, not run); 9.9.0-9.12.2 and 10.0.0-10.3.1 were not run. Default codec: main since #15003 and releases from 10.5.1; in 10.4.0 and 10.5.0 only an HNSW format that is not per-field wrapped reaches the line (#16400) [read]. Zero-live ArrayIndexOutOfBoundsException variant [exec, class level]: main ea57360912ed (before #16794; gone on main from a9779ef3c193), 10.4.0, 10.5.2 and branch_10_6 RC1 4ae946e5a9b (-ea, -da; 2026-10-29); branch_10x 657014b3c57 [read: identical merger and builder files]; whether the #16400 gap blocks it in 10.4.0-10.5.0 with the default codec was not checked. Not fixed upstream: main 645d4fe14a2 :133 [exec 2026-10-29], branch_10x 657014b3c57 and branch_10_6 :138 still compute the int (read-only check 2026-10-26, re-read 2026-10-29). No physical index with more than 21,474,836 deleted vectors in one segment was built on any version.
- Status
- documented (brief, checks and a per-finding doc exist)
- Verification
- Confirmed by AI-run checks: an independent repro, a cross-model review that agreed, an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
- Found by
- semi-formal: Z3, code reading
- Upstream and prior reports
- none found (2026-10-26, verdict new, confidence high: two scripted prior-report searches, each with 16 GitHub issue/PR, 3 commit, 2 downstream-repo, 20 mailing-list (dev@, java-user@, issues@, commits@) and 4 JIRA queries, plus 15 web queries in run 2 that also cover the 6 left pending in run 1; 10 manual GitHub issue searches, 3 GitHub code searches (the code exists only in apache/lucene) and 2 downstream-repo searches; 19 direct mailing-list searches; the body and all comments of 14 related PRs and issues fetched and grepped for overflow, 100L, (long), Integer.MAX, multiplyExact and deletePct; the changed files of all 413 open apache/lucene PRs; every apache/lucene issue and PR updated since 2026-09-15 (402 items); 36 hits read, none the same bug; re-checked 2026-10-26 with gh search for deletePct and IncrementalHnswGraphMerger: no new item); not fixed: upstream main still has the int line at :133, branch_10x and branch_10_6 at :138, and no open PR changes it (#15208, #16794, #16815 and #16879 edit the file elsewhere); related, not reports of this bug: #15003 (introduced the line; a review comment on it concerned counting deleted docs, not overflow), #16739 (reworked the next line to compare live counts and kept the int formula; its test oracle uses the same int expression), #16400/#16403 (per-field reuse gap that limits default-codec exposure in 10.4.0-10.5.0), #16552/#16559 and #16618/#16627 (repair quality and speed of reused graphs); gaps: GitHub search is lexical, and private reports to security@lucene.apache.org are not visible
- Lucene commit tested
- main
645d4fe14a20(Gradle in a scratch worktree, assertions on and off, and the standalone JUnit runner); class-level runs on 9.12.3, 10.3.2, 10.4.0, 10.5.0, 10.5.1, 10.5.2, 10.6.0 (its release commit4ae946e5a9b, as branch_10_6 RC1) and mainea57360912ed; the recommended fix with 19 suites (352 tests) and the core static checks. OpenJDK 25.0.3, Linux aarch64, 2026-10-25 to 2026-10-31.
- Finding record
lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java:39-44 (@lucene.experimental), :57-65 (DELETE_PCT_THRESHOLD javadoc: 'if more than 40% of the graph's original vectors have been deleted, the graph will not be selected as the base'), :105-108 (stale addReader javadoc 'does not contain any deleted vector'), :133 (int deletePct = ((graphSize - candidateVectorCount) * 100) / graphSize), :135-139 (eligibility check and live-count comparison)lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java:156-158 (getNewOrdMapping returns new int[0] when the base has no live document) and InitializedHnswGraphBuilder.java:353 (newOrdMap[oldOrd], where the ArrayIndexOutOfBoundsException is thrown)lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java:518-524 (merger.addReader for every merge reader with the field) and :667-690 (createGraphMerger: ConcurrentHnswMerger only with a merge executor, or an intra-merge executor and more than one merge worker); Lucene99HnswVectorsFormat.java:120 (DEFAULT_NUM_MERGE_WORKER = 1); index/IndexWriter.java:208 (MAX_DOCS = Integer.MAX_VALUE - 128)lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:94-98 (the base must be within the deletion threshold, or none) and :119 (its oracle uses the same int expression) and src/test/org/apache/lucene/index/TestHnswMergeAbort.java:64-66 (segments above the threshold force a rebuild)read-only upstream check 2026-10-26: gh search issues deletePct and IncrementalHnswGraphMerger in apache/lucene (no item newer than 2026-10-22 on this code), and the contents API on main (line 133 still 'int deletePct')
- The finding in 30 seconds
lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java:57-65, (at 645d4fe14a20) :110-147 (:128, :129, :133, :135-139), :157-177, :187-192, :204-250lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java:303-316; (at 645d4fe14a20) util/hnsw/ConcurrentHnswMerger.java:77-101lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java:510-525, (at 645d4fe14a20) :668-689; codecs/lucene99/Lucene99HnswVectorsFormat.java:120; codecs/perfield/PerFieldKnnVectorsFormat.java:198, :357-369a Lucene clone releases/lucene/10.6.0 (4ae946e5a9b) lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java:161-163; InitializedHnswGraphBuilder.java:352lucene/CHANGES.txt:228 (at 645d4fe14a20) (GITHUB#16794 under 11.0.0)lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java:108; (at 645d4fe14a20) util/hnsw/InitializedHnswGraphBuilder.java:187, :303-316; util/hnsw/IncrementalHnswGraphMerger.java:221, :229; test util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:119a Lucene clone releases/lucene/10.4.0, 10.5.0, 10.5.1, 10.5.2, 10.6.0 lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java (return new int[0]: :129, :129, :147, :147, :162); IncrementalHnswGraphMerger.java:93 at 10.4.0 and 10.5.0 (early return for the per-field reader)
- Who is affected
lucene/core/src/java/org/apache/lucene/index/TieredMergePolicy.java:77, (at 645d4fe14a20) :81, :82, :383-385, :789-791, :813; index/TieredMergePolicy.java findForcedDeletesMerges (:925-977) and doFindMerges singleton handling (:550-571)lucene/CHANGES.txt (at 645d4fe14a20) (10.5.1 section, GITHUB#16400: "every merge rebuilt the graph from scratch")
- Minimal repro
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java (at 645d4fe14a20) (same-package read of largestGraphReader)
- Why it looks unintended
lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java:42, (at 645d4fe14a20) :57-65, :105-108lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:94-98, (at 645d4fe14a20) :104, :119; index/TestHnswMergeAbort.java:63-67lucene/core/src/java/org/apache/lucene/index/TieredMergePolicy.java:383; (at 645d4fe14a20) index/IndexWriter.java:208
- Suggested fix
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:119 (at 645d4fe14a20)a Lucene clone releases/lucene/10.6.0 (4ae946e5a9b) lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java:161-163; a Lucene clone origin/branch_10_6 IncrementalHnswGraphMerger.java:138
- History
a Lucene clone: git rev-parse releases/lucene/10.6.0^{commit} = 4ae946e5a9b; git show origin/branch_11x, origin/branch_10_6, releases/lucene/10.4.0-10.5.2 IncrementalHnswGraphMerger.java (deletePct line) and ConcurrentHnswMerger.java (new int[0]); origin/branch_10x README (#16911); git diff 645d4fe14a20 origin/branch_11x -- util/hnsw codecs/lucene99 (empty)
- Diagrams
lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java:57-65, (at 645d4fe14a20) :133, :135-139
- TestMergeBaseDeletePctOverflow.java (JUnit, one test):
repro/LFV-160/src/org/apache/lucene/util/hnsw/TestMergeBaseDeletePctOverflow.java(145 lines)
A picture of the mechanism, made in parallel with this doc from the code at 645d4fe14a20 and the minimal repro's numbers; the PNG is the summary still.
assets/LFV-160/bug.png(458 KB)